PaperlayerView exact revision on arXiv

Source-linked AI summary

Two-level hybrid Schwarz preconditioners with preasymptotic piecewise-polynomial coarse spaces for the high-frequency Helmholtz equation

Jeffrey Galkowski, Euan A. Spence, Pierre-Henri Tournier

arXiv:2610.11774v1math.NAcs.NA

TL;DR

Existing k-explicit theory for two-level Schwarz preconditioners considers only asymptotic coarse spaces. This paper analyzes piecewise-polynomial coarse spaces in the preasymptotic regime and proves logarithmic-in-k convergence under a mesh threshold. The stated theory assumes smooth coefficients and scatterer boundaries.

  • Problem

    Existing k-explicit convergence theory for two-level Schwarz methods requires coarse spaces whose Galerkin solutions are k-uniformly quasi-optimal.

    Source: §1 · p. 1, §2.6 · p. 8

  • Method

    The paper analyzes hybrid Schwarz preconditioners with piecewise-polynomial fine and coarse spaces in the preasymptotic regime under the threshold (H_c k)^(2p)ρ(k) ≪ 1.

    Source: §1 · p. 1

  • Results

    With (H_c k)^(2p)ρ(k) ≪ 1 and h not superalgebraically small in k, the fixed-point method, weighted GMRES, and unweighted GMRES converge in no more than ∼log k iterations.

    Source: §2.7 · p. 10

  • Takeaways & Limitations

    Theorem 2.7 establishes convergence results for two-level domain decomposition without requiring the coarse space to be in the asymptotic regime.

    Source: §2.6 · p. 8

    The theorem assumes smooth coefficients and scatterer boundaries; relaxing this to C^p-type regularity would require a stronger polynomial-growth assumption on ρ(k).

    Source: §2.7 · p. 10

Abstract

from arXiv · show

We consider two-level hybrid Schwarz domain-decomposition preconditioners for finite element discretizations of the high-frequency Helmholtz equation (with wavenumber $k$). To date, all existing $k$-explicit theory for these preconditioners considers coarse spaces in the $\textit{asymptotic regime}$, i.e., where the Galerkin solution is $k$-uniformly quasi-optimal. We consider the situation where the fine and coarse spaces consist, respectively, of piecewise polynomials of degree $p$ on meshes of width $h$ and $H_c$. We prove results for the coarse space in the $\textit{preasymptotic regime}$, under the familiar mesh threshold that $(H_c k)^{2p} \rho(k)$ is sufficiently small, where $\rho(k)$ is the norm of the solution operator (such that $\rho(k)\sim k$ for the Helmholtz equation in free space). We prove that, in this regime, the fixed-point iteration with this preconditioner converges in a number of iterations that grows at most like $\log k$. We give numerical experiments demonstrating this theory. Furthermore, these experiments indicate that our theoretical results are sharp, in that the number of iterations required for these preconditioners to converge with $(H_c k)^{2p} \rho(k) \gg 1$ grows rapidly with $k$.

1 Context and informal statement of the main result

Existing k-explicit theory for two-level Schwarz methods assumes an asymptotic coarse space, while this paper analyzes piecewise-polynomial coarse spaces in the preasymptotic regime. Under the stated mesh and problem conditions, the preconditioned fixed-point method converges in at most about log k iterations.

1 Context and informal statement of the main result

  • Earlier k-explicit analyses of two-level Schwarz methods require asymptotic coarse spaces with k-uniform quasi-optimality.The paper identifies six recent studies with sufficient conditions for k-independent iteration counts for the fixed-point method or GMRES.Source: §1 · p. 1
  • The analysis covers piecewise-polynomial coarse spaces in the preasymptotic regime, where relative error is k-uniformly bounded but quasi-optimality is not required.The stated mesh threshold is (H_c k)^(2p)ρ(k) ≪ 1; ρ(k) is the solution-operator norm and scales like k in free space.Source: §1 · p. 1
  • The preconditioned fixed-point method converges in ≲log k iterations under the theorem’s assumptions.The problem considered is Helmholtz scattering outside a smooth bounded Dirichlet or Neumann obstacle, with an absorbing layer approximating the radiation condition.Source: §1 · p. 2
  • When (H_c k)^(2p)ρ(k) ≫ 1, experiments indicate that GMRES iterations grow quickly with k, even when h is very small.The paper explains the threshold by the need for the coarse space to resolve propagation at length scales independent of k; one-level methods with subdomains of size k^-1 require at least ∼k iterations for that resolution.Source: §1 · p. 2

2 Statement of the main result

