Source-linked AI summary
Discrete Edge Multiscale Space based Hybrid Schwarz Preconditioner for High-Frequency Helmholtz Problems
Shubin Fu, Shihua Gong, Guanglian Li, Yueqi Wang
TL;DR
High-frequency Helmholtz problems combine fine-scale oscillations with indefinite, non-normal systems and long-range propagation, while coarse spaces can lack stable projections when their meshes are too coarse. This paper develops an edge multiscale coarse space within a multiplicative hybrid Schwarz preconditioner and analyzes its approximation properties. The analysis establishes contractivity under stated conditions and reports rapid convergence with level ℓ=1 in numerical tests.
Problem
High-frequency Helmholtz problems are challenging because oscillations demand fine meshes, indefiniteness and non-normality undermine standard iterative methods, and long-range propagation inhibits localization-based parallelism.
Source: §1 · pp. 1–2Method
The paper combines a one-level RAS-imp preconditioner with a coarse solver based on an edge multiscale space in a multiplicative hybrid Schwarz method.
Source: §1 · p. 3, §3.2 · p. 8Results
The analysis establishes convergence of the EMs-HS iteration under stated conditions, and numerical experiments report rapid convergence with level ℓ=1.
Source: §1 · p. 3, §5.2 · p. 26Takeaways & Limitations
In the stated optimal uniform-mesh case, convergence requires a coarse-space dimension of about min{k^(3d-2), k^(-1/2)h^(-d)}.
Source: §1 · p. 3
Abstract
from arXiv · showhide
In this work, we develop a novel hybrid Schwarz method, termed as edge multiscale space based hybrid Schwarz (EMs-HS), for solving the Helmholtz problem with large wavenumbers. The problem is discretized using $H^1$-conforming nodal finite element methods on meshes of size $h$ decreasing faster than $k^{-3/2}$ such that the discretization error can be bounded by the data uniformly with respect to $k$. EMs-HS consists of a one-level Schwarz preconditioner (RAS-imp) and a coarse solver in a multiplicative way. The RAS-imp preconditioner solves local problems on overlapping subdomains with impedance boundary conditions in parallel, and combines the local solutions using partition of unity. On the PDE level, this coarse space corresponds to an edge multiscale space proposed in {[S. Fu, G. Li, R. Craster, and S. Guenneau, \emph{Multiscale Model. Simul.}, 19(4):1684-1709, 2021]}. The approximation properties of this coarse space to the discrete solutions from the primal and adjoint problems are derived by a novel conforming Galerkin finite element method based upon a nonstandard variational formulation. This work represents the first theoretical analysis of an edge multiscale space at the discrete level. We prove that the EMs-HS preconditioner leads to a convergent fixed-point iteration uniformly for large wavenumbers, by rigorously analyzing the approximation properties of the coarse space to the global Helmholtz harmonic extension part and to the solution of the adjoint problem. We provide extensive numerical results on the sharpness of the theoretical findings and also demonstrate the method on challenging heterogeneous models.
1. Introduction
High-frequency Helmholtz problems are difficult because oscillatory solutions require fine meshes, while indefiniteness and long-range propagation hinder iterative and parallel methods. The paper proposes an edge multiscale coarse space for a hybrid Schwarz method and analyzes its convergence.
1. Introduction
- Oscillatory solutions require fine discretizations, while indefinite, non-normal systems and long-range propagation challenge standard iterative methods and localization-based parallel algorithms.These difficulties worsen as the wavenumber k increases.Source: §1 · pp. 1–2
- Classical two-level Schwarz theory gives pessimistic estimates for high-frequency Helmholtz problems because the indefinite part grows with k^2.A coarse space is generally needed to capture and transfer global information for scalable domain decomposition.Source: §1 · p. 2
- Conventional coarse spaces may lack a guaranteed stable projection when the coarse mesh is too coarse, motivating spaces with mild wavenumber dependence and stable approximation.The paper identifies pollution control and coarse-grid accuracy as desired properties.Source: §1 · p. 2
- The proposed EMs-HS method combines an edge multiscale coarse space with a one-level Schwarz preconditioner, and its analysis establishes convergence under stated conditions.The coarse-space approximation analysis covers the global Helmholtz harmonic extension and the adjoint solution.Source: §1 · p. 3
- The proposed coarse-space dimension is about min{k^(3d-2), k^(-1/2)h^(-d)} in the stated optimal uniform-mesh case, and experiments report rapid convergence with level ℓ=1.The numerical tests cover two- and three-dimensional homogeneous and heterogeneous coefficients.Source: §1 · p. 3
2. The Helmholtz equation and its finite element approximation
This section sets out the Helmholtz problem and its variational formulation, then records a wavenumber-independent boundedness property of the associated sesquilinear form.
2. The Helmholtz equation and its finite element approximation
- The problem is posed on a bounded convex polygonal or polyhedral domain in dimensions two or three, with data f and impedance-boundary data g.The wavenumber is assumed to satisfy k ≥ k0 > 0.Source: §2 · p. 4
- The variational formulation seeks u in V satisfying the weak equation defined by sesquilinear form a and conjugate-linear form F.The passages identify these forms but do not provide their expressions.Source: §2 · p. 4
- The sesquilinear form a is bounded by a constant independent of the wavenumber k.Source: §2 · p. 4
2. The G˚arding’s inequality holds
This section defines the adjoint problem and describes the finite element approximation framework used to establish discrete stability and well-posedness under mesh assumptions.
2. The G˚arding’s inequality holds
- The adjoint problem is introduced as an auxiliary variational problem used in analysis of indefinite problems satisfying the Gårding inequality.The passage states that the adjoint form a* is obtained by interchanging the arguments of a.Source: §2 · pp. 4–5
- The discretization uses a uniform triangulation and an H1-conforming piecewise-linear finite element space, with a standard nodal interpolation operator.The FEM approximation property is assumed for functions in H2(Ω).Source: §2 · pp. 4–5
- Under the stated mesh condition, the discrete problem is well-posed and its solution satisfies a stability estimate whose constant is independent of h and k.Source: §2 · p. 5
- For quasi-uniform meshes, the cited background gives h-version quasi-optimality when kp+1hp is sufficiently small, while the hp-version requires hk/p sufficiently small and p growing logarithmically with k.The passage notes that these piecewise-polynomial spaces have dimensions much larger than k^d.Source: §2 · p. 5
3. The hybrid Schwarz method
The method combines overlapping local Schwarz solves with a coarse correction in a multiplicative preconditioner. The section sets out the overlap assumptions, local RAS-imp construction, and the contractivity objective for the hybrid method.
3. The hybrid Schwarz method
- The domain is covered by overlapping subdomains associated with a quasi-uniform coarse mesh, with finite overlap and a scale-resolution requirement on each subdomain.The partition of unity is subordinate to the subdomain cover.Source: §3 · pp. 5–6
3.1. RAS-imp preconditioner
- RAS-imp defines local problems with impedance boundary conditions and combines local corrections using partition-of-unity weighted prolongation.The local sesquilinear form is stated to be bounded by a constant independent of k.Source: §3.1 · pp. 6–7
- The local-global approximation lemma bounds the assembled finite element function from the local functions with a constant independent of k, h, and H.Its proof invokes interpolation stability and the finite-overlap assumption.Source: §3.1 · p. 8
3.2. The EMs-HS preconditioner
- EMs-HS is a multiplicative assembly of RAS-imp and a coarse solver determined by a coarse space Vh,0.The one-level correction is applied first, followed by a coarse correction computed from the updated residual.Source: §3.2 · p. 8
- The analysis targets contractivity of the error-transfer operator I − BhybridA under explicit requirements on h, k, subdomain diameter, and overlap.The section also studies the discrepancy between a local Schwarz projection and restriction to a subdomain.Source: §3.2 · p. 9
- A discrepancy estimate is stated using σ := (k d̄)^(-3/2)(kh)^(-1/2), with its constant independent of h, k, d̄, and δ.Source: §3.2 · p. 9
4. Coarse space
The coarse space uses hierarchical edge data and local multiscale extensions, assembled globally to approximate the global Helmholtz harmonic extension space and provide an ansatz for the adjoint problem.
4. Coarse space
- The edge multiscale coarse space approximates the global Helmholtz harmonic extension space and also serves as an ansatz space for the adjoint problem.Its global basis functions are obtained from local ones through weighted prolongation.Source: §4 · p. 10, §4.2 · p. 11
4.1. Hierarchical subspace splitting over I =: [0,1]
- The nested hierarchical subspaces Vℓ split L2(I), with the construction extended to L2(I^(d−1)) by tensor products for d = 2,3.The hierarchical space is used to approximate the exact solution restricted to the coarse skeleton.Source: §4.1 · p. 10
4.2. Coarse space
- The boundary of each subdomain is partitioned into uniformly shape-regular affine edges or faces, with their number uniformly bounded independently of h and H.Hierarchical bases up to level ℓ define the local edge space on each coarse edge.Source: §4.2 · p. 11
- Local multiscale spaces are computed by FEM solves and assembled into the global coarse space using weighted prolongation.The local problems can be solved in parallel.Source: §4.2 · pp. 11–12
- Under Assumption 1, the local sesquilinear form is coercive for functions that vanish on the subdomain boundary.This establishes well-posedness of the local problems used in the coarse-space construction.Source: §4.2 · p. 13
5. Convergence analysis
The convergence analysis establishes contractivity of the hybrid error-transfer operator, and thus the hybrid iteration, under specified conditions on the wavenumber, mesh, subdomains, and levels. It does so using local and edge multiscale approximation properties, including approximation to the adjoint solution, and states that condition (5.49) ensures the coarse problem is well-posed.
5. Convergence analysis
- The hybrid error-transfer operator is contractive under explicit conditions, using a Schatz argument based on Gårding’s inequality and adjoint approximation.The discrete approximation properties of Vh,0 and solvability of the coarse solver are identified as key novelties.Source: §5 · pp. 13–14
5.1.1. a priori estimate on the PDE level
- The PDE-level nonstandard variational formulation is shown to be well-posed and to satisfy a local a priori estimate.The estimate is used to establish well-posedness of the formulation for prescribed boundary data.Source: Then there holds · p. 16
5.1.2. Local a priori estimate on a discrete level
- Under the stated assumptions, a conforming Galerkin approximation yields a discrete local error estimate, supporting approximation of the local multiscale space.The analysis introduces a finite-element approximation based on the nonstandard formulation and derives local stability and approximation estimates.Source: §5.1.2 · p. 17, Then there holds · pp. 21, 23
5.2. Contractive property of I −BhybridA
- The edge multiscale ansatz space Vh,0 approximates the target Helmholtz-harmonic space under the stated assumptions, with a constant independent of k, h, d̄, and δ.The proof uses global-to-local splittings and weighted prolongation.Source: §5.2 · pp. 23–24
- The analysis also establishes an approximation property of Vh,0 for discrete solutions of the adjoint problem, under the stated assumptions.This adjoint approximation supports the contractivity argument.Source: §5 · p. 14, §5.2 · p. 24
- Theorem 6 establishes contractivity of I − BhybridA under its stated subdomain, mesh, and level conditions, with the desired assertion proved when h ≥ Ck^-3 for a sufficiently large constant C.Source: §5.2 · pp. 26, 28
- Condition (5.49) guarantees well-posedness of the coarse problem A0.Source: §5.2 · p. 28
6. Numerical tests
The tests verify two theoretical estimates, examine convergence as wavenumber and problem size increase at fixed wavelength resolution, and assess heterogeneous media with discontinuous wave speed.
6.1. Test 1: verification of Lemma 2
- In Setting A, the correlation between bσ and (hk)^-1/2 is 0.9999; in Setting B, both quantities remain constant over the tested wavenumbers.These observations are consistent with the dependence on hk in Lemma 2.Source: §6.1 · p. 28
6.2. Test 2: verification of Corollary 1
- The observed dependence of Δ on d̄ is approximately linear in both settings, consistent with the Corollary 1 bound.Table 2 compares Δ with 2^-ℓ/2 d̄.Source: §6.2 · p. 29, Table 2 · p. 29
6.3. Test 3: challenging fixed-nppw family in two dimensions
- In the 2D fixed-resolution family, level-1 EMs-HS needs 5–7 BiCGStab applications and 6–9 stationary applications, while level-0 fails on the finest mesh.One-level application counts grow with k; level-0 stationary iteration diverges on the three finest meshes, and BiCGStab exceeds 200 applications on the finest mesh.Source: Table 3 · p. 30, §6.3 · p. 30
6.4. Test 4: challenging fixed-nppw family in three dimensions
- In 3D, BiCGStab requires four applications at every mesh size, while stationary EMs-HS requires four or five as wavenumber and subdomain count increase.The family maintains fixed wavelength resolution.Source: §6.4 · p. 30, Table 4 · p. 31
6.5. Test 5: heterogeneous media
- For all three heterogeneous media, level-0 EMs-HS converges in five BiCGStab applications; level-1 reduces this to four in both 2D models.The tested media include high-speed inclusions, low-speed fractures, and a 3D system with 8,120,601 unknowns.Source: Table 5 · p. 31, §6.5 · p. 31
7. Conclusion
The paper presents and analyzes an edge-multiscale-based hybrid Schwarz preconditioner for large-wavenumber Helmholtz problems, with numerical demonstrations in 2D and 3D. Future work includes scalable coarse solvers and adapting the approach to time-harmonic Maxwell problems.
7. Conclusion
- The EMs-HS preconditioner uses an edge multiscale ansatz space and allows overlap of one coarse-grid size.The authors report rigorous convergence analysis and extensive 2D and 3D numerical tests.Source: §7 · p. 32
- A scalable coarse solver remains a research direction because the coarse-problem dimension increases with wavenumber k.Source: §7 · p. 32
- The authors identify a similar hybrid Schwarz preconditioner for large-wavenumber time-harmonic Maxwell equations as future work.Source: §7 · p. 32