X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/GMRES2stage.git/blobdiff_plain/aeb5859d1996432c60c4346b9f961298caa11f5a..6857ecf2cdc87f1eec0618e8f148dae094224933:/paper.tex diff --git a/paper.tex b/paper.tex index b1c6f59..8bb4dc3 100644 --- a/paper.tex +++ b/paper.tex @@ -431,9 +431,9 @@ convergence of Krylov iterative methods, typically those of GMRES variants. The principle of our approach is to build an external iteration over the Krylov method and to save the current residual frequently (for example, for each restart of GMRES). Then after a given number of outer iterations, a minimization -step is applied on the matrix composed of the save residuals in order to compute -a better solution and make a new iteration if necessary. We prove that our -method has the same convergence property than the inner method used. Some +step is applied on the matrix composed of the saved residuals in order to +compute a better solution and make a new iteration if necessary. We prove that +our method has the same convergence property than the inner method used. Some experiments using up to 16,394 cores show that compared to GMRES our algorithm can be around 7 times faster. \end{abstract} @@ -583,8 +583,7 @@ performances. The present paper is organized as follows. In Section~\ref{sec:02} some related works are presented. Section~\ref{sec:03} presents our two-stage algorithm using a least-square residual minimization. Section~\ref{sec:04} describes some -convergence results on this method. In Section~\ref{sec:05}, parallization -details of TSARM are given. Section~\ref{sec:06} shows some experimental +convergence results on this method. Section~\ref{sec:05} shows some experimental results obtained on large clusters of our algorithm using routines of PETSc toolkit. Finally Section~\ref{sec:06} concludes and gives some perspectives. %%%********************************************************* @@ -680,18 +679,6 @@ To summarize, the important parameters of TSARM are: \item $\epsilon_{ls}$ the threshold to stop the least-square method \end{itemize} -%%%********************************************************* -%%%********************************************************* - -\section{Convergence results} -\label{sec:04} - - - -%%%********************************************************* -%%%********************************************************* -\section{Parallelization} -\label{sec:05} The parallelisation of TSARM relies on the parallelization of all its parts. More precisely, except the least-square step, all the other parts are @@ -733,10 +720,21 @@ In each iteration of CGLS, there is two matrix-vector multiplications and some classical operations: dots, norm, multiplication and addition on vectors. All these operations are easy to implement in PETSc or similar environment. + + +%%%********************************************************* +%%%********************************************************* + +\section{Convergence results} +\label{sec:04} + + + + %%%********************************************************* %%%********************************************************* \section{Experiments using petsc} -\label{sec:06} +\label{sec:05} In order to see the influence of our algorithm with only one processor, we first @@ -793,7 +791,7 @@ minimization. \begin{tabular}{|c|c|r|r|r|r|} \hline - \multirow{2}{*}{Matrix name} & Solver / & \multicolumn{2}{c|}{gmres variant} & \multicolumn{2}{c|}{2 stage CGLS} \\ + \multirow{2}{*}{Matrix name} & Solver / & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSARM CGLS} \\ \cline{3-6} & precond & Time & \# Iter. & Time & \# Iter. \\\hline \hline @@ -814,16 +812,29 @@ torso3 & fgmres / sor & 37.70 & 565 & 34.97 & 510 \\ -Larger experiments ....\\ -Describe the problems ex15 and ex54 +In the following we describe the applications of PETSc we have experimented. Those applications are available in the ksp part which is suited for scalable linear equations solvers: +\begin{itemize} +\item ex15 is an example which solves in parallel an operator using a finite difference scheme. The diagonal is equals to 4 and 4 + extra-diagonals representing the neighbors in each directions is equal to + -1. This example is used in many physical phenomena , for exemple, heat and + fluid flow, wave propagation... +\item ex54 is another example based on 2D problem discretized with quadrilateral finite elements. For this example, the user can define the scaling of material coefficient in embedded circle, it is called $\alpha$. +\end{itemize} +For more technical details on these applications, interested reader are invited +to read the codes available in the PETSc sources. Those problem have been +chosen because they are scalable with many cores. We have tested other problem +but they are not scalable with many cores. + + + \begin{table*} \begin{center} \begin{tabular}{|r|r|r|r|r|r|r|r|r|} \hline - nb. cores & precond & \multicolumn{2}{c|}{gmres variant} & \multicolumn{2}{c|}{2 stage CGLS} & \multicolumn{2}{c|}{2 stage LSQR} & best gain \\ + nb. cores & precond & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSARM CGLS} & \multicolumn{2}{c|}{TSARM LSQR} & best gain \\ \cline{3-8} & & Time & \# Iter. & Time & \# Iter. & Time & \# Iter. & \\\hline \hline 2,048 & mg & 403.49 & 18,210 & 73.89 & 3,060 & 77.84 & 3,270 & 5.46 \\ @@ -848,7 +859,7 @@ Describe the problems ex15 and ex54 \begin{tabular}{|r|r|r|r|r|r|r|r|r|} \hline - nb. cores & threshold & \multicolumn{2}{c|}{gmres variant} & \multicolumn{2}{c|}{2 stage CGLS} & \multicolumn{2}{c|}{2 stage LSQR} & best gain \\ + nb. cores & threshold & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSARM CGLS} & \multicolumn{2}{c|}{TSARM LSQR} & best gain \\ \cline{3-8} & & Time & \# Iter. & Time & \# Iter. & Time & \# Iter. & \\\hline \hline 2,048 & 8e-5 & 108.88 & 16,560 & 23.06 & 3,630 & 22.79 & 3,630 & 4.77 \\ @@ -856,7 +867,7 @@ Describe the problems ex15 and ex54 4,096 & 7e-5 & 160.59 & 22,530 & 35.15 & 5,130 & 29.21 & 4,350 & 5.49 \\ 4,096 & 6e-5 & 249.27 & 35,520 & 52.13 & 7,950 & 39.24 & 5,790 & 6.35 \\ 8,192 & 6e-5 & 149.54 & 17,280 & 28.68 & 3,810 & 29.05 & 3,990 & 5.21 \\ - 8,192 & 5e-5 & 792.11 & 109,590 & 76.83 & 10,470 & 65.20 & 9,030 & 12.14 \\ + 8,192 & 5e-5 & 785.04 & 109,590 & 76.07 & 10,470 & 69.42 & 9,030 & 11.30 \\ 16,384 & 4e-5 & 718.61 & 86,400 & 98.98 & 10,830 & 131.86 & 14,790 & 7.26 \\ \hline @@ -872,17 +883,17 @@ Describe the problems ex15 and ex54 \begin{table*} \begin{center} -\begin{tabular}{|r|r|r|r|r|r|r|r|} +\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} \hline - nb. cores & \multicolumn{2}{c|}{gmres variant} & \multicolumn{2}{c|}{2 stage CGLS} & \multicolumn{2}{c|}{2 stage LSQR} & best gain \\ -\cline{2-7} - & Time & \# Iter. & Time & \# Iter. & Time & \# Iter. & \\\hline \hline - 512 & 3,969.69 & 33,120 & 709.57 & 5,790 & 622.76 & 5,070 & \\ - 1024 & 1,530.06 & 25,860 & 290.95 & 4,830 & 307.71 & 5,070 & \\ - 2048 & 919.62 & 31,470 & 237,52 & 8,040 & 194.22 & 6,510 & \\ - 4096 & 405.60 & 28,380 & 111.67 & 7,590 & 91.72 & 6,510 & \\ - 8192 & 785.04 & 109,590 & 76.07 & 10,470 & 69,42 & 9,030 & \\ + nb. cores & \multicolumn{2}{c|}{GMRES} & \multicolumn{2}{c|}{TSARM CGLS} & \multicolumn{2}{c|}{TSARM LSQR} & best gain & \multicolumn{3}{c|}{efficiency} \\ +\cline{2-7} \cline{9-11} + & Time & \# Iter. & Time & \# Iter. & Time & \# Iter. & & GMRES & TS CGLS & TS LSQR\\\hline \hline + 512 & 3,969.69 & 33,120 & 709.57 & 5,790 & 622.76 & 5,070 & 6.37 & 1 & 1 & 1 \\ + 1024 & 1,530.06 & 25,860 & 290.95 & 4,830 & 307.71 & 5,070 & 5.25 & 1.30 & 1.21 & 1.01 \\ + 2048 & 919.62 & 31,470 & 237.52 & 8,040 & 194.22 & 6,510 & 4.73 & 1.08 & .75 & .80\\ + 4096 & 405.60 & 28,380 & 111.67 & 7,590 & 91.72 & 6,510 & 4.42 & 1.22 & .79 & .84 \\ + 8192 & 785.04 & 109,590 & 76.07 & 10,470 & 69.42 & 9,030 & 11.30 & .32 & .58 & .56 \\ \hline @@ -900,7 +911,7 @@ Describe the problems ex15 and ex54 %%%********************************************************* %%%********************************************************* \section{Conclusion} -\label{sec:07} +\label{sec:06} %The conclusion goes here. this is more of the conclusion %%%********************************************************* %%%*********************************************************