On the Multi-Level Solution Algorithm for Markov Chains

                                Graham Horton

                         Computer Science Department
                       University of Erlangen-Nurnberg
                                Martensstr. 3
                           91058 Erlangen, GERMANY

We discuss the recently introduced multi-level algorithm for the steady state
solution of Markov chains.  The method is based on the aggregation principle,
which is well established in the literature.  Recursive application of the
aggregation yields a multi-level method which has been shown experimentally to
give results significantly faster than the metho currently in use.  The
algorithm can be reformulated as an algebraic multigrid scheme of Galerkin-
full approximation type.  The uniqueness of the scheme stems from its
solution-dependent prolongation operator which permits significant
computational savings in the evaluation of certain terms.