X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/blobdiff_plain/124fbe31852f69cefa44e364e767c5e0e07ef670..b599aea7bd0cb52057a014508bf1bccdd41c7770:/paper.tex

diff --git a/paper.tex b/paper.tex
index fb68702..112b322 100644
--- a/paper.tex
+++ b/paper.tex
@@ -354,6 +354,7 @@
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage{multirow}
+\usepackage{graphicx}
 
 \algnewcommand\algorithmicinput{\textbf{Input:}}
 \algnewcommand\Input{\item[\algorithmicinput]}
@@ -583,8 +584,7 @@ performances.
 The present paper is organized  as follows. In Section~\ref{sec:02} some related
 works are presented. Section~\ref{sec:03} presents our two-stage algorithm using
 a  least-square  residual  minimization.   Section~\ref{sec:04}  describes  some
-convergence  results  on this  method.   In Section~\ref{sec:05},  parallization
-details  of  TSARM  are  given.  Section~\ref{sec:06}  shows  some  experimental
+convergence  results  on this  method.   Section~\ref{sec:05}  shows  some  experimental
 results  obtained on large  clusters of  our algorithm  using routines  of PETSc
 toolkit.  Finally Section~\ref{sec:06} concludes and gives some perspectives.
 %%%*********************************************************
@@ -615,7 +615,7 @@ points of our solver are given in Algorithm~\ref{algo:01}.
 
 In order to accelerate the convergence, the outer iteration periodically applies
 a least-square minimization  on the residuals computed by  the inner solver. The
-inner solver is a Krylov based solver which does not required to be changed.
+inner solver is based on a Krylov method which does not require to be changed.
 
 At each outer iteration, the sparse linear system $Ax=b$ is solved, only for $m$
 iterations, using an iterative method restarting with the previous solution. For
@@ -644,11 +644,11 @@ appropriate than a direct method in a parallel context.
   \Input $A$ (sparse matrix), $b$ (right-hand side)
   \Output $x$ (solution vector)\vspace{0.2cm}
   \State Set the initial guess $x^0$
-  \For {$k=1,2,3,\ldots$ until convergence (error$<\epsilon_{kryl}$)} \label{algo:conv}
+  \For {$k=1,2,3,\ldots$ until convergence (error$<\epsilon_{tsarm}$)} \label{algo:conv}
     \State  $x^k=Solve(A,b,x^{k-1},max\_iter_{kryl})$   \label{algo:solve}
     \State retrieve error
     \State $S_{k~mod~s}=x^k$ \label{algo:store}
-    \If {$k$ mod $s=0$ {\bf and} error$>\epsilon_{kryl}$}
+    \If {$k$ mod $s=0$ {\bf and} error$>\epsilon_{tsarm}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}
       \State Solve least-squares problem $\underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2$ \label{algo:}
       \State $x^k=S\alpha$  \Comment{compute new solution}
@@ -664,7 +664,7 @@ called for a  maximum of $max\_iter_{kryl}$ iterations.  In practice, we  sugges
 equals to  the restart  number of the  GMRES-like method. Moreover,  a tolerance
 threshold must be specified for the  solver. In practice, this threshold must be
 much  smaller  than the  convergence  threshold  of  the TSARM  algorithm  (i.e.
-$\epsilon$).  Line~\ref{algo:store}, $S_{k~ mod~ s}=x^k$ consists in copying the
+$\epsilon_{tsarm}$).  Line~\ref{algo:store}, $S_{k~ mod~ s}=x^k$ consists in copying the
 solution  $x_k$  into the  column  $k~  mod~Â s$ of  the  matrix  $S$. After  the
 minimization, the matrix $S$ is reused with the new values of the residuals.  To
 solve the minimization problem, an  iterative method is used. Two parameters are
@@ -673,25 +673,13 @@ method.
 
 To summarize, the important parameters of TSARM are:
 \begin{itemize}
