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 of linear equations
  60 $Ax=b$ consists in partitioning the matrix $A$ in $L$ several ways
  61 \begin{equation}
  62 A = M_l - N_l,~l\in\{1,\ldots,L\},
  63 \label{eq01}
  64 \end{equation}
  65 where $M_l$ are nonsingular matrices. Then the linear system is solved by iteration based
  66 on the multisplittings as follows
  67 \begin{equation}
  68 x^{k+1}=\displaystyle\sum^L_{l=1} E_l M^{-1}_l (N_l x^k + b),~k=1,2,3,\ldots
  69 \label{eq02}
  70 \end{equation}
  71 where $E_l$ are non-negative and diagonal weighting matrices such that $\sum^L_{l=1}E_l=I$ ($I$ is an identity matrix).
  72 Thus the convergence of such a method is dependent on the condition
  73 \begin{equation}
  74 \rho(\displaystyle\sum^L_{l=1}E_l M^{-1}_l N_l)<1.
  75 \label{eq03}
  76 \end{equation}
  77
  78 The advantage of the multisplitting method is that at each iteration $k$ there are $L$ different linear
  79 systems
  80 \begin{equation}
  81 y_l^k=M^{-1}_l N_l x_l^{k-1} + M^{-1}_l b,~l\in\{1,\ldots,L\},
  82 \label{eq04}
  83 \end{equation}
  84 to be solved independently by a direct or an iterative method, where $y_l^k$ is the solution of the local system.
  85 A multisplitting method using an iterative method for solving the $L$ linear systems is called an inner-outer
  86 iterative method or a two-stage method. The solution of the global linear system at the iteration $k$ is computed
  87 as follows
  88 \begin{equation}
  89 x^k = \displaystyle\sum^L_{l=1} E_l y_l^k,
  90 \label{eq05}
  91 \end{equation}
  92 In the case where the diagonal weighting matrices $E_l$ have only zero and one factors (i.e. $y_l^k$ are disjoint vectors),
  93 the multisplitting method is non-overlapping and corresponds to the block Jacobi method.
  94 %%%%%%%%%%%%%%%%%%%%%%%
  95 %% END
  96 %%%%%%%%%%%%%%%%%%%%%%%
  97
  98 \section{Related works}
  99
 100
 101 A general framework  for studying parallel multisplitting has  been presented in
 102 \cite{o1985multi} by O'Leary and White. Convergence conditions are given for the
 103 most general case.  Many authors improved multisplitting algorithms by proposing
 104 for  example  a  asynchronous  version  \cite{bru1995parallel}  and  convergence
 105 condition  \cite{bai1999block,bahi2000asynchronous}   in  this  case   or  other
 106 two-stage algorithms~\cite{frommer1992h,bru1995parallel}
 107
 108 In  \cite{huang1993krylov},  the  authors  proposed  a  parallel  multisplitting
 109 algorithm in which all the tasks except  one are devoted to solve a sub-block of
 110 the splitting  and to send their  local solution to  the first task which  is in
 111 charge to  combine the vectors at  each iteration.  These vectors  form a Krylov
 112 basis for  which the first tasks minimize  the error function over  the basis to
 113 increase the convergence, then the other tasks receive the update solution until
 114 convergence of the global system.
 115
 116
 117
 118 In \cite{couturier2008gremlins}, the  authors proposed practical implementations
 119 of multisplitting algorithms that take benefit from multisplitting algorithms to
 120 solve large scale linear systems. Inner  solvers could be based on scalar direct
 121 method with the LU method or scalar iterative one with GMRES.
 122
 123
 124
 125
 126 %%%%%%%%%%%%%%%%%%%%%%%%
 127 %%%%%%%%%%%%%%%%%%%%%%%%
 128
 129
 130 \section{A two-stage method with a minimization}
 131 Let $Ax=b$ be a given sparse and large linear system of $n$ equations
 132 to solve in parallel on $L$ clusters, physically adjacent or geographically
 133 distant, where $A\in\mathbb{R}^{n\times n}$ is a square and nonsingular
 134 matrix, $x\in\mathbb{R}^{n}$ is the solution vector and $b\in\mathbb{R}^{n}$
 135 is the right-hand side vector. The multisplitting of this linear system
 136 is defined as follows:
 137 \begin{equation}
 138 \left\{
 139 \begin{array}{lll}
 140 A & = & [A_{1}, \ldots, A_{L}]\\
 141 x & = & [X_{1}, \ldots, X_{L}]\\
 142 b & = & [B_{1}, \ldots, B_{L}]
 143 \end{array}
 144 \right.
 145 \label{sec03:eq01}
 146 \end{equation}
 147 where for all $l\in\{1,\ldots,L\}$ $A_l$ is a rectangular block of size $n_l\times n$
 148 and $X_l$ and $B_l$ are sub-vectors of size $n_l$, such that $\sum_ln_l=n$. In this
 149 case, we use a row-by-row splitting without overlapping in such a way that successive
 150 rows of the sparse matrix $A$ and both vectors $x$ and $b$ are assigned to one cluster.
 151 So, the multisplitting format of the linear system is defined as follows:
 152 \begin{equation}
 153 \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,
 154 \label{sec03:eq02}
 155 \end{equation}
 156 where $A_{li}$ is a block of size $n_l\times n_i$ of the rectangular matrix $A_l$, $X_i\neq X_l$
 157 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$,
 158 for all $i\in\{1,\ldots,l-1,l+1,\ldots,L\}$. Therefore, each cluster $l$ is in charge of solving
 159 the following spare sub-linear system:
 160 \begin{equation}
 161 \left\{
 162 \begin{array}{l}
 163 A_{ll}X_l = Y_l \mbox{,~such that}\\
 164 Y_l = B_l - \displaystyle\sum_{i=1,i\neq l}^{L}A_{li}X_i,
 165 \end{array}
 166 \right.
 167 \label{sec03:eq03}
 168 \end{equation}
 169 where the sub-vectors $X_i$ define the data dependencies between the cluster $l$ and other clusters.
 170
 171
 172
 173 %%%%%%%%%%%%%%%%%%%%%%%%
 174 %%%%%%%%%%%%%%%%%%%%%%%%
 175
 176 \bibliographystyle{plain}
 177 \bibliography{biblio}
 178
 179 \end{document}