section 5.4

[GMRES2stage.git] / IJHPCN / paper.tex

%%%%%%%%%%%%%%%%%%%%%%\r
\documentclass{doublecol-new}\r
%%%%%%%%%%%%%%%%%%%%%%\r
\r
\usepackage{natbib,stfloats}\r
\usepackage{mathrsfs}\r
\usepackage[utf8]{inputenc}\r
\usepackage[T1]{fontenc}\r
\usepackage{algorithm}\r
\usepackage{algpseudocode}\r
\usepackage{amsmath}\r
\usepackage{amssymb}\r
\usepackage{multirow}\r
\usepackage{graphicx}\r
\usepackage{url}\r
\usepackage{dsfont}\r
\r
\r
\def\newblock{\hskip .11em plus .33em minus .07em}\r
\r
\theoremstyle{TH}{\r
\newtheorem{lemma}{Lemma}\r
\newtheorem{theorem}[lemma]{Theorem}\r
\newtheorem{corrolary}[lemma]{Corrolary}\r
\newtheorem{conjecture}[lemma]{Conjecture}\r
\newtheorem{proposition}[lemma]{Proposition}\r
\newtheorem{claim}[lemma]{Claim}\r
\newtheorem{stheorem}[lemma]{Wrong Theorem}\r
%\newtheorem{algorithm}{Algorithm}\r
}\r
\r
\theoremstyle{THrm}{\r
\newtheorem{definition}{Definition}[section]\r
\newtheorem{question}{Question}[section]\r
\newtheorem{remark}{Remark}\r
\newtheorem{scheme}{Scheme}\r
}\r
\r
\theoremstyle{THhit}{\r
\newtheorem{case}{Case}[section]\r
}\r
\algnewcommand\algorithmicinput{\textbf{Input:}}\r
\algnewcommand\Input{\item[\algorithmicinput]}\r
\r
\algnewcommand\algorithmicoutput{\textbf{Output:}}\r
\algnewcommand\Output{\item[\algorithmicoutput]}\r
\r
\r
\r
\r
\makeatletter\r
\def\theequation{\arabic{equation}}\r
\r
\JOURNALNAME{\TEN{\it International Journal of High Performance Computing and Networking}}\r
%\r
%\def\BottomCatch{%\r
%\vskip -10pt\r
%\thispagestyle{empty}%\r
%\begin{table}[b]%\r
%\NINE\begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}lcr@{}}%\r
%\\[-12pt]\r
%Copyright \copyright\ 2012 Inderscience Enterprises Ltd. & &%\r
%\end{tabular*}%\r
%\vskip -30pt%\r
%%%\vskip -35pt%\r
%\end{table}%\r
%}\r
\makeatother\r
\r
%%%%%%%%%%%%%%%%%\r
\begin{document}%\r
%%%%%%%%%%%%%%%%%\r
\r
\setcounter{page}{1}\r
\r
\LRH{R. Couturier, L. Ziane Khodja and C. Guyeux}\r
\r
\RRH{TSIRM: A Two-Stage Iteration with least-squares Residual Minimization algorithm}\r
\r
\VOL{x}\r
\r
\ISSUE{x}\r
\r
\PUBYEAR{xxxx}\r
\r
\BottomCatch\r
\r
\PUBYEAR{2015}\r
\r
\subtitle{}\r
\r
\title{TSIRM: A Two-Stage Iteration with least-squares Residual Minimization algorithm to solve large sparse linear and non linear systems}\r
\r
%\r
\authorA{Rapha\"el Couturier}\r
%\r
\affA{Femto-ST Institute, University of Bourgogne Franche-Comte, France\\\r
  E-mail: raphael.couturier@univ-fcomte.fr}\r
%\r
%\r
\authorB{Lilia Ziane Khodja}\r
\affB{LTAS-Mécanique numérique non linéaire, University of Liege, Belgium \\\r
   E-mail: l.zianekhodja@ulg.ac.be}\r
\r
\authorC{Christophe Guyeux}\r
\affC{Femto-ST Institute, University of Bourgogne Franche-Comte, France\\\r
  E-mail: christophe.guyeux@univ-fcomte.fr}\r
\r
\r
\begin{abstract}\r
In  this paper,  a  two-stage iterative  algorithm is  proposed  to improve  the\r
convergence  of  Krylov  based  iterative  methods,  typically  those  of  GMRES\r
variants.   The principle  of  the proposed  approach is  to  build an  external\r
iteration over the  Krylov method, and to frequently store  its current residual\r
(at each GMRES restart for instance).  After a given number of outer iterations,\r
a least-squares minimization step is applied on the matrix composed by the saved\r
residuals, in order to  compute a better solution and to  make new iterations if\r
required.  It  is proven that the  proposal has the same  convergence properties\r
than the inner  embedded method itself.\r
%%NEW\r
Several experiments  have been performed\r
with  the PETSc  solver  with  linear and  nonlinear  problems.  They show  good\r
speedups   compared  to   GMRES  with   up  to   16,394  cores   with  different\r
preconditioners.\r
%%ENDNEW\r
\end{abstract}\r
\r
\r
\r
\KEYWORD{Iterative Krylov methods; sparse linear and non linear systems; two stage iteration; least-squares residual minimization; PETSc.}\r
\r
%\REF{to this paper should be made as follows: Rodr\'{\i}guez\r
%Bol\'{\i}var, M.P. and Sen\'{e}s Garc\'{\i}a, B. (xxxx) `The\r
%corporate environmental disclosures on the internet: the case of\r
%IBEX 35 Spanish companies', {\it International Journal of Metadata,\r
%Semantics and Ontologies}, Vol. x, No. x, pp.xxx\textendash xxx.}\r
\r
\begin{bio}\r
Raphaël Couturier ....\r
\r
\noindent Lilia Ziane Khodja ...\r
\r
\noindent Christophe Guyeux ...\r
\end{bio}\r
\r
\r
\maketitle\r
\r
\r
 \section{Introduction}\r
