×

Physiology and pathology of iterative aggregation-disaggregation methods. (English) Zbl 1265.65010

Iterative aggregation-disaggregation (IAD) methods have long been used for computing the stationary distribution vector of Markov chains with a large number of states. In spite of this, many open questions remain concerning the convergence of these algorithms. This paper is an attempt to increase our understanding of IAD methods, mostly through the analysis of a few situations leading to pathological behavior of the iterative process. The important issue of state sorting is also given some consideration. The main findings are the following:
(i) Local convergence is guaranteed for a wide class of IAD methods when the transition matrix is diagonally similar to a symmetric matrix;
(ii) For certain cyclic stochastic matrices (related to permutation matrices) arbitrarily fast divergence of the IAD iteration may occur;
(iii) For the same stochastic matrix, one choice of the aggregation procedure may lead to convergence in just two steps, while another choice can lead to divergence.
The authors identify certain types of “desirable” matrix structures leading to good behavior of IAD methods. In the conclusions, it is mentioned that many questions in the theory of IAD methods remain wide open, even for simple methods.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains

Software:

MARCA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Stewart, Introduction to the Numerical Solution of Markov Chains (1994) · Zbl 0821.65099
[2] Ipsen, Convergence analysis of a PageRank updating algorithm by Langville and Meyer, SIAM Journal on Matrix Analysis and Applications 27 pp 952– (2006) · Zbl 1108.65030
[3] Marek, A note on local and global convergence analysis of iterative aggregation-disaggregation methods, Linear Algebra and Its Applications 413 pp 327– (2006) · Zbl 1087.65030
[4] Pultarová, Local convergence analysis of iterative aggregation-disaggregation methods with polynomial correction, Linear Algebra and Its Applications 421 pp 122– (2007) · Zbl 1117.65015
[5] Pultarová, Necessary and sufficient local convergence condition of one class of iterative aggregation-disaggregation methods, Numerical Linear Algebra with Applications 15 pp 339– (2008) · Zbl 1212.65028
[6] Pultarová, Ordering of matrices for iterative aggregation-disaggregation methods, Lecture Notes in Control and Information Sciences 389 pp 379– (2009) · Zbl 1182.93059
[7] Ipsen, PageRank computation, with special attention to dangling nodes, SIAM Journal on Matrix Analysis and Applications 29 (4) pp 1281– (2007) · Zbl 1156.65038
[8] Langville, A reordering for the PageRank problem, SIAM Journal on Scientific Computing 27 pp 2112– (2006) · Zbl 1103.65048
[9] Langville, Updating Markov chains with an eye on Google’s PageRank, SIAM Journal on Matrix Analysis and Applications 27 (4) pp 968– (2006) · Zbl 1098.60073
[10] Lee CP Golub GH Zenios A 2008 A two-stage algorithm for computing PageRank and multi-stage generalizations
[11] Dayar, State space orderings for Gauss-Seidel in Markov chains revisited, SIAM Journal on Scientific Computing 19 pp 148– (1998) · Zbl 0912.65120
[12] Dayar T 1998 Permuting Markov chains to nearly completely decomposable form
[13] Dayar, Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing 21 pp 1691– (2000) · Zbl 0957.60076
[14] Dayar, On the effects of using the Grassmann-Taksar-Heyman method in iterative aggregation-disaggregation, SIAM Journal on Scientific Computing 17 pp 287– (1996) · Zbl 0840.60062
[15] De Sterck, Multilevel adaptive aggregation for Markov chains, with application to Web ranking, SIAM Journal on Scientific Computing 5 pp 2235– (2008) · Zbl 1173.65028
[16] De Sterck, Smoothed aggregation multigrid for Markov chains, SIAM Journal on Scientific Computing 32 pp 40– (2010) · Zbl 1209.65011
[17] Pultarová, Convergence of multi-level iterative aggregation-disaggregation methods, Journal of Computational and Applied Mathematics 236 (3) pp 354– (2011) · Zbl 1228.65016
[18] Buchholz, On the convergence of a class of multilevel methods for large sparse Markov chains, SIAM Journal on Matrix Analysis and Applications 29 (3) pp 1025– (2007) · Zbl 1148.60050
[19] Marek, Convergence theory of some classes of iterative aggregation-disaggregation methods for computing stationary probability vectors of stochastic matrices, Linear Algebra and Its Applications 363 pp 177– (2003) · Zbl 1018.65048
[20] Berman, Nonnegative Matrices in the Mathematical Sciences, SIAM: Classics in Applied Mathematics 9 pp 130– (1994)
[21] Varga, Springer Series in Computational Mathematics 27, in: Matrix Iterative Analysis (2000) · Zbl 1216.65042
[22] Krieger, Computations with Markov Chains pp 403– (1995)
[23] Mandel, A local convergence proof for the iterative aggregation method, Linear Algebra and Its Applications 51 pp 163– (1983) · Zbl 0494.65014
[24] Marek, Convergence analysis of an iterative aggregation/disaggregation method for computing stationary probability vectors of stochastic matrices, Numerical Linear Algebra with Applications 5 pp 253– (1998) · Zbl 0937.65047
[25] Duff, An implementation of Tarjan’s algorithm for the block triangularization of a matrix, ACM transactions on Mathematical Software 4 pp 137– (1978) · Zbl 0389.65019
[26] Greenbaum, Any nonincreasing convergence curve is possible for GMRES, SIAM Journal on Matrix Analysis and Applications 17 (3) pp 465– (1996) · Zbl 0857.65029
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.