Fast multilevel methods for Markov chains

Hans De Sterck, Killian Miller, Eran Treister, Irad Yavneh

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

This paper describes multilevel methods for the calculation of the stationary probability vector of large, sparse, irreducible Markov chains. In particular, several recently proposed significant improvements to the multilevel aggregation method of Horton and Leutenegger are described and compared. Furthermore, we propose a very simple improvement of that method using an over-correction mechanism. We also compare with more traditional iterative methods for Markov chains such as weighted Jacobi, two-level aggregation/disaggregation, and preconditioned stabilized biconjugate gradient and generalized minimal residual method. Numerical experiments confirm that our improvements lead to significant speedup, and result in multilevel methods that are competitive with leading iterative solvers for Markov chains.

Original languageEnglish
Pages (from-to)961-980
Number of pages20
JournalNumerical Linear Algebra with Applications
Volume18
Issue number6
DOIs
Publication statusPublished - Nov 2011
Externally publishedYes

Keywords

  • Markov chain
  • Multigrid
  • Multilevel aggregation
  • Over-correction
  • Stationary probability vector

Cite this