Volume 48, pp. 348-361, 2018.

Multigrid methods combined with low-rank approximation for tensor-structured Markov chains

Matthias Bolten, Karsten Kahl, Daniel Kressner, Francisco Macedo, and Sonja Sokolović

Abstract

Markov chains that describe interacting subsystems suffer from state space explosion but lead to highly structured matrices. In this work, we propose a novel tensor-based algorithm to address such tensor-structured Markov chains. Our algorithm combines a tensorized multigrid method with AMEn, an optimization-based low-rank tensor solver, for addressing coarse grid problems. Numerical experiments demonstrate that this combination overcomes the limitations incurred when using each of the two methods individually. As a consequence, Markov chain models of unprecedented size from a variety of applications can be addressed.

Full Text (PDF) [372 KB], BibTeX

Key words

Multigrid method, SVD, Tensor Train format, Markov chains, singular linear system, alternating optimization

AMS subject classifications

65F10, 65F50, 60J22, 65N55

Links to the cited ETNA articles

[6]	Vol. 10 (2000), pp. 1-20 Achi Brandt: General highly accurate algebraic coarsening

< Back