Stable Computation with the Fundamental Matrix of a Markov Chain
Jesse L. Barlow · SIAM Journal on Matrix Analysis and Applications · 2000
The short term behavior of a Markov chain can be inferred from its fundamental matrix F. One method of computing the parts of F that are needed is to compute F y for a given vector y. It is shown that all forward stable algorithms that solve a particular least squares problem lead to forward stable algorithms for computing F y . This in turn leads to a class of algorithms that compute F y accurately whenever the underlying problem is well-conditioned. One algorithm from this class is based upon the Grassman--Taksar--Heyman variant of Gaussian elimination. Other such algorithms include one based upon orthogonal factorization and one based upon the conjugate gradient least squares algorithm.