\r
Iterative methods have recently become more attractive than direct ones to solve\r
very large sparse  linear systems~\cite{Saad2003}.  They are more  efficient in a\r
parallel context,  supporting thousands of  cores, and they require  less memory\r
and  arithmetic operations than  direct methods~\cite{bahicontascoutu}.  This is\r
why new iterative methods are frequently proposed or adapted by researchers, and\r
the increasing need to solve very  large sparse linear systems has triggered the\r
development  of  such  efficient  iterative  techniques  suitable  for  parallel\r
processing.\r
\r
Most  of the  successful  iterative  methods currently  available  are based  on\r
so-called ``Krylov  subspaces''. They consist  in forming a basis  of successive\r
matrix powers  multiplied by an  initial vector, which  can be for  instance the\r
residual. These methods  use vectors orthogonality of the  Krylov subspace basis\r
in  order to solve  linear systems.   The best  known iterative  Krylov subspace\r
methods are conjugate gradient and GMRES ones (Generalized Minimal RESidual).\r
\r
\r
However,  iterative  methods  suffer   from  scalability  problems  on  parallel\r
computing  platforms  with many  processors,  due  to  their need  of  reduction\r
operations,   and  to   collective  communications   to   achieve  matrix-vector\r
multiplications. The  communications on large  clusters with thousands  of cores\r
and large sizes  of messages can significantly affect  the performances of these\r
iterative methods. As a consequence, Krylov subspace iteration methods are often\r
used  with  preconditioners  in  practice,  to increase  their  convergence  and\r
accelerate their  performances.  However, most  of the good  preconditioners are\r
not scalable on large clusters.\r
\r
In  this research work,  a two-stage  algorithm based  on two  nested iterations\r
called inner-outer  iterations is proposed.  This algorithm  consists in solving\r
the sparse  linear system iteratively with  a small number  of inner iterations,\r
and  restarting  the  outer step  with  a  new  solution minimizing  some  error\r
functions  over some previous  residuals. For  further information  on two-stage\r
iteration      methods,     interested      readers      are     invited      to\r
consult~\cite{Nichols:1973:CTS}. Two-stage algorithms are easy to parallelize on\r
large clusters.  Furthermore,  the least-squares minimization technique improves\r
its convergence and performances.\r
\r
The present  article is  organized as follows.   Related works are  presented in\r
Section~\ref{sec:02}. Section~\ref{sec:03} details the two-stage algorithm using\r
a  least-squares  residual   minimization,  while  Section~\ref{sec:04}  provides\r
convergence  results  regarding this  method.   Section~\ref{sec:05} shows  some\r
experimental  results  obtained  on  large  clusters  using  routines  of  PETSc\r
toolkit. This research work ends by  a conclusion section, in which the proposal\r
is summarized while intended perspectives are provided.\r
\r
\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\r
\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\section{Related works}\r
\label{sec:02} \r
Krylov subspace iteration methods have increasingly become key\r
techniques  for  solving  linear and nonlinear systems,  or  eigenvalue  problems,\r
especially      since       the      increasing      development       of      \r
preconditioners~\cite{Saad2003,Meijerink77}.  One reason  for  the popularity  of\r
these methods is their generality, simplicity, and efficiency to solve systems of\r
equations arising from very large and complex problems.\r
\r
GMRES is one of the most  widely used Krylov iterative method for solving sparse\r
and   large  linear   systems.  It   has   been  developed   by  Saad   \emph{et\r
  al.}~\cite{Saad86}  as  a generalized  method  to  deal  with unsymmetric  and\r
non-Hermitian problems,  and indefinite symmetric problems too.  In its original\r
version  called full  GMRES,  this  algorithm minimizes  the  residual over  the\r
current Krylov subspace  until convergence in at most  $n$ iterations, where $n$\r
is the size  of the sparse matrix.   Full GMRES is however too  expensive in the\r
case  of  large  matrices,  since  the required  orthogonalization  process  per\r
iteration grows  quadratically with the  number of iterations. For  that reason,\r
GMRES is  restarted in  practice after  each $m\ll n$  iterations, to  avoid the\r
storage of a  large orthonormal basis. However, the  convergence behavior of the\r
restarted GMRES,  called GMRES($m$), in  many cases depends quite  critically on\r
the  $m$  value~\cite{Huang89}.  Therefore  in  most  cases,  a  preconditioning\r
technique  is applied  to the  restarted GMRES  method in  order to  improve its\r
convergence.\r
\r
To enhance the robustness of Krylov iterative solvers, some techniques have been\r
proposed allowing the use of different preconditioners, if necessary, within the\r
iteration  itself   instead  of  restarting.   Those  techniques   may  lead  to\r
considerable  savings  in  CPU  time  and memory  requirements.  Van  der  Vorst\r
in~\cite{Vorst94} has for  instance proposed variants of the  GMRES algorithm in\r
which a  different preconditioner is applied  in each iteration,  leading to the\r
so-called  GMRESR  family of  nested  methods.  In  fact,  the  GMRES method  is\r
effectively preconditioned with other iterative schemes (or GMRES itself), where\r
the  iterations  of the  GMRES  method are  called  outer  iterations while  the\r
iterations of  the preconditioning process  is referred to as  inner iterations.\r
Saad in~\cite{Saad:1993}  has proposed Flexible GMRES (FGMRES)  which is another\r
variant of the  GMRES algorithm using a variable  preconditioner.  In FGMRES the\r
search  directions  are  preconditioned  whereas  in GMRESR  the  residuals  are\r
preconditioned. However,  in practice, good  preconditioners are those  based on\r
direct methods,  as ILU preconditioners, which  are not easy  to parallelize and\r
suffer from the scalability problems on large clusters of thousands of cores.\r
\r
Recently,  communication-avoiding  methods have  been  developed  to reduce  the\r
communication overheads in Krylov subspace iterative solvers. On modern computer\r
architectures,   communications  between   processors  are   much   slower  than\r
floating-point        arithmetic       operations        on        a       given\r
processor.   Communication-avoiding  techniques  reduce   either  communications\r
between processors or data movements  between levels of the memory hierarchy, by\r
reformulating the communication-bound kernels (more frequently SpMV kernels) and\r
the orthogonalization  operations within the Krylov  iterative solver. Different\r
works have  studied the communication-avoiding techniques for  the GMRES method,\r
so-called     CA-GMRES,     on     multicore    processors     and     multi-GPU\r
machines~\cite{Mohiyuddin2009,Hoemmen2010,Yamazaki2014}.\r
\r
Compared  to all these  works and  to all  the other  works on  Krylov iterative\r
methods,  the originality of  our work  is to  build a  second iteration  over a\r
Krylov  iterative method  and to  minimize  the residuals  with a  least-squares\r
method after a given number of outer iterations.\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\r
\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\section{TSIRM: Two-stage iteration with least-squares residuals minimization algorithm}\r
\label{sec:03}\r
A two-stage  algorithm is proposed to  solve large sparse linear  systems of the\r
form  $Ax=b$,  where  $A\in\mathbb{R}^{n\times   n}$  is  a  sparse  and  square\r
nonsingular   matrix,   $x\in\mathbb{R}^n$   is   the   solution   vector,   and\r
$b\in\mathbb{R}^n$  is  the  right-hand  side.   As  explained  previously,  the\r
algorithm is implemented  as an inner-outer iteration solver  based on iterative\r
Krylov  methods.  The  main key-points  of  the  proposed  solver are  given  in\r
Algorithm~\ref{algo:01}.  It can be summarized as follows: the inner solver is a\r
Krylov  based one.  In order  to accelerate  its convergence,  the  outer solver\r
periodically applies  a least-squares minimization on the  residuals computed by\r
the inner one.\r
\r
At each  outer iteration,  the sparse linear  system $Ax=b$ is  partially solved\r
using only $m$ iterations of  an iterative method, this latter being initialized\r
with the last obtained approximation.  The GMRES method~\cite{Saad86}, or any of\r
its variants, can potentially be used as inner solver. The current approximation\r
of the Krylov method  is then stored inside a $n \times  s$ matrix $S$, which is\r
composed by  the $s$  last solutions  that have been  computed during  the inner\r
iterations phase.   In the remainder,  the $i$-th column  vector of $S$  will be\r
denoted by $S_i$.\r
\r
At each $s$ iterations, another kind of minimization step is applied in order to\r
compute  a new  solution $x$.  For that,  the previous  residuals of  $Ax=b$ are\r
computed  by  the  inner  iterations  with $(b-AS)$.  The  minimization  of  the\r
residuals is obtained by\r
\begin{equation}\r
   \underset{\alpha\in\mathbb{R}^{s}}{min}\|b-R\alpha\|_2\r
\label{eq:01}\r
\end{equation}\r
with $R=AS$. The new solution $x$ is then computed with $x=S\alpha$.\r
\r
\r
In practice, $R$ is a dense rectangular matrix belonging in $\mathbb{R}^{n\times\r
  s}$,  with $s\ll  n$.   In order  to  minimize~\eqref{eq:01}, a  least-squares\r
