{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T03:21:52Z","timestamp":1787541712347,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>Algebraic multigrid (AMG) is a very efficient iterative solver and preconditioner for large unstructured sparse linear systems. Traditional coarsening schemes for AMG can, however, lead to computational complexity growth as problem size increases, resulting in increased memory use and execution time, and diminished scalability. Two new parallel AMG coarsening schemes are proposed that are based solely on enforcing a maximum independent set property, resulting in sparser coarse grids. The new coarsening techniques remedy memory and execution time complexity growth for various large three-dimensional (3D) problems. If used within AMG as a preconditioner for Krylov subspace methods, the resulting iterative methods tend to converge fast. This paper discusses complexity issues that can arise in AMG, describes the new coarsening schemes, and examines the performance of the new preconditioners for various large 3D problems.<\/jats:p>","DOI":"10.1137\/040615729","type":"journal-article","created":{"date-parts":[[2006,3,24]],"date-time":"2006-03-24T21:00:17Z","timestamp":1143234017000},"page":"1019-1039","source":"Crossref","is-referenced-by-count":156,"title":["Reducing Complexity in Parallel Algebraic Multigrid Preconditioners"],"prefix":"10.1137","volume":"27","author":[{"given":"Hans","family":"De Sterck","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ulrike Meier","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey J.","family":"Heys","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","unstructured":"A. Brandt, S. F. McCormick, and J. W. Ruge,\n                      Algebraic Multigrid (AMG) for Automatic Multigrid Solutions with Application to Geodetic Computations\n                      , Report, Inst. for Computational Studies, Fort Collins, CO, 1982."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142994266066"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Andrew Cleary, Robert Falgout, Van Henson, Jim Jones, Coarse\u2010grid selection for parallel algebraic multigrid, Lecture Notes in Comput. Sci., Vol. 1457, Springer, Berlin, 1998, 104\u20131151670449","DOI":"10.1007\/BFb0018531"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598339402"},{"key":"R6","unstructured":"M. Griebel, B. Metsch, D. Oeltz, and A. Schweitzer,\n                      Coarse grid classification: A parallel coarsening scheme for algebraic multigrid methods\n                      , SIAM J. Sci. Comput., submitted."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(01)00115-5"},{"key":"R8","unstructured":"G. Karypis,\n                      METIS\n                      , http:\/\/www\u2010users.cs.umn.edu\/\u223ckarypis\/metis\/."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0914041"},{"key":"R10","unstructured":"W. Joubert and J. Cullum,\n                      Scalable Algebraic Multigrid on 3500 Processors\n                      , Los Alamos National Laboratory Technical report no. LAUR03\u2010568, Electron. Trans. Numer. Anal., submitted."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00080-1"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Ruge, K. St\u00fcben, Algebraic multigrid, Frontiers Appl. Math., Vol. 3, SIAM, Philadelphia, PA, 1987, 73\u2013130972756","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"R14","unstructured":"K. St\u00fcben,\n                      Algebraic multigrid (AMG): An introduction with applications\n                      , in Multigrid, U. Trottenberg, C. Oosterlee, and A. Sch\u00fcller, eds., Academic Press, San Diego, 2000."},{"key":"R15","volume-title":"Multigrid","author":"Trottenberg U.","year":"2001"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"R. Tuminaro and C. Tong,\n                      Parallel smoothed aggregation multigrid: Aggregation strategies on massively parallel machines\n                      , in Proceedings of the 2000 ACM\/IEEE Conference on Supercomputing, Dallas, 2000.","DOI":"10.1109\/SC.2000.10008"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1002\/nla.375"},{"key":"R18","unstructured":"U. M. Yang,\n                      Parallel algebraic multigrid methods\u2014high performance preconditioners\n                      , in Numerical Solution of Partial Differential Equations on Parallel Computers, A. Bruaset and A. Tveito, eds., Springer\u2010Verlag, New York, 2006."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040615729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:33:18Z","timestamp":1787333598000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040615729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/040615729"],"URL":"https:\/\/doi.org\/10.1137\/040615729","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}