  In this paper we are concerned with fast algorithms for the systems arising
from the plane wave discretizations for two-dimensional Helmholtz equations
with large wave numbers. We consider the plane wave weighted least squares
(PWLS) method and the plane wave discontinuous Galerkin (PWDG) method. The main
goal of this paper is to construct multilevel parallel preconditioners for
solving the resulting Helmholtz systems. To this end, we first build a
multilevel overlapping space decomposition for the plane wave discretization
space based on a multilevel overlapping domain decomposition method. Then,
corresponding to the space decomposition, we construct an additive multilevel
preconditioner for the underlying Helmholtz systems. Further, we design both
additive and multiplicative multilevel preconditioners with smoothers, which
are different from the standard multigrid preconditioners. We apply the
proposed multilevel preconditioners with a {\it constant} coarsest mesh size to
solve two dimensional Helmholtz systems generated by PWLS method or PWDG
method, and we find that the new preconditioners possess nearly stable
convergence, i.e., the iteration counts of the preconditioned iterative methods
(PCG or PGMRES) with the preconditioners increase very slowly when the wave
number increases (and the fine mesh size decreases).

Numerical Analysis