The paper sets up a truncated Helmholtz scattering problem with an absorbing layer, then specifies the global, coarse, fine, and subdomain components used in its hybrid Schwarz framework. The subdomain problems agree with the global problem in designated regions and include absorption in designated layers.

2.1 Helmholtz problems

  • The scattering model is truncated to a bounded computational domain, where an absorbing layer approximates the radiation condition.The underlying scattering problem includes an obstacle and conditions on its boundary; the truncated problem imposes a boundary condition on the truncation boundary.Source: §2.1 · p. 2

2.2 Components of the two-level hybrid Schwarz preconditioner

  • The hybrid Schwarz setup includes the global Helmholtz problem, subdomain problems with absorbing layers and agreement regions, and nested coarse and fine spaces.The geometric setup is illustrated with subdomains Ω_j, their absorbing layers U_j, and regions W_j where they agree with the global problem.Source: §2.2 · p. 4, Figure 2.1 · p. 4

2.3 The subdomain problems

  • Each subdomain problem is defined with a region W_ℓ of agreement with the global problem and an absorbing region U_ℓ.When a subdomain touches the scatterer boundary or Γ_p, the stated conditions require CAP rather than PML absorption at the boundary of the absorbing layer.Source: §2.3 · p. 5

2.4 The finite-element space

The finite-element space uses mapped piecewise polynomials on curved elements. The preconditioner is described through embeddings of the finite-element spaces and matrix representations of the global and subdomain forms.

2.4 The finite-element space

  • The finite-element spaces consist of mapped degree-p polynomials on triangulations with element maps.The meshes use curved elements.Source: §2.4 · p. 6

2.5 Definition of the two-level hybrid Schwarz preconditioner

  • The preconditioner setup uses inclusion maps for the fine, coarse, and subdomain spaces, with interpolation and adjoint maps also specified.The adjoints of the inclusion maps are identified with the corresponding L2 orthogonal projectors.Source: §2.5 · pp. 6–7
  • At matrix level, the global and subdomain matrices are defined by evaluating their respective sesquilinear forms on basis functions.The setup also defines an overlap number based on the maximum number of domains intersecting a ball of radius R/k around a subdomain.Source: §2.5 · p. 7

2.6 The main result

Theorem 2.7 establishes convergence for two-level hybrid Schwarz methods with preasymptotic piecewise-polynomial coarse spaces, under mesh, subdomain, and problem assumptions. In this regime, iteration counts grow at most logarithmically with k; experiments indicate rapid growth beyond the coarse-mesh threshold.

2.7 Discussion of Theorem 2.7

  • The stated mesh condition includes (Hc k)^{2p}ρ(k) + Hc k ≤ c; the discussion also requires ρ(Hc k)^{2p} ≪ 1, h ≪ Hc, and (hℓk)^p(kδℓ) ≪ 1.When kδℓ ∼ 1, the last subdomain-mesh requirement is automatic.Source: §2.6 · p. 8, §2.7 · p. 10

2.6 The main result

  • Theorem 2.7 is presented as the first two-level domain-decomposition convergence result that does not require a k-uniformly quasi-optimal coarse-space Galerkin solution.It treats piecewise-polynomial spaces in the preasymptotic regime.Source: §2.6 · p. 8

2.7 Discussion of Theorem 2.7

  • Subdomains have diameter ∼δℓ and absorbing-layer width at least cδℓ, with minimum diameter ∼k^-1 and generous overlap.For diameters at most c k^-1, the subdomain solution-operator norm satisfies ρℓ ≤ 1.Source: §2.7 · p. 9
  • For non-trapping subdomain problems, ρℓ is bounded by Ckδℓ; with ρ ≥ ck, the discussion derives the conditions needed to make ϵ small.The discussion also treats middle-sized subdomains, where finitely many eigenvalues can obstruct uniform bounds; with CAP absorption and sufficiently large k, it states that no such eigenvalues occur and ρℓ is bounded.Source: §2.7 · pp. 9–10
  • Experiments indicate that when (Hc k)^{2p}ρ(k) ≫ 1, fixed-point and GMRES iteration counts are not uniformly bounded in k and grow rapidly, even for very small h.The paper describes this as evidence that the sufficient coarse-mesh threshold is optimal.Source: §2.7 · p. 10
  • At most ~log k iterations suffice for the fixed-point method and weighted or unweighted GMRES when (Hc k)^{2p}ρ is sufficiently small and h is not superalgebraically small in k.The theorem discussion also recovers k-independent convergence when (Hc k)^pρ is bounded.Source: §2.7 · p. 10
  • The theorem assumes a smooth global truncation boundary and a specified absorption condition, excluding Cartesian PML truncations from its stated scope.Covering Cartesian PMLs would require repeating the preasymptotic h-FEM error analysis while accounting for improved solution-operator behavior in the PML region.Source: §2.7 · p. 10
  • The theorem assumes smooth coefficients and scatterer boundaries; relaxing to Cp-type regularity would require strengthening the polynomial-growth assumption on ρ(k).The discussion specifies that the allowed polynomial growth would then be fixed and p-dependent.Source: §2.7 · p. 10

