Block SOR for Kronecker Structured Representations
by
Tugrul
Dayar
Bilkent University
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.