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

TITLE: Block SOR for Kronecker Structured Representations 

AUTHORS: Peter Buchholz and Tugrul Dayar

ABSTRACT: Hierarchical Markovian Models (HMMs) are composed of multiple low 
level models (LLMs) and a high level model (HLM) that defines the interaction 
among LLMs. The essence of the HMM approach is to model the system at hand in 
the form of interacting components so that its (larger) underlying continuous-
time Markov chain (CTMC) is not generated but implicitly represented as a sum 
of Kronecker products of (smaller) component matrices. The Kronecker structure 
of an HMM induces nested block partitionings in its underlying CTMC. These 
partitionings may be used in block versions of classical iterative methods 
based on splittings, such as block SOR (BSOR), to solve the underlying CTMC 
for its stationary vector. Therein the problem becomes that of solving 
multiple nonsingular linear systems whose coefficient matrices are the 
diagonal blocks of a particular partitioning. This paper shows that in each 
HLM state there may be diagonal blocks with identical off-diagonal parts and 
diagonals differing from each other by a multiple of the identity matrix. Such 
diagonal blocks are named candidate blocks. The paper explains how candidate 
blocks can be detected and how they can mutually benefit from a single real 
Schur factorization. It gives sufficient conditions for the existence of 
diagonal blocks with real eigenvalues and shows how these conditions can be 
checked using component matrices. It describes how the sparse real Schur 
factors of candidate blocks satisfying these conditions can be constructed 
from component matrices and their real Schur factors. It also demonstrates how 
fill-in of LU factorized (non-candidate) diagonal blocks can be reduced by 
using the column approximate minimum degree algorithm (COLAMD). Then it 
presents a three-level BSOR solver in which the diagonal blocks at the first 
level are solved using block Gauss-Seidel (BGS) at the second and the methods 
of real Schur and LU factorizations at the third level. Finally, on a set of 
numerical experiments it shows how these ideas can be used to reduce the
storage required by the factors of the diagonal blocks at the third level and 
to improve the solution time compared to an all LU factorization 
implementation of the three-level BSOR solver.