Comparison of Partitioning Techniques for Two-Level Iterative Solvers on Large, Sparse Markov Chains

DOI10.1137/S1064827598338159zbMath0957.60076OpenAlexW2063333912MaRDI QIDQ4509795

Tuǧrul Dayar, William J. Stewart

Publication date: 19 October 2000

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

Full work available at URL: https://doi.org/10.1137/s1064827598338159

zbMATH Keywords

partitioningMarkov chainspreconditioningKrylov subspace methodsblock SORnear-complete decomposabilityiterative aggregation-disaggregation

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical analysis or methods applied to Markov chains (65C40) Iterative numerical methods for linear systems (65F10) Acceleration of convergence in numerical analysis (65B99)

Related Items

Iterative aggregation/disaggregation methods for computing some characteristics of Markov chains. II: Fast convergence, A geometric view of Krylov subspace methods on singular systems, A parallel solver for large-scale Markov chains, The cross-entropy method with patching for rare-event simulation of large Markov chains, Convergence of multi-level iterative aggregation-disaggregation methods, Block SOR for Kronecker structured representations, Algorithms for an irreducible and lumpable strong stochastic bound, Fast multilevel methods for Markov chains, Physiology and pathology of iterative aggregation–disaggregation methods, Componentwise bounds for nearly completely decomposable Markov chains using stochastic comparison and reordering, Aggregation/disaggregation iterative methods applied to Leontev systems and Markov chains., Lumpable continuous-time stochastic automata networks., Alternating two-stage methods for consistent linear systems with applications to the parallel solution of Markov chains, Convergence theory of some classes of iterative aggregation/disaggregation methods for computing stationary probability vectors of stochastic matrices

Uses Software

• MARCA
• DQGMRES
• ITSOL
• mctoolbox
• SPARSKIT