COMPUTING, VOL.73, NO.4, PP.349-371, 2004.

TITLE: Comparison of Multilevel Methods for Kroncker-based Markovian
       Representations

AUTHORS: Peter Buchholz and Tugrul Dayar

ABSTRACT: The paper presents a class of numerical methods to compute the
stationary distribution of Markov chains (MCs) with large and structured state 
spaces. A popular way of dealing with large state spaces in Markovian modeling 
and analysis is to employ Kronecker-based representations for the generator 
matrix and to exploit this matrix structure in numerical analysis methods. 
This paper presents various multilevel (ML) methods for a broad class of MCs 
with a hierarchical Kronecker structure of the generator matrix. The particular
ML methods are inspired by multigrid and aggregation-disaggregation techniques,
and differ among each other by the type of multigrid cycle, the type of 
smoother, and the order of component aggregation they use. Numerical 
experiments demonstrate that so far ML methods with successive over-relaxation 
as smoother provide the most effective solvers for considerably large Markov 
chains modeled as HMMs with multiple macrostates.

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