Volume 26, pp. 209-227, 2007.

Block triangular preconditioners for $M$-matrices and Markov chains

Michele Benzi and Bora Uçar

Abstract

We consider preconditioned Krylov subspace methods for solving large sparse linear systems under the assumption that the coefficient matrix is a (possibly singular) $M$-matrix. The matrices are partitioned into $2\times 2$ block form using graph partitioning. Approximations to the Schur complement are used to produce various preconditioners of block triangular and block diagonal type. A few properties of the preconditioners are established, and extensive numerical experiments are used to illustrate the performance of the various preconditioners on singular linear systems arising from Markov modeling.

Full Text (PDF) [276 KB], BibTeX

Key words

$M$-matrices, preconditioning, discrete Markov chains, iterative methods, graph partitioning

AMS subject classifications

05C50, 60J10, 60J22, 65F10, 65F35, 65F50