Multigrid methods for tensor structured Markov chains with low rank approximation
From MaRDI portal
Computational methods in Markov chains (60J22) Continuous-time Markov processes on discrete state spaces (60J27) Numerical analysis or methods applied to Markov chains (65C40) Iterative numerical methods for linear systems (65F10) Computational methods for sparse matrices (65F50) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)
Abstract: Tensor structured Markov chains are part of stochastic models of many practical applications, e.g., in the description of complex production or telephone networks. The most interesting question in Markov chain models is the determination of the stationary distribution as a description of the long term behavior of the system. This involves the computation of the eigenvector corresponding to the dominant eigenvalue or equivalently the solution of a singular linear system of equations. Due to the tensor structure of the models the dimension of the operators grows rapidly and a direct solution without exploiting the tensor structure becomes infeasible. Algebraic multigrid methods have proven to be efficient when dealing with Markov chains without using tensor structure. In this work we present an approach to adapt the algebraic multigrid framework to the tensor frame, not only using the tensor structure in matrix-vector multiplications, but also tensor structured coarse-grid operators and tensor representations of the solution vector.
Recommendations
- Multigrid methods combined with low-rank approximation for tensor-structured Markov chains
- Algebraic multigrid for Markov chains
- On a two-level multigrid solution method for finite Markov chains
- Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains
- Fast multilevel methods for Markov chains.
Cites work
- A bootstrap algebraic multilevel method for Markov chains
- A Multigrid Method to Solve Large Scale Sylvester Equations
- A new scheme for the tensor representation
- Algebraic multigrid for Markov chains
- Alternating minimal energy methods for linear systems in higher dimensions
- An adaptive algebraic multigrid algorithm for low-rank canonical tensor decomposition
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Analysis of tensor product multigrid
- Approximation of 2d²^d matrices using tensor decomposition
- Bootstrap AMG
- Comparison of multilevel methods for Kronecker-based Markovian representations
- Compatible relaxation and coarsening in algebraic multigrid
- Fast multigrid solver
- General highly accurate algebraic coarsening
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Hierarchical Singular Value Decomposition of Tensors
- scientific article; zbMATH DE number 734901 (Why is no real title available?)
- scientific article; zbMATH DE number 1049350 (Why is no real title available?)
- scientific article; zbMATH DE number 1561761 (Why is no real title available?)
- scientific article; zbMATH DE number 1424146 (Why is no real title available?)
- Iterative methods based on splittings for stochastic automata networks
- Iterative methods for overflow queueing models. I
- Iterative methods for overflow queuing models. II
- Iterative solution of large sparse systems of equations. Transl. from the German
- Low-rank tensor methods with subspace correction for symmetric eigenvalue problems
- Matrix Methods for Queuing Problems
- Methods of conjugate gradients for solving linear systems
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- Multilevel Adaptive Aggregation for Markov Chains, with Application to Web Ranking
- Multilevel solutions for structured Markov chains
- On the Convergence of a Class of Multilevel Methods for Large Sparse Markov Chains
- Operator-based interpolation for bootstrap algebraic multigrid.
- QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images
- Smoothed aggregation multigrid for Markov chains
- Solution of Linear Systems and Matrix Inversion in the TT-Format
- Structured analysis approaches for large Markov chains
- Tensor Decompositions and Applications
- Tensor spaces and numerical tensor calculus
- Tensor-train decomposition
- The Kronecker product and stochastic automata networks
- Towards adaptive smoothed aggregation (\(\alpha\)SA) for nonsymmetric problems
Cited in
(6)- Multigrid methods combined with low-rank approximation for tensor-structured Markov chains
- Low-rank tensor methods for Markov chains with applications to tumor progression models
- A bootstrap algebraic multilevel method for Markov chains
- scientific article; zbMATH DE number 7640094 (Why is no real title available?)
- Randomized sketched TT-GMRES for linear systems with tensor structure
- Operator-dependent prolongation and restriction for the parameter-dependent multigrid method using low-rank tensor formats
This page was built for publication: Multigrid methods for tensor structured Markov chains with low rank approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2790081)
