TRuc

[GMRES2stage.git] / paper.tex

diff --git a/paper.tex b/paper.tex
index 6a83f5221e0d087a74df1fc7b2502da6cbc1f965..4d0e239a02f1d21caede6978887dbfb368d7a932 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -621,19 +621,27 @@ outer solver periodically applies a least-squares minimization  on the residuals
 At each outer iteration, the sparse linear system $Ax=b$ is partially 
 solved using only $m$
 iterations of an iterative method, this latter being initialized with the 
 At each outer iteration, the sparse linear system $Ax=b$ is partially 
 solved using only $m$
 iterations of an iterative method, this latter being initialized with the 

-best known approximation previously obtained. 
-GMRES method~\cite{Saad86}, or any of its variants, can be used for instance as an
-inner solver. The current approximation of the Krylov method is then stored inside a matrix
-$S$ composed by the successive solutions that are computed during inner iterations.
+last obtained approximation. 
+GMRES method~\cite{Saad86}, or any of its variants, can potentially be used as
+inner solver. The current approximation of the Krylov method is then stored inside a $n \times s$ matrix
+$S$, which is composed by the $s$ last solutions that have been computed during 
+the inner iterations phase.
+In the remainder, the $i$-th column vector of $S$ will be denoted by $S_i$. 

 
 

-At each $s$ iterations, the minimization step is applied in order to
+$\|r_n\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{n/2} \|r_0\|,$
+In the general case, where A is not positive definite, we have
+
+$\|r_n\| \le \inf_{p \in P_n} \|p(A)\| \le \kappa_2(V) \inf_{p \in P_n} \max_{\lambda \in \sigma(A)} |p(\lambda)| \|r_0\|, \,$
+
+
+At each $s$ iterations, another kind of minimization step is applied in order to

 compute a new  solution $x$. For that, the previous  residuals of $Ax=b$ are computed by
 the inner iterations with $(b-AS)$. The minimization of the residuals is obtained by  
 \begin{equation}
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}
 \end{equation}
 compute a new  solution $x$. For that, the previous  residuals of $Ax=b$ are computed by
 the inner iterations with $(b-AS)$. The minimization of the residuals is obtained by  
 \begin{equation}
    \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
 \label{eq:01}
 \end{equation}

-with $R=AS$. Then the new solution $x$ is computed with $x=S\alpha$.
+with $R=AS$. The new solution $x$ is then computed with $x=S\alpha$.

 
 
 In  practice, $R$  is a  dense rectangular  matrix belonging in  $\mathbb{R}^{n\times s}$,
 
 
 In  practice, $R$  is a  dense rectangular  matrix belonging in  $\mathbb{R}^{n\times s}$,


@@ -663,14 +671,15 @@ appropriate than a single direct method in a parallel context.
 \label{algo:01}
 \end{algorithm}
 
 \label{algo:01}
 \end{algorithm}
 

-Algorithm~\ref{algo:01}  summarizes  the principle  of  our  method.  The  outer
-iteration is  inside the for  loop. Line~\ref{algo:solve}, the Krylov  method is
+Algorithm~\ref{algo:01}  summarizes  the principle  of  the proposed  method.  The  outer
+iteration is  inside the \emph{for}  loop. Line~\ref{algo:solve}, the Krylov  method is

 called for a  maximum of $max\_iter_{kryl}$ iterations.  In practice, we  suggest to set this parameter
 called for a  maximum of $max\_iter_{kryl}$ iterations.  In practice, we  suggest to set this parameter

-equals to  the restart  number of the  GMRES-like method. Moreover,  a tolerance
+equal to  the restart  number in the  GMRES-like method. Moreover,  a tolerance

 threshold must be specified for the  solver. In practice, this threshold must be
 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.}
+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
 $\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
+solution  $x_k$  into the  column  $k \mod s$ of $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
 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


@@ -735,7 +744,7 @@ these operations are easy to implement in PETSc or similar environment.
 
 \section{Convergence results}
 \label{sec:04}
 
 \section{Convergence results}
 \label{sec:04}

-Let us recall the following result, see~\cite{Saad86}.
+Let us recall the following result, see~\cite{Saad86} for further readings.

 \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{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: