archi

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 08e7b8a01b4ea3bfbf56b0c326fc2a2b78675924..d00cbe105f66a3782e53dde816ca0e89af594740 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -621,19 +621,21 @@ outer solver periodically applies a least-squares minimization  on the residuals
 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 
 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 $s$ iterations, the minimization step is applied in order to
+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, 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}$,


@@ -663,14 +665,15 @@ 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
+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
 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
+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
 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.}
+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
 $\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
+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
 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


@@ -735,7 +738,7 @@ 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}.
+Let us recall the following result, see~\cite{Saad86} for further readings.

 \begin{proposition}
 \label{prop:saad}
 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{proposition}
 \label{prop:saad}
 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:


@@ -885,7 +888,17 @@ For more technical details on  these applications, interested readers are invite
 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.
 
 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... {\bf description...}\\
+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.
+

 
 
 {\bf Description of preconditioners}\\
 
 
 {\bf Description of preconditioners}\\


@@ -1029,6 +1042,15 @@ 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.
+
+

 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 
 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