Skip to main content
Log in

Optimized Schwarz waveform relaxation for advection reaction diffusion equations in two dimensions

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

Optimized Schwarz waveform relaxation methods have been developed over the last decade for the parallel solution of evolution problems. They are based on a decomposition in space and an iteration, where only subproblems in space-time need to be solved. Each subproblem can be simulated using an adapted numerical method, for example with local time stepping, or one can even use a different model in different subdomains, which makes these methods very suitable also from a modeling point of view. For rapid convergence however, it is important to use effective transmission conditions between the space-time subdomains, and for best performance, these transmission conditions need to take the physics of the underlying evolution problem into account. The optimization of these transmission conditions leads to mathematically hard best approximation problems of homographic functions. We study in this paper in detail the best approximation problem for the case of linear advection reaction diffusion equations in two spatial dimensions. We prove comprehensively best approximation results for transmission conditions of Robin and Ventcel (higher order) type, which can also be used in the various limits for example for the heat equation, since we include in our analysis a positive low frequency limiter both in space and time. We give for each case closed form asymptotic values for the parameters which can directly be used in implementations of these algorithms, and which guarantee asymptotically best performance of the iterative methods. We finally show extensive numerical experiments, including cases not covered by our analysis, for example decompositions with cross points. We use Q1 finite element discretizations in space and Forward and Backward Euler discretizations in time (other discretization could also have been considered, since all our analysis is at the continuous level), and in all cases, we measure performance corresponding to our analysis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. At the continuous level the transmission operator on the left and right is indeed the same, but the discretization leads in general to a small difference, see for example [10].