-\item $\epsilon_{kryl}$ the threshold to stop the method of the krylov method
+\item $\epsilon_{tsarm}$ the threshold to stop the TSARM method
 \item $max\_iter_{kryl}$ the maximum number of iterations for the krylov method
 \item $s$ the number of outer iterations before applying the minimization step
 \item $max\_iter_{ls}$ the maximum number of iterations for the iterative least-square method
 \item $\epsilon_{ls}$ the threshold to stop the least-square method
 \end{itemize}
 
-%%%*********************************************************
-%%%*********************************************************
-
-\section{Convergence results}
-\label{sec:04}
-
-
-
-%%%*********************************************************
-%%%*********************************************************
-\section{Parallelization}
-\label{sec:05}
 
 The  parallelisation  of  TSARM  relies   on  the  parallelization  of  all  its
 parts. More  precisely, except  the least-square step,  all the other  parts are
@@ -733,10 +721,21 @@ In each iteration  of CGLS, there is two  matrix-vector multiplications and some
 classical operations:  dots, norm, multiplication  and addition on  vectors. All
 these operations are easy to implement in PETSc or similar environment.
 
+
+
+%%%*********************************************************
+%%%*********************************************************
+
+\section{Convergence results}
+\label{sec:04}
+
+
+
+
 %%%*********************************************************
 %%%*********************************************************
 \section{Experiments using petsc}
-\label{sec:06}
+\label{sec:05}
 
 
 In order to see the influence of our algorithm with only one processor, we first
@@ -766,12 +765,10 @@ torso3             & 2D/3D problem & 259,156 & 4,429,042 \\
 
 The following  parameters have been chosen  for our experiments.   As by default
 the restart  of GMRES is performed every  30 iterations, we have  chosen to stop
-the     GMRES    every     30    iterations     (line     \ref{algo:solve}    in
-Algorithm~\ref{algo:01}).   $s$ is  set to  8. CGLS  is chosen  to  minimize the
-least-squares  problem.  Two  conditions  are  used to  stop  CGLS,  either  the
-precision is under $1e-40$ or the  number of iterations is greater to $20$.  The
-external   precision    is   set    to   $1e-10$   (line    \ref{algo:conv}   in
-Algorithm~\ref{algo:01}).  Those  experiments have been performed  on a Intel(R)
+the GMRES every 30 iterations, $max\_iter_{kryl}=30$).  $s$ is set to 8. CGLS is
+chosen  to minimize  the least-squares  problem with  the  following parameters:
+$\epsilon_{ls}=1e-40$ and $max\_iter_{ls}=20$.  The external precision is set to
+$\epsilon_{tsarm}=1e-10$.  Those  experiments have been performed  on a Intel(R)
 Core(TM) i7-3630QM CPU @ 2.40GHz with the version 3.5.1 of PETSc.
 
 
@@ -779,13 +776,12 @@ In  Table~\ref{tab:02}, some  experiments comparing  the solving  of  the linear
 systems obtained with the previous matrices  with a GMRES variant and with out 2
 stage algorithm are  given. In the second column, it can  be noticed that either
 gmres or fgmres is used to  solve the linear system.  According to the matrices,
-different preconditioner is  used.  With the 2 stage  algorithm, the same solver
-and  the same  preconditionner  is used.   This  Table shows  that  the 2  stage
-algorithm  can  drastically  reduce  the  number  of  iterations  to  reach  the
-convergence when the  number of iterations for the normal GMRES  is more or less
-greater than  500. In fact  this also depends  on tow parameters: the  number of
-iterations  to  stop  GMRES  and   the  number  of  iterations  to  perform  the
-minimization.
+different  preconditioner is used.   With TSARM,  the same  solver and  the same
+preconditionner is used.  This Table shows that TSARM can drastically reduce the
+number of iterations to reach the  convergence when the number of iterations for
+the normal GMRES is more or less  greater than 500. In fact this also depends on
+tow  parameters: the  number  of iterations  to  stop GMRES  and  the number  of
+iterations to perform the minimization.
 
 
 \begin{table}
@@ -814,27 +810,36 @@ torso3             & fgmres / sor  & 37.70 & 565 & 34.97 & 510 \\
 
 
 
-Larger experiments ....\\
 
