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
Published electronically: August 4, 2008
MathSciNet review: 2448703
Full-text PDF Free Access

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 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
  • 5. E. W. Cheney, Introduction to approximation theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0222517
  • 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. Philippe D’Anfray, Laurence Halpern, and Juliette Ryan, New trends in coupled simulations featuring domain decomposition and metacomputing, M2AN Math. Model. Numer. Anal. 36 (2002), no. 5, 953–970. Programming. MR 1955544, 10.1051/m2an:2002043
  • 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. 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, 10.1002/(SICI)1099-1506(199903)6:2<125::AID-NLA152>3.0.CO;2-4
  • 12. Martin J. Gander, Optimized Schwarz methods, SIAM J. Numer. Anal. 44 (2006), no. 2, 699–731 (electronic). MR 2218966, 10.1137/S0036142903425409
  • 13. Martin J. Gander and Laurence Halpern, Méthodes de relaxation d’ondes (SWR) pour l’équation de la chaleur en dimension 1, C. R. Math. Acad. Sci. Paris 336 (2003), no. 6, 519–524 (French, with English and French summaries). MR 1975090, 10.1016/S1631-073X(03)00009-8
  • 14. Martin J. Gander and Laurence Halpern, Absorbing boundary conditions for the wave equation and parallel computing, Math. Comp. 74 (2005), no. 249, 153–176. MR 2085406, 10.1090/S0025-5718-04-01635-7
  • 15. M. J. Gander and L. Halpern, Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems, SIAM J. Numer. Anal. 45 (2007), no. 2, 666–697 (electronic). MR 2300292, 10.1137/050642137
  • 16. M. J. Gander, L. Halpern, and F. Magoulès, An optimized Schwarz method with two-sided Robin transmission conditions for the Helmholtz equation, Internat. J. Numer. Methods Fluids 55 (2007), no. 2, 163–175. MR 2344706, 10.1002/fld.1433
  • 17. M. J. Gander, L. Halpern, and F. Nataf, Optimal convergence for overlapping and non-overlapping Schwarz waveform relaxation, Eleventh International Conference on Domain Decomposition Methods (London, 1998) DDM.org, Augsburg, 1999, pp. 27–36 (electronic). MR 1827406
  • 18. Martin J. Gander, Laurence Halpern, and Frédéric Nataf, Optimal Schwarz waveform relaxation for the one dimensional wave equation, SIAM J. Numer. Anal. 41 (2003), no. 5, 1643–1681. MR 2035001, 10.1137/S003614290139559X
  • 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 (electronic). MR 1924414, 10.1137/S1064827501387012
  • 20. Martin J. Gander and Christian Rohde, Overlapping Schwarz waveform relaxation for convection-dominated nonlinear conservation laws, SIAM J. Sci. Comput. 27 (2005), no. 2, 415–439. MR 2202227, 10.1137/030601090
  • 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, 10.1137/S1064827596305337
  • 22. Martin J. Gander and Hongkai Zhao, Overlapping Schwarz waveform relaxation for the heat equation in 𝑛 dimensions, BIT 42 (2002), no. 4, 779–795. MR 1944537, 10.1023/A:1021900403785
  • 23. Eldar Giladi and Herbert B. Keller, Space-time domain decomposition for parabolic problems, Numer. Math. 93 (2002), no. 2, 279–313. MR 1941398, 10.1007/s002110100345
  • 24. Ronald D. Haynes and Robert D. Russell, A Schwarz waveform moving mesh method, SIAM J. Sci. Comput. 29 (2007), no. 2, 656–673. MR 2306263, 10.1137/050631549
  • 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. Véronique Martin, An optimized Schwarz waveform relaxation method for the unsteady convection diffusion equation in two dimensions, Appl. Numer. Math. 52 (2005), no. 4, 401–428. MR 2112867, 10.1016/j.apnum.2004.08.022
  • 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), 670–699. MR 0133636
  • 36. Walter Rudin, Real and complex analysis, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0210528
  • 37. H. A. Schwarz, Über einen Grenzübergang durch alternierendes Verfahren, Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 15 (1870), 272-286.
  • 38. V. I. Smirnov and N. A. Lebedev, Functions of a complex variable: Constructive theory, Translated from the Russian by Scripta Technica Ltd, The M.I.T. Press, Cambridge, Mass., 1968. MR 0229803
  • 39. Jérémie Szeftel, Absorbing boundary conditions for reaction-diffusion equations, IMA J. Appl. Math. 68 (2003), no. 2, 167–184. MR 1968310, 10.1093/imamat/68.2.167

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