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

Private GIT Repository
Sec 04: multisplitting mehods
[rce2015.git] / paper.tex
index 923a1df25bbc9f4c39141e0a982e0997d3d3d722..3120437ca7154ffc12866986118ef10f350600f0 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -1,4 +1,3 @@
-%\documentclass[conference]{IEEEtran}
 \documentclass[times]{cpeauth}
 
 \usepackage{moreverb}
 \documentclass[times]{cpeauth}
 
 \usepackage{moreverb}
@@ -85,6 +84,8 @@
     Email: \email{{raphael.couturier,arnaud.giersch,david.laiymani,charles.ramamonjisoa}@univ-fcomte.fr}
 }
 
     Email: \email{{raphael.couturier,arnaud.giersch,david.laiymani,charles.ramamonjisoa}@univ-fcomte.fr}
 }
 
+%% Lilia Ziane Khodja: Department of Aerospace \& Mechanical Engineering\\ Non Linear Computational Mechanics\\ University of Liege\\ Liege, Belgium. Email: l.zianekhodja@ulg.ac.be
+
 \begin{abstract}
 ABSTRACT
 \end{abstract}
 \begin{abstract}
 ABSTRACT
 \end{abstract}
@@ -99,7 +100,46 @@ ABSTRACT
 
 \section{SimGrid}
 
 
 \section{SimGrid}
 
-\section{Simulation of the multisplitting method}
+%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{Two-stage splitting methods}
+\label{sec:04}
+\subsection{Multisplitting methods for sparse linear systems}
+\label{sec:04.01}
+Let us consider the following sparse linear system of $n$ equations in $\mathbb{R}$
+\begin{equation}
+Ax=b,
+\label{eq:01}
+\end{equation}
+where $A$ is a sparse square and nonsingular matrix, $b$ is the right-hand side and $x$ is the solution of the system. The multisplitting methods solve the linear system~(\ref{eq:01}) iteratively as follows
+\begin{equation}
+x^{k+1}=\displaystyle\sum^L_{\ell=1} E_\ell M^{-1}_\ell (N_\ell x^k + b),~k=1,2,3,\ldots
+\label{eq:02}
+\end{equation}
+where a collection of $L$ triplets $(M_\ell, N_\ell, E_\ell)$ defines the multisplitting of matrix $A$, such that: the different splittings are defined as $A=M_\ell-N_\ell$ where $M_\ell$ are nonsingular matrices, and $\sum_\ell{E_\ell=I}$ are diagonal nonnegative weighting matrices and $I$ is the identity matrix. The iterations of the multisplitting methods can naturally be computed in parallel such that each processor or a group of processors is responsible for solving one splitting as a linear sub-system   
+\begin{equation}
+M_\ell y_\ell^{k+1} = R_\ell^k,\mbox{~such that~} R_\ell^k = N_\ell x^k_\ell + b,
+\label{eq:03}
+\end{equation}
+then the weighting matrices $E_\ell$ are used to compute the solution of the global system~(\ref{eq:01})
+\begin{equation}
+x^{k+1}=\displaystyle\sum^L_{\ell=1} E_\ell y^{k+1}_\ell.
+\label{eq:04}
+\end{equation}
+The convergence of the multisplitting methods, based on synchronous or asynchronous iterations, is studied by many authors. It is dependent on the condition  
+\begin{equation}
+\rho(\displaystyle\sum_{\ell=1}^L E_\ell M^{-1}_\ell N_\ell) < 1,
+\label{eq:05}
+\end{equation}
+where $\rho$ is the spectral radius of the square matrix. The different linear splittings~(\ref{eq:03}) arising from the multisplitting of matrix $A$can be solved exactly with a direct method or approximated with an iterative method. When the inner method used to solve the linear sub-systems is iterative, the multisplitting method is called {\it inner-outer iterative method} or {\it two-stage multisplitting method}.
+
+In this paper we are focused on two-stage multisplitting methods where the well-known iterative method GMRES is used as an inner iteration. 
+
+\subsection{Simulation of two-stage methods using SimGrid framework}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \section{Experimental, Results and Comments}
 
 
 \section{Experimental, Results and Comments}
 
@@ -226,14 +266,14 @@ The results in figure 1 show the non-variation of the number of
 iterations of classical GMRES for a given input matrix size; it is not 
 the case for the multisplitting method. 
 
 iterations of classical GMRES for a given input matrix size; it is not 
 the case for the multisplitting method. 
 
