Research topic: parallel sparse linear solvers - preconditioned GMRES

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. We consider here the nonsymmetric case. Krylov iterative methods are commonly used as sparse solvers and among them, BICGSTAB or GMRES method. 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 a parallel version of GMRES and on efficient parallel preconditioners.

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 GPREMS (parallel GMRES preconditioned by Multiplicative Schwarz)

Publications about DEFGMRES and deflation

Publications about PARGMRES (parallel GMRES)

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 are studied (participant B. Philippe), in collaboration with N. Gmati, Tunisia and with L. Reichel, USA.

The research continues in the Sage team (participants J. Erhel, B. Philippe, E. Canot), with the thesis of D. Nuentsa Wakam. The thesis should be defended in autumn 2011.

Grants

Work on parallel and deflated GMRES is funded by the ANR RNTL with the project LIBRAERO (2008-2011).

It is 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-2011).