![]() |
![]() |
![]() |
![]() | A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations | ![]() |
![]() |
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 | ![]() |
![]() |