{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T00:05:10Z","timestamp":1773619510718,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,2,6]],"date-time":"2018-02-06T00:00:00Z","timestamp":1517875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Unions Horizon 2020 research and innovation programme","award":["671698 (ExaHyPE)"],"award-info":[{"award-number":["671698 (ExaHyPE)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>We present a family of spacetree-based multigrid realizations using the tree\u2019s multiscale nature to derive coarse grids. They align with matrix-free geometric multigrid solvers as they never assemble the system matrices, which is cumbersome for dynamically adaptive grids and full multigrid. The most sophisticated realizations use BoxMG to construct operator-dependent prolongation and restriction in combination with Galerkin\/Petrov-Galerkin coarse-grid operators. This yields robust solvers for nontrivial elliptic problems. We embed the algebraic, problem-dependent, and grid-dependent multigrid operators as stencils into the grid and evaluate all matrix-vector products<jats:italic>in situ<\/jats:italic>throughout the grid traversals. Such an approach is not literally matrix-free as the grid carries the matrix. We propose to switch to a hierarchical representation of all operators. Only differences of algebraic operators to their geometric counterparts are held. These hierarchical differences can be stored and exchanged with small memory footprint. Our realizations support arbitrary dynamically adaptive grids while they vertically integrate the multilevel operations through spacetree linearization. This yields good memory access characteristics, while standard colouring of mesh entities with domain decomposition allows us to use parallel many-core clusters. All realization ingredients are detailed such that they can be used by other codes.<\/jats:p>","DOI":"10.1145\/3165280","type":"journal-article","created":{"date-parts":[[2018,2,6]],"date-time":"2018-02-06T18:13:28Z","timestamp":1517940808000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Quasi-matrix-free Hybrid Multigrid on Dynamically Adaptive Cartesian Grids"],"prefix":"10.1145","volume":"44","author":[{"given":"Marion","family":"Weinzierl","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Durham University, Durham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6208-1841","authenticated-orcid":false,"given":"Tobias","family":"Weinzierl","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, Durham, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975127"},{"key":"e_1_2_1_2_1","unstructured":"Advanced Scientific Computing Advisory Committee (ASCAC) Subcommittee. 2010. The Opportunities and Challenges of Exascale Computing. (2010). Retrieved from https:\/\/science.energy.gov\/&sim;\/media\/ascr\/ascac\/pdf\/reports\/Exascale_subcomm ittee_report.pdf. Advanced Scientific Computing Advisory Committee (ASCAC) Subcommittee. 2010. The Opportunities and Challenges of Exascale Computing. (2010). Retrieved from https:\/\/science.energy.gov\/&sim;\/media\/ascr\/ascac\/pdf\/reports\/Exascale_subcomm ittee_report.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093172.3093230"},{"key":"e_1_2_1_4_1","volume-title":"Space-Filling Curves\u2014An Introduction with Applications in Scientific Computing. Texts in Computational Science and Engineering","author":"Bader M."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJCSE.2008.021108"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/100798806"},{"key":"e_1_2_1_7_1","unstructured":"S. Balay and others. 2016. PETSc Web page. Retrieved from http:\/\/www.mcs.anl.gov\/petsc. S. Balay and others. 2016. PETSc Web page. Retrieved from http:\/\/www.mcs.anl.gov\/petsc."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684380"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(83)90014-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0431719-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"A. Brandt and O. E. Livne. 2011. Multigrid techniques\u20141984 guide with applications to fluid dynamics. Classics in Applied Mathematics 67 SIAM. A. Brandt and O. E. Livne. 2011. Multigrid techniques\u20141984 guide with applications to fluid dynamics. Classics in Applied Mathematics 67 SIAM.","DOI":"10.1137\/1.9781611970753"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2009.05.011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791634"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Conference on Parallel Processing and Applied Mathematics (PPAM\u201917)","author":"Charrier D. E."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598339402"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(82)90057-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(83)90016-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0908059"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(88)90060-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.705"},{"key":"e_1_2_1_21_1","volume-title":"Technical Report 2016.25. University of Manchester.","author":"Dongarra J.","year":"2016"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"J. Dongarra J. Hittinger etal 2014. Applied Mathematics Research for Exascale Computing. Technical Report. DOE ASCR Exascale Mathematics Working Group: Retrieved from http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/PAPERS\/doe-exascale-math-report.pdf. J. Dongarra J. Hittinger et al. 2014. Applied Mathematics Research for Exascale Computing. Technical Report. DOE ASCR Exascale Mathematics Working Group: Retrieved from http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/PAPERS\/doe-exascale-math-report.pdf.","DOI":"10.2172\/1149042"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Parallel Computing (ParCo\u201915)","volume":"27","author":"Eckhardt W."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Conference on Parallel Processing and Applied Mathematics (PPAM\u201909)","volume":"6068","author":"Eckhardt W."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2011.01.004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/130935781"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.2968"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4208\/nmtma.2015.w10si"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"M. Griebel. 1994. Multilevelmethoden als Iterationsverfahren \u00fcber Erzeugendensystemen. Habilitation Thesis. TU M\u00fcnchen. M. Griebel. 1994. Multilevelmethoden als Iterationsverfahren \u00fcber Erzeugendensystemen. Habilitation Thesis. TU M\u00fcnchen.","DOI":"10.1007\/978-3-322-89224-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00020-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90099-8"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/070702564"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of ISC High Performance","author":"King J.","year":"2016"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1925"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.837"},{"key":"e_1_2_1_37_1","unstructured":"T. Malas G. Hager H. Ltaief and D. Keyes. 2015. Multi-dimensional intra-tile parallelization for memory-starved stencil computations. CoRR abs\/1510.04995 (2015). T. Malas G. Hager H. Ltaief and D. Keyes. 2015. Multi-dimensional intra-tile parallelization for memory-starved stencil computations. CoRR abs\/1510.04995 (2015)."},{"key":"e_1_2_1_38_1","volume-title":"Memory bandwidth and machine balance in current high performance computers","author":"McCalpin J. D.","year":"1995"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"S. F. McCormick. 1989. Multilevel Adaptive Methods for Partial Differential Equations. SIAM. S. F. McCormick. 1989. Multilevel Adaptive Methods for Partial Differential Equations. SIAM.","DOI":"10.1137\/1.9781611971026"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.481"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1998.5911"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3054946"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807675"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 2008 ACM\/IEEE Conference on Supercomputing (SC\u201908)","author":"Sampath R. S."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_50"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(85)90147-0"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Y. Shapira. 2003. Matrix-Based Multigrid. Kluwer. Y. Shapira. 2003. Matrix-Based Multigrid. Kluwer.","DOI":"10.1007\/978-1-4757-3726-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"K. St\u00fcben. 2001. Appendix A: An introduction to algebraic multigrid. In Multigrid U. Trottenberg C. W. Oosterlee and A. Sch\u00fcller (Eds.). Elsevier Science Inc. K. St\u00fcben. 2001. Appendix A: An introduction to algebraic multigrid. In Multigrid U. Trottenberg C. W. Oosterlee and A. Sch\u00fcller (Eds.). Elsevier Science Inc.","DOI":"10.1016\/B978-0-444-50616-0.50012-9"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC\u201912)","author":"Sundar H."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/070681727"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.708"},{"key":"e_1_2_1_52_1","unstructured":"U. Trottenberg C. W. Oosterlee and A. Sch\u00fcller. 2001. Multigrid. Academic Press. U. Trottenberg C. W. Oosterlee and A. Sch\u00fcller. 2001. Multigrid. Academic Press."},{"key":"e_1_2_1_54_1","volume-title":"A Framework for Parallel PDE Solvers on Multiscale Adaptive Cartesian Grids","author":"Weinzierl T."},{"key":"e_1_2_1_56_1","unstructured":"T. Weinzierl etal 2012. Peano\u2014a Framework for PDE Solvers on Spacetree Grids. Retrieved from http:\/\/www.peano-framework.orgwww.peano-framework.org. T. Weinzierl et al. 2012. Peano\u2014a Framework for PDE Solvers on Spacetree Grids. Retrieved from http:\/\/www.peano-framework.orgwww.peano-framework.org."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626414410060"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799071"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113220.3113538"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596310998"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1813"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3165280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3165280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:54Z","timestamp":1750213614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3165280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,6]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3165280"],"URL":"https:\/\/doi.org\/10.1145\/3165280","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,6]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}