10-10-2014 05

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 15a45f01b040b1c1e94e37ab157aab8906124fd3..4cd16c3355ff4b1402e9093542b26d33c6606af7 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -370,10 +370,7 @@
 % paper title
 % can use linebreaks \\ within to get better formatting as desired
 \title{TSIRM: A Two-Stage Iteration with least-square Residual Minimization algorithm to solve large sparse linear systems}
 % paper title
 % can use linebreaks \\ within to get better formatting as desired
 \title{TSIRM: A Two-Stage Iteration with least-square Residual Minimization algorithm to solve large sparse linear systems}

-%où
-%\title{A two-stage algorithm with error minimization to solve large sparse linear systems}
-%où
-%\title{???}
+

 
 
 
 
 
 


@@ -428,16 +425,16 @@ Email: lilia.ziane@inria.fr}
 
 
 \begin{abstract}
 
 
 \begin{abstract}

-In  this article,  a  two-stage  iterative method is proposed to improve  the
-convergence of Krylov based iterative ones,  typically those of GMRES variants. The
+In  this article,  a  two-stage  iterative algorithm is proposed to improve  the
+convergence of Krylov based iterative methods,  typically those of GMRES variants. The

 principle of  the proposed approach  is to  build an external  iteration over  the Krylov
 method, and to  frequently store its current  residual   (at  each
 GMRES restart for instance). After a given number of outer iterations, a minimization
 step  is applied  on the  matrix composed by the  saved residuals,  in  order to
 principle of  the proposed approach  is to  build an external  iteration over  the Krylov
 method, and to  frequently store its current  residual   (at  each
 GMRES restart for instance). After a given number of outer iterations, a minimization
 step  is applied  on the  matrix composed by the  saved residuals,  in  order to

-compute a better solution while making  new iterations if required.  It is proven that
+compute a better solution and to make  new iterations if required.  It is proven that

 the proposal has  the same convergence properties than the  inner embedded method itself. 
 Experiments using up  to 16,394 cores also show that the proposed algorithm
 the proposal has  the same convergence properties than the  inner embedded method itself. 
 Experiments using up  to 16,394 cores also show that the proposed algorithm

-run around 7 times faster than GMRES.
+runs around 5 or 7 times faster than GMRES.

 \end{abstract}
 
 \begin{IEEEkeywords}
 \end{abstract}
 
 \begin{IEEEkeywords}


@@ -607,7 +604,7 @@ is summarized while intended perspectives are provided.
 
 %%%*********************************************************
 %%%*********************************************************
 
 %%%*********************************************************
 %%%*********************************************************

-\section{Two-stage algorithm with least-square residuals minimization}
+\section{Two-stage iteration with least-square residuals minimization algorithm}

 \label{sec:03}
 A two-stage algorithm is proposed  to solve large  sparse linear systems  of the
 form  $Ax=b$,  where  $A\in\mathbb{R}^{n\times   n}$  is  a  sparse  and  square
 \label{sec:03}
 A two-stage algorithm is proposed  to solve large  sparse linear systems  of the
 form  $Ax=b$,  where  $A\in\mathbb{R}^{n\times   n}$  is  a  sparse  and  square


@@ -629,8 +626,8 @@ inner solver. The current approximation of the Krylov method is then stored insi
 $S$ composed by the successive solutions that are computed during inner iterations.
 
 At each $s$ iterations, the minimization step is applied in order to
 $S$ composed by the successive solutions that are computed during inner iterations.
 
 At each $s$ iterations, the minimization step is applied in order to

-compute a new  solution $x$. For that, the previous  residuals are computed with
-$(b-AS)$. The minimization of the residuals is obtained by 
+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}
 \begin{equation}
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}


@@ -639,7 +636,7 @@ with $R=AS$. Then the new solution $x$ is 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}$,

-with $s\ll n$.   In order  to minimize~(\eqref{eq:01}), a  least-square method  such as
+with $s\ll n$.   In order  to minimize~\eqref{eq:01}, a  least-square method  such as

 CGLS ~\cite{Hestenes52}  or LSQR~\cite{Paige82} is used. Remark that these  methods are more
 appropriate than a single direct method in a parallel context.
 
 CGLS ~\cite{Hestenes52}  or LSQR~\cite{Paige82} is used. Remark that these  methods are more
 appropriate than a single direct method in a parallel context.
 


@@ -657,7 +654,7 @@ appropriate than a single direct method in a parallel context.
     \State $S_{k \mod s}=x^k$ \label{algo:store}
     \If {$k \mod s=0$ {\bf and} error$>\epsilon_{kryl}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}
     \State $S_{k \mod s}=x^k$ \label{algo:store}
     \If {$k \mod s=0$ {\bf and} error$>\epsilon_{kryl}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}

