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

Private GIT Repository
08-01-2013
[Krylov_multi.git] / krylov_multi.tex
index ad465ee8ace6ca835cf2f0f9a07c2da69b36f2ac..3295c82e9c5b16cdeb4287c5192d00e088bfb3e8 100644 (file)
@@ -48,7 +48,52 @@ thousands of cores are used.
 
 
 A completer...
 
 
 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
+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 system.
+A multisplitting method using an iterative method for solving the $L$ linear systems is called an inner-outer
+iterative method or a two-stage method. The solution of the global linear system at the iteration $k$ is computed
+as follows
+\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}
 
 
 \section{Related works}
 
@@ -75,9 +120,7 @@ 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.
 
 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.
+
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%
@@ -85,6 +128,46 @@ method with the LU method or scalar iterative one with GMRES.
 
 
 \section{A two-stage method with a minimization}
 
 
 \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 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, 
+\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.
+
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%