Research topic: parallel sparse linear solvers
Scientific context
In many scientific applications, the core operation is solving a sparse
linear system Ax=b, where A is a large sparse square matrix. Krylov
iterative methods are
commonly used as sparse solvers and among them, CG is the method of
choice for symmetric positive definite matrices, whereas BICGSTAB or
GMRES
methods are a frequent choice for the nonsymmetric case. They must be
used with a preconditioner in order to reduce the
number of iterations. Members of the team SAGE have been working for
many years on parallel versions of CG and GMRES and on efficient
parallel
preconditioners.
Research subtopic: preconditioned Conjugate Gradient
Algorithm description
DEFCG starts with an initial guess such that the residual is orthogonal
to some basis of a small subspace. Then deflation is added at each
iteration in order to keep the orthogonality. Deflation can be combined with preconditioners.
Software description
SIDNUR implements DEFCG in combination with a Schur domain
decomposition method. Here deflation is equivalent to a so-called
balancing approach (BDD method).
Objectives and projects
The SIDNUR approach is used for solving systems arising from groundwater flow simulation in fractured and porous media.
Publications about Deflated CG and parallel CG
- J. Erhel and F. Guyomarc'h.
An Augmented Conjugate Gradient Method for solving consecutive symmetric positive definite systems.
SIAM Journal on Matrix Analysis and Applications , Volume 21, no. 4, pp. 1279-1299, 2000.
- Y. Saad, M. Yeung, J. Erhel, and F. Guyomarc'h.
A deflated version of the Conjugate Gradient Algorithm.
SIAM Journal on Scientific Computing, Volume 21, no. 5 pp.1909-1926, 2000.
- F. Guyomarc'h
Méthodes de Krylov : régularisation de la solution et accélération de la convergence.
Ph-D thesis, University of Rennes 1, 2000.
- M-O. Bristeau, J. Erhel.
Augmented Conjugate Gradient. Application in an iterative process for the solution of scattering problems.
Numerical Algorithms, 18, pp. 71-90, 1998.
- M.O. Bristeau and P. Féat and J. Erhel and R. Glowinski and J. Périaux.
Solving the Helmholtz equation at high wave numbers on a parallel computer with a shared virtual memory.
International Journal of Supercomputer Applications and High Performance Computing, Volume 9, pp.18-28, 1995.
Publications about Balanced Domain Decomposition (deflated Schur method)
Applications to groundwater flow
- de Dreuzy, J.-R.; Pichot, G.; Poirriez, B. and Erhel, J.
Synthetic benchmark for modeling flow in 3D fractured media
Computers & Geosciences, 50, 59-71, 2013
- Pichot, G.; Poirriez, B.; Erhel, J. & de Dreuzy, J.-R.
A Mortar BDD method for solving flow in stochastic discrete fracture networks
Domain Decomposition Methods in Science and Engineering XXI
Jocelyne Erhel; Martin Gander; Laurence Halpern; Géraldine Pichot; Taoufik Sassi & Olof Widlund, ed
LNCSE, Springer, 2014
- Poirriez, B.
Etude et mise en oeuvre d'une méthode de sous-domaines pour la modélisation de l'écoulement dans des réseaux de fractures en 3D
Ph-D thesis, University of Rennes 1, 2011
Research subtopic: preconditioned
GMRES
Algorithm description
PARGMRES does not use the classical Arnoldi process to build an
orthonormal basis of the Krylov subpsace but first builds a so-called
Newton-basis then computes an orthonormal basis. Thanks to a reduction
of communication, parallelism is enforced. The restarting parameter can
be controled to ensure robustness of the Krylov basis.
DEFGMRES computes and updates a preconditioner at each restart by using
an estimation of an invariant subspace. It can be used with any other
preconditioner. It is parallel but involves some communications.
Deflation avoids stagnation when the restarting parameter is small.
AUGMRES computes an augmented basis of the Krylov subspace by
estimating an invariant subspace. Like DEFGMRES, it can be used with
any preconditioner, it avoids stagnation and is parallel.
MSGMRES computes a parallel Multiplicative Schwarz preconditioner. It
is based on an algebraic matrix partition and on an explicit
formulation of the preconditioning matrix. The matrix vector product
and the preconditioning are pipelined through parallel processes.
Software description
- GPREMS implements a combination of the three algorithms PARGMRES,
MSGMRES and AUGMRES: it
is parallel and preconditioned by Multiplicative Schwarz. The basis can
be augmented by deflating approximate eigenvalues.
- DGMRES implements DEFGMRES in the Petsc library. It can be
combined with GMRES and any preconditioner included in Petsc. DGMRES is
included in Petsc library.
- AGMRES implements a combination of the algorithms PARGMRES and
AUGMRES in the Petsc library. It is included in the repository of Petsc.
Objectives and projects
The main objective is to pursue the research for improving
robustness and parallelism.
Algorithms are applied to 3D industrial
problems stemming from Computational
Fluid Dynamics applications aiming at reducing fuel consumption.
Matrices are provided by the industrial partners of the LIBRAERO and CINEMAS2 projects (see below).
Publications about GMRES
- D. Nuentsa Wakam and F. Pacull
Memory efficient hybrid algebraic solvers for linear systems arising from compressible flows
Computers and Fluids, 2013, Volume 80, 158-167
- J. Erhel
Some Properties of Krylov Projection Methods for Large Linear Systems.
P. Ivanyi and B.H.V. Topping (ed), Computational Technology Reviews,
Saxe-Coburg Publications, 2011, Volume 3, 41-70
- B. Philippe and L. Reichel
on the generation of Krylov subspace bases
Applied Numerical Mathematics (APNUM), 2012, Volume 62, 1171-1186
- N. Gmati, B. Philippe,
Comments on the GMRES convergence for preconditioned systems
proceedings of the international conference on Large-Scale
Scientific Computations, 2007, 40-51, LNCS
Publications about DEFGMRES and deflation
- D. Nuentsa-Wakam and J. Erhel.
Parallelism and robustness in GMRES with the Newton basis
and the deflated restarting.
ETNA, 40, 381-406, 2013.
- D. Nuentsa-Wakam and J. Erhel and W. Gropp.
Parallel adaptive deflated GMRES.
Domain Decomposition Methods in Science and Engineering XX (DD20), R. Bank, M. Holst, O. Widlund and J. Xu editors,
pp. 631-638, LNCSE, Springer, 2013.
- D. Nuentsa-Wakam and J. Erhel and É. Canot.
Robustness in hybrid algebraic solvers for large linear systems.
Proceedings of Parallel CFD 2011, 2011, online.
- D. Nuentsa Wakam
Parallélisme et robustesse dans les solveurs hybrides pour grands
systèmes linéaires: Application à l'optimisation en dynamique des
fluides. Ph-D thesis, University of Rennes 1, 2011
- K. Burrage, J. Erhel, B. Pohl and A. Williams.
A deflation technique for linear systems of equations.
SIAM
Journal on Science and Computation,
Volume 19, Number 4, pp. 1245-1260, 1998.
- K. Burrage, J. Erhel.
On the performance of various adaptive preconditioned GMRES
strategies.
Numerical
Linear Algebra with Applications,
Volume 5, pp. 101-121, 1998.
- J. Erhel and K. Burrage and B. Pohl.
Restarted GMRES preconditioned by deflation.
Journal of Computation and Applied Mathematics,
Volume 69, pp.303-318, 1996.
- K. Burrage and A. Williams and J. Erhel and B. Pohl.
The implementation of a Generalized Cross Validation algorithm using
deflation techniques for linear systems.
Applied Numerical Mathematics,
Volume 19, pp.17-31, 1995.
Publications about GPREMS (parallel GMRES preconditioned by
Multiplicative Schwarz)
- G.-A.
Atenekeng Kahou and D. Nuentsa-Wakam.
Parallel GMRES with a multiplicative Schwarz preconditioner.
ARIMA, 2011, Volume 14, 81-99
- D. Nuentsa-Wakam, J. Erhel, É. Canot and G.
Atenekeng-Kahou
A comparative study of some distributed linear solvers on systems
arising from fluid dynamics simulations
Parallel Computing: from Multicores and GPU's to Petascale
(Proceedings of PARCO'2009), 2010, 51-58
B. Chapman and F. Desprez and G. Joubert
and A. Lichnewsky and F. Peters and T. Priol (ed.)
IOS Press - D. Nuentsa-Wakam and J. Erhel and É. Canot
Parallélisme à deux niveaux dans {GMRES} avec un
préconditionneur Schwarz multiplicatif
proceedings of CARI'2010, 2010,
189-196, INRIA - G.-A. Atenekeng Kahou, L.
Grigori, and M. Sosonkina.
A Partitioning Algorithm for Block-Diagonal Matrices with Overlap.
Parallel Computing, 2008, Volume 34,
Issues 6-8 , 332-344 - G.-A.
Atenekeng Kahou, E. Kamgnia, and B. Philippe.
An explicit formulation of the multiplicative Schwarz preconditionner.
Applied Numerical Mathematics, 2007, Volume 57,
1197-1213 (also
INRIA research report RR-5685). - G.-A.
Atenekeng Kahou, E. Kamgnia, and B. Philippe.
A Combinatorial tool for GMRES preconditioned by Multiplicative
Schwarz.
Proceedings of PPAM'2007, CTPSM07 Workshop, 2007.
Publications about PARGMRES (parallel GMRES)
- D. Imberti and J. Erhel
Vary the s in Your s-step GMRES
preprint, 2016. https://hal.inria.fr/hal-01299652
- Sidje, R.B.
Alternatives for Parallel Krylov Basis Computation.
Numerical Linear Algebra with Applications, Vol. 4(4), 305-331, 1997.
- J. Erhel.
A parallel GMRES version for general sparse matrices.
Electronic Transactions on Numerical Analysis,
Volume 3, pp.160-176, 1995.
- J. Erhel.
A Parallel Preconditioned GMRES Algorithm for Sparse Matrices.
Lectures in Applied Mathematics, The Mathematics of
Numerical Analysis, 1996, pp. 345-355.
- R-B. Sidje.
Algorithmes parallèles pour le calcul d'exponentielles de matrices de
grandes tailles.
Ph-D thesis, University of Rennes 1, 1994.
- B. Philippe and R. B. Sidje.
Parallel Krylov Subspace Basis Computation.
proceedings of the 2nd Colloque Africain sur la Recherche en
Informatique (CARI), 1994, 421-440.
J. Tankoano Ed., ORSTOM Editions.
Participants
This topic started in the Aladin team (participants B. Philippe and
J. Erhel) with the Ph-D thesis of R. Sidje. The thesis was defended in
1994. It was extended with several internships to define PARGMRES.
Then the research continued in the Aladin team (participant J. Erhel)
in collaboration with K. Burrage, in Brisbane, Australia. Several
variants of DEFGMRES were defined.
The work on Multiplicative Schwarz was done in the Sage team
(participants B. Philippe and L. Grigori) with the Ph-D thesis of G-A.
Atenekeng Kahou, in collaboration with E. Kamgnia, Cameroon and M.
Sosonkina, USA. The thesis was defended in 2008.
Some convergence aspects of GMRES were studied (participant B.
Philippe), in collaboration with N. Gmati, Tunisia and with L. Reichel, USA.
The research continued in the Sage team (participants J. Erhel, B. Philippe,
E. Canot), with the Ph-D thesis of D. Nuentsa Wakam. The thesis was defended in 2011.
The research continues in the Fluminance team ((participant J. Erhel) with the post-doctoral position of D. Imberti.
Grants
Work on preconditioned GMRES is funded by Europe with the project EXA2CT (2013-2017).
Work on parallel and deflated GMRES was funded by the ANR RNTL with the project LIBRAERO (2008-2011).
It was also funded by Région Rhône-Alpes, in the framework of LUTB, with
the project CINEMAS2 (2007-2011).
It is partly funded by the INRIA Illinois Joint Lab on Petascale Computing (2010-2011).
D. Nuentsa Wakam spent a month at UIUC (USA), thanks to a grant from the university of Rennes 1 (2011).
The visits of L. Reichel (Kent Univ, USA) in the team were funded by the university of Rennes 1 (2010).
The visits of B. Philippe at ENIT (Tunisia) were funded by a Unesco chair (2003-2004).
The exchanges between INRIA and Univ. of Queensland (Australia) were partly funded by the australian government (1994-1997).
Computing facilities
Numerical experiments run on the Grid'5000 french grid and at the IDRIS french supercomputing center (2008-2013).
