Comparisons between aggregation/disaggregation and a direct algorithm for computing the stationary probabilities of a Markov chain

Aggregation/disaggregation is an iterative scheme that leads to an algorithm for computing the steady-state distribution of a finite Markov chain. The idea is to partition the states into aggregates, estimate the probability that the Markov chain is in a particular aggregate, and then estimate the conditional probability of being in each state of an aggregate given that the Markov chain is in some state in that aggregate. Previous computational performance studies of this algorithm concentrated on applying it to chains that were nearly decomposable. We focus on chains that are not nearly decomposable. We compare this iterative algorithm to a direct method that is a variant of Gaussian elimination. We use a variety of test problems that range in size from 500 to 5,000 states, and which include unstructured and banded matrices. We conclude that, for this array of problems, the direct method requires less computation.