Block SOR for Kronecker structured representations (Q1434413)

Markov chain (MC) modelling with Kronecker based numerical techniques relies on representing the system at hand as a sum of Kronecker products of smaller component matrices, the explosion problem of total state space being handled by a cross product of the state spaces of the components. The present 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. Another constructive idea is to apply the column approximate minimum degree (COLAMD) ordering algorithm as a useful tool to reduce fill-in remaining diagonal blocks that are sparse LU factorized when solving non-singular linear systems associated to MC problems. Combining these ideas fruitfully, the authors propose a three-level block successive over-relaxation (BSOR) competitive steady state solver for hierarchical Markovian models (HMMs). HMMs are considered to be composed of multiple low level models (LLMs) and a high level model (HLM) that defines the interaction among LLMs. The Kronecker structure of a HMM induces nested block partitionings in its underlying continuous-time Markov chains (MCs). The authors show 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 called candidate blocks, and the paper explains how candidate blocks can be detected and how they can be mutually benefit from a single real Schur factorization. Sufficient conditions for the existence of diagonal blocks with real eigenvalues are given, and how to check these conditions using component matrices is detailed. The particular implementation of the three-level BSOR solver is based on diagonal blocks at the first level, it is using block Gauss-Seidel at the second level, and the methods of real Schur and LU factorization are employed at the third level. On a set of numerical experiments, the paper demonstrates how the proposed three-level BSOR solves reduces the storage requirements and time disadvantages related to the factorization of diagonal blocks in large systems. Different combinations of parameters for the BSOR solves are experimented and comps with commonly used solvers for Kronecker representations.