X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/blobdiff_plain/1e098dfc32858d5c40fdc47bec94526503edf207..3a5b93822385ad5f4b99dd2c311422369f84ecbe:/IJHPCN/paper.tex

diff --git a/IJHPCN/paper.tex b/IJHPCN/paper.tex
index 9c7ff0c..2d0bd55 100644
--- a/IJHPCN/paper.tex
+++ b/IJHPCN/paper.tex
@@ -13,6 +13,8 @@
 \usepackage{multirow}
 \usepackage{graphicx}
 \usepackage{url}
+\usepackage{dsfont}
+
 
 \def\newblock{\hskip .11em plus .33em minus .07em}
 
@@ -364,41 +366,48 @@ in  practice.  As  explained  previously,  at  least  two  methods  seem  to  be
 interesting  to solve  the least-squares  minimization,  the CGLS  and the  LSQR
 methods.
 
-In Algorithm~\ref{algo:02} we remind the CGLS algorithm. The LSQR method follows
-more or less the  same principle but it takes more place,  so we briefly explain
-the parallelization of CGLS which is  similar to LSQR.
-
-\begin{algorithm}[t]
-\caption{CGLS}
-\begin{algorithmic}[1]
-  \Input $A$ (matrix), $b$ (right-hand side)
-  \Output $x$ (solution vector)\vspace{0.2cm}
-  \State Let $x_0$ be an initial approximation
-  \State $r_0=b-Ax_0$
-  \State $p_1=A^Tr_0$
-  \State $s_0=p_1$
-  \State $\gamma=||s_0||^2_2$
-  \For {$k=1,2,3,\ldots$ until convergence ($\gamma<\epsilon_{ls}$)} \label{algo2:conv}
-    \State $q_k=Ap_k$
-    \State $\alpha_k=\gamma/||q_k||^2_2$
-    \State $x_k=x_{k-1}+\alpha_kp_k$
-    \State $r_k=r_{k-1}-\alpha_kq_k$
-    \State $s_k=A^Tr_k$
-    \State $\gamma_{old}=\gamma$
-    \State $\gamma=||s_k||^2_2$
-    \State $\beta_k=\gamma/\gamma_{old}$
-    \State $p_{k+1}=s_k+\beta_kp_k$
-  \EndFor
-\end{algorithmic}
-\label{algo:02}
-\end{algorithm}
+%% In Algorithm~\ref{algo:02} we remind the CGLS algorithm. The LSQR method follows
+%% more or less the  same principle but it takes more place,  so we briefly explain
+%% the parallelization of CGLS which is  similar to LSQR.
+
+%% \begin{algorithm}[t]
+%% \caption{CGLS}
+%% \begin{algorithmic}[1]
+%%   \Input $A$ (matrix), $b$ (right-hand side)
+%%   \Output $x$ (solution vector)\vspace{0.2cm}
+%%   \State Let $x_0$ be an initial approximation
+%%   \State $r_0=b-Ax_0$
+%%   \State $p_1=A^Tr_0$
+%%   \State $s_0=p_1$
+%%   \State $\gamma=||s_0||^2_2$
+%%   \For {$k=1,2,3,\ldots$ until convergence ($\gamma<\epsilon_{ls}$)} \label{algo2:conv}
+%%     \State $q_k=Ap_k$
+%%     \State $\alpha_k=\gamma/||q_k||^2_2$
+%%     \State $x_k=x_{k-1}+\alpha_kp_k$
+%%     \State $r_k=r_{k-1}-\alpha_kq_k$
+%%     \State $s_k=A^Tr_k$
+%%     \State $\gamma_{old}=\gamma$
+%%     \State $\gamma=||s_k||^2_2$
+%%     \State $\beta_k=\gamma/\gamma_{old}$
+%%     \State $p_{k+1}=s_k+\beta_kp_k$
+%%   \EndFor
+%% \end{algorithmic}
+%% \label{algo:02}
+%% \end{algorithm}
 
+%%NEW
 
