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

DOI10.1553/ETNA_VOL48S348zbMATH Open1401.65031arXiv1605.06246OpenAlexW2963257358WikidataQ129116841 ScholiaQ129116841MaRDI QIDQ1990903FDOQ1990903

Authors: Matthias Bolten, K. Kahl, Daniel Kressner, Francisco Macedo, Sonja Sokolović 

Publication date: 26 October 2018

Published in: ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)

Abstract: Markov 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.

Full work available at URL: https://arxiv.org/abs/1605.06246

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Multigrid methods for tensor structured Markov chains with low rank approximation
• Low-rank tensor methods for Markov chains with applications to tumor progression models
• Efficient low-rank approximation of the stochastic Galerkin matrix in tensor formats
• Tensor approximation methods for stochastic problems
• Compact adaptive aggregation multigrid method for Markov chains
• On a two-level multigrid solution method for finite Markov chains
• Markov chains and tensor multiplications
• A new \(\mathrm{GMRES}(m)\) method for Markov chains
• Low-rank tensor methods for partial differential equations

zbMATH Keywords

SVDMarkov chainsmultigrid methodtensor train formatalternating optimizationsingular linear system

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Computational methods for sparse matrices (65F50) Multilinear algebra, tensor calculus (15A69) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Iterative numerical methods for linear systems (65F10)

Cites Work

• Title not available (Why is that?)
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Tensor-train decomposition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Analysis of loss networks with routing
• Alternating minimal energy methods for linear systems in higher dimensions
• The Kronecker product and stochastic automata networks
• Approximation of \(2^d\times2^d\) matrices using tensor decomposition
• Solution of Linear Systems and Matrix Inversion in the TT-Format
• Title not available (Why is that?)
• A projection method to solve linear systems in tensor format
• Iterative methods for overflow queueing models. I
• Iterative methods for overflow queuing models. II
• Matrix Methods for Queuing Problems
• General highly accurate algebraic coarsening
• Numerical Methods in Markov Chain Modeling
• Low-rank tensor methods with subspace correction for symmetric eigenvalue problems
• Product-form stationary distributions for deficiency zero chemical reaction networks
• Towards adaptive smoothed aggregation (\(\alpha\)SA) for nonsymmetric problems
• Title not available (Why is that?)
• Stochastic fluctuations in metabolic pathways
• On the Convergence of a Class of Multilevel Methods for Large Sparse Markov Chains
• Simultaneous state-time approximation of the chemical master equation using tensor product formats.
• Compatible relaxation and coarsening in algebraic multigrid
• Multigrid methods for tensor structured Markov chains with low rank approximation

Cited In (2)

• Low-rank tensor methods for Markov chains with applications to tumor progression models
• Multigrid methods for tensor structured Markov chains with low rank approximation

Uses Software

• Matlab

This page was built for publication: Multigrid methods combined with low-rank approximation for tensor-structured Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990903)