On a two-level multigrid solution method for finite Markov chains

DOI10.1016/0024-3795(95)00166-OMaRDI QIDQ1894507zbMATH OpenOpenAlexFDO

Authors Udo R. Krieger

Publication date 18 February 1996

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(95)00166-o

zbMATH Keywords

algebraic multigrid schemeerror analysishomogeneous Markov chainiterative aggregation-disaggregation technique

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27) Probabilistic methods, stochastic differential equations (65C99)

Review text

The author presents a two-level algebraic multigrid scheme for computing the stationary distribution of a homogeneous Markov chain with a finite state space. Both, continuous-time and discrete-time Markov chains are discussed. The author reveals his technique to be equivalent to an iterative aggregation-disaggregation technique. Error analysis results are presented, too. The author refines the error analysis of \textit{F. Chatelin} and \textit{W. L. Miranker} [ibid. 43, 17-47 (1982; Zbl 0485.65023)] and \textit{M. Haviv} [SIAM J. Numer. Anal. 24, 952- 966 (1987; Zbl 0637.65147)]. An interpretation of the block underrelaxation smoother in the stochastic context is developed, too.

Recommendations

• scientific article; zbMATH DE number 956817
• Algebraic multigrid for Markov chains
• Fast multilevel methods for Markov chains.
• Smoothed aggregation multigrid for Markov chains
• Compact adaptive aggregation multigrid method for Markov chains

Cites work

• A local convergence proof for the iterative aggregation method
• A Unified Convergence Theory for Abstract Multigrid or Multilevel Algorithms, Serial and Parallel
• Acceleration by aggregation of successive approximation methods
• Aggregation/Disaggregation Methods for Computing the Stationary Distribution of a Markov Chain
• An iterative aggregation-disaggregation algorithm for solving linear equations
• Constructive Interference in Parallel Algorithms
• Convergent Regular Splittings for Singular M-Matrices
• Finite Continuous Time Markov Chains
• Hierarchical aggregation of singularly perturbed finite state markov processes
• scientific article; zbMATH DE number 4013703 (Why is no real title available?)
• scientific article; zbMATH DE number 440690 (Why is no real title available?)
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• scientific article; zbMATH DE number 19229 (Why is no real title available?)
• scientific article; zbMATH DE number 19241 (Why is no real title available?)
• scientific article; zbMATH DE number 48923 (Why is no real title available?)
• scientific article; zbMATH DE number 3574935 (Why is no real title available?)
• scientific article; zbMATH DE number 510830 (Why is no real title available?)
• scientific article; zbMATH DE number 510832 (Why is no real title available?)
• Iterative aggregation/disaggregation techniques for nearly uncoupled markov chains
• Limits for the characteristic roots of a matrix. IV. Applications to stochastic matrices
• Numerical Experiments with Iteration and Aggregation for Markov Chains
• Numerical solution of sparse singular systems of equations arising from ergodic markov chains
• Regenerative Analysis and Steady State Distributions for Markov Chains
• The Role of the Group Generalized Inverse in the Theory of Finite Markov Chains
• Theorems on M-splittings of a singular M-Matrix which depend on graph structure
• Upper bounds on the maximum modulus of subdominant eigenvalues of nonnegative matrices

Cited in

(20)

• Alternating two-stage methods for consistent linear systems with applications to the parallel solution of Markov chains
• Exploiting the Toeplitz structure in certain queueing problems
• A cost-effective smoothed multigrid with modified neighborhood-based aggregation for Markov chains
• A multi-cluster time aggregation approach for Markov chains
• Convergence theory of some classes of iterative aggregation/disaggregation methods for computing stationary probability vectors of stochastic matrices
• Multigrid methods combined with low-rank approximation for tensor-structured Markov chains
• Triangular and skew-symmetric splitting method for numerical solutions of Markov chains
• Iterant recombination with one-norm minimization for multilevel Markov chain algorithms via the ellipsoid method
• Multigrid methods for tensor structured Markov chains with low rank approximation
• Algebraic multigrid for Markov chains
• Square and stretch multigrid for stochastic matrix eigenproblems
• On-the-Fly Adaptive Smoothed Aggregation Multigrid for Markov Chains
• A bootstrap algebraic multilevel method for Markov chains
• On the Convergence of a Class of Multilevel Methods for Large Sparse Markov Chains
• scientific article; zbMATH DE number 1226277 (Why is no real title available?)
• Fast multilevel methods for Markov chains.
• Fourier analysis of the aggregation based algebraic multigrid for stochastic matrices
• scientific article; zbMATH DE number 956817 (Why is no real title available?)
• Aggregation Methods for Computing Steady States in Statistical Physics
• Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains

This page was built for publication: On a two-level multigrid solution method for finite Markov chains

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