Spectral coarse spaces based on indefinite operators: the $H_k$-GenEO method

Technical Summary: Spectral Coarse Spaces Based on Indefinite Operators: The Hk-GenEO Method

Problem Statement
The paper addresses the numerical solution of highly indefinite boundary value problems arising from the heterogeneous Helmholtz equation:
$$-\nabla \cdot (A\nabla u) - k^2 n u = f \quad \text{in } \Omega, \quad u = 0 \quad \text{on } \partial\Omega,$$
where $k > 0$ is a large wavenumber, $A$ is a positive definite matrix with $L^\infty$ entries, and $n$ is a positive $L^\infty$ function. The focus is on the regime where $k$ is large, rendering the problem highly indefinite and challenging for standard iterative solvers. While classical domain decomposition methods (DDM) with spectral coarse spaces (e.g., GenEO) have been successful for positive semi-definite problems, they often fail to be robust for highly indefinite problems when constructed from positive semi-definite local eigenproblems.

Methodology
The authors propose a novel two-level additive Schwarz preconditioner, termed Hk-GenEO, designed specifically for indefinite operators. The methodology involves the following key components:

1. Local Indefinite Eigenproblems: Unlike previous spectral methods that rely on positive semi-definite local operators (such as the Laplacian), Hk-GenEO constructs the coarse space by solving local generalised eigenvalue problems (GEVPs) based on the full indefinite operator of the global problem. On each coarse subdomain $\Omega^c_i$, the GEVP is defined as:
   $$-\nabla \cdot (A\nabla p) - k^2 n p = \lambda \left[ -\nabla \cdot (A\nabla (\Xi_i p)) + k^2 n (\Xi_i p) \right] \quad \text{on } \Omega^c_i,$$
   where $\Xi_i$ is a partition of unity operator. The right-hand side is modified to be positive definite (close to the norm used in analysis), while the left-hand side retains the indefiniteness of the original Helmholtz operator.

2. Coarse Space Construction: The coarse space $V_0$ is spanned by the eigenfunctions corresponding to the smallest eigenvalues (including negative and small positive ones) of these local GEVPs. The method explicitly allows the local subdomains to be large enough such that the local GEVPs remain indefinite, thereby capturing oscillatory modes essential for high-frequency problems.

3. Theoretical Framework: The paper develops an abstract spectral theory for indefinite GEVPs. It establishes conditions under which the bilinear form associated with the GEVP is positive definite on the complement of the subspace spanned by the retained eigenfunctions. This theory is applied to derive sufficient conditions for the robustness of the preconditioned GMRES solver.

4. Robustness Conditions: The analysis provides explicit conditions for robust convergence in terms of the local subdomain diameter $H_\ell$, the coarse subdomain diameter $H_c$, and the eigenvalue tolerance $\tau$ (the threshold for retaining eigenmodes). Specifically, robustness is guaranteed if:

   • $H_\ell \lesssim k^{-1}$ (ensuring local solvability).
   • $\tau \gtrsim (1+C_{stab})^2 k^2$ (ensuring sufficient modes are retained).
   • Crucially, the theory imposes no explicit upper constraint on the coarse diameter $H_c$, allowing coarse subdomains to be large and the local GEVPs to be indefinite.

Key Contributions

• Hk-GenEO Formulation: Introduction of a spectral coarse space built directly from indefinite local operators, contrasting with previous $\Delta$-GenEO or $H$-GenEO approaches that used positive semi-definite operators.
• Abstract Indefinite Spectral Theory: Development of a general theory for indefinite GEVPs, including the existence of a basis of eigenvectors and the construction of a projection operator that ensures stability on the complement of the coarse space.
• Explicit Robustness Estimates: Derivation of $k$-explicit sufficient conditions for the convergence of GMRES. The paper proves that the method is robust with respect to the wavenumber $k$, the number of subdomains, and coefficient heterogeneity, provided the eigenvalue tolerance $\tau$ is chosen appropriately.
• Decoupled Decompositions: Theoretical and numerical demonstration that the coarse decomposition (used for eigenproblems) can be decoupled from the local decomposition (used for one-level solves), allowing for different subdomain sizes ($H_c$ vs. $H_\ell$).

Numerical Results
The authors present numerical experiments in 2D for both homogeneous and heterogeneous (layered medium) cases using the FreeFEM framework.

• Robustness to $k$: For moderate to large thresholds ($\tau = 0.4, 0.6$), the GMRES iteration counts remain stable and essentially independent of $k$ and the number of subdomains $N$.
• Threshold Sensitivity: A small threshold ($\tau = 0.2$) leads to a significant increase in iterations as $k$ grows, indicating a loss of robustness.
• Heterogeneity: The method demonstrates resilience to high variations in the coefficient $A$, with iteration counts showing only mild dependence on the contrast ratio.
• Coarse Space Dimension: The dimension of the coarse space grows moderately with $k$ (empirically observed as $O(k^{1.1} \text{ to } k^{1.4})$), which is significantly slower than the fine space dimension growth ($O(k^2)$).
• Decoupled Decompositions: Experiments show that using a coarser decomposition for the coarse space (fewer subdomains $N$) compared to the local solver ($Q$) yields only a modest increase in iteration counts, offering potential memory savings.

Significance and Claims
The paper claims that Hk-GenEO provides a practical and scalable preconditioner for highly indefinite Helmholtz-type problems. Its primary significance lies in:

1. Overcoming the Limitations of Positive Semi-Definite Coarse Spaces: By utilizing the indefinite nature of the operator in the coarse space construction, the method captures the necessary oscillatory modes that positive semi-definite approaches miss at high frequencies.
2. Theoretical Rigor: It provides the first substantial theoretical analysis for spectral coarse spaces based on indefinite operators, moving beyond empirical observations found in prior work (e.g., [5, 7]).
3. Flexibility: The method allows for large coarse subdomains and decoupled decompositions, offering flexibility in algorithm design that was previously constrained by the requirement for small, coercive local problems.

The authors note that while their theoretical bound for the eigenvalue tolerance $\tau$ (scaling with $k^2$) appears pessimistic compared to numerical observations (where constant $\tau$ often suffices), the method remains robust under these weaker practical conditions. The work establishes a foundation for solving indefinite PDEs where coefficient heterogeneity and high wavenumbers previously posed significant challenges to iterative solvers.