De Sterck, H.; Miller, K.; Treister, E.; Yavneh, I. Fast multilevel methods for Markov chains. (English) Zbl 1265.65009 Numer. Linear Algebra Appl. 18, No. 6, 961-980 (2011). The paper presents some improvements to the multilevel aggregation method of G. Horton and S. T. Leutenegger [“A multi-level solution algorithm for steady-state Markov chains”, in: Proceedings of the 1994 ACM SIGMETRICS conference on measurement and modeling of computer systems, 191–200 (1994; doi:10.1145/183018.183040)] for the numerical solution of the stationary probability vector of discrete finite Markov chains. Instead of an aggregation it is used an algebraic multigrid coarsening procedure and a lumping technique, which preserves the positivity of approximations on all levels. The main adaptive (on-the-fly) iteration scheme combines multiplicative (setup) and additive (solution) phases. The additive parts are cheaper because of frozen restriction and prolongation operators. The idea of the over-correction is adapted: the residual norm and a projection onto the coarse space are utilized instead of the energy norm and smoothing, respectively. Several large scale examples of queuing networks and directed random walks confirm a speedup of the solution process caused by the suggested improvements. Reviewer: Ivana Pultarová (Praha) Cited in 3 Documents MSC: 65C40 Numerical analysis or methods applied to Markov chains 60J22 Computational methods in Markov chains Keywords:Markov chain; stationary probability vector; multigrid; multi-level aggregation; over-correction; iteration scheme; queuing networks; random walks Software:MARCA PDFBibTeX XMLCite \textit{H. De Sterck} et al., Numer. Linear Algebra Appl. 18, No. 6, 961--980 (2011; Zbl 1265.65009) Full Text: DOI References: [1] Horton G Leutenegger ST A multi-level solution algorithm for steady-state Markov chains Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems 1994 191 200 [2] Treister, On-the-fly adaptive smoothed aggregation multigrid for Markov chains, Accepted to SIAM Journal on Scientific Computing (2011) · Zbl 1232.65167 [3] De Sterck, Algebraic multigrid for Markov chains, SIAM Journal on Scientific Computing 32 pp 544– (2010) · Zbl 1210.65016 [4] Stewart, An Introduction to the Numerical Solution of Markov Chains (1994) · Zbl 0821.65099 [5] De Sterck, Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains, Advances in Computational Mathematics (2010) [6] Philippe, Numerical methods in Markov chain modeling, Operations Research 40 (6) pp 1156– (1992) · Zbl 0764.65095 [7] Stewart WJ MARCA Models: A collection of markov chain models 2008 http://www4.ncsu.edu/billy/MARCA_Models/MARCA_Models.html [8] Leutenegger ST Horton G On the utility of the multi-level algorithm for the solution of nearly completely decomposable Markov chains Technical Report 94-44 1994 [9] Krieger, Computations with Markov Chains pp 403– (1995) [10] Takahashi Y A lumping method for numerical calculations of stationary distributions of Markov chains Technical Report B-18 1975 [11] Simon, Aggregation of variables in dynamic systems, Econometrica 29 pp 111– (1961) · Zbl 0121.15103 [12] Chatelin, Acceleration by aggregation of successive approximation methods, Linear Algebra and its Applications 43 pp 17– (1982) · Zbl 0485.65023 [13] Mandel, A local convergence proof for the iterative aggregation method, Linear Algebra and its Applications 51 pp 163– (1983) · Zbl 0494.65014 [14] Koury, Iterative methods for computing stationary distributions of nearly completely decomposable Markov chains, SIAM Journal on Algebraic and Discrete Methods 5 (2) pp 164– (1984) · Zbl 0605.60064 [15] Cao, Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains, Journal of the ACM 32 (3) pp 702– (1985) · Zbl 0628.65145 [16] Haviv, Aggregation/disaggregation methods for computing the stationary distribution of Markov chains, SIAM Journal on Numerical Analysis 24 (4) pp 952– (1987) · Zbl 0637.65147 [17] Krieger, On a two-level multigrid solution method for Markov chains, Linear Algebra and its Applications 223-224 pp 415– (1995) · Zbl 0831.65149 [18] 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 [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] Marek, Algebraic Schwarz methods for the numerical solution of Markov chains, Linear Algebra and its Applications 386 pp 67– (2004) · Zbl 1050.65030 [21] Benzi, Restricted additive Schwarz methods for Markov chains, Numerical Linear Algebra with Applications 00 pp 1– (2000) [22] Saad, Iterative Methods for Sparse Linear Systems (2003) · Zbl 1031.65046 [23] Buchholz, Multilevel solutions for structured Markov chains, SIAM Journal on Matrix Analysis and Applications 22 (2) pp 342– (2000) · Zbl 0967.60075 [24] 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 [25] De Sterck, Smoothed aggregation multigrid for Markov chains, SIAM Journal on Scientific Computing 32 pp 40– (2010) · Zbl 1209.65011 [26] De Sterck, Recursively accelerated multilevel aggregation for Markov chains, SIAM Journal on Scientific Computing 32 (3) pp 1652– (2010) · Zbl 1213.65018 [27] Treister, Square and stretch multigrid for stochastic matrix eigenproblems, Numerical Linear Algebra with Applications 17 pp 229– (2010) · Zbl 1240.65124 [28] Seibold, Performance of algebraic multigrid methods for non-symmetric matrices arising in particle methods, Numerical Linear Algebra with Applications 17 pp 433– (2010) · Zbl 1240.76047 [29] Berman, Nonnegative Matrices in the Mathematical Sciences (1987) [30] Briggs, A Multigrid Tutorial (2000) · Zbl 0958.65128 [31] Brezina, Towards adaptive smooth aggregation ({\(\alpha\)}SA) for nonsymmetric problems, SIAM Journal on Scientific Computing 32 pp 14– (2010) · Zbl 1210.65075 [32] Grassmann, Regenerative analysis and steady-state distributions for Markov chains, Operations Research 33 (5) pp 1107– (1985) · Zbl 0576.60083 [33] Krieger, Modeling and analysis of communication systems based on computational methods for Markov chains, IEEE Journal on Selected Areas in Communications 8 (9) pp 1630– (1990) [34] Brezina, Adaptive algebraic multigrid, SIAM Journal on Scientific Computing 27 pp 1261– (2006) · Zbl 1100.65025 [35] Brezina, Adaptive smoothed aggregation ({\(\alpha\)}SA) multigrid, SIAM Journal on Scientific Computing 25 pp 317– (2005) · Zbl 1075.65042 [36] Klaus S Algebraic multigrid (amg): an introduction with applications Technical Report 70 1999 [37] Vaněk, Modification of two-level algorithm with overcorrection, Applications of Mathematics 37 pp 13– (1992) · Zbl 0753.65028 [38] Blaheta, A multilevel method with overcorrection by aggregation for solving discrete elliptic problems, Journal of Computational and Applied Mathematics 24 pp 227– (1988) · Zbl 0663.65106 [39] Braess, Towards algebraic multigrid for elliptic problems of second order, Computing 55 pp 379– (1995) · Zbl 0844.65088 [40] Brandt, Accelerated multigrid convergence and high-Reynolds recirculating flows, SIAM Journal on Scientific Computing 14 (3) pp 607– (1993) · Zbl 0770.76039 [41] Guillard H Vaněk P An aggregation multigrid solver for convection-diffusion problems on unstructured meshes Technical Report UCD-CCM-130 1998 [42] Zhang, Residual scaling techniques in multigrid, I: equivalence proof, Applied Mathematics and Computation 86 pp 283– (1997) · Zbl 0905.65113 [43] Zhang, Residual scaling techniques in multigrid, II: practical applications, Applied Mathematics and Computation 90 pp 229– (1998) · Zbl 0905.65114 [44] Zhang, Minimal residual smoothing in multi-level iterative method, Applied Mathematics and Computation 84 pp 1– (1997) · Zbl 0877.65017 [45] 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 [46] Barrett, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1993) · Zbl 0814.65030 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.