Algebraic multigrid for Markov Chains

H. De Sterck, T. A. Manteuffel, S. F. McCgrmick, K. Miller, J. Ruge, G. Sanders

Research output: Contribution to journalArticleResearchpeer-review

16 Citations (Scopus)

Abstract

An algebraic multigrid (AMG) method is presented for the calculation of the stationary probability vector of an irreducible Markov chain. The method is based on standard AMG for nonsingular linear systems, but in a multiplicative, adaptive setting. A modified AMG interpolation formula is proposed that produces a nonnegative interpolation operator with unit row sums. We show how the adoption of a previously described lumping technique maintains the irreducible singular M-matrix character of the coarse-level operators on all levels. Together, these properties are sufficient to guarantee the well-posedness of the algorithm. Numerical results show how it leads to nearly optimal multigrid efficiency for a representative set of test problems.

Original languageEnglish
Pages (from-to)544-562
Number of pages19
JournalSIAM Journal on Scientific Computing
Volume32
Issue number2
DOIs
Publication statusPublished - 2010
Externally publishedYes

Keywords

  • Algebraic multigrid
  • Markov chain
  • Multilevel method
  • Stationary probability vector

Cite this

De Sterck, H., Manteuffel, T. A., McCgrmick, S. F., Miller, K., Ruge, J., & Sanders, G. (2010). Algebraic multigrid for Markov Chains. SIAM Journal on Scientific Computing, 32(2), 544-562. https://doi.org/10.1137/090753589