×

Convergence of multi-level iterative aggregation-disaggregation methods. (English) Zbl 1228.65016

Summary: This paper introduces an error propagation formula of a certain class of multi-level iterative aggregation-disaggregation (IAD) methods for numerical solutions of stationary probability vectors of discrete finite Markov chains. The formula can be used to investigate convergence by computing the spectral radius of the error propagation matrix for specific Markov chains. Numerical experiments indicate that the same type of the formula could be used for a wider class of the multi-level IAD methods. Using the formula we show that for given data there is no relation between convergence of two-level and of multi-level IAD 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] Dayar, T.; Stewart, W. J., Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing, 21, 1691-1705 (2000) · Zbl 0957.60076
[2] Stewart, W. J., Introduction to the Numerical Solutions of Markov Chains (1994), Princeton University Press: Princeton University Press Princeton
[3] T. Dayar, Permuting Markov chains to nearly completely decomposable form, Technical Report BU-CEIS-9808, Department of Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, August 1998.; T. Dayar, Permuting Markov chains to nearly completely decomposable form, Technical Report BU-CEIS-9808, Department of Computer Engineering and Information Science, Bilkent University, Ankara, Turkey, August 1998.
[4] Gusak, O.; Dayar, T.; Fourneau, J.-M., Stochastic automata networks and near complete decomposability, SIAM Journal on Matrix Analysis and Applications, 23, 581-599 (2001) · Zbl 0992.60078
[5] Dayar, T., State space orderings for Gauss-Seidel in Markov chains revisited, SIAM Journal on Scientific Computing, 19, 148-154 (1998) · Zbl 0912.65120
[6] Horton, G.; Leutenegger, S. T., A multi-level solution algorithm for steady-state Markov chains, ACM SIGMETRICS Performance Evaluation Review, 22 (1994)
[7] De Sterck, H.; Manteuffel, T. A.; McCormick, S. F.; Nguyen, Q.; Ruge, J., Multilevel adaptive aggregation for Markov chains, with application to web ranking, SIAM Journal on Scientific Computing, 5, 2235-2262 (2008) · Zbl 1173.65028
[8] De Sterck, H.; Manteuffel, T. A.; McCormick, S. F.; Miller, K.; Pearson, J.; Ruge, J.; Sanders, G., Smoothed aggregation multigrid for Markov chains, SIAM Journal on Scientific Computing, 32, 40-61 (2010) · Zbl 1209.65011
[9] Ipsen, I. C.F.; Kirkland, S., Convergence analysis of a PageRank updating algorithm by Langville and Meyer, SIAM Journal on Matrix Analysis and Applications, 27, 952-967 (2006) · Zbl 1108.65030
[10] Ipsen, I. C.F.; Selee, T. M., PageRank computation, with special attention to dangling nodes, SIAM Journal on Matrix Analysis and Applications, 29, 4, 1281-1296 (2007) · Zbl 1156.65038
[11] Langville, A. N.; Meyer, C. D., A reordering for the PageRank problem, SIAM Journal on Scientific Computing, 27, 2112-2120 (2006) · Zbl 1103.65048
[12] Buchholz, P.; Dayar, T., On the convergence of a class of multilevel methods for large sparse Markov chains, SIAM Journal on Matrix Analysis and Applications, 29, 1025-1049 (2007) · Zbl 1148.60050
[13] Marek, I.; Mayer, P., Convergence theory of some classes of iterative aggregation-disaggregation methods for computing stationary probability vectors of stochastic matrices, Linear Algebra and Its Applications, 363, 177-200 (2003) · Zbl 1018.65048
[14] Marek, I.; Mayer, P., Convergence analysis of an iterative aggregation/disaggregation method for computing stationary probability vectors of stochastic matrices, Numerical Linear Algebra with Applications, 5, 253-274 (1998) · Zbl 0937.65047
[15] Krieger, U. R., Numerical solution of large finite Markov chains by algebraic multigrid techniques, (Stewart, W. J., Computations with Markov Chains (1995), Kluwer Academic Publisher: Kluwer Academic Publisher Boston), 403-424 · Zbl 0860.90061
[16] Marek, I.; Pultarová, I., A note on local and global convergence analysis of iterative aggregation-disaggregation methods, Linear Algebra and Its Applications, 413, 327-341 (2006) · Zbl 1087.65030
[17] Pultarová, I., Local convergence analysis of iterative aggregation-disaggregation methods with polynomial correction, Linear Algebra and Its Applications, 421, 122-137 (2007) · Zbl 1117.65015
[18] Pultarová, I., Necessary and sufficient local convergence condition of one class of iterative aggregation-disaggregation methods, Numerical Linear Algebra with Applications, 15, 339-354 (2008) · Zbl 1212.65028
[19] I. Pultarová, I. Marek, Physiology and pathology of iterative aggregation-disaggregation methods (submitted for publication).; I. Pultarová, I. Marek, Physiology and pathology of iterative aggregation-disaggregation methods (submitted for publication).
[20] Vaněk, P.; Brezina, M.; Mandel, J., Convergence of algebraic multigrid based on smoothed aggregation, Computing, 56, 179-196 (1998)
[21] Vaněk, P.; Brezina, M.; Tezaur, R., Two-grid method for linear elasticity on unstructured meshes, SIAM Journal on Scientific Computing, 21, 900-923 (1999) · Zbl 0952.65099
[22] Varga, R. S., (Matrix Iterative Analysis. Matrix Iterative Analysis, Springer Series in Computational Mathematics, vol. 27 (2000), Springer-Verlag: Springer-Verlag New York) · Zbl 0998.65505
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.