-In each iteration  of CGLS, there are two  matrix-vector multiplications and some
-classical  operations:  dot  product,   norm,  multiplication,  and  addition  on
-vectors.  All  these  operations are  easy  to  implement  in PETSc  or  similar
-environment.  It should be noticed that LSQR follows the same principle, it is a
-little bit longer but it performs more or less the same operations.
+The PETSc code we have develop is avaiable here: {\bf a mettre} and it will soon
+be integrated with  the PETSc sources. TSIRM has been  implemented as any solver
+for linear systems in PETSc. As it  requires to use another solver, we have used
+a very interesting  feature of PETSc that  enables to use a  preconditioner as a
+linear system  with the  function {\it  PCKSPGetKSP}.  As  the LSQR  function is
+already implemented in PETSc, we have used  it. CGLS was not implemented yet, so
+we have  implemented it and  we plan  to define it  as a minimization  solver in
+PETSc similarly to LSQR. Both CGLS and LSQR are not complex from the computation
+point of  view. They involves  matrix-vector multiplications and  some classical
+operations:  dot product,  norm,  multiplication, and  addition  on vectors.  As
+presented in Section~\ref{sec:05} the minimization step is scalable.
 
 
 %%%*********************************************************
@@ -408,56 +417,71 @@ little bit longer but it performs more or less the same operations.
 \label{sec:04}
 
 
-We can now claim that,
+We suppose in this section that GMRES($m$) is used as solver in the TSIRM algorithm applied on a complex matrix $A$.
+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)$. 
+
+\subsection{$\mathfrak{R}(A)$ is positive}
+
+\begin{proposition}
+\label{positiveConvergent}
+If $\mathfrak{R}(A)$ is positive, then the TSIRM algorithm is convergent.
+\end{proposition}
+
+
+\begin{proof}
+If $\mathfrak{R}(A)$ is positive, then even if $A$ is complex, it is possible to state that 
+the GMRES algorithm is convergent, see, \emph{e.g.},~\cite{Huang89}. In particular, its residual norm
+decreases to zero.
+
+At each iterate of the TSIRM algorithm, either a GMRES iteration is realized or a least square
+resolution (to find the minimum of $||b-Ax||_2$ is achieved on the linear span of the iterated approximation vectors 
+$span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$
+of the last GMRES stage,
+where
+$\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 \}$.
+
+Obviously, the minimum of $||b-Ax||_2$ on the set $span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$ 
+is lower than or equal to $||b-Ax_k||_2$, which is the last obtained GMRES-residual norm. So we can
+conclude that the intermediate stage of least square resolution inserted into the GMRES algorithm
+does not break the decreasing to zero of the GMRES-residual norm. 
+
+In other words, the TSIRM algorithm is convergent.
+\end{proof}
+
+
+Regarding the convergence speed, we can claim that,
 \begin{proposition}
 \label{prop:saad}
-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. 
+If $A$ is a positive matrix, then the convergence of the 
+TSIRM algorithm is linear. 
 
-Furthermore, let $r_k$ be the
-$k$-th residue of TSIRM, then
+Furthermore, let $r_k$ be the $k$-th residue of TSIRM, then
 we have the following boundaries:
-\begin{itemize}
-\item when $A$ is positive:
 \begin{equation}
 ||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| ,
 \end{equation}
-where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$;
-\item when $A$ is positive definite:
-\begin{equation}
-\|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\|.
-\end{equation}
-\end{itemize}
-%In the general case, where A is not positive definite, we have
-%$\|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\|, .$
+where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$.
 \end{proposition}
 
 \begin{proof}
-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:
-\begin{equation*}
-\|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\| .
-\end{equation*}
-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:
+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:
 \begin{equation*}
 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,
 \end{equation*}
-where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}, which proves 
-the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$.
+where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}.
 These well-known results can be found, \emph{e.g.}, in~\cite{Saad86}.
 
 We will now prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, 
-$||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_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||$ when $A$ is positive.
 
 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.
 
-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.
+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||$.
 We will show that the statement holds too for $r_k$. Two situations can occur:
 \begin{itemize}
