research-article

Complex Additive Geometric Multilevel Solvers for Helmholtz Equations on Spacetrees

Authors:

Tobias WeinzierlAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 44, Issue 1

Article No.: 2, Pages 1 - 36

https://doi.org/10.1145/3054946

Published: 27 March 2017 Publication History

Abstract

We introduce a family of implementations of low-order, additive, geometric multilevel solvers for systems of Helmholtz equations arising from Schrödinger 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.

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—the grid unfolds throughout the computation—allows us to reduce the cost per unknown.

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.

References

[1]

M. F. Adams, J. Brown, M. Knepley, and R. Samtaney. 2016. Segmental refinement: A multigrid technique for data locality. SIAM Journal on Scientific Computing 38, 4, C426--C440.

[2]

J. Aguilar and J. M. Combes. 1971. A class of analytic perturbations for one-body Schrödinger Hamiltonians. Communications in Mathematical Physics 22, 269--279.

[3]

M. Bader. 2013. Space-Filling Curves: An Introduction with Applications in Scientific Computing. Texts in Computational Science and Engineering, Vol. 9. Springer-Verlag.

Digital Library

[4]

M. Baertschy and X. Li. 2001. Solution of a three-body problem in quantum mechanics using sparse linear algebra on parallel computers. In Proceedings of the 2001 ACM/IEEE Conference on Supercomputing. ACM, New York, NY, 47.

Digital Library

[5]

E. Balslev and J. M. Combes. 1971. Spectral properties of many-body Schrödinger operators with dilatation-analytic interactions. Communications in Mathematical Physics 22, 280--294.

[6]

P. Bastian, W. Hackbusch, and G. Wittum. 1998. Additive and multiplicative multi-grid: A comparison. Computing 60, 4, 345--364.

Digital Library

[7]

A. Bayliss, C. I. Goldstein, and E. Turkel. 1983. An iterative method for the Helmholtz equation. Journal of Computational Physics 49, 443--457.

[8]

A. Bayliss, C. I. Goldstein, and E. Turkel. 1985. On accuracy conditions for the numerical computation of waves. Journal of Computational Physics 59, 396--404.

[9]

R. Bellman. 1961. Adaptive Control Processes: A Guided Tour. Princeton University Press, Princeton, NJ.

[10]

H. bin Zubair, S. P. MacLachlan, and C. W. Oosterlee. 2010. A geometric multigrid method based on L-shaped coarsening for PDEs on stretched grids. Numerical Linear Algebra with Applications 17, 871--894.

[11]

H. bin Zubair, B. Reps, and W. Vanroose. 2012. A preconditioned iterative solver for the scattering solutions of the Schrödinger equation. Communications in Computational Physics 11, 2, 415--434.

[12]

M. Bollhöfer, M. J. Grote, and O. Schenk. 2009. Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media. SIAM Journal on Scientific Computing 31, 5, 3781--3805.

Digital Library

[13]

J. H. Bramble, J. E. Pasciak, and J. Xu. 1990. Parallel multilevel preconditioners. Mathematics of Computation 55, 1--22.

[14]

A. Brandt. 1973. Multi-level adaptive technique (MLAT) for fast numerical solution to boundary value problems. In Proceedings of the 3rd International Conference on Numerical Methods in Fluid Mechanics. 82--89.

[15]

A. Brandt. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 138, 333--390.

[16]

A. Brandt and I. Livshits. 1997. Wave-ray multigrid method for standing wave equations. Electronic Transactions on Numerical Analysis 6, 162--181.

[17]

H.-J. Bungartz and M. Griebel. 2004. Sparse grids. Acta Numerica 13, 147--269.

[18]

Z. Chen, D. Cheng, and T. Wu. 2012. A dispersion minimizing finite difference scheme and preconditioned solver for the 3D Helmholtz equation. Journal of Computational Physics 231, 24, 8152--8175.

Digital Library

[19]

E. Chow, R. D. Falgout, J. J. Hu, R. S. Tuminaro, and U. Meier Yang. 2006. A survey of parallelization techniques for multigrid solvers. In Parallel Processing for Scientific Computing, M. Heroux, P. Raghavan, and H. Simon (Eds.). SIAM, 179--201.

