A low-rank tensor method for structured large-scale Markov Chains

A number of practical applications lead to Markov Chains with extremely large state spaces. Such an instance arises from the class of Queuing Networks, which lead to a number of applications of interest including, for instance, the analysis of the well-known tandem networks. The state space of a Markov process describing these interactions typically grows exponentially with the number of queues. More generally, Stochastic Automata Networks (SANs) are networks of interacting stochastic automata. The dimension of the resulting state space grows exponentially with the number of involved automata. Several techniques have been established to arrive at a formulation such that the transition matrix has Kronecker product structure. This allows, for example, for efficient matrix-vector multiplications. However, the number of possible automata is still severely limited by the need of representing a single vector (e.g., the stationary vector) explicitly. We propose the use of low-rank tensor techniques to avoid this barrier. More specifically, an algorithm will be presented that allows to approximate the solution of certain SAN s very efficiently in a low-rank tensor format.