Factorized sparse approximate inverse preconditioning for singular M-matrices

Abstract

Here we consider the factorized sparse approximate inverse (FSAI) preconditioner. We apply the FSAI preconditioner to singular irreducible M-matrices. These matrices arise e.g. in discrete Markov chain modeling or as graph Laplacians. We show, that there are some restrictions on the nonzero pattern needed for a stable construction of the FSAI preconditioner in this case. With these restrictions FSAI is well-defined. Moreover, we proved that the FSAI preconditioner shares some important properties with the original system. The lower triangular matrix $L_G$ and the upper triangular matrix $U_G$, generated by FSAI, are non-singular and non-negative. The diagonal entries of $L_{G}A{U}_G$ are positive and $L_{G}A{U}_G$, the preconditioned matrix, is a singular M-matrix. Even more, we establish that a (1,2)-inverse is computed for the complete nonzero patter.

Preprint 17 pages