2.8 Discussion of the ideas of the proof

The proof combines coarse and subdomain solves by assigning them complementary roles across frequency ranges. It controls coarse-space error under the preasymptotic mesh condition and uses localization and subdomain estimates to handle the remaining error.

2.8 Discussion of the ideas of the proof

  • The proof combines coarse and local solves because frequencies much larger than k do not propagate under the Helmholtz solution operator and can be approximated by sums of local solves.The coarse solve controls errors after coarse-space approximation, and the subdomain solve corrects the remaining errors.Source: §2.8 · pp. 11–12
  • The coarse solve removes low-frequency components when (Hc k)^{2p}ρ is sufficiently small, while high-frequency errors are not well approximated by the coarse space.The discussion uses a frequency-k operator Ψ to distinguish low and high components.Source: §2.8 · p. 11
  • Under the mesh condition, the coarse solve has bounded relative error in the X norm, and the coarse-space correction is the identity on the coarse space.The cited argument uses the orthogonal decomposition on VHc.Source: §2.8 · p. 12
  • The subdomain analysis uses cutoff localization, smoothing and orthogonality properties, then estimates the difference between continuous and discrete subdomain Galerkin solutions using local quasi-optimality and preasymptotic Galerkin estimates.The forcing near subdomain boundaries is small because the coarse correction is orthogonal to the coarse space.Source: §2.8 · pp. 12–13

3 Numerical experiments

The experiments test degree-2 and degree-4 polynomial spaces in free space and around a trapping obstacle, including settings covered and not covered by Theorem 2.7. Covered settings show convergence uniformly in k, while experiments outside the theorem’s conditions show iteration counts increasing with k.

3 Numerical experiments

  • The experiments use degree-2 and degree-4 polynomials, subdomains of size approximately k^-1, and compare free-space and trapping-obstacle settings.The numerical setup uses the FreeFEM implementation and includes piecewise-linear partition-of-unity functions and a nonsmooth absorbing profile.Source: §3 · p. 13, §3.1 · pp. 13–14

3.2 Experiments in free space.

  • For p = 2 in free space, both methods converge in a k-uniform number of iterations in Point A, while iteration counts increase with k in the other three experiments.The experiments use ρ = k in free space.Source: §3.2 · p. 14, Figure 3.1 · p. 14, Figure 3.2 · p. 15
  • For p = 4 in free space, the Point A experiment converges uniformly in k, while the other two experiments show iteration counts increasing with k.The reported experiments use Points A, B.1, B.2, and B.3; the passage describes increasing counts in the other two experiments.Source: §3.2 · p. 16, Figure 3.5 · p. 16, Figure 3.6 · p. 16

3.3 Experiments in the exterior of a trapping obstacle

  • For p = 2 around a trapping obstacle, the Point A experiment converges uniformly in k, while iteration counts increase with k in the other experiments.The reported p = 2 cases cover Point A and Point B.1.Source: §3.3 · p. 17, Figure 3.10 · p. 18, Figure 3.11 · p. 18
  • For p = 4 around a trapping obstacle, the Point A experiment converges uniformly in k, while the other two experiments show iteration counts increasing with k.The reported p = 4 cases cover Points A, B.2, and B.3.Source: §3.3 · p. 17, Figure 3.12 · p. 19, Figure 3.13 · p. 19

4 Functional-analytic set up

This section sets up Hilbert-space scales for describing operator mappings and introduces a self-adjoint operator generated by a symmetrized form. It also gives an interpretation of the spaces in relation to boundary conditions.

4 Functional-analytic set up

  • The operator P is self-adjoint and is generated by a quadratic form built from the sesquilinear form a.The passage introduces P to state mapping properties of P and its adjoint.Source: §4 · p. 20
  • The Hilbert scales set H0 = Z0 = L2(Ω), define positive-index spaces, and define negative-index spaces as duals.The construction is given for Hn and Zn.Source: §4 · p. 20
  • The spaces Wn and Yn can be viewed as spaces with and without boundary conditions, respectively, and applying P removes boundary conditions.Source: §4 · p. 20

