×

Square and stretch multigrid for stochastic matrix eigenproblems. (English) Zbl 1240.65124

Summary: A novel multigrid algorithm for computing the principal eigenvector of column-stochastic matrices is developed. The method is based on an approach originally introduced by G. Horton and S. T. Leutenegger [“A multi-level solution algorithm for steady-state Markov chains”, ACM SIGMETRICS Performance Evaluation Review 22, No. 1, 191–200 (1994; doi:10.1145/183019.183040)] in which the coarse-grid problem is adapted to yield a better and better coarse representation of the original problem. A special feature of the present approach is the squaring of the stochastic matrix – followed by a stretching of its spectrum – just prior to the coarse-grid correction process. This procedure is shown to yield good convergence properties, even though a cheap and simple aggregation is used for the restriction and prolongation matrices, which is important for maintaining competitive computational costs. A second special feature is a bottom-up procedure for defining coarse-grid aggregates.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15B51 Stochastic matrices
65C40 Numerical analysis or methods applied to Markov chains
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

Software:

MARCA; MVMRWK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandt, Multigrid methods for differential eigenproblems, SIAM Journal on Scientific Computing 4 pp 655– (1983) · Zbl 0517.65083
[2] Livne, Multiscale Computational Methods in Chemistry and Physics (2001)
[3] McCormick, Multilevel adaptive methods for elliptic eigenproblems: a two-level convergence theory, SIAM Journal on Numerical Analysis 31 (6) pp 1731– (1994) · Zbl 0816.65076
[4] Borzi, Algebraic multigrid methods for solving generalized eigenvalue problems, International Journal for Numerical Methods in Engineering 65 (8) pp 1186– (2006)
[5] Brandt, Multilevel Optimization and VLSICAD pp 1– (2003)
[6] Ruge J. Algebraic multigrid (AMG) for geodetic survey problems. Proceedings of the International Multigrid Conference, Copper Mountain, CO, 1983.
[7] Brandt, Sparsity and its Applications pp 257– (1984)
[8] Takahashi Y. A lumping method for numerical calculations of stationary distributions of Markov chains. Technical Report Research Report B-18, Department of Information Sciences, Tokyo Institute of Technology, 1975.
[9] Horton, A multi-level solution algorithm for steady-state Markov chains, Performance Evaluation Review 22 pp 191– (1994)
[10] De Sterck, Multilevel adaptive aggregation for Markov chains, with application to web ranking, SIAM Journal on Scientific Computing 30 pp 2235– (2008) · Zbl 1173.65028
[11] De Sterck, Algebraic multigrid for Markov chains, SIAM Journal on Scientific Computing (2009)
[12] Virnik, An algebraic multigrid preconditioner for a class of singular M-matrices, SIAM Journal on Scientific Computing 29 (5) pp 1982– (2007) · Zbl 1155.65037
[13] De Sterck, Smoothed aggregation multigrid for Markov chains, SIAM Journal on Scientific Computing (2009)
[14] Kamvar S, Haveliwala T, Manning C, Golub G. Extrapolation methods for accelerating pagerank computations. Proceedings of the 12th International World Wide Web Conference, Budapest, Hungary, 20-24 May 2003.
[15] Sidi, Vector extrapolation methods with applications to solution of large systems of equations and to pagerank computations, Computers and Mathematics with Applications 56 pp 1– (2008) · Zbl 1145.65312
[16] Horn, Matrix Analysis (1985) · Zbl 0576.15001
[17] Notay, Aggregation-based algebraic multilevel preconditioning, SIAM Journal on Matrix Analysis and Applications 27 pp 998– (2006) · Zbl 1102.65053
[18] Notay Y. An aggregation-based algebraic multigrid method. Technical Report GANMN 08-02, Universite Libre de Bruxelles, Brussels, Belgium, 2008 (revised 2009). · Zbl 1206.65133
[19] Philippe, Numerical methods in Markov chain modeling, Journal of Operations Research 40 (6) pp 1156– (1992) · Zbl 0764.65095
[20] Stewart WJ. MARCA_models. Available from: http://www4.ncsu.edu/billy/MARCA/marca.html.
[21] Stewart G. Matrix generator MVMRWK. Available from: http://math.nist.gov/MatrixMarket/data/NEP/mvmrwk/mvmrwk.html.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.