09-01-2014

[Krylov_multi.git] / krylov_multi.tex

diff --git a/krylov_multi.tex b/krylov_multi.tex
index 3295c82e9c5b16cdeb4287c5192d00e088bfb3e8..48d9e2e191998300b47a9534c27a1dd89c622534 100644 (file)
--- a/krylov_multi.tex
+++ b/krylov_multi.tex
@@ -38,9 +38,14 @@ classical GMRES both in terms of number of iterations and execution times.
 
 Iterative methods are used to solve  large sparse linear systems of equations of
 the form  $Ax=b$ because they are  easier to parallelize than  direct ones. Many
 
 Iterative methods are used to solve  large sparse linear systems of equations of
 the form  $Ax=b$ because they are  easier to parallelize than  direct ones. Many

-iterative  methods have  been proposed  and  adapted by  many researchers.  When
-solving large  linear systems  with many cores,  iterative methods  often suffer
-from  scalability  problems.    This  is  due  to  their   need  for  collective
+iterative  methods have  been proposed  and  adapted by  many researchers.   For
+example, the GMRES method and the  Conjugate Gradient method are very well known
+and  used by  many researchers  ~\cite{S96}. Both  the method  are based  on the
+Krylov subspace which consists in forming  a basis of the sequence of successive
+matrix powers times the initial residual.
+
+When  solving large  linear systems  with  many cores,  iterative methods  often
+suffer  from scalability problems.   This is  due to  their need  for collective

 communications  to  perform  matrix-vector  products and  reduction  operations.
 Preconditionners can be  used in order to increase  the convergence of iterative
 solvers.   However, most  of the  good preconditionners  are not  sclalable when
 communications  to  perform  matrix-vector  products and  reduction  operations.
 Preconditionners can be  used in order to increase  the convergence of iterative
 solvers.   However, most  of the  good preconditionners  are not  sclalable when


@@ -56,41 +61,49 @@ On ne peut pas parler de tout...\\
 %%%%%%%%%%%%%%%%%%%%%%%
 %% BEGIN
 %%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%
 %% BEGIN
 %%%%%%%%%%%%%%%%%%%%%%%

-The key idea of the multisplitting method for solving a large system of linear equations
-$Ax=b$ consists in partitioning the matrix $A$ in $L$ several ways 
+The key idea  of the multisplitting method for  solving a large system
+of linear equations $Ax=b$ consists  in partitioning the matrix $A$ in
+$L$ several ways

 \begin{equation}
 A = M_l - N_l,~l\in\{1,\ldots,L\},
 \label{eq01}
 \end{equation}
 \begin{equation}
 A = M_l - N_l,~l\in\{1,\ldots,L\},
 \label{eq01}
 \end{equation}

-where $M_l$ are nonsingular matrices. Then the linear system is solved by iteration based
-on the multisplittings as follows  
+where $M_l$ are nonsingular matrices. Then the linear system is solved
+by iteration based on the multisplittings as follows

 \begin{equation}
 x^{k+1}=\displaystyle\sum^L_{l=1} E_l M^{-1}_l (N_l x^k + b),~k=1,2,3,\ldots
 \label{eq02}
 \end{equation}
 \begin{equation}
 x^{k+1}=\displaystyle\sum^L_{l=1} E_l M^{-1}_l (N_l x^k + b),~k=1,2,3,\ldots
 \label{eq02}
 \end{equation}

-where $E_l$ are non-negative and diagonal weighting matrices such that $\sum^L_{l=1}E_l=I$ ($I$ is an identity matrix).
-Thus the convergence of such a method is dependent on the condition
+where $E_l$ are non-negative and diagonal weighting matrices such that
+$\sum^L_{l=1}E_l=I$ ($I$ is an identity matrix).  Thus the convergence
+of such a method is dependent on the condition

 \begin{equation}
 \rho(\displaystyle\sum^L_{l=1}E_l M^{-1}_l N_l)<1.
 \label{eq03}
 \end{equation}
 
 \begin{equation}
 \rho(\displaystyle\sum^L_{l=1}E_l M^{-1}_l N_l)<1.
 \label{eq03}
 \end{equation}
 

