new

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 517cb8e283f8f514809af58f2bd9b75309d1358e..a4c9b268faf6197c47d7c288188adc6bf299b3de 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -380,8 +380,8 @@
 % use a multiple column layout for up to two different
 % affiliations
 
 % use a multiple column layout for up to two different
 % affiliations
 

-\author{\IEEEauthorblockN{Rapha\"el Couturier\IEEEauthorrefmark{1}, Lilia Ziane Khodja \IEEEauthorrefmark{2}, and Christophe Guyeux\IEEEauthorrefmark{1}}
-\IEEEauthorblockA{\IEEEauthorrefmark{1} Femto-ST Institute, University of Franche Comte, France\\
+\author{\IEEEauthorblockN{Rapha\"el Couturier\IEEEauthorrefmark{1}, Lilia Ziane Khodja\IEEEauthorrefmark{2}, and Christophe Guyeux\IEEEauthorrefmark{1}}
+\IEEEauthorblockA{\IEEEauthorrefmark{1} Femto-ST Institute, University of Franche-Comt\'e, France\\

 Email: \{raphael.couturier,christophe.guyeux\}@univ-fcomte.fr}
 \IEEEauthorblockA{\IEEEauthorrefmark{2} INRIA Bordeaux Sud-Ouest, France\\
 Email: lilia.ziane@inria.fr}
 Email: \{raphael.couturier,christophe.guyeux\}@univ-fcomte.fr}
 \IEEEauthorblockA{\IEEEauthorrefmark{2} INRIA Bordeaux Sud-Ouest, France\\
 Email: lilia.ziane@inria.fr}


@@ -439,7 +439,7 @@ GMRES.
 \end{abstract}
 
 \begin{IEEEkeywords}
 \end{abstract}
 
 \begin{IEEEkeywords}

-Iterative Krylov methods; sparse linear systems; residual minimization; PETSc; %à voir... 
+Iterative Krylov methods; sparse linear systems; two stage iteration; least-squares residual minimization; PETSc

 \end{IEEEkeywords}
 
 
 \end{IEEEkeywords}
 
 


@@ -547,38 +547,42 @@ Iterative Krylov methods; sparse linear systems; residual minimization; PETSc; %
 % You must have at least 2 lines in the paragraph with the drop letter
 % (should never be an issue)
 
 % You must have at least 2 lines in the paragraph with the drop letter
 % (should never be an issue)
 

-Iterative methods have recently become more attractive than  direct ones to  solve very large
-sparse  linear systems.  They are more  efficient  in a  parallel
-context,  supporting  thousands  of  cores,  and they require  less  memory  and  arithmetic
-operations than direct  methods. This is why new iterative  methods are frequently 
-proposed or adapted by researchers, and the increasing need to solve very large sparse
-linear  systems  has triggered the  development  of such efficient iterative  techniques
-suitable for parallel processing.
-
-Most of the successful iterative methods currently available are based on so-called ``Krylov
-subspaces''. They  consist in forming a  basis of successive matrix
-powers multiplied by an initial vector, which can be for instance the residual. These methods use vectors orthogonality of the Krylov  subspace  basis in order to solve  linear
-systems.  The  most known iterative  Krylov subspace methods  are conjugate
-gradient and GMRES ones (Generalized Minimal RESidual).
-
-
-However,  iterative  methods suffer  from scalability  problems  on parallel
-computing  platforms  with many  processors, due  to  their need  of  reduction
-operations, and to  collective    communications   to  achive   matrix-vector
+Iterative methods have recently become more attractive than direct ones to solve
+very large sparse  linear systems\cite{Saad2003}.  They are more  efficient in a
+parallel context,  supporting thousands of  cores, and they require  less memory
+and  arithmetic operations than  direct methods~\cite{bahicontascoutu}.  This is
+why new iterative methods are frequently proposed or adapted by researchers, and
+the increasing need to solve very  large sparse linear systems has triggered the
+development  of  such  efficient  iterative  techniques  suitable  for  parallel
+processing.
+
+Most  of the  successful  iterative  methods currently  available  are based  on
+so-called ``Krylov  subspaces''. They consist  in forming a basis  of successive
+matrix powers  multiplied by an  initial vector, which  can be for  instance the
+residual. These methods  use vectors orthogonality of the  Krylov subspace basis
+in  order to solve  linear systems.   The most  known iterative  Krylov subspace
+methods are conjugate gradient and GMRES ones (Generalized Minimal RESidual).
+
+
+However,  iterative  methods  suffer   from  scalability  problems  on  parallel
+computing  platforms  with many  processors,  due  to  their need  of  reduction
+operations,   and  to   collective  communications   to   achieve  matrix-vector

 multiplications. The  communications on large  clusters with thousands  of cores
 multiplications. The  communications on large  clusters with thousands  of cores

-and  large  sizes of  messages  can  significantly  affect the  performances  of these
-iterative methods. As a consequence, Krylov subspace iteration methods are often used
-with preconditioners in practice, to increase their convergence and accelerate their
-performances.  However, most  of the  good preconditioners  are not  scalable on
-large clusters.
-
-In this research work, a two-stage algorithm based on  two nested iterations
-called inner-outer  iterations is proposed.  This algorithm  consists in solving  the sparse
-linear system iteratively  with a small number of  inner iterations, and restarting
-the outer  step with a  new solution minimizing  some error functions  over some
-previous residuals. This algorithm is iterative and easy to parallelize on large
-clusters. Furthermore,  the   minimization  technique   improves  its   convergence  and
-performances.
+and large sizes  of messages can significantly affect  the performances of these
+iterative methods. As a consequence, Krylov subspace iteration methods are often
+used  with  preconditioners  in  practice,  to increase  their  convergence  and
+accelerate their  performances.  However, most  of the good  preconditioners are
+not scalable on large clusters.
+
+In  this research work,  a two-stage  algorithm based  on two  nested iterations
+called inner-outer  iterations is proposed.  This algorithm  consists in solving
+the sparse  linear system iteratively with  a small number  of inner iterations,
+and  restarting  the  outer step  with  a  new  solution minimizing  some  error
+functions  over some previous  residuals. For  further information  on two-stage
+iteration      methods,     interested      readers      are     invited      to
+consult~\cite{Nichols:1973:CTS}. Two-stage algorithms are easy to parallelize on
+large clusters.  Furthermore,  the least-squares minimization technique improves
+its convergence and performances.

 
 The present  article is  organized as follows.   Related works are  presented in
 Section~\ref{sec:02}. Section~\ref{sec:03} details the two-stage algorithm using
 
 The present  article is  organized as follows.   Related works are  presented in
 Section~\ref{sec:02}. Section~\ref{sec:03} details the two-stage algorithm using


@@ -618,22 +622,23 @@ It can be summarized as follows: the
 inner solver is a Krylov based one. In order to accelerate its convergence, the 
 outer solver periodically applies a least-squares minimization  on the residuals computed by  the inner one. %Tsolver which does not required to be changed.
 
 inner solver is a Krylov based one. In order to accelerate its convergence, the 
 outer solver periodically applies a least-squares minimization  on the residuals computed by  the inner one. %Tsolver which does not required to be changed.
 

-At each outer iteration, the sparse linear system $Ax=b$ is partially 
-solved using only $m$
-iterations of an iterative method, this latter being initialized with the 
-best known approximation previously obtained. 
-GMRES method~\cite{Saad86}, or any of its variants, can be used for instance as an
-inner solver. The current approximation of the Krylov method is then stored inside a matrix
-$S$ composed by the successive solutions that are computed during inner iterations.
+At each  outer iteration,  the sparse linear  system $Ax=b$ is  partially solved
+using only $m$ iterations of  an iterative method, this latter being initialized
+with the last obtained approximation.  GMRES method~\cite{Saad86}, or any of its
+variants, can potentially be used  as inner solver. The current approximation of
+the Krylov  method is then  stored inside  a $n \times  s$ matrix $S$,  which is
+composed by  the $s$  last solutions  that have been  computed during  the inner
+iterations phase.   In the remainder,  the $i$-th column  vector of $S$  will be
+denoted by $S_i$.

 
 

-At each $s$ iterations, the minimization step is applied in order to
+At each $s$ iterations, another kind of minimization step is applied in order to

 compute a new  solution $x$. For that, the previous  residuals of $Ax=b$ are computed by
 the inner iterations with $(b-AS)$. The minimization of the residuals is obtained by  
 \begin{equation}
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}
 \end{equation}
 compute a new  solution $x$. For that, the previous  residuals of $Ax=b$ are computed by
 the inner iterations with $(b-AS)$. The minimization of the residuals is obtained by  
 \begin{equation}
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}
 \end{equation}

-with $R=AS$. Then the new solution $x$ is computed with $x=S\alpha$.
+with $R=AS$. The new solution $x$ is then computed with $x=S\alpha$.

 
 
 In  practice, $R$  is a  dense rectangular  matrix belonging in  $\mathbb{R}^{n\times s}$,
 
 
 In  practice, $R$  is a  dense rectangular  matrix belonging in  $\mathbb{R}^{n\times s}$,


@@ -650,9 +655,8 @@ appropriate than a single direct method in a parallel context.
   \Output $x$ (solution vector)\vspace{0.2cm}
   \State Set the initial guess $x_0$
   \For {$k=1,2,3,\ldots$ until convergence (error$<\epsilon_{tsirm}$)} \label{algo:conv}
   \Output $x$ (solution vector)\vspace{0.2cm}
   \State Set the initial guess $x_0$
   \For {$k=1,2,3,\ldots$ until convergence (error$<\epsilon_{tsirm}$)} \label{algo:conv}

-    \State  $x_k=Solve(A,b,x_{k-1},max\_iter_{kryl})$   \label{algo:solve}
-    \State retrieve error
-    \State $S_{k \mod s}=x_k$ \label{algo:store}
+    \State  $[x_k,error]=Solve(A,b,x_{k-1},max\_iter_{kryl})$   \label{algo:solve}
+    \State $S_{k \mod s}=x_k$ \label{algo:store} \Comment{update column (k mod s) of S}

     \If {$k \mod s=0$ {\bf and} error$>\epsilon_{kryl}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}
             \State $\alpha=Least\_Squares(R,b,max\_iter_{ls})$ \label{algo:}
     \If {$k \mod s=0$ {\bf and} error$>\epsilon_{kryl}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}
             \State $\alpha=Least\_Squares(R,b,max\_iter_{ls})$ \label{algo:}


@@ -663,18 +667,22 @@ appropriate than a single direct method in a parallel context.
 \label{algo:01}
 \end{algorithm}
 
 \label{algo:01}
 \end{algorithm}
 

-Algorithm~\ref{algo:01}  summarizes  the principle  of  our  method.  The  outer
-iteration is  inside the for  loop. Line~\ref{algo:solve}, the Krylov  method is
-called for a  maximum of $max\_iter_{kryl}$ iterations.  In practice, we  suggest to set this parameter
-equals to  the restart  number of the  GMRES-like method. Moreover,  a tolerance
-threshold must be specified for the  solver. In practice, this threshold must be
-much  smaller  than the  convergence  threshold  of  the TSIRM  algorithm  (\emph{i.e.}
-$\epsilon_{tsirm}$).  Line~\ref{algo:store}, $S_{k \mod s}=x^k$ consists in copying the
-solution  $x_k$  into the  column  $k \mod s$ of  the  matrix  $S$, where $S$ is a matrix of size $n\times s$ whose column vector $i$ is denoted by $S_i$. After  the
-minimization, the matrix $S$ is reused with the new values of the residuals.  To
-solve the minimization problem, an  iterative method is used. Two parameters are
-required for that: the maximum number of iterations and the threshold to stop the
-method.
+Algorithm~\ref{algo:01} summarizes  the principle  of the proposed  method.  The
+outer iteration is inside the \emph{for} loop. Line~\ref{algo:solve}, the Krylov
+method is called  for a maximum of $max\_iter_{kryl}$  iterations.  In practice,
+we suggest to  set this parameter equal to the restart  number in the GMRES-like
+method. Moreover,  a tolerance  threshold must be  specified for the  solver. In
+practice, this threshold must be  much smaller than the convergence threshold of
+the  TSIRM algorithm  (\emph{i.e.}, $\epsilon_{tsirm}$).  We also  consider that
+after the call of the $Solve$ function, we obtain the vector $x_k$ and the error
+which is defined by $||Ax^k-b||_2$.
+
+  Line~\ref{algo:store},
+$S_{k \mod  s}=x^k$ consists in  copying the solution  $x_k$ into the  column $k
+\mod s$ of $S$.   After the minimization, the matrix $S$ is  reused with the new
+values of the residuals.  To solve the minimization problem, an iterative method
+is used. Two parameters are required  for that: the maximum number of iterations
+and the threshold to stop the method.

 
 Let us summarize the most important parameters of TSIRM:
 \begin{itemize}
 
 Let us summarize the most important parameters of TSIRM:
 \begin{itemize}


@@ -735,38 +743,79 @@ these operations are easy to implement in PETSc or similar environment.
 
 \section{Convergence results}
 \label{sec:04}
 
 \section{Convergence results}
 \label{sec:04}

-Let us recall the following result, see~\cite{Saad86}.
-\begin{proposition}
-Suppose that $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 = \lambda_min(M)^2$ and $\beta = \lambda_max(A^T A)$, which proves 
-the convergence of GMRES($m$) for all $m$ under that assumption regarding $A$.
-\end{proposition}

 
 
 We can now claim that,
 \begin{proposition}
 
 
 We can now claim that,
 \begin{proposition}

-If $A$ is a positive real matrix and GMRES($m$) is used as solver, then the TSIRM algorithm is convergent.
+\label{prop:saad}
+If $A$ is either a definite positive or a positive matrix and GMRES($m$) is used as solver, then the TSIRM algorithm is convergent. 
+
+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\|, .$

 \end{proposition}
 
 \begin{proof}
 \end{proposition}
 
 \begin{proof}

-Let $r_k = b-Ax_k$, where $x_k$ is the approximation of the solution after the
-$k$-th iterate of TSIRM.
-We will prove that $r_k \rightarrow 0$ when $k \rightarrow +\infty$.
+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:
+\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$.
+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.

 
 

-Each step of the TSIRM algorithm \\
+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.
+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 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}
+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$
 
 $\begin{array}{ll}
 $\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 Vect\left(S_{k-s}, S_{k-s+1}, \hdots, S_{k-1} \right)} ||b-AS\alpha ||_2\\
