betaFeedback

WorksMathematics

A First Closed-Form Robin Parameter for Optimized Schwarz Waveform Relaxation as a Function of Iteration Count, Overlap, and Time Window Length

Abstract

Schwarz waveform relaxation (SWR) is a parallel-in-time iterative method for the solution of evolution problems and belongs to the class of Parallel-in-Time algorithms that have received increasing attention over the past three decades. For parabolic problems, SWR converges linearly over long time intervals and exhibits superlinear convergence on short time intervals. Since the introduction of optimized variants (OSWR) nearly three decades ago, determining the optimized Robin parameter when OSWR is applied on bounded time windows has remained an open problem. We introduce here a new analytical approach that, for the first time, yields a closed-form expression for the optimal Robin parameter in the transmission conditions for the one-dimensional heat equation with two overlapping subdomains. The resulting formula explicitly characterizes the dependence of the optimal parameter on the iteration number, the overlap size, and the length of the time window. Beyond resolving this long-standing optimization problem, our analysis provides a framework that can be extended to more general settings, including higher-dimensional problems, multiple subdomains, and higher-order transmission conditions.

Introduction

The convergence behaviour of classical and optimized Schwarz Waveform Relaxation (SWR) methods for parabolic partial differential equations (PDEs) differs markedly from that of Schwarz methods for elliptic problems [5], owing to the non-normal nature of the time derivative operator. It is known that classical SWR methods (i.e., with Dirichlet transmission conditions) converge superlinearly on bounded time intervals, but such convergence deteriorates as the time interval length TT goes to infinity; in the limit, convergence is only linear [11, 13, 12]. As the iteration progresses, the convergence curve exhibits different phases: there is an initial rapid phase, then a slowdown, and finally an acceleration to superlinear convergence [10]. Moreover, when Robin transmission conditions are used, the best Robin parameter pp that minimizes error reduction depends on the number of iterations nn one intends to take, rather than a fixed constant [4].

The classical approach to finding best parameters via Fourier analysis, see [3], is unable to capture this dependence on nn. Indeed, such an analysis does not even yield superlinear convergence estimates (but see [10] for a Kernel Fourier analysis that uses the heat kernel to restore superlinearity with the estimates). As a result, superlinear estimates typically employ kernel techniques [11, 12] or Laplace transforms [8, 14, 9]. The latter is useful when the iteration function in Laplace space admits a closed form inverse Laplace transform, or can be expressed as a convergent series of such inverse transforms. This is feasible for Dirichlet and Neumann transmission conditions, but not for Robin transmission conditions. As a result, the problem of finding nn-dependent best Robin parameters remains so far an open problem, even for the simple case of

*Department of Mathematics and Statistics, Université Laval, Quebec, Canada [email protected].

†Section de mathématiques, Université de Genève, Geneva, Switzerland [email protected].

‡Department of Mathematics and Statistics, Université Laval, Quebec, Canada [email protected]. the one-dimensional heat equation in two subdomains. Note that in the discrete-time setting, it is possible to find the best Robin parameter by numerically minimizing the norm of the appropriate iteration matrix, whose size is proportional to the number of time steps, see [2, 1].

The goal of this paper is twofold. The first goal is to introduce a theoretical tool for estimating the error of domain decomposition methods with simple Laplace transforms, even when the inverse transforms do not have closed form formulas. The tool relies on a simple relationship between the Laplace and Fourier transforms, together with the Plancherel theorem. Although the tool is easy to understand, its application is not so widespread in the domain decomposition literature; we therefore illustrate its utility by giving a new convergence analysis of the classical SWR method for two subdomains, for which we are able to recover the known superlinear estimates using only a few lines of calculations. The second goal of the paper is to use the same techniques to fully analyze the convergence of optimized SWR (OSWR), first as a function of the Robin parameter pp, and then by choosing the parameter pp to minimize this contraction estimate for a given number of iterations nn. Note that this is the first time we are able to truly optimize pp in the superlinear regime, even though the algorithm exists and has been used for three decades. In each case, we use numerical examples to illustrate the sharpness of our estimates.

