SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, VOL.29, NO.3, 
PP.1025-1049, 2007.

TITLE: On the Convergence of a Class of Multilevel Methods for Large, 
Sparse Markov Chains

AUTHORS: Peter Buchholz and Tugrul Dayar

ABSTRACT: This paper investigates the theory behind the steady state 
analysis of large sparse Markov chains with a recently proposed class of
multilevel methods using concepts from algebraic multigrid and iterative
aggregation-disaggregation. The motivation is to better understand the
convergence characteristics of the class of multilevel methods and to have
a clearer formulation that will aid their implementation. In doing this,
restriction (or aggregation) and prolongation (or disaggregation) operators
of multigrid are used, and the Kronecker-based approach for hierarchical
Markovian models is employed, since it suggests a natural and compact
definition of grids (or levels). However, the formalism used to describe
the class of multilevel methods for large sparse Markov chains has no
influence on the theoretical results derived.

KEY WORDS: Markov chains; multigrid; aggregation-disaggregation;
Kronecker-based numerical techniques; multilevel methods