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

2016/05/20 by Matthias Bolten, Karsten Kahl, Bolten, Matthias +7
Computer Science · Mathematics · Physics and Astronomy · #60J22 #65F10 #65F50 #65N55 #FOS: Mathematics #Numerical Analysis (math.NA) #Parallel Computing and Optimization Techniques #Solar and Space Plasma Dynamics #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1605.06246

openalex publication_date 2016/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Markov chains that describe interacting subsystems suffer, on the one hand,\nfrom state space explosion but lead, on the other hand, to highly structured\nmatrices. In this work, we propose a novel tensor-based algorithm to address\nsuch tensor structured Markov chains. Our algorithm combines a tensorized\nmultigrid method with AMEn, an optimization-based low-rank tensor solver, for\naddressing coarse grid problems. Numerical experiments demonstrate that this\ncombination overcomes the limitations incurred when using each of the two\nmethods individually. As a consequence, Markov chain models of unprecedented\nsize from a variety of applications can be addressed.\n

Related

• Multigrid methods for tensor structured Markov chains with low rank\n approximation
• Low-Rank Tensors for Multi-Dimensional Markov Models
• Low-rank tensor methods for Markov chains with applications to tumor progression models
• Markov chains for tensor network states
• Tensor methods for the computation of MTTA in large systems of loosely interconnected components