-& = \min_{x \in Vect\left(x_{k-s}, x_{k-s}+1, \hdots, x_{k-1} \right)} ||b-AS\alpha ||_2\\
-& \leqslant \min_{x \in Vect\left( x_{k-1} \right)} ||b-Ax ||_2\\
-& \leqslant ||b-Ax_{k-1}||
+& = \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 \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,} 

 \end{array}$
 \end{array}$

+\end{itemize}
+which concludes the induction and the proof.

 \end{proof}
 
 \end{proof}
 

+%We can remark that, at each iterate, the residue of the TSIRM algorithm is lower 
+%than the one of the GMRES method.

 
 %%%*********************************************************
 %%%*********************************************************
 
 %%%*********************************************************
 %%%*********************************************************


@@ -774,11 +823,13 @@ $\begin{array}{ll}
 \label{sec:05}
 
 
 \label{sec:05}
 
 

-In order to see the influence of our algorithm with only one processor, we first
-show  a comparison  with the  standard version  of GMRES  and our  algorithm. In
-Table~\ref{tab:01},  we  show  the  matrices  we  have used  and  some  of  them
-characteristics. For all  the matrices, the name, the field,  the number of rows
-and the number of nonzero elements are given.
+In order to see the behavior of the proposal when considering only one processor, a first
+comparison with GMRES or FGMRES and the new algorithm detailed previously has been experimented. 
+Matrices that have been used with their characteristics (names, fields, rows, and nonzero coefficients) are detailed in 
+Table~\ref{tab:01}.  These latter, which are real-world applications matrices, 
+have been extracted 
+ from   the  Davis  collection,   University  of
+Florida~\cite{Dav97}.

 
 \begin{table}[htbp]
 \begin{center}
 
 \begin{table}[htbp]
 \begin{center}


