TITLE: On Compact Solution Vectors in Kronecker-based Markovian Analysis

AUTHORS: Peter Buchholz, Tugrul Dayar, Jan Kriege, and M. Can Orhan

ABSTRACT: State based analysis of stochastic models for performance and 
dependability often requires the computation of the stationary 
distribution of a multidimensional continuous-time Markov chain (CTMC). 
The infinitesimal generator underlying a multidimensional CTMC with a 
large reachable state space can be represented compactly in the form of 
a block matrix in which each nonzero block is expressed as a sum of 
Kronecker products of smaller matrices. However, solution vectors used 
in the analysis of such Kronecker-based Markovian representations require 
memory proportional to the size of the reachable state space. This 
implies that memory allocated to solution vectors becomes a bottleneck as 
the size of the reachable state space increases. Here, it is shown that 
the hierarchical Tucker decomposition (HTD) can be used with adaptive 
truncation strategies to store the solution vectors during Kronecker-
based Markovian analysis compactly and still carry out the basic 
operations including vector–matrix multiplication in Kronecker form 
within Power, Jacobi, and Generalized Minimal Residual methods. Numerical 
experiments on multidimensional problems of varying sizes indicate that 
larger memory savings are obtained with the HTD approach as the number of 
dimensions increases.

KEY WORDS: Markov chain; Kronecker product; Hierarchical Tucker 
decomposition; Reachable state space; Compact vector.