\usepackage{multirow}\r
\usepackage{graphicx}\r
\usepackage{url}\r
+\usepackage{dsfont}\r
+\r
\r
\def\newblock{\hskip .11em plus .33em minus .07em}\r
\r
\makeatletter\r
\def\theequation{\arabic{equation}}\r
\r
-%\JOURNALNAME{\TEN{\it Int. J. System Control and Information\r
-%Processing,\r
-%Vol. \theVOL, No. \theISSUE, \thePUBYEAR\hfill\thepage}}%\r
+\JOURNALNAME{\TEN{\it International Journal of High Performance Computing and Networking}}\r
%\r
%\def\BottomCatch{%\r
%\vskip -10pt\r
\r
\setcounter{page}{1}\r
\r
-\LRH{F. Wang et~al.}\r
+\LRH{R. Couturier, L. Ziane Khodja and C. Guyeux}\r
\r
-\RRH{Metadata Based Management and Sharing of Distributed Biomedical\r
-Data}\r
+\RRH{TSIRM: A Two-Stage Iteration with least-squares Residual Minimization algorithm}\r
\r
\VOL{x}\r
\r
\r
\BottomCatch\r
\r
-\PUBYEAR{2012}\r
+\PUBYEAR{2015}\r
\r
\subtitle{}\r
\r
\r
\r
\begin{abstract}\r
-In this article, a two-stage iterative algorithm is proposed to improve the\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
+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. Experiments using up to 16,394 cores\r
-also show that the proposed algorithm runs around 5 or 7 times faster than\r
-GMRES.\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
%Semantics and Ontologies}, Vol. x, No. x, pp.xxx\textendash xxx.}\r
\r
\begin{bio}\r
-Manuel Pedro Rodr\'iguez Bol\'ivar received his PhD in Accounting at\r
-the University of Granada. He is a Lecturer at the Department of\r
-Accounting and Finance, University of Granada. His research\r
-interests include issues related to conceptual frameworks of\r
-accounting, diffusion of financial information on Internet, Balanced\r
-Scorecard applications and environmental accounting. He is author of\r
-a great deal of research studies published at national and\r
-international journals, conference proceedings as well as book\r
-chapters, one of which has been edited by Kluwer Academic\r
-Publishers.\vs{9}\r
-\r
-\noindent Bel\'en Sen\'es Garc\'ia received her PhD in Accounting at\r
-the University of Granada. She is a Lecturer at the Department of\r
-Accounting and Finance, University of Granada. Her research\r
-interests are related to cultural, institutional and historic\r
-accounting and in environmental accounting. She has published\r
-research papers at national and international journals, conference\r
-proceedings as well as chapters of books.\vs{8}\r
-\r
-\noindent Both authors have published a book about environmental\r
-accounting edited by the Institute of Accounting and Auditing,\r
-Ministry of Economic Affairs, in Spain in October 2003.\r
+Raphaël Couturier ....\r
+\r
+\noindent Lilia Ziane Khodja ...\r
+\r
+\noindent Christophe Guyeux ...\r
\end{bio}\r
\r
\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
+%% 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
-In each iteration of CGLS, there are two matrix-vector multiplications and some\r
-classical operations: dot product, norm, multiplication, and addition on\r
-vectors. All these operations are easy to implement in PETSc or similar\r
-environment. It should be noticed that LSQR follows the same principle, it is a\r
-little bit longer but it performs more or less the same operations.\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
\label{sec:04}\r
\r
\r
-We can now claim that,\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 either a definite positive or a positive matrix and GMRES($m$) is used as a solver, then the TSIRM algorithm is convergent. \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\r
-$k$-th residue of TSIRM, then\r
+Furthermore, let $r_k$ be the $k$-th residue of TSIRM, then\r
we have the following boundaries:\r
-\begin{itemize}\r
-\item when $A$ is positive:\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
-\item when $A$ is positive definite:\r
-\begin{equation}\r
-\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|.\r
-\end{equation}\r
-\end{itemize}\r
-%In the general case, where A is not positive definite, we have\r
-%$\|r_n\| \le \inf_{p \in P_n} \|p(A)\| \le \kappa_2(V) \inf_{p \in P_n} \max_{\lambda \in \sigma(A)} |p(\lambda)| \|r_0\|, .$\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 the residue is under control when considering the GMRES algorithm on a positive definite matrix, and it is bounded as follows:\r
-\begin{equation*}\r
-\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{k/2} \|r_0\| .\r
-\end{equation*}\r
-Additionally, 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
+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}, which proves \r
-the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$.\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, and $\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|$ when $A$ is positive definite.\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||$ in the positive case, and $\|r_k\| \leq \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_0\|$ in the definite positive one.\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||$ if $A$ is positive, or $\|r_k\| \leqslant \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{m/2} \|r_{k-1}\|$ $\leqslant$ $\left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_{0}\|$ in the positive definite case.\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
-\begin{itemize}\r
-\item $||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||$ in the positive case, \r
-\item $\|r_k\| \leqslant \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{m/2} \|r_{k-1}\|$ $\leqslant$ $\left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_{0}\|$ in the positive definite one,\r
-\end{itemize}\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
& \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||, \textrm{ if $A$ is positive,}\\\r
-& \leqslant \left( 1-\frac{\lambda_{\mathrm{min}}^2(1/2(A^T + A))}{ \lambda_{\mathrm{max}}(A^T A)} \right)^{km/2} \|r_{0}\|, \textrm{ if $A$ is}\\\r
-& \textrm{positive definite,} \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
\end{table*}\r
\r
\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
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
+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
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
+ 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
+\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
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
+ 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
\end{figure}\r
\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
-%%%*********************************************************\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
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 & 1083 & 5.84 & >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 25,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
+\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
-\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
+\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
+ 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
- 1024 & 667.92 & 48,732 & 81.65 & 5,087 & 8.18 \\\r
- 2048 & 966.87 & 77,177 & 90.34 & 5,716 & 10.70\\\r
- 4096 & 1,742.31 & 124,411 & 119.21 & 6,905 & 14.61\\\r
- 8192 & 2,739.21 & 187,626 & 168.9 & 9,000 & 16.22\\\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 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
+\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
+ 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
- 1024 & 159.52 & 11,584 & 26.34 & 1,563 & 6.06 \\\r
- 2048 & 226.24 & 16,459 & 37.23 & 2,248 & 6.08\\\r
- 4096 & 391.21 & 27,794 & 50.93 & 2,911 & 7.69\\\r
- 8192 & 543.23 & 37,770 & 79.21 & 4,324 & 6.86 \\\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 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
+\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. We conducted experiments on $16$ cores to solve 3D problems of size $200,000$ components per core. We solved nonlinear problems token from examples of PETSc. We fixed some parameters of the TSIRM algorithm as follows: the nonlinear systems are solved with a precision of $10^{-8}$, block Jacobi preconditioner is used, the tolerance threshold $\epsilon_{tsirm}$ is $10^{-8}$ , the maximum number of iterations $max\_iter_{tsirm}$ is set to $10,000$ iterations, the FGMRES method is used as the inner solver with a tolerance threshold $\epsilon_{kryl}=10^{-10}$ and the least-squares problem is solved with a precision $\epsilon_{ls}=10^{-40}$ in the minimization process.\r
+\r
+%time mpirun ../ex48 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -snes_rtol 1.e-8 -snes_monitor -ksp_type tsirm -ksp_pc_type bjacobi -pc_type ksp -ksp_tsirm_tol 1e-8 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 30 -ksp_tsirm_inner_restarts 30 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 15 -ksp_tsirm_size_ls 10 \r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_cgls_iter_total}\r
+\caption{Number of total iterations using two different methods for the minimization: LSQR and CGLS.}\r
+\label{fig:cgls-iter} \r
+\end{figure}\r
+\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_cgls_time}\r
+\caption{Execution time in seconds using two different methods for the minimization: LSQR and CGLS.}\r
+\label{fig:cgls-time} \r
+\end{figure}\r
+\r
+%time mpirun ../ex35 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -snes_rtol 1.e-8 -snes_monitor -ksp_type tsirm -ksp_pc_type bjacobi -pc_type ksp -ksp_tsirm_tol 1e-8 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 30 -ksp_tsirm_inner_restarts 38 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 15 -ksp_tsirm_size_ls 10\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_inner_restarts_iter_total}\r
+\caption{Number of total iterations with variation of restarts in the inner solver FGMRES.}\r
+\label{fig:inner_restarts_iter_total} \r
+\end{figure}\r
+\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_inner_restarts_time}\r
+\caption{Execution time in seconds with variation of restarts in the inner solver FGMRES.}\r
+\label{fig:inner_restarts_time} \r
+\end{figure}\r
+\r
+%time mpirun ../ex14 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -snes_rtol 1.e-8 -snes_monitor -ksp_type tsirm -ksp_pc_type bjacobi -pc_type ksp -ksp_tsirm_tol 1e-8 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 1000 -ksp_tsirm_inner_restarts 30 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 15 -ksp_tsirm_size_ls 10\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_max_inner_iter}\r
+\caption{Number of total iterations with variation of number of inner iterations.}\r
+\label{fig:max_inner_iter} \r
+\end{figure}\r
+\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_max_inner_time}\r
+\caption{Execution time in seconds with variation of number of inner iterations.}\r
+\label{fig:max_inner_time} \r
+\end{figure}\r
+\r
+%time mpirun ../ex14 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -snes_rtol 1.e-8 -snes_monitor -ksp_type tsirm -ksp_pc_type bjacobi -pc_type ksp -ksp_tsirm_tol 1e-8 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 30 -ksp_tsirm_inner_restarts 30 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 5 -ksp_tsirm_size_ls 10\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_maxiter_ls_iter}\r
+\caption{Number of total iterations with variation of number of iterations in the minimization process.}\r
+\label{fig:maxiter_ls_iter} \r
+\end{figure}\r
+\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_maxiter_ls_time}\r
+\caption{Execution time in seconds with variation of number of iterations in the minimization process.}\r
+\label{fig:maxiter_ls_time} \r
+\end{figure}\r
+\r
+%time mpirun ../ex14 -da_grid_x 147 -da_grid_y 147 -da_grid_z 147 -snes_rtol 1.e-8 -snes_monitor -ksp_type tsirm -ksp_pc_type bjacobi -pc_type ksp -ksp_tsirm_tol 1e-8 -ksp_tsirm_maxiter 10000 -ksp_ksp_type fgmres -ksp_tsirm_max_inner_iter 30 -ksp_tsirm_inner_restarts 30 -ksp_tsirm_inner_tol 1e-10 -ksp_tsirm_cgls 0 -ksp_tsirm_tol_ls 1.e-40 -ksp_tsirm_maxiter_ls 15 -ksp_tsirm_size_ls 2\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_size_ls_iter}\r
+\caption{Number of total iterations with variation of the size of the least-squares problem in the minimization process.}\r
+\label{fig:size_ls_iter} \r
+\end{figure}\r
+\r
+\begin{figure}[htbp]\r
+\centering\r
+ \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_size_ls_time}\r
+\caption{Execution time in seconds with variation of the size of the least-squares problem in the minimization process.}\r
+\label{fig:size_ls_time} \r
+\end{figure}\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
%%%*********************************************************\r
%%%*********************************************************\r
\r
-A new two-stage iterative algorithm TSIRM has been proposed in this article,\r
-in order to accelerate the convergence of Krylov iterative methods.\r
-Our TSIRM proposal acts as a merger between Krylov based solvers and\r
-a least-squares minimization step.\r
-The convergence of the method has been proven in some situations, while \r
-experiments up to 16,394 cores have been led to verify that TSIRM runs\r
-5 or 7 times faster than GMRES.\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
-For future work, the authors' intention is to investigate other kinds of\r
-matrices, problems, and inner solvers. In particular, the possibility \r
-to obtain a convergence of TSIRM in situations where the GMRES is divergent will be\r
-investigated. The influence of all parameters must be\r
-tested too, while other methods to minimize the residuals must be regarded. The\r
-number of outer iterations to minimize should become adaptive to improve the\r
-overall performances of the proposal. Finally, this solver will be implemented\r
-inside PETSc, which would be of interest as it would allows us to test\r
-all the non-linear examples and compare our algorithm with the other algorithm\r
-implemented in PETSc.\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
-% conference papers do not normally have an appendix\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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
\r
\bibliography{biblio}\r
-\bibliographystyle{unsrt}\r
-\bibliographystyle{alpha}\r
+\bibliographystyle{plain}\r
+%\bibliographystyle{alpha}\r
\r
\end{document}\r
