Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A homographic best approximation problem with application to optimized Schwarz waveform relaxation


Authors: D. Bennequin, M. J. Gander and L. Halpern
Journal: Math. Comp. 78 (2009), 185-223
MSC (2000): Primary 65M12, 65M55, 30E10
DOI: https://doi.org/10.1090/S0025-5718-08-02145-5
Published electronically: August 4, 2008
MathSciNet review: 2448703
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present and study a homographic best approximation problem, which arises in the analysis of waveform relaxation algorithms with optimized transmission conditions. Its solution characterizes in each class of transmission conditions the one with the best performance of the associated waveform relaxation algorithm. We present the particular class of first order transmission conditions in detail and show that the new waveform relaxation algorithms are well posed and converge much faster than the classical one: the number of iterations to reach a certain accuracy can be orders of magnitudes smaller. We illustrate our analysis with numerical experiments.


References [Enhancements On Off] (What's this?)

  • 1. Daniel Bennequin, Martin J. Gander, and Laurence Halpern, Optimized Schwarz waveform relaxation methods for convection reaction diffusion problems, Tech. Report 24, Institut Galilée, Paris XIII, 2004.
  • 2. Haïm Brézis, Analyse fonctionnelle : théorie et applications, Dunod, Paris, 1983.
  • 3. Girolamo Cardano, Ars magna or the rules of algebra, 1545, MIT, 1968.
  • 4. 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 1133498 (92j:65192)
  • 5. Elliot W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York, 1966. MR 0222517 (36:5568)
  • 6. Philippe Chevalier, Méthodes numériques pour les tubes hyperfréquences. résolution par décomposition de domaine, Ph.D. thesis, Université Paris VI, 1998.
  • 7. 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.
  • 8. P. D'Anfray, L. Halpern, and J. Ryan, New trends in coupled simulations featuring domain decomposition and metacomputing, M2AN 36 (2002), no. 5, 953-970. MR 1955544
  • 9. Olivier Dubois, Optimized Schwarz methods for the advection-diffusion equation and for problems with discontinuous coefficients, Ph.D. thesis, McGill University, June 2007.
  • 10. 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.
  • 11. -, A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations, Numerical Linear Algebra with Applications 6 (1998), 125-145. MR 1695405 (2000m:65110)
  • 12. -, Optimized Schwarz methods, SIAM J. Numer. Anal. 44 (2006), no. 2, 699-731. MR 2218966 (2007d:65121)
  • 13. Martin J. Gander and Laurence Halpern, Méthodes de relaxation d'ondes pour l'équation de la chaleur en dimension 1, C.R. Acad. Sci. Paris, Série I 336 (2003), no. 6, 519-524. MR 1975090 (2004a:65124)
  • 14. -, Absorbing boundary conditions for the wave equation and parallel computing, Math. of Comp. 74 (2004), no. 249, 153-176. MR 2085406 (2005h:65158)
  • 15. -, Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems, SIAM J. Numer. Anal. 45 (2007), no. 2, 666-697. MR 2300292
  • 16. Martin J. Gander, Laurence Halpern, and Frédéric Magoulès, An optimized Schwarz method with two-sided Robin transmission conditions for the Helmholtz equation, Int. J. for Num. Meth. in Fluids 55 (2007), no. 2, 163-175. MR 2344706
  • 17. Martin J. Gander, Laurence Halpern, and Frédéric Nataf, Optimal convergence for overlapping and non-overlapping 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. MR 1827406
  • 18. Martin J. Gander, Laurence Halpern, and Frédéric Nataf, Optimal Schwarz waveform relaxation for the one dimensional wave equation, SIAM Journal of Numerical Analysis 41 (2003), no. 5, 1643-1681. MR 2035001 (2005h:65252)
  • 19. 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 (2003i:65124)
  • 20. Martin J. Gander and Christian Rohde, Overlapping Schwarz waveform relaxation for convection dominated nonlinear conservation laws, SIAM J. Sci. Comp. 27 (2005), no. 2, 415-439. MR 2202227 (2006i:35234)
  • 21. 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 (99h:65164)
  • 22. Martin J. Gander and Hongkai Zhao, Overlapping Schwarz waveform relaxation for the heat equation in n-dimensions, BIT 42 (2002), no. 4, 779-795. MR 1944537 (2003m:65170)
  • 23. Eldar Giladi and Herbert B. Keller, Space time domain decomposition for parabolic problems, Numerische Mathematik 93 (2002), no. 2, 279-313. MR 1941398 (2003j:65088)
  • 24. Ronald D. Haynes and Robert D. Russell, A Schwarz waveform moving mesh method, SIAM J. Sci. Comp. 29 (2007), no. 2, 656-673. MR 2306263
  • 25. Lars Hörmander, Linear partial differential operators, Springer, Berlin, Heidelberg, 1969.
  • 26. Caroline Japhet, Conditions aux limites artificielles et décomposition de domaine: Méthode OO2 (optimisé d'ordre 2). application à la résolution de problèmes en mécanique des fluides, Tech. Report 373, CMAP (Ecole Polytechnique), 1997.
  • 27. Caroline Japhet, Frédéric Nataf, and Francois Rogier, The optimized order 2 method. application to convection-diffusion problems, Future Generation Computer Systems FUTURE 18 (2001), no. 1, 17-30.
  • 28. Caroline Japhet, Frédéric 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 Decompositon Methods in Science and Engineering (P. Bjorstad, M. Espedal, and D. Keyes, eds.), John Wiley & Sons, 1998, pp. 382-389.
  • 29. Jacques-Louis Lions and Enrico Magenes, Problèmes aux limites non homogènes et applications, Travaux et recherches mathématiques, vol. 18, Dunod, 1968.
  • 30. Pierre-Louis Lions, On the Schwarz alternating method. I., First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Philadelphia, PA) (Roland Glowinski, Gene H. Golub, Gérard A. Meurant, and Jacques Périaux, eds.), SIAM, 1988, pp. 1-42.
  • 31. Veronique Martin, An optimized Schwarz waveform relaxation method for unsteady convection diffusion equation, Applied Numerical Mathematics 52 (2005), no. 4, 401-428. MR 2112867 (2005i:65137)
  • 32. Günter Meinardus, Approximation von Funktionen und ihre numerische Behandlung, Springer-Verlag, 1964.
  • 33. Eugène Remes, Sur le calcul effectif des polynômes d'approximation de Tchebycheff, Comptes rendus hebdomadaires des scéances de l'académie des sciences, Paris 199 (1934), 337-340.
  • 34. -, Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximations, Comptes rendus hebdomadaires des scéances de l'académie des sciences, Paris 198 (1934), 2063-2065.
  • 35. T. J. Rivlin and H. S. Shapiro, A unified approach to certain problems of approximation and minimization, J. Soc. Indust. Appl. Math 9 (1961), no. 4, 670-699. MR 0133636 (24:A3462)
  • 36. Walter Rudin, Real and complex analysis, McGraw-Hill, 1966. MR 0210528 (35:1420)
  • 37. H. A. Schwarz, Über einen Grenzübergang durch alternierendes Verfahren, Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 15 (1870), 272-286.
  • 38. Vladimir I. Smirnov and N. A. Lebedev, Functions of a complex variable, MIT Press, Cambridge, Massachusetts, 1968. MR 0229803 (37:5369)
  • 39. J. Szeftel, Absorbing boundary conditions for reaction-diffusion equations, IMA J. Appl. Math. 68 (2003), no. 2, 167-184. MR 1968310 (2004k:35219)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65M12, 65M55, 30E10

Retrieve articles in all journals with MSC (2000): 65M12, 65M55, 30E10


Additional Information

D. Bennequin
Affiliation: Institut de Mathématiques de Jussieu, Université Paris VII, Case 7012, 2 place Jussieu, 75251 Paris Cedex 05, France
Email: bennequin@math.jussieu.fr

M. J. Gander
Affiliation: Section de Mathématiques, Université de Genève, 2-4 rue du Lièvre, CP 240, CH-1211 Genève, Switzerland
Email: Martin.Gander@math.unige.ch

L. Halpern
Affiliation: LAGA,Institut Galilée, Université Paris XIII, 93430 Villetaneuse, France
Email: halpern@math.univ-paris13.fr

DOI: https://doi.org/10.1090/S0025-5718-08-02145-5
Keywords: Schwarz method, domain decomposition, waveform relaxation, best approximation
Received by editor(s): November 14, 2006
Received by editor(s) in revised form: December 1, 2007
Published electronically: August 4, 2008
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society