method such  as CGLS ~\cite{Hestenes52}  or LSQR~\cite{Paige82} is  used. Remark\r
that  these methods  are  more appropriate  than  a single  direct  method in  a\r
parallel context. CGLS has recently been used to improve the performance of multisplitting algorithms \cite{cz15:ij}.\r
\r
\r
\r
\begin{algorithm}[t]\r
\caption{TSIRM}\r
\begin{algorithmic}[1]\r
  \Input $A$ (sparse matrix), $b$ (right-hand side)\r
  \Output $x$ (solution vector)\vspace{0.2cm}\r
  \State Set the initial guess $x_0$\r
  \For {$k=1,2,3,\ldots$ until convergence ($error<\epsilon_{tsirm}$)} \label{algo:conv}\r
    \State  $[x_k,error]=Solve(A,b,x_{k-1},max\_iter_{kryl})$   \label{algo:solve}\r
    \State $S_{k \mod s}=x_k$ \label{algo:store} \Comment{update column ($k \mod s$) of $S$}\r
    \If {$k \mod s=0$ {\bf and} $error>\epsilon_{kryl}$}\r
      \State $R=AS$ \Comment{compute dense matrix} \label{algo:matrix_mul}\r
            \State $\alpha=Least\_Squares(R,b,max\_iter_{ls})$ \label{algo:}\r
      \State $x_k=S\alpha$  \Comment{compute new solution}\r
    \EndIf\r
  \EndFor\r
\end{algorithmic}\r
\label{algo:01}\r
\end{algorithm}\r
\r
Algorithm~\ref{algo:01} summarizes  the principle  of the proposed  method.  The\r
outer iteration is inside the \emph{for} loop. Line~\ref{algo:solve}, the Krylov\r
method is called  for a maximum of $max\_iter_{kryl}$  iterations.  In practice,\r
we suggest to  set this parameter equal to the restart  number in the GMRES-like\r
method. Moreover,  a tolerance  threshold must be  specified for the  solver. In\r
practice, this threshold must be  much smaller than the convergence threshold of\r
the TSIRM  algorithm (\emph{i.e.},  $\epsilon_{tsirm}$).  We also  consider that\r
after  the call of  the $Solve$  function, we  obtain the  vector $x_k$  and the\r
$error$, which is defined by $||Ax_k-b||_2$.\r
\r
  Line~\ref{algo:store},  $S_{k \mod  s}=x_k$ consists  in copying  the solution\r
  $x_k$ into the  column $k \mod s$ of $S$.  After  the minimization, the matrix\r
  $S$ is reused with the new values of the residuals.  To solve the minimization\r
  problem, an  iterative method is used.  Two parameters are  required for that:\r
  the maximum number of iterations  ($max\_iter_{ls}$) and the threshold to stop\r
  the method ($\epsilon_{ls}$).\r
