Smoothed Aggregation Multigrid for Markov Chains

A smoothed aggregation multigrid method is presented for the numerical calculation of the stationary probability vector of an irreducible sparse Markov chain. It is shown how smoothing the interpolation and restriction operators can dramatically increase the efficiency of aggregation multigrid metho...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific computing 2010-01, Vol.32 (1), p.40-61
Main Authors: De Sterck, H, Manteuffel, T A, McCormick, S F, Miller, K, Pearson, J, Ruge, J, Sanders, G
Format: Article
Language:English
Subjects:
Agglomeration
Algebra
Computational efficiency
Linear systems
Markov analysis
Markov chains
Mathematical analysis
Multigrid methods
Operators
Smoothing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A smoothed aggregation multigrid method is presented for the numerical calculation of the stationary probability vector of an irreducible sparse Markov chain. It is shown how smoothing the interpolation and restriction operators can dramatically increase the efficiency of aggregation multigrid methods for Markov chains that have been proposed in the literature. The proposed smoothing approach is inspired by smoothed aggregation multigrid for linear systems, supplemented with a new lumping technique that assures well-posedness of the coarse-level problems: the coarse-level operators are singular M-matrices on all levels, resulting in strictly positive coarse-level corrections on all levels. Numerical results show how these methods lead to nearly optimal multigrid efficiency for an extensive set of test problems, both when geometric and algebraic aggregation strategies are used. [PUBLICATION ABSTRACT]
ISSN:1064-8275
1095-7197
DOI:10.1137/080719157