+\label{sec:03}
+A two-stage algorithm is proposed 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 functions over a Krylov
+subspace~\cite{saad96}. At each iteration, the sparse linear system $Ax=b$ is
+solved iteratively with an iterative method, for example GMRES
+method~\cite{saad86} or some of its variants, and the Krylov subspace 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 subspace 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
+subspace 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}) such as CGLS
+~\cite{hestenes52} or LSQR~\cite{paige82} which are more appropriate than a
+direct method in the parallel context.
+
+\begin{algorithm}[t]
+\caption{A Krylov two-stage algorithm}
+\begin{algorithmic}[1]
+ \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 $S_{k~mod~s}=x^k$
+ \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$
+ \EndIf
+ \EndFor
+\end{algorithmic}
+\label{algo:01}
+\end{algorithm}
+
+Operation $S_{k~ mod~ s}=x^k$ consists in copying the residual $x_k$ into the
+column $k~ mod~ s$ of the matrix $S$. After the minimization, the matrix $S$ is
+reused with the new values of the residuals.
+
