Avancées dans la preuve par induction

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index c0e8b160c9e49691cd802e77fbeb37f4f5bdf246..d9880d1683c4f4bddad5319fef970a3411ce330c 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -380,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\\


@@ -669,8 +669,8 @@ 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 TSIRM  algorithm  (\emph{i.e.}
 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 TSIRM  algorithm  (\emph{i.e.}

-$\epsilon_{tsirm}$).  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
+$\epsilon_{tsirm}$).  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$, where $S$ is a matrix of size $n\times s$ whose column vector $i$ is denoted by $S_i$. 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
 required for that: the maximum number of iterations and the threshold to stop 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
 required for that: the maximum number of iterations and the threshold to stop the


@@ -686,13 +686,13 @@ Let us summarize the most important parameters of TSIRM:
 \end{itemize}
 
 
 \end{itemize}
 
 

-The  parallelisation  of  TSIRM  relies   on  the  parallelization  of  all  its
+The  parallelization  of  TSIRM  relies   on  the  parallelization  of  all  its

 parts. More  precisely, except  the least-squares step,  all the other  parts are
 obvious to  achieve out in parallel. In  order to develop a  parallel version of
 our   code,   we   have   chosen  to   use   PETSc~\cite{petsc-web-page}.    For
 line~\ref{algo:matrix_mul} the  matrix-matrix multiplication is  implemented and
 efficient since the  matrix $A$ is sparse and since the  matrix $S$ contains few
 parts. More  precisely, except  the least-squares step,  all the other  parts are
 obvious to  achieve out in parallel. In  order to develop a  parallel version of
 our   code,   we   have   chosen  to   use   PETSc~\cite{petsc-web-page}.    For
 line~\ref{algo:matrix_mul} the  matrix-matrix multiplication is  implemented and
 efficient since the  matrix $A$ is sparse and since the  matrix $S$ contains few

-colums in  practice. As explained  previously, at least  two methods seem  to be
+columns in  practice. As explained  previously, at least  two methods seem  to be

 interesting to solve the least-squares minimization, CGLS and LSQR.
 
 In the following  we remind the CGLS algorithm. The LSQR  method follows more or
 interesting to solve the least-squares minimization, CGLS and LSQR.
 
 In the following  we remind the CGLS algorithm. The LSQR  method follows more or


@@ -737,6 +737,7 @@ these operations are easy to implement in PETSc or similar environment.
 \label{sec:04}
 Let us recall the following result, see~\cite{Saad86}.
 \begin{proposition}
 \label{sec:04}
 Let us recall the following result, see~\cite{Saad86}.
 \begin{proposition}

+\label{prop:saad}

 Suppose that $A$ is a positive real matrix with symmetric part $M$. Then the residual norm provided at the $m$-th step of GMRES satisfies:
 \begin{equation}
 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,
 Suppose that $A$ is a positive real matrix with symmetric part $M$. Then the residual norm provided at the $m$-th step of GMRES satisfies:
 \begin{equation}
 ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,


@@ -748,24 +749,41 @@ the convergence of GMRES($m$) for all $m$ under that assumption regarding $A$.
 
 We can now claim that,
 \begin{proposition}
 
 We can now claim that,
 \begin{proposition}

-If $A$ is a positive real matrix and GMRES($m$) is used as solver, 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. Furthermore, we still have 
+\begin{equation}
+||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,
+\end{equation}
+where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}.

 \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.
 \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$.
+We will prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, 
+$||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0||.$
+
+The base case is obvious, as for $k=1$, the TSIRM algorithm simply consists in applying GMRES($m$) once, leading to a new residual $r_1$ which follows the inductive hypothesis due to Proposition~\ref{prop:saad}.

 
 

-Each step of the TSIRM algorithm \\
+Suppose now that the claim holds for all $m=1, 2, \hdots, k-1$, that is, $\forall m \in \{1,2,\hdots, k-1\}$, $||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0||$.
+We will show that the statement holds too for $r_k$. Two situations can occur:
+\begin{itemize}
+\item If $k \mod m \neq 0$, then
+
+\item Else, let $\operatorname{span}(S) = \left \{ {\sum_{i=1}^k \lambda_i v_i \Big| k \in \mathbb{N}, v_i \in S, \lambda _i \in \mathbb{R}} \right \}$ be the linear span of a set of real vectors $S$. So,\\

 $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$
 
 $\begin{array}{ll}
 $\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}||
+& = \min_{x \in span\left(S_{k-s}, S_{k-s+1}, \hdots, S_{k-1} \right)} ||b-AS\alpha ||_2\\
+& = \min_{x \in span\left(x_{k-s}, x_{k-s}+1, \hdots, x_{k-1} \right)} ||b-AS\alpha ||_2\\
+& \leqslant \min_{x \in span\left( x_{k-1} \right)} ||b-Ax ||_2\\
+& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k-1} ||_2\\
+& \leqslant ||b-Ax_{k-1}||_2 .

 \end{array}$
 \end{array}$

+\end{itemize}

 \end{proof}
 
 \end{proof}
 

+We can remark that, at each iterate, the residue of the TSIRM algorithm is lower 
+than the one of the GMRES method.

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


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

-