-            \State Solve least-square problem $\underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2$ \label{algo:}
+            \State $\alpha=Solve\_Least\_Squares(R,b,max\_iter_{ls})$ \label{algo:}

       \State $x^k=S\alpha$  \Comment{compute new solution}
     \EndIf
   \EndFor
       \State $x^k=S\alpha$  \Comment{compute new solution}
     \EndIf
   \EndFor


@@ -675,7 +672,7 @@ $\epsilon_{tsirm}$).  Line~\ref{algo:store}, $S_{k~ mod~ s}=x^k$ consists in cop
 solution  $x_k$  into the  column  $k~ mod~ s$ of  the  matrix  $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
 solution  $x_k$  into the  column  $k~ mod~ s$ of  the  matrix  $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 iteration and the threshold to stop the
+required for that: the maximum number of iterations and the threshold to stop the

 method.
 
 Let us summarize the most important parameters of TSIRM:
 method.
 
 Let us summarize the most important parameters of TSIRM:


@@ -698,7 +695,7 @@ colums in  practice. As explained  previously, at least  two methods seem  to be
 interesting to solve the least-square minimization, CGLS and LSQR.
 
 In the following  we remind the CGLS algorithm. The LSQR  method follows more or
 interesting to solve the least-square minimization, CGLS and LSQR.
 
 In the following  we remind the CGLS algorithm. The LSQR  method follows more or

-less the same principle but it take more place, so we briefly explain the parallelization of CGLS which is similar to LSQR.
+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{algorithm}[t]
 \caption{CGLS}


@@ -725,7 +722,7 @@ less the same principle but it take more place, so we briefly explain the parall
 
 
 In each iteration  of CGLS, there is two  matrix-vector multiplications and some
 
 
 In each iteration  of CGLS, there is two  matrix-vector multiplications and some

-classical operations:  dots, norm, multiplication  and addition on  vectors. All
+classical operations:  dot product, norm, multiplication  and addition on  vectors. All

 these operations are easy to implement in PETSc or similar environment.
 
 
 these operations are easy to implement in PETSc or similar environment.
 
 


@@ -757,18 +754,18 @@ 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
 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 is given.
+and the number of nonzero elements are given.

 
 

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

 \begin{center}
 \begin{tabular}{|c|c|r|r|r|} 
 \hline
 Matrix name              & Field             &\# Rows   & \# Nonzeros   \\\hline \hline
 crashbasis         & Optimization      & 160,000  &  1,750,416  \\
 \begin{center}
 \begin{tabular}{|c|c|r|r|r|} 
 \hline
 Matrix name              & Field             &\# Rows   & \# Nonzeros   \\\hline \hline
 crashbasis         & Optimization      & 160,000  &  1,750,416  \\

-parabolic\_fem     & Computational fluid dynamics  & 525,825 & 2,100,225 \\
+parabolic\_fem     & Comput. fluid dynamics  & 525,825 & 2,100,225 \\

 epb3               & Thermal problem   & 84,617  & 463,625  \\
 epb3               & Thermal problem   & 84,617  & 463,625  \\

-atmosmodj          & Computational fluid dynamics  & 1,270,432 & 8,814,880 \\
-bfwa398            & Electromagnetics problem & 398 & 3,678 \\
+atmosmodj          & Comput. fluid dynamics  & 1,270,432 & 8,814,880 \\
+bfwa398            & Electromagnetics pb & 398 & 3,678 \\

 torso3             & 2D/3D problem & 259,156 & 4,429,042 \\
 \hline
 
 torso3             & 2D/3D problem & 259,156 & 4,429,042 \\
 \hline
 


@@ -776,11 +773,11 @@ torso3             & 2D/3D problem & 259,156 & 4,429,042 \\
 \caption{Main characteristics of the sparse matrices chosen from the Davis collection}
 \label{tab:01}
 \end{center}
 \caption{Main characteristics of the sparse matrices chosen from the Davis collection}
 \label{tab:01}
 \end{center}

-\end{table*}
+\end{table}

 
 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 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, $max\_iter_{kryl}=30$).  $s$ is set to 8. CGLS is
+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:
 $\epsilon_{ls}=1e-40$ and $max\_iter_{ls}=20$.  The external precision is set to
 $\epsilon_{tsirm}=1e-10$.  Those  experiments have been performed  on a Intel(R)
 chosen  to minimize  the least-squares  problem with  the  following parameters:
 $\epsilon_{ls}=1e-40$ and $max\_iter_{ls}=20$.  The external precision is set to
 $\epsilon_{tsirm}=1e-10$.  Those  experiments have been performed  on a Intel(R)


