blabla

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 7e4945e0f0127478c09f3c6d3ace9f2f6a8bab0e..57cbb068ea60d3c8bfd278be7518b247e3308c5f 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -601,29 +601,29 @@ is summarized while intended perspectives are provided.
 %%%*********************************************************
 \section{Related works}
 \label{sec:02} 
 %%%*********************************************************
 \section{Related works}
 \label{sec:02} 

-Krylov subspace iteration methods have increasingly become useful and successful
-techniques  for  solving  linear,  nonlinear systems  and  eigenvalue  problems,
-especially      since       the      increase      development       of      the
+Krylov subspace iteration methods have increasingly become key
+techniques  for  solving  linear and nonlinear systems,  or  eigenvalue  problems,
+especially      since       the      increasing      development       of      

 preconditioners~\cite{Saad2003,Meijerink77}.  One reason  of  the popularity  of
 preconditioners~\cite{Saad2003,Meijerink77}.  One reason  of  the popularity  of

-these methods is their generality, simplicity and efficiency to solve systems of
+these methods is their generality, simplicity, and efficiency to solve systems of

 equations arising from very large and complex problems.
 
 GMRES is one of the most  widely used Krylov iterative method for solving sparse
 equations arising from very large and complex problems.
 
 GMRES is one of the most  widely used Krylov iterative method for solving sparse

-and large  linear systems. It  is developed by  Saad and al.~\cite{Saad86}  as a
+and large  linear systems. It  has been developed by  Saad \emph{et al.}~\cite{Saad86}  as a

 generalized  method to  deal with  unsymmetric and  non-Hermitian  problems, and
 generalized  method to  deal with  unsymmetric and  non-Hermitian  problems, and

-indefinite symmetric problems too. In its original version called full GMRES, it
+indefinite symmetric problems too. In its original version called full GMRES, this algorithm

 minimizes the residual over the  current Krylov subspace until convergence in at
 minimizes the residual over the  current Krylov subspace until convergence in at

-most $n$ iterations,  where $n$ is the  size of the sparse matrix.  It should be
-noticed that full GMRES is too expensive in the case of large matrices since the
+most $n$ iterations,  where $n$ is the  size of the sparse matrix.  
+Full GMRES is however too much expensive in the case of large matrices, since the

 required orthogonalization  process per  iteration grows quadratically  with the
 required orthogonalization  process per  iteration grows quadratically  with the

-number of iterations. For that reason, in practice GMRES is restarted after each
-$m\ll n$ iterations to avoid the  storage of a large orthonormal basis. However,
+number of iterations. For that reason, GMRES is restarted in practice after each
+$m\ll n$ iterations, to avoid the  storage of a large orthonormal basis. However,

 the  convergence behavior  of the  restarted GMRES,  called GMRES($m$),  in many
 the  convergence behavior  of the  restarted GMRES,  called GMRES($m$),  in many

-cases depends quite critically on  the value of $m$~\cite{Huang89}. Therefore in
+cases depends quite critically on  the $m$ value~\cite{Huang89}. Therefore in

 most cases, a preconditioning technique is applied to the restarted GMRES method
 in order to improve its convergence.
 
 most cases, a preconditioning technique is applied to the restarted GMRES method
 in order to improve its convergence.
 

