Convergence of restricted additive Schwarz with impedance transmission conditions for discretised Helmholtz problems
HTML articles powered by AMS MathViewer
- by Shihua Gong, Ivan G. Graham and Euan A. Spence;
- Math. Comp. 92 (2023), 175-215
- DOI: https://doi.org/10.1090/mcom/3772
- Published electronically: October 6, 2022
- HTML | PDF | Request permission
Abstract:
The Restricted Additive Schwarz method with impedance transmission conditions, also known as the Optimised Restricted Additive Schwarz (ORAS) method, is a simple overlapping one-level parallel domain decomposition method, which has been successfully used as an iterative solver and as a preconditioner for discretised Helmholtz boundary-value problems. In this paper, we give, for the first time, a convergence analysis for ORAS as an iterative solver—and also as a preconditioner—for nodal finite element Helmholtz systems of any polynomial order. The analysis starts by showing (for general domain decompositions) that ORAS is an unconventional finite element approximation of a classical parallel iterative Schwarz method, formulated at the PDE (non-discrete) level. This non-discrete Schwarz method was recently analysed in [Gong, Gander, Graham, Lafontaine, and Spence, Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation], and the present paper gives a corresponding discrete version of this analysis. In particular, for domain decompositions in strips in 2-d, we show that, when the mesh size is small enough, ORAS inherits the convergence properties of the Schwarz method, independent of polynomial order. The proof relies on characterising the ORAS iteration in terms of discrete ‘impedance-to-impedance maps’, which we prove (via a novel weighted finite-element error analysis) converge as $h\rightarrow 0$ in the operator norm to their non-discrete counterparts.References
- 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
- M. Bonazzoli, V. Dolean, I. G. Graham, E. A. Spence, and P.-H. Tournier, Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption, Math. Comp. 88 (2019), no. 320, 2559–2604. MR 3985469, DOI 10.1090/mcom/3447
- Niall Bootland, Victorita Dolean, Pierre Jolivet, and Pierre-Henri Tournier, A comparison of coarse spaces for Helmholtz problems in the high frequency regime, Comput. Math. Appl. 98 (2021), 239–253. MR 4299039, DOI 10.1016/j.camwa.2021.07.011
- T. Chaumont-Frelet and S. Nicaise, High-frequency behaviour of corner singularities in Helmholtz problems, ESAIM Math. Model. Numer. Anal. 52 (2018), no. 5, 1803–1845. MR 3881571, DOI 10.1051/m2an/2018031
- Théophile Chaumont-Frelet, Serge Nicaise, and Jérôme Tomezyk, Uniform a priori estimates for elliptic problems with impedance boundary conditions, Commun. Pure Appl. Anal. 19 (2020), no. 5, 2445–2471. MR 4153517, DOI 10.3934/cpaa.2020107
- 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
- Xavier Claeys and Emile Parolin, Robust treatment of cross-points in optimized Schwarz methods, Numer. Math. 151 (2022), no. 2, 405–442. MR 4433119, DOI 10.1007/s00211-022-01288-x
- Bruno Després, Méthodes de décomposition de domaine pour les problèmes de propagation d’ondes en régime harmonique. Le théorème de Borg pour l’équation de Hill vectorielle, Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt, 1991 (French, with English and French summaries). Thèse, Université de Paris IX (Dauphine), Paris, 1991. MR 1291197
- B. Després, A. Nicolopoulos, and B. Thierry, Corners and stable optimized domain decomposition methods for the Helmholtz problem, Numer. Math. 149 (2021), no. 4, 779–818. MR 4344598, DOI 10.1007/s00211-021-01251-2
- Victorita Dolean, Pierre Jolivet, and Frédéric Nataf, An introduction to domain decomposition methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2015. Algorithms, theory, and parallel implementation. MR 3450068, DOI 10.1137/1.9781611974065.ch1
- Yu Du and Haijun Wu, Preasymptotic error analysis of higher order FEM and CIP-FEM for Helmholtz equation with high wave number, SIAM J. Numer. Anal. 53 (2015), no. 2, 782–804. MR 3324975, DOI 10.1137/140953125
- Todd Dupont and Ridgway Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441–463. MR 559195, DOI 10.1090/S0025-5718-1980-0559195-7
- Evridiki Efstathiou and Martin J. Gander, Why restricted additive Schwarz converges faster than additive Schwarz, BIT 43 (2003), no. suppl., 945–959. MR 2058877, DOI 10.1023/B:BITN.0000014563.33622.1d
- Björn Engquist and Lexing Ying, Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers, Multiscale Model. Simul. 9 (2011), no. 2, 686–710. MR 2818416, DOI 10.1137/100804644
- 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
- Xiaobing Feng and Haijun Wu, Discontinuous Galerkin methods for the Helmholtz equation with large wave number, SIAM J. Numer. Anal. 47 (2009), no. 4, 2872–2896. MR 2551150, DOI 10.1137/080737538
- Xiaobing Feng and Haijun Wu, $hp$-discontinuous Galerkin methods for the Helmholtz equation with large wave number, Math. Comp. 80 (2011), no. 276, 1997–2024. MR 2813347, DOI 10.1090/S0025-5718-2011-02475-0
- 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 and Hui Zhang, A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods, SIAM Rev. 61 (2019), no. 1, 3–76. MR 3908314, DOI 10.1137/16M109781X
- S. Gong, M. J. Gander, I. G. Graham, D. Lafontaine, and E. A. Spence, Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation, Numer. Math., to appear, arXiv:2106.05218, 2021.
- S. Gong, M. J. Gander, I. G. Graham, and E. A. Spence, A variational interpretation of restricted additive Schwarz with impedance transmission condition for the Helmholtz problem, Proceedings of 26th Domain Decomposition Conference, 279–286 arXiv:2103.11379, 2022.
- Shihua Gong, Ivan G. Graham, and Euan A. Spence, Domain decomposition preconditioners for high-order discretizations of the heterogeneous Helmholtz equation, IMA J. Numer. Anal. 41 (2021), no. 3, 2139–2185. MR 4286258, DOI 10.1093/imanum/draa080
- Ivan G. Graham, Euan A. Spence, and Jun Zou, Domain decomposition with local impedance conditions for the Helmholtz equation with absorption, SIAM J. Numer. Anal. 58 (2020), no. 5, 2515–2543. MR 4150274, DOI 10.1137/19M1272512
- F. Hecht, Freefem++ manual (version 3.58-1), 2019.
- 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
- D. Lafontaine and E. A. Spence, Sharp bounds on Helmholtz impedance-to-impedance maps and application to overlapping domain decomposition, In preparation, 2021.
- D. Lafontaine, E. A. Spence, and J. Wunsch, A sharp relative-error bound for the Helmholtz $h$-FEM at high frequency, Numer. Math. 150 (2022), no. 1, 137–178. MR 4363822, DOI 10.1007/s00211-021-01253-0
- William McLean, Strongly elliptic systems and boundary integral equations, Cambridge University Press, Cambridge, 2000. MR 1742312
- A. Modave, A. Royer, X. Antoine, and C. Geuzaine, A non-overlapping domain decomposition method with high-order transmission conditions and cross-point treatment for Helmholtz problems, Comput. Methods Appl. Mech. Engrg. 368 (2020), 113162, 23. MR 4106670, DOI 10.1016/j.cma.2020.113162
- O. R. Pembery, The Helmholtz equation in heterogeneous and random media: analysis and numerics. PhD Thesis, University of Bath, 2020, https://researchportal.bath.ac.uk/en/studentTheses/the-helmholtz-equation-in-heterogeneous-and-random-media-analysis.
- S. A. Sauter, A refined finite element convergence theory for highly indefinite Helmholtz problems, Computing 78 (2006), no. 2, 101–115. MR 2255368, DOI 10.1007/s00607-006-0177-z
- Francisco-Javier Sayas, Thomas S. Brown, and Matthew E. Hassell, Variational techniques for elliptic partial differential equations, CRC Press, Boca Raton, FL, 2019. Theoretical tools and advanced applications. MR 3930592, DOI 10.1201/9780429507069
- Alfred H. Schatz, An observation concerning Ritz-Galerkin methods with indefinite bilinear forms, Math. Comp. 28 (1974), 959–962. MR 373326, DOI 10.1090/S0025-5718-1974-0373326-0
- 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. St-Cyr, M. J. Gander, and S. J. Thomas, Optimized multiplicative, additive, and restricted additive Schwarz preconditioning, SIAM J. Sci. Comput. 29 (2007), no. 6, 2402–2425. MR 2357620, DOI 10.1137/060652610
- Matthias Taus, Leonardo Zepeda-Núñez, Russell J. Hewett, and Laurent Demanet, L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation, J. Comput. Phys. 420 (2020), 109706, 32. MR 4126398, DOI 10.1016/j.jcp.2020.109706
- P.-H. Tournier, I. Aliferis, M. Bonazzoli et al., Microwave tomographic imaging of cerebrovascular accidents by using high-performance computing, Parallel Comput. 85 (2019), 88–97. MR 3940974, DOI 10.1016/j.parco.2019.02.004
- Haijun Wu, Pre-asymptotic error analysis of CIP-FEM and FEM for the Helmholtz equation with high wave number. Part I: linear version, IMA J. Numer. Anal. 34 (2014), no. 3, 1266–1288. MR 3232452, DOI 10.1093/imanum/drt033
Bibliographic Information
- Shihua Gong
- Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom
- Address at time of publication: School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen, Guangdong 518172, China
- MR Author ID: 1240731
- ORCID: 0000-0003-3650-2283
- Email: gongshihua@cuhk.edu.cn
- Ivan G. Graham
- Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom
- MR Author ID: 76020
- ORCID: 0000-0002-5730-676X
- Email: i.g.graham@bath.ac.uk
- Euan A. Spence
- Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom
- MR Author ID: 858295
- ORCID: 0000-0003-1236-4592
- Email: e.a.spence@bath.ac.uk
- Received by editor(s): October 29, 2021
- Received by editor(s) in revised form: June 3, 2022
- Published electronically: October 6, 2022
- Additional Notes: The authors gratefully acknowledge support from the UK Engineering and Physical Sciences Research Council Grants EP/R005591/1 (EAS) and EP/S003975/1 (SG, IGG, and EAS)
- © Copyright 2022 American Mathematical Society
- Journal: Math. Comp. 92 (2023), 175-215
- MSC (2020): Primary 35J05, 65N55, 65N22; Secondary 65F08
- DOI: https://doi.org/10.1090/mcom/3772
- MathSciNet review: 4496963