{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:39Z","timestamp":1787337219265,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>A smoothed aggregation multigrid method is presented for the numerical calculation of the stationary probability vector of an irreducible sparse Markov chain. It is shown how smoothing the interpolation and restriction operators can dramatically increase the efficiency of aggregation multigrid methods for Markov chains that have been proposed in the literature. The proposed smoothing approach is inspired by smoothed aggregation multigrid for linear systems, supplemented with a new lumping technique that assures well-posedness of the coarse-level problems: the coarse-level operators are singular M-matrices on all levels, resulting in strictly positive coarse-level corrections on all levels. Numerical results show how these methods lead to nearly optimal multigrid efficiency for an extensive set of test problems, both when geometric and algebraic aggregation strategies are used.<\/jats:p>","DOI":"10.1137\/080719157","type":"journal-article","created":{"date-parts":[[2010,2,5]],"date-time":"2010-02-05T18:13:52Z","timestamp":1265393632000},"page":"40-61","source":"Crossref","is-referenced-by-count":35,"title":["Smoothed Aggregation Multigrid for Markov Chains"],"prefix":"10.1137","volume":"32","author":[{"given":"H.","family":"De Sterck","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T. A.","family":"Manteuffel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. F.","family":"McCormick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Pearson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Ruge","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G.","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,5]]},"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","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 (Nashville, TN), 1994, pp. 191\u2013200.","DOI":"10.1145\/183018.183040"},{"key":"R5","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, Dordrecht, The Netherlands, 1995, pp. 425\u2013443.","DOI":"10.1007\/978-1-4615-2241-6_24"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/070685142"},{"key":"R7","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, 1975."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0605019"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90003-2"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/49.62851"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00166-O"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(199807\/08)5:4<253::AID-NLA124>3.0.CO;2-B"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598338159"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00333-6"},{"key":"R15","unstructured":"A. Brandt, S. F. McCormick, and J. W. Ruge,\n                      Algebraic multigrid (AMG) for sparse matrix equations\n                      , in Sparsity and Its Applications, D. J. Evans, ed., Cambridge University Press, Cambridge, UK, 1984."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. W. Ruge and K. St\u00fcben,\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":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/050626272"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/040614402"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1002\/nla.575"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238511"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/s211-001-8015-y"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/060659272"},{"key":"R23","unstructured":"C. Isensee and G. Horton,\n                      A multi-level method for the steady state solution of Markov chains\n                      , Simulation und Visualisierung 2004, T. Schulze, S. Schlechtweg, and V. Hinz, eds., SCS Publishing House e.V., Erlangen, Germany, 2004, pp. 191\u2013202."},{"key":"R24","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd,\n                      The PageRank Citation Ranking: Bringing Order to the Web\n                      , Technical Report 1999-0120, Computer Science Department, Stanford University, Stanford, CA, 1999."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"A. N. Langville and C. D. Meyer,\n                      Google's PageRank and Beyond: The Science of Search Engine Rankings\n                      , Princeton University Press, Princeton, NJ, 2006.","DOI":"10.1515\/9781400830329"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"R27","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":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/060678397"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/nla.593"},{"key":"R30","unstructured":"L. Lovasz,\n                      Random walks on graphs: A survey\n                      , in Combinatorics, Paul Erd\u0151s Is Eighty, Vol. 2, Bolyai Soc. Math. Stud. 2, J\u00e1nos Bolyai Mathematical Society, Budapest, 1996, pp. 353\u2013397."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90095-0"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598339402"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080719157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:50:14Z","timestamp":1787334614000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080719157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080719157"],"URL":"https:\/\/doi.org\/10.1137\/080719157","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}