{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:34:35Z","timestamp":1787384075225,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>An algebraic multigrid (AMG) method is presented for the calculation of the stationary probability vector of an irreducible Markov chain. The method is based on standard AMG for nonsingular linear systems, but in a multiplicative, adaptive setting. A modified AMG interpolation formula is proposed that produces a nonnegative interpolation operator with unit row sums. We show how the adoption of a previously described lumping technique maintains the irreducible singular M-matrix character of the coarse-level operators on all levels. Together, these properties are sufficient to guarantee the well-posedness of the algorithm. Numerical results show how it leads to nearly optimal multigrid efficiency for a representative set of test problems.<\/jats:p>","DOI":"10.1137\/090753589","type":"journal-article","created":{"date-parts":[[2010,2,17]],"date-time":"2010-02-17T18:07:17Z","timestamp":1266430037000},"page":"544-562","source":"Crossref","is-referenced-by-count":17,"title":["Algebraic 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":"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,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"F. Bause and P. Kritzinger,\n                      Stochastic Petri Nets\n                      , Verlag Vieweg, Germany, 1996.","DOI":"10.1007\/978-3-663-11521-2"},{"key":"R2","unstructured":"A. Berman and R. J. Plemmons,\n                      Nonnegative Matrices in the Mathematical Sciences\n                      , SIAM, Philadelphia, 1987."},{"key":"R3","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, 1984."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Brandt and D. Ron,\n                      Multigrid solvers and multilevel optimization strategies\n                      , in Multilevel Optimization and VLSICAD, J. Cong and J. R. Shinnerl, eds., Kluwer, Boston, 2003, pp. 1\u201369.","DOI":"10.1007\/978-1-4757-3748-6_1"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/040614402"},{"key":"R6","unstructured":"W. L. Briggs, V. Emden Henson, and S. F. McCormick,\n                      A Multigrid Tutorial\n                      , SIAM, Philadelphia, 2000."},{"key":"R7","unstructured":"G. Chartrand and L. Lesniak,\n                      Graphs & Digraphs\n                      , Chapman and Hall\/CRC, Boca Raton, 2005."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/nla.559"},{"key":"R9","unstructured":"H. De Sterck, T. A. Manteuffel, S. F. McCormick, K. Miller, J. Pearson, J. Ruge, and G. Sanders,\n                      Smoothed aggregation multigrid for Markov chains\n                      , SIAM J. Sci. Comp., to appear."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/070685142"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/040615729"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, New York, 1985.","DOI":"10.1017\/CBO9780511810817"},{"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 ACM SIGMETRICS Performance Evaluation Review 22, http:\/\/portal.acm.org\/citation.cfm?id=183019.183040.","DOI":"10.1145\/183019.183040"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/nla.379"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676110"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/nla.542"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.6.1156"},{"key":"R18","unstructured":"J. W. Ruge,\n                      Algebraic multigrid (AMG) for geodetic survey problems\n                      , in Proceedings of the International Multigrid Conference, Copper Mountain, CO, 1983."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. W. Ruge and K. Stueben,\n                      Algebraic Multigrid (AMG)\n                      , in Multigrid Methods Frontiers Appl. Math., S. F. McCormick, ed., SIAM, Philadelphia, 1987, pp. 73\u2013130.","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Yo. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"R22","unstructured":"W. J. Stewart,\n                      An Introduction to the Numerical Solution of Markov Chains\n                      , Princeton University Press, Princeton, NJ, 1994."},{"key":"R23","unstructured":"W. J. Stewart,\n                      MARCA_Models\n                      , from http:\/\/www4.ncsu.edu\/~billy\/MARCA_Models\/MARCA_Models.html."},{"key":"R24","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":"R25","unstructured":"E. Treister and I. Yavneh,\n                      Square and stretch multigrid for stochastic matrix eigenproblems\n                      , Numer. Linear Algebra Appl., submitted."},{"key":"R26","unstructured":"U. Trottenberg, C. W. Oosterlee, and A. Sch\u00fcller,\n                      Multigrid\n                      , Elsevier, Academic Press, 2001."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/060659272"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090753589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:50:01Z","timestamp":1787334601000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090753589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090753589"],"URL":"https:\/\/doi.org\/10.1137\/090753589","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}