Mathematics of Computation

Author(s): Martin J. Gander; Laurence Halpern.
Journal: Math. Comp. 74 (2005), 153-176.
MSC (2000): Primary 65M55, 35L20
Posted: March 18, 2004
Retrieve article in: PDF DVI PostScript

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.

1.: Alain Bamberger, Roland Glowinski, and Quang H. Tran, A domain decomposition method for the acoustic wave equation with discontinuous coefficients and grid change, SIAM Journal on Numerical Analysis 34 (1997), no. 2, 603-639. MR 98c:65161
2.: A. Bayliss and E. Turkel, Radiation boundary conditions for wave-like equations, Comm. Pure and Appl. Math. 33 (1980), no. 6, 707-725. MR 82b:65091
3.: J. D. Benamou and B. Després, A domain decomposition method for the Helmholtz equation and related optimal control problems, J. of Comp. Physics 136 (1997), 68-82. MR 98c:65162
4.: Morten Bjørhus, On domain decomposition, subdomain iteration and waveform relaxation, Ph.D. thesis, University of Trondheim, Norway, 1995.
5.: Xiao-Chuan Cai, Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math. 60 (1991), no. 1, 41-61. MR 93a:65127
6.: -, Multiplicative Schwarz methods for parabolic problems, SIAM J. Sci Comput. 15 (1994), no. 3, 587-603. MR 95c:65178
7.: 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.
8.: Philippe Charton, Frédéric Nataf, and Francois Rogier, Méthode de décomposition de domaine pour l'équation d'advection-diffusion, C. R. Acad. Sci. 313 (1991), no. 9, 623-626. MR 92j:65192
9.: 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.
10.: P. Collino, G. Delbue, P. Joly, and A. Piacentini, A new interface condition in the nonoverlapping domain decomposition for the Maxwell equations Helmholtz equation and related optimal control, Comput. Methods Appl. Mech. Engrg. 148 (1997), 195-207. MR 98f:78001
11.: Armel de La Bourdonnaye, Charbel Farhat, Antonini Macedo, Frédéric Magoulès, and François-Xavier Roux, A nonoverlapping domain decomposition method for exterior Helmholtz problems, Domain decomposition methods, 10 (Boulder, CO, 1997) (Providence, RI), Amer. Math. Soc., 1998, pp. 42-66. MR 99f:65190
12.: 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.
13.: 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.
14.: B. Engquist and L. Halpern, Long-time behaviour of absorbing boundary conditions, Math. Methods Appl. Sci. 13 (1990), no. 3, 189-203. MR 91m:35045
15.: B. Engquist and A. Majda, Absorbing boundary conditions for the numerical simulation of waves, Math. Comp. 31 (1977), no. 139, 629-651. MR 55:9555
16.: 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.
17.: -, Overlapping Schwarz waveform relaxation for parabolic problems, Tenth International Conference on Domain Decomposition Methods (J. Mandel, C. Farhat, and X.-C. Cai, eds.), AMS, Contemporary Mathematics 218, 1998. MR 99f:65005
18.: -, A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations, Numerical Linear Algebra with Applications 6 (1998), 125-145. MR 2000m:65110
19.: -, Optimized Schwarz methods for Helmholtz problems, Thirteenth international conference on domain decomposition, 2001, pp. 245-252.
20.: 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 I (2001), no. 333, 589-592. MR 2002i:65096
21.: -, Un algorithme discret de décomposition de domaines pour l'équation des ondes en dimension 1, C. R. Acad. Sci. Paris I (2001), no. 333, 699-702. MR 2002i:65097
22.: 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.
23.: 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.
24.: 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.
25.: Martin J. Gander and Andrew M. Stuart, Space time continuous analysis of waveform relaxation for the heat equation, SIAM J. 19 (1998), 2014-2031. MR 99h:65164
26.: Martin J. Gander and Hongkai Zhao, Overlapping Schwarz waveform relaxation for parabolic problems in higher dimension, Proceedings of Algoritmy 14 (A. Handlovicová, Magda Komorníkova, and Karol Mikula, eds.), Slovak Technical University, September 1997, pp. 42-51.
27.: Eldar Giladi and Herbert Keller, Space time domain decomposition for parabolic problems, Numerische Mathematik 93 (2002), no. 2, 279-313.
28.: Laurence Halpern, Absorbing boundary conditions for the discretization schemes of the one-dimensional wave equation, Mathematics of Computation 38 (1982), no. 158, 415-429. MR 83d:65245
29.: -, Artificial boundary conditions for the advection-diffusion equations, Math. Comp. 174 (1986), 425-438. MR 87e:76005
30.: Robert L. Higdon, Initial-boundary value problems for linear hyperbolic systems, SIAM Rev. 28 (1986), no. 2, 177-217. MR 88a:35138
31.: 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.
32.: Caroline Japhet, Frederic Nataf, and Francois Rogier, The optimized order 2 method. Application to convection-diffusion problems, Future Generation Computer Systems FUTURE 18 (2001).
33.: 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.
34.: Jacques-Louis Lions and Enrico Magenes, Problèmes aux limites non homogènes et applications, Travaux et recherches mathématiques, vol. 17-18, Dunod, 1968. MR 40:512 MR 40:513
35.: 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.
36.: Gérard A. Meurant, Numerical experiments with a domain decomposition method for parabolic problems on parallel computers, Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Philadelphia, PA) (Roland Glowinski, Yuri A. Kuznetsov, Gérard A. Meurant, Jacques Périaux, and Olof Widlund, eds.), SIAM, 1991. MR 92a:65023
37.: Ulla Miekkala and Olavi Nevanlinna, Convergence of dynamic iteration methods for initial value problems, SIAM J. Sci. Stat. Comput. 8 (1987), 459-482. MR 89f:65076
38.: Frédéric Nataf, Absorbing boundary conditions in block Gauss-Seidel methods for convection problems, Math. Models Methods Appl. Sci. 6 (1996), no. 4, 481-502. MR 97g:65259
39.: Frédéric Nataf and Francis Nier, Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains, Numerische Mathematik 75 (1997), no. 3, 357-77. MR 98m:65219
40.: Donald J. Newman, Rational approximation to $\vert x\vert$ , Michigan Math. J. 11 (1964), 11-14. MR 30:1344
41.: Alfio Quarteroni and Alberto Valli, Domain decomposition methods for partial differential equations, Oxford Science Publications, 1999. MR 2002i:65002
42.: 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.
43.: Loic Tourrette and Laurence Halpern (eds.), Absorbing boundaries and layers, domain decomposition methods, application to large scale computations, Novascience, 2001.
44.: Lloyd N. Trefethen and Laurence Halpern, Well-posedness of one-way wave equations and absorbing boundary conditions, Math. of Comp. 47 (1986), no. 167, 421-435. MR 88b:65148
45.: Eugene L. Wachspress, Optimum alternating-direction-implicit iteration parameters for a model problem, J. Soc. Indust. Appl. Math. 10 (1962), 339-350. MR 27:921
46.: 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.

Martin J. Gander
Affiliation: Department of Mathematics and Statistics, McGill University, Montreal, Canada

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS