A Survey of Methods for Computing Large Sparse Matrix Exponentials Arising in Markov Chains

Krylov subspace techniques have been shown to yield robust methods for the numerical computation of large sparse matrix exponentials and especially the transient solutions of Markov Chains. The attractiveness of these methods results from the fact that they allow us to compute the action of a matrix exponential operator on an operand vector without having to compute, explicitly, the matrix exponential in isolation. In this paper we compare a Krylov-based method with some of the current approaches used for computing transient solutions of Markov chains. After a brief synthesis of the features of the methods used, numerical comparisons are performed on a POWER CHALLENGEarray supercomputer on three different models. Keywords. Matrix exponential, Markov chains, Krylov methods, Ordinary differential equations. AMS Subject Classification. 65F99, 65L05, 65U05. 1 Introduction There exists several numerical techniques for obtaining transient solutions of homogeneous, irreducible Markov chain..