{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:43:15Z","timestamp":1787330595201,"version":"build-2736575974"},"reference-count":64,"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":[[2010,1]]},"abstract":"<jats:p>In this article, we present a parallel geometric multigrid algorithm for solving variable-coefficient elliptic partial differential equations on the unit box (with Dirichlet or Neumann boundary conditions) using highly nonuniform, octree-based, conforming finite element discretizations. Our octrees are 2:1 balanced, that is, we allow no more than one octree-level difference between octants that share a face, edge, or vertex. We describe a parallel algorithm whose input is an arbitrary 2:1 balanced fine-grid octree and whose output is a set of coarser 2:1 balanced octrees that are used in the multigrid scheme. Also, we derive matrix-free schemes for the discretized finite element operators and the intergrid transfer operations. The overall scheme is second-order accurate for sufficiently smooth right-hand sides and material properties; its complexity for nearly uniform trees is $\\mathcal{O}(\\frac{N}{n_p}\\log\\frac{N}{n_p})+\\mathcal{O}(n_p\\log n_p)$, where N is the number of octree nodes and $n_p$ is the number of processors. Our implementation uses the Message Passing Interface standard. We present numerical experiments for the Laplace and Navier (linear elasticity) operators that demonstrate the scalability of our method. Our largest run was a highly nonuniform, 8-billion-unknown, elasticity calculation using 32,000 processors on the Teragrid system, \u201cRanger,\u201d at the Texas Advanced Computing Center. Our implementation is publically available in the Dendro library, which is built on top of the PETSc library from Argonne National Laboratory.<\/jats:p>","DOI":"10.1137\/090747774","type":"journal-article","created":{"date-parts":[[2010,5,21]],"date-time":"2010-05-21T18:10:20Z","timestamp":1274465420000},"page":"1361-1392","source":"Crossref","is-referenced-by-count":66,"title":["A Parallel Geometric Multigrid Method for Finite Elements on Octree Meshes"],"prefix":"10.1137","volume":"32","author":[{"given":"Rahul S.","family":"Sampath","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Biros","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,5,21]]},"reference":[{"key":"R1","unstructured":"M. F. Adams, H. H. Bayraktar, T. M. Keaveny, and P. Papadopoulos,\n                      Ultrascalable implicit finite element analyses in solid mechanics with over a half a billion degrees of freedom\n                      , in Proceedings of the 2004 ACM\/IEEE Conference on Supercomputing, ACM\/IEEE, Pittsburgh, PA, ACM, New York, 2004."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Adams and J. W. Demmel,\n                      Parallel multigrid solver for 3d unstructured finite element problems\n                      , in Proceedings of the 1999 ACM\/IEEE Conference on Supercomputing, Portland, OR, ACM Press, New York, 1999.","DOI":"10.1145\/331532.331559"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"V. Akcelik, J. Bielak, G. Biros, I. Epanomeritakis, A. Fernandez, O. Ghattas, E. J. Kim, J. Lopez, D. R. O'Hallaron, T. Tu, and J. Urbanic,\n                      High resolution forward and inverse earthquake modeling on terascale computers\n                      , in Proceedings of the 2003 ACM\/IEEE Conference on Supercomputing, Phoenix, AZ, ACM, New York, 2003.","DOI":"10.1145\/1048935.1050202"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-7225(02)00014-9"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"W. K. Anderson, W. D. Gropp, D. K. Kaushik, D. E. Keyes, and B. F. Smith,\n                      Achieving high sustained performance in an unstructured mesh CFD application\n                      , in Proceedings of the 1999 ACM\/IEEE Conference on Supercomputing, 1999, ACM, New York, pp. 69\u201369.","DOI":"10.1145\/331532.331600"},{"key":"R6","unstructured":"S. Balay, K. Buschelman, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, B. F. Smith, and H. Zhang,\n                      PETSc home page\n                      , http:\/\/www.mcs.anl.gov\/petsc, 2001."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0595040-2"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684380"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. Becker, M. Braack, and T. Richter,\n                      Parallel multigrid on locally refined meshes\n                      , in Reactive Flows, Diffusion and Transport, Springer, Berlin, 2007, pp. 77\u201392.","DOI":"10.1007\/978-3-540-28396-6_4"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1506(200009)7:6<363::AID-NLA202>3.0.CO;2-V"},{"key":"R11","unstructured":"B. Bergen, F. Hulsemann, and U. Rude,\n                      Is $1.7\\times10^{10}$ unknowns the largest finite element system that can be solved today?\n                      , in Proceedings of the 2005 ACM\/IEEE Conference on Supercomputing, IEEE, Washington, DC, 2005."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000303"},{"key":"R13","unstructured":"M. Bittencourt and R. Feij'oo,\n                      Non-nested multigrid methods in finite element linear structural analysis\n                      , in Virtual Proceedings of the 8th Copper Mountain Conference on Multigrid Methods, 1997."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0720066"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1988-0930228-6"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1023042-6"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"S. C. Brenner and L. R. Scott,\n                      The mathematical theory of finite element methods\n                      , in Texts Appl. Math. 15, Springer, New York, 1994.","DOI":"10.1007\/978-1-4757-4338-8"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"W. L. Briggs, V. E. Henson, and S. F. McCormick,\n                      A Multigrid Tutorial 2nd ed.\n                      , SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719505"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"H.J. Bungartz, M. Mehl, and T. Weinzierl,\n                      A parallel adaptive Cartesian PDE solver using space\u2013filling curves\n                      , in Parallel Processing, 12th International Euro-Par Conference, W. E. Nagel, W. V. Walter, and W. Lehner, eds., Lecture Notes in Comput. Sci. 4128, Springer, Berlin, 2006, pp. 1064\u20131074.","DOI":"10.1007\/11823285_112"},{"key":"R20","unstructured":"P. M. Campbell, K. D. Devine, J. E. Flaherty, L. G. Gervasio, and J. D. Teresco,\n                      Dynamic Octree Load Balancing Using Space-Filling Curves\n                      , Technical report CS-03-01, Department of Computer Science, Williams College, Williamstown, MA, 2003."},{"key":"R21","unstructured":"W. M. Deen,\n                      Analysis of Transport Phenomena\n                      , Topics in Chemical Engineering, Oxford University Press, New York, 1998."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(82)90057-2"},{"key":"R23","unstructured":"R. Falgout, A. Cleary, J. Jones, E. Chow, V. Henson, C. Baldwin, P. Brown, P. Vassilevski, and U. M. Yang,\n                      Hypre home page\n                      , http:\/\/acts.nersc.gov\/hypre, 2001."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2006.105"},{"key":"R25","unstructured":"M. Gee, C. Siefert, J. Hu, R. Tuminaro, and M. Sala,\n                      ML $5.0$ Smoothed Aggregation User's Guide\n                      , Technical report SAND2006-2649, Sandia National Laboratories, Albuquerque, NM, 2006."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/218\/03006"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.253"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00020-4"},{"key":"R29","unstructured":"D. J. Griffiths,\n                      Introduction to Electrodynamics\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1999."},{"key":"R30","unstructured":"D. J. Griffiths,\n                      Introduction to Quantum Mechanics\n                      , Prentice-Hall, Englewood Cliffs, NJ, 2004."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"W. D. Gropp, D. K. Kaushik, D. E. Keyes, and B. F. Smith,\n                      Performance modeling and tuning of an unstructured mesh CFD application\n                      , in Proceedings of the 2000 ACM\/IEEE Conference on Supercomputing, Washington, DC, IEEE, Dallas, TX, 2000.","DOI":"10.1109\/SC.2000.10059"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2006.10.012"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"W. Hackbusch,\n                      Multigrid methods and applications\n                      , Springer Ser. Comput. Math. 4, Springer, Berlin, 1985.","DOI":"10.1007\/978-3-662-02427-0"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1002\/fld.845"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595293557"},{"key":"R36","unstructured":"E. Kim, J. Bielak, O. Ghattas, and J. Wang,\n                      Octree-based finite element method for large-scale earthquake ground motion modeling in heterogeneous basins\n                      , AGU Fall Meeting Abstracts, San Francisco, CA, 2002."},{"key":"R37","unstructured":"E. Kreyszig,\n                      Introductory Functional Analysis with Applications\n                      , John Wiley, New York, 1989."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-006-0033-y"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"R40","unstructured":"D. J. Mavriplis, M. J. Aftosmis, and M. Berger,\n                      High resolution aerospace applications using the NASA Columbia Supercomputer\n                      , in Proceedings of the 2005 ACM\/IEEE Conference on Supercomputing, IEEE, Washington, DC, 2005."},{"key":"R41","doi-asserted-by":"crossref","unstructured":"M. Mehl,\n                      Cache-optimal data-structures for hierarchical methods on adaptively refined space-partitioning grids\n                      , in 2006 International Conference on High Performance Computing and Communications, Bangalore, India, 2006.","DOI":"10.1007\/11847366_15"},{"key":"R42","unstructured":"J. Modersitzki,\n                      Numerical Methods for Image Registration\n                      , Numer. Math. Sci. Comput., Oxford University Press, New York, 2004."},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1016\/S1387-2656(03)09010-0"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9991(03)00298-5"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"J. B. Pormann, C. S. Henriquez, J. John, A. Board, D. J. Rose, D. M. Harrild, and A. P. Henriquez,\n                      Computer simulations of cardiac electrophysiology\n                      , in Proceedings of the 2000 IEEE\/ACM Conference on Supercomputing, Washington, DC, IEEE, Dallas, TX, 2000.","DOI":"10.1109\/SC.2000.10032"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2007.01.026"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"R. S. Sampath, S. S. Adavani, H. Sundar, I. Lashuk, and G. Biros,\n                      Dendro: Parallel algorithms for multigrid and AMR methods on\n                      2:1\n                      balanced octrees\n                      , in Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing, Austin, TX, IEEE, Piscataway, NJ, 2008, pp. 1\u201312.","DOI":"10.1109\/SC.2008.5218558"},{"key":"R48","unstructured":"R. Sampath, H. Sundar, S. S. Adavani, I. Lashuk, and G. Biros,\n                      Dendro\n                      :\n                      A Parallel Geometric Multigrid Library for Finite Elements on Octree Meshes\n                      , http:\/\/www.cc.gatech.edu\/csela\/dendro, 2008."},{"key":"R49","unstructured":"R. Sampath, H. Sundar, S. S. Adavani, I. Lashuk, and G. Biros,\n                      Dendro\n                      Users Manual\n                      , Technical report, Georgia Institute of Technology, Atlanta, GA, 2008."},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597316564"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1995.1078"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"H. Sundar, R. S. Sampath, S. S. Adavani, C. Davatzikos, and G. Biros,\n                      Low-constant parallel algorithms for finite element simulations using linear octrees\n                      , in Proceedings of the 2007 ACM\/IEEE Conference on Supercomputing, Reno, NV, ACM Press, New York, 2007.","DOI":"10.1145\/1362622.1362656"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1137\/070681727"},{"key":"R54","unstructured":"TACC,\n                      Ranger's system architecture\n                      . http:\/\/www.tacc.utexas.edu."},{"key":"R55","doi-asserted-by":"crossref","unstructured":"O. Tatebe and Y. Oyanagi,\n                      Efficient implementation of the multigrid preconditioned conjugate gradient method on distributed memory machines\n                      , in Proceedings of the 1994 ACM\/IEEE Conference on Supercomputing, Washington, DC, ACM, New York, 1994, pp. 194\u2013203.","DOI":"10.1145\/602770.602807"},{"key":"R56","first-page":"71","volume":"2","author":"Tropf H.","year":"1981","journal-title":"Angew Inform."},{"key":"R57","unstructured":"U. Trottenberg, C. W. Oosterlee, and A. Schuller,\n                      Multigrid\n                      , Academic Press, San Diego, CA, 2001."},{"key":"R58","unstructured":"T. Tu, D. R. O'Hallaron, and O. Ghattas,\n                      Scalable parallel octree meshing for terascale applications\n                      , in Proceedings of the 2005 ACM\/IEEE Conference on Supercomputing, Seattle, WA, IEEE, Washington, DC, 2005."},{"key":"R59","doi-asserted-by":"crossref","unstructured":"T. Tu, H. Yu, L. Ramirez-Guzman, J. Bielak, O. Ghattas, K.L. Ma, and D. R. O'Hallaron,\n                      From mesh generation to scientific visualization: An end-to-end approach to parallel supercomputing\n                      , in Proceedings of the 2006 ACM\/IEEE Conference on Supercomputing, Tampa, FL, ACM Press, New York, 2006.","DOI":"10.1145\/1188455.1188551"},{"key":"R60","doi-asserted-by":"crossref","unstructured":"B. S. White, S. A. McKee, B. R. de Supinski, B. Miller, D. Quinlan, and M. Schulz,\n                      Improving the computational intensity of unstructured mesh applications\n                      , in Proceedings of the 19th Annual International Conference on Supercomputing, Dresden, Germany, ACM Press, New York, 2005, pp. 341\u2013350.","DOI":"10.1145\/1088149.1088195"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242137"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1986-0856693-9"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1023054-2"},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1035947-0"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090747774","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:14:40Z","timestamp":1787328880000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090747774"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":64,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090747774"],"URL":"https:\/\/doi.org\/10.1137\/090747774","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}