\r
Let us summarize the most important parameters of TSIRM:\r
\begin{itemize}\r
\item $\epsilon_{tsirm}$: the threshold that stops the TSIRM method;\r
\item $max\_iter_{kryl}$: the maximum number of iterations for the Krylov method;\r
\item $s$: the number of outer iterations before applying the minimization step;\r
\item $max\_iter_{ls}$: the maximum number of iterations for the iterative least-squares method;\r
\item $\epsilon_{ls}$: the threshold used to stop the least-squares method.\r
\end{itemize}\r
\r
\r
The  parallelization  of  TSIRM  relies   on  the  parallelization  of  all  its\r
parts. More  precisely, except the least-squares  step, all the  other parts are\r
obvious to  achieve out in parallel. In  order to develop a  parallel version of\r
our   code,   we   have   chosen   to   use   PETSc~\cite{petsc-web-page}.    In\r
line~\ref{algo:matrix_mul}, the matrix-matrix  multiplication is implemented and\r
efficient since the matrix $A$ is sparse and the matrix $S$ contains few columns\r
in  practice.  As  explained  previously,  at  least  two  methods  seem  to  be\r
interesting  to solve  the least-squares  minimization,  the CGLS  and the  LSQR\r
methods.\r
\r
%% In Algorithm~\ref{algo:02} we remind the CGLS algorithm. The LSQR method follows\r
%% more or less the  same principle but it takes more place,  so we briefly explain\r
%% the parallelization of CGLS which is  similar to LSQR.\r
\r
%% \begin{algorithm}[t]\r
%% \caption{CGLS}\r
%% \begin{algorithmic}[1]\r
%%   \Input $A$ (matrix), $b$ (right-hand side)\r
%%   \Output $x$ (solution vector)\vspace{0.2cm}\r
%%   \State Let $x_0$ be an initial approximation\r
%%   \State $r_0=b-Ax_0$\r
%%   \State $p_1=A^Tr_0$\r
%%   \State $s_0=p_1$\r
%%   \State $\gamma=||s_0||^2_2$\r
%%   \For {$k=1,2,3,\ldots$ until convergence ($\gamma<\epsilon_{ls}$)} \label{algo2:conv}\r
%%     \State $q_k=Ap_k$\r
%%     \State $\alpha_k=\gamma/||q_k||^2_2$\r
%%     \State $x_k=x_{k-1}+\alpha_kp_k$\r
%%     \State $r_k=r_{k-1}-\alpha_kq_k$\r
%%     \State $s_k=A^Tr_k$\r
%%     \State $\gamma_{old}=\gamma$\r
%%     \State $\gamma=||s_k||^2_2$\r
%%     \State $\beta_k=\gamma/\gamma_{old}$\r
%%     \State $p_{k+1}=s_k+\beta_kp_k$\r
%%   \EndFor\r
%% \end{algorithmic}\r
%% \label{algo:02}\r
%% \end{algorithm}\r
\r
%%NEW\r
\r
The PETSc code we have develop is avaiable here: {\bf a mettre} and it will soon\r
be integrated with  the PETSc sources. TSIRM has been  implemented as any solver\r
for linear systems in PETSc. As it  requires to use another solver, we have used\r
a very interesting  feature of PETSc that  enables to use a  preconditioner as a\r
linear system  with the  function {\it  PCKSPGetKSP}.  As  the LSQR  function is\r
already implemented in PETSc, we have used  it. CGLS was not implemented yet, so\r
we have  implemented it and  we plan  to define it  as a minimization  solver in\r
PETSc similarly to LSQR. Both CGLS and LSQR are not complex from the computation\r
point of  view. They involves  matrix-vector multiplications and  some classical\r
operations:  dot product,  norm,  multiplication, and  addition  on vectors.  As\r
presented in Section~\ref{sec:05} the minimization step is scalable.\r
\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\r
\section{Convergence results}\r
\label{sec:04}\r
\r
\r
We suppose in this section that GMRES($m$) is used as solver in the TSIRM algorithm applied on a complex matrix $A$.\r
Let us denote $A^\ast$ the conjugate transpose of $A$, and let $\mathfrak{R}(A)=\dfrac{1}{2} \left( A + A^\ast\right)$, $\mathfrak{I}(A)=\dfrac{1}{2i} \left( A - A^\ast\right)$. \r
\r
\subsection{$\mathfrak{R}(A)$ is positive}\r
\r
\begin{proposition}\r
\label{positiveConvergent}\r
If $\mathfrak{R}(A)$ is positive, then the TSIRM algorithm is convergent.\r
\end{proposition}\r
\r
\r
\begin{proof}\r
If $\mathfrak{R}(A)$ is positive, then even if $A$ is complex, it is possible to state that \r
the GMRES algorithm is convergent, see, \emph{e.g.},~\cite{Huang89}. In particular, its residual norm\r
decreases to zero.\r
\r
At each iterate of the TSIRM algorithm, either a GMRES iteration is realized or a least square\r
resolution (to find the minimum of $||b-Ax||_2$ is achieved on the linear span of the iterated approximation vectors \r
$span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$\r
of the last GMRES stage,\r
where\r
$\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 \}$.\r
\r
Obviously, the minimum of $||b-Ax||_2$ on the set $span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$ \r
is lower than or equal to $||b-Ax_k||_2$, which is the last obtained GMRES-residual norm. So we can\r
conclude that the intermediate stage of least square resolution inserted into the GMRES algorithm\r
does not break the decreasing to zero of the GMRES-residual norm. \r
\r
In other words, the TSIRM algorithm is convergent.\r
\end{proof}\r
\r
\r
Regarding the convergence speed, we can claim that,\r
\begin{proposition}\r
\label{prop:saad}\r
If $A$ is a positive matrix, then the convergence of the \r
TSIRM algorithm is linear. \r
\r
Furthermore, let $r_k$ be the $k$-th residue of TSIRM, then\r
we have the following boundaries:\r
\begin{equation}\r
||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| ,\r
\end{equation}\r
where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$.\r
\end{proposition}\r
\r
\begin{proof}\r
Let us first recall that, when $A$ is a positive real matrix with symmetric part $M$, then the residual norm provided at the $m$-th step of GMRES satisfies:\r
\begin{equation*}\r
||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| ,\r
\end{equation*}\r
where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}.\r
These well-known results can be found, \emph{e.g.}, in~\cite{Saad86}.\r
\r
We will now prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, \r
$||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||$ when $A$ is positive.\r
\r
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$ that follows the inductive hypothesis due to the results recalled above.\r
\r
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||$.\r
We will show that the statement holds too for $r_k$. Two situations can occur:\r
\begin{itemize}\r
\item If $k \not\equiv 0 ~(\textrm{mod}\ m)$, then the TSIRM algorithm consists in executing GMRES once. In that case and by using the inductive hypothesis, we obtain either $||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||$.\r
\item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies:\r
$$||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||$$\r
and a least squares resolution.\r
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,\\\r
$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$\r
\r
$\begin{array}{ll}\r
& = \min_{x \in span\left(S_{k-s+1}, S_{k-s+2}, \hdots, S_{k} \right)} ||b-AS\alpha ||_2\\\r
& = \min_{x \in span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)} ||b-AS\alpha ||_2\\\r
& \leqslant \min_{x \in span\left( x_{k} \right)} ||b-Ax ||_2\\\r
& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\\r
& \leqslant ||b-Ax_{k}||_2\\\r
& = ||r_k||_2\\\r
& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \\\r
\end{array}$\r
\end{itemize}\r
which concludes the induction and the proof.\r
\end{proof}\r
\r
\r
\r
\subsection{$\mathfrak{R}(A)$ is positive definite}\r
\r
\begin{proposition}\r
\label{prop2}\r
Convergence of the TSIRM algorithm is at least linear when $\mathfrak{R}(A)$ is \r
positive definite. Furthermore, the rate of convergence is lower \r
than $$\min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}}; \r
\left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ,$$\r
where ${\lambda_{min}^{X}}$ (resp. ${\lambda_{max}^{X}}$) is the lowest (resp. largest) eigenvalue of matrix $X$.\r
\end{proposition}\r
\r
\r
\begin{proof}\r
If $\mathfrak{R}(A)$ is positive definite, then it is positive, and so the TSIRM algorithm\r
is convergent due to Proposition~\ref{positiveConvergent}.\r
\r
Furthermore, as stated in the proof of Proposition~\ref{positiveConvergent}, the GMRES residue is under control \r
when $\mathfrak{R}(A)$ is positive. More precisely, it has been proven in the literature that the residual norm \r
provided at the $m$-th step of GMRES satisfies:\r
\begin{enumerate}\r
\item $||r_m|| \leqslant \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}} ||r_0||$, see, \emph{e.g.},~\cite{citeulike:2951999}, \r
\item $||r_m|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}} ||r_0||$, see~\cite{ANU:137201},\r
\end{enumerate}\r
which proves the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$.\r
\r
We will now prove by a mathematical induction, and following the same canvas than in the proof of Prop.~\ref{positiveConvergent}, that: for each $k \in \mathbb{N}^\ast$, the TSIRM-residual norm satisfies\r
\begin{equation}\r
\label{induc}\r
\begin{array}{ll}\r
||r_k|| \leqslant & \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}}; \right. \\\r
& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ||r_0||\r
\end{array}\r
\end{equation}\r
when $A$ is positive definite.\r
\r
\r
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$ that follows the inductive hypothesis due to the results recalled in the items listed above.\r
\r
Suppose now that the claim holds for all $u=1, 2, \hdots, k-1$, that is, $\forall u \in \{1,2,\hdots, k-1\}$, $||r_u|| \leqslant  \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mu}{2}} ||r_0||$.\r
We will show that the statement holds too for $r_k$. Two situations can occur:\r
\begin{itemize}\r
\item If $k \not\equiv 0 ~(\textrm{mod}\ m)$, then the TSIRM algorithm consists in executing GMRES once. In that case and by using the inductive hypothesis, we obtain \r
$||r_k|| \leqslant \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}} \leqslant \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}} ||r_0||$, due to~\cite{citeulike:2951999}. Furthermore, we have too that: $||r_k|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}} ||r_{k-1}|| \leqslant \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}} ||r_0||$, as proven in~\cite{ANU:137201} and by using the inductive hypothesis. So we can conclude that \r
$$\begin{array}{ll}||r_k|| \leqslant & \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}}; \right. \\\r
& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| \r
\end{array}.$$\r
\r
\item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies, following the previous item:\r
$$\begin{array}{ll}\r
||r_k|| & \leqslant  \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{m}{2}}; \right. \\\r
& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) \times ||r_{k-1}||\\\r
 & \leqslant  \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}}; \right. \\\r
& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| \r
\end{array}$$\r
and the least squares resolution of $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2$.\r
\r
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$, as defined previously. So,\\\r
$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2  = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$\r
\r
$\begin{array}{ll}\r
& = \min_{x \in span\left(S_{k-s+1}, S_{k-s+2}, \hdots, S_{k} \right)} ||b-AS\alpha ||_2\\\r
& = \min_{x \in span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)} ||b-AS\alpha ||_2\\\r
& \leqslant \min_{x \in span\left( x_{k} \right)} ||b-Ax ||_2\\\r
& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\\r
& \leqslant ||b-Ax_{k}||_2\\\r
& = ||r_k||_2\\\r
& \leqslant \min\left( \left(1- \dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{ \lambda_{min}^{\mathfrak{R}(A)} \lambda_{max}^{\mathfrak{R}(A)} + {\lambda_{max}^{\mathfrak{I}(A)}}^2}\right)^{\frac{mk}{2}}; \right. \\\r
& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| \r
\end{array} .$\r
\end{itemize}\r
due to the inductive hypothesis. \r
So the statement of Equation~\eqref{induc} holds too for the $k$-th iterate, which concludes the induction and the proof.\r
\end{proof}\r
\r
\subsection{A last linear convergence}\r
\r
\r
\begin{proposition}\r
Let us define the field of values of $A$ by \r
$$\mathfrak{F}(A) = \left\{ \dfrac{x^\ast A x}{x^\ast x}, x \in \mathds{C}^n\setminus \{0\} \right\} .$$\r
\r
Then if $\mathfrak{F}(A)$ is included into a closed ball of radius $r$ and center $c$,\r
which does not contain the origin, then the convergence of the TSIRM algorithm is at least linear. \r
\r
More precisely, the rate of convergence is lower \r
than $2 \dfrac{r}{|c|}$.\r
\end{proposition}\r
\r
\begin{proof}\r
This inequality comes from the fact that, in the conditions of the proposition, the GMRES residue \r
satisfies the inequality: $|r_k| \leqslant 2 \dfrac{r}{|c|}^k |r_0|$. An induction inspired by\r
the proofs of Propositions~\ref{prop:saad} and~\ref{prop2} can transfer this inequality to the\r
TSIRM residue.\r
\end{proof}\r
\r
\r
\r
Remark that a similar proposition can be formulated at each time\r
the given solver satisfies an inequality of the form $||r_n|| \leqslant \mu^n ||r_0||$,\r
with $|\mu|<1$. Furthermore, it is \emph{a priori} possible in some particular cases \r
regarding $A$, \r
that the proposed TSIRM converges while the GMRES($m$) does not.\r
\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\section{Experiments using PETSc}\r
\label{sec:05}\r
\r
In  this section  four kinds  of experiments  have been  performed. First,  some\r
experiments on  real matrices issued  from the  sparse matrix florida  have been\r
achieved out. Second, some experiments in parallel with some linear problems are\r
reported and analyzed.  Third, some experiments in parallèle  with som nonlinear\r
problems are illustrated. Finally some parameters  of TSIRM are studied in order\r
to understand their influences.\r
\r
\r
\subsection{Real matrices}\r
%%ENDNEW\r
\r
\r
In order to see the behavior of our approach when considering only one processor,\r
a  first  comparison  with  GMRES  or  FGMRES and  the  new  algorithm  detailed\r
previously  has been  experimented.  Matrices  that  have been  used with  their\r
characteristics (names, fields, rows,  and nonzero coefficients) are detailed in\r
Table~\ref{tab:01}.  These  latter, which are  real-world applications matrices,\r
have    been   extracted    from   the    Davis   collection,    University   of\r
Florida~\cite{Dav97}.\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|c|c|r|r|r|} \r
\hline\r
Matrix name              & Field             &\# Rows   & \# Nonzeros   \\\hline \hline\r
crashbasis         & Optimization      & 160,000  &  1,750,416  \\\r
parabolic\_fem     & Comput. fluid dynamics  & 525,825 & 2,100,225 \\\r
epb3               & Thermal problem   & 84,617  & 463,625  \\\r
atmosmodj          & Comput. fluid dynamics  & 1,270,432 & 8,814,880 \\\r
bfwa398            & Electromagnetics pb & 398 & 3,678 \\\r
torso3             & 2D/3D problem & 259,156 & 4,429,042 \\\r
\hline\r
\r
\end{tabular}\r
\caption{Main characteristics of the sparse matrices chosen from the Davis collection}\r
\label{tab:01}\r
\end{center}\r
\end{table*}\r
Chosen parameters  are detailed below.   \r
We have  stopped  the  GMRES every  30\r
iterations (\emph{i.e.}, $max\_iter_{kryl}=30$), which is the default \r
setting of GMRES restart parameter.  The parameter $s$ has been set to 8. CGLS \r
 minimizes  the   least-squares  problem   with  parameters\r
$\epsilon_{ls}=1e-40$ and $max\_iter_{ls}=20$.  The external precision is set to\r
$\epsilon_{tsirm}=1e-10$.  These  experiments have been performed  on an Intel(R)\r
Core(TM) i7-3630QM CPU @ 2.40GHz with the 3.5.1 version  of PETSc.\r
\r
\r
Experiments comparing \r
a GMRES variant with TSIRM in the resolution of linear systems are given in  Table~\ref{tab:02}. \r
The  second column describes whether GMRES or FGMRES has been used for linear systems solving.  \r
Different preconditioners  have been used according to the matrices.  With  TSIRM, the  same\r
solver and the  same preconditioner are used.  This table  shows that TSIRM can\r
drastically reduce  the number of iterations needed to reach the  convergence, when the\r
number of iterations for  the normal GMRES is more or less  greater than 500. In\r
fact this also depends on two parameters: the number of iterations before stopping GMRES\r
and the number of iterations to perform the minimization.\r
\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|c|c|r|r|r|r|} \r
\hline\r
\r
 \multirow{2}{*}{Matrix name}  & Solver /   & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSIRM CGLS} \\ \r
\cline{3-6}\r
       &  precond             & Time  & \# Iter.  & Time  & \# Iter.  \\\hline \hline\r
\r
crashbasis         & gmres / none             &  15.65     & 518  &  14.12 & 450  \\\r
parabolic\_fem     & gmres / ilu           & 1009.94   & 7573 & 401.52 & 2970 \\\r
epb3               & fgmres / sor             &  8.67     & 600  &  8.21 & 540  \\\r
atmosmodj          &  fgmres / sor & 104.23  & 451 & 88.97 & 366  \\\r
bfwa398            & gmres / none  & 1.42 & 9612 & 0.28 & 1650 \\\r
torso3             & fgmres / sor  & 37.70 & 565 & 34.97 & 510 \\\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison between sequential standalone (F)GMRES and TSIRM with (F)GMRES (time in seconds).}\r
\label{tab:02}\r
\end{center}\r
\end{table*}\r
\r
\r
%%NEW\r
\subsection{Parallel linear problems}\r
%%ENDNEW\r
\r
In order to perform larger experiments, we have tested some example applications\r
of  PETSc. These  applications are  available in  the \emph{ksp}  part,  which is\r
suited for scalable linear equations solvers:\r
\begin{itemize}\r
\item ex15  is an example  that solves in  parallel an operator using  a finite\r
  difference  scheme.   The  diagonal  is  equal to  4  and  4  extra-diagonals\r
  representing the neighbors in each directions  are equal to -1. This example is\r
  used  in many  physical phenomena, for  example, heat  and fluid  flow, wave\r
  propagation, etc.\r
\item ex54 is another example based on a 2D problem discretized with quadrilateral\r
  finite elements. In this example, the user can define the scaling of material\r
  coefficient in embedded circle called $\alpha$.\r
\end{itemize}\r
For more technical details on these applications, interested readers are invited\r
to read  the codes  available in  the PETSc sources.   These problems  have been\r
chosen because they are scalable with many  cores.\r
\r
In  the  following,   larger  experiments  are  described  on   two  large  scale\r
architectures: Curie  and Juqueen.   Both these architectures  are supercomputers\r
respectively  composed  of  80,640  cores   for  Curie  and  458,752  cores  for\r
Juqueen. Those  machines are respectively hosted  by GENCI in  France and Jülich\r
Supercomputing Center in Germany.  They belong with other similar architectures\r
to the  PRACE initiative (Partnership  for Advanced Computing  in Europe), which\r
aims  at  proposing  high  performance supercomputing  architecture  to  enhance\r
research  in  Europe.  The  Curie  architecture is  composed  of  Intel  E5-2680\r
processors  at 2.7  GHz with  2Gb memory  by core.  The Juqueen  architecture,\r
for its part, is\r
composed by IBM PowerPC  A2 at  1.6 GHz with  1Gb memory  per core.  Both those\r
architectures are equipped with a dedicated high speed network.\r
\r
\r
In  many situations, using  preconditioners is  essential in  order to  find the\r
solution of a linear system.  There are many preconditioners available in PETSc.\r
However, for parallel applications, all  the preconditioners based on matrix factorization\r
are  not  available. In  our  experiments, we  have  tested  different kinds  of\r
preconditioners, but  as it is  not the subject  of this paper, we  will not\r
present results with many preconditioners. In  practice, we have chosen to use a\r
multigrid (MG)  and successive  over-relaxation (SOR). For  further details  on the\r
preconditioners in PETSc, readers are referred to~\cite{petsc-web-page}.\r
\r
\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|r|r|r|r|r|r|r|r|r|} \r
\hline\r
\r
  nb. cores & precond   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain \\ \r