@@ -798,8 +849,9 @@ torso3             & 2D/3D problem & 259,156 & 4,429,042 \\
 \label{tab:01}
 \end{center}
 \end{table}
 \label{tab:01}
 \end{center}
 \end{table}

-
-The following  parameters have been chosen  for our experiments.   As by default
+Chosen parameters are detailed below.
+%The following  parameters have been chosen  for our experiments.   
+As by default

 the restart  of GMRES is performed every  30 iterations, we have  chosen to stop
 the GMRES every 30 iterations (\emph{i.e.} $max\_iter_{kryl}=30$).  $s$ is set to 8. CGLS is
 chosen  to minimize  the least-squares  problem with  the  following parameters:
 the restart  of GMRES is performed every  30 iterations, we have  chosen to stop
 the GMRES every 30 iterations (\emph{i.e.} $max\_iter_{kryl}=30$).  $s$ is set to 8. CGLS is
 chosen  to minimize  the least-squares  problem with  the  following parameters:


@@ -811,13 +863,14 @@ Core(TM) i7-3630QM CPU @ 2.40GHz with the version 3.5.1 of PETSc.
 In  Table~\ref{tab:02}, some  experiments comparing  the solving  of  the linear
 systems obtained with the previous matrices  with a GMRES variant and with out 2
 stage algorithm are  given. In the second column, it can  be noticed that either
 In  Table~\ref{tab:02}, some  experiments comparing  the solving  of  the linear
 systems obtained with the previous matrices  with a GMRES variant and with out 2
 stage algorithm are  given. In the second column, it can  be noticed that either

