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

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

AUTHORS: 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