-The advantage of the multisplitting method is that at each iteration $k$ there are $L$ different linear
-systems
+The advantage of  the multisplitting method is that  at each iteration
+$k$ there are $L$ different linear sub-systems

 \begin{equation}
 \begin{equation}

-y_l^k=M^{-1}_l N_l x_l^{k-1} + M^{-1}_l b,~l\in\{1,\ldots,L\},
+v_l^k=M^{-1}_l N_l x_l^{k-1} + M^{-1}_l b,~l\in\{1,\ldots,L\},

 \label{eq04}
 \end{equation}
 \label{eq04}
 \end{equation}

-to be solved independently by a direct or an iterative method, where $y_l^k$ is the solution of the local system.
-A multisplitting method using an iterative method for solving the $L$ linear systems is called an inner-outer
-iterative method or a two-stage method. The solution of the global linear system at the iteration $k$ is computed
-as follows
+to be solved  independently by a direct or  an iterative method, where
+$v_l^k$  is   the  solution  of   the  local  sub-system.   Thus,  the
+calculations  of $v_l^k$  may be  performed in  parallel by  a  set of
+processors.   A multisplitting  method using  an iterative  method for
+solving the $L$ linear  sub-systems is called an inner-outer iterative
+method or a  two-stage method.  The results $v_l^k$  obtained from the
+different splittings~(\ref{eq04}) are combined to compute the solution
+$x^k$ of the linear system by using the diagonal weighting matrices

 \begin{equation}
 \begin{equation}

-x^k = \displaystyle\sum^L_{l=1} E_l y_l^k,
+x^k = \displaystyle\sum^L_{l=1} E_l v_l^k,

 \label{eq05}
 \end{equation}    
 \label{eq05}
 \end{equation}    

-In the case where the diagonal weighting matrices $E_l$ have only zero and one factors (i.e. $y_l^k$ are disjoint vectors),
-the multisplitting method is non-overlapping and corresponds to the block Jacobi method.  
+In the case where the diagonal weighting matrices $E_l$ have only zero
+and   one   factors  (i.e.   $v_l^k$   are   disjoint  vectors),   the
+multisplitting method is non-overlapping  and corresponds to the block
+Jacobi method.

 %%%%%%%%%%%%%%%%%%%%%%%
 %% END
 %%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%
 %% END
 %%%%%%%%%%%%%%%%%%%%%%%


@@ -101,15 +114,15 @@ the multisplitting method is non-overlapping and corresponds to the block Jacobi
 A general framework  for studying parallel multisplitting has  been presented in
 \cite{o1985multi} by O'Leary and White. Convergence conditions are given for the
 most general case.  Many authors improved multisplitting algorithms by proposing
 A general framework  for studying parallel multisplitting has  been presented in
 \cite{o1985multi} by O'Leary and White. Convergence conditions are given for the
 most general case.  Many authors improved multisplitting algorithms by proposing

-for  example  a  asynchronous  version  \cite{bru1995parallel}  and  convergence
-condition  \cite{bai1999block,bahi2000asynchronous}   in  this  case   or  other
-two-stage algorithms~\cite{frommer1992h,bru1995parallel}
+for  example  an  asynchronous  version  \cite{bru1995parallel}  and  convergence
+conditions  \cite{bai1999block,bahi2000asynchronous}   in  this  case   or  other
+two-stage algorithms~\cite{frommer1992h,bru1995parallel}.

 
 In  \cite{huang1993krylov},  the  authors  proposed  a  parallel  multisplitting
 algorithm in which all the tasks except  one are devoted to solve a sub-block of
 the splitting  and to send their  local solution to  the first task which  is in
 charge to  combine the vectors at  each iteration.  These vectors  form a Krylov
 
 In  \cite{huang1993krylov},  the  authors  proposed  a  parallel  multisplitting
 algorithm in which all the tasks except  one are devoted to solve a sub-block of
 the splitting  and to send their  local solution to  the first task which  is in
 charge to  combine the vectors at  each iteration.  These vectors  form a Krylov