[20]

A. T. Chronopoulos and C. W. Gear. 1989. s-step iterative methods for symmetric linear systems. Journal of Computational and Applied Mathematics 25, 2, 153--168.

Digital Library

[21]

C. Cohen-Tannoudji, B. Diu, and F. Laloë. 1977. Quantum Mechanics Volume 1. Wiley-VCH.

[22]

S. Cools, B. Reps, and W. Vanroose. 2014a. An efficient multigrid calculation of the far field map for Helmholtz and Schrödinger equations. SIAM Journal on Scientific Computing 36, B367--B395.

[23]

S. Cools, B. Reps, and W. Vanroose. 2014b. A new level-dependent coarse grid correction scheme for indefinite Helmholtz problems. Numerical Linear Algebra with Applications 21, 513--533.

[24]

S. Cools and W. Vanroose. 2013. Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems. Numerical Linear Algebra with Applications 20, 4, 575--597.

[25]

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.

[26]

H. C. Elman, O. G. Ernst, and D. P. O’Leary. 2001. A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations. SIAM Journal of Scientific Computing 23, 4, 1291--1315.

Digital Library

[27]

B. Engquist and L. Ying. 2011. Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers. Multiscale Modeling and Simulation 9, 686--710.

[28]

Y. A. Erlangga, C. W. Oosterlee, and C. Vuik. 2006. A novel multigrid based preconditioner for heterogeneous Helmholtz problems. SIAM Journal on Scientific Computing 27, 1471--1492.

Digital Library

[29]

Y. A. Erlangga and R. Nabben. 2008. On a multilevel Krylov method for the Helmholtz equation preconditioned by shifted Laplacian. Electronic Transactions on Numerical Analysis 31, 403--424.

[30]

Y. A. Erlangga, C. Vuik, and C. W. Oosterlee. 2004. On a class of preconditioners for solving the Helmholtz equation. Applied Numerical Mathematics 50, 409--425.

Digital Library

[31]

O. Ernst and M. Gander. 2011. Why it is difficult to solve Helmholtz problems with classical iterative methods. Numerical Analysis of Multiscale Problems 83, 325--361.

[32]

L. D. Faddeev and S. P. Merkuriev. 1993. Quantum Scattering Theory for Several Particle Systems. Mathematical Physics and Applied Mathematics, Vol. 11. Springer, Netherlands.

[33]

I. Foster. 1995. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison-Wesley Longman.

Digital Library

[34]

P. Ghysels, T. Ashby, K. Meerbergen, and W. Vanroose. 2013. Hiding global communication latency in the GMRES algorithm on massively parallel machines. SIAM Journal on Scientific Computing 35, 1, C48--C71.

[35]

P. Ghysels, P. Kosiewicz, and W. Vanroose. 2012. Improving the arithmetic intensity of multigrid with the help of polynomial smoothers. Numerical Linear Algebra with Applications 19, 2, 253--267.

[36]

P. Ghysels and W. Vanroose. 2014. Hiding global synchronization latency in the preconditioned conjugate gradient algorithm. Parallel Computing 40, 7, 224--238.

Digital Library

[37]

P. Ghysels and W. Vanroose. 2015. Modeling the performance of geometric multigrid on many-core computer architectures. SIAM Journal on Scientific Computing 37, 2, C194--C216.

[38]

M. Griebel. 1990. Zur Lösung von Finite-Differenzen- und Finite-Element-Gleichungen Mittels Der Hiearchischen-Transformations-Mehrgitter-Methode. Vol. 342/4/90 A. Dissertation, Technische Universität München.

[39]

M. Griebel. 1994. Multilevel algorithms considered as iterative methods on semidefinite systems. SIAM Journal on Scientific Computing 15, 3, 547--565.

Digital Library

[40]

E. Haber and S. MacLachlan. 2011. A fast method for the solution of the Helmholtz equation. Journal of Computational Physics 230, 4403--4418.

Digital Library

[41]

G. Ronald Hadley. 2005. A complex Jacobi iterative method for the indefinite Helmholtz equation. Journal of Computational Physics 203, 1, 358--370.

Digital Library

[42]

M. Hoemmen. 2010. Communication-Avoiding Krylov Subspace Methods. Ph.D. Dissertation. EECS Department, University of California, Berkeley.

Digital Library

[43]

D. A. Horner, F. Morales, T. N. Rescigno, F. Martín, and C. W. McCurdy. 2007. Two-photon double ionization of helium above and below the threshold for sequential ionization. Physical Review A 76, 3, 30701.

[44]

F. Ihlenburg and I. Babuska. 1995. Finite element solution to the Helmholtz equation with high wave numbers. Computers and Mathematics with Applications 30, 9--37.

[45]

M. Kowarschik, U. Rüde, C. Weiß, and W. Karl. 2000. Cache-aware multigrid methods for solving Poisson’s equation in two dimensions. Computing 64, 4, 381--399.

Digital Library

[46]

M. Magolu Monga Made, R. Beauwens, and G. Warze. 2000. Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix. Communications in Numerical Methods in Engineering 16, 11, 801--817.

[47]

J. D. McCalpin. 1995. Memory bandwidth and machine balance in current high performance computers. IEEE Computer Society Technical Committee on Computer Architecture (TCCA) Newsletter 12, 19--25.

[48]

K. Meerbergen and J. P. Coyette. 2009. Connection and comparison between frequency shift time integration and a spectral transformation preconditioner. Numerical Linear Algebra with Applications 16, 1, 1--17.

[49]

M. Mehl, T. Weinzierl, and C. Zenger. 2006. A cache-oblivious self-adaptive full multigrid method. Numerical Linear Algebra with Applications 13, 2--3, 275--291.

[50]

N. Moiseyev. 1998. Quantum theory of resonances: Calculating energies, widths and cross-sections by complex scaling. Physics Reports 302, 211.

[51]

D. Osei-Kuffuor and Y. Saad. 2010. Preconditioning Helmholtz linear systems. Applied Numerical Mathematics 60, 4, 420--431.

Digital Library

[52]

National Research Council, Plasma 2010 Committee, and Plasma Science Committee. 2007. Plasma Science: Advancing Knowledge in the National Interest. National Academies Press, Washington, DC.

[53]

R. E. Plessix and W. A. Mulder. 2003. Separation-of-variables as a preconditioner for an iterative Helmholtz solver. Applied Numerical Mathematics 44, 385--400.

Digital Library

[54]

Y. P. Raizer. 1991. Gas Discharge Physics. Springer-Verlag, Berlin, Germany.

[55]

J. Reinders and J. Jeffers. 2015. High Performance Parallelism Pearls. Elsevier.

Digital Library

[56]

B. Reps, W. Vanroose, and H. bin Zubair. 2010. On the indefinite Helmholtz equation: Complex stretched absorbing boundary layers, iterative analysis, and preconditioning. Journal of Computational Physics 229, 22, 8384--8405.

Digital Library

[57]

E. Schrödinger. 1926. An undulatory theory of the mechanics of atoms and molecules. Physical Review 28, 1049--1070.

[58]

A. H. Sheikh, D. Lahaye, and C. Vuik. 2013. On the convergence of shifted Laplace preconditioner combined with multilevel deflation. Numerical Linear Algebra with Applications 20, 645--662.

[59]

B. Simon. 1979. The definition of molecular resonance curves by the method of exterior complex scaling. Physics Letters A 71, 211.

[60]

B. M. Smirnov. 2015. Theory of Gas Discharge Plasma. Springer Series on Atomic, Optical, and Plasma Physics, Vol. 84. Springer.

[61]

C. C. Stolk. 2015. A Dispersion Minimizing Scheme for the 3-D Helmholtz Equation with Applications in Multigrid Based Solvers. Technical Report. arXiv:1504.01609.

[62]

H. Sundar, R. S. Sampath, and G. Biros. 2008. Bottom-up construction and 2:1 balance refinement of linear octrees in parallel. SIAM Journal on Scientific Computing 30, 5, 2675--2708.

Digital Library

[63]

J. Treibig, G. Hager, and G. Wellein. 2010. LIKWID: A lightweight performance-oriented tool suite for x86 multicore environments. In Proceedings of the 2010 39th International Conference on Parallel Processing Workshops (ICPPW’10). IEEE, Los Alamitos, CA, 207--216.

Digital Library

[64]

U. Trottenberg, C. W. Oosterlee, and A. Schuller. 2001. Multigrid. Academic Press.

Digital Library

[65]

P. Tsuji and R. Tuminaro. 2015. Augmented AMG-shifted Laplacian preconditioners for indefinite Helmholtz problems. Numerical Linear Algebra with Applications 22, 6, 1077--1101.

[66]

M.B. van Gijzen, Y. A. Erlangga, and C. Vuik. 2007. Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian. SIAM Journal on Scientific Computing 29, 5, 1942--1958.

Digital Library

[67]

W. Vanroose, F. Martin, T. N. Rescigno, and C. W. McCurdy. 2005. Complete photo-induced breakup of the H₂ molecule as a probe of molecular electron correlation. Science 310, 1787--1789.

[68]

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.

[69]

M. Weinzierl. 2013. Hybrid Geometric-Algebraic Matrix-Free Multigrid on Spacetrees. Ph.D. Dissertation. Fakultät für Informatik, Technische Universität München, München.

[70]

T. Weinzierl. 2009. A Framework for Parallel PDE Solvers on Multiscale Adaptive Cartesian Grids. Verlag Dr. Hut, München. http://www.dr.hut-verlag.de/978-3-86853-146-6.html.

[71]

T. Weinzierl. 2017. The Peano Software: Parallel, Automaton-Based, Dynamically Adaptive Grid Traversals. Technical Report. arXiv:1506.04496.

[72]

T. Weinzierl et al. 2012. Peano—A Framework for solvers on Spacetree Grids. Retrieved March 3, 2017, from http://www.peano-framework.org.

[73]

T. Weinzierl, M. Bader, K. Unterweger, and R. Wittmann. 2014. Block fusion on dynamically adaptive spacetree grids for shallow water waves. Parallel Processing Letters 24, 3, 1441006.

[74]

T. Weinzierl and M. Mehl. 2011. Peano—a traversal and storage scheme for octree-like adaptive cartesian multiscale grids. SIAM Journal on Scientific Computing 33, 5, 2732--2760.

Digital Library

[75]

I. Yavneh and M. Weinzierl. 2012. Nonsymmetric black box multigrid with coarsening by three. Numerical Linear Algebra with Applications 19, 2, 246--262.

Cited By

Treister EYovel R(2023)A hybrid shifted Laplacian multigrid and domain decomposition preconditioner for the elastic Helmholtz equationsJournal of Computational Physics10.1016/j.jcp.2023.112622(112622)Online publication date: Nov-2023
https://doi.org/10.1016/j.jcp.2023.112622
Munch PKormann KKronbichler M(2021)hyper.deal: An Efficient, Matrix-free Finite-element Library for High-dimensional Partial Differential EquationsACM Transactions on Mathematical Software10.1145/346972047:4(1-34)Online publication date: 31-Dec-2021
https://dl.acm.org/doi/10.1145/3469720
Reinarz ACharrier DBader MBovard LDumbser MDuru KFambri FGabriel AGallard JKöppel SKrenz LRannabauer LRezzolla LSamfass PTavelli MWeinzierl T(2020)ExaHyPE: An engine for parallel dynamically adaptive simulations of wave problemsComputer Physics Communications10.1016/j.cpc.2020.107251(107251)Online publication date: Mar-2020
https://doi.org/10.1016/j.cpc.2020.107251
Show More Cited By

Index Terms

Complex Additive Geometric Multilevel Solvers for Helmholtz Equations on Spacetrees
1. Computing methodologies
  1. Parallel computing methodologies
2. Mathematics of computing
  1. Mathematical software

Recommendations

Development of a Godunov method for Maxwell's equations with Adaptive Mesh Refinement

In this paper we present a second order 3D method for Maxwell's equations based on a Godunov scheme with Adaptive Mesh Refinement (AMR). In order to achieve it, we apply a limiter which better preserves extrema and boundary conditions based on a ...
Multilevel Preconditioners for Reaction-Diffusion Problems with Discontinuous Coefficients

In this paper, we extend some of the multilevel convergence results obtained by Xu and Zhu in [Xu and Zhu, M3AS 2008], to the case of second order linear reaction-diffusion equations. Specifically, we consider the multilevel preconditioners for solving ...
A perfectly matched layer for the Helmholtz equation in a semi-infinite strip

The perfectly matched layer (PML) has become a widespread technique for preventing reflections from far field boundaries for wave propagation problems in both the time dependent and frequency domains. We develop a discretization to solve the Helmholtz ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 44, Issue 1

March 2018

308 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3071076

Editor:
Daniel Kressner
EPF Lausanne, Switzerland

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 March 2017

Accepted: 01 January 2017

Revised: 01 August 2016

Received: 01 September 2015

Published in TOMS Volume 44, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

FP7/2007-2013 programme
European Unions Horizon 2020 research and innovation programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
204
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Treister EYovel R(2023)A hybrid shifted Laplacian multigrid and domain decomposition preconditioner for the elastic Helmholtz equationsJournal of Computational Physics10.1016/j.jcp.2023.112622(112622)Online publication date: Nov-2023
https://doi.org/10.1016/j.jcp.2023.112622
Munch PKormann KKronbichler M(2021)hyper.deal: An Efficient, Matrix-free Finite-element Library for High-dimensional Partial Differential EquationsACM Transactions on Mathematical Software10.1145/346972047:4(1-34)Online publication date: 31-Dec-2021
https://dl.acm.org/doi/10.1145/3469720
Reinarz ACharrier DBader MBovard LDumbser MDuru KFambri FGabriel AGallard JKöppel SKrenz LRannabauer LRezzolla LSamfass PTavelli MWeinzierl T(2020)ExaHyPE: An engine for parallel dynamically adaptive simulations of wave problemsComputer Physics Communications10.1016/j.cpc.2020.107251(107251)Online publication date: Mar-2020
https://doi.org/10.1016/j.cpc.2020.107251
Murray CWeinzierl T(2020)Lazy Stencil Integration in Multigrid AlgorithmsParallel Processing and Applied Mathematics10.1007/978-3-030-43229-4_3(25-37)Online publication date: 19-Mar-2020
https://doi.org/10.1007/978-3-030-43229-4_3
Murray CWeinzierl T(2020)Stabilized asynchronous fast adaptive composite multigrid using additive dampingNumerical Linear Algebra with Applications10.1002/nla.232828:3Online publication date: 24-Aug-2020
https://doi.org/10.1002/nla.2328
Murray CWeinzierl T(2020)Delayed approximate matrix assembly in multigrid with dynamic precisionsConcurrency and Computation: Practice and Experience10.1002/cpe.594133:11Online publication date: 22-Jul-2020
https://doi.org/10.1002/cpe.5941
Weinzierl T(2019)The Peano Software—Parallel, Automaton-based, Dynamically Adaptive Grid TraversalsACM Transactions on Mathematical Software10.1145/331979745:2(1-41)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3319797
Červený JDobrev VKolev T(2019)Nonconforming Mesh Refinement for High-Order Finite ElementsSIAM Journal on Scientific Computing10.1137/18M119399241:4(C367-C392)Online publication date: 25-Jul-2019
https://doi.org/10.1137/18M1193992
Weinzierl MWeinzierl T(2018)Quasi-matrix-free Hybrid Multigrid on Dynamically Adaptive Cartesian GridsACM Transactions on Mathematical Software10.1145/316528044:3(1-44)Online publication date: 6-Feb-2018
https://dl.acm.org/doi/10.1145/3165280
Treister EHaber E(2018)A multigrid solver to the Helmholtz equation with a point source based on travel time and amplitudeNumerical Linear Algebra with Applications10.1002/nla.220626:1Online publication date: 27-Jul-2018
https://doi.org/10.1002/nla.2206
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents