TECHNICAL REPORT TUD-FI03-05, DRESDEN UNIVERSITY OF TECHNOLOGY, 
DEPARTMENT OF COMPUTER SCIENCE

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 SOR
(BSOR) preconditioner for hierarchical Markovian Models (HMMs) 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 algorithm (COLAMD). A set 
of numerical experiments are presented to show the merits of the proposed BSOR 
preconditioner.