Resolution of sparse linear systems of equations: the RPK strategy

Abstract

An over view of advanced techniques for solving large sparse linear systems of equations is presented. First, several reordering algorithms are introduced in order to improve the effect of preconditioning on a linear system. Next, we define the concept of preconditioning and formulate some of most popular preconditioners, especially those based in approximate inverse. On the other hand, some Krylov subspace methods for solving linear systems of equations are considered. For symmetric problems, the Conjugate Gradient method is proposed. However, for non-symmetric linear systems there exist several alternatives that may be classified into three family of methods: orthogonalisation, biorthogonalisation and normal equation methods. Nowadays, RPK strategy which combines those three techniques, reordering, preconditioning and Krylov subspace methods, seems to be the most efficient from the computational point of view. This is finally illustrated with some numerical experiments.