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 2x2 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.
Key words. M-matrices, preconditioning, discrete Markov chains, iterative methods, graph partitioning