{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:40Z","timestamp":1750306120362,"version":"3.41.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,3,27]],"date-time":"2017-03-27T00:00:00Z","timestamp":1490572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>We introduce a family of implementations of low-order, additive, geometric multilevel solvers for systems of Helmholtz equations arising from Schr\u00f6dinger equations. Both grid spacing and arithmetics may comprise complex numbers, and we thus can apply complex scaling to the indefinite Helmholtz operator. Our implementations are based on the notion of a spacetree and work exclusively with a finite number of precomputed local element matrices. They are globally matrix-free.<\/jats:p>\n          <jats:p>Combining various relaxation factors with two grid transfer operators allows us to switch from additive multigrid over a hierarchical basis method into a Bramble-Pasciak-Xu (BPX)-type solver, with several multiscale smoothing variants within one code base. Pipelining allows us to realize full approximation storage (FAS) within the additive environment where, amortized, each grid vertex carrying degrees of freedom is read\/written only once per iteration. The codes realize a single-touch policy. Among the features facilitated by matrix-free FAS is arbitrary dynamic mesh refinement (AMR) for all solver variants. AMR as an enabler for full multigrid (FMG) cycling\u2014the grid unfolds throughout the computation\u2014allows us to reduce the cost per unknown.<\/jats:p>\n          <jats:p>The present work primary contributes toward software realization and design questions. Our experiments show that the consolidation of single-touch FAS, dynamic AMR, and vectorization-friendly, complex scaled, matrix-free FMG cycles delivers a mature implementation blueprint for solvers of Helmholtz equations in general. For this blueprint, we put particular emphasis on a strict implementation formalism as well as some implementation correctness proofs.<\/jats:p>","DOI":"10.1145\/3054946","type":"journal-article","created":{"date-parts":[[2017,3,27]],"date-time":"2017-03-27T12:25:10Z","timestamp":1490617510000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Complex Additive Geometric Multilevel Solvers for Helmholtz Equations on Spacetrees"],"prefix":"10.1145","volume":"44","author":[{"given":"Bram","family":"Reps","sequence":"first","affiliation":[{"name":"University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Weinzierl","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975127"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877510"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31046-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/582034.582081"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01877511"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684380"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(83)90139-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(85)90119-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400874668"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.665"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4208\/cicp.121209.180910s"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/080725702"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-1023042-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0118663"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0431719-X"},{"key":"e_1_2_1_16_1","first-page":"162","article-title":"Wave-ray multigrid method for standing wave equations","volume":"6","author":"Brandt A.","year":"1997","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492904000182"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2012.07.048"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718133.ch10"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90045-9"},{"key":"e_1_2_1_21_1","unstructured":"C. Cohen-Tannoudji B. Diu and F. Lalo\u00eb. 1977. Quantum Mechanics Volume 1. Wiley-VCH.  C. Cohen-Tannoudji B. Diu and F. Lalo\u00eb. 1977. Quantum Mechanics Volume 1. Wiley-VCH."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/130921064"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1895"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1881"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"J. Dongarra J. Hittinger J. Bell L. Chacon R. Falgout M. Heroux P. Hovland E. Ng C. Webster and S. Wild. 2014. Applied Mathematics Research for Exascale Computing. Retrieved March 3 2017 from http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/PAPERS\/doe-exascale-math-report.pdf.  J. Dongarra J. Hittinger J. Bell L. Chacon R. Falgout M. Heroux P. Hovland E. Ng C. Webster and S. Wild. 2014. Applied Mathematics Research for Exascale Computing. Retrieved March 3 2017 from http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/PAPERS\/doe-exascale-math-report.pdf.","DOI":"10.2172\/1149042"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501357190"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/100804644"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/040615195"},{"key":"e_1_2_1_29_1","first-page":"403","article-title":"On a multilevel Krylov method for the Helmholtz equation preconditioned by shifted Laplacian","volume":"31","author":"Erlangga Y. A.","year":"2008","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2004.01.009"},{"key":"e_1_2_1_31_1","first-page":"325","article-title":"Why it is difficult to solve Helmholtz problems with classical iterative methods","volume":"83","author":"Ernst O.","year":"2011","journal-title":"Numerical Analysis of Multiscale Problems"},{"volume":"11","volume-title":"Quantum Scattering Theory for Several Particle Systems. Mathematical Physics and Applied Mathematics","author":"Faddeev L. D.","key":"e_1_2_1_32_1"},{"volume-title":"Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering","author":"Foster I.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086563X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1808"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2013.06.001"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/130935781"},{"volume-title":"Zur L\u00f6sung von Finite-Differenzen- und Finite-Element-Gleichungen Mittels Der Hiearchischen-Transformations-Mehrgitter-Methode","author":"Griebel M.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0915036"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.01.015"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2004.09.015"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.76.030701"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(95)00144-N"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070070032"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/1099-0887(200011)16:11%3C801::AID-CNM377%3E3.0.CO;2-M"},{"key":"e_1_2_1_47_1","first-page":"19","article-title":"Memory bandwidth and machine balance in current high performance computers","volume":"12","author":"McCalpin J. D.","year":"1995","journal-title":"IEEE Computer Society Technical Committee on Computer Architecture (TCCA) Newsletter"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.590"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.481"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0370-1573(98)00002-7"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2009.09.003"},{"volume-title":"Plasma 2010 Committee, and Plasma Science Committee","year":"2007","author":"National Research Council","key":"e_1_2_1_52_1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(02)00165-4"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61247-3"},{"key":"e_1_2_1_55_1","unstructured":"J. Reinders and J. Jeffers. 2015. High Performance Parallelism Pearls. Elsevier.   J. Reinders and J. Jeffers. 2015. High Performance Parallelism Pearls. Elsevier."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2010.07.022"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.28.1049"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1882"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(79)90165-8"},{"volume-title":"Theory of Gas Discharge Plasma","series-title":"Springer Series on Atomic","author":"Smirnov B. M.","key":"e_1_2_1_60_1"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/070681727"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2010.38"},{"key":"e_1_2_1_64_1","unstructured":"U. Trottenberg C. W. Oosterlee and A. Schuller. 2001. Multigrid. Academic Press.   U. Trottenberg C. W. Oosterlee and A. Schuller. 2001. Multigrid. Academic Press."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1997"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/060661491"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1120263"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"P. S. Vassilevski and U. Meier Yang. 2014. Reducing communication in algebraic multigrid using additive variants. Numerical Linear Algebra with Application: Special Issue Multigrid Methods 2013 21 2 275--296.  P. S. Vassilevski and U. Meier Yang. 2014. Reducing communication in algebraic multigrid using additive variants. Numerical Linear Algebra with Application: Special Issue Multigrid Methods 2013 21 2 275--296.","DOI":"10.1002\/nla.1928"},{"volume-title":"A Framework for Parallel PDE Solvers on Multiscale Adaptive Cartesian Grids","author":"Weinzierl T.","key":"e_1_2_1_70_1"},{"key":"e_1_2_1_72_1","unstructured":"T. Weinzierl etal 2012. Peano\u2014A Framework for solvers on Spacetree Grids. Retrieved March 3 2017 from http:\/\/www.peano-framework.org.  T. Weinzierl et al. 2012. Peano\u2014A Framework for solvers on Spacetree Grids. Retrieved March 3 2017 from http:\/\/www.peano-framework.org."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626414410060"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799071"},{"key":"e_1_2_1_75_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\/3054946","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3054946","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:43Z","timestamp":1750217803000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3054946"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,27]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3054946"],"URL":"https:\/\/doi.org\/10.1145\/3054946","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2017,3,27]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}