-%%\begin{wrapfigure}{l}{60mm}
+%\begin{wrapfigure}{l}{60mm}
 \begin{figure} [ht!]
 \centering
 \begin{figure} [ht!]
 \centering
-\includegraphics[width=60mm]{"Cluster x Nodes NX=150 and NX=170".JPG}
-\caption{Cluster x Nodes NX=150 and NX=170 \label{overflow}}
+\includegraphics[width=60mm]{cluster_x_nodes_nx_150_and_nx_170.pdf}
+\caption{Cluster x Nodes NX=150 and NX=170} 
+%\label{overflow}}
 \end{figure}
 \end{figure}
-%%\end{wrapfigure}
-
+%\end{wrapfigure}
 
 Unless the 8x8 cluster, the time 
 execution difference between the two algorithms is important when 
 
 Unless the 8x8 cluster, the time 
 execution difference between the two algorithms is important when 
@@ -260,11 +300,14 @@ matrix size.
 %\RCE{idem pour tous les tableaux de donnees}
 
 
 %\RCE{idem pour tous les tableaux de donnees}
 
 
+%\begin{wrapfigure}{l}{60mm}
 \begin{figure} [ht!]
 \centering
 \begin{figure} [ht!]
 \centering
-\includegraphics[width=60mm]{"Cluster x Nodes N1 x N2".JPG}
-\caption{Cluster x Nodes N1 x N2\label{overflow}}
+\includegraphics[width=60mm]{cluster_x_nodes_n1_x_n2.pdf}
+\caption{Cluster x Nodes N1 x N2}
+%\label{overflow}}
 \end{figure}
 \end{figure}
+%\end{wrapfigure}
 
 The experiments compare the behavior of the algorithms running first on 
 speed inter- cluster network (N1) and a less performant network (N2). 
 
 The experiments compare the behavior of the algorithms running first on 
 speed inter- cluster network (N1) and a less performant network (N2). 
@@ -291,8 +334,9 @@ Table 3 : Network latency impact
 
 \begin{figure} [ht!]
 \centering
 
 \begin{figure} [ht!]
 \centering
-\includegraphics[width=60mm]{"Network latency impact on execution time".JPG}
-\caption{Network latency impact on execution time\label{overflow}}
+\includegraphics[width=60mm]{network_latency_impact_on_execution_time.pdf}
+\caption{Network latency impact on execution time}
+%\label{overflow}}
 \end{figure}
 
 
 \end{figure}
 
 
@@ -322,8 +366,9 @@ Table 4 : Network bandwidth impact
 
 \begin{figure} [ht!]
 \centering
 
 \begin{figure} [ht!]
 \centering
-\includegraphics[width=60mm]{"Network bandwith impact on execution time".JPG}
-\caption{Network bandwith impact on execution time\label{overflow}}
+\includegraphics[width=60mm]{network_bandwith_impact_on_execution_time.pdf}
+\caption{Network bandwith impact on execution time}
+%\label{overflow}
 \end{figure}
 
 
 \end{figure}
 
 
@@ -350,8 +395,9 @@ Table 5 : Input matrix size impact
 
 \begin{figure} [ht!]
 \centering
 
 \begin{figure} [ht!]
 \centering
-\includegraphics[width=60mm]{"Pb size impact on execution time".JPG}
-\caption{Pb size impact on execution time\label{overflow}}
+\includegraphics[width=60mm]{pb_size_impact_on_execution_time.pdf}
+\caption{Pb size impact on execution time}
+%\label{overflow}}
 \end{figure}
 
 In this experimentation, the input matrix size has been set from 
 \end{figure}
 
 In this experimentation, the input matrix size has been set from 
@@ -384,8 +430,9 @@ Table 6 : CPU Power impact
 
 \begin{figure} [ht!]
 \centering
 
 \begin{figure} [ht!]
 \centering
-\includegraphics[width=60mm]{"CPU Power impact on execution time".JPG}
-\caption{CPU Power impact on execution time\label{overflow}}
+\includegraphics[width=60mm]{cpu_power_impact_on_execution_time.pdf}
+\caption{CPU Power impact on execution time}
+%\label{overflow}}
 \end{figure}
 
 Using the SIMGRID simulator flexibility, we have tried to determine the 
 \end{figure}
 
 Using the SIMGRID simulator flexibility, we have tried to determine the