Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption

Bonazzoli, M.; Dolean, V.; Graham, I.; Spence, E.; Tournier, P.-H.

doi:10.1090/mcom/3447

Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption
HTML articles powered by AMS MathViewer

by M. Bonazzoli, V. Dolean, I. G. Graham, E. A. Spence and P.-H. Tournier HTML | PDF

Math. Comp. 88 (2019), 2559-2604 Request permission

Abstract:

This paper rigorously analyses preconditioners for the time- harmonic Maxwell equations with absorption, where the PDE is discretised using curl-conforming finite-element methods of fixed, arbitrary order and the preconditioner is constructed using additive Schwarz domain decomposition methods. The theory developed here shows that if the absorption is large enough, and if the subdomain and coarse mesh diameters and overlap are chosen appropriately, then the classical two-level overlapping additive Schwarz preconditioner (with PEC boundary conditions on the subdomains) performs optimally—in the sense that GMRES converges in a wavenumber-independent number of iterations—for the problem with absorption. An important feature of the theory is that it allows the coarse space to be built from low-order elements even if the PDE is discretised using high-order elements. It also shows that additive methods with minimal overlap can be robust. Numerical experiments are given that illustrate the theory and its dependence on various parameters. These experiments motivate some extensions of the preconditioners which have better robustness for problems with less absorption, including the propagative case. At the end of the paper we illustrate the performance of these on two substantial applications; the first (a problem with absorption arising from medical imaging) shows the empirical robustness of the preconditioner against heterogeneity, and the second (scattering by a COBRA cavity) shows good scalability of the preconditioner with up to 3,000 processors.

References

Patrick R. Amestoy, Iain S. Duff, Jean-Yves L’Excellent, and Jacko Koster, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl. 23 (2001), no. 1, 15–41. MR 1856597, DOI 10.1137/S0895479899358194
C. Amrouche, C. Bernardi, M. Dauge, and V. Girault, Vector potentials in three-dimensional non-smooth domains, Math. Methods Appl. Sci. 21 (1998), no. 9, 823–864 (English, with English and French summaries). MR 1626990, DOI 10.1002/(SICI)1099-1476(199806)21:9<823::AID-MMA976>3.0.CO;2-B
Douglas N. Arnold, Richard S. Falk, and Ragnar Winther, Multigrid in $H(\textrm {div})$ and $H(\textrm {curl})$, Numer. Math. 85 (2000), no. 2, 197–217. MR 1754719, DOI 10.1007/PL00005386
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
C. Bernardi, M. Dauge, and Y. Maday Polynomials in the Sobolev world, HAL report hal-00153795, 2007.
M. Bonazzoli, V. Dolean, I. G. Graham, E. A. Spence, and P.-H. Tournier, A two-level domain-decomposition preconditioner for the time-harmonic Maxwell’s equations, Domain Decomposition Methods in Science and Engineering XXIV, Lecture Notes in Computational Science and Engineering, vol. 125, Springer, 2018, pp. 149–157.
M. Bonazzoli, V. Dolean, I. G. Graham, E. A. Spence, and P.-H. Tournier, Two-level preconditioners for the Helmholtz equation, Domain Decomposition Methods in Science and Engineering XXIV, Lecture Notes in Computational Science and Engineering, vol. 125, Springer, 2018, pp. 139–147.
Marcella Bonazzoli and Francesca Rapetti, High-order finite elements in numerical electromagnetism: degrees of freedom and generators in duality, Numer. Algorithms 74 (2017), no. 1, 111–136. MR 3590392, DOI 10.1007/s11075-016-0141-8
Y. Boubendir, X. Antoine, and C. Geuzaine, A quasi-optimal non-overlapping domain decomposition algorithm for the Helmholtz equation, J. Comput. Phys. 231 (2012), no. 2, 262–280. MR 2872075, DOI 10.1016/j.jcp.2011.08.007
Xiao-Chuan Cai, Mario A. Casarin, Frank W. Elliott Jr., and Olof B. Widlund, Overlapping Schwarz algorithms for solving Helmholtz’s equation, Domain decomposition methods, 10 (Boulder, CO, 1997) Contemp. Math., vol. 218, Amer. Math. Soc., Providence, RI, 1998, pp. 391–399. MR 1649635, DOI 10.1090/conm/218/03034
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
Pierre-Henri Cocquet and Martin J. Gander, How large a shift is needed in the shifted Helmholtz preconditioner for its effective inversion by multigrid?, SIAM J. Sci. Comput. 39 (2017), no. 2, A438–A478. MR 3623699, DOI 10.1137/15M102085X
David Colton and Rainer Kress, Inverse acoustic and electromagnetic scattering theory, 2nd ed., Applied Mathematical Sciences, vol. 93, Springer-Verlag, Berlin, 1998. MR 1635980, DOI 10.1007/978-3-662-03537-5
Lea Conen, Victorita Dolean, Rolf Krause, and Frédéric Nataf, A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator, J. Comput. Appl. Math. 271 (2014), 83–99. MR 3209915, DOI 10.1016/j.cam.2014.03.031
M. Costabel, M. Dauge, and S. Nicaise, Corner singularities and analytic regularity for linear elliptic systems. Part i: Smooth domains, 2010. https://hal.archives-ouvertes.fr/file/index/docid/453934/filename/CoDaNi_Analytic_Part_I.pdf.
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
Monique Dauge, Neumann and mixed problems on curvilinear polyhedra, Integral Equations Operator Theory 15 (1992), no. 2, 227–261. MR 1147281, DOI 10.1007/BF01204238
M. Dauge, Regularity and singularities in polyhedral domains: The case of Laplace and Maxwell equations, 2008. https://perso.univ-rennes1.fr/monique.dauge/publis/Talk_Karlsruhe08.pdf.
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
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
Victorita Dolean, Martin J. Gander, Stephane Lanteri, Jin-Fa Lee, and Zhen Peng, Effective transmission conditions for domain decomposition methods applied to the time-harmonic curl-curl Maxwell’s equations, J. Comput. Phys. 280 (2015), 232–247. MR 3273134, DOI 10.1016/j.jcp.2014.09.024
Michael Eiermann and Oliver G. Ernst, Geometric aspects of the theory of Krylov subspace methods, Acta Numer. 10 (2001), 251–312. MR 2009695, DOI 10.1017/S0962492901000046
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
M. El Bouajaji, V. Dolean, M. J. Gander, and S. Lanteri, Optimized Schwarz methods for the time-harmonic Maxwell equations with damping, SIAM J. Sci. Comput. 34 (2012), no. 4, A2048–A2071. MR 2970396, DOI 10.1137/110842995
H. C. Elman, Iterative methods for sparse nonsymmetric systems of linear equations, PhD thesis, Yale University, 1982.
Bjorn Engquist and Hong-Kai Zhao, Absorbing boundary conditions for domain decomposition, Appl. Numer. Math. 27 (1998), no. 4, 341–365. Absorbing boundary conditions. MR 1644668, DOI 10.1016/S0168-9274(98)00019-1
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
Charbel Farhat, Michel Lesoinne, Patrick LeTallec, Kendall Pierson, and Daniel Rixen, FETI-DP: a dual-primal unified FETI method. I. A faster alternative to the two-level FETI method, Internat. J. Numer. Methods Engrg. 50 (2001), no. 7, 1523–1544. MR 1813746, DOI 10.1002/nme.76
Charbel Farhat, Antonini Macedo, and Michel Lesoinne, A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems, Numer. Math. 85 (2000), no. 2, 283–308. MR 1754722, DOI 10.1007/PL00005389
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
Martin J. Gander and Hui Zhang, Optimized Schwarz methods with overlap for the Helmholtz equation, SIAM J. Sci. Comput. 38 (2016), no. 5, A3195–A3219. MR 3554882, DOI 10.1137/15M1021659
Vivette Girault and Pierre-Arnaud Raviart, Finite element methods for Navier-Stokes equations, Springer Series in Computational Mathematics, vol. 5, Springer-Verlag, Berlin, 1986. Theory and algorithms. MR 851383, DOI 10.1007/978-3-642-61623-5
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
Jayadeep Gopalakrishnan, Joseph E. Pasciak, and Leszek F. Demkowicz, Analysis of a multigrid algorithm for time harmonic Maxwell equations, SIAM J. Numer. Anal. 42 (2004), no. 1, 90–108. MR 2051058, DOI 10.1137/S003614290139490X
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
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, E. A. Spence, and E. Vainikko, Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption, Math. Comp. 86 (2017), no. 307, 2089–2127. MR 3647952, DOI 10.1090/mcom/3190
Ivan G. Graham, Euan A. Spence, and Eero Vainikko, Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption, Modern solvers for Helmholtz problems, Geosyst. Math., Birkhäuser/Springer, Cham, 2017, pp. 3–26. MR 3644970
I. G. Graham, E. A. Spence, and J. Zou, Domain decompositon with local impedance condition for the Helmholtz equation, arXiv preprint arXiv:1806.03731, 2018.
P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR 775683
Karl E. Gustafson and Duggirala K. M. Rao, Numerical range, Universitext, Springer-Verlag, New York, 1997. The field of values of linear operators and matrices. MR 1417493, DOI 10.1007/978-1-4613-8498-4
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
R. Hiptmair, Finite elements in computational electromagnetism, Acta Numer. 11 (2002), 237–339. MR 2009375, DOI 10.1017/S0962492902000041
Ralf Hiptmair, Andrea Moiola, and Ilaria Perugia, Stability results for the time-harmonic Maxwell equations with impedance boundary conditions, Math. Models Methods Appl. Sci. 21 (2011), no. 11, 2263–2287. MR 2860676, DOI 10.1142/S021820251100574X
Ralf Hiptmair and Andrea Toselli, Overlapping and multilevel Schwarz methods for vector valued elliptic problems in three dimensions, Parallel solution of partial differential equations (Minneapolis, MN, 1997) IMA Vol. Math. Appl., vol. 120, Springer, New York, 2000, pp. 181–208. MR 1838270, DOI 10.1007/978-1-4612-1176-1_{8}
Jianming Jin, The finite element method in electromagnetics, 2nd ed., Wiley-Interscience [John Wiley & Sons], New York, 2002. MR 1903357
George Karypis and Vipin Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput. 20 (1998), no. 1, 359–392. MR 1639073, DOI 10.1137/S1064827595287997
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
Kristin Kirchner, Karsten Urban, and Oliver Zeeb, Maxwell’s equations for conductors with impedance boundary conditions: discontinuous Galerkin and reduced basis methods, ESAIM Math. Model. Numer. Anal. 50 (2016), no. 6, 1763–1787. MR 3580121, DOI 10.1051/m2an/2016006
Domenico Lahaye, Jok Tang, and Kees Vuik (eds.), Modern solvers for Helmholtz problems, Geosystems Mathematics, Birkhäuser/Springer, Cham, 2017. MR 3560300, DOI 10.1007/978-3-319-28832-1
Rolf Leis, Initial-boundary value problems in mathematical physics, B. G. Teubner, Stuttgart; John Wiley & Sons, Ltd., Chichester, 1986. MR 841971, DOI 10.1007/978-3-663-10649-4
J. Liesen and P. Tichỳ, The field of values bound on ideal GMRES, arXiv preprint arXiv:1211.5969, 2012.
J. Liu and J.-M. Jin, Scattering analysis of a large body with deep cavities, IEEE Trans. on Antennas and Propagation, 51 2003, no. 6, 1157–1167.
William McLean, Strongly elliptic systems and boundary integral equations, Cambridge University Press, Cambridge, 2000. MR 1742312
Jens Markus Melenk, On generalized finite-element methods, ProQuest LLC, Ann Arbor, MI, 1995. Thesis (Ph.D.)–University of Maryland, College Park. MR 2692949
A. Moiola, Trefftz-discontinuous Galerkin methods for time-harmonic wave problems, PhD thesis, Seminar for applied mathematics, ETH Zürich, 2011. Available at http://e-collection.library.ethz.ch/view/eth:4515.
A. Moiola and E. A. Spence, Explicit bounds for the time-harmonic Maxwell equations in heterogeneous media, In preparation, 2019.
Peter Monk, A finite element method for approximating the time-harmonic Maxwell equations, Numer. Math. 63 (1992), no. 2, 243–261. MR 1182977, DOI 10.1007/BF01385860
Peter Monk, Finite element methods for Maxwell’s equations, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2003. MR 2059447, DOI 10.1093/acprof:oso/9780198508885.001.0001
P. Le Tallec, A mixed finite element approximation of the Navier-Stokes equations, Numer. Math. 35 (1980), no. 4, 381–404. MR 593835, DOI 10.1007/BF01399007
J. E. Pasciak and J. Zhao, Overlapping Schwarz methods in $H$(curl) on polyhedral domains, J. Numer. Math. 10 (2002), no. 3, 221–234. MR 1935967, DOI 10.1515/JNMA.2002.221
Stefan A. Sauter and Christoph Schwab, Boundary element methods, Springer Series in Computational Mathematics, vol. 39, Springer-Verlag, Berlin, 2011. Translated and expanded from the 2004 German original. MR 2743235, DOI 10.1007/978-3-540-68093-2
Achim Schädle and Lin Zschiedrich, Additive Schwarz method for scattering problems using the PML method at interfaces, Domain decomposition methods in science and engineering XVI, Lect. Notes Comput. Sci. Eng., vol. 55, Springer, Berlin, 2007, pp. 205–212. MR 2334105, DOI 10.1007/978-3-540-34469-8_{2}1
J. Schöberl, Commuting quasi-interpolation operators for mixed finite elements, Preprint ISC-01-10-MATH, Texas A&M University, College Station, TX, 2001. http://www.asc.tuwien.ac.at/~schoeberl/wiki/images/1/1e/Paper.pdf.
J. Schöberl, Numerical methods for Maxwell equations, 2009. http://www.asc.tuwien.ac.at/~schoeberl/wiki/lva/notes/maxwell.pdf.
Valeria Simoncini and Daniel B. Szyld, Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl. 14 (2007), no. 1, 1–59. MR 2289520, DOI 10.1002/nla.499
Gerhard Starke, Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems, Numer. Math. 78 (1997), no. 1, 103–117. MR 1483571, DOI 10.1007/s002110050306
J. M. Tang, R. Nabben, C. Vuik, and Y. A. Erlangga, Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods, J. Sci. Comput. 39 (2009), no. 3, 340–370. MR 2506657, DOI 10.1007/s10915-009-9272-6
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, Overlapping Schwarz methods for Maxwell’s equations in three dimensions, Numer. Math. 86 (2000), no. 4, 733–752. MR 1794350, DOI 10.1007/PL00005417
P.-H. Tournier, I. Aliferis, M. Bonazzoli, M. de Buhan, M. Darbas, V. Dolean, F. Hecht, P. Jolivet, I. El Kanfoud, C. Migliaccio, F. Nataf, Ch. Pichot, and S. Semenov, Microwave tomographic imaging of cerebrovascular accidents by using high-performance computing, Parallel Computing, 2019.
Hans Triebel, Theory of function spaces, Monographs in Mathematics, vol. 78, Birkhäuser Verlag, Basel, 1983. MR 781540, DOI 10.1007/978-3-0346-0416-1