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

AMS SUBJECT CLASSIFICATIONS: 60J27, 65F50, 65F10, 65B99, 65F15, 65F05, 15A72