@@ -792,7 +789,7 @@ 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
 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 is used.  This Table shows that TSIRM can drastically reduce the
+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
 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


@@ -826,12 +823,12 @@ torso3             & fgmres / sor  & 37.70 & 565 & 34.97 & 510 \\
 
 
 
 
 
 

-In order to perform larger  experiments, we have tested some example application
+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}
 \item ex15  is an example  which solves in  parallel an operator using  a finite
 of PETSc. Those  applications are available in the ksp part  which is suited for
 scalable linear equations solvers:
 \begin{itemize}
 \item ex15  is an example  which solves in  parallel an operator using  a finite

-  difference  scheme.   The  diagonal  is  equals to  4  and  4  extra-diagonals
+  difference  scheme.   The  diagonal  is  equal to  4  and  4  extra-diagonals

   representing the neighbors in each directions  is equal to -1. This example is
   used  in many  physical phenomena, for  example, heat  and fluid  flow, wave
   propagation...
   representing the neighbors in each directions  is equal to -1. This example is
   used  in many  physical phenomena, for  example, heat  and fluid  flow, wave
   propagation...


@@ -882,23 +879,20 @@ 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.
 
 of  memory, the  number of  components per  processor requires  sometimes  to be
 small.
 

+
+

 In this Table, we  can notice that TSIRM is always faster  than FGMRES. The last
 column shows the ratio between FGMRES and the best version of TSIRM according to
 the minimization  procedure: CGLS or  LSQR. Even if  we have computed  the worst
 case  between CGLS  and LSQR,  it is  clear that  TSIRM is  alsways  faster than
 FGMRES. For this example, the  multigrid preconditionner is faster than SOR. The
 gain  between   TSIRM  and  FGMRES  is   more  or  less  similar   for  the  two
 In this Table, we  can notice that TSIRM is always faster  than FGMRES. The last
 column shows the ratio between FGMRES and the best version of TSIRM according to
 the minimization  procedure: CGLS or  LSQR. Even if  we have computed  the worst
 case  between CGLS  and LSQR,  it is  clear that  TSIRM is  alsways  faster than
 FGMRES. For this example, the  multigrid preconditionner is faster than SOR. The
 gain  between   TSIRM  and  FGMRES  is   more  or  less  similar   for  the  two

-preconditioners.
-
-In  Figure~\ref{fig:01}, the number  of iterations  per second  corresponding to
-Table~\ref{tab:01} is displayed.  It should  be noticed that for TSIRM, only the
-iterations of  the Krylov solver are  taken into account. Iterations  of CGLS or
-LSQR are  not recorded but they are  time-consuming. It can be  noticed that the
-number of iterations  per second of FMGRES is constant  whereas it decrease with
-TSIRM with both preconditioner. This can  be explained by the fact that when the
-number of core  increases the time for the minimization  step also increases but
-it  is  also  more efficient  to reduce the number of iterations.
-
+preconditioners.  Looking at the number  of iterations to reach the convergence,
+it is  obvious that TSIRM allows the  reduction of the number  of iterations. It
+should be noticed  that for TSIRM, in those experiments,  only the iterations of
+the Krylov solver  are taken into account.  Iterations of CGLS  or LSQR were not
+recorded but they are time-consuming. In general each $max\_iter_{kryl}*s$ which
+corresponds to 30*12, there are $max\_iter_{ls}$ which corresponds to 15.

 
 \begin{figure}[htbp]
 \centering
 
 \begin{figure}[htbp]
 \centering


@@ -908,6 +902,17 @@ it  is  also  more efficient  to reduce the number of iterations.
 \end{figure}
 
 
 \end{figure}
 
 

+In  Figure~\ref{fig:01}, the number  of iterations  per second  corresponding to
+Table~\ref{tab:01}  is  displayed.   It  can  be  noticed  that  the  number  of
+iterations per second of FMGRES is  constant whereas it decrease with TSIRM with
+both preconditioner. This  can be explained by the fact that  when the number of
+core increases the time for the minimization step also increases but, generally,
+when  the number  of cores  increases,  the number  of iterations  to reach  the
+threshold also increases,  and, in that case, TSIRM is  more efficient to reduce
+the number of iterations. So, the overall benefit of using TSIRM is interesting.
+
+
+

 
 
 
 
 
 


@@ -935,7 +940,7 @@ it  is  also  more efficient  to reduce the number of iterations.
 \end{table*}
 
 
 \end{table*}
 
 

-
+In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architecture are reported.

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