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

Publications about Balanced Domain Decomposition (deflated Schur method)
Applications to groundwater flow

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

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

Publications about DEFGMRES and deflation

Publications about GPREMS (parallel GMRES preconditioned by Multiplicative Schwarz)

Publications about PARGMRES (parallel GMRES)


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.


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).