-gmres or fgmres is used to  solve the linear system.  According to the matrices,
-different  preconditioner is used.   With TSIRM,  the same  solver and  the same
-preconditionner are used.  This Table shows that TSIRM can drastically reduce the
-number of iterations to reach the  convergence when the number of iterations for
-the normal GMRES is more or less  greater than 500. In fact this also depends on
-tow  parameters: the  number  of iterations  to  stop GMRES  and  the number  of
-iterations to perform the minimization.
+GRMES or  FGMRES (Flexible  GMRES)~\cite{Saad:1993} is used  to solve  the linear
+system.   According to  the matrices,  different preconditioner  is  used.  With
+TSIRM, the same solver and the  same preconditionner are used.  This Table shows
+that  TSIRM  can  drastically reduce  the  number  of  iterations to  reach  the
+convergence when the  number of iterations for the normal GMRES  is more or less
+greater than  500. In fact  this also depends  on tow parameters: the  number of
+iterations  to  stop  GMRES  and   the  number  of  iterations  to  perform  the
+minimization.

 
 
 \begin{table}[htbp]
 
 
 \begin{table}[htbp]


@@ -838,7 +891,7 @@ torso3             & fgmres / sor  & 37.70 & 565 & 34.97 & 510 \\
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of (F)GMRES and 2 stage (F)GMRES algorithms in sequential with some matrices, time is expressed in seconds.}
+\caption{Comparison of (F)GMRES and TSIRM with (F)GMRES in sequential with some matrices, time is expressed in seconds.}

 \label{tab:02}
 \end{center}
 \end{table}
 \label{tab:02}
 \end{center}
 \end{table}


