Factorized sparse approximate inverse preconditioning for singular M-matrices

2025/12/25 by Katherina Bick, Bick, Katherina, Reinhard Nabben +1
Computer Science · Mathematics · #Matrix Theory and Algorithms #Tensor decomposition and applications #Markov Chains and Monte Carlo Methods

paper · doi:10.48550/arxiv.2512.21744

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_GAU_G are positive and L_GAU_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.

Citations

• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver\n (Journal Version)

Related

• A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems
• Preconditioning with direct approximate factoring of the inverse
• Approximate Inverse Preconditioners via Sparse-Sparse Iterations
• Stochastic Preconditioning for Iterative Linear Equation Solvers
• A sparse approximate inverse for triangular matrices based on Jacobi iteration