{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:12:15Z","timestamp":1792156335617,"version":"4.4.0"},"reference-count":39,"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":[[2011,1]]},"abstract":"<jats:p>We present scalable algorithms for parallel adaptive mesh refinement and coarsening (AMR), partitioning, and 2:1 balancing on computational domains composed of multiple connected two-dimensional quadtrees or three-dimensional octrees, referred to as a forest of octrees. By distributing the union of octants from all octrees in parallel, we combine the high scalability proven previously for adaptive single-octree algorithms with the geometric flexibility that can be achieved by arbitrarily connected hexahedral macromeshes, in which each macroelement is the root of an adapted octree. A key concept of our approach is an encoding scheme of the interoctree connectivity that permits arbitrary relative orientations between octrees. Based on this encoding we develop interoctree transformations of octants. These form the basis for high-level parallel octree algorithms, which are designed to interact with an application code such as a numerical solver for partial differential equations. We have implemented and tested these algorithms in the p4est software library. We demonstrate the parallel scalability of p4est on its own and in combination with two geophysics codes. Using p4est we generate and adapt multioctree meshes with up to $5.13\\times10^{11}$ octants on as many as 220,320 CPU cores and execute the 2:1 balance algorithm in less than 10 seconds per million octants per process.<\/jats:p>","DOI":"10.1137\/100791634","type":"journal-article","created":{"date-parts":[[2011,5,17]],"date-time":"2011-05-17T18:11:35Z","timestamp":1305655895000},"page":"1103-1133","source":"Crossref","is-referenced-by-count":649,"title":["<tt>p4est<\/tt>\n                    : Scalable Algorithms for Parallel Adaptive Mesh Refinement on Forests of Octrees"],"prefix":"10.1137","volume":"33","author":[{"given":"Carsten","family":"Burstedde","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lucas C.","family":"Wilcox","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omar","family":"Ghattas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,5,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"V. Ak\u00e7elik, 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 SC '03: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2003.","DOI":"10.1145\/1048935.1050202"},{"key":"R2","unstructured":"W. Bangerth, C. Burstedde, T. Heister, and M. Kronbichler,\n                      Algorithms and data structures for massively parallel generic adaptive finite element codes\n                      , ACM Trans. Math. Software, to appear."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/1268776.1268779"},{"key":"R4","unstructured":"B. K. Bergen, F. H\u00fclsemann, and U. R\u00fcde,\n                      Is $1.7\\times10^{10}$ unknowns the largest finite element system that can be solved today?\n                      , in SC '05: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2005."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(84)90073-1"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"G. L. Bryan, T. Abel, and M. L. Norman,\n                      Achieving extreme resolution in numerical cosmology using adaptive mesh refinement: Resolving primordial star formation\n                      , in SC '01: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2001.","DOI":"10.1145\/582034.582047"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/180\/1\/012009"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"C. Burstedde, O. Ghattas, M. Gurnis, E. Tan, T. Tu, G. Stadler, L. C. Wilcox, and S. Zhong,\n                      Scalable adaptive mantle convection simulation on petascale supercomputers\n                      , in SC '08: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2008.","DOI":"10.1109\/SC.2008.5214248"},{"key":"R9","unstructured":"C. Burstedde, O. Ghattas, G. Stadler, T. Tu, and L. C. Wilcox,\n                      Towards adaptive mesh PDE simulations on petascale computers\n                      , in Proceedings of Teragrid '08, Las Vegas, NV, 2008."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2008.12.015"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. C. Calder, B. C. Curtis, L. J. Dursi, B. Fryxell, G. Henry, P. MacNeice, K. Olson, P. Ricker, R. Rosner, F. X. Timmes, H. M. Tufo, J. W. Truran, and M. Zingale,\n                      High-performance reactive fluid flow simulations using adaptive mesh refinement on thousands of processors\n                      , in SC '00: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2000, pp. 56\u201356.","DOI":"10.1109\/SC.2000.10010"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/78\/1\/012013"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2004.08.028"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1412"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"U. Frisch,\n                      Turbulence: The Legacy of A. N. Kolmogorov\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9781139170666"},{"key":"R17","unstructured":"J.L. Gailly and M. Adler,\n                      A massively spiffy yet delicately unobtrusive compression library\n                      , http:\/\/zlib.net\/."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"T. Goodale, G. Allen, G. Lanfermann, J. Masso, T. Radke, E. Seidel, and J. Shalf,\n                      The Cactus framework and toolkit: Design and applications\n                      , in Vector and Parallel Processing\u2014VECPAR '2002, 5th International Conference, Springer, New York, 2003.","DOI":"10.1007\/3-540-36569-9_13"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1403"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"B. S. Kirk, J. W. Peterson, R. H. Stogner, and G. F. Carey,\n                      libMesh\n                      : A C++ library for parallel adaptive mesh refinement\/coarsening simulations\n                      , Engineering with Computers, 22 (2006), pp. 237\u2013254.","DOI":"10.1007\/s00366-006-0049-3"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00054-5"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-006-0039-5"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"J. Luitjens, B. Worthen, M. Berzins, and T. C. Henderson,\n                      Scalable parallel AMR for the Uintah multiphysics code\n                      , in Petascale Computing Algorithms and Applications, D. A. Bader, ed., Chapman and Hall\/CRC, Boca Raton, FL, 2007.","DOI":"10.1201\/9781584889106.ch4"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90104-6"},{"key":"R25","unstructured":"R. J. Meyers, T. J. Tautges, and P. M. Tuchinsky,\n                      The hex-tet hex-dominant meshing algorithm as implemented in CUBIT\n                      , in Proceedings of the 7th International Meshing Roundtable, Sandia National Laboratory, Albuquerque, NM, 1998, pp. 151\u2013158."},{"key":"R26","unstructured":"G. M. Morton,\n                      A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing\n                      , Technical report, IBM Ltd., Armonk, NY, 1966."},{"key":"R27","unstructured":"C. D. Norton, J. Z. Lou, and T. A. Cwik,\n                      Status and directions for the pyramid parallel unstructured amr library\n                      , in Proceedings of the 15th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2001, p. 120."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2009.09.007"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9991(03)00298-5"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. S. Sampath, S. S. Adavani, H. Sundar, I. Lashuk, and G. Biros,\n                      Dendro\n                      : Parallel algorithms for multigrid and AMR methods on\n                      2:1\n                      balanced octrees\n                      , in SC '08: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2008.","DOI":"10.1109\/SC.2008.5218558"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/090747774"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1126\/science.1191223"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/j.finel.2003.10.006"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/070681727"},{"key":"R35","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 SC '07: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2007.","DOI":"10.1145\/1362622.1362656"},{"key":"R36","first-page":"71","volume":"2","author":"Tropf H.","year":"1981","journal-title":"Angewandte Informatik"},{"key":"R37","unstructured":"T. Tu, D. R. O'Hallaron, and O. Ghattas,\n                      Scalable parallel octree meshing for terascale applications\n                      , in SC '05: Proceedings of the ACM\/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis, ACM, New York, 2005."},{"key":"R38","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 SC2006, Tampa, FL, 2006.","DOI":"10.1145\/1188455.1188551"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2010.09.008"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100791634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:19:47Z","timestamp":1787325587000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100791634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100791634"],"URL":"https:\/\/doi.org\/10.1137\/100791634","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}