krylov_multi.tex

   1 \documentclass{article}
   2 \usepackage[utf8]{inputenc}
   3 \usepackage{amsfonts,amssymb}
   4 \usepackage{amsmath}
   5 \usepackage{graphicx}
   6
   7 \title{A scalable multisplitting algorithm for solving large sparse linear systems}
   8
   9
  10
  11 \begin{document}
  12 \author{Raphaël Couturier \and Lilia Ziane Khodja}
  13
  14 \maketitle
  15
  16
  17 %%%%%%%%%%%%%%%%%%%%%%%%
  18 %%%%%%%%%%%%%%%%%%%%%%%%
  19
  20
  21 \begin{abstract}
  22 In  this  paper we  revist  the  krylov  multisplitting algorithm  presented  in
  23 \cite{huang1993krylov}  which  uses  a  scalar  method to  minimize  the  krylov
  24 iterations computed by a multisplitting algorithm. Our new algorithm is based on
  25 a  parallel multisplitting  algorithm  with few  blocks  of large  size using  a
  26 parallel GMRES method inside each block and on a parallel krylov minimization in
  27 order to improve the convergence. Some large scale experiments with a 3D Poisson
  28 problem  are presented.   They  show  the obtained  improvements  compared to  a
  29 classical GMRES both in terms of number of iterations and execution times.
  30 \end{abstract}
  31
  32
  33 %%%%%%%%%%%%%%%%%%%%%%%%
  34 %%%%%%%%%%%%%%%%%%%%%%%%
  35
  36
  37 \section{Introduction}
  38
  39 Iterative methods are used to solve  large sparse linear systems of equations of
  40 the form  $Ax=b$ because they are  easier to parallelize than  direct ones. Many
  41 iterative  methods have  been proposed  and  adapted by  many researchers.  When
  42 solving large  linear systems  with many cores,  iterative methods  often suffer
  43 from  scalability  problems.    This  is  due  to  their   need  for  collective
  44 communications  to  perform  matrix-vector  products and  reduction  operations.
  45 Preconditionners can be  used in order to increase  the convergence of iterative
  46 solvers.   However, most  of the  good preconditionners  are not  sclalable when
  47 thousands of cores are used.
  48
  49
  50 A completer...
  51 On ne peut pas parler de tout...\\
  52
  53
  54
  55
  56 %%%%%%%%%%%%%%%%%%%%%%%
  57 %% BEGIN
  58 %%%%%%%%%%%%%%%%%%%%%%%
  59 The key idea  of the multisplitting method for  solving a large system
  60 of linear equations $Ax=b$ consists  in partitioning the matrix $A$ in
  61 $L$ several ways
  62 \begin{equation}
  63 A = M_l - N_l,~l\in\{1,\ldots,L\},
  64 \label{eq01}
  65 \end{equation}
  66 where $M_l$ are nonsingular matrices. Then the linear system is solved
  67 by iteration based on the multisplittings as follows
  68 \begin{equation}
  69 x^{k+1}=\displaystyle\sum^L_{l=1} E_l M^{-1}_l (N_l x^k + b),~k=1,2,3,\ldots
  70 \label{eq02}
  71 \end{equation}
  72 where $E_l$ are non-negative and diagonal weighting matrices such that
  73 $\sum^L_{l=1}E_l=I$ ($I$ is an identity matrix).  Thus the convergence
  74 of such a method is dependent on the condition
  75 \begin{equation}
  76 \rho(\displaystyle\sum^L_{l=1}E_l M^{-1}_l N_l)<1.
  77 \label{eq03}
  78 \end{equation}
  79
  80 The advantage of  the multisplitting method is that  at each iteration
  81 $k$ there are $L$ different linear sub-systems
  82 \begin{equation}
  83 v_l^k=M^{-1}_l N_l x_l^{k-1} + M^{-1}_l b,~l\in\{1,\ldots,L\},
  84 \label{eq04}
  85 \end{equation}
  86 to be solved  independently by a direct or  an iterative method, where
  87 $v_l^k$  is the solution  of the  local sub-system.   A multisplitting
  88 method  using   an  iterative  method  for  solving   the  $L$  linear
  89 sub-systems is  called an inner-outer iterative method  or a two-stage
  90 method.   The   results    $v_l^k$   obtained   from   the   different
  91 splittings~(\ref{eq04}) are combined to  compute the solution $x^k$ of
  92 the linear system by using the diagonal weighting matrices
  93 \begin{equation}
  94 x^k = \displaystyle\sum^L_{l=1} E_l v_l^k,
  95 \label{eq05}
  96 \end{equation}
  97 In the case where the diagonal weighting matrices $E_l$ have only zero
  98 and   one   factors  (i.e.   $v_l^k$   are   disjoint  vectors),   the
  99 multisplitting method is non-overlapping  and corresponds to the block
 100 Jacobi method.
 101 %%%%%%%%%%%%%%%%%%%%%%%
 102 %% END
 103 %%%%%%%%%%%%%%%%%%%%%%%
 104
 105 \section{Related works}
 106
 107
 108 A general framework  for studying parallel multisplitting has  been presented in
 109 \cite{o1985multi} by O'Leary and White. Convergence conditions are given for the
 110 most general case.  Many authors improved multisplitting algorithms by proposing
 111 for  example  an  asynchronous  version  \cite{bru1995parallel}  and  convergence
 112 conditions  \cite{bai1999block,bahi2000asynchronous}   in  this  case   or  other
 113 two-stage algorithms~\cite{frommer1992h,bru1995parallel}.
 114
 115 In  \cite{huang1993krylov},  the  authors  proposed  a  parallel  multisplitting
 116 algorithm in which all the tasks except  one are devoted to solve a sub-block of
 117 the splitting  and to send their  local solution to  the first task which  is in
 118 charge to  combine the vectors at  each iteration.  These vectors  form a Krylov
 119 basis for  which the first task minimizes  the error function over  the basis to
 120 increase the convergence, then the other tasks receive the update solution until
 121 convergence of the global system.
 122
 123
 124
 125 In \cite{couturier2008gremlins}, the  authors proposed practical implementations
 126 of multisplitting algorithms that take benefit from multisplitting algorithms to
 127 solve large scale linear systems. Inner  solvers could be based on scalar direct
 128 method with the LU method or scalar iterative one with GMRES.
 129
 130 In~\cite{prace-multi},  the  authors  have  proposed a  parallel  multisplitting
 131 algorithm in which large block are solved using a GMRES solver. The authors have
 132 performed large scale experimentations upto  32.768 cores and they conclude that
 133 asynchronous  multisplitting algorithm  could more  efficient  than traditionnal
 134 solvers on exascale architecture with hunders of thousands of cores.
 135
 136
 137 %%%%%%%%%%%%%%%%%%%%%%%%
 138 %%%%%%%%%%%%%%%%%%%%%%%%
 139
 140
 141 \section{A two-stage method with a minimization}
 142 Let $Ax=b$ be a given sparse and large linear system of $n$ equations
 143 to solve in parallel on $L$ clusters, physically adjacent or geographically
 144 distant, where $A\in\mathbb{R}^{n\times n}$ is a square and nonsingular
 145 matrix, $x\in\mathbb{R}^{n}$ is the solution vector and $b\in\mathbb{R}^{n}$
 146 is the right-hand side vector. The multisplitting of this linear system
 147 is defined as follows:
 148 \begin{equation}
 149 \left\{
 150 \begin{array}{lll}
 151 A & = & [A_{1}, \ldots, A_{L}]\\
 152 x & = & [X_{1}, \ldots, X_{L}]\\
 153 b & = & [B_{1}, \ldots, B_{L}]
 154 \end{array}
 155 \right.
 156 \label{sec03:eq01}
 157 \end{equation}
 158 where for all $l\in\{1,\ldots,L\}$ $A_l$ is a rectangular block of size $n_l\times n$
 159 and $X_l$ and $B_l$ are sub-vectors of size $n_l$, such that $\sum_ln_l=n$. In this
 160 case, we use a row-by-row splitting without overlapping in such a way that successive
 161 rows of the sparse matrix $A$ and both vectors $x$ and $b$ are assigned to one cluster.
 162 So, the multisplitting format of the linear system is defined as follows:
 163 \begin{equation}
 164 \forall l\in\{1,\ldots,L\} \mbox{,~} \displaystyle\sum_{i=1}^{l-1}A_{li}X_i + A_{ll}X_l + \displaystyle\sum_{i=l+1}^{L}A_{li}X_i = B_l,
 165 \label{sec03:eq02}
 166 \end{equation}
 167 where $A_{li}$ is a block of size $n_l\times n_i$ of the rectangular matrix $A_l$, $X_i\neq X_l$
 168 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$,
 169 for all $i\in\{1,\ldots,l-1,l+1,\ldots,L\}$.
 170
 171 The multisplitting method proceeds by iteration for solving the linear system in such a
 172 way each sub-system
 173 \begin{equation}
 174 \left\{
 175 \begin{array}{l}
 176 A_{ll}X_l = Y_l \mbox{,~such that}\\
 177 Y_l = B_l - \displaystyle\sum_{i=1,i\neq l}^{L}A_{li}X_i,
 178 \end{array}
 179 \right.
 180 \label{sec03:eq03}
 181 \end{equation}
 182 is solved independently by a cluster of processors and communication are required to
 183 update the right-hand side vectors $Y_l$, such that the vectors $X_i$ represent the data
 184 dependencies between the clusters. In this case, the parallel GMRES method is used
 185 as an inner iteration method for solving the linear sub-systems~(\ref{sec03:eq03}).
 186
 187
 188
 189
 190
 191
 192
 193
 194 %%%%%%%%%%%%%%%%%%%%%%%%
 195 %%%%%%%%%%%%%%%%%%%%%%%%
 196
 197 \bibliographystyle{plain}
 198 \bibliography{biblio}
 199
 200 \end{document}