A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods

摘要

Solving time-harmonic wave propagation problems by iterative methods is adifficult task, and over the last two decades, an important research effort hasgone into developing preconditioners for the simplest representative of suchwave propagation problems, the Helmholtz equation. A specific class of thesenew preconditioners are considered here. They were developed by researcherswith various backgrounds using formulations and notations that are verydifferent, and all are among the most promising preconditioners for theHelmholtz equation. The goal of the present manuscript is to show that this class ofpreconditioners are based on a common mathematical principle, and they can allbe formulated in the context of domain decomposition methods called optimizedSchwarz methods. This common formulation allows us to explain in detail how andwhy all these methods work. The domain decomposition formulation also allows usto avoid technicalities in the implementation description we give of theserecent methods. The equivalence of these methods with optimized Schwarz methods translates atthe discrete level into equivalence with approximate block LU decompositionpreconditioners, and we give in each case the algebraic version, including adetailed description of the approximations used. While we chose to use theHelmholtz equation for which these methods were developed, our notation iscompletely general and the algorithms we give are written for an arbitrarysecond order elliptic operator. The algebraic versions are even more general,assuming only a connectivity pattern in the discretization matrix.