\cline{3-8}\r
             &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline\r
  2,048      & MG                    & 403.49   & 18,210    & 73.89  & 3,060   & 77.84  & 3,270  & 5.46 \\\r
  2,048      & SOR                   & 745.37   & 57,060    & 87.31  & 6,150   & 104.21 & 7,230  & 8.53 \\\r
  4,096      & MG                    & 562.25   & 25,170    & 97.23  & 3,990   & 89.71  & 3,630  & 6.27 \\\r
  4,096      & SOR                   & 912.12   & 70,194    & 145.57 & 9,750   & 168.97 & 10,980 & 6.26 \\\r
  8,192      & MG                    & 917.02   & 40,290    & 148.81 & 5,730   & 143.03 & 5,280  & 6.41 \\\r
  8,192      & SOR                   & 1,404.53 & 106,530   & 212.55 & 12,990  & 180.97 & 10,470 & 7.76 \\\r
  16,384     & MG                    & 1,430.56 & 63,930    & 237.17 & 8,310   & 244.26 & 7,950  & 6.03 \\\r
  16,384     & SOR                   & 2,852.14 & 216,240   & 418.46 & 21,690  & 505.26 & 23,970 & 6.82 \\\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison of FGMRES and TSIRM with FGMRES for example ex15 of PETSc/KSP with two preconditioners (MG and SOR) having 25,000 components per core on Juqueen ($\epsilon_{tsirm}=1e-3$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}\r
\label{tab:03}\r
\end{center}\r
\end{table*}\r
\r
Table~\ref{tab:03} shows  the execution  times and the  number of  iterations of\r
example ex15  of PETSc on the  Juqueen architecture. Different  numbers of cores\r
are studied  ranging from 2,048 up-to  16,383 with the  two preconditioners {\it\r
  MG}  and {\it  SOR}.   For those  experiments,  the number  of components  (or\r
unknowns  of  the problems)  per  core  is fixed  at  25,000,  also called  weak\r
scaling. This number  can seem relatively small. In  fact, for some applications\r
that  need a  lot of  memory, the  number of  components per  processor requires\r
sometimes to  be small. Other parameters  for this application  are described in\r
the legend of this table.\r
\r
\r
\r
In  Table~\ref{tab:03},  we  can  notice   that  TSIRM  is  always  faster  than\r
FGMRES. The last  column shows the ratio between FGMRES and  the best version of\r
TSIRM according  to the minimization  procedure: CGLS or  LSQR. Even if  we have\r
computed the worst case between CGLS and  LSQR, it is clear that TSIRM is always\r
faster than  FGMRES. For  this example, the  multigrid preconditioner  is faster\r
than SOR. The gain between TSIRM and  FGMRES is more or less similar for the two\r
preconditioners.  Looking at the number  of iterations to reach the convergence,\r
it is  obvious that TSIRM allows the  reduction of the number  of iterations. It\r
should be noticed  that for TSIRM, in those experiments,  only the iterations of\r
the Krylov solver  are taken into account.  Iterations of CGLS  or LSQR were not\r
recorded  but they  are  time-consuming.  In  general, each  $max\_iter_{kryl}*s$\r
iterations which corresponds to 30*12, there are $max\_iter_{ls}$ iterations for\r
the least-squares method which corresponds to 15.\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{nb_iter_sec_ex15_juqueen}\r
\caption{Number of iterations per second with ex15 and the same parameters as in Table~\ref{tab:03} (weak scaling)}\r
\label{fig:01}\r
\end{figure}\r
\r
\r
In  Figure~\ref{fig:01}, the number  of iterations  per second  corresponding to\r
Table~\ref{tab:03}  is  displayed.   It  can  be  noticed  that  the  number  of\r
iterations per second of FMGRES is constant whereas it decreases with TSIRM with\r
both preconditioners. This can be explained  by the fact that when the number of\r
cores increases, the time for the least-squares minimization step also increases\r
but, generally, when the number of  cores increases, the number of iterations to\r
reach the threshold  also increases, and, in that case,  TSIRM is more efficient\r
to reduce  the number of iterations. So,  the overall benefit of  using TSIRM is\r
interesting.\r
\r
\r
\r
\r
\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|r|r|r|r|r|r|r|r|r|} \r
\hline\r
\r
  nb. cores & $\epsilon_{tsirm}$  & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain \\ \r
\cline{3-8}\r
             &                       & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. & \\\hline \hline\r
  2,048      & 8e-5                  & 108.88 & 16,560  & 23.06  &  3,630  & 22.79  & 3,630   & 4.77 \\\r
  2,048      & 6e-5                  & 194.01 & 30,270  & 35.50  &  5,430  & 27.74  & 4,350   & 6.99 \\\r
  4,096      & 7e-5                  & 160.59 & 22,530  & 35.15  &  5,130  & 29.21  & 4,350   & 5.49 \\\r
  4,096      & 6e-5                  & 249.27 & 35,520  & 52.13  &  7,950  & 39.24  & 5,790   & 6.35 \\\r
  8,192      & 6e-5                  & 149.54 & 17,280  & 28.68  &  3,810  & 29.05  & 3,990  & 5.21 \\\r
  8,192      & 5e-5                  & 785.04 & 109,590 & 76.07  &  10,470  & 69.42 & 9,030  & 11.30 \\\r
  16,384     & 4e-5                  & 718.61 & 86,400 & 98.98  &  10,830  & 131.86  & 14,790  & 7.26 \\\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison of FGMRES  and TSIRM with FGMRES algorithms for ex54 of PETSc/KSP (both with the MG preconditioner) with 25,000 components per core on Curie ($max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}\r
\label{tab:04}\r
\end{center}\r
\end{table*}\r
\r
\r
In  Table~\ref{tab:04},  some  experiments   with  example  ex54  on  the  Curie\r
architecture are reported.  For this  application, we fixed $\alpha=0.6$.  As it\r
can be seen in that table, the size of the problem has a strong influence on the\r
number of iterations to reach the  convergence. That is why we have preferred to\r
change the threshold.  If we set  it to $1e-3$ as with the previous application,\r
only one iteration is necessary  to reach the convergence. So Table~\ref{tab:04}\r
shows the  results of  different executions with  different number of  cores and\r
different thresholds. As with the previous example, we can observe that TSIRM is\r
faster than  FGMRES. The ratio greatly  depends on the number  of iterations for\r
FMGRES to reach the threshold. The greater the number of iterations to reach the\r
convergence is, the  better the ratio between our algorithm  and FMGRES is. This\r
experiment is  also a  weak scaling with  approximately $25,000$  components per\r
core. It can also  be observed that the difference between CGLS  and LSQR is not\r
significant. Both can be good but it seems not possible to know in advance which\r
one will be the best.\r
\r
Table~\ref{tab:05} shows  a strong scaling  experiment with example ex54  on the\r
Curie  architecture. So,  in  this case,  the  number of  unknowns  is fixed  at\r
$204,919,225$ and the number of cores ranges from $512$ to $8192$ with the power\r
of two.  The  threshold is fixed at $5e-5$ and only  the $mg$ preconditioner has\r
been  tested. Here  again  we can  see that  TSIRM  is faster  than FGMRES.  The\r
efficiency of each algorithm is reported.  It can be noticed that the efficiency\r
of FGMRES is  better than the TSIRM  one except with $8,192$ cores  and that its\r
efficiency is  greater than one  whereas the efficiency  of TSIRM is  lower than\r
one.  Nevertheless,  the ratio  of TSIRM with  any version of  the least-squares\r
method is  always faster.  With $8,192$  cores when the number  of iterations is\r
far  more important  for  FGMRES,  we can  see  that it  is  only slightly  more\r
important for TSIRM.\r
\r
In Figure~\ref{fig:02}  we report  the number of  iterations per second  for the\r
experiments  reported in  Table~\ref{tab:05}.  This  figure highlights  that the\r
number of iterations  per second is more  or less the same for  FGMRES and TSIRM\r
with a little advantage for FGMRES. It  can be explained by the fact that, as we\r
have previously  explained, the  iterations of the  least-squares steps  are not\r
taken into account with TSIRM.\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} \r
\hline\r
\r
  nb. cores   & \multicolumn{2}{c|}{FGMRES} & \multicolumn{2}{c|}{TSIRM CGLS} &  \multicolumn{2}{c|}{TSIRM LSQR} & best gain & \multicolumn{3}{c|}{efficiency} \\ \r
