From 103f48c15495d519e9a9f39a9ba06430c7ad1016 Mon Sep 17 00:00:00 2001
From: lilia <lilia@amazigh.bordeaux.inria.fr>
Date: Mon, 18 Aug 2014 13:25:16 +0200
Subject: [PATCH] v0

---
 paper.tex | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)

diff --git a/paper.tex b/paper.tex
index a848958..312270c 100644
--- a/paper.tex
+++ b/paper.tex
@@ -348,6 +348,18 @@
 \hyphenation{op-tical net-works semi-conduc-tor}
 
 
+
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+
+\algnewcommand\algorithmicinput{\textbf{Input:}}
+\algnewcommand\Input{\item[\algorithmicinput]}
+
+\algnewcommand\algorithmicoutput{\textbf{Output:}}
+\algnewcommand\Output{\item[\algorithmicoutput]}
+
+
+
 \begin{document}
 %
 % paper title
@@ -541,6 +553,47 @@ Iterative Krylov methods; sparse linear systems; error minimization; PETSC; %à
 %%%*********************************************************
 %%%*********************************************************
 \section{A Krylov two-stage algorithm}
+
+
+\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
+\end{algorithmic}
+\label{algo:01}
+\end{algorithm}
 %%%*********************************************************
 %%%*********************************************************
 
-- 
2.39.5