-basis for  which the first tasks minimize  the error function over  the basis to
+basis for  which the first task minimizes  the error function over  the basis to

 increase the convergence, then the other tasks receive the update solution until
 convergence of the global system. 
 
 increase the convergence, then the other tasks receive the update solution until
 convergence of the global system. 
 


@@ -120,7 +133,11 @@ of multisplitting algorithms that take benefit from multisplitting algorithms to
 solve large scale linear systems. Inner  solvers could be based on scalar direct
 method with the LU method or scalar iterative one with GMRES.
 
 solve large scale linear systems. Inner  solvers could be based on scalar direct
 method with the LU method or scalar iterative one with GMRES.
 

-
+In~\cite{prace-multi},  the  authors  have  proposed a  parallel  multisplitting
+algorithm in which large block are solved using a GMRES solver. The authors have
+performed large scale experimentations upto  32.768 cores and they conclude that
+asynchronous  multisplitting algorithm  could more  efficient  than traditionnal
+solvers on exascale architecture with hunders of thousands of cores.

 
 
 %%%%%%%%%%%%%%%%%%%%%%%%
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%


@@ -144,7 +161,7 @@ b & = & [B_{1}, \ldots, B_{L}]
 \right.
 \label{sec03:eq01}
 \end{equation}  
 \right.
 \label{sec03:eq01}
 \end{equation}  

-where for all $l\in\{1,\ldots,L\}$ $A_l$ is a rectangular block of size $n_l\times n$
+where for $l\in\{1,\ldots,L\}$ $A_l$ is a rectangular block of size $n_l\times n$

 and $X_l$ and $B_l$ are sub-vectors of size $n_l$, such that $\sum_ln_l=n$. In this
 case, we use a row-by-row splitting without overlapping in such a way that successive
 rows of the sparse matrix $A$ and both vectors $x$ and $b$ are assigned to one cluster.
 and $X_l$ and $B_l$ are sub-vectors of size $n_l$, such that $\sum_ln_l=n$. In this
 case, we use a row-by-row splitting without overlapping in such a way that successive
 rows of the sparse matrix $A$ and both vectors $x$ and $b$ are assigned to one cluster.


@@ -155,8 +172,10 @@ So, the multisplitting format of the linear system is defined as follows:
 \end{equation} 
 where $A_{li}$ is a block of size $n_l\times n_i$ of the rectangular matrix $A_l$, $X_i\neq X_l$
 is a sub-vector of size $n_i$ of the solution vector $x$ and $\sum_{i<l}n_i+\sum_{i>l}n_i+n_l=n$,
 \end{equation} 
 where $A_{li}$ is a block of size $n_l\times n_i$ of the rectangular matrix $A_l$, $X_i\neq X_l$
 is a sub-vector of size $n_i$ of the solution vector $x$ and $\sum_{i<l}n_i+\sum_{i>l}n_i+n_l=n$,

-for all $i\in\{1,\ldots,l-1,l+1,\ldots,L\}$. Therefore, each cluster $l$ is in charge of solving
-the following spare sub-linear system: 
+for all $i\in\{1,\ldots,l-1,l+1,\ldots,L\}$. 
+
+The multisplitting method proceeds by iteration for solving the linear system in such a
+way each sub-system

 \begin{equation}
 \left\{
 \begin{array}{l}
 \begin{equation}
 \left\{
 \begin{array}{l}


@@ -166,7 +185,15 @@ Y_l = B_l - \displaystyle\sum_{i=1,i\neq l}^{L}A_{li}X_i,
 \right.
 \label{sec03:eq03}
 \end{equation}
 \right.
 \label{sec03:eq03}
 \end{equation}

-where the sub-vectors $X_i$ define the data dependencies between the cluster $l$ and other clusters.
+is solved independently by a cluster of processors and communication are required to
+update the right-hand side vectors $Y_l$, such that the vectors $X_i$ represent the data
+dependencies between the clusters. In this work, we use the GMRES method as an inner
+iteration method for solving the sub-systems~(\ref{sec03:eq03}). It is a well-known
+iterative method which gives good performances for solving sparse linear systems in
+parallel on a cluster of processors. 
+
+
+