References

  1. Audusse, E., Dreyfuss, P., Merlet, B.: Optimized Schwarz waveform relaxation for the primitive equations of the ocean. SIAM J. Sci. Comput. 32(5), 2908–2936 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bai, Z.-Z., Yang, Xi: On convergence conditions of waveform relaxation methods for linear differential-algebraic equations. J. Comput. Appl. Math. 235(8), 2790–2804 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bennequin, D., Gander, M.J., Halpern, L.: A homographic best approximation problem with application to optimized Schwarz waveform relaxation. Math. Comput. 78(265), 185–232 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bjørhus, M.: On domain decomposition, subdomain iteration and waveform relaxation. PhD thesis, University of Trondheim (1995)

  5. Caetano, F., Halpern, L., Gander, M., Szeftel, J.: Schwarz waveform relaxation algorithms for semilinear reaction-diffusion. Netw. Heterog. Media 5(3), 487–505 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. D’Anfray, P., Halpern, L., Ryan, J.: New trends in coupled simulations featuring domain decomposition and metacomputing. M2AN. 36(5), 953–970 (2002)

  7. Daoud, D.S.: Overlapping Schwarz waveform relaxation method for the solution of the forward-backward heat equation. J. Comput. Appl. Math. 208(2), 380–390 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Daoud, D.S.: Overlapping schwarz waveform relaxation method for the solution of the convectiondiffusion equation. Math. Methods Appl. Sci. 31(9), 1099–1111 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gander, M.J., Halpern, L.: Absorbing boundary conditions for the wave equation and parallel computing. Math. Comput. 74(249), 153–176 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  10. Gander, M.J., Halpern, L., Nataf, F.: Optimal Schwarz waveform relaxation for the one dimensional wave equation. SIAM J. Numer. Anal. 41(5), 1643–1681 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gander, M.J.: Optimized Schwarz methods. SIAM J. Numer. Anal. 44(2), 699–731 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gander, M.J.: Schwarz methods over the course of time. ETNA 31, 228–255 (2008)

    MathSciNet  MATH  Google Scholar 

  13. Gander, M.J.: On the influence of geometry on Schwarz methods. Bol. Soc. Esp. Mat. Apl., Num. 53, 71–78 (2011)

  14. Gander, M.J., Al-Khaleel, M, Ruchli, A.E.: Optimized waveform relaxation methods for longitudinal partitioning of transmission lines. IEEE Trans. Circuits Syst. I. Regul. Pap. 56(8), 1732–1743 (2009)

  15. Gander, M.J., Halpern, L.: Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems. SIAM J. Numer. Anal. 45(2), 666–697 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gander, M.J., Halpern, L, Nataf, F.: Optimal convergence for overlapping and non-overlapping Schwarz waveform relaxation. In: Lai, C-H., Bjørstad, P., Cross, M., Widlund, O. (eds.) Eleventh international Conference of Domain Decomposition Methods. http://ddm.org (1999)

  17. Gander, M.J., Haynes, R.D.: Domain decomposition approaches for mesh generation via the equidistribution principle. SIAM J. Numer. Anal. 50(4), 2111–2135 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gander, M.J., Rohde, C.: Overlapping Schwarz waveform relaxation for convection dominated nonlinear conservation laws. SIAM J. Sci. Comput. 27(2), 415–439 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gander, M.J., Ruehli, A.E.: Optimized waveform relaxation methods for \(RC\) type circuits. IEEE Trans. Circuits Syst. I Regul. Pap. 51(4), 755–768 (2004)

  20. Gander, M.J., Stuart, A.M.: Space time continuous analysis of waveform relaxation for the heat equation. SIAM J. 19, 2014–2031 (1998)

    MathSciNet  MATH  Google Scholar 

  21. Gander, M.J., Zhao, H.: Overlapping Schwarz waveform relaxation for the heat equation in n-dimensions. BIT 42(4), 779–795 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  22. Garbey, M.: Acceleration of a Schwarz waveform relaxation method for parabolic problems. Int. J. Math. Model. Numer. Optim. 1(3), 185–212 (2010)

  23. Gerardo-Giorda, L.: Balancing waveform relaxation for age-structured populations in a multilayer environment. J. Numer. Math. 16(4), 281–306 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Giladi, E., Keller, H.B.: Space time domain decomposition for parabolic problems. Numerische Mathematik 93(2), 279–313 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Halpern, L.: Optimized Schwarz waveform relaxation: roots, blossoms and fruits. In: Domain decomposition methods in science and engineering XVIII, Lect. Notes Comput. Sci. Eng., vol. 70, pp. 225–232. Springer (2009)

  26. Haynes, R.D., Huang, W., Russell, R.D.: A moving mesh method for time-dependent problems based on Schwarz waveform relaxation. In: Domain decomposition methods in science and engineering XVII, Lect. Notes Comput. Sci. Eng., vol. 60, pp. 229–236. Springer (2008)

  27. Haynes, R.D., Russell, R.D.: A Schwarz waveform moving mesh method. SIAM J. Sci. Comput. 29(2), 656–673 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  28. Janssen, J., Vandewalle, S.: Multigrid waveform relaxation on spatial finite element meshes: the continuous-time case. SIAM J. Numer. Anal. 33(2), 456–474 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  29. Janssen, J., Vandewalle, S.: Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case. SIAM J. Sci. Comput. 17(1), 133–155 (1996). Special issue on iterative methods in numerical linear algebra (Breckenridge, CO, 1994)

  30. Jiang, Y.-L., Ding, X.-L.: Waveform relaxation methods for fractional differential equations with the Caputo derivatives. J. Comput. Appl. Math. 238, 51–67 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  31. Jiang, Y.-L., Zhang, H.: Schwarz waveform relaxation methods for parabolic equations in space-frequency domain. Comput. Math. Appl. 55(12), 2924–2933 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  32. Lelarasmee, E., Ruehli, A.E., Sangiovanni-Vincentelli, A.L.: The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE Trans. CAD IC Syst. 1, 131–145 (1982)

  33. Liu, J., Jiang, Y.-L.: Waveform relaxation for reaction-diffusion equations. J. Comput. Appl. Math. 235(17), 5040–5055 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  34. Liu, J., Jiang, Y.-L.: A parareal waveform relaxation algorithm for semi-linear parabolic partial differential equations. J. Comput. Appl. Math. 236(17), 4245–4263 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  35. Ltaief, H., Garbey, M.: A parallel Aitken-additive Schwarz waveform relaxation suitable for the grid. Parallel Comput. 35(7), 416–428 (2009)

    Article  MathSciNet  Google Scholar 

  36. Martin, V.: An optimized Schwarz waveform relaxation method for unsteady convection diffusion equation. Appl. Numer. Math. 52(4), 401–428 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  37. Halpern, L., Gander, M.J., Gouarin, L.: Optimized schwarz waveform relaxation methods: a large scale numerical study. In: Domain decomposition methods in science and engineering XIX, Lecture notes in computational science and engineering, pp. 261–268. Springer-Verlag (2010)

  38. Quarteroni, A., Valli, A.: Domain decomposition methods for partial differential equations. Oxford Science Publications (1999)

  39. Schwarz, H.A.: Über einen Grenzübergang durch alternierendes Verfahren. Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 15, 272–286 (1870)

    Google Scholar 

  40. Smith, B.F., Bjørstad, P.E., Gropp, W.: Domain decomposition: parallel multilevel methods for elliptic partial differential equations. Cambridge University Press (1996)

  41. Toselli, A., Widlund, O.: Domain decomposition methods—algorithms and theory, Springer series in computational mathematics, vol. 34. Springer (2004)

  42. Tran, M.B.: Schwarz waveform relaxation methods. PhD thesis, LAGA, Paris 13, 2011. http://hal.archives-ouvertes.fr/hal-00589252

  43. van Lent, J., Vandewalle, S.: Multigrid waveform relaxation for anisotropic partial differential equations. Numer. Algorithms 31(1-4), 361–380 (2002, Numerical methods for ordinary differential equations (Auckland, 2001))

  44. Ventcel, A.D.: On boundary conditions for multidimensional diffusion processes. Theory Probab. Appl. 4, 164–177 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  45. Shu-Lin, W., Huang, C.-M., Huang, T.-Z.: Convergence analysis of the overlapping Schwarz waveform relaxation algorithm for reaction-diffusion equations with time delay. IMA J. Numer. Anal. 32(2), 632 (2011)

    MathSciNet  MATH  Google Scholar 

  46. Zhang, H., Jiang, Y.-L.: Schwarz waveform relaxation methods for parabolic time periodic problems. Sci. China (Mathematics)(Chinese edition) 40, 497–516 (2010)

  47. Zhao, Y., Li, L.: On the convergence of continuous-time waveform relaxation methods for singular perturbation initial value problems. J. Appl. Math. Art. ID 241984, p. 11 (2012)

  48. Zubik-Kowal, B., Vandewalle, S.: Waveform relaxation for functional-differential equations. SIAM J. Sci. Comput. 21(1), 207–226 (1999, electronic)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Laurence Halpern.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bennequin, D., Gander, M.J., Gouarin, L. et al. Optimized Schwarz waveform relaxation for advection reaction diffusion equations in two dimensions. Numer. Math. 134, 513–567 (2016). https://doi.org/10.1007/s00211-015-0784-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-015-0784-8

Keywords

Mathematics Subject Classification

Navigation