{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T05:58:35Z","timestamp":1787378315047,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>This work concerns the development of an algebraic multilevel method for computing state vectors of Markov chains. We present an efficient bootstrap algebraic multigrid (AMG) method for this task. In our proposed approach, we employ a multilevel eigensolver, with interpolation built using ideas based on compatible relaxation, algebraic distances, and least squares fitting of test vectors. Our adaptive variational strategy for computation of the state vector of a given Markov chain is then a combination of this multilevel eigensolver and an associated additive multilevel preconditioned correction process. We show that the bootstrap AMG eigensolver by itself can efficiently compute accurate approximations to the steady state vector. An additional benefit of the bootstrap approach is that it yields an accurate interpolation operator for many other eigenmodes. This in turn allows for the use of the resulting multigrid hierarchy as a preconditioner to accelerate the generalized minimal residual (GMRES) iteration for computing an additive correction equation for the approximation to the steady state vector. Unlike other existing multilevel methods for Markov chains, our method does not employ any special processing of the coarse-level systems to ensure that stochastic properties of the fine-level system are maintained there. The proposed approach is applied to a range of test problems involving nonsymmetric M-matrices arising from stochastic matrices and showing promising results.<\/jats:p>","DOI":"10.1137\/100791816","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T18:27:16Z","timestamp":1323800836000},"page":"3425-3446","source":"Crossref","is-referenced-by-count":10,"title":["A Bootstrap Algebraic Multilevel Method for Markov Chains"],"prefix":"10.1137","volume":"33","author":[{"given":"Matthias","family":"Bolten","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Achi","family":"Brandt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Brannick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Frommer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karsten","family":"Kahl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ira","family":"Livshits","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. Berman and R. J. Plemmons,\n                      Nonnegative Matrices in the Mathematical Sciences\n                      , Classics Appl. Math. 9, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611971262"},{"key":"R2","first-page":"1","volume":"10","author":"Brandt A.","year":"2000","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R3","unstructured":"A. Brandt,\n                      Multiscale scientific computation: Review\n                      2001, in Multiscale and MultiresolutionMethods: Theory and Applications, T. Barth, T. Chan, and R. Haimes, eds., Springer-Verlag, Heidelberg, 2001, pp. 1\u201396. Also available at www.wisdom.weizmann.ac.il\/~achi\/review00.ps."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Brandt,\n                      Principles of systematic upscaling\n                      , in Bridging the Scales in Science and Engineering, J. Fish, ed., Oxford University Press, Oxford, UK, 2008, pp. 193\u2013215.","DOI":"10.1093\/acprof:oso\/9780199233854.003.0007"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/090752973"},{"key":"R6","unstructured":"J. Brannick,\n                      Adaptive Algebraic Multigrid Coarsening Strategies\n                      , Ph.D. thesis, Department of Applied Mathematics, University of Colorado at Boulder, Boulder, CO, 2005."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/090772216"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/050626272"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898342419"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0074-2"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/060651161"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(82)90242-7"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/080719157"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/090753589"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/070685142"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/090770114"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142903429742"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/nla.437"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0724062"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/nla.737"},{"key":"R21","unstructured":"S. Kaczmarz,\n                      Angen\u00e4herte Aufl\u00f6sung von Systemen linearer Gleichungen\n                      , Bull. Internat. Acad. Polon. Sci. Lettres A, (1937), pp. 335\u2013357."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/49.62851"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.147"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/nla.378"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/070684197"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(83)90157-X"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.08.001"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"E. Seneta,\n                      Non-negative Matrices and Markov Chains\n                      , 2nd rev. ed., Springer Ser. Statist., Springer, Heidelberg, New York, 1981.","DOI":"10.1007\/0-387-32792-4"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"R31","unstructured":"W. J. Stewart,\n                      Introduction to the Numerical Solution of Markov Chains\n                      , Princeton University Press, Princeton, NJ, 1994."},{"key":"R32","unstructured":"Y. Takahashi,\n                      A Lumping Method for Numerical Calculations of Stationary Distributions of Markov Chains\n                      , Tech. Report B-18, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, 1975."},{"key":"R33","unstructured":"U. Trottenberg, C. Oosterlee, and A. Sch\u00fcller,\n                      Multigrid\n                      , Academic Press, San Diego, 2001."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/060659272"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894262339"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100791816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:23:52Z","timestamp":1787325832000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100791816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100791816"],"URL":"https:\/\/doi.org\/10.1137\/100791816","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}