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.