X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/Krylov_multi.git/blobdiff_plain/c0329df983b381995f844afef4536e2853e59e78..23d19900771651bd580496ebc8ca0fc156aedc88:/krylov_multi.tex?ds=inline diff --git a/krylov_multi.tex b/krylov_multi.tex index b96a5b9..82cf45e 100644 --- a/krylov_multi.tex +++ b/krylov_multi.tex @@ -21,12 +21,12 @@ \begin{abstract} In this paper we revist the krylov multisplitting algorithm presented in \cite{huang1993krylov} which uses a scalar method to minimize the krylov -iterations computed by a multisplitting algorithm. Our new algorithm is simply a -parallel multisplitting algorithm with few blocks of large size and a parallel -krylov minimization is used to improve the convergence. Some large scale -experiments with a 3D Poisson problem are presented. They show the obtained -improvements compared to a classical GMRES both in terms of number of iterations -and execution times. +iterations computed by a multisplitting algorithm. Our new algorithm is based on +a parallel multisplitting algorithm with few blocks of large size using a +parallel GMRES method inside each block and on a parallel krylov minimization in +order to improve the convergence. Some large scale experiments with a 3D Poisson +problem are presented. They show the obtained improvements compared to a +classical GMRES both in terms of number of iterations and execution times. \end{abstract} @@ -38,14 +38,44 @@ 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 have been proposed and adpated by many researchers. When +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 -communications to perform matrix-vector products and reduction operations. +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 +thousands of cores are used. + + +A completer... +On ne peut pas parler de tout... + +\section{Related works} + + +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} + +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 +increase the convergence, then the other tasks receive the update solution until +convergence of the global system. + + + +In \cite{couturier2008gremlins}, the authors proposed practical implementations +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. + -%%%%% Lilia -% doit-on définir le principe et les préliminaires du multisplitting dans l'intro ou dans l'autre section? -% valides-tu le titre de la 2eme section? celle que je voudrai rédiger. %%%%%%%%%%%%%%%%%%%%%%%% @@ -53,6 +83,46 @@ communications to perform matrix-vector products and reduction operations. \section{A two-stage method with a minimization} +Let $Ax=b$ be a given sparse and large linear system of $n$ equations +to solve in parallel on $L$ clusters, physically adjacent or geographically +distant, where $A\in\mathbb{R}^{n\times n}$ is a square and nonsingular +matrix, $x\in\mathbb{R}^{n}$ is the solution vector and $b\in\mathbb{R}^{n}$ +is the right-hand side vector. The multisplitting of this linear system +is defined as follows: +\begin{equation} +\left\{ +\begin{array}{lll} +A & = & [A_{1}, \ldots, A_{L}]\\ +x & = & [X_{1}, \ldots, X_{L}]\\ +b & = & [B_{1}, \ldots, B_{L}] +\end{array} +\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$ +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 a cluster. +So, the multisplitting format of the linear system is defined as follows: +\begin{equation} +\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, +\label{sec03:eq02} +\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: +\begin{equation} +\left\{ +\begin{array}{l} +A_{ll}X_l = Y_l \mbox{,~such that}\\ +Y_l = B_l - \displaystyle\sum_{i=1,i\neq l}^{L}A_{li}X_i, +\end{array} +\right. +\label{sec03:eq03} +\end{equation} +where the sub-vectors $X_i$ define the data dependencies between the cluster $l$ and other clusters. + %%%%%%%%%%%%%%%%%%%%%%%%