Avancées dans la preuve

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index e512018b8fd2b0bf94de9dbf5cdd4b83a8264a8f..ceffa3d7903def8c6c51d0395e382a9487e67e2a 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,18 +741,32 @@ 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}

+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$.
+
+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}


@@ -853,7 +866,7 @@ chosen because they  are scalable with many cores which is not the case of other
 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...}\\
 
 

-{\bf Description of preconditioners}
+{\bf Description of preconditioners}\\

 
 \begin{table*}[htbp]
 \begin{center}
 
 \begin{table*}[htbp]
 \begin{center}


@@ -874,15 +887,15 @@ In the following larger experiments are described on two large scale architectur
 \hline
 
 \end{tabular}
 \hline
 
 \end{tabular}

-\caption{Comparison of FGMRES and TSIRM 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.}
+\caption{Comparison of FGMRES and TSIRM with FGMRES for example ex15 of PETSc with two preconditioners (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
 \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
+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
 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
 problems)  per processor  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


@@ -890,11 +903,11 @@ small.
 
 
 
 
 
 

-In this Table, we  can notice that TSIRM is always faster  than FGMRES. The last
+In Table~\ref{tab:03}, we  can notice that TSIRM is always faster  than FGMRES. The last

 column shows the ratio between FGMRES and the best version of TSIRM according to
 the minimization  procedure: CGLS or  LSQR. Even if  we have computed  the worst
 column shows the ratio between FGMRES and the best version of TSIRM according to
 the minimization  procedure: CGLS or  LSQR. Even if  we have computed  the worst

-case  between CGLS  and LSQR,  it is  clear that  TSIRM is  alsways  faster than
-FGMRES. For this example, the  multigrid preconditionner is faster than SOR. The
+case  between CGLS  and LSQR,  it is  clear that  TSIRM is  always  faster than
+FGMRES. For this example, the  multigrid preconditioner is faster than SOR. The

 gain  between   TSIRM  and  FGMRES  is   more  or  less  similar   for  the  two
 preconditioners.  Looking at the number  of iterations to reach the convergence,
 it is  obvious that TSIRM allows the  reduction of the number  of iterations. It
 gain  between   TSIRM  and  FGMRES  is   more  or  less  similar   for  the  two
 preconditioners.  Looking at the number  of iterations to reach the convergence,
 it is  obvious that TSIRM allows the  reduction of the number  of iterations. It


@@ -912,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.