{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T04:12:01Z","timestamp":1787371921857,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>A recursive acceleration method is proposed for multiplicative multilevel aggregation algorithms that calculate the stationary probability vector of large, sparse, and irreducible Markov chains. Pairs of consecutive iterates at all branches and levels of a multigrid W cycle with simple, nonoverlapping aggregation are recombined to produce improved iterates at those levels. This is achieved by solving quadratic programming problems with inequality constraints: the linear combination of the two iterates is sought that has a minimal two-norm residual, under the constraint that all vector components are nonnegative. It is shown how the two-dimensional quadratic programming problems can be solved explicitly in an efficient way. The method is further enhanced by windowed top-level acceleration of the W cycles using the same constrained quadratic programming approach. Recursive acceleration is an attractive alternative to smoothing the restriction and interpolation operators, since the operator complexity is better controlled and the probabilistic interpretation of coarse-level operators is maintained on all levels. Numerical results are presented showing that the resulting recursively accelerated multilevel aggregation cycles for Markov chains, combined with top-level acceleration, converge significantly faster than W cycles and lead to close-to-linear computational complexity for challenging test problems.<\/jats:p>","DOI":"10.1137\/090770114","type":"journal-article","created":{"date-parts":[[2010,6,9]],"date-time":"2010-06-09T18:05:21Z","timestamp":1276106721000},"page":"1652-1671","source":"Crossref","is-referenced-by-count":14,"title":["Recursively Accelerated Multilevel Aggregation for Markov Chains"],"prefix":"10.1137","volume":"32","author":[{"given":"H.","family":"De Sterck","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G.","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Winlaw","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,6,9]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. Berman and R. J. Plemmons,\n                      Nonnegative Matrices in the Mathematical Sciences\n                      , SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611971262"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.6.1156"},{"key":"R3","unstructured":"W. J. Stewart,\n                      An Introduction to the Numerical Solution of Markov Chains\n                      , Princeton University Press, Princeton, NJ, 1994."},{"key":"R4","unstructured":"Y. Takahashi,\n                      A Lumping Method for Numerical Calculations of Stationary Distributions of Markov Chains\n                      , Research report B-18, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1975."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0605019"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90003-2"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/49.62851"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00166-O"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(199807\/08)5:4<253::AID-NLA124>3.0.CO;2-B"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598338159"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00333-6"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"W. L. Briggs, V. E. Henson, and S. F. McCormick,\n                      A Multigrid Tutorial\n                      , 2nd ed., SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719505"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"G. Horton and S. T. Leutenegger,\n                      A multi-level solution algorithm for steady-state Markov chains\n                      , in Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 1994, pp. 191\u2013200.","DOI":"10.1145\/183018.183040"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"S. T. Leutenegger and G. Horton,\n                      On the utility of the multi-level algorithm for the solution of nearly completely decomposable Markov chains\n                      , in Numerical Solution of Markov Chains, W. Stewart, ed., Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995, pp. 425\u2013443.","DOI":"10.1007\/978-1-4615-2241-6_24"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/070685142"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/050626272"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/040614402"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/080719157"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1002\/nla.542"},{"key":"R20","unstructured":"Y. Notay,\n                      An aggregation-based algebraic multigrid method\n                      , Electron. Trans. Numer. Anal., to appear."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598338093"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J. Ruge and K. Stueben,\n                      Algebraic multigrid\n                      , in Multigrid Methods, Frontiers Appl. Math. 3, S. F. McCormick, ed., SIAM, Philadelphia, 1987, pp. 73\u2013130.","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/090753589"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/nla.708"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"R26","unstructured":"P. Van\u011bk, J. Mandel, and M. Brezina,\n                      Algebraic Multigrid on Unstructured Meshes\n                      , Technical report UCD-CCM-034, Mathematics Department, University of Colorado at Denver, Denver, CO, 1994."},{"key":"R27","first-page":"271","volume":"6","author":"Washio T.","year":"1997","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R28","unstructured":"H. De Sterck, T. A. Manteuffel, K. Miller, and G. Sanders,\n                      Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains\n                      , Adv. Comput. Math., to appear."},{"key":"R29","unstructured":"P. E. Gill, W. Murray, and M. H. Wright,\n                      Practical Optimization\n                      , Academic Press, London, 1981."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676110"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090770114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:16:58Z","timestamp":1787329018000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090770114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090770114"],"URL":"https:\/\/doi.org\/10.1137\/090770114","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}