On $hp$-Convergence of PSWFs and A New Well-Conditioned Prolate-Collocation Scheme

Technical Summary: On hp-Convergence of PSWFs and a New Well-Conditioned Prolate-Collocation Scheme

Problem Statement
Prolate Spheroidal Wave Functions (PSWFs) offer a spectral basis for approximating bandlimited functions, possessing unique properties such as orthogonality over both finite and infinite intervals and optimal time-frequency concentration. While they have been proposed as superior alternatives to Legendre and Chebyshev polynomials for pseudospectral and spectral-element methods, their application faces significant theoretical and numerical hurdles. Specifically, PSWFs are non-polynomial bases, which leads to the failure of standard polynomial-based numerical properties. A critical issue identified recently by Boyd et al. is the nonconvergence of $h$-refinement in prolate-element methods, a behavior that contradicts the standard convergence theory of spectral elements. Furthermore, the lack of exact quadrature rules for products of PSWFs renders the Galerkin formulation less attractive, and standard collocation schemes often suffer from ill-conditioning.

Methodology
The authors address these challenges through three primary methodological developments:

1. Theoretical Analysis of hp-Convergence: The paper establishes an $hp$-error bound for PSWF-projections. By analyzing the projection operator on broken Sobolev spaces, the authors derive a rigorous error estimate that isolates the dependence on the mesh size $h$ and the polynomial degree $N$.
2. Practical Implementation of the Kong-Rokhlin Rule: The selection of the bandwidth parameter $c$ relative to the number of collocation points $N$ is crucial for accuracy. The authors propose a practical approximation to the Kong-Rokhlin rule, which pairs $(c, N)$ to ensure high accuracy in integration and differentiation. This approximation avoids the computationally expensive calculation of PSWF eigenvalues $\lambda_N$ by utilizing an upper bound derived from Stirling's approximation.
3. Construction of a New Basis for Well-Conditioning: To overcome the ill-conditioning of standard prolate-collocation systems, the authors construct a new basis $\{\beta_k\}$ with "dual nature."
   • This basis is defined via a generalized Birkhoff interpolation problem where the second derivative of the basis functions approximates the cardinal basis properties.
   • Crucially, the basis functions $\beta_k$ (for interior points) are constructed in a space spanned by the double integrals of PSWFs, rather than the PSWFs themselves. This allows for stable computation without inverting ill-conditioned differentiation matrices.
   • The resulting matrix $B_{in}$ acts as a near-inverse to the second-order differentiation matrix $D^{(2)}_{in}$, effectively preconditioning the system.

Key Contributions

• Rigorous Proof of Nonconvergence: The paper provides a theoretical justification for the nonconvergence of $h$-refinement in prolate-element methods. The derived error bound (Theorem 4.1) demonstrates that for a fixed $N$, refining $h$ does not lead to convergence in the $L^2$ norm because the error term independent of $h$ dominates. This contrasts sharply with Legendre polynomial approximations, which exhibit standard $h$-convergence.
• Well-Conditioned Collocation Schemes: The authors introduce a new PSWF basis that leads to collocation linear systems with condition numbers independent of both the bandwidth parameter $c$ and the number of points $N$. Two approaches are presented:
  1. Preconditioning: Using the new basis matrix $B_{in}$ to precondition the standard collocation system.
  2. Direct Basis Formulation: Formulating the collocation scheme directly using the new basis, where the matrix of the highest derivative becomes the identity matrix.
• Optimized Parameter Pairing: A practical algorithm is proposed to implement the Kong-Rokhlin rule for pairing $(c, N)$, ensuring that the discrete eigenvalues of the prolate differentiation matrix approximate the continuous operator's eigenvalues with high accuracy (up to 12 digits) for a significantly larger portion of the spectrum compared to Legendre methods.

Results

• Eigenvalue Resolution: Numerical experiments show that when using the proposed $(c, N)$ pairing, approximately 87% of the discrete eigenvalues of the prolate differentiation matrix approximate the continuous eigenvalues to 12-digit accuracy. In contrast, the Legendre case achieves this accuracy for only about 25% of the eigenvalues.
• Conditioning and Solver Performance: The new well-conditioned schemes (P-PCOL and N-PCOL) exhibit condition numbers that remain stable (around 1.3–1.9) as $N$ increases, whereas the standard prolate-collocation scheme (PCOL) suffers from condition numbers growing as $O(N^4)$. Consequently, iterative solvers (BiCGSTAB) converge in a constant number of steps (6–7) for the new schemes, compared to thousands of steps for the standard scheme at high $N$.
• Helmholtz Equations: In solving Helmholtz equations with high wave numbers in heterogeneous media, the new $p$-version prolate-element method significantly outperforms Legendre-based spectral-element methods. The new approach achieves high accuracy with coarser grids and demonstrates rapid convergence rates for highly oscillatory solutions.

Significance
The paper claims that while PSWFs possess unique advantages for bandlimited functions, their naive application in spectral methods is flawed due to the lack of $h$-convergence and numerical instability. The significance of this work lies in:

1. Clarifying Limitations: Providing a rigorous theoretical explanation for the failure of $h$-refinement in prolate elements, correcting the assumption that standard spectral-element convergence theories apply directly to non-polynomial bases.
2. Enabling Practical Use: Offering a robust, well-conditioned collocation framework that makes PSWFs a viable and often superior alternative to polynomial bases for problems involving bandlimited or highly oscillatory solutions.
3. Superior Performance: Demonstrating that, when combined with the appropriate $(c, N)$ pairing and the new basis, PSWF-based methods significantly outperform Legendre polynomial-based methods in resolving continuous spectra and solving high-wave-number Helmholtz equations in heterogeneous media.

The authors conclude that the proposed well-conditioned collocation approach, rather than the Galerkin method, is likely the best choice for spectral algorithms using PSWFs due to the absence of exact quadrature rules for PSWF products.