X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hpcc2014.git/blobdiff_plain/fadf3e9c2be61f86ddebab4672ca769096168535..33ff15ea54b83011db5d2392c0e517c0855abce8:/hpcc.tex

diff --git a/hpcc.tex b/hpcc.tex
index b4d0be3..fc79391 100644
--- a/hpcc.tex
+++ b/hpcc.tex
@@ -320,9 +320,11 @@
 
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
-%\usepackage{amsmath}
+\usepackage{amsfonts,amssymb}
+\usepackage{amsmath}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
 %\usepackage{amsthm}
-%\usepackage{amsfonts}
 %\usepackage{graphicx}
 %\usepackage{xspace}
 \usepackage[american]{babel}
@@ -333,6 +335,14 @@
 % et l'affichage correct des URL (commande \url{http://example.com})
 %\usepackage{hyperref}
 
+\algnewcommand\algorithmicinput{\textbf{Input:}}
+\algnewcommand\Input{\item[\algorithmicinput]}
+
+\algnewcommand\algorithmicoutput{\textbf{Output:}}
+\algnewcommand\Output{\item[\algorithmicoutput]}
+
+
+
 
 \begin{document}
 %
@@ -409,9 +419,79 @@ Décrire le modèle asynchrone. Je m'en charge (DL)
 
 Décrire SimGrid (Arnaud)
 
-\section{Simulation of the multi-splitting method}
 
-Décrire le problème (algo) traité ainsi que le processus d'adaptation à SimGrid.
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Simulation of the multisplitting method}
+%Décrire le problème (algo) traité ainsi que le processus d'adaptation à SimGrid.
+Let $Ax=b$ be a large sparse system of $n$ linear equations in $\mathbb{R}$, where $A$ is a sparse square and nonsingular matrix, $x$ is the solution vector and $y$ is the right-hand side vector. We use a multisplitting method based on the block Jacobi partitioning to solve this linear system on a large scale platform composed of $L$ clusters of processors. In this case, we apply a row-by-row splitting without overlapping  
+\[
+\left(\begin{array}{ccc}
+A_{11} & \cdots & A_{1L} \\
+\vdots & \ddots & \vdots\\
+A_{L1} & \cdots & A_{LL}
+\end{array} \right)
+\times 
+\left(\begin{array}{c}
+X_1 \\
+\vdots\\
+X_L
+\end{array} \right)
+=
+\left(\begin{array}{c}
+Y_1 \\
+\vdots\\
+Y_L
+\end{array} \right)\] 
+in such a way that successive rows of matrix $A$ and both vectors $x$ and $b$ are assigned to one cluster, where for all $l,i\in\{1,\ldots,L\}$ $A_{li}$ is a rectangular block of $A$ of size $n_l\times n_i$, $X_l$ and $Y_l$ are sub-vectors of $x$ and $y$, respectively, each of size $n_l$ and $\sum_{l} n_l=\sum_{i} n_i=n$.
+
+The multisplitting method proceeds by iteration to solve in parallel the linear system by $L$ clusters of processors, in such a way each sub-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{eq:4.1}
+\end{equation}
+is solved independently by a cluster and communication are required to update the right-hand side sub-vectors $Y_l$, such that the sub-vectors $X_i$ represent the data dependencies between the clusters. As each sub-system (\ref{eq:4.1}) is solved in parallel by a cluster of processors, our multisplitting method uses an iterative method as an inner solver which is easier to parallelize and more scalable than a direct method. In this work, we use the parallel GMRES method~\cite{ref1} which is one of the most used iterative method by many researchers. 
+
+\begin{algorithm}
+\caption{A multisplitting solver with inner iteration GMRES method}
+\begin{algorithmic}[1]
+\Input $A_l$ (local sparse matrix), $B_l$ (local right-hand side), $x^0$ (initial guess)
+\Output $X_l$ (local solution vector)\vspace{0.2cm}
+\State Load $A_l$, $B_l$, $x^0$
+\State Initialize the shared vector $\hat{x}=x^0$
+\For {$k=1,2,3,\ldots$ until the global convergence}
+\State $x^0=\hat{x}$
+\State Inner iteration solver: \Call{InnerSolver}{$x^0$, $k$}
+\State Exchange the local solution ${X}_l^k$ with the neighboring clusters and copy the shared vector elements in $\hat{x}$
+\EndFor
+
+\Statex
+
+\Function {InnerSolver}{$x^0$, $k$}
+\State Compute the local right-hand side: $Y_l = B_l - \sum^L_{i=1,i\neq l}A_{li}X_i^0$
+\State Solving the local splitting $A_{ll}X_l^k=Y_l$ using the parallel GMRES method, such that $X_l^0$ is the local initial guess
+\State \Return $X_l^k$
+\EndFunction
+\end{algorithmic}
+\label{algo:01}
+\end{algorithm}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+
+
+
 
 \section{Experimental results}
 
@@ -650,7 +730,7 @@ The authors would like to thank...
 % http://www.michaelshell.org/tex/ieeetran/bibtex/
 \bibliographystyle{IEEEtran}
 % argument is your BibTeX string definitions and bibliography database(s)
-\bibliography{bib/hpccBib}
+\bibliography{hpccBib}
 %
 % <OR> manually copy in the resultant .bbl file
 % set second argument of \begin to the number of references