A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations |

Introduction

where is the spatially varying wave speed, and is the time-harmonic response to an acoustic wave equation with forcing function . It is important to recognize that is positive-definite and that its combination with the negative-definite term results in an indefinite system.

Before discussing the overall asymptotic complexity of solution techniques, it is helpful to first motivate why high frequency problems require large numbers of degrees of freedom: Given the wave speed bounds , we can define the minimum wavelength as . In order to resolve oscillations in the solution using piecewise polynomial basis functions, e.g., with finite-difference and finite-element methods, it is necessary to increase the number of degrees of freedom in each direction at least linearly with the number of wavelengths spanned by the domain. In order to combat pollution effects (4), which are closely related to phase errors in the discrete solution, one must use asymptotically more than a constant number of grid points per wavelength with standard discretization schemes. Nevertheless, it is common practice to resolve the domain to as few as ten points per wavelength. In any case, piecewise polynomial discretizations require degrees of freedom in dimensions.

Until recently, doubling the frequency of Eq. (1) not only
increased the size of the linear system by at least a factor of
, it also
doubled the number of iterations required for convergence with standard
preconditioned Krylov methods (18,6,17).
Thus, denoting the number of degrees of freedom in a three-dimensional
finite-element or finite-difference discretization as
,
every linear solve required
work with traditional iterative
techniques.
Engquist and Ying recently introduced two classes of *sweeping*
preconditioners for Helmholtz equations without large
cavities (14,15): Both approaches
approximate a block
factorization of the Helmholtz operator in
block tridiagonal form in a manner which exploits a radiation boundary
condition.
The first approach performs a block tridiagonal factorization algorithm in
-matrix arithmetic (25,22),
while the second approach approximates the Schur complements of the
factorization using auxiliary problems with artificial radiation boundary
conditions.
Though the
-matrix sweeping preconditioner has theoretical
support for two-dimensional
problems (14,28),
there is not yet justification for three-dimensional problems.

This paper therefore focuses on the second approach, which relies on multifrontal factorizations (21,27,12,34) of the approximate auxiliary problems in order to achieve an setup cost and an application cost, where denotes the number of grid points used for each Perfectly Matched Layer (PML) (29). While the sweeping preconditioner is competitive with existing techniques even for a single right-hand side, its main advantage is for problems with large numbers of right-hand sides, as the preconditioner appears to converge in iterations for problems without large cavities. Thus, after setting up the preconditioner, typically only work is required for each solution.

A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations |

2014-08-20