A parallel sweeping preconditioner for high frequency heterogeneous 3D Helmholtz equations

Jack Poulson, Björn Engquist, Sergey Fomel, Siwei Li, Lexing YingarXiv 2012 · arXiv · OpenReview

Abstract

A parallelization of a sweeping preconditioner for 3D Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be $O(\gamma^2 N^{4/3})$ and $O(\gamma N \log N)$, where $\gamma(\omega)$ denotes the modestly frequency-dependent number of grid points per Perfectly Matched Layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: "Parallel Sweeping Preconditioner (PSP)" and the underlying distributed multifrontal solver, "Clique".

Introduction

Simulating time-harmonic wave propagation in complex 3D environments, governed by the Helmholtz equation, is a fundamental challenge in fields such as seismic imaging and medical diagnostics. The primary mathematical obstacle is the indefinite nature of the resulting matrix systems. Standard iterative solvers like GMRES often fail to converge efficiently as frequency increases, while exact direct solvers suffer from prohibitive memory requirements for large-scale 3D grids.

The sweeping preconditioner offers a middle ground by processing the domain layer-by-layer. However, its inherently sequential nature has historically limited its scalability on modern high-performance computing (HPC) architectures. This work addresses this limitation by introducing a parallelized sweeping preconditioner capable of handling massive, high-frequency models with near-linear efficiency.

Methods

The proposed approach bridges the gap between sequential sweeping and massive parallelism through several key innovations:

Moving Perfectly Matched Layers (PML)

Instead of a full matrix factorization, the method approximates the physics by solving local auxiliary problems. Perfectly Matched Layers (PMLs) act as mathematical sponges that absorb waves at the domain boundaries, allowing for local wave propagation analysis without spurious reflections.

Figure 1: Domain truncation using a Perfectly Matched Layer (PML) to define a local region of interest.

Panel-based Parallelization and Selective Inversion

While the sweep itself follows a directional order, the authors group planes into "panels." The factorization of these panels is distributed across multiple processors. To further enhance parallel performance, the authors employ "selective inversion" within their custom distributed multifrontal solver, Clique. This technique transforms difficult-to-parallelize triangular solves into efficient dense matrix-vector multiplications.

Figure 4: The moving PML approximation logic used to transition between layers during the sweeping process.

Results and Discussion

The algorithm was benchmarked against several complex 3D velocity models, including the SEG/EAGE Overthrust model, a standard real-world seismic benchmark. Key findings include:

  • Frequency Independence: Iteration counts remain nearly constant ($O(1)$) as frequency increases, provided the model lacks large resonant cavities.
  • Scalability: The implementation demonstrated efficient scaling on up to 2,048 cores. An 8 Hz Overthrust model on an $801 \times 801 \times 187$ grid was solved in under 7.5 minutes.
  • Computational Efficiency: Setup costs were verified at $O(\gamma^2 N^{4/3})$ with application costs at $O(\gamma N \log N)$, outperforming traditional 3D sparse-direct methods.

Conclusion

The parallel sweeping preconditioner, implemented in the open-source PSP and Clique packages, represents a significant advancement in solving high-frequency Helmholtz equations. While highly effective for most geological models, future work will address performance in environments with large resonant cavities and explore extensions to Maxwell’s equations and linear elasticity.

Summary updated

Abstract

A parallelization of a sweeping preconditioner for 3D Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be O({\gamma}^2 N^{4/3}) and O({\gamma} N log N), where {\gamma}({\omega}) denotes the modestly frequency-dependent number of grid points per Perfectly Matched Layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: "Parallel Sweeping Preconditioner (PSP)" and the underlying distributed multifrontal solver, "Clique".
BibTeX
@misc{poulson2012parallel,
  author = {Jack Poulson and Björn Engquist and Sergey Fomel and Siwei Li and Lexing Ying},
  title = {{A parallel sweeping preconditioner for high frequency heterogeneous 3D Helmholtz equations}},
  year = {2012},
  eprint = {1204.0111},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.0111},
}
Figure