]> AND Private Git Repository - GMRES2stage.git/blobdiff - paper.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
v2
[GMRES2stage.git] / paper.tex
index 312270cdad324e70a9c5c6777fcc5b056fd86898..185bbf3dd3570b39b038a2cdbc0aac81e454b7c5 100644 (file)
--- a/paper.tex
+++ b/paper.tex
@@ -553,44 +553,25 @@ Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à
 %%%*********************************************************
 %%%*********************************************************
 \section{A Krylov two-stage algorithm}
 %%%*********************************************************
 %%%*********************************************************
 \section{A Krylov two-stage algorithm}
+We propose a two-stage algorithm to solve large sparse linear systems of the form $Ax=b$ based on iterative Krylov sub-space methods.
 
 
 
 
-\begin{algorithm}[!t]
+\begin{algorithm}[!h]
 \caption{A Krylov two-stage algorithm}
 \begin{algorithmic}[1]
 \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 basis $S$
+    \If {$k$ mod $s=0$ {\bf and} not convergence}
+      \State Compute dense matrix $R=AS$
+      \State Solve least-squares problem $\|b-R\alpha\|_2$
+      \State Compute minimizer $x^k=S\alpha$
+      \State Reinitialize Krylov basis $S$
+    \EndIf
+  \EndFor
 \end{algorithmic}
 \label{algo:01}
 \end{algorithm}
 \end{algorithmic}
 \label{algo:01}
 \end{algorithm}