-In order to enhance the robustness of Krylov iterative solvers, some techniques have been proposed allowing the use of different preconditioners, if necessary, within the iteration instead of restarting. Those techniques may lead to considerable savings in CPU time and memory requirements. Van der Vorst in~\cite{Vorst94} has proposed variants of the GMRES algorithm in which a different preconditioner is applied in each iteration, so-called GMRESR family of nested methods. In fact, the GMRES method is effectively preconditioned with other iterative schemes (or GMRES itself), where the iterations of the GMRES method are called outer iterations while the iterations of the preconditioning process referred to as inner iterations. Saad in~\cite{Saad:1993} has proposed FGMRES which is another variant of the GMRES algorithm using a variable preconditioner. In FGMRES the search directions are preconditioned whereas in GMRESR the residuals are preconditioned. However in practice the good preconditioners are those based on direct methods, as ILU preconditioners, which are not easy to parallelize and suffer from the scalability problems on large clusters of thousands of cores.  
+To enhance the robustness of Krylov iterative solvers, some techniques have been proposed allowing the use of different preconditioners, if necessary, within the iteration instead of restarting. Those techniques may lead to considerable savings in CPU time and memory requirements. Van der Vorst in~\cite{Vorst94} has proposed variants of the GMRES algorithm in which a different preconditioner is applied in each iteration, so-called GMRESR family of nested methods. In fact, the GMRES method is effectively preconditioned with other iterative schemes (or GMRES itself), where the iterations of the GMRES method are called outer iterations while the iterations of the preconditioning process referred to as inner iterations. Saad in~\cite{Saad:1993} has proposed FGMRES which is another variant of the GMRES algorithm using a variable preconditioner. In FGMRES the search directions are preconditioned whereas in GMRESR the residuals are preconditioned. However in practice the good preconditioners are those based on direct methods, as ILU preconditioners, which are not easy to parallelize and suffer from the scalability problems on large clusters of thousands of cores.  

 
 Recently, communication-avoiding methods have been developed to reduce the communication overheads in Krylov subspace iterative solvers. On modern computer architectures, communications between processors are much slower than floating-point arithmetic operations on a given processor. Communication-avoiding techniques reduce either communications between processors or data movements between levels of the memory hierarchy, by reformulating the communication-bound kernels (more frequently SpMV kernels) and the orthogonalization operations within the Krylov iterative solver. Different works have studied the communication-avoiding techniques for the GMRES method, so-called CA-GMRES, on multicore processors and multi-GPU machines~\cite{Mohiyuddin2009,Hoemmen2010,Yamazaki2014}. 
 
 
 Recently, communication-avoiding methods have been developed to reduce the communication overheads in Krylov subspace iterative solvers. On modern computer architectures, communications between processors are much slower than floating-point arithmetic operations on a given processor. Communication-avoiding techniques reduce either communications between processors or data movements between levels of the memory hierarchy, by reformulating the communication-bound kernels (more frequently SpMV kernels) and the orthogonalization operations within the Krylov iterative solver. Different works have studied the communication-avoiding techniques for the GMRES method, so-called CA-GMRES, on multicore processors and multi-GPU machines~\cite{Mohiyuddin2009,Hoemmen2010,Yamazaki2014}. 
 


@@ -1138,12 +1138,12 @@ Concerning the  experiments some  other remarks are  interesting.
   examples,  we also obtained  similar gain  between GMRES  and TSIRM  but those
   examples are  not scalable with many  cores. In general, we  had some problems
   with more than $4,096$ cores.
   examples,  we also obtained  similar gain  between GMRES  and TSIRM  but those
   examples are  not scalable with many  cores. In general, we  had some problems
   with more than $4,096$ cores.

-\item We have tested many iterative  solvers available in PETSc.  In fast, it is
+\item We have tested many iterative  solvers available in PETSc.  In fact, it is

   possible to use most of them with TSIRM. From our point of view, the condition
   to  use  a  solver inside  TSIRM  is  that  the  solver  must have  a  restart
   possible to use most of them with TSIRM. From our point of view, the condition
   to  use  a  solver inside  TSIRM  is  that  the  solver  must have  a  restart

-  feature. More  precisely, the solver must  support to be  stoped and restarted
+  feature. More  precisely, the solver must  support to be  stopped and restarted

   without decrease its  converge. That is why  with GMRES we stop it  when it is
   without decrease its  converge. That is why  with GMRES we stop it  when it is

-  naturraly  restarted (i.e.  with  $m$ the  restart parameter).   The Conjugate
+  naturally  restarted (i.e.  with  $m$ the  restart parameter).   The Conjugate

   Gradient (CG) and all its variants do not have ``restarted'' version in PETSc,
   so they  are not  efficient.  They  will converge with  TSIRM but  not quickly
   because if  we compare  a normal CG  with a CG  for which  we stop it  each 16
   Gradient (CG) and all its variants do not have ``restarted'' version in PETSc,
   so they  are not  efficient.  They  will converge with  TSIRM but  not quickly
   because if  we compare  a normal CG  with a CG  for which  we stop it  each 16