Updating $LU$ Factorizations for Computing Stationary Distributions

Abstract

The computation of stationary probability distributions for Markov chains is important in the analysis of many models in the mathematical sciences, such as queueing network models, input-output economic models and compartmental tracer analysis models. These computations often involve the solution of large-scale homogeneous linear equations by Gaussian elimination, where A is a Q-matrix, i.e., $A = ( a_{ij} )$ is irreducible, $a_{ij} \leqq 0$ for all $i \ne j$ and has zero column sums. The stationary distributions are the components of the unique solution vector x of positive components whose sum is one. Stable direct methods for computing x by triangular factorization $A = LU$ have received considerable attention recently and the purpose of this paper is to provide a stable method for updating the factors L and U in $O( n^2 )$ flops in the case where a column of A is modified. Updating formulas are derived here using an approach similar to that for updating the Cholesky factor of a symmetric positive definite matrix after the addition of a rank one matrix. The algorithm is effective more generally for any matrix that has a stable $LU$ factorization and for which the updated matrix has a stable $LU$ factorization. An error analysis for thw $LU$ update algorithm is outlined along the lines of that given for the Cholesky update by Fletcher and Powell. Details of the algorithm based on the error analysis and other considerations are given.