{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T16:45:14Z","timestamp":1791909914287,"version":"4.3.4"},"reference-count":25,"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":[[2018,1]]},"abstract":"<jats:p>In this paper, we consider a classical algebraic multigrid (AMG) form of optimal interpolation that directly minimizes the two-grid convergence rate and compare it with a so-called ideal interpolation that minimizes a weak approximation property of the coarse space. We study compatible relaxation type estimates for the quality of the coarse grid and derive a new sharp measure using optimal interpolation that provides a guaranteed lower bound on the convergence rate of the resulting two-grid method for a given grid. In addition, we design a generalized bootstrap AMG setup algorithm that computes a sparse approximation to the optimal interpolation matrix. We demonstrate numerically that the bootstrap AMG method with sparse interpolation matrix (and spanning multiple levels) converges faster than the two-grid method with the standard ideal interpolation (a dense matrix) for various scalar diffusion problems with highly varying diffusion coefficient.<\/jats:p>","DOI":"10.1137\/17m1123456","type":"journal-article","created":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T09:29:30Z","timestamp":1527067770000},"page":"A1473-A1493","source":"Crossref","is-referenced-by-count":30,"title":["Optimal Interpolation and Compatible Relaxation in Classical Algebraic Multigrid"],"prefix":"10.1137","volume":"40","author":[{"given":"James","family":"Brannick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fei","family":"Cao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karsten","family":"Kahl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert D.","family":"Falgout","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaozhe","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,22]]},"reference":[{"key":"atypb1","first-page":"1","volume":"10","author":"Brandt A.","year":"2000","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb2","first-page":"1","volume-title":"Multiscale and Multiresolution Methods: Theory and Applications","author":"Brandt A.","year":"2001"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.4208\/nmtma.2015.w06si"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/090752973"},{"key":"atypb5","volume-title":"Technical report","author":"Brandt A.","year":"1983"},{"key":"atypb6","first-page":"257","volume-title":"Sparsity and Its Applications (Loughborough","author":"Brandt A.","year":"1983"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/090772216"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/130934660"},{"key":"atypb9","first-page":"472","volume":"44","author":"Brannick J.","year":"2015","journal-title":"Electron. Trans. Numer. Anal."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-34469-8_2"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502418598"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/040614402"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"R. Eymard, T. Gallou\u00ebt, and R. Herbin,\n                      Finite volume methods\n                      , in Handbook of Numerical Analysis 7, Elsevier, Amsterdam, 2000, pp. 713-1018.","DOI":"10.1016\/S1570-8659(00)07005-8"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/nla.437"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142903429742"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1142\/9789812836021_0015"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1080\/03081088508817636"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/cnm.1630080909"},{"key":"atypb20","volume-title":"Technical report, CU Denver","author":"Mandel J.","year":"1998"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1201\/9780203908518"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238511"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598334277"},{"key":"atypb24","volume-title":"The Algebraic Eigenvalue Problem","author":"Wilkinson J.","year":"1965"},{"key":"atypb25","volume-title":"Algebraic Multigrid Methods, preprint, arXiv:1611.01917","author":"Xu J.","year":"2016"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9582-6"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1123456","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:47:15Z","timestamp":1787327235000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1123456"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1123456"],"URL":"https:\/\/doi.org\/10.1137\/17m1123456","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}