-In the following we describe the applications of PETSc we have experimented. Those applications are available in the ksp part which is suited for  scalable linear equations solvers:
+In order to perform larger  experiments, we have tested some example application
+of PETSc. Those  applications are available in the ksp part  which is suited for
+scalable linear equations solvers:
 \begin{itemize}
-\item  ex15   is  an  example  which   solves  in  parallel   a  2D  homogeneous
-  Laplacian. Thediagonal is  equals to 4 and 4  extra-diagonals representing the
-  neighbors in  each directions  is equal to  -1. This  example is used  in many
-  physical phenomena , for exemple, heat and fluid flow, wave propagation...
-\item
+\item ex15  is an example  which solves in  parallel an operator using  a finite
+  difference  scheme.   The  diagonal  is  equals to  4  and  4  extra-diagonals
+  representing the neighbors in each directions  is equal to -1. This example is
+  used  in many  physical phenomena, for  example, heat  and fluid  flow, wave
+  propagation...
+\item ex54 is another example based on 2D problem discretized with quadrilateral
+  finite elements. For this example, the user can define the scaling of material
+  coefficient in embedded circle, it is called $\alpha$.
 \end{itemize}
+For more technical details on  these applications, interested reader are invited
+to  read the  codes available  in the  PETSc sources.   Those problem  have been
+chosen because they  are scalable with many cores. We  have tested other problem
+but they are not scalable with many cores.
 
+In the following larger experiments are described on two large scale architectures: Curie and Juqeen... {\bf description...}\\
 
 
-
+{\bf Description of preconditioners}
 
 \begin{table*}
 \begin{center}
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 
 \hline
 
-  nb. cores & precond   & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSARM CGLS} &  \multicolumn{2}{c|}{TSARM LSQR} & best gain \\ 
+  nb. cores & precond   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSARM CGLS} &  \multicolumn{2}{c|}{TSARM LSQR} & best gain \\ 
 \cline{3-8}
              &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline
   2,048      & mg                    & 403.49   & 18,210    & 73.89  & 3,060   & 77.84  & 3,270  & 5.46 \\
@@ -848,11 +853,34 @@ In the following we describe the applications of PETSc we have experimented. Tho
 \hline
 
 \end{tabular}
-\caption{Comparison of FGMRES and 2 stage FGMRES algorithms for ex15 of Petsc with 25000 components per core on Juqueen (threshold 1e-3, restart=30, s=12),  time is expressed in seconds.}
+\caption{Comparison of FGMRES and TSARM with FGMRES for example ex15 of PETSc with two preconditioner (mg and sor) with 25,000 components per core on Juqueen (threshold 1e-3, restart=30, s=12),  time is expressed in seconds.}
 \label{tab:03}
 \end{center}
 \end{table*}
 
+Table~\ref{tab:03} shows  the execution  times and the  number of  iterations of
+example ex15  of PETSc on the  Juqueen architecture. Differents  number of cores
+are  studied rangin  from  2,048  upto 16,383.   Two  preconditioners have  been
+tested.   For those experiments,  the number  of components  (or unknown  of the
+problems)  per processor is  fixed to  25,000. This  number can  seem relatively
+small. In fact, for  some applications that need a lot of  memory, the number of
+components per processor requires sometimes to be small.
+
+In this Table, we  can notice that TSARM is always faster  than FGMRES. The last
+column shows the ratio between FGMRES and the best version of TSARM according to
+the minimization procedure: CGLS or LSQR.
+
+
+\begin{figure}
+\centering
+  \includegraphics[width=0.45\textwidth]{nb_iter_sec_ex15_juqueen}
+\caption{Number of iterations per second with ex15 and the same parameters than in Table~\ref{tab:03}}
+\label{fig:01}
+\end{figure}
+
+
+
+
 
 \begin{table*}
 \begin{center}
@@ -911,7 +939,7 @@ In the following we describe the applications of PETSc we have experimented. Tho
 %%%*********************************************************
 %%%*********************************************************
 \section{Conclusion}
-\label{sec:07}
+\label{sec:06}
 %The conclusion goes here. this is more of the conclusion
 %%%*********************************************************
 %%%*********************************************************