@@ -847,7 +900,7 @@ torso3             & fgmres / sor  & 37.70 & 565 & 34.97 & 510 \\
 
 
 
 
 
 

-In order to perform larger  experiments, we have tested some example applications
+In order to perform larger experiments, we have tested some example applications

 of PETSc. Those  applications are available in the ksp part  which is suited for
 scalable linear equations solvers:
 \begin{itemize}
 of PETSc. Those  applications are available in the ksp part  which is suited for
 scalable linear equations solvers:
 \begin{itemize}


@@ -860,15 +913,35 @@ scalable linear equations solvers:
   finite elements. For this example, the user can define the scaling of material
   coefficient in embedded circle called $\alpha$.
 \end{itemize}
   finite elements. For this example, the user can define the scaling of material
   coefficient in embedded circle called $\alpha$.
 \end{itemize}

-For more technical details on  these applications, interested readers are invited
-to  read the  codes available  in the  PETSc sources.   Those problems  have been
-chosen because they  are scalable with many cores which is not the case of other problems that we have tested.
+For more technical details on these applications, interested readers are invited
+to read  the codes  available in  the PETSc sources.   Those problems  have been
+chosen because they are scalable with many  cores which is not the case of other
+problems that we have tested.
+
+In  the  following   larger  experiments  are  described  on   two  large  scale
+architectures:  Curie and  Juqeen.  Both  these architectures  are supercomputer
+composed of 80,640 cores for Curie and 458,752 cores for Juqueen. Those machines
+are respectively hosted  by GENCI in France and  Jülich Supercomputing Centre in
+Germany. They belongs with other similar architectures of the PRACE initiative (
+Partnership  for Advanced  Computing in  Europe)  which aims  at proposing  high
+performance supercomputing architecture to enhance research in Europe. The Curie
+architecture is composed of Intel E5-2680  processors at 2.7 GHz with 2Gb memory
+by core. The Juqueen architecture is composed  of IBM PowerPC A2 at 1.6 GHz with
+1Gb memory per  core. Both those architecture are equiped  with a dedicated high
+speed network.
+
+
+In  many situations, using  preconditioners is  essential in  order to  find the
+solution of a linear system.  There are many preconditioners available in PETSc.
+For parallel applications all  the preconditioners based on matrix factorization
+are  not  available. In  our  experiments, we  have  tested  different kinds  of
+preconditioners, however  as it is  not the subject  of this paper, we  will not
+present results with many preconditioners. In  practise, we have chosen to use a
+multigrid (mg)  and successive  over-relaxation (sor). For  more details  on the
+preconditioner in PETSc please consult~\cite{petsc-web-page}.

 
 

