A Combined Direct-Iterative Method for Certain <i>M</i>-Matrix Linear Systems

Abstract

Large, sparse, irreducible singular (column diagonal dominant) M-matrices A occur in various applications including queueing networks, input-output analysis and compartmental analysis. Our splitting $A = M - N$ with the matrix M having symmetric zero structure is a regular splitting, and these splittings induce a combined direct-iterative solution to $Ax = 0$. A sparse $LU$ factorization of a symmetric permutation of A can be obtained using a standard symmetric ordering scheme such as minimum degree. No pivoting for stability is necessary. Splitting strategies based on a tolerance factor are also discussed and some numerical experience is given.