TECHNICAL REPORT BU-CE-0601, BILKENT UNIVERSITY, 
DEPARTMENT OF COMPUTER ENGINEERING

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 (MCs) with a recently proposed 
class of multilevel (ML) methods using concepts from algebraic multigrid 
and iterative aggregation-disaggregation. The motivation is to better 
understand the convergence characteristics of the class of ML 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 (HMMs) is employed, since it 
suggests a natural and compact definition of grids (or levels). However, 
the HMM formalism used to describe the class of ML methods for large, 
sparse MCs has no influence on the theoretical results derived.