X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/blobdiff_plain/3f095ff7f3fff2553897be9e8dce25d2c3e9298f..82de9e14d2d33f6ed381b34feec71fa5b0964ad7:/IJHPCN/paper.tex diff --git a/IJHPCN/paper.tex b/IJHPCN/paper.tex index 999ce37..80a5a12 100644 --- a/IJHPCN/paper.tex +++ b/IJHPCN/paper.tex @@ -13,6 +13,8 @@ \usepackage{multirow} \usepackage{graphicx} \usepackage{url} +\usepackage{dsfont} + \def\newblock{\hskip .11em plus .33em minus .07em} @@ -407,57 +409,74 @@ little bit longer but it performs more or less the same operations. \section{Convergence results} \label{sec:04} +%%NEW + + +We suppose in this section that GMRES($m$) is used as solver in the TSIRM algorithm applied on a complex matrix $A$. +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)$. + +\subsection{$\mathfrak{R}(A)$ is positive} + +\begin{proposition} +\label{positiveConvergent} +If $\mathfrak{R}(A)$ is positive, then the TSIRM algorithm is convergent. +\end{proposition} + + +\begin{proof} +If $\mathfrak{R}(A)$ is positive, then even if $A$ is complex, it is possible to state that +the GMRES algorithm is convergent, see, \emph{e.g.},~\cite{Huang89}. In particular, its residual norm +decreases to zero. + +At each iterate of the TSIRM algorithm, either a GMRES iteration is realized or a least square +resolution (to find the minimum of $||b-Ax||_2$ is achieved on the linear span of the iterated approximation vectors +$span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$ +of the last GMRES stage, +where +$\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 \}$. + +Obviously, the minimum of $||b-Ax||_2$ on the set $span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)$ +is lower than or equal to $||b-Ax_k||_2$, which is the last obtained GMRES-residual norm. So we can +conclude that the intermediate stage of least square resolution inserted into the GMRES algorithm +does not break the decreasing to zero of the GMRES-residual norm. + +In other words, the TSIRM algorithm is convergent. +\end{proof} + -We can now claim that, +Regarding the convergence speed, we can claim that, \begin{proposition} \label{prop:saad} -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. +If $A$ is a positive matrix, then the convergence of the +TSIRM algorithm is linear. -Furthermore, let $r_k$ be the -$k$-th residue of TSIRM, then +Furthermore, let $r_k$ be the $k$-th residue of TSIRM, then we have the following boundaries: -\begin{itemize} -\item when $A$ is positive: \begin{equation} ||r_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0|| , \end{equation} -where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$; -\item when $A$ is positive definite: -\begin{equation} -\|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\|. -\end{equation} -\end{itemize} -%In the general case, where A is not positive definite, we have -%$\|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\|, .$ +where $M$ is the symmetric part of $A$, $\alpha = \lambda_{min}(M)^2$ and $\beta = \lambda_{max}(A^T A)$. \end{proposition} \begin{proof} -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: -\begin{equation*} -\|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\| . -\end{equation*} -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: +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: \begin{equation*} ||r_m|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{m}{2}} ||r_0|| , \end{equation*} -where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}, which proves -the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$. +where $\alpha$ and $\beta$ are defined as in Proposition~\ref{prop:saad}. These well-known results can be found, \emph{e.g.}, in~\cite{Saad86}. We will now prove by a mathematical induction that, for each $k \in \mathbb{N}^\ast$, -$||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_k|| \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{mk}{2}} ||r_0||$ when $A$ is positive. 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. -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. +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||$. We will show that the statement holds too for $r_k$. Two situations can occur: \begin{itemize} -\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. +\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||$. \item Else, the TSIRM algorithm consists in two stages: a first GMRES($m$) execution leads to a temporary $x_k$ whose residue satisfies: -\begin{itemize} -\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, -\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, -\end{itemize} +$$||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||$$ and a least squares resolution. 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,\\ $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$ @@ -469,20 +488,120 @@ $\begin{array}{ll} & \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\ & \leqslant ||b-Ax_{k}||_2\\ & = ||r_k||_2\\ -& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \textrm{ if $A$ is positive,}\\ -& \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}\\ -& \textrm{positive definite,} +& \leqslant \left(1-\dfrac{\alpha}{\beta}\right)^{\frac{km}{2}} ||r_0||, \\ \end{array}$ \end{itemize} which concludes the induction and the proof. \end{proof} + + +\subsection{$\mathfrak{R}(A)$ is positive definite} + +\begin{proposition} +\label{prop2} +Convergence of the TSIRM algorithm is at least linear when $\mathfrak{R}(A)$ is +positive definite. Furthermore, the rate of convergence is lower +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}}; +\left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ,$$ +where ${\lambda_{min}^{X}}$ (resp. ${\lambda_{max}^{X}}$) is the lowest (resp. largest) eigenvalue of matrix $X$. +\end{proposition} + + +\begin{proof} +If $\mathfrak{R}(A)$ is positive definite, then it is positive, and so the TSIRM algorithm +is convergent due to Proposition~\ref{positiveConvergent}. + +Furthermore, as stated in the proof of Proposition~\ref{positiveConvergent}, the GMRES residue is under control +when $\mathfrak{R}(A)$ is positive. More precisely, it has been proven in the literature that the residual norm +provided at the $m$-th step of GMRES satisfies: +\begin{enumerate} +\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}, +\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}, +\end{enumerate} +which proves the convergence of GMRES($m$) for all $m$ under such assumptions regarding $A$. + +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 +\begin{equation} +\label{induc} +\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{m}{2}}; \right. \\ +& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) ||r_0|| +\end{array} +\end{equation} +when $A$ is positive definite. + + +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. + +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||$. +We will show that the statement holds too for $r_k$. Two situations can occur: +\begin{itemize} +\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_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 +$$\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. \\ +& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| +\end{array}.$$ + +\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: +$$\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{m}{2}}; \right. \\ +& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{m}{2}}\right) \times ||r_{k-1}||\\ + & \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. \\ +& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| +\end{array}$$ +and the least squares resolution of $\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2$. + +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,\\ +$\min_{\alpha \in \mathbb{R}^s} ||b-R\alpha ||_2 = \min_{\alpha \in \mathbb{R}^s} ||b-AS\alpha ||_2$ + +$\begin{array}{ll} +& = \min_{x \in span\left(S_{k-s+1}, S_{k-s+2}, \hdots, S_{k} \right)} ||b-AS\alpha ||_2\\ +& = \min_{x \in span\left(x_{k-s+1}, x_{k-s}+2, \hdots, x_{k} \right)} ||b-AS\alpha ||_2\\ +& \leqslant \min_{x \in span\left( x_{k} \right)} ||b-Ax ||_2\\ +& \leqslant \min_{\lambda \in \mathbb{R}} ||b-\lambda Ax_{k} ||_2\\ +& \leqslant ||b-Ax_{k}||_2\\ +& = ||r_k||_2\\ +& \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. \\ +& \left. \left(1-\dfrac{{\lambda_{min}^{\mathfrak{R}(A)}}^2}{||A||^2}\right)^{\frac{mk}{2}}\right) \times ||r_0|| +\end{array} .$ +\end{itemize} +due to the inductive hypothesis. +So the statement of Equation~\eqref{induc} holds too for the $k$-th iterate, which concludes the induction and the proof. +\end{proof} + +\subsection{A last linear convergence} + + +\begin{proposition} +Let us define the field of values of $A$ by +$$\mathfrak{F}(A) = \left\{ \dfrac{x^\ast A x}{x^\ast x}, x \in \mathds{C}^n\setminus \{0\} \right\} .$$ + +Then if $\mathfrak{F}(A)$ is included into a closed ball of radius $r$ and center $c$, +which does not contain the origin, then the convergence of the TSIRM algorithm is at least linear. + +More precisely, the rate of convergence is lower +than $2 \dfrac{r}{|c|}$. +\end{proposition} + +\begin{proof} +This inequality comes from the fact that, in the conditions of the proposition, the GMRES residue +satisfies the inequality: $|r_k| \leqslant 2 \dfrac{r}{|c|}^k |r_0|$. An induction inspired by +the proofs of Propositions~\ref{prop:saad} and~\ref{prop2} can transfer this inequality to the +TSIRM residue. +\end{proof} + + + Remark that a similar proposition can be formulated at each time the given solver satisfies an inequality of the form $||r_n|| \leqslant \mu^n ||r_0||$, with $|\mu|<1$. Furthermore, it is \emph{a priori} possible in some particular cases regarding $A$, that the proposed TSIRM converges while the GMRES($m$) does not. +%%ENDNEW + + %%%********************************************************* %%%********************************************************* \section{Experiments using PETSc} @@ -786,6 +905,30 @@ taken into account with TSIRM. %%NEW +{\bf example ex45/ksp à décrire et commenter en montrant que hypre est pourri avec cet exemple} + +\begin{table*}[htbp] +\begin{center} +\begin{tabular}{|r|r|r|r|r|r|r|r|} +\hline + + nb. cores & \multicolumn{2}{c|}{FGMRES/ASM} & \multicolumn{2}{c|}{TSIRM CGLS/ASM} & gain& \multicolumn{2}{c|}{FGMRES/HYPRE} \\ +\cline{2-5} \cline{7-8} + & Time & \# Iter. & Time & \# Iter. & & Time & \# Iter. \\\hline \hline + 512 & 5.54 & 685 & 2.5 & 570 & 2.21 & 128.9 & 9 \\ + 2048 & 14.95 & 1,560 & 4.32 & 746 & 3.48 & 335.7 & 9 \\ + 4096 & 25.13 & 2,369 & 5.61 & 859 & 4.48 & >1000 & -- \\ + 8192 & 44.35 & 3,197 & 7.6 & 1083 & 5.84 & >1000 & -- \\ + +\hline + +\end{tabular} +\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.} +\label{tab:06} +\end{center} +\end{table*} + + \subsection{Parallel nonlinear problems} With PETSc, linear solvers are used inside nonlinear solvers. The SNES @@ -799,10 +942,17 @@ classical solvers. Consequently, we have chosen two of these examples: ex14 and ex20. In ex14, the code solves the Bratu (SFI - solid fuel ignition) nonlinear partial difference equations in 3 dimension. In ex20, the code solves a 3 dimension radiative transport test problem. For more details on these examples, -interested readers are invited to see the code in the PETSc examples. - -In Table~\ref{tab:07} we report the result of our experiments for the example -ex14. +interested readers are invited to see the code in the PETSc examples. For both +these examples, a weak scaling case is chosen where processors have +approximately a number of components equals to 100,000. + +In Table~\ref{tab:07} we report the result of our experiments for the example +ex14 with the block Jacobi preconditioner. For TSIRM the CGLS algorithm is used +to solve the minimization step. In this table, we can see that the number of +iterations used by the linear solver is smaller with TSIRM compared with FGMRES. +Consequently the execution times are smaller with TSIRM. The gain between TSIRM +and FGMRES is around 6 and 7. The parameters of TSIRM are expressed in the +caption of the table. \begin{table*}[htbp] \begin{center} @@ -812,10 +962,10 @@ ex14. nb. cores & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain \\ \cline{2-5} & Time & \# Iter. & Time & \# Iter. & \\\hline \hline - 1024 & 159.52 & 11,584 & 26.34 & 1,563 & 6.06 \\ - 2048 & 226.24 & 16,459 & 37.23 & 2,248 & 6.08\\ - 4096 & 391.21 & 27,794 & 50.93 & 2,911 & 7.69\\ - 8192 & 543.23 & 37,770 & 79.21 & 4,324 & 6.86 \\ + 1,024 & 159.52 & 11,584 & 26.34 & 1,563 & 6.06 \\ + 2,048 & 226.24 & 16,459 & 37.23 & 2,248 & 6.08\\ + 4,096 & 391.21 & 27,794 & 50.93 & 2,911 & 7.69\\ + 8,192 & 543.23 & 37,770 & 79.21 & 4,324 & 6.86 \\ \hline @@ -825,6 +975,15 @@ ex14. \end{center} \end{table*} +In Table~\cite{tab:08}, the results of the experiments with the example ex20 are +reported. The block Jacobi preconditioner has also been used and CGLS to solve +the minimization step for TSIRM. For this example, we can observ that the number +of iterations for FMGRES increase drastically when the number of cores +increases. With TSIRM, we can see that the number of iterations is initially +very small compared to the FGMRES ones and when the number of cores increase, +the number of iterations increases slighther with TSIRM than with FGMRES. For +this example, the gain between TSIRM and FGMRES ranges between 8 with 1,024 +cores to more than 16 with 8,192 cores. \begin{table*}[htbp] \begin{center} @@ -834,10 +993,10 @@ ex14. nb. cores & \multicolumn{2}{c|}{FGMRES/BJAC} & \multicolumn{2}{c|}{TSIRM CGLS/BJAC} & gain \\ \cline{2-5} & Time & \# Iter. & Time & \# Iter. & \\\hline \hline - 1024 & 667.92 & 48,732 & 81.65 & 5,087 & 8.18 \\ - 2048 & 966.87 & 77,177 & 90.34 & 5,716 & 10.70\\ - 4096 & 1,742.31 & 124,411 & 119.21 & 6,905 & 14.61\\ - 8192 & 2,739.21 & 187,626 & 168.9 & 9,000 & 16.22\\ + 1,024 & 667.92 & 48,732 & 81.65 & 5,087 & 8.18 \\ + 2,048 & 966.87 & 77,177 & 90.34 & 5,716 & 10.70\\ + 4,096 & 1,742.31 & 124,411 & 119.21 & 6,905 & 14.61\\ + 8,192 & 2,739.21 & 187,626 & 168.9 & 9,000 & 16.22\\ \hline @@ -850,7 +1009,89 @@ ex14. + + + +%%NEW \subsection{Influence of parameters for TSIRM} +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. + +%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 +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_cgls_iter_total} +\caption{Number of total iterations using two different methods for the minimization: LSQR and CGLS.} +\label{fig:cgls-iter} +\end{figure} + +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_cgls_time} +\caption{Execution time in seconds using two different methods for the minimization: LSQR and CGLS.} +\label{fig:cgls-time} +\end{figure} + +%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 +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_inner_restarts_iter_total} +\caption{Number of total iterations with variation of restarts in the inner solver FGMRES.} +\label{fig:inner_restarts_iter_total} +\end{figure} + +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_inner_restarts_time} +\caption{Execution time in seconds with variation of restarts in the inner solver FGMRES.} +\label{fig:inner_restarts_time} +\end{figure} + +%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 +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_max_inner_iter} +\caption{Number of total iterations with variation of number of inner iterations.} +\label{fig:max_inner_iter} +\end{figure} + +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_max_inner_time} +\caption{Execution time in seconds with variation of number of inner iterations.} +\label{fig:max_inner_time} +\end{figure} + +%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 +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_maxiter_ls_iter} +\caption{Number of total iterations with variation of number of iterations in the minimization process.} +\label{fig:maxiter_ls_iter} +\end{figure} + +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_maxiter_ls_time} +\caption{Execution time in seconds with variation of number of iterations in the minimization process.} +\label{fig:maxiter_ls_time} +\end{figure} + +%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 +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_size_ls_iter} +\caption{Number of total iterations with variation of the size of the least-squares problem in the minimization process.} +\label{fig:size_ls_iter} +\end{figure} + +\begin{figure}[htbp] +\centering + \includegraphics[angle=-90,width=0.5\textwidth]{ksp_tsirm_size_ls_time} +\caption{Execution time in seconds with variation of the size of the least-squares problem in the minimization process.} +\label{fig:size_ls_time} +\end{figure} + +%%ENDNEW @@ -923,7 +1164,7 @@ Curie and Juqueen respectively based in France and Germany. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliography{biblio} -\bibliographystyle{unsrt} -\bibliographystyle{alpha} +\bibliographystyle{plain} +%\bibliographystyle{alpha} \end{document}