L-sweeps: A scalable parallel high-frequency Helmholtz solver

Abstract

We present the first fast solver for the high-frequency Helmholtz equation that scales optimally in parallel, for a single right-hand side. The L-sweeps approach is based on the well-established method of polarized traces, but considers a checkerboard domain decomposition instead of a layered decomposition. In particular, we extend the notion of accurate transmission conditions to checkerboard domain decompositions and introduce a new sweeping strategy. The progression of a wave is still captured in a single sweep, and the notion of accurate transmission conditions is properly extended to this context. This precaution effectively decouples the cells at the front of the sweep, and results in a much more favorable parallel performance than previously published in the literature. The method has an overall O(N log^2 w/p) empirical runtime for N=n^d total degrees-of-freedom in a d-dimensional problem, frequency w, and p~n processors. We introduce the algorithm and provide a complexity analysis for our parallel implementation of the solver. We corroborate all claims considering several two- and three-dimensional numerical examples involving constant, smooths, and discontinuous wave speeds.