LINEAR ALGEBRA AND ITS APPLICATIONS, VOL.386, PP.83-109, 2004.

TITLE: Block SOR for Kronecker Structured Representations

AUTHORS: Peter Buchholz and Tugrul Dayar

ABSTRACT: The Kronecker structure of a hierarchical Markovian model (HMM) 
induces nested block partitionings in the transition matrix of its 
underlying Markov chain. This paper shows how sparse real Schur factors 
of certain diagonal blocks of a given partitioning induced by the 
Kronecker structure can be constructed from smaller component matrices 
and their real Schur factors. Furthermore, it shows how the column 
approximate minimum degree (COLAMD) ordering algorithm can be used to 
reduce fill-in of the remaining diagonal blocks that are sparse LU 
factorized. Combining these ideas, the paper proposes three-level block 
successive over-relaxation (BSOR) as a competitive steady state solver 
for HMMs. Finally, on a set of numerical experiments it demonstrates how 
these ideas reduce storage required by the factors of the diagonal blocks 
and improve solution time compared to an all LU factorization 
implementation of the BSOR solver.

KEY WORDS: Markov chains; Kronecker based numerical techniques; Block SOR; 
Real Schur factorization; COLAMD ordering