-In the following larger experiments are described on two large scale architectures: Curie and Juqeen... {\bf description...}\\

 
 
 
 

-{\bf Description of preconditioners}\\
-

 \begin{table*}[htbp]
 \begin{center}
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 
 \begin{table*}[htbp]
 \begin{center}
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 


@@ -895,9 +968,8 @@ In the following larger experiments are described on two large scale architectur
 
 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
 
 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.   Two  preconditioners have  been
-tested: {\it mg} and {\it sor}.   For those experiments,  the number  of components  (or unknowns  of the
-problems)  per processor  is fixed  to 25,000,  also called  weak  scaling. This
+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 unknowns  of the
+problems)  per core  is fixed  to 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  sometimes  to be
 small.
 number can seem relatively small. In fact, for some applications that need a lot
 of  memory, the  number of  components per  processor requires  sometimes  to be
 small.


@@ -944,7 +1016,7 @@ the number of iterations. So, the overall benefit of using TSIRM is interesting.
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 
 \hline
 
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 
 \hline
 

-  nb. cores & threshold   & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain \\ 
+  nb. cores & threshold   & \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      & 8e-5                  & 108.88 & 16,560  & 23.06  &  3,630  & 22.79  & 3,630   & 4.77 \\
 \cline{3-8}
              &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline
   2,048      & 8e-5                  & 108.88 & 16,560  & 23.06  &  3,630  & 22.79  & 3,630   & 4.77 \\


@@ -957,13 +1029,27 @@ the number of iterations. So, the overall benefit of using TSIRM is interesting.
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of FGMRES  and 2 stage FGMRES algorithms for ex54 of Petsc (both with the MG preconditioner) with 25000 components per core on Curie (restart=30, s=12),  time is expressed in seconds.}
+\caption{Comparison of FGMRES  and TSIRM with FGMRES algorithms for ex54 of Petsc (both with the MG preconditioner) with 25,000 components per core on Curie (restart=30, s=12),  time is expressed in seconds.}

 \label{tab:04}
 \end{center}
 \end{table*}
 
 
 \label{tab:04}
 \end{center}
 \end{table*}
 
 

-In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architecture are reported.
+In  Table~\ref{tab:04},  some  experiments   with  example  ex54  on  the  Curie
+architecture are reported.  For this  application, we fixed $\alpha=0.6$.  As it
+can be seen in that Table, the size of the problem has a strong influence on the
+number of iterations to reach the  convergence. That is why we have preferred to
+change the threshold.  If we set  it to $1e-3$ as with the previous application,
+only one iteration is necessray  to reach the convergence. So Table~\ref{tab:04}
+shows the results  of differents executions with differents  number of cores and
+differents thresholds. As  with the previous example, we  can observe that TSIRM
+is faster than FGMRES. The ratio greatly depends on the number of iterations for
+FMGRES to reach the threshold. The greater the number of iterations to reach the
+convergence is, the  better the ratio between our algorithm  and FMGRES is. This
+experiment is  also a  weak scaling with  approximately $25,000$  components per
+core. It can also  be observed that the difference between CGLS  and LSQR is not
+significant. Both can be good but it seems not possible to know in advance which
+one will be the best.

 
 
 \begin{table*}[htbp]
 
 
 \begin{table*}[htbp]


