\usepackage{multirow}\r
\usepackage{graphicx}\r
\usepackage{url}\r
+\usepackage{dsfont}\r
+\r
\r
\def\newblock{\hskip .11em plus .33em minus .07em}\r
\r
\section{Convergence results}\r
\label{sec:04}\r
\r
+%%NEW\r
+\r
+\r
+We suppose in this section that GMRES($m$) is used as solver in the TSIRM algorithm applied on a complex matrix $A$.\r
+Let us denote $A^\ast$ the conjugate transpose of $A$, and let $\mathfrak{R}(A)=\dfrac{1}{2} \left( A + A^\ast\right)$, $\mathfrak{I}(A)=\dfrac{1}{2i} \left( A - A^\ast\right)$. \r
+\r
+\subsection{$\mathfrak{R}(A)$ is positive}\r
+\r
+\begin{proposition}\r
+\label{positiveConvergent}\r
+If $\mathfrak{R}(A)$ is positive, then the TSIRM algorithm is convergent.\r
+\end{proposition}\r
+\r
+\r
+\begin{proof}\r
+If $\mathfrak{R}(A)$ is positive, then even if $A$ is complex, it is possible to state that \r
+the GMRES algorithm is convergent, see, \emph{e.g.},~\cite{Huang89}. In particular, its residual norm\r
+decreases to zero.\r
+\r
+At each iterate of the TSIRM algorithm, either a GMRES iteration is realized or a least square\r
+resolution (to find the minimum of $||b-Ax||_2$ is achieved on the linear span of the iterated approximation vectors \r
+$span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$\r
+of the last GMRES stage,\r
+where\r
+$\operatorname{span}(S) = \left \{ {\sum_{i=1}^k \lambda_i v_i \Big| k \in \mathbb{N}, v_i \in S, \lambda _i \in \mathbb{R}} \right \}$.\r
+\r
+Obviously, the minimum of $||b-Ax||_2$ on the set $span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$ \r
+is lower than or equal to $||b-Ax_k||_2$, which is the last obtained GMRES-residual norm. So we can\r
+conclude that the intermediate stage of least square resolution inserted into the GMRES algorithm\r
+does not break the decreasing to zero of the GMRES-residual norm. \r
+\r
+In other words, the TSIRM algorithm is convergent.\r
+\end{proof}\r
+\r
\r
-We can now claim that,\r
+Regarding the convergence speed, we can claim that,\r
\begin{proposition}\r
\label{prop:saad}\r
-If $A$ is either a definite positive or a positive matrix and GMRES($m$) is used as a solver, then the TSIRM algorithm is convergent. \r
+If $A$ is a positive matrix, then the convergence of the \r
+TSIRM algorithm is linear. \r
\r
-Furthermore, let $r_k$ be the\r
-$k$-th residue of TSIRM, then\r
+Furthermore, let $r_k$ be the $k$-th residue of TSIRM, then\r
we have the following boundaries:\r
-\begin{itemize}\r
-\item when $A$ is positive:\r
\begin{equation}\r
||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| ,\r
\end{equation}\r
-where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$;\r
-\item when $A$ is positive definite:\r
-\begin{equation}\r
-\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|.\r
-\end{equation}\r
-\end{itemize}\r
-%In the general case, where A is not positive definite, we have\r
-%$\|r_n\| \le \inf_{p \in P_n} \|p(A)\| \le \kappa_2(V) \inf_{p \in P_n} \max_{\lambda \in \sigma(A)} |p(\lambda)| \|r_0\|, .$\r
+where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$.\r
\end{proposition}\r
\r
\begin{proof}\r
-Let us first recall that the residue is under control when considering the GMRES algorithm on a positive definite matrix, and it is bounded as follows:\r
-\begin{equation*}\r
-\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{k/2} \|r_0\| .\r
-\end{equation*}\r
-Additionally, when $A$ is a positive real matrix with symmetric part $M$, then the residual norm provided at the $m$-th step of GMRES satisfies:\r
+Let us first recall that, when $A$ is a positive real matrix with symmetric part $M$, then the residual norm provided at the $m$-th step of GMRES satisfies:\r
\begin{equation*}\r
||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,\r
\end{equation*}\r
-where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}, which proves \r
-the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$.\r
+where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}.\r
These well-known results can be found, \emph{e.g.}, in~\cite{Saad86}.\r
\r
We will now prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, \r
-$||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||$ when $A$ is positive, and $\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|$ when $A$ is positive definite.\r
+$||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||$ when $A$ is positive.\r
\r
The base case is obvious, as for $k=1$, the TSIRM algorithm simply consists in applying GMRES($m$) once, leading to a new residual $r_1$ that follows the inductive hypothesis due to the results recalled above.\r
\r
-Suppose now that the claim holds for all $m=1, 2, \hdots, k-1$, that is, $\forall m \in \{1,2,\hdots, k-1\}$, $||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$ in the positive case, and $\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|$ in the definite positive one.\r
+Suppose now that the claim holds for all $m=1, 2, \hdots, k-1$, that is, $\forall m \in \{1,2,\hdots, k-1\}$, $||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$.\r
We will show that the statement holds too for $r_k$. Two situations can occur:\r
\begin{itemize}\r
-\item If $k \not\equiv 0 ~(\textrm{mod}\ m)$, then the TSIRM algorithm consists in executing GMRES once. In that case and by using the inductive hypothesis, we obtain either $||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_{k-1}||\leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$ if $A$ is positive, or $\|r_k\| \leqslant \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{m/2} \|r_{k-1}\|$ $\leqslant$ $\left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_{0}\|$ in the positive definite case.\r
+\item If $k \not\equiv 0 ~(\textrm{mod}\ m)$, then the TSIRM algorithm consists in executing GMRES once. In that case and by using the inductive hypothesis, we obtain either $||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_{k-1}||\leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$.\r
\item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies:\r
-\begin{itemize}\r
-\item $||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_{k-1}||\leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$ in the positive case, \r
-\item $\|r_k\| \leqslant \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{m/2} \|r_{k-1}\|$ $\leqslant$ $\left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_{0}\|$ in the positive definite one,\r
-\end{itemize}\r
+$$||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_{k-1}||\leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$$\r
and a least squares resolution.\r
Let $\operatorname{span}(S) = \left \{ {\sum_{i=1}^k \lambda_i v_i \Big| k \in \mathbb{N}, v_i \in S, \lambda _i \in \mathbb{R}} \right \}$ be the linear span of a set of real vectors $S$. So,\\\r
$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$\r
& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\\r
& \leqslant ||b-Ax_{k}||_2\\\r
& = ||r_k||_2\\\r
-& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \textrm{ if $A$ is positive,}\\\r
-& \leqslant \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_{0}\|, \textrm{ if $A$ is}\\\r
-& \textrm{positive definite,} \r
+& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \\\r
\end{array}$\r
\end{itemize}\r
which concludes the induction and the proof.\r
\end{proof}\r
\r
+\r
+\r
+\subsection{$\mathfrak{R}(A)$ is positive definite}\r
+\r
+\begin{proposition}\r
+\label{prop2}\r
+Convergence of the TSIRM algorithm is at least linear when $\mathfrak{R}(A)$ is \r
+positive definite. Furthermore, the rate of convergence is lower \r
+than $$\min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}}; \r
+\left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ,$$\r
+where ${\lambda_{min}^{X}}$ (resp. ${\lambda_{max}^{X}}$) is the lowest (resp. largest) eigenvalue of matrix $X$.\r
+\end{proposition}\r
+\r
+\r
+\begin{proof}\r
+If $\mathfrak{R}(A)$ is positive definite, then it is positive, and so the TSIRM algorithm\r
+is convergent due to Proposition~\ref{positiveConvergent}.\r
+\r
+Furthermore, as stated in the proof of Proposition~\ref{positiveConvergent}, the GMRES residue is under control \r
+when $\mathfrak{R}(A)$ is positive. More precisely, it has been proven in the literature that the residual norm \r
+provided at the $m$-th step of GMRES satisfies:\r
+\begin{enumerate}\r
+\item $||r_m|| \leqslant \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}} ||r_0||$, see, \emph{e.g.},~\cite{citeulike:2951999}, \r
+\item $||r_m|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}} ||r_0||$, see~\cite{ANU:137201},\r
+\end{enumerate}\r
+which proves the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$.\r
+\r
+We will now prove by a mathematical induction, and following the same canvas than in the proof of Prop.~\ref{positiveConvergent}, that: for each $k \in \mathbb{N}^\ast$, the TSIRM-residual norm satisfies\r
+\begin{equation}\r
+\label{induc}\r
+\begin{array}{ll}\r
+||r_k|| \leqslant & \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}}; \right. \\\r
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ||r_0||\r
+\end{array}\r
+\end{equation}\r
+when $A$ is positive definite.\r
+\r
+\r
+The base case is obvious, as for $k=1$, the TSIRM algorithm simply consists in applying GMRES($m$) once, leading to a new residual $r_1$ that follows the inductive hypothesis due to the results recalled in the items listed above.\r
+\r
+Suppose now that the claim holds for all $u=1, 2, \hdots, k-1$, that is, $\forall u \in \{1,2,\hdots, k-1\}$, $||r_u|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mu}{2}} ||r_0||$.\r
+We will show that the statement holds too for $r_k$. Two situations can occur:\r
+\begin{itemize}\r
+\item If $k \not\equiv 0 ~(\textrm{mod}\ m)$, then the TSIRM algorithm consists in executing GMRES once. In that case and by using the inductive hypothesis, we obtain \r
+$||r_k|| \leqslant \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}} \leqslant \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}} ||r_0||$, due to~\cite{citeulike:2951999}. Furthermore, we have too that: $||r_k|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}} ||r_{k-1}|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}} ||r_0||$, as proven in~\cite{ANU:137201} and by using the inductive hypothesis. So we can conclude that \r
+$$\begin{array}{ll}||r_k|| \leqslant & \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}}; \right. \\\r
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| \r
+\end{array}.$$\r
+\r
+\item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies, following the previous item:\r
+$$\begin{array}{ll}\r
+||r_k|| & \leqslant \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}}; \right. \\\r
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) \times ||r_{k-1}||\\\r
+ & \leqslant \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}}; \right. \\\r
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| \r
+\end{array}$$\r
+and the least squares resolution of $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2$.\r
+\r
+Let $\operatorname{span}(S) = \left \{ {\sum_{i=1}^k \lambda_i v_i \Big| k \in \mathbb{N}, v_i \in S, \lambda _i \in \mathbb{R}} \right \}$ be the linear span of a set of real vectors $S$, as defined previously. So,\\\r
+$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$\r
+\r
+$\begin{array}{ll}\r
+& = \min_{x \in span\left(S_{k-s+1}, S_{k-s+2}, \hdots, S_{k} \right)} ||b-AS\alpha ||_2\\\r
+& = \min_{x \in span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)} ||b-AS\alpha ||_2\\\r
+& \leqslant \min_{x \in span\left( x_{k} \right)} ||b-Ax ||_2\\\r
+& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\\r
+& \leqslant ||b-Ax_{k}||_2\\\r
+& = ||r_k||_2\\\r
+& \leqslant \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}}; \right. \\\r
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| \r
+\end{array} .$\r
+\end{itemize}\r
+due to the inductive hypothesis. \r
+So the statement of Equation~\eqref{induc} holds too for the $k$-th iterate, which concludes the induction and the proof.\r
+\end{proof}\r
+\r
+\subsection{A last linear convergence}\r
+\r
+\r
+\begin{proposition}\r
+Let us define the field of values of $A$ by \r
+$$\mathfrak{F}(A) = \left\{ \dfrac{x^\ast A x}{x^\ast x}, x \in \mathds{C}^n\setminus \{0\} \right\} .$$\r
+\r
+Then if $\mathfrak{F}(A)$ is included into a closed ball of radius $r$ and center $c$,\r
+which does not contain the origin, then the convergence of the TSIRM algorithm is at least linear. \r
+\r
+More precisely, the rate of convergence is lower \r
+than $2 \dfrac{r}{|c|}$.\r
+\end{proposition}\r
+\r
+\begin{proof}\r
+This inequality comes from the fact that, in the conditions of the proposition, the GMRES residue \r
+satisfies the inequality: $|r_k| \leqslant 2 \dfrac{r}{|c|}^k |r_0|$. An induction inspired by\r
+the proofs of Propositions~\ref{prop:saad} and~\ref{prop2} can transfer this inequality to the\r
+TSIRM residue.\r
+\end{proof}\r
+\r
+\r
+\r
Remark that a similar proposition can be formulated at each time\r
the given solver satisfies an inequality of the form $||r_n|| \leqslant \mu^n ||r_0||$,\r
with $|\mu|<1$. Furthermore, it is \emph{a priori} possible in some particular cases \r
regarding $A$, \r
that the proposed TSIRM converges while the GMRES($m$) does not.\r
\r
+%%ENDNEW\r
+\r
+\r
%%%*********************************************************\r
%%%*********************************************************\r
\section{Experiments using PETSc}\r
