MATHICSE-GroupBolten, MatthiasKahl, KarstenKressner, DanielSantos Paredes Quartin de Macedo, FranciscoSokolović, Sonja2019-10-042019-10-042019-10-042016-05-1110.5075/epfl-MATHICSE-271079https://infoscience.epfl.ch/handle/20.500.14299/161829Markov chains that describe interacting subsystems suffer, on the one hand, from state space explosion but lead, on the other hand, 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.Multigrid methodSVDTensor Train formatMarkov chainssingular linear systemalternating optimizationtext::working paper