]> AND Private Git Repository - GMRES2stage.git/blobdiff - IJHPCN/paper.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ksp_ex34
[GMRES2stage.git] / IJHPCN / paper.tex
index 02ab9cfa0bcb286751452025f86f99dd9372d83f..2d0bd55e7f0f6607e8259b4a612a33110aec56bd 100644 (file)
@@ -366,41 +366,48 @@ in  practice.  As  explained  previously,  at  least  two  methods  seem  to  be
 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
@@ -409,8 +416,6 @@ little bit longer but it performs more or less the same operations.
 \section{Convergence results}\r
 \label{sec:04}\r
 \r
-%%NEW\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
@@ -599,16 +604,18 @@ with $|\mu|<1$. Furthermore, it is \emph{a priori} possible in some particular c
 regarding $A$, \r
 that the proposed TSIRM converges while the GMRES($m$) does not.\r
 \r
-%%ENDNEW\r
-\r
 \r
 %%%*********************************************************\r
 %%%*********************************************************\r
 \section{Experiments using PETSc}\r
 \label{sec:05}\r
 \r
-%%NEW\r
-In this section four kinds of experiments have been performed. First, some experiments on real matrices issued from the sparse matrix florida have been achieved out. Second, some experiments in parallel with some linear problems are reported and analyzed. Third, some experiments in parallèle with som nonlinear problems are illustrated. Finally some parameters of TSIRM are studied in order to understand their influences.\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
@@ -904,8 +911,20 @@ taken into account with TSIRM.
 \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
-{\bf example ex45/ksp à décrire et commenter en montrant que hypre est pourri avec cet exemple}\r
 \r
 \begin{table*}[htbp]\r
 \begin{center}\r
@@ -918,7 +937,7 @@ taken into account with TSIRM.
    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
@@ -975,7 +994,7 @@ caption of the table.
 \end{center}\r
 \end{table*}\r
 \r
-In Table~\cite{tab:08}, the results of the experiments with the example ex20 are\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
@@ -1016,80 +1035,23 @@ cores to more than 16 with 8,192 cores.
 \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
+%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[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
+  \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[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
+  \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
-%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
@@ -1164,7 +1126,7 @@ Curie and Juqueen respectively based in France and Germany.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
 \r
 \bibliography{biblio}\r
-\bibliographystyle{unsrt}\r
-\bibliographystyle{alpha}\r
+\bibliographystyle{plain}\r
+%\bibliographystyle{alpha}\r
 \r
 \end{document}\r