Je sais pas trop

[GMRES2stage.git] / paper.tex

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

+\newtheorem{proof}{Proof}

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


@@ -380,7 +381,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\\


@@ -425,16 +426,17 @@ Email: lilia.ziane@inria.fr}
 
 
 \begin{abstract}
 
 
 \begin{abstract}

-In  this article,  a  two-stage  iterative algorithm is proposed to improve  the
-convergence of Krylov based iterative methods,  typically those of GMRES variants. The
-principle of  the proposed approach  is to  build an external  iteration over  the Krylov
-method, and to  frequently store its current  residual   (at  each
-GMRES restart for instance). After a given number of outer iterations, a minimization
-step  is applied  on the  matrix composed by the  saved residuals,  in  order to
-compute a better solution and to make  new iterations if required.  It is proven that
-the proposal has  the same convergence properties than the  inner embedded method itself. 
-Experiments using up  to 16,394 cores also show that the proposed algorithm
-runs around 5 or 7 times faster than GMRES.
+In  this article, a  two-stage iterative  algorithm is  proposed to  improve the
+convergence  of  Krylov  based  iterative  methods,  typically  those  of  GMRES
+variants.  The  principle of  the  proposed approach  is  to  build an  external
+iteration over the  Krylov method, and to frequently  store its current residual
+(at each GMRES restart for instance).  After a given number of outer iterations,
+a least-squares minimization step is applied on the matrix composed by the saved
+residuals, in order  to compute a better solution and to  make new iterations if
+required.  It  is proven that the  proposal has the  same convergence properties
+than the  inner embedded  method itself.  Experiments  using up to  16,394 cores
+also  show that the  proposed algorithm  runs around  5 or  7 times  faster than
+GMRES.

 \end{abstract}
 
 \begin{IEEEkeywords}
 \end{abstract}
 
 \begin{IEEEkeywords}


@@ -647,15 +649,15 @@ appropriate than a single direct method in a parallel context.
 \begin{algorithmic}[1]
   \Input $A$ (sparse matrix), $b$ (right-hand side)
   \Output $x$ (solution vector)\vspace{0.2cm}
 \begin{algorithmic}[1]
   \Input $A$ (sparse matrix), $b$ (right-hand side)
   \Output $x$ (solution vector)\vspace{0.2cm}

-  \State Set the initial guess $x^0$
+  \State Set the initial guess $x_0$

   \For {$k=1,2,3,\ldots$ until convergence (error$<\epsilon_{tsirm}$)} \label{algo:conv}
   \For {$k=1,2,3,\ldots$ until convergence (error$<\epsilon_{tsirm}$)} \label{algo:conv}

-    \State  $x^k=Solve(A,b,x^{k-1},max\_iter_{kryl})$   \label{algo:solve}
+    \State  $x_k=Solve(A,b,x_{k-1},max\_iter_{kryl})$   \label{algo:solve}

     \State retrieve error
     \State retrieve error

-    \State $S_{k \mod s}=x^k$ \label{algo:store}
+    \State $S_{k \mod s}=x_k$ \label{algo:store}

     \If {$k \mod s=0$ {\bf and} error$>\epsilon_{kryl}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}
     \If {$k \mod s=0$ {\bf and} error$>\epsilon_{kryl}$}
       \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}

-            \State $\alpha=Solve\_Least\_Squares(R,b,max\_iter_{ls})$ \label{algo:}
-      \State $x^k=S\alpha$  \Comment{compute new solution}
+            \State $\alpha=Least\_Squares(R,b,max\_iter_{ls})$ \label{algo:}
+      \State $x_k=S\alpha$  \Comment{compute new solution}

     \EndIf
   \EndFor
 \end{algorithmic}
     \EndIf
   \EndFor
 \end{algorithmic}


@@ -702,19 +704,21 @@ less the same principle but it takes more place, so we briefly explain the paral
 \begin{algorithmic}[1]
   \Input $A$ (matrix), $b$ (right-hand side)
   \Output $x$ (solution vector)\vspace{0.2cm}
 \begin{algorithmic}[1]
   \Input $A$ (matrix), $b$ (right-hand side)
   \Output $x$ (solution vector)\vspace{0.2cm}

-  \State $r=b-Ax$
-  \State $p=A'r$
-  \State $s=p$
-  \State $g=||s||^2_2$
-  \For {$k=1,2,3,\ldots$ until convergence (g$<\epsilon_{ls}$)} \label{algo2:conv}
-    \State $q=Ap$
-    \State $\alpha=g/||q||^2_2$
-    \State $x=x+alpha*p$
-    \State $r=r-alpha*q$
-    \State $s=A'*r$
-    \State $g_{old}=g$
-    \State $g=||s||^2_2$
-    \State $\beta=g/g_{old}$
+  \State Let $x_0$ be an initial approximation
+  \State $r_0=b-Ax_0$
+  \State $p_1=A^Tr_0$
+  \State $s_0=p_1$
+  \State $\gamma=||s_0||^2_2$
+  \For {$k=1,2,3,\ldots$ until convergence ($\gamma<\epsilon_{ls}$)} \label{algo2:conv}
+    \State $q_k=Ap_k$
+    \State $\alpha_k=\gamma/||q_k||^2_2$
+    \State $x_k=x_{k-1}+\alpha_kp_k$
+    \State $r_k=r_{k-1}-\alpha_kq_k$
+    \State $s_k=A^Tr_k$
+    \State $\gamma_{old}=\gamma$
+    \State $\gamma=||s_k||^2_2$
+    \State $\beta_k=\gamma/\gamma_{old}$
+    \State $p_{k+1}=s_k+\beta_kp_k$

   \EndFor
 \end{algorithmic}
 \label{algo:02}
   \EndFor
 \end{algorithmic}
 \label{algo:02}


@@ -738,11 +742,17 @@ 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}
+If $A$ is a positive real matrix, then the TSIRM algorithm is convergent.
+\end{proposition}

 
 

+\begin{proof}
+\end{proof}

 
 %%%*********************************************************
 %%%*********************************************************
 
 %%%*********************************************************
 %%%*********************************************************


@@ -829,17 +839,16 @@ scalable linear equations solvers:
 \begin{itemize}
 \item ex15  is an example  which solves in  parallel an operator using  a finite
   difference  scheme.   The  diagonal  is  equal to  4  and  4  extra-diagonals
 \begin{itemize}
 \item ex15  is an example  which solves in  parallel an operator using  a finite
   difference  scheme.   The  diagonal  is  equal to  4  and  4  extra-diagonals

-  representing the neighbors in each directions  is equal to -1. This example is
+  representing the neighbors in each directions  are equal to -1. This example is

   used  in many  physical phenomena, for  example, heat  and fluid  flow, wave
   used  in many  physical phenomena, for  example, heat  and fluid  flow, wave

-  propagation...
+  propagation, etc.

 \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
 \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$.
+  coefficient in embedded circle called $\alpha$.

 \end{itemize}
 \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.
+For more technical details on  these applications, interested readers are invited
+to  read the  codes available  in the  PETSc sources.   Those problems  have been
+chosen because they  are scalable with many cores which is not the case of other problems that we have tested.

 
 In the following larger experiments are described on two large scale architectures: Curie and Juqeen... {\bf description...}\\
 
 
 In the following larger experiments are described on two large scale architectures: Curie and Juqeen... {\bf description...}\\
 


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

-