@@ -971,9 +1057,9 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} 
 \hline
 
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} 
 \hline
 

-  nb. cores   & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain & \multicolumn{3}{c|}{efficiency} \\ 
+  nb. cores   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain & \multicolumn{3}{c|}{efficiency} \\ 

 \cline{2-7} \cline{9-11}
 \cline{2-7} \cline{9-11}

-                    & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. &   & GMRES & TS CGLS & TS LSQR\\\hline \hline
+                    & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. &   & FGMRES & TS CGLS & TS LSQR\\\hline \hline

    512              & 3,969.69 & 33,120 & 709.57 & 5,790  & 622.76 & 5,070  & 6.37  &   1    &    1    &     1     \\
    1024             & 1,530.06  & 25,860 & 290.95 & 4,830  & 307.71 & 5,070 & 5.25  &  1.30  &    1.21  &   1.01     \\
    2048             & 919.62    & 31,470 & 237.52 & 8,040  & 194.22 & 6,510 & 4.73  & 1.08   &    .75   &   .80\\
    512              & 3,969.69 & 33,120 & 709.57 & 5,790  & 622.76 & 5,070  & 6.37  &   1    &    1    &     1     \\
    1024             & 1,530.06  & 25,860 & 290.95 & 4,830  & 307.71 & 5,070 & 5.25  &  1.30  &    1.21  &   1.01     \\
    2048             & 919.62    & 31,470 & 237.52 & 8,040  & 194.22 & 6,510 & 4.73  & 1.08   &    .75   &   .80\\


@@ -983,7 +1069,7 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of FGMRES  and 2 stage FGMRES algorithms for ex54 of Petsc (both with the MG preconditioner) with 204,919,225 components on Curie with different number of cores (restart=30, s=12, threshol 5e-5),  time is expressed in seconds.}
+\caption{Comparison of FGMRES  and TSIRM with FGMRES for ex54 of Petsc (both with the MG preconditioner) with 204,919,225 components on Curie with different number of cores (restart=30, s=12, threshold 5e-5),  time is expressed in seconds.}

 \label{tab:05}
 \end{center}
 \end{table*}
 \label{tab:05}
 \end{center}
 \end{table*}


@@ -1008,13 +1094,22 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect
 %%%*********************************************************
 %%%*********************************************************
 
 %%%*********************************************************
 %%%*********************************************************
 

+A novel two-stage iterative  algorithm has been proposed in this article,
+in order to accelerate the convergence Krylov iterative  methods.
+Our TSIRM proposal acts as a merger between Krylov based solvers and
+a least-squares minimization step.
+The convergence of the method has been proven in some situations, while 
+experiments up to 16,394 cores have been led to verify that TSIRM runs
+5 or  7 times  faster than GMRES.
+

 
 

-future plan : \\
-- study other kinds of matrices, problems, inner solvers\\
-- test the influence of all the parameters\\
-- adaptative number of outer iterations to minimize\\
-- other methods to minimize the residuals?\\
-- implement our solver inside PETSc
+For future work, the authors' intention is to investigate 
+other kinds of matrices, problems, and inner solvers. The 
+influence of all parameters must be tested too, while 
+other methods to minimize the residuals must be regarded.
+The number of outer iterations to minimize should become 
+adaptative to improve the overall performances of the proposal.
+Finally, this solver will be implemented inside PETSc.

 
 
 % conference papers do not normally have an appendix
 
 
 % conference papers do not normally have an appendix


@@ -1026,7 +1121,7 @@ future plan : \\
 %%%*********************************************************
 \section*{Acknowledgment}
 This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract
 %%%*********************************************************
 \section*{Acknowledgment}
 This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract

-ANR-11-LABX-01-01).   We acknowledge PRACE  for awarding  us access  to resource
+ANR-11-LABX-01-01).   We acknowledge PRACE  for awarding  us access  to resources

 Curie and Juqueen respectively based in France and Germany.
 
 
 Curie and Juqueen respectively based in France and Germany.
 
 


@@ -1069,4 +1164,3 @@ Curie and Juqueen respectively based in France and Germany.
 
 % that's all folks
 \end{document}
 
 % that's all folks
 \end{document}

-