🔢 mathematics

Numerical Study of Eigenvector Deflation to Accelerate the WaveHoltz Method

This paper presents a numerical study demonstrating that eigenvector deflation, implemented via direct projection or augmented-Krylov methods and utilizing the EigenWave approach for efficient eigenpair computation, significantly accelerates the WaveHoltz method for solving the Helmholtz equation at high frequencies by maintaining a constant asymptotic convergence rate and achieving cost-effectiveness after solving just two right-hand sides.

Original authors: Daniel Appelo, William D. Henshaw, Zhichao Peng

Published 2026-07-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Appelo, William D. Henshaw, Zhichao Peng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to tune a radio to a specific station, but the signal is incredibly weak and full of static. In the world of physics and engineering, solving the Helmholtz equation is like trying to find that perfect signal. It describes how waves (like sound or light) behave when they hit obstacles or bounce around a room.

The problem is, when the frequency of the wave is high (like a high-pitched whistle), the math gets incredibly messy. The computer has to do millions of tiny calculations, and it often gets "stuck" in a loop, trying to find the answer over and over again without getting closer. This is like trying to tune a radio that keeps jumping between stations.

This paper introduces a clever trick to stop the radio from jumping: Eigenvector Deflation.

Here is a breakdown of how the authors fixed this problem, using simple analogies:

1. The Problem: The "Stuck" Radio

The authors use a method called WaveHoltz. Think of this as a way to solve the wave problem by simulating a movie of the wave moving back and forth in time, then filtering the result to find the steady answer.

The Issue: At high frequencies, this "movie" takes a very long time to settle down. The computer has to run the simulation thousands of times just to get a clear picture.
The Analogy: Imagine trying to push a heavy swing. If you push at the wrong time, the swing barely moves. If you push at the exact right rhythm (resonance), it goes high. But if you are trying to find that rhythm in a noisy room, you might push hundreds of times before you get it right.

2. The Solution: "Deflation" (Turning Down the Volume on the Noise)

The authors realized that the reason the computer gets stuck is that it's struggling with specific "troublemaker" frequencies (eigenvalues) that are very close to the one it's trying to solve.

Deflation is like a noise-canceling headphone for the math.

How it works: Before the computer starts its long simulation, it identifies those specific "troublemaker" frequencies. It then mathematically "turns down the volume" on them (deflates them) so they don't interfere with the main calculation.
The Result: Once those troublemakers are silenced, the computer can find the answer much, much faster. In some cases, it went from needing hundreds of steps to just a few.

3. Two Ways to Do It

The paper tests two different ways to apply this "noise cancellation":

Method A: Direct Deflation (The "Pre-Filter"):
Imagine you have a bucket of muddy water. Before you try to drink it, you manually scoop out the biggest chunks of dirt (the eigenvectors) and throw them away. Then you filter the rest. This is fast and direct.
Method B: Augmented Krylov (The "Smart Assistant"):
Instead of just removing the dirt, you hire a smart assistant who knows exactly where the dirt is. As you try to drink, the assistant constantly guides your hand to avoid the dirt spots. This is a bit more complex but very robust, especially if the water is extra muddy (like on complex, overlapping grids).

4. The "Magic Number" Rule

The authors discovered a golden rule for how many "troublemakers" to silence.

If you double the frequency of the wave, you don't just need to silence twice as many troublemakers; you need to silence four times as many (in 2D space).
Analogy: If you are trying to tune a radio in a small room, you might only need to block out one noisy neighbor. But if you move to a huge stadium with high-frequency noise, you need to block out a whole section of the crowd, not just one person. If you follow this "quadratic" rule, the computer stays fast no matter how high the frequency gets.

5. Compression: Fitting the Library in a Backpack

To silence the troublemakers, the computer needs to store a lot of data (the "eigenvectors"). Storing hundreds of these can take up a lot of memory, like trying to carry a library in your backpack.

The Trick: The authors used a technique called SVD Compression.
Analogy: Imagine you have a photo of a complex landscape. Instead of saving every single pixel, you realize that 90% of the image is just a smooth blue sky. You can describe the sky with a simple formula and only save the details for the mountains. This shrinks the file size massively without losing the important picture.
The Result: They could shrink the memory needed to store these "troublemakers" by a huge amount (sometimes down to 13% of the original size) without slowing down the solution.

6. The "Overset" Grids (The Puzzle Piece Approach)

Real-world problems often have weird shapes (like a room with curved walls or a complex machine). To solve these, the authors use Overset Grids, which are like overlapping puzzle pieces (some square, some curved) that fit together to cover the whole shape.

The Challenge: When you overlap these grids, the math gets messy, and the "noise cancellation" isn't perfect.
The Finding: They found that the "Smart Assistant" method (Augmented Krylov) worked better than the "Pre-Filter" method on these complex, overlapping grids. It was more forgiving of the slight errors caused by the puzzle pieces not matching perfectly.

Summary

The paper proves that by identifying and silencing specific mathematical "troublemakers" before solving a wave problem, we can make the computer drastically faster.

Speed: It can solve problems that previously took forever in a fraction of the time.
Efficiency: It works well even when you need to solve the same problem for many different inputs (like different sound sources in a room).
Practicality: By compressing the data, it doesn't require a supercomputer's memory to work.