5 Preasymptotic analysis of coarse problem

The coarse-problem analysis establishes operator and finite-element bounds under the preasymptotic assumptions. Its proof combines FEM error estimates, smoothing, and a duality argument.

5 Preasymptotic analysis of coarse problem

  • The analysis establishes existence, uniqueness, and a bound for the coarse-space map Hc: Vh → VHc.The supplied passage states the result but does not include the bound’s expression.Source: §5 · p. 20
  • The proof obtains a low-frequency FEM error bound using prior estimates and combines it with a smoothing bound.The passage identifies the resulting estimate as (5.3).Source: §5 · p. 21
  • A modified argument uses a projection, Galerkin orthogonality, smoothing, coercivity, and Aubin–Nitsche-type duality to establish the remaining bound.The argument is identified with bounds (5.4) and (5.10).Source: §5 · pp. 21–22

6 FEM analysis of the subdomain problems

The subdomain analysis develops solution-operator bounds in absorbing and high-frequency settings, then uses them in a quasi-optimality result for the subdomain FEM solution.

6 FEM analysis of the subdomain problems

  • The section establishes solution-operator bounds for subdomain problems in the absorbing region and at high frequency.Source: §6 · pp. 22–23
  • The proof localizes the subdomain analysis using interior, absorbing-region, and exterior cutoffs with specified support conditions.The cutoff argument combines operator mapping properties and localization estimates.Source: §6 · pp. 24–25
  • Lemma 6.3 establishes quasi-optimality of the FEM solution for the subdomain problems under a stated condition on s.Its proof follows a Schatz duality argument combining Aubin–Nitsche duality and a Gårding inequality.Source: §6 · pp. 25–26

7 Superapproximation and subdomain overlaps

This section develops a superapproximation result for functions close to finite element functions and tools for handling overlapping subdomains. Its analysis also uses enlarged cutoffs and approximate orthogonality properties.

7 Superapproximation and subdomain overlaps

  • A new lemma shows that functions that are k-close to finite element functions still satisfy a type of superapproximation.Lemma 7.1 gives the result for finite element functions and a further particular bound.Source: §7 · p. 26

7.1 Cutoff functions associated to the overlapping subdomains

  • Only χℓ enters the preconditioner; the larger cutoffs, whose transition lies in the absorbing region, are used only for analysis.The larger cutoffs are supported in the overlapping subdomains.Source: §7.1 · p. 27

7.2 Approximate orthogonality of spaces on subdomains

  • The section establishes approximate orthogonality results for subdomain spaces and gives an analogue in negative Sobolev spaces.The negative-space result is stated for 1 ≤ m ≤ p + 1 and smooth, supported ψℓ.Source: §7.2 · pp. 27–28

8 Proof of Theorem 2.7

The proof of Theorem 2.7 analyzes the preconditioner through continuous-level subdomain problems and estimates for their local terms. It combines those bounds under the mesh threshold to complete the theorem’s proof.

8 Proof of Theorem 2.7

  • The proof is given for left preconditioning; the right-preconditioned result follows because the assumptions are invariant under taking adjoints.The passage points to [20, Equation 1.8] for the right-preconditioning argument.Source: §8 · p. 28

8.3 Start of the proof of Theorem 2.7

  • The proof decomposes the fine space using the coarse-space orthogonal projector, reducing the theorem to a bound on the resulting operator terms.The projector is Z-orthogonal, and the decomposition is ΠHcVh ⊕ (I − ΠHc)Vh.Source: §8.3 · p. 29

8.4 Study of the local problems at the continuous level

  • The continuous-level analysis splits the local correction into low- and high-frequency components and proves bounds for local operators, including Lℓ and Aℓ, Bℓ.Lemma 8.1 gives Lℓ regularity and boundedness results; Lemma 8.2 studies Aℓ and Bℓ.Source: §8.4 · pp. 30, 33
  • A key estimate used for the local bounds relies on Galerkin orthogonality with respect to a Z-orthogonal projection onto VHc.The proof identifies this projection and uses it to reduce the estimates it needs to establish.Source: §8.4 · p. 31

8.5 End of the proof of Theorem 2.7

  • The final estimates combine the local bounds under the mesh threshold, with a constant independent of the number of subdomains N.The proof invokes the condition ρ(Hc k)^{2p} ≤ c in estimating terms.Source: §8.5 · pp. 35–37

A Coercive estimates in the absorbing layer

The appendix derives a coercive estimate under a stated ellipticity condition, using a square-completion argument.

A Coercive estimates in the absorbing layer

Loading 2610.11774v1…