SIAM JOURNAL ON SCIENTIFIC COMPUTING, VOL.26, NO.4, PP.1289-1313, 2005. 

TITLE: Block SOR Preconditioned Projection Methods for Kronecker Structured
       Markovian Representations 

AUTHOR: Peter Buchholz and Tugrul Dayar

ABSTRACT: Kronecker structured representations are used to cope with the state 
space explosion problem in Markovian modeling and analysis. Currently, an open 
research problem is that of devising strong preconditioners to be used with 
projection methods for the computation of the stationary vector of Markov 
chains (MCs) underlying such representations. This paper proposes a block 
successive overrelaxation (BSOR) preconditioner for hierarchical Markovian 
models (HMMs; throughout the paper, the HMM acronym stands for hierarchical 
Markovian models and should not be confused with the HMM that is sometimes 
used for hidden Markov models.) that are composed of multiple low-level models 
and a high-level model that defines the interaction among low-level models. 
The Kronecker structure of an HMM yields nested block partitionings in its 
underlying continuous-time MC which may be used in the BSOR preconditioner. 
The computation of the BSOR preconditioned residual in each iteration of a 
preconditioned projection method becomes the problem of solving multiple 
nonsingular linear systems whose coefficient matrices are the diagonal blocks 
of the chosen partitioning. The proposed BSOR preconditioner solves these 
systems using sparse LU or real Schur factors of diagonal blocks. The fill-in 
of sparse LU factorized diagonal blocks is reduced using the column 
approximate minimum degree (COLAMD) ordering. A set of numerical experiments 
is presented to show the merits of the proposed BSOR preconditioner. 

KEY WORDS: Markov chains, Kronecker structured numerical techniques, block 
SOR, preconditioning, projection methods, real Schur factorization, COLAMD 
ordering

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