-\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.
+\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||$.
 \item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies:
-\begin{itemize}
-\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, 
-\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,
-\end{itemize}
+$$||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||$$
 and a least squares resolution.
 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,\\
 $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$
@@ -469,27 +493,129 @@ $\begin{array}{ll}
 & \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\
 & \leqslant ||b-Ax_{k}||_2\\
 & = ||r_k||_2\\
-& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \textrm{ if $A$ is positive,}\\
-& \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}\\
-& \textrm{positive definite,} 
+& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \\
 \end{array}$
 \end{itemize}
 which concludes the induction and the proof.
 \end{proof}
 
+
+
+\subsection{$\mathfrak{R}(A)$ is positive definite}
+
+\begin{proposition}
+\label{prop2}
+Convergence of the TSIRM algorithm is at least linear when $\mathfrak{R}(A)$ is 
+positive definite. Furthermore, the rate of convergence is lower 
+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}}; 
+\left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ,$$
+where ${\lambda_{min}^{X}}$ (resp. ${\lambda_{max}^{X}}$) is the lowest (resp. largest) eigenvalue of matrix $X$.
+\end{proposition}
+
+
+\begin{proof}
+If $\mathfrak{R}(A)$ is positive definite, then it is positive, and so the TSIRM algorithm
+is convergent due to Proposition~\ref{positiveConvergent}.
+
+Furthermore, as stated in the proof of Proposition~\ref{positiveConvergent}, the GMRES residue is under control 
+when $\mathfrak{R}(A)$ is positive. More precisely, it has been proven in the literature that the residual norm 
+provided at the $m$-th step of GMRES satisfies:
+\begin{enumerate}
+\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}, 
+\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},
+\end{enumerate}
+which proves the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$.
+
+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
+\begin{equation}
+\label{induc}
+\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{m}{2}}; \right. \\
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ||r_0||
+\end{array}
+\end{equation}
+when $A$ is positive definite.
+
+
+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.
+
+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||$.
+We will show that the statement holds too for $r_k$. Two situations can occur:
+\begin{itemize}
+\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_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 
+$$\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. \\
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| 
+\end{array}.$$
+
+\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:
+$$\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{m}{2}}; \right. \\
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) \times ||r_{k-1}||\\
+ & \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. \\
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| 
+\end{array}$$
+and the least squares resolution of $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2$.
+
+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,\\
+$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2  = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$
+
+$\begin{array}{ll}
+& = \min_{x \in span\left(S_{k-s+1}, S_{k-s+2}, \hdots, S_{k} \right)} ||b-AS\alpha ||_2\\
+& = \min_{x \in span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)} ||b-AS\alpha ||_2\\
+& \leqslant \min_{x \in span\left( x_{k} \right)} ||b-Ax ||_2\\
+& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\
+& \leqslant ||b-Ax_{k}||_2\\
+& = ||r_k||_2\\
+& \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. \\
+& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| 
+\end{array} .$
+\end{itemize}
+due to the inductive hypothesis. 
+So the statement of Equation~\eqref{induc} holds too for the $k$-th iterate, which concludes the induction and the proof.
+\end{proof}
+
+\subsection{A last linear convergence}
+
+
+\begin{proposition}
+Let us define the field of values of $A$ by 
+$$\mathfrak{F}(A) = \left\{ \dfrac{x^\ast A x}{x^\ast x}, x \in \mathds{C}^n\setminus \{0\} \right\} .$$
+
+Then if $\mathfrak{F}(A)$ is included into a closed ball of radius $r$ and center $c$,
+which does not contain the origin, then the convergence of the TSIRM algorithm is at least linear. 
+
+More precisely, the rate of convergence is lower 
+than $2 \dfrac{r}{|c|}$.
+\end{proposition}
+
+\begin{proof}
+This inequality comes from the fact that, in the conditions of the proposition, the GMRES residue 
+satisfies the inequality: $|r_k| \leqslant 2 \dfrac{r}{|c|}^k |r_0|$. An induction inspired by
+the proofs of Propositions~\ref{prop:saad} and~\ref{prop2} can transfer this inequality to the
+TSIRM residue.
+\end{proof}
+
+
+
 Remark that a similar proposition can be formulated at each time
 the given solver satisfies an inequality of the form $||r_n|| \leqslant \mu^n ||r_0||$,
 with $|\mu|<1$. Furthermore, it is \emph{a priori} possible in some particular cases 
 regarding $A$, 
 that the proposed TSIRM converges while the GMRES($m$) does not.
 