In short, they found a way to tell the computer, "Ignore these specific annoying frequencies, and you'll find the answer almost instantly." This makes solving complex wave problems (like designing better concert halls or sonar systems) much more practical.

Technical Summary: Numerical Study of Eigenvector Deflation to Accelerate the WaveHoltz Method

Problem Statement
The paper addresses the computational challenge of solving the Helmholtz equation for high frequencies, particularly when multiple right-hand sides are required. High-frequency solutions necessitate fine grid resolutions to control dispersion (pollution) errors and involve solving indefinite linear systems, which are difficult for iterative solvers. The WaveHoltz method, an iterative technique that transforms the indefinite Helmholtz problem into a positive-definite (or near-positive-definite) system by filtering the solution of an associated wave equation, offers a pathway to solve these problems. However, for energy-conserving boundary conditions (Dirichlet or Neumann), the standard WaveHoltz fixed-point iteration (FPI) converges slowly at high frequencies, requiring approximately $O(\omega^{2d})$ iterations in $d$ dimensions. Even when accelerated by Krylov subspace methods like Conjugate Gradient (CG) or GMRES, the iteration count scales as $O(\omega^d)$ , leading to high computational costs.

Methodology
The authors investigate the use of eigenvector deflation to accelerate the WaveHoltz method. The core idea is to remove the components of the solution and forcing function associated with eigenvalues of the discrete operator that lie nearest to the driving frequency $\omega$ , as these eigenvalues correspond to the slowest convergence modes.

The study employs two primary strategies for incorporating eigenvectors:

Direct Eigenvector Deflation (DEVD): This approach, based on Algorithm 2, explicitly projects the forcing function and the iterates against a set of deflation vectors (eigenvectors). The WaveHoltz iteration solves the deflated problem, and the final solution is reconstructed by adding back the components along the deflation set. This method is applied directly to the WaveHoltz fixed-point iteration or used as a preconditioner for Krylov methods.
Augmented-Krylov Eigenvector Deflation (AUKED): This approach augments the Krylov subspace with deflation vectors. The paper implements and tests three specific algorithms:
- Deflated Conjugate Gradient (DCG) for symmetric systems.
- Augmented GMRES (AGMRES) for non-symmetric systems (e.g., on overset grids).
- Augmented (recycled) BICGSTAB (ABICGSTAB).

The eigenvectors required for deflation are computed using the EigenWave approach, a matrix-free Arnoldi method. The study also explores the use of approximate eigenvectors (computed on coarser grids) and the compression of eigenvectors using Singular Value Decomposition (SVD) to reduce storage costs, leveraging the fact that eigenvectors on structured grids can be represented as matrices.

Key Contributions and Results

Convergence Acceleration: Numerical experiments on single curvilinear grids and overset grids demonstrate that deflating eigenvectors with eigenvalues closest to $\omega$ significantly reduces iteration counts. The deflated solvers (DCG, AGMRES, ABICGSTAB) consistently outperform standard Krylov acceleration and the undeflated fixed-point iteration.
Scaling of Deflation Vectors: The paper establishes that to maintain a frequency-independent asymptotic convergence rate (ACR) as $\omega$ increases, the number of deflation vectors $N_D$ must grow quadratically with frequency in two dimensions ( $N_D \propto \omega^2$ ). Linear growth of $N_D$ with $\omega$ results in a degradation of the convergence rate.
Efficiency and "Break-even": The overhead of precomputing eigenvectors is shown to be manageable. The authors demonstrate that the deflated solver breaks even against the undeflated solver after as few as two right-hand sides, making the approach highly attractive for problems requiring multiple solutions.
SVD Compression: The study shows that eigenvectors on structured grids are highly compressible via SVD. Compressing eigenvectors reduces storage requirements significantly (compression ratios as low as 0.13 were observed) without measurably affecting the convergence rate of the iterative solver, provided the compression tolerance is sufficiently small relative to the solver tolerance.
Overset Grids and Approximate Eigenvectors: On overset grids, where discrete eigenvectors are not perfectly orthogonal due to interpolation errors, the AUKED approach (AGMRES/ABICGSTAB) yields more accurate solutions than DEVD. However, DEVD still provides results consistent with the grid resolution. Furthermore, the use of eigenvectors computed on coarser grids is effective for deflation, provided the coarse grid is sufficiently resolved to capture the relevant eigenmodes.
Robustness: The approach is validated on complex geometries, including a circular disk, the Penrose unilluminable room, and a domain with sixteen knife edges, using summation-by-parts (SBP) operators on curvilinear and overset grids.

Significance
The paper claims that eigenvector deflation, when combined with the WaveHoltz method, transforms it into a robust and efficient solver for high-frequency Helmholtz problems, particularly those requiring many right-hand sides. By systematically analyzing the relationship between the number of deflation vectors and frequency, and by demonstrating the viability of SVD compression and coarse-grid eigenvectors, the authors show that the computational overhead of deflation is outweighed by the reduction in iteration counts. The results suggest that this deflated WaveHoltz approach is a competitive alternative to standard iterative solvers for complex engineering applications involving wave propagation.