This project will investigate the numerical solution of discrete Markov chains, with an emphasis on the computation of the steady-state vector of ergodic chains. Although the problem can be cast as an ordinary eigenvalue problem, it is special in two ways. First, the eigenvalue in question, namely one, is known exactly. Second, many of the applications, such as queuing modeling, have special structure that can be exploited computationally. Consequently, diverse methods have been set forth, some of which are poorly understood. The goal of this work is to improve understanding of their theory, their interrelations, and their implementation, particularly parallel implementations, beginning with a classification of the methods and then focusing on particularly promising algorithms.