+
 %%%*********************************************************
 %%%*********************************************************
 \section{Experiments using PETSc}
 \label{sec:05}
 
-%%NEW
-In this section four kinds of experiments have been performed. First, some experiments on real matrices issued from the sparse matrix florida have been achieved out. Second, some experiments in parallel with some linear problems are reported and analyzed. Third, some experiments in parallÃ¨le with som nonlinear problems are illustrated. Finally some parameters of TSIRM are studied in order to understand their influences.
+In  this section  four kinds  of experiments  have been  performed. First,  some
+experiments on  real matrices issued  from the  sparse matrix florida  have been
+achieved out. Second, some experiments in parallel with some linear problems are
+reported and analyzed.  Third, some experiments in parallÃ¨le  with som nonlinear
+problems are illustrated. Finally some parameters  of TSIRM are studied in order
+to understand their influences.
 
 
 \subsection{Real matrices}
@@ -608,7 +734,7 @@ However, for parallel applications, all  the preconditioners based on matrix fac
 are  not  available. In  our  experiments, we  have  tested  different kinds  of
 preconditioners, but  as it is  not the subject  of this paper, we  will not
 present results with many preconditioners. In  practice, we have chosen to use a
-multigrid (mg)  and successive  over-relaxation (sor). For  further details  on the
+multigrid (MG)  and successive  over-relaxation (SOR). For  further details  on the
 preconditioners in PETSc, readers are referred to~\cite{petsc-web-page}.
 
 
@@ -621,18 +747,18 @@ preconditioners in PETSc, readers are referred to~\cite{petsc-web-page}.
   nb. cores & precond   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain \\ 
 \cline{3-8}
              &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline
-  2,048      & mg                    & 403.49   & 18,210    & 73.89  & 3,060   & 77.84  & 3,270  & 5.46 \\
-  2,048      & sor                   & 745.37   & 57,060    & 87.31  & 6,150   & 104.21 & 7,230  & 8.53 \\
-  4,096      & mg                    & 562.25   & 25,170    & 97.23  & 3,990   & 89.71  & 3,630  & 6.27 \\
-  4,096      & sor                   & 912.12   & 70,194    & 145.57 & 9,750   & 168.97 & 10,980 & 6.26 \\
-  8,192      & mg                    & 917.02   & 40,290    & 148.81 & 5,730   & 143.03 & 5,280  & 6.41 \\
-  8,192      & sor                   & 1,404.53 & 106,530   & 212.55 & 12,990  & 180.97 & 10,470 & 7.76 \\
-  16,384     & mg                    & 1,430.56 & 63,930    & 237.17 & 8,310   & 244.26 & 7,950  & 6.03 \\
-  16,384     & sor                   & 2,852.14 & 216,240   & 418.46 & 21,690  & 505.26 & 23,970 & 6.82 \\
+  2,048      & MG                    & 403.49   & 18,210    & 73.89  & 3,060   & 77.84  & 3,270  & 5.46 \\
+  2,048      & SOR                   & 745.37   & 57,060    & 87.31  & 6,150   & 104.21 & 7,230  & 8.53 \\
+  4,096      & MG                    & 562.25   & 25,170    & 97.23  & 3,990   & 89.71  & 3,630  & 6.27 \\
+  4,096      & SOR                   & 912.12   & 70,194    & 145.57 & 9,750   & 168.97 & 10,980 & 6.26 \\
+  8,192      & MG                    & 917.02   & 40,290    & 148.81 & 5,730   & 143.03 & 5,280  & 6.41 \\
+  8,192      & SOR                   & 1,404.53 & 106,530   & 212.55 & 12,990  & 180.97 & 10,470 & 7.76 \\
+  16,384     & MG                    & 1,430.56 & 63,930    & 237.17 & 8,310   & 244.26 & 7,950  & 6.03 \\
+  16,384     & SOR                   & 2,852.14 & 216,240   & 418.46 & 21,690  & 505.26 & 23,970 & 6.82 \\
 \hline
 
 \end{tabular}
