X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/blobdiff_plain/7de6cc5b2d794c02ef46116780ac061eff79ab7a..0f544a712fbfaa8e36e2d89273b1ecf21085669c:/paper.tex diff --git a/paper.tex b/paper.tex index 063cbf9..3a51e45 100644 --- a/paper.tex +++ b/paper.tex @@ -380,8 +380,8 @@ % 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}} -\IEEEauthorblockA{\IEEEauthorrefmark{1} Femto-ST Institute, University of Franche Comte, France\\ +\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-Comt\'e, France\\ Email: \{raphael.couturier,christophe.guyeux\}@univ-fcomte.fr} \IEEEauthorblockA{\IEEEauthorrefmark{2} INRIA Bordeaux Sud-Ouest, France\\ Email: lilia.ziane@inria.fr} @@ -564,7 +564,7 @@ gradient and GMRES ones (Generalized Minimal RESidual). However, iterative methods suffer from scalability problems on parallel computing platforms with many processors, due to their need of reduction -operations, and to collective communications to achive matrix-vector +operations, and to collective communications to achieve matrix-vector multiplications. The communications on large clusters with thousands of cores and large sizes of messages can significantly affect the performances of these iterative methods. As a consequence, Krylov subspace iteration methods are often used @@ -621,10 +621,11 @@ 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 -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. At each $s$ iterations, the minimization step is applied in order to compute a new solution $x$. For that, the previous residuals of $Ax=b$ are computed by @@ -737,35 +738,57 @@ 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{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|| , \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} 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, +let $r_k$ be the +$k$-th residue of TSIRM, then +we still have: +\begin{equation} +||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{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. -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_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||.$ -Each step of the TSIRM algorithm \\ +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}. + +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{km}{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 the TSIRM algorithm consists in executing GMRES once. In that case, we obtain $||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_{k-1}||\leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$ by the inductive hypothesis. +\item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies $||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_{k-1}||\leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||$, and a least squares resolution. +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_{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+1}, S_{k-s+2}, \hdots, S_{k} \right)} ||b-AS\alpha ||_2\\ +& = \min_{x \in span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)} ||b-AS\alpha ||_2\\ +& \leqslant \min_{x \in span\left( x_{k} \right)} ||b-Ax ||_2\\ +& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\ +& \leqslant ||b-Ax_{k}||_2\\ +& = ||r_k||_2\\ +& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \end{array}$ +\end{itemize} +which concludes the induction and the 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. %%%********************************************************* %%%********************************************************* @@ -1007,13 +1030,22 @@ In Table~\ref{tab:04}, some experiments with example ex54 on the Curie architect %%%********************************************************* %%%********************************************************* +A novel two-stage iterative algorithm has been proposed in this article, +in order to accelerate the convergence Krylov iterative methods. +Our TSIRM proposal acts as a merger between Krylov based solvers and +a least-squares minimization step. +The convergence of the method has been proven in some situations, while +experiments up to 16,394 cores have been led to verify that TSIRM runs +5 or 7 times faster than GMRES. + -future plan : \\ -- study other kinds of matrices, problems, inner solvers\\ -- test the influence of all parameters\\ -- adaptative number of outer iterations to minimize\\ -- other methods to minimize the residuals?\\ -- implement our solver inside PETSc +For future work, the authors' intention is to investigate +other kinds of matrices, problems, and inner solvers. The +influence of all parameters must be tested too, while +other methods to minimize the residuals must be regarded. +The number of outer iterations to minimize should become +adaptative to improve the overall performances of the proposal. +Finally, this solver will be implemented inside PETSc. % conference papers do not normally have an appendix @@ -1068,4 +1100,3 @@ Curie and Juqueen respectively based in France and Germany. % that's all folks \end{document} -