Laplace transform and exponential weighting

Let Ω=R\Omega= \mathbb{R}. To explain this new technique, it suffices to focus on the one-dimensional heat equation1

∂tu−∂yyu=f,(y,t)∈Ω×(0,T)(1)\partial_t u-\partial_{yy}u=f,\qquad(y,t)\in\Omega\times(0,T) \tag*{(1)}

with source term f∈L2(0,T;L2(Ω))f\in L^2(0,T;L^2(\Omega)) and initial conditions u(⋅,0)=u0∈H1(Ω)u(\cdot,0)=u_0\in H^1(\Omega). Note the higher regularity assumed in the initial conditions, which is needed for the well-posedness of the SWR methods later. The problem (1) is well posed [6, 7] with a unique solution u∈H2,1(Ω×(0,T)):=L2(0,T;H2(Ω))∩H1(0,T;L2(Ω))u\in H^{2,1}(\Omega\times(0,T)):=L^2(0,T;H^2(\Omega))\cap H^1(0,T;L^2(\Omega)).

Next, we consider a decomposition of Ω\Omega into two spatial subdomains Ω1=(−∞,δ)\Omega_1=(-\infty,\delta), Ω2=(0,∞)\Omega_2=(0,\infty) with an overlap of width δ>0\delta>0. The alternating (O)SWR method solves, for n=1,2,3,…n=1,2,3,\ldots,

∂tu1n−∂yyu1n=fin Ω1×(0,T),∂tu2n−∂yyu2n=fin Ω2×(0,T),u1n(⋅,0)=u0in Ω1,u2n(⋅,0)=u0in Ω2,B1u1n(δ,⋅)=B1u2n−1(δ,⋅)on (0,T),B2u2n(0,⋅)=B2u1n(0,⋅)on (0,T).\begin{aligned} \partial_t u_1^n-\partial_{yy}u_1^n&=f &&\text{in }\Omega_1\times(0,T),& \partial_t u_2^n-\partial_{yy}u_2^n&=f &&\text{in }\Omega_2\times(0,T),\\ u_1^n(\cdot,0)&=u_0 &&\text{in }\Omega_1,& u_2^n(\cdot,0)&=u_0 &&\text{in }\Omega_2,\\ B_1u_1^n(\delta,\cdot)&=B_1u_2^{n-1}(\delta,\cdot) &&\text{on }(0,T),& B_2u_2^n(0,\cdot)&=B_2u_1^n(0,\cdot) &&\text{on }(0,T). \end{aligned}

where the transmission conditions can be

  • classical (Dirichlet) conditions: Bi=idB_i=\mathrm{id}, i.e., the identity operator;

  • optimized (Robin) conditions: Bi=∂ni+pB_i=\partial_{n_i}+p, where p>0p>0 is a constant and ∂ni\partial_{n_i} is the normal derivative, with nin_i being the normal vector pointing outward from Ωi\Omega_i. In other words, we have B1=∂y+pB_1=\partial_y+p and B2=−∂y+pB_2=-\partial_y+p.

For classical SWR, the iteration is well posed if f∈L2(0,T;L2(Ω))f\in L^2(0,T;L^2(\Omega)), u0∣Ωi∈H1(Ωi)u_0|_{\Omega_i}\in H^1(\Omega_i), and if the initial guess u10(δ,⋅)u_1^0(\delta,\cdot) is in H3/4(0,T)H^{3/4}(0,T) and compatible with u0u_0 at t=0t=0. The iterates uinu_i^n then converge to u∣Ωiu|_{\Omega_i} in H2,1(Ωi×(0,T))H^{2,1}(\Omega_i\times(0,T)) as n→∞n\to\infty. For OSWR with p>0p>0, the algorithm is well-posed if f∈L2(0,T;L2(Ω))f\in L^2(0,T;L^2(\Omega)), u0∣Ωi∈H1(Ωi)u_0|_{\Omega_i}\in H^1(\Omega_i) and if the initial Robin trace B1u10(δ,⋅)B_1u_1^0(\delta,\cdot) is in H1/4(0,T)H^{1/4}(0,T); in that case, the iterates uinu_i^n all lie in H2,1(Ωi×(0,T))H^{2,1}(\Omega_i\times(0,T)) and converge to u∣Ωiu|_{\Omega_i} as n→∞n\to\infty. See [6, 7] for the proof of these results.

