  The paper introduces the sweeping preconditioner, which is highly efficient
for iterative solutions of the variable coefficient Helmholtz equation
including very high frequency problems. The first central idea of this novel
approach is to construct an approximate factorization of the discretized
Helmholtz equation by sweeping the domain layer by layer, starting from an
absorbing layer or boundary condition. Given this specific order of
factorization, the second central idea of this approach is to represent the
intermediate matrices in the hierarchical matrix framework. In two dimensions,
both the construction and the application of the preconditioners are of linear
complexity. The GMRES solver with the resulting preconditioner converges in an
amazingly small number of iterations, which is essentially independent of the
number of unknowns. This approach is also extended to the three dimensional
case with some success. Numerical results are provided in both two and three
dimensions to demonstrate the efficiency of this new approach.
