Première version finalisée de la prop.

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 25f1393e95bfd5d65094c8a57eb03211344bb34b..812326f0a520ef867be69f9f7582e322f3b564fe 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -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  achieve   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


@@ -739,33 +743,45 @@ 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} 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{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. Furthermore, 
+\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
 let $r_k$ be the
 $k$-th residue of TSIRM, then

-we still have:
+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}
 \begin{equation}
 ||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| ,
 \end{equation}

-where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}.
+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}

-We will 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||.$
+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_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{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 that assumption regarding $A$.
+Such 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.

 
 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$ which follows the inductive hypothesis due to Proposition~\ref{prop:saad}.
 
 
 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$ which follows the inductive hypothesis due to Proposition~\ref{prop:saad}.
 


@@ -838,13 +854,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]