Since the problem (1) is linear, it suffices to analyze the convergence of the local errors Ein=uin−u∣ΩiE_i^n=u_i^n-u|_{\Omega_i} to zero. The error equations satisfied by EinE_i^n have the same form as the original problem, but with zero initial conditions and source term:

References

  1. [1]Arthur Arnoult. Méthode de décomposition de domaine espace–temps et parallèle en temps pour les écoulements incompressibles et nouvelle analyse de la méthode de relaxation d’onde de Schwarz optimisée. PhD thesis, Université Paris-Nord-Paris XIII, 2025.DOI
  2. [2]Arthur Arnoult, Caroline Japhet, and Pascal Omnes. Discrete-time analysis of optimized Schwarz waveform relaxation with Robin parameters depending on the targeted iteration count. ESAIM: Mathematical Modelling and Numerical Analysis, 57(4):2371–2396, 2023.DOI
  3. [3]Daniel Bennequin, Martin J. Gander, and Laurence Halpern. A homographic best approximation problem with application to optimized Schwarz waveform relaxation. Mathematics of Computation, 78(265):185–223, 2009.DOI
  4. [4]Yves Courvoisier and Martin J. Gander. Optimization of Schwarz waveform relaxation over short time windows. Numerical Algorithms, 64(2):221–243, 2013.DOI
  5. [5]Martin J. Gander. Optimized Schwarz methods. SIAM Journal on Numerical Analysis, 44(2):699–731, 2006.DOI
  6. [6]Martin J. Gander and Laurence Halpern. Méthode de relaxation d’ondes (SWR) pour l’équation de la chaleur en dimension 1. C.R. Acad. Sci. Paris Ser. I, Math., 336(6):519–524, 2003.DOI
  7. [7]Martin J. Gander and Laurence Halpern. Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems. SIAM Journal on Numerical Analysis, 45(2):666–697, 2007.DOI
  8. [8]Martin J. Gander, Felix Kwok, and Bankim C. Mandal. Dirichlet-Neumann and Neumann-Neumann waveform relaxation algorithms for parabolic problems. Electronic Transactions on Numerical Analysis, 45:424–456, 2016.
  9. [9]Martin J. Gander, Felix Kwok, and Bankim C. Mandal. Dirichlet-Neumann waveform relaxation methods for parabolic and hyperbolic problems in multiple subdomains. BIT Numerical Mathematics, 61(1):173–207, 2021.DOI
  10. [10]Martin J. Gander and Véronique Martin. Why Fourier mode analysis in time is different when studying Schwarz waveform relaxation. Journal of Computational Physics, 491:112316, 2023.DOI
  11. [11]Martin J. Gander and Andrew M. Stuart. Space-time continuous analysis of waveform relaxation for the heat equation. SIAM Journal on Scientific Computing, 19(6):2014–2031, 1998.DOI
  12. [12]Martin J. Gander and Hongkai Zhao. Overlapping Schwarz waveform relaxation for the heat equation in n-dimensions. BIT Numerical Mathematics, 42(4):779–795, 2002.DOI
  13. [13]Eldar Giladi and Herbert B. Keller. Space-time domain decomposition for parabolic problems. Numerische Mathematik, 93(2):279–313, 2002.DOI
  14. [14]Bankim C. Mandal. Neumann–Neumann waveform relaxation algorithm in multiple subdomains for hyperbolic problems in 1D and 2D. Numerical Methods for Partial Differential Equations, 33(2):514–530, 2017.arxiv.org/abs/1507.04008

Paper details

vlnc:W_qsmup45k
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents