Absorbing boundary conditions for the wave equation and parallel computing

Gander, Martin; Halpern, Laurence

doi:10.1090/S0025-5718-04-01635-7

Absorbing boundary conditions for the wave equation and parallel computing
HTML articles powered by AMS MathViewer

by Martin J. Gander and Laurence Halpern PDF

Math. Comp. 74 (2005), 153-176 Request permission

Abstract:

Absorbing boundary conditions have been developed for various types of problems to truncate infinite domains in order to perform computations. But absorbing boundary conditions have a second, recent and important application: parallel computing. We show that absorbing boundary conditions are essential for a good performance of the Schwarz waveform relaxation algorithm applied to the wave equation. In turn this application gives the idea of introducing a layer close to the truncation boundary which leads to a new way of optimizing absorbing boundary conditions for truncating domains. We optimize the conditions in the case of straight boundaries and illustrate our analysis with numerical experiments both for truncating domains and the Schwarz waveform relaxation algorithm.

References

Alain Bamberger, Roland Glowinski, and Quang Huy Tran, A domain decomposition method for the acoustic wave equation with discontinuous coefficients and grid change, SIAM J. Numer. Anal. 34 (1997), no. 2, 603–639. MR 1442931, DOI 10.1137/S0036142994261518
Alvin Bayliss and Eli Turkel, Radiation boundary conditions for wave-like equations, Comm. Pure Appl. Math. 33 (1980), no. 6, 707–725. MR 596431, DOI 10.1002/cpa.3160330603
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
Morten Bjørhus, On domain decomposition, subdomain iteration and waveform relaxation, Ph.D. thesis, University of Trondheim, Norway, 1995.
Xiao-Chuan Cai, Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math. 60 (1991), no. 1, 41–61. MR 1131498, DOI 10.1007/BF01385713
Xiao-Chuan Cai, Multiplicative Schwarz methods for parabolic problems, SIAM J. Sci. Comput. 15 (1994), no. 3, 587–603. Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992). MR 1273154, DOI 10.1137/0915039
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), Amer. Math. Soc., Providence, RI, 1998, pp. 391–399.
Philippe Charton, Frédéric Nataf, and François Rogier, Méthode de décomposition de domaine pour l’équation d’advection-diffusion, C. R. Acad. Sci. Paris Sér. I Math. 313 (1991), no. 9, 623–626 (French, with English summary). MR 1133498
Philippe Chevalier and Frédéric Nataf, Symmetrized method with optimized second-order conditions for the Helmholtz equation, Domain decomposition methods, 10 (Boulder, CO, 1997), Amer. Math. Soc., Providence, RI, 1998, pp. 400–407.
P. Collino, G. Delbue, P. Joly, and A. Piacentini, A new interface condition in the non-overlapping domain decomposition method for the Maxwell equations, Comput. Methods Appl. Mech. Engrg. 148 (1997), no. 1-2, 195–207. MR 1460323, DOI 10.1016/S0045-7825(97)00014-5
Armel de La Bourdonnaye, Charbel Farhat, Antonini Macedo, Frédéric Magoulès, and François-Xavier Roux, A non-overlapping domain decomposition method for the exterior Helmholtz problem, Domain decomposition methods, 10 (Boulder, CO, 1997) Contemp. Math., vol. 218, Amer. Math. Soc., Providence, RI, 1998, pp. 42–66. MR 1645843, DOI 10.1090/conm/218/03001
Bruno Després, Patrick Joly, and Jean E. Roberts, A domain decomposition method for the harmonic Maxwell equations, Iterative methods in linear algebra (Brussels, 1991) (Amsterdam), North-Holland, 1992, pp. 475–484.
J. Douglas, Jr. and D. B. Meade, Second-order transmission conditions for the Helmholtz equation, Ninth International Conference on Domain Decomposition Methods (P. E. Bjørstad, M. Espedal, and D. Keyes, eds.), ddm.org, 1997, pp. 434–440.
B. Engquist and L. Halpern, Long-time behaviour of absorbing boundary conditions, Math. Methods Appl. Sci. 13 (1990), no. 3, 189–203. MR 1071439, DOI 10.1002/mma.1670130302
Bjorn Engquist and Andrew Majda, Absorbing boundary conditions for the numerical simulation of waves, Math. Comp. 31 (1977), no. 139, 629–651. MR 436612, DOI 10.1090/S0025-5718-1977-0436612-4
Martin J. Gander, Overlapping Schwarz for parabolic problems, Ninth International Conference on Domain Decomposition Methods (Petter E. Bjørstad, Magne Espedal, and David Keyes, eds.), ddm.org, 1997, pp. 97–104.
Jan Mandel, Charbel Farhat, and Xiao-Chuan Cai (eds.), Domain decomposition methods. 10, Contemporary Mathematics, vol. 218, American Mathematical Society, Providence, RI, 1998. MR 1649656, DOI 10.1090/conm/218
Martin J. Gander, A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations, Numer. Linear Algebra Appl. 6 (1999), no. 2, 125–145. Czech-US Workshop in Iterative Methods and Parallel Computing, Part 2 (Milovy, 1997). MR 1695405, DOI 10.1002/(SICI)1099-1506(199903)6:2<125::AID-NLA152>3.0.CO;2-4
—, Optimized Schwarz methods for Helmholtz problems, Thirteenth international conference on domain decomposition, 2001, pp. 245–252.
Martin J. Gander and Laurence Halpern, Méthodes de décomposition de domaines pour l’équation des ondes en dimension 1, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 6, 589–592 (French, with English and French summaries). MR 1860935, DOI 10.1016/S0764-4442(01)02084-5
Martin J. Gander and Laurence Halpern, Un algorithme discret de décomposition de domaines pour l’équation des ondes en dimension 1, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 7, 699–702 (French, with English and French summaries). MR 1869041, DOI 10.1016/S0764-4442(01)02083-3
Martin J. Gander, Laurence Halpern, and Frédéric Nataf, Optimal convergence for overlapping and nonoverlapping Schwarz waveform relaxation, Eleventh international Conference of Domain Decomposition Methods (C-H. Lai, P. Bjørstad, M. Cross, and O. Widlund, eds.), ddm.org, 1999.
Martin J. Gander, Laurence Halpern, and Frédéric Nataf, Optimized Schwarz methods, Twelfth International Conference on Domain Decomposition Methods, Chiba, Japan (Bergen) (Tony Chan, Takashi Kako, Hideo Kawarada, and Olivier Pironneau, eds.), Domain Decomposition Press, 2001, pp. 15–28.
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.
Martin J. Gander and Andrew M. Stuart, Space-time continuous analysis of waveform relaxation for the heat equation, SIAM J. Sci. Comput. 19 (1998), no. 6, 2014–2031. MR 1638096, DOI 10.1137/S1064827596305337
Martin J. Gander and Hongkai Zhao, Overlapping Schwarz waveform relaxation for parabolic problems in higher dimension, Proceedings of Algoritmy 14 (A. Handlovičová, Magda Komorníkova, and Karol Mikula, eds.), Slovak Technical University, September 1997, pp. 42–51.
Eldar Giladi and Herbert Keller, Space time domain decomposition for parabolic problems, Numerische Mathematik 93 (2002), no. 2, 279–313.
Laurence Halpern, Absorbing boundary conditions for the discretization schemes of the one-dimensional wave equation, Math. Comp. 38 (1982), no. 158, 415–429. MR 645659, DOI 10.1090/S0025-5718-1982-0645659-6
Laurence Halpern, Artificial boundary conditions for the linear advection diffusion equation, Math. Comp. 46 (1986), no. 174, 425–438. MR 829617, DOI 10.1090/S0025-5718-1986-0829617-8
Robert L. Higdon, Initial-boundary value problems for linear hyperbolic systems, SIAM Rev. 28 (1986), no. 2, 177–217. MR 839822, DOI 10.1137/1028050
Caroline Japhet, Optimized Krylov-Ventcell method. Application to convection-diffusion problems, Proceedings of the 9th international conference on domain decomposition methods (Petter E. Bjørstad, Magne S. Espedal, and David E. Keyes, eds.), ddm.org, 1998, pp. 382–389.
Caroline Japhet, Frederic Nataf, and Francois Rogier, The optimized order 2 method. Application to convection-diffusion problems, Future Generation Computer Systems FUTURE 18 (2001).
Caroline Japhet, Frederic Nataf, and Francois-Xavier Roux, The Optimized Order 2 Method with a coarse grid preconditioner. Application to convection-diffusion problems, Ninth International Conference on Domain Decomposition Methods in Science and Engineering (P. Bjorstad, M. Espedal, and D. Keyes, eds.), John Wiley & Sons, 1998, pp. 382–389.
J.-L. Lions and E. Magenes, Problèmes aux limites non homogènes et applications. Vol. 1, Travaux et Recherches Mathématiques, No. 17, Dunod, Paris, 1968 (French). MR 0247243
Lois C. McInnes, Romeo F. Susan-Resigna, David E. Keyes, and Hafiz M. Atassi, Additive Schwarz methods with nonreflecting boundary conditions for the parallel computation of Helmholtz problems, Domain decomposition methods, 10 (Boulder, CO, 1997), Amer. Math. Soc., 1998, pp. 325–333.
Roland Glowinski, Yuri A. Kuznetsov, Gérard Meurant, Jacques Périaux, and Olof B. Widlund (eds.), Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. MR 1106444
Ulla Miekkala and Olavi Nevanlinna, Convergence of dynamic iteration methods for initial value problem, SIAM J. Sci. Statist. Comput. 8 (1987), no. 4, 459–482. MR 892300, DOI 10.1137/0908046
Frederic Nataf, Absorbing boundary conditions in block Gauss-Seidel methods for convection problems, Math. Models Methods Appl. Sci. 6 (1996), no. 4, 481–502. MR 1395814, DOI 10.1142/S0218202596000183
F. Nataf and F. Nier, Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains, Numer. Math. 75 (1997), no. 3, 357–377. MR 1427713, DOI 10.1007/s002110050243
D. J. Newman, Rational approximation to $| x|$, Michigan Math. J. 11 (1964), 11–14. MR 171113
Alfio Quarteroni and Alberto Valli, Domain decomposition methods for partial differential equations, Numerical Mathematics and Scientific Computation, The Clarendon Press, Oxford University Press, New York, 1999. Oxford Science Publications. MR 1857663
Andrea Toselli, Some results on overlapping Schwarz methods for the Helmholtz equation employing perfectly matched layers, Tech. Report 765, Courant Institute, New York, June 1998.
Loic Tourrette and Laurence Halpern (eds.), Absorbing boundaries and layers, domain decomposition methods, application to large scale computations, Novascience, 2001.
Lloyd N. Trefethen and Laurence Halpern, Well-posedness of one-way wave equations and absorbing boundary conditions, Math. Comp. 47 (1986), no. 176, 421–435. MR 856695, DOI 10.1090/S0025-5718-1986-0856695-2
E. L. Wachspress, Optimum alternating-direction-implicit iteration parameters for a model problem, J. Soc. Indust. Appl. Math. 10 (1962), 339–350. MR 150935
Yunhai Wu, Xiao-Chuan Cai, and David E. Keyes, Additive Schwarz methods for hyperbolic equations, Tenth International Conference on Domain Decomposition Methods (J. Mandel, C. Farhat, and X.-C. Cai, eds.), AMS, Contemporary Mathematics 218, 1998, pp. 513–521.