10-10-2014 14

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 1d4cac09f311bc2942f5bc0278957528aa0c19a3..c0e8b160c9e49691cd802e77fbeb37f4f5bdf246 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -364,7 +364,6 @@
 \algnewcommand\Output{\item[\algorithmicoutput]}
 
 \newtheorem{proposition}{Proposition}
 \algnewcommand\Output{\item[\algorithmicoutput]}
 
 \newtheorem{proposition}{Proposition}

-\newtheorem{proof}{Proof}

 
 \begin{document}
 %
 
 \begin{document}
 %


@@ -381,7 +380,7 @@
 % use a multiple column layout for up to two different
 % affiliations
 
 % use a multiple column layout for up to two different
 % affiliations
 

-\author{\IEEEauthorblockN{Rapha\"el Couturier\IEEEauthorrefmark{1}, Lilia Ziane Khodja\IEEEauthorrefmark{2}, and Christophe Guyeux\IEEEauthorrefmark{1}}
+\author{\IEEEauthorblockN{Rapha\"el Couturier\IEEEauthorrefmark{1}, Lilia Ziane Khodja \IEEEauthorrefmark{2}, and Christophe Guyeux\IEEEauthorrefmark{1}}

 \IEEEauthorblockA{\IEEEauthorrefmark{1} Femto-ST Institute, University of Franche Comte, France\\
 Email: \{raphael.couturier,christophe.guyeux\}@univ-fcomte.fr}
 \IEEEauthorblockA{\IEEEauthorrefmark{2} INRIA Bordeaux Sud-Ouest, France\\
 \IEEEauthorblockA{\IEEEauthorrefmark{1} Femto-ST Institute, University of Franche Comte, France\\
 Email: \{raphael.couturier,christophe.guyeux\}@univ-fcomte.fr}
 \IEEEauthorblockA{\IEEEauthorrefmark{2} INRIA Bordeaux Sud-Ouest, France\\


@@ -742,13 +741,14 @@ Suppose that $A$ is a positive real matrix with symmetric part $M$. Then the res
 \begin{equation}
 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,
 \end{equation}
 \begin{equation}
 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,
 \end{equation}

-where $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$, which proves 
+where $\alpha = \lambda_min(M)^2$ and $\beta = \lambda_max(A^T A)$, which proves 

 the convergence of GMRES($m$) for all $m$ under that assumption regarding $A$.
 \end{proposition}
 
 the convergence of GMRES($m$) for all $m$ under that assumption regarding $A$.
 \end{proposition}
 

+

 We can now claim that,
 \begin{proposition}
 We can now claim that,
 \begin{proposition}

-If $A$ is a positive real matrix, then the TSIRM algorithm is convergent.
+If $A$ is a positive real matrix and GMRES($m$) is used as solver, then the TSIRM algorithm is convergent.

 \end{proposition}
 
 \begin{proof}
 \end{proposition}
 
 \begin{proof}


@@ -756,9 +756,17 @@ Let $r_k = b-Ax_k$, where $x_k$ is the approximation of the solution after the
 $k$-th iterate of TSIRM.
 We will prove that $r_k \rightarrow 0$ when $k \rightarrow +\infty$.
 
 $k$-th iterate of TSIRM.
 We will prove that $r_k \rightarrow 0$ when $k \rightarrow +\infty$.
 

+Each step of the TSIRM algorithm \\
+$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$

 
 

+$\begin{array}{ll}
+& = \min_{x \in Vect\left(x_0, x_1, \hdots, x_{k-1} \right)} ||b-AS\alpha ||_2\\
+& \leqslant \min_{x \in Vect\left( S_{k-1} \right)} ||b-Ax ||_2\\
+& \leqslant ||b-Ax_{k-1}||
+\end{array}$

 \end{proof}
 
 \end{proof}
 

+

 %%%*********************************************************
 %%%*********************************************************
 \section{Experiments using PETSc}
 %%%*********************************************************
 %%%*********************************************************
 \section{Experiments using PETSc}


@@ -829,7 +837,7 @@ torso3             & fgmres / sor  & 37.70 & 565 & 34.97 & 510 \\
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of (F)GMRES and 2 stage (F)GMRES algorithms in sequential with some matrices, time is expressed in seconds.}
+\caption{Comparison of (F)GMRES and TSIRM with (F)GMRES in sequential with some matrices, time is expressed in seconds.}

 \label{tab:02}
 \end{center}
 \end{table}
 \label{tab:02}
 \end{center}
 \end{table}


@@ -888,7 +896,7 @@ Table~\ref{tab:03} shows  the execution  times and the  number of  iterations of
 example ex15  of PETSc on the  Juqueen architecture. Different  numbers of cores
 are  studied ranging  from  2,048  up-to 16,383.   Two  preconditioners have  been
 tested: {\it mg} and {\it sor}.   For those experiments,  the number  of components  (or unknowns  of the
 example ex15  of PETSc on the  Juqueen architecture. Different  numbers of cores
 are  studied ranging  from  2,048  up-to 16,383.   Two  preconditioners have  been
 tested: {\it mg} and {\it sor}.   For those experiments,  the number  of components  (or unknowns  of the

-problems)  per processor  is fixed  to 25,000,  also called  weak  scaling. This
+problems)  per core  is fixed  to 25,000,  also called  weak  scaling. 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.
 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.


@@ -917,10 +925,10 @@ corresponds to 30*12, there are $max\_iter_{ls}$ which corresponds to 15.
 
 
 In  Figure~\ref{fig:01}, the number  of iterations  per second  corresponding to
 
 
 In  Figure~\ref{fig:01}, the number  of iterations  per second  corresponding to

-Table~\ref{tab:01}  is  displayed.   It  can  be  noticed  that  the  number  of
-iterations per second of FMGRES is  constant whereas it decrease with TSIRM with
-both preconditioner. This  can be explained by the fact that  when the number of
-core increases the time for the minimization step also increases but, generally,
+Table~\ref{tab:03}  is  displayed.   It  can  be  noticed  that  the  number  of
+iterations per second of FMGRES is  constant whereas it decreases with TSIRM with
+both preconditioners. This  can be explained by the fact that  when the number of
+cores increases the time for the least-squares minimization step also increases but, generally,

 when  the number  of cores  increases,  the number  of iterations  to reach  the
 threshold also increases,  and, in that case, TSIRM is  more efficient to reduce
 the number of iterations. So, the overall benefit of using TSIRM is interesting.
 when  the number  of cores  increases,  the number  of iterations  to reach  the
 threshold also increases,  and, in that case, TSIRM is  more efficient to reduce
 the number of iterations. So, the overall benefit of using TSIRM is interesting.


@@ -935,7 +943,7 @@ the number of iterations. So, the overall benefit of using TSIRM is interesting.
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 
 \hline
 
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} 
 \hline
 

-  nb. cores & threshold   & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain \\ 
+  nb. cores & threshold   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain \\ 

 \cline{3-8}
              &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline
   2,048      & 8e-5                  & 108.88 & 16,560  & 23.06  &  3,630  & 22.79  & 3,630   & 4.77 \\
 \cline{3-8}
              &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline
   2,048      & 8e-5                  & 108.88 & 16,560  & 23.06  &  3,630  & 22.79  & 3,630   & 4.77 \\


@@ -948,7 +956,7 @@ the number of iterations. So, the overall benefit of using TSIRM is interesting.
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of FGMRES  and 2 stage FGMRES algorithms for ex54 of Petsc (both with the MG preconditioner) with 25000 components per core on Curie (restart=30, s=12),  time is expressed in seconds.}
+\caption{Comparison of FGMRES  and TSIRM with FGMRES algorithms for ex54 of Petsc (both with the MG preconditioner) with 25,000 components per core on Curie (restart=30, s=12),  time is expressed in seconds.}

 \label{tab:04}
 \end{center}
 \end{table*}
 \label{tab:04}
 \end{center}
 \end{table*}


@@ -962,9 +970,9 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} 
 \hline
 
 \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} 
 \hline
 

-  nb. cores   & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain & \multicolumn{3}{c|}{efficiency} \\ 
+  nb. cores   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain & \multicolumn{3}{c|}{efficiency} \\ 

 \cline{2-7} \cline{9-11}
 \cline{2-7} \cline{9-11}

-                    & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. &   & GMRES & TS CGLS & TS LSQR\\\hline \hline
+                    & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. &   & FGMRES & TS CGLS & TS LSQR\\\hline \hline

    512              & 3,969.69 & 33,120 & 709.57 & 5,790  & 622.76 & 5,070  & 6.37  &   1    &    1    &     1     \\
    1024             & 1,530.06  & 25,860 & 290.95 & 4,830  & 307.71 & 5,070 & 5.25  &  1.30  &    1.21  &   1.01     \\
    2048             & 919.62    & 31,470 & 237.52 & 8,040  & 194.22 & 6,510 & 4.73  & 1.08   &    .75   &   .80\\
    512              & 3,969.69 & 33,120 & 709.57 & 5,790  & 622.76 & 5,070  & 6.37  &   1    &    1    &     1     \\
    1024             & 1,530.06  & 25,860 & 290.95 & 4,830  & 307.71 & 5,070 & 5.25  &  1.30  &    1.21  &   1.01     \\
    2048             & 919.62    & 31,470 & 237.52 & 8,040  & 194.22 & 6,510 & 4.73  & 1.08   &    .75   &   .80\\


@@ -974,7 +982,7 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of FGMRES  and 2 stage FGMRES algorithms for ex54 of Petsc (both with the MG preconditioner) with 204,919,225 components on Curie with different number of cores (restart=30, s=12, threshol 5e-5),  time is expressed in seconds.}
+\caption{Comparison of FGMRES  and TSIRM with FGMRES for ex54 of Petsc (both with the MG preconditioner) with 204,919,225 components on Curie with different number of cores (restart=30, s=12, threshold 5e-5),  time is expressed in seconds.}

 \label{tab:05}
 \end{center}
 \end{table*}
 \label{tab:05}
 \end{center}
 \end{table*}


@@ -1002,7 +1010,7 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect
 
 future plan : \\
 - study other kinds of matrices, problems, inner solvers\\
 
 future plan : \\
 - study other kinds of matrices, problems, inner solvers\\

-- test the influence of all the parameters\\
+- test the influence of all parameters\\

 - adaptative number of outer iterations to minimize\\
 - other methods to minimize the residuals?\\
 - implement our solver inside PETSc
 - adaptative number of outer iterations to minimize\\
 - other methods to minimize the residuals?\\
 - implement our solver inside PETSc


@@ -1017,7 +1025,7 @@ future plan : \\
 %%%*********************************************************
 \section*{Acknowledgment}
 This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract
 %%%*********************************************************
 \section*{Acknowledgment}
 This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract

-ANR-11-LABX-01-01).   We acknowledge PRACE  for awarding  us access  to resource
+ANR-11-LABX-01-01).   We acknowledge PRACE  for awarding  us access  to resources

 Curie and Juqueen respectively based in France and Germany.
 
 
 Curie and Juqueen respectively based in France and Germany.
 
 


@@ -1060,3 +1068,4 @@ Curie and Juqueen respectively based in France and Germany.
 
 % that's all folks
 \end{document}
 
 % that's all folks
 \end{document}

+