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

TITLE: Comparison of Multilevel Methods for Kroncker-based Markovian

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

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