ajout 1ere expes

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 8bef816d7236b576fe1c43b789d93d3bdaddf081..36298aa5ea5d0e07e8be169e7918b43b4b4d74dc 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -353,6 +353,7 @@
 \usepackage{algpseudocode}
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage{algpseudocode}
 \usepackage{amsmath}
 \usepackage{amssymb}

+\usepackage{multirow}

 
 \algnewcommand\algorithmicinput{\textbf{Input:}}
 \algnewcommand\Input{\item[\algorithmicinput]}
 
 \algnewcommand\algorithmicinput{\textbf{Input:}}
 \algnewcommand\Input{\item[\algorithmicinput]}


@@ -431,7 +432,7 @@ Email: lilia.ziane@inria.fr}
 \end{abstract}
 
 \begin{IEEEkeywords}
 \end{abstract}
 
 \begin{IEEEkeywords}

-Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à voir... 
+Iterative Krylov methods; sparse linear systems; error minimization; PETSc; %à voir... 

 \end{IEEEkeywords}
 
 
 \end{IEEEkeywords}
 
 


@@ -538,12 +539,42 @@ Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à
 % no \IEEEPARstart
 % You must have at least 2 lines in the paragraph with the drop letter
 % (should never be an issue)
 % no \IEEEPARstart
 % You must have at least 2 lines in the paragraph with the drop letter
 % (should never be an issue)

-Iterative methods are become more attractive than direct ones to solve large sparse linear systems. They are more effective in a parallel context and require less memory and arithmetic operations than direct methods. A number of iterative methods are proposed and adapted by many researchers and the increased need for solving very large sparse linear systems triggered the development of efficient iterative techniques suitable for the parallel processing.
-
-The most successful iterative methods currently available are those based on the Krylov subspace which consists in forming a basis of a sequence of successive matrix powers times the initial residual. These methods are based on orthogonality of vectors of the Krylov subspace basis to solve generalized linear systems. The most well-known iterative Krylov subspace methods are Conjugate Gradient method and GMRES method (generalized minimal residual).
-
-However, the iterative methods suffer from scalability problems on parallel computing platforms with many processors due to their need for reduction operations and collective communications to perform matrix-vector multiplications. 
-
+Iterative  methods are become  more attractive  than direct  ones to  solve very
+large sparse linear  systems. They are more effective in  a parallel context and
+require less memory  and arithmetic operations than direct  methods. A number of
+iterative methods are proposed and adapted by many researchers and the increased
+need for solving  very large sparse linear systems  triggered the development of
+efficient iterative techniques suitable for the parallel processing.
+
+Most of the successful iterative methods currently available are based on Krylov
+subspaces which  consist in forming a  basis of a sequence  of successive matrix
+powers times an initial vector for example the residual. These methods are based
+on  orthogonality  of vectors  of  the Krylov  subspace  basis  to solve  linear
+systems.  The  most well-known iterative  Krylov subspace methods  are Conjugate
+Gradient method and GMRES method (generalized minimal residual).
+
+However,  iterative  methods suffer  from scalability  problems  on parallel
+computing  platforms  with many  processors  due  to  their need  for  reduction
+operations    and   collective    communications   to    perform   matrix-vector
+multiplications. The  communications on large  clusters with thousands  of cores
+and  large  sizes of  messages  can  significantly  affect the  performances  of
+iterative methods. In practice, Krylov subspace iteration methods are often used
+with preconditioners in order to increase their convergence and accelerate their
+performances.  However, most  of the  good preconditioners  are not  scalable on
+large clusters.
+
+In this  paper we propose a  two-stage algorithm based on  two nested iterations
+called inner-outer  iterations.  This algorithm  consists in solving  the sparse
+linear system iteratively  with a small number of  inner iterations and restarts
+the outer step with a new solution minimizing some error functions over a Krylov
+subspace. This algorithm is iterative  and easy to parallelize on large clusters
+and the minimization technique improves its convergence and performances.
+
+The present paper is organized  as follows. In Section~\ref{sec:02} some related
+works are presented. Section~\ref{sec:03} presents our two-stage algorithm based
+on   Krylov  subspace   iteration  methods.   Section~\ref{sec:04}   shows  some
+experimental results obtained on large  clusters of our algorithm using routines
+of PETSc toolkit.

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


@@ -552,6 +583,7 @@ However, the iterative methods suffer from scalability problems on parallel comp
 %%%*********************************************************
 %%%*********************************************************
 \section{Related works}
 %%%*********************************************************
 %%%*********************************************************
 \section{Related works}

