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

Private GIT Repository
05-01-2013
[Krylov_multi.git] / krylov_multi.tex
index ad465ee8ace6ca835cf2f0f9a07c2da69b36f2ac..82cf45e9e563b28c4fb2afd8c82ef26f22957294 100644 (file)
@@ -75,9 +75,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 +83,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 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.
+
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%