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 \section{Related works}
  54
  55
  56 A general framework  for studying parallel multisplitting has  been presented in
  57 \cite{o1985multi} by O'Leary and White. Convergence conditions are given for the
  58 most general case.  Many authors improved multisplitting algorithms by proposing
  59 for  example  a  asynchronous  version  \cite{bru1995parallel}  and  convergence
  60 condition  \cite{bai1999block,bahi2000asynchronous}   in  this  case   or  other
  61 two-stage algorithms~\cite{frommer1992h,bru1995parallel}
  62
  63 In  \cite{huang1993krylov},  the  authors  proposed  a  parallel  multisplitting
  64 algorithm in which all the tasks except  one are devoted to solve a sub-block of
  65 the splitting  and to send their  local solution to  the first task which  is in
  66 charge to  combine the vectors at  each iteration.  These vectors  form a Krylov
  67 basis for  which the first tasks minimize  the error function over  the basis to
  68 increase the convergence, then the other tasks receive the update solution until
  69 convergence of the global system.
  70
  71
  72
  73 In \cite{couturier2008gremlins}, the  authors proposed practical implementations
  74 of multisplitting algorithms that take benefit from multisplitting algorithms to
  75 solve large scale linear systems. Inner  solvers could be based on scalar direct
  76 method with the LU method or scalar iterative one with GMRES.
  77
  78 %%%%% Lilia
  79 % doit-on définir le principe et les préliminaires du multisplitting dans l'intro ou dans l'autre section?
  80 % valides-tu le titre de la 2eme section? celle que je voudrai rédiger.
  81
  82
  83 %%%%%%%%%%%%%%%%%%%%%%%%
  84 %%%%%%%%%%%%%%%%%%%%%%%%
  85
  86
  87 \section{A two-stage method with a minimization}
  88
  89
  90 %%%%%%%%%%%%%%%%%%%%%%%%
  91 %%%%%%%%%%%%%%%%%%%%%%%%
  92
  93 \bibliographystyle{plain}
  94 \bibliography{biblio}
  95
  96 \end{document}