+\label{sec:02} 

 %Wherever Times is specified, Times Roman or Times New Roman may be used. If neither is available on your system, please use the font closest in appearance to Times. Avoid using bit-mapped fonts if possible. True-Type 1 or Open Type fonts are preferred. Please embed symbol fonts, as well, for math, etc.
 %%%*********************************************************
 %%%*********************************************************
 %Wherever Times is specified, Times Roman or Times New Roman may be used. If neither is available on your system, please use the font closest in appearance to Times. Avoid using bit-mapped fonts if possible. True-Type 1 or Open Type fonts are preferred. Please embed symbol fonts, as well, for math, etc.
 %%%*********************************************************
 %%%*********************************************************


@@ -561,13 +593,30 @@ However, the iterative methods suffer from scalability problems on parallel comp
 %%%*********************************************************
 %%%*********************************************************
 \section{A Krylov two-stage algorithm}
 %%%*********************************************************
 %%%*********************************************************
 \section{A Krylov two-stage algorithm}

-We propose a two-stage algorithm to solve large sparse linear systems of the form $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ is a sparse and square nonsingular matrix, $x\in\mathbb{R}^n$ is the solution vector and $b\in\mathbb{R}^n$ is the right-hand side. The algorithm is implemented as an inner-outer iteration solver based on iterative Krylov methods. The main key points of our solver are given in Algorithm~\ref{algo:01}. 
-
-In order to accelerate the convergence, the outer iteration is implemented as an iterative Krylov method which minimizes some error function over a Krylov sub-space~\cite{saad96}. At every iteration, the sparse linear system $Ax=b$ is solved iteratively with an iterative method as GMRES method~\cite{saad86} and the Krylov sub-space that we used is spanned by a basis $S$ composed of successive solutions issued from the inner iteration
+\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
+nonsingular   matrix,   $x\in\mathbb{R}^n$    is   the   solution   vector   and
+$b\in\mathbb{R}^n$ is  the right-hand side.  The algorithm is implemented  as an
+inner-outer iteration  solver based  on iterative Krylov  methods. The  main key
+points of our solver are given in Algorithm~\ref{algo:01}.
+
+In order to accelerate the convergence, the outer iteration is implemented as an
+iterative  Krylov method  which minimizes  some  error functions  over a  Krylov
+subspace~\cite{saad96}. At  each iteration, the  sparse linear system  $Ax=b$ is
+solved   iteratively    with   an   iterative   method,    for   example   GMRES
+method~\cite{saad86} or  some of its variants,  and the Krylov  subspace that we
+used is spanned by a basis  $S$ composed of successive solutions issued from the
+inner iteration

 \begin{equation}
   S = \{x^1, x^2, \ldots, x^s\} \text{,~} s\leq n.
 \end{equation} 
 \begin{equation}
   S = \{x^1, x^2, \ldots, x^s\} \text{,~} s\leq n.
 \end{equation} 

-The advantage of such a Krylov subspace is that we neither need an orthogonal basis nor any synchronization between processors to generate this basis. The algorithm is periodically restarted every $s$ iterations with a new initial guess $x=S\alpha$ which minimizes the residual norm $\|b-Ax\|_2$ over the Krylov subspace spanned by vectors of $S$, where $\alpha$ is a solution of the normal equations
+The advantage  of such a Krylov subspace  is that we neither  need an orthogonal
+basis nor  any synchronization  between processors to  generate this  basis. The
+algorithm  is periodically  restarted every  $s$ iterations  with a  new initial
+guess $x=S\alpha$ which minimizes the residual norm $\|b-Ax\|_2$ over the Krylov
+subspace spanned by  vectors of $S$, where $\alpha$ is a  solution of the normal
+equations

 \begin{equation}
   R^TR\alpha = R^Tb,
 \end{equation}
 \begin{equation}
   R^TR\alpha = R^Tb,
 \end{equation}


@@ -576,7 +625,11 @@ which is associated with the least-squares problem
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}
 \end{equation}
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}
 \end{equation}

-such that $R=AS$ is a dense rectangular matrix in $\mathbb{R}^{n\times s}$, $s\ll n$, and $R^T$ denotes the transpose of matrix $R$. We use an iterative method to solve the least-squares problem~(\ref{eq:01}) as CGLS~\cite{hestenes52} or LSQR~\cite{paige82} methods which is more appropriate than a direct method in the parallel context.
+such  that $R=AS$  is a  dense rectangular  matrix in  $\mathbb{R}^{n\times s}$,
+$s\ll n$,  and $R^T$ denotes  the transpose of  matrix $R$. We use  an iterative
+method   to  solve   the  least-squares   problem~(\ref{eq:01})  such   as  CGLS
+~\cite{hestenes52}  or LSQR~\cite{paige82}  which  are more  appropriate than  a
+direct method in the parallel context.

 
 \begin{algorithm}[t]
 \caption{A Krylov two-stage algorithm}
 
 \begin{algorithm}[t]
 \caption{A Krylov two-stage algorithm}


