]> AND Private Git Repository - Krylov_multi.git/blobdiff - krylov_multi.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
07-01-2014 V1
[Krylov_multi.git] / krylov_multi.tex
index 82cf45e9e563b28c4fb2afd8c82ef26f22957294..e61890d318e3fd40e2237f2ff4cc310399fefaa4 100644 (file)
@@ -48,7 +48,59 @@ thousands of cores are used.
 
 
 A completer...
-On ne peut pas parler de tout...
+On ne peut pas parler de tout...\\
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%
+%% 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
+\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
+\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
+\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 sub-systems
+\begin{equation}
+y_l^k=M^{-1}_l N_l x_l^{k-1} + M^{-1}_l b,~l\in\{1,\ldots,L\},
+\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 sub-system.   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    $y_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}
+x^k = \displaystyle\sum^L_{l=1} E_l y_l^k,
+\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.
+%%%%%%%%%%%%%%%%%%%%%%%
+%% END
+%%%%%%%%%%%%%%%%%%%%%%%
 
 \section{Related works}
 
@@ -102,7 +154,7 @@ b & = & [B_{1}, \ldots, B_{L}]
 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.
+rows of the sparse matrix $A$ and both vectors $x$ and $b$ are assigned to one 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,