\cline{2-7} \cline{9-11}\r
                    & Time  & \# Iter.  & Time  & \# Iter. & Time  & \# Iter. &   & FGMRES & TS CGLS & TS LSQR\\\hline \hline\r
   512              & 3,969.69 & 33,120 & 709.57 & 5,790  & 622.76 & 5,070  & 6.37  &   1    &    1    &     1     \\\r
   1024             & 1,530.06  & 25,860 & 290.95 & 4,830  & 307.71 & 5,070 & 5.25  &  1.30  &    1.21  &   1.01     \\\r
   2048             & 919.62    & 31,470 & 237.52 & 8,040  & 194.22 & 6,510 & 4.73  & 1.08   &    .75   &   .80\\\r
   4096             & 405.60    & 28,380 & 111.67 & 7,590  & 91.72  & 6,510 & 4.42  & 1.22   &  .79     &   .84 \\\r
   8192             & 785.04   & 109,590 & 76.07  & 10,470 & 69.42 & 9,030  & 11.30 &   .32  &   .58    &  .56 \\\r
\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison of FGMRES  and TSIRM for ex54 of PETSc/KSP (both with the MG preconditioner) with 204,919,225 components on Curie with different number of cores ($\epsilon_{tsirm}=5e-5$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}\r
\label{tab:05}\r
\end{center}\r
\end{table*}\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{nb_iter_sec_ex54_curie}\r
\caption{Number of iterations per second with ex54 and the same parameters as in Table~\ref{tab:05} (strong scaling)}\r
\label{fig:02}\r
\end{figure}\r
\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{nb_iter_sec_ex45_curie}\r
\caption{Number of iterations per second with ex45 and the same parameters as in Table~\ref{tab:06} (weak scaling)}\r
\label{fig:03}\r
\end{figure}\r
\r
\r
%%NEW\r
It  is well-known  that  preconditioners have  a very  strong  influence on  the\r
convergence  of  linear  systems.   Previously,  we  have  used  some  classical\r
preconditioners provided  by PETSc.  HYPRE~\cite{Falgout06} is  a very efficient\r
preconditioner  based  on  structured   multigrid  and  element-based  algebraic\r
multigrid algorithms. In Table~\ref{tab:06} we report an experiment that show it\r
reduces  drastivally  the  number  of   iterations  but  sometimes  it  is  very\r
time-consuming compared  to other simpler  precondititioners. In this  table, we\r
can see that  for $512$ and $2,048$ cores, HYPRE  reduces drastically the number\r
of  iterations  for FGMRES  to  reach  the  convergence.   However, it  is  very\r
time-consuming compared  to TSIRM  and FGMRES with  the ASM  preconditioner. For\r
$4,096$ and $8,192$ cores, FGMRES with HYPRE did not converge in less than 1000s\r
where FGMRES and  TSIRM with the ASM  converge very quickly. Finally,  it can be\r
noticed that TSIRM is also faster than FGMRES and it requires less iterations.\r
\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|r|r|r|r|r|r|r|r|} \r
\hline\r
\r
  nb. cores   & \multicolumn{2}{c|}{FGMRES/ASM} & \multicolumn{2}{c|}{TSIRM CGLS/ASM} & gain& \multicolumn{2}{c|}{FGMRES/HYPRE}   \\ \r
\cline{2-5} \cline{7-8}\r
                    & Time  & \# Iter.  & Time  & \# Iter. &        & Time  & \# Iter.   \\\hline \hline\r
   512              & 5.54      & 685    & 2.5 &       570 & 2.21   & 128.9 & 9     \\\r
   2048             & 14.95     & 1,560  &  4.32 &     746 & 3.48   & 335.7 & 9 \\\r
   4096             & 25.13    & 2,369   & 5.61 &   859    & 4.48   & >1000  & -- \\\r
   8192             & 44.35   & 3,197   &  7.6  &  1,083    &  5.84  & >1000 &  --   \\\r
\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison of FGMRES  and TSIRM for ex45 of PETSc/KSP with two preconditioner (ASM and HYPRE)  having 5,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$,$\epsilon_{ls}=1e-40$),  time is expressed in seconds.}\r
\label{tab:06}\r
\end{center}\r
\end{table*}\r
\r
\r
\subsection{Parallel nonlinear problems}\r
\r
With  PETSc,  linear  solvers  are  used inside  nonlinear  solvers.   The  SNES\r
(Scalable Nonlinear  Equations Solvers) module  in PETSc implements easy  to use\r
methods,  like  Newton-type, quasi-Newton  or  full  approximation scheme  (FAS)\r
multigrid to  solve systems of  nonlinears equations.  As  SNES is based  on the\r
Krylov methods of PETSc, it is interesting to investigate if the TSIRM method is\r
also efficient  and scalable with non  linear problems. In PETSc,  some examples\r
are provided.  An important criteria is the scalability of the initial code with\r
classical solvers. Consequently, we have chosen  two of these examples: ex14 and\r
ex20.  In ex14, the code solves the  Bratu (SFI - solid fuel ignition) nonlinear\r
partial  difference equations  in 3  dimension.  In  ex20, the  code solves  a 3\r
dimension radiative transport test problem.  For more details on these examples,\r
interested readers are invited  to see the code in the  PETSc examples. For both\r
these  examples,   a  weak  scaling   case  is  chosen  where   processors  have\r
approximately a number of components equals to 100,000.\r
\r
In Table~\ref{tab:07}  we report the result  of our experiments for  the example\r
ex14 with the block Jacobi preconditioner.  For TSIRM the CGLS algorithm is used\r
to solve  the minimization step. In  this table, we  can see that the  number of\r
iterations used by the linear solver is smaller with TSIRM compared with FGMRES.\r
Consequently the execution times are smaller  with TSIRM. The gain between TSIRM\r
and FGMRES  is around  6 and  7. The parameters  of TSIRM  are expressed  in the\r
caption of the table.\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|r|r|r|r|r|r|} \r
\hline\r
\r
  nb. cores   & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain  \\ \r
\cline{2-5}\r
                    & Time         & \# Iter.  & Time   & \# Iter. &  \\\hline \hline\r
   1,024              & 159.52      & 11,584    &  26.34  &     1,563  &  6.06  \\\r
   2,048             & 226.24       & 16,459    &  37.23 &     2,248   &  6.08\\\r
   4,096             & 391.21     & 27,794   &  50.93 &   2,911  &  7.69\\\r
   8,192             & 543.23     & 37,770   &  79.21  &  4,324  & 6.86 \\\r
\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison of FGMRES  and TSIRM for ex14 of PETSc/SNES with a Block Jacobi  preconditioner  having 100,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}\r
\label{tab:07}\r
\end{center}\r
\end{table*}\r
\r
In Table~\ref{tab:08}, the results of the experiments with the example ex20 are\r
reported. The block  Jacobi preconditioner has also been used  and CGLS to solve\r
the minimization step for TSIRM. For this example, we can observ that the number\r
of  iterations  for  FMGRES  increase  drastically  when  the  number  of  cores\r
increases. With  TSIRM, we can  see that the  number of iterations  is initially\r
very small compared  to the FGMRES ones  and when the number  of cores increase,\r
the number  of iterations increases slighther  with TSIRM than with  FGMRES. For\r
this example,  the gain  between TSIRM  and FGMRES ranges  between 8  with 1,024\r
cores to more than 16 with 8,192 cores.\r
\r
\begin{table*}[htbp]\r
\begin{center}\r
\begin{tabular}{|r|r|r|r|r|r|} \r
\hline\r
\r
  nb. cores   & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain   \\ \r