@@ -586,17 +639,21 @@ such that $R=AS$ is a dense rectangular matrix in $\mathbb{R}^{n\times s}$, $s\l
   \State Set the initial guess $x^0$
   \For {$k=1,2,3,\ldots$ until convergence}
     \State Solve iteratively $Ax^k=b$
   \State Set the initial guess $x^0$
   \For {$k=1,2,3,\ldots$ until convergence}
     \State Solve iteratively $Ax^k=b$

-    \State Add vector $x^k$ to Krylov subspace basis $S$
+    \State $S_{k~mod~s}=x^k$ 

     \If {$k$ mod $s=0$ {\bf and} not convergence}
       \State Compute dense matrix $R=AS$
       \State Solve least-squares problem $\underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2$
       \State Compute minimizer $x^k=S\alpha$
     \If {$k$ mod $s=0$ {\bf and} not convergence}
       \State Compute dense matrix $R=AS$
       \State Solve least-squares problem $\underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2$
       \State Compute minimizer $x^k=S\alpha$

-      \State Reinitialize Krylov subspace basis $S$

     \EndIf
   \EndFor
 \end{algorithmic}
 \label{algo:01}
 \end{algorithm}
     \EndIf
   \EndFor
 \end{algorithmic}
 \label{algo:01}
 \end{algorithm}

+
+Operation $S_{k~  mod~ s}=x^k$ consists in  copying the residual  $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.
+

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


@@ -605,6 +662,67 @@ such that $R=AS$ is a dense rectangular matrix in $\mathbb{R}^{n\times s}$, $s\l
 %%%*********************************************************
 %%%*********************************************************
 \section{Experiments using petsc}
 %%%*********************************************************
 %%%*********************************************************
 \section{Experiments using petsc}

+\label{sec:04}
+
+
+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.
+
+\begin{table}
+\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 \\
+epb3               & Thermal problem   & 84,617  & 463,625  \\
+atmosmodj          & Computational fluid dynamics  & 1,270,432 & 8,814,880 \\
+bfwa398            & Electromagnetics problem & 398 & 3,678 \\
+torso3             & 2D/3D problem & 259,156 & 4,429,042 \\
+\hline
+
+\end{tabular}
+\caption{Main characteristics of the sparse matrices chosen from the Davis collection}
+\label{tab:01}
+\end{center}
+\end{table}
+
+
+
+
+\begin{table}
+\begin{center}
+\begin{tabular}{|c|c|r|r|r|r|} 
+\hline
+
+ \multirow{2}{*}{Matrix name}  & Solver /   & \multicolumn{2}{c|}{gmres variant} & \multicolumn{2}{c|}{2 stage} \\
+       &  precond             & Time  & \# Iter.  & Time  & \# Iter.  \\\hline \hline
+
+crashbasis         & gmres / none             &  15.65     & 518  &  14.12 & 450  \\
+parabolic\_fem     & gmres / ilu           &  2152  & ?? & 724 & ?? \\
+epb3               & fgmres / sor             &  8.67     & 600  &  8.21 & 540  \\
+atmosmodj          &  fgmres / sor & 104.23  & 451 & 88.97 & 366  \\
+bfwa398            & gmres / none  & 1.42 & 9612 & 0.28 & 1650 \\
+torso3             & fgmres/sor  & 565  & 37.70 & 34.97 & 510 \\
+\hline
+
+\end{tabular}
+\caption{Comparison of GMRES and 2 stage GMRES algorithms in sequential with some matrices, time is expressed in seconds.}
+\label{tab:02}
+\end{center}
+\end{table}
+
+
+Param : retart 30 iters
+cols = 8
+iter cgls = 20
+cgls prec = 1e-40
+prec = 1e-10
+Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz
+
+

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


@@ -613,6 +731,7 @@ such that $R=AS$ is a dense rectangular matrix in $\mathbb{R}^{n\times s}$, $s\l
 %%%*********************************************************
 %%%*********************************************************
 \section{Conclusion}
 %%%*********************************************************
 %%%*********************************************************
 \section{Conclusion}

+\label{sec:05}

 %The conclusion goes here. this is more of the conclusion
 %%%*********************************************************
 %%%*********************************************************
 %The conclusion goes here. this is more of the conclusion
 %%%*********************************************************
 %%%*********************************************************