-\caption{Comparison of FGMRES and TSIRM with FGMRES for example ex15 of PETSc/KSP with two preconditioners (mg and sor) having 25,000 components per core on Juqueen ($\epsilon_{tsirm}=1e-3$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
+\caption{Comparison of FGMRES and TSIRM with FGMRES for example ex15 of PETSc/KSP with two preconditioners (MG and SOR) having 25,000 components per core on Juqueen ($\epsilon_{tsirm}=1e-3$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
 \label{tab:03}
 \end{center}
 \end{table*}
@@ -640,7 +766,7 @@ preconditioners in PETSc, readers are referred to~\cite{petsc-web-page}.
 Table~\ref{tab:03} shows  the execution  times and the  number of  iterations of
 example ex15  of PETSc on the  Juqueen architecture. Different  numbers of cores
 are studied  ranging from 2,048 up-to  16,383 with the  two preconditioners {\it
-  mg}  and {\it  sor}.   For those  experiments,  the number  of components  (or
+  MG}  and {\it  SOR}.   For those  experiments,  the number  of components  (or
 unknowns  of  the problems)  per  core  is fixed  at  25,000,  also called  weak
 scaling. This number  can seem relatively small. In  fact, for some applications
 that  need a  lot of  memory, the  number of  components per  processor requires
@@ -785,63 +911,149 @@ taken into account with TSIRM.
 
 
 %%NEW
+It  is well-known  that  preconditioners have  a very  strong  influence on  the
+convergence  of  linear  systems.   Previously,  we  have  used  some  classical
+preconditioners provided  by PETSc.  HYPRE~\cite{Falgout06} is  a very efficient
+preconditioner  based  on  structured   multigrid  and  element-based  algebraic
+multigrid algorithms. In Table~\ref{tab:06} we report an experiment that show it
+reduces  drastivally  the  number  of   iterations  but  sometimes  it  is  very
+time-consuming compared  to other simpler  precondititioners. In this  table, we
+can see that  for $512$ and $2,048$ cores, HYPRE  reduces drastically the number
+of  iterations  for FGMRES  to  reach  the  convergence.   However, it  is  very
+time-consuming compared  to TSIRM  and FGMRES with  the ASM  preconditioner. For
+$4,096$ and $8,192$ cores, FGMRES with HYPRE did not converge in less than 1000s
+where FGMRES and  TSIRM with the ASM  converge very quickly. Finally,  it can be
+noticed that TSIRM is also faster than FGMRES and it requires less iterations.
+
+
+\begin{table*}[htbp]
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|r|r|r|} 
+\hline
+
+  nb. cores   & \multicolumn{2}{c|}{FGMRES/ASM} & \multicolumn{2}{c|}{TSIRM CGLS/ASM} & gain& \multicolumn{2}{c|}{FGMRES/HYPRE}   \\ 
+\cline{2-5} \cline{7-8}
+                    & Time  & \# Iter.  & Time  & \# Iter. &        & Time  & \# Iter.   \\\hline \hline
+   512              & 5.54      & 685    & 2.5 &       570 & 2.21   & 128.9 & 9     \\
+   2048             & 14.95     & 1,560  &  4.32 &     746 & 3.48   & 335.7 & 9 \\
+   4096             & 25.13    & 2,369   & 5.61 &   859    & 4.48   & >1000  & -- \\
+   8192             & 44.35   & 3,197   &  7.6  &  1,083    &  5.84  & >1000 &  --   \\
+
+\hline
+
+\end{tabular}
+\caption{Comparison of FGMRES  and TSIRM for ex45 of PETSc/KSP with two preconditioner (ASM and HYPRE)  having 5,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$,$\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
+\label{tab:06}
+\end{center}
+\end{table*}
+
 
 \subsection{Parallel nonlinear problems}
 
 With  PETSc,  linear  solvers  are  used inside  nonlinear  solvers.   The  SNES
 (Scalable Nonlinear  Equations Solvers) module  in PETSc implements easy  to use
 methods,  like  Newton-type, quasi-Newton  or  full  approximation scheme  (FAS)
-multigrid to solve systems of nonlinears equations.  As the SNES is based on the
+multigrid to  solve systems of  nonlinears equations.  As  SNES is based  on the
 Krylov methods of PETSc, it is interesting to investigate if the TSIRM method is
-also efficient and scalable with non linear problems.
-
-
-
+also efficient  and scalable with non  linear problems. In PETSc,  some examples
+are provided.  An important criteria is the scalability of the initial code with
+classical solvers. Consequently, we have chosen  two of these examples: ex14 and
+ex20.  In ex14, the code solves the  Bratu (SFI - solid fuel ignition) nonlinear
+partial  difference equations  in 3  dimension.  In  ex20, the  code solves  a 3
+dimension radiative transport test problem.  For more details on these examples,
+interested readers are invited  to see the code in the  PETSc examples. For both
+these  examples,   a  weak  scaling   case  is  chosen  where   processors  have
+approximately a number of components equals to 100,000.
+
+In Table~\ref{tab:07}  we report the result  of our experiments for  the example
+ex14 with the block Jacobi preconditioner.  For TSIRM the CGLS algorithm is used
+to solve  the minimization step. In  this table, we  can see that the  number of
+iterations used by the linear solver is smaller with TSIRM compared with FGMRES.
+Consequently the execution times are smaller  with TSIRM. The gain between TSIRM
+and FGMRES  is around  6 and  7. The parameters  of TSIRM  are expressed  in the
+caption of the table.
 
 \begin{table*}[htbp]
 \begin{center}
 \begin{tabular}{|r|r|r|r|r|r|} 
 \hline
 
-  nb. cores   & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain   \\ 
+  nb. cores   & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain  \\ 
 \cline{2-5}
-                    & Time         & \# Iter.  & Time   & \# Iter.  &  \\\hline \hline
-   1024              & 667.92      & 48,732    & 81.65  &     5,087 &  8.18 \\
-   2048             & 966.87       & 77,177    &  90.34 &     5,716 &  10.70\\
-   4096             & 1,742.31     & 124,411   &  119.21 &   6,905  & 14.61\\
-   8192             & 2,739.21     & 187,626   &  168.9  &  9,000   & 16.22\\
+                    & Time         & \# Iter.  & Time   & \# Iter. &  \\\hline \hline
+   1,024              & 159.52      & 11,584    &  26.34  &     1,563  &  6.06  \\
+   2,048             & 226.24       & 16,459    &  37.23 &     2,248   &  6.08\\
+   4,096             & 391.21     & 27,794   &  50.93 &   2,911  &  7.69\\
+   8,192             & 543.23     & 37,770   &  79.21  &  4,324  & 6.86 \\
 
 \hline
 
 \end{tabular}
-\caption{Comparison of FGMRES  and TSIRM for ex20 of PETSc/SNES with a Block Jacobi  preconditioner  having 100,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
+\caption{Comparison of FGMRES  and TSIRM for ex14 of PETSc/SNES with a Block Jacobi  preconditioner  having 100,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
 \label{tab:07}
 \end{center}
 \end{table*}
 
+In Table~\ref{tab:08}, the results of the experiments with the example ex20 are
+reported. The block  Jacobi preconditioner has also been used  and CGLS to solve
+the minimization step for TSIRM. For this example, we can observ that the number
+of  iterations  for  FMGRES  increase  drastically  when  the  number  of  cores
+increases. With  TSIRM, we can  see that the  number of iterations  is initially
+very small compared  to the FGMRES ones  and when the number  of cores increase,
+the number  of iterations increases slighther  with TSIRM than with  FGMRES. For
+this example,  the gain  between TSIRM  and FGMRES ranges  between 8  with 1,024
+cores to more than 16 with 8,192 cores.
+
 \begin{table*}[htbp]
 \begin{center}
 \begin{tabular}{|r|r|r|r|r|r|} 
 \hline
 
-  nb. cores   & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain  \\ 
+  nb. cores   & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain   \\ 
 \cline{2-5}
-                    & Time         & \# Iter.  & Time   & \# Iter. &  \\\hline \hline
-   1024              & 159.52      & 11,584    &  26.34  &     1,563  &  6.06  \\
-   2048             & 226.24       & 16,459    &  37.23 &     2,248   &  6.08\\
-   4096             & 391.21     & 27,794   &  50.93 &   2,911  &  7.69\\
-   8192             & 543.23     & 37,770   &  79.21  &  4,324  & 6.86 \\
+                    & Time         & \# Iter.  & Time   & \# Iter.  &  \\\hline \hline
+   1,024              & 667.92      & 48,732    & 81.65  &     5,087 &  8.18 \\
+   2,048             & 966.87       & 77,177    &  90.34 &     5,716 &  10.70\\
+   4,096             & 1,742.31     & 124,411   &  119.21 &   6,905  & 14.61\\
+   8,192             & 2,739.21     & 187,626   &  168.9  &  9,000   & 16.22\\
 
 \hline
 
 \end{tabular}
-\caption{Comparison of FGMRES  and TSIRM for ex14 of PETSc/SNES with a Block Jacobi  preconditioner  having 100,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
+\caption{Comparison of FGMRES  and TSIRM for ex20 of PETSc/SNES with a Block Jacobi  preconditioner  having 100,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}
 \label{tab:08}
 \end{center}
 \end{table*}
 
 
+
+
+
+
+
+%%NEW
 \subsection{Influence of parameters for TSIRM}
+In this section we present some experimental results in order to study the influence of some parameters on the TSIRM algorithm. We conducted experiments on $16$ cores to solve 3D problems of size $200,000$ components per core. We solved nonlinear problems token from examples of PETSc. We fixed some parameters of the TSIRM algorithm as follows: the nonlinear systems are solved with a precision of $10^{-8}$, block Jacobi preconditioner is used, the tolerance threshold $\epsilon_{tsirm}$ is $10^{-8}$ , the maximum number of iterations $max\_iter_{tsirm}$ is set to $10,000$ iterations, the FGMRES method is used as the inner solver with a tolerance threshold $\epsilon_{kryl}=10^{-10}$ and the least-squares problem is solved with a precision $\epsilon_{ls}=10^{-40}$ in the minimization process.
+
+%time mpirun ../ex34 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -ksp_type tsirm -ksp_pc_type asm -pc_type ksp -ksp_tsirm_tol 1e-10 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 30 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 20 -ksp_tsirm_size_ls 10
+\begin{figure}[htbp]
+\centering
+  \includegraphics[width=0.5\textwidth]{ksp_tsirm_cgls}
+\caption{Number of total iterations using two different methods for the minimization: CGLS and LSQR.}
+\label{fig:cgls} 
+\end{figure}
+
+\begin{figure}[htbp]
+\centering
+  \includegraphics[width=0.5\textwidth]{snes_ex14}
+\caption{Total number of iterations in example {\it snes ex14} of PETSc by varyin the number of inner iterations and the size of the least-squares problem.}
+\label{fig:snes_ex14} 
+\end{figure}
+
+
+
+
+%%ENDNEW
 
 
 
@@ -914,7 +1126,7 @@ Curie and Juqueen respectively based in France and Germany.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \bibliography{biblio}
-\bibliographystyle{unsrt}
-\bibliographystyle{alpha}
+\bibliographystyle{plain}
+%\bibliographystyle{alpha}
 
 \end{document}
