TITLE: Compact Representation of Solution Vectors in Kronecker-based 
Markovian Analysis

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

ABSTRACT: It is well known that the infinitesimal generator underlying
a multi-dimensional Markov chain with a relatively large reachable
state space can be represented compactly on a computer in the form of
a block matrix in which each nonzero block is expressed as a sum of
Kronecker products of smaller matrices. Nevertheless, solution vectors
used in the analysis of such Kronecker-based Markovian representations
still require memory proportional to the size of the reachable state
space, and this becomes a bigger problem as the number of dimensions
increases. The current paper shows that it is possible to use the
hierarchical Tucker decomposition (HTD) to store the solution vectors
during Kronecker-based Markovian analysis relatively compactly and
still carry out the basic operation of vector-matrix multiplication in
Kronecker form relatively efficiently. Numerical experiments on two
different problems of varying sizes indicate that larger memory savings
are obtained with the HTD approach as the number of dimensions increases.

KEY WORDS: Markov chains, Kronecker products, hierarchical Tucker
decomposition, reachable state space, compact vectors.