L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation

Matthias Taus, Leonardo Zepeda-Núñez, Russell J. Hewett, Laurent DemanetJournal of Computational Physics 2020 · DOI

TL;DR

This paper introduces "L-Sweeps," a novel parallel algorithm for efficiently solving the high-frequency Helmholtz equation. It achieves optimal parallel scalability by employing a checkerboard domain decomposition and a new sweeping strategy, making it a significant advancement for modeling wave propagation in complex media.

What Problem Does This Paper Address?

The Helmholtz equation is fundamental to modeling wave phenomena in various fields, including geophysics and electromagnetics. However, solving this equation at high frequencies presents a significant computational challenge. As frequencies increase, the discrete systems become ill-conditioned, making traditional solvers inefficient. Existing methods, like domain decomposition, struggle with parallel scalability for a single right-hand side due to the inherently sequential nature of wave propagation. This paper addresses the need for a truly scalable and parallel solver that can handle these high-frequency problems efficiently.

Methods

The core innovation is the "L-Sweeps" algorithm, which departs from traditional layered domain decompositions. Instead, it utilizes a checkerboard domain decomposition (CDD) and a novel sweeping strategy. This approach allows information to propagate in 90-degree cones, enabling more efficient parallel processing. The method extends accurate transmission conditions to CDDs and introduces a sweeping strategy that decouples subdomains at wave fronts, allowing for parallel computation. The algorithm is interpreted as an approximate block-LU factorization, where parallelism arises from the block-diagonal structure of the diagonal blocks. The authors also employ Perfectly Matched Layers (PMLs) for absorbing boundary conditions and a finite-difference discretization.

Datasets

Not discussed in the paper. The paper focuses on numerical examples generated by the authors to test their algorithm.

Key Insights and Ideas

  • Checkerboard Domain Decomposition (CDD): Moving away from layered decompositions to a CDD is key to unlocking new parallelism. This allows for information propagation in 90-degree cones, which is more amenable to parallelization than the traditional 180-degree propagation.
  • L-Sweeps Strategy: The new sweeping strategy efficiently tracks wave fronts by decoupling subdomains, enabling parallel processing. This is a significant departure from previous sweeping methods.
  • Optimal Parallel Scalability: The L-Sweeps algorithm achieves optimal parallel scalability, meaning the computational time scales linearly with the number of processors for a fixed problem size. This is a major breakthrough for high-frequency Helmholtz solvers.
  • Trade-off between PML Thickness and Effectiveness: The paper highlights a crucial trade-off: while thinner PMLs are desirable for computational efficiency, they can reduce the effectiveness of the preconditioner. Maintaining a sufficient PML thickness (around 2 wavelengths) is essential for achieving good performance.

Key Results

The L-Sweeps algorithm demonstrates optimal parallel scalability with a computational complexity of $O((N/p) \log \omega)$, where $N$ is the total number of degrees of freedom, $p$ is the number of processors, and $\omega$ is the frequency. This complexity holds for both two- and three-dimensional problems. Numerical experiments show that the number of GMRES iterations required to solve the preconditioned system grows logarithmically with frequency ($\log \omega$), indicating the effectiveness of the preconditioner. The method successfully handles problems with constant, smooth, and discontinuous wave speeds, although performance can be affected by a high number of reflections.

Limitations and Future Work

The authors acknowledge that the performance of the L-Sweeps preconditioner can deteriorate in the presence of excessive reflections and refractions, particularly in problems with resonant cavities. They suggest that sweeping strategies might not be the ideal approach for such scenarios and propose this as a topic for future research. Additionally, the paper mentions that for three-dimensional problems, further parallelism can be exploited by using multi-frontal methods for the quasi-one-dimensional local problems, potentially achieving an almost $O(n)$ parallel complexity. The authors also suggest investigating processor assignments tailored to heterogeneous parallel environments for further efficiency gains.

Summary updated

BibTeX
@article{taus2020l,
  author = {Matthias Taus and Leonardo Zepeda-Núñez and Russell J. Hewett and Laurent Demanet},
  title = {{L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation}},
  journal = {Journal of Computational Physics},
  year = {2020},
  doi = {10.1016/j.jcp.2020.109706},
}
Figure