Low-Rank Tensor Methods for Communicating Markov Processes

Stochastic models that describe interacting processes, such as stochastic automata networks, feature a dimensionality that grows exponentially with the number of processes. This state space explosion severely impairs the use of standard methods for the numerical analysis of such Markov chains. In this work, we discuss the approximation of solutions by matrix product states or, equivalently, by tensor train decompositions. Two classes of algorithms based on this low-rank decomposition are proposed, using either iterative truncation or alternating optimization. Our approach significantly extends existing approaches based on product form solutions and can, in principle, attain arbitrarily high accuracy. Numerical experiments demonstrate that the newly proposed algorithms are particularly well suited to deal with pairwise neighbor interactions.


Editor(s):
Norman, G
Sanders, W
Published in:
Quantitative Evaluation Of Systems, Qest 2014, 8657, 25-40
Presented at:
11th International Conference on Quantitative Evaluation of Systems (QEST), Florence, ITALY, SEP 08-10, 2014
Year:
2014
Publisher:
Berlin, Springer-Verlag Berlin
ISSN:
0302-9743
ISBN:
978-3-319-10696-0; 978-3-319-10695-3
Laboratories:




 Record created 2015-02-20, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)