A bootstrap algebraic multilevel method for Markov chains

DOI10.1137/100791816MaRDI QIDQ3116499zbMATH OpenOpenAlexFDO

Authors Matthias Bolten, Achi Brandt, J. Brannick, Andreas Frommer, K. Kahl, Irene Livshits

Publication date 23 February 2012

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

bootstrapnumerical examplesMarkov chainsstochastic matricesadaptive methodsalgebraic multigridgeneralized minimal residual (GMRES) iterationleast squares prolongationmultilevel eigensolverpreconditioned GMRES iteration

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Stochastic matrices (15B51)

Abstract: This work concerns the development of an Algebraic Multilevel method for computing stationary vectors of Markov chains. We present an efficient Bootstrap Algebraic Multilevel method for this task. In our proposed approach, we employ a multilevel eigensolver, with interpolation built using ideas based on compatible relaxation, algebraic distances, and least squares fitting of test vectors. Our adaptive variational strategy for computation of the state vector of a given Markov chain is then a combination of this multilevel eigensolver and associated multilevel preconditioned GMRES iterations. We show that the Bootstrap AMG eigensolver by itself can efficiently compute accurate approximations to the state vector. An additional benefit of the Bootstrap approach is that it yields an accurate interpolation operator for many other eigenmodes. This in turn allows for the use of the resulting AMG hierarchy to accelerate the MLE steps using standard multigrid correction steps. The proposed approach is applied to a range of test problems, involving non-symmetric stochastic M-matrices, showing promising results for all problems considered.

Recommendations

• Algebraic multigrid for Markov chains
• Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains
• Fast multilevel methods for Markov chains.
• On a two-level multigrid solution method for finite Markov chains
• Multigrid methods for tensor structured Markov chains with low rank approximation

Cited in

(4)

• Algebraic multigrid for Markov chains
• The least squares AMG solver for the one-dimensional Helmholtz operator
• Multigrid methods for tensor structured Markov chains with low rank approximation
• Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains

This page was built for publication: A bootstrap algebraic multilevel method for Markov chains

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