\cline{2-5}\r
                    & Time         & \# Iter.  & Time   & \# Iter.  &  \\\hline \hline\r
   1,024              & 667.92      & 48,732    & 81.65  &     5,087 &  8.18 \\\r
   2,048             & 966.87       & 77,177    &  90.34 &     5,716 &  10.70\\\r
   4,096             & 1,742.31     & 124,411   &  119.21 &   6,905  & 14.61\\\r
   8,192             & 2,739.21     & 187,626   &  168.9  &  9,000   & 16.22\\\r
\r
\hline\r
\r
\end{tabular}\r
\caption{Comparison of FGMRES  and TSIRM for ex20 of PETSc/SNES with a Block Jacobi  preconditioner  having 100,000 components per core on Curie ($\epsilon_{tsirm}=1e-10$, $max\_iter_{kryl}=30$, $s=12$, $max\_iter_{ls}=15$, $\epsilon_{ls}=1e-40$),  time is expressed in seconds.}\r
\label{tab:08}\r
\end{center}\r
\end{table*}\r
\r
\r
\r
\r
\r
\r
\r
%%NEW\r
\subsection{Influence of parameters for TSIRM}\r
In this section we present some experimental results in order to study the influence of some parameters on the TSIRM algorithm which are: the method to solve the linear least-squares problem in the minimization process, the number of inner iterations $max\_iter_{kryl}$, and the size $s$ of matrix $AS$ (i.e. matrix $S$) of the least-squares problem. We conducted experiments on $16$ cores to solve linear and nonlinear problems of size $200,000$ components per core. We solved problems token from examples {\it ksp} and {\it snes} of PETSc~\cite{ksp,snes}. We fixed some parameters of the TSIRM algorithm as follows: the nonlinear systems are solved with a precision of $10^{-8}$, the tolerance threshold and the maximum number of iterations of TSIRM algorithm are $\epsilon_{tsirm}=10^{-10}$ and $max\_iter_{tsirm}=10,000$, the FGMRES method is used as the inner solver with a tolerance threshold $\epsilon_{kryl}=10^{-10}$, the additive Schwarz method (ASM) is used as a preconditioner, and the least-squares problem is solved with a precision $\epsilon_{ls}=10^{-40}$ in the minimization process.\r
\r
%time mpirun ../ex34 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -ksp_type tsirm -ksp_pc_type asm -pc_type ksp -ksp_tsirm_tol 1e-10 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 30 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 20 -ksp_tsirm_size_ls 10\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{ksp_tsirm_cgls}\r
\caption{Number of total iterations using two different methods for the minimization: CGLS and LSQR.}\r
\label{fig:cgls} \r
\end{figure}\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{ksp_ex12}\r
\caption{Total number of iterations in example {\it ksp ex12} of PETSc by varyin the number of inner iterations and the size of the least-squares problem.}\r
\label{fig:ksp_ex12} \r
\end{figure}\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{ksp_ex34}\r
\caption{Total number of iterations in example {\it ksp ex34} of PETSc by varyin the number of inner iterations and the size of the least-squares problem.}\r
\label{fig:ksp_ex34} \r
\end{figure}\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{snes_ex14}\r
\caption{Total number of iterations in example {\it snes ex14} of PETSc by varyin the number of inner iterations and the size of the least-squares problem.}\r
\label{fig:snes_ex14} \r
\end{figure}\r
\r
\begin{figure}[htbp]\r
\centering\r
  \includegraphics[width=0.5\textwidth]{snes_ex20}\r
\caption{Total number of iterations in example {\it snes ex20} of PETSc by varyin the number of inner iterations and the size of the least-squares problem.}\r
\label{fig:snes_ex20} \r
\end{figure}\r
\r
\r
\r
\r
\r
%%ENDNEW\r
\r
\r
\r
\r
\r
\subsection{Experiments conclusions }\r
\r
{\bf A refaire}\r
\r
Concerning the  experiments some  other remarks are  interesting.\r
\begin{itemize}\r
\item We have tested other examples  of PETSc/KSP (ex29, ex45, ex49).  For all these\r
  examples,  we have also  obtained similar  gains between  GMRES and  TSIRM but\r
  those  examples are  not scalable  with many  cores. In  general, we  had some\r
  problems with more than $4,096$ cores.\r
\item We have tested many iterative  solvers available in PETSc.  In fact, it is\r
  possible to use most of them with TSIRM. From our point of view, the condition\r
  to  use  a  solver inside  TSIRM  is  that  the  solver  must have  a  restart\r
  feature. More precisely,  the solver must support to  be stopped and restarted\r
  without decreasing its convergence. That is  why with GMRES we stop it when it\r
  is  naturally restarted (\emph{i.e.}   with $m$  the restart  parameter).  The\r
  Conjugate Gradient (CG) and all its variants do not have ``restarted'' version\r
  in PETSc,  so they are not efficient.   They will converge with  TSIRM but not\r
  quickly because  if we  compare a  normal CG with  a CG  which is  stopped and\r
  restarted every  16 iterations (for example),  the normal CG will  be far more\r
  efficient.   Some  restarted  CG or  CG  variant  versions  exist and  may  be\r
  interesting to study in future works.\r
\end{itemize}\r
\r
%%ENDNEW\r
\r
\r
%%%*********************************************************\r
%%%*********************************************************\r
\section{Conclusion}\r
\label{sec:06}\r
%The conclusion goes here. this is more of the conclusion\r
%%%*********************************************************\r
%%%*********************************************************\r
\r
%%NEW\r
In this paper a new two-stage algorithm TSIRM has been described. This method allows us to improve the convergence of  Krylov iterative  methods. It is based\r
on a least-squares minimization step which uses the  Krylov residuals.\r
\r
\r
We have implemented our code in PETSc in order to show that it is efficient and scalable. Some experiments with classical examples of PETSc for linear and nonlinear problems have been performed. We observed that TSIRM outperforms GMRES variants when the number of iterations is large. TSIRM is also scalable since we made some experiments with up to 16,394 cores.\r
\r
We also observed that TSIRM is efficient with different preconditioners. The hypre preconditioner that is globally very efficient for many problems is also very time consuming. Consequently, sometimes using a less performent preconditioners may be a better solution. In that case, TSIRM is also more efficient than traditional Krylov methods.\r
\r
{\bf A CHECKER !!}\r
The influence of some important parameters of TSIRM have been studied. It can be noticed that they have a strong influence on the convergence speed\r
\r
In future works, we plan to study other problems coming from different research areas. Other efficient Krylov optimisation methods as communication avoiding technique may be interesting to be investigated\r
%%ENDNEW\r
\r
\r
\r
% use section* for acknowledgement\r
%%%*********************************************************\r
%%%*********************************************************\r
\section*{Acknowledgment}\r
This  paper  is   partially  funded  by  the  Labex   ACTION  program  (contract\r
ANR-11-LABX-01-01).  We  acknowledge PRACE for  awarding us access  to resources\r
Curie and Juqueen respectively based in France and Germany.\r
\r
\r
\r
\r
\r
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
\bibliography{biblio}\r
\bibliographystyle{plain}\r
%\bibliographystyle{alpha}\r
\r
\end{document}\r