X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/blobdiff_plain/103f48c15495d519e9a9f39a9ba06430c7ad1016..4c9039f1d8f4a9b3099479e6f78f45f497dc0e59:/paper.tex

diff --git a/paper.tex b/paper.tex
index 312270c..60c7878 100644
--- a/paper.tex
+++ b/paper.tex
@@ -351,6 +351,8 @@
 
 \usepackage{algorithm}
 \usepackage{algpseudocode}
+\usepackage{amsmath}
+\usepackage{amssymb}
 
 \algnewcommand\algorithmicinput{\textbf{Input:}}
 \algnewcommand\Input{\item[\algorithmicinput]}
@@ -536,6 +538,11 @@ Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à
 % no \IEEEPARstart
 % You must have at least 2 lines in the paragraph with the drop letter
 % (should never be an issue)
+Iterative methods are become more attractive than direct ones to solve large sparse linear systems. They are more effective in a parallel context and require less memory and arithmetic operations than direct methods. 
+
+%les chercheurs ont développer différentes méthodes exemple de méthode iteratives stationnaires et non stationnaires (krylov) 
+%problème de convergence et difficulté dans le passage à l'échelle
+
 %%%*********************************************************
 %%%*********************************************************
 
@@ -553,44 +560,39 @@ Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à
 %%%*********************************************************
 %%%*********************************************************
 \section{A Krylov two-stage algorithm}
-
-
-\begin{algorithm}[!t]
+We propose a two-stage algorithm to solve large sparse linear systems of the form $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ is a sparse and square nonsingular matrix, $x\in\mathbb{R}^n$ is the solution vector and $b\in\mathbb{R}^n$ is the right-hand side. The algorithm is implemented as an inner-outer iteration solver based on iterative Krylov methods. The main key points of our solver are given in Algorithm~\ref{algo:01}. 
+
+In order to accelerate the convergence, the outer iteration is implemented as an iterative Krylov method which minimizes some error function over a Krylov sub-space~\cite{saad96}. At every iteration, the sparse linear system $Ax=b$ is solved iteratively with an iterative method as GMRES method~\cite{saad86} and the Krylov sub-space that we used is spanned by a basis $S$ composed of successive solutions issued from the inner iteration
+\begin{equation}
+  S = \{x^1, x^2, \ldots, x^s\} \text{,~} s\leq n.
+\end{equation} 
+The advantage of such a Krylov sub-space is that we neither need an orthogonal basis nor any synchronization between processors to generate this basis. The algorithm is periodically restarted every $s$ iterations with a new initial guess $x=S\alpha$ which minimizes the residual norm $\|b-Ax\|_2$ over the Krylov sub-space spanned by vectors of $S$, where $\alpha$ is a solution of the normal equations
+\begin{equation}
+  R^TR\alpha = R^Tb,
+\end{equation}
+which is associated with the least-squares problem
+\begin{equation}
+   \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2
+\label{eq:01}
+\end{equation}
+such that $R=AS$ is a dense rectangular matrix in $\mathbb{R}^{n\times s}$, $s\ll n$, and $R^T$ denotes the transpose of matrix $R$. We use an iterative method to solve the least-squares problem~(\ref{eq:01}) as CGLS~\cite{hestenes52} or LSQR~\cite{paige82} methods which is more appropriate than a direct method in the parallel context.
+
+\begin{algorithm}[t]
 \caption{A Krylov two-stage algorithm}
 \begin{algorithmic}[1]
-\Input $A_\ell$ (sparse sub-matrix), $B_\ell$ (right-hand side sub-vector)
-\Output $X_\ell$ (solution sub-vector)\vspace{0.2cm}
-\State Load $A_\ell$, $B_\ell$
-\State Set the initial guess $x^0$
-\State Set the minimizer $\tilde{x}^0=x^0$
-\For {$k=1,2,3,\ldots$ until the global convergence}
-\State Restart with $x^0=\tilde{x}^{k-1}$:
-\For {$j=1,2,\ldots,s$}
-\State \label{line7}Inner iteration solver: \Call{InnerSolver}{$x^0$, $j$}
-\State Construct basis $S$: add column vector $X_\ell^j$ to the matrix $S_\ell^k$
-\State Exchange local values of $X_\ell^j$ with the neighboring clusters
-\State Compute dense matrix $R$: $R_\ell^{k,j}=\sum^L_{i=1}A_{\ell i}X_i^j$ 
-\EndFor 
-\State \label{line12}Minimization $\|b-R\alpha\|_2$: \Call{UpdateMinimizer}{$S_\ell$, $R$, $b$, $k$}
-\State Local solution of linear system $Ax=b$: $X_\ell^k=\tilde{X}_\ell^k$
-\State Exchange the local minimizer $\tilde{X}_\ell^k$ with the neighboring clusters
-\EndFor
-
-\Statex
-
-\Function {InnerSolver}{$x^0$, $j$}
-\State Compute local right-hand side $Y_\ell = B_\ell - \sum^L_{\substack{m=1\\m\neq \ell}}A_{\ell m}X_m^0$
-\State Solving local splitting $A_{\ell \ell}X_\ell^j=Y_\ell$ using parallel GMRES method, such that $X_\ell^0$ is the initial guess
-\State \Return $X_\ell^j$
-\EndFunction
-
-\Statex
-
-\Function {UpdateMinimizer}{$S_\ell$, $R$, $b$, $k$}
-\State Solving normal equations $(R^k)^TR^k\alpha^k=(R^k)^Tb$ in parallel by $L$ clusters using parallel CGNR method
-\State Compute local minimizer $\tilde{X}_\ell^k=S_\ell^k\alpha^k$
-\State \Return $\tilde{X}_\ell^k$
-\EndFunction
+  \Input $A$ (sparse matrix), $b$ (right-hand side)
+  \Output $x$ (solution vector)\vspace{0.2cm}
+  \State Set the initial guess $x^0$
+  \For {$k=1,2,3,\ldots$ until convergence}
+    \State Solve iteratively $Ax^k=b$
+    \State Add vector $x^k$ to Krylov sub-space basis $S$
+    \If {$k$ mod $s=0$ {\bf and} not convergence}
+      \State Compute dense matrix $R=AS$
+      \State Solve least-squares problem $\underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2$
+      \State Compute minimizer $x^k=S\alpha$
+      \State Reinitialize Krylov sub-space basis $S$
+    \EndIf
+  \EndFor
 \end{algorithmic}
 \label{algo:01}
 \end{algorithm}
@@ -654,10 +656,13 @@ Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à
 % (used to reserve space for the reference number labels box)
 \begin{thebibliography}{1}
 
-\bibitem{IEEEhowto:kopka}
-%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
-%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
+\bibitem{saad86} Y.~Saad and M.~H.~Schultz, \emph{GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems}, SIAM Journal on Scientific and Statistical Computing, 7(3):856--869, 1986.
+
+\bibitem{saad96} Y.~Saad, \emph{Iterative Methods for Sparse Linear Systems}, PWS Publishing, New York, 1996.
+
+\bibitem{hestenes52} M.~R.~Hestenes and E.~Stiefel, \emph{Methods of conjugate gradients for solving linear system}, Journal of Research of National Bureau of Standards, B49:409--436, 1952.
 
+\bibitem{paige82} C.~C.~Paige and A.~M.~Saunders, \emph{LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares}, ACM Trans. Math. Softw. 8(1):43--71, 1982.
 \end{thebibliography}