Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption
HTML articles powered by AMS MathViewer
- by I. G. Graham, E. A. Spence and E. Vainikko PDF
- Math. Comp. 86 (2017), 2089-2127 Request permission
Abstract:
In this paper we give new results on domain decomposition preconditioners for GMRES when computing piecewise linear finite-element approximations of the Helmholtz equation $-\Delta u - (k^2+ \mathrm {i} \varepsilon )u = f$, with absorption parameter $\varepsilon \in \mathbb {R}$. Multigrid approximations of this equation with $\varepsilon \not = 0$ are commonly used as preconditioners for the pure Helmholtz case ($\varepsilon = 0$). However a rigorous theory for such (so-called “shifted Laplace”) preconditioners, either for the pure Helmholtz equation, or even the absorptive equation ($\varepsilon \not =0$), is still missing. We present a new theory for the absorptive equation that provides rates of convergence for (left- or right-) preconditioned GMRES, via estimates of the norm and field of values of the preconditioned matrix. This theory uses a $k$- and $\varepsilon$-explicit coercivity result for the underlying sesquilinear form and shows, for example, that if $|\varepsilon |\sim k^2$, then classical overlapping Additive Schwarz will perform optimally for the damped problem, provided the subdomain and coarse mesh diameters are carefully chosen. Extensive numerical experiments are given that support the theoretical results. While the theory applies to a certain weighted variant of GMRES, the experiments for both weighted and classical GMRES give comparable results. The theory for the absorptive case gives insight into how its domain decomposition approximations perform as preconditioners for the pure Helmholtz case $\varepsilon = 0$. At the end of the paper we propose a (scalable) multilevel preconditioner for the pure Helmholtz problem that has an empirical computation time complexity of about $\mathcal {O}(n^{4/3})$ for solving finite-element systems of size $n=\mathcal {O}(k^3)$, where we have chosen the mesh diameter $h \sim k^{-3/2}$ to avoid the pollution effect. Experiments on problems with $h\sim k^{-1}$, i.e., a fixed number of grid points per wavelength, are also given.References
- B. Beckermann, S. A. Goreinov, and E. E. Tyrtyshnikov, Some remarks on the Elman estimate for GMRES, SIAM J. Matrix Anal. Appl. 27 (2005), no. 3, 772–778. MR 2208334, DOI 10.1137/040618849
- Jean-David Benamou and Bruno Desprès, A domain decomposition method for the Helmholtz equation and related optimal control problems, J. Comput. Phys. 136 (1997), no. 1, 68–82. MR 1468624, DOI 10.1006/jcph.1997.5742
- Xiao-Chuan Cai and Marcus Sarkis, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput. 21 (1999), no. 2, 792–797. MR 1718707, DOI 10.1137/S106482759732678X
- Xiao-Chuan Cai and Olof B. Widlund, Domain decomposition algorithms for indefinite elliptic problems, SIAM J. Sci. Statist. Comput. 13 (1992), no. 1, 243–258. MR 1145185, DOI 10.1137/0913013
- Xiao-Chuan Cai and Jun Zou, Some observations on the $l^2$ convergence of the additive Schwarz preconditioned GMRES method, Numer. Linear Algebra Appl. 9 (2002), no. 5, 379–397. MR 1913211, DOI 10.1002/nla.280
- Zhiming Chen and Xueshuang Xiang, A source transfer domain decomposition method for Helmholtz equations in unbounded domain Part II: Extensions, Numer. Math. Theory Methods Appl. 6 (2013), no. 3, 538–555. MR 3081789
- Zhiming Chen and Xueshuang Xiang, A source transfer domain decomposition method for Helmholtz equations in unbounded domain, SIAM J. Numer. Anal. 51 (2013), no. 4, 2331–2356. MR 3085122, DOI 10.1137/130917144
- P-H. Cocquet and M. Gander, Analysis of multigrid performance for finite element discretizations of the shifted Helmholtz equation, preprint (2014).
- Siegfried Cools and Wim Vanroose, Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems, Numer. Linear Algebra Appl. 20 (2013), no. 4, 575–597. MR 3084822, DOI 10.1002/nla.1881
- Monique Dauge, Elliptic boundary value problems on corner domains, Lecture Notes in Mathematics, vol. 1341, Springer-Verlag, Berlin, 1988. Smoothness and asymptotics of solutions. MR 961439, DOI 10.1007/BFb0086682
- V. Dolean, M. J. Gander, and L. Gerardo-Giorda, Optimized Schwarz methods for Maxwell’s equations, SIAM J. Sci. Comput. 31 (2009), no. 3, 2193–2213. MR 2516149, DOI 10.1137/080728536
- Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983), no. 2, 345–357. MR 694523, DOI 10.1137/0720023
- H. C. Elman, Iterative methods for sparse nonsymmetric systems of linear equations, Ph.D. thesis, Yale University, 1982.
- Björn Engquist and Lexing Ying, Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation, Comm. Pure Appl. Math. 64 (2011), no. 5, 697–735. MR 2789492, DOI 10.1002/cpa.20358
- Yogi A. Erlangga, Advances in iterative methods and preconditioners for the Helmholtz equation, Arch. Comput. Methods Eng. 15 (2008), no. 1, 37–66. MR 2387515, DOI 10.1007/s11831-007-9013-7
- Y. A. Erlangga, C. W. Oosterlee, and C. Vuik, A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM J. Sci. Comput. 27 (2006), no. 4, 1471–1492. MR 2199758, DOI 10.1137/040615195
- Y. A. Erlangga, C. Vuik, and C. W. Oosterlee, On a class of preconditioners for solving the Helmholtz equation, Appl. Numer. Math. 50 (2004), no. 3-4, 409–425. MR 2074012, DOI 10.1016/j.apnum.2004.01.009
- O. G. Ernst and M. J. Gander, Why it is difficult to solve Helmholtz problems with classical iterative methods, Numerical analysis of multiscale problems, Lect. Notes Comput. Sci. Eng., vol. 83, Springer, Heidelberg, 2012, pp. 325–363. MR 3050918, DOI 10.1007/978-3-642-22061-6_{1}0
- Azeddine Essai, Weighted FOM and GMRES for solving nonsymmetric linear systems, Numer. Algorithms 18 (1998), no. 3-4, 277–292. MR 1669954, DOI 10.1023/A:1019177600806
- M. J. Gander, L. Halpern, and F. Magoulès, An optimized Schwarz method with two-sided Robin transmission conditions for the Helmholtz equation, Internat. J. Numer. Methods Fluids 55 (2007), no. 2, 163–175. MR 2344706, DOI 10.1002/fld.1433
- M. J. Gander, I. G. Graham, and E. A. Spence, Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: what is the largest shift for which wavenumber-independent convergence is guaranteed?, Numer. Math. 131 (2015), no. 3, 567–614. MR 3395145, DOI 10.1007/s00211-015-0700-2
- Martin J. Gander, Frédéric Magoulès, and Frédéric Nataf, Optimized Schwarz methods without overlap for the Helmholtz equation, SIAM J. Sci. Comput. 24 (2002), no. 1, 38–60. MR 1924414, DOI 10.1137/S1064827501387012
- Jayadeep Gopalakrishnan and Joseph E. Pasciak, Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations, Math. Comp. 72 (2003), no. 241, 1–15. MR 1933811, DOI 10.1090/S0025-5718-01-01406-5
- I. G. Graham, M. Löhndorf, J. M. Melenk, and E. A. Spence, When is the error in the $h$-BEM for solving the Helmholtz equation bounded independently of $k$?, BIT 55 (2015), no. 1, 171–214. MR 3313606, DOI 10.1007/s10543-014-0501-5
- I. G. Graham and R. Scheichl, Robust domain decomposition algorithms for multiscale PDEs, Numer. Methods Partial Differential Equations 23 (2007), no. 4, 859–878. MR 2326197, DOI 10.1002/num.20254
- I. G. Graham, E. A. Spence, and E. Vainikko, Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption, Modern Solvers for Helmholtz Problems (Domenico Lahaye, Jok Tang, and Kees Vuik, eds.), Birkhauser series in Geosystems Mathematics, 2016.
- I. G. Graham, P. O. Lechner, and R. Scheichl, Domain decomposition for multiscale PDEs, Numer. Math. 106 (2007), no. 4, 589–626. MR 2317926, DOI 10.1007/s00211-007-0074-1
- P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR 775683
- Stefan Güttel and Jennifer Pestana, Some observations on weighted GMRES, Numer. Algorithms 67 (2014), no. 4, 733–752. MR 3277781, DOI 10.1007/s11075-013-9820-x
- Jung-Han Kimn and Marcus Sarkis, Restricted overlapping balancing domain decomposition methods and restricted coarse problems for the Helmholtz problem, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1507–1514. MR 2277034, DOI 10.1016/j.cma.2006.03.016
- Jung-Han Kimn and Marcus Sarkis, Shifted Laplacian RAS solvers for the Helmholtz equation, Domain decomposition methods in science and engineering XX, Lect. Notes Comput. Sci. Eng., vol. 91, Springer, Heidelberg, 2013, pp. 151–158. MR 3242986, DOI 10.1007/978-3-642-35275-1_{1}6
- Jan Mandel and Marian Brezina, Balancing domain decomposition for problems with large jumps in coefficients, Math. Comp. 65 (1996), no. 216, 1387–1401. MR 1351204, DOI 10.1090/S0025-5718-96-00757-0
- R. Nabben and C. Vuik, A comparison of deflation and coarse grid correction applied to porous media flow, SIAM J. Numer. Anal. 42 (2004), no. 4, 1631–1647. MR 2114294, DOI 10.1137/S0036142903430451
- J. Nečas, Les méthodes directes en théorie des équations elliptiques, Masson, 1967.
- Maxim A. Olshanskii and Eugene E. Tyrtyshnikov, Iterative methods for linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014. Theory and applications. MR 3243627, DOI 10.1137/1.9781611973464
- Marcus Sarkis and Daniel B. Szyld, Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1612–1621. MR 2277042, DOI 10.1016/j.cma.2006.03.027
- L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483–493. MR 1011446, DOI 10.1090/S0025-5718-1990-1011446-7
- A. H. Sheikh, D. Lahaye, and C. Vuik, On the convergence of shifted Laplace preconditioner combined with multilevel deflation, Numer. Linear Algebra Appl. 20 (2013), no. 4, 645–662. MR 3084825, DOI 10.1002/nla.1882
- E. A. Spence, Overview of variational formulations for linear elliptic PDEs, Unified transform for boundary value problems, SIAM, Philadelphia, PA, 2015, pp. 93–159. MR 3364235
- C. C. Stolk, A rapidly converging domain decomposition method for the Helmholtz equation, Journal of Computational Physics 241 (2013), 240–252.
- A. Toselli, Some results on overlapping Schwarz methods for the Helmholtz equation employing perfectly matched layers, Domain Decomposition Methods in Sciences and Engineering: Eleventh International Conference London, UK, Citeseer, 1998, pp. 539–545.
- Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
- M. B. van Gijzen, Y. A. Erlangga, and C. Vuik, Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian, SIAM J. Sci. Comput. 29 (2007), no. 5, 1942–1958. MR 2350014, DOI 10.1137/060661491
- Leonardo Zepeda-Núñez and Laurent Demanet, The method of polarized traces for the 2D Helmholtz equation, J. Comput. Phys. 308 (2016), 347–388. MR 3448251, DOI 10.1016/j.jcp.2015.11.040
Additional Information
- I. G. Graham
- Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom
- MR Author ID: 76020
- Email: I.G.Graham@bath.ac.uk
- E. A. Spence
- Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom
- MR Author ID: 858295
- Email: E.A.Spence@bath.ac.uk
- E. Vainikko
- Affiliation: Institute of Computer Science, University of Tartu, 50409, Estonia
- MR Author ID: 176540
- Email: eero.vainikko@ut.ee
- Received by editor(s): July 7, 2015
- Received by editor(s) in revised form: March 23, 2016
- Published electronically: February 8, 2017
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 2089-2127
- MSC (2010): Primary 35J05, 65N55; Secondary 65F08, 65F10, 65N30, 78A45
- DOI: https://doi.org/10.1090/mcom/3190
- MathSciNet review: 3647952