Multigrid methods combined with low-rank approximation for tensor-structured Markov chains. ETNA - Electronic Transactions on Numerical Analysis
Fiche du document
9 octobre 2018
- handle: 10670/1.vaq95v
- issn: 1068-9613
- doi: 10.1553/etna_vol48s348
info:eu-repo/semantics/openAccess
Sujets proches
Markov models Markoff processes Analysis, Markov Models, Markov Markov analysis Chains, Markov Markov chains Processes, MarkovCiter ce document
Daniel Kressner et al., « Multigrid methods combined with low-rank approximation for tensor-structured Markov chains. ETNA - Electronic Transactions on Numerical Analysis », Elektronisches Publikationsportal der Österreichischen Akademie der Wissenschafte, ID : 10.1553/etna_vol48s348
Métriques
Partage / Export
Résumé
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.