A New Interpolated Pseudodifferential Preconditioner for the Helmholtz Equation in Heterogeneous Media

This paper introduces a new pseudodifferential preconditioner for the Helmholtz equation in variable media with absorption. The pseudodifferential operator is associated with the multiplicative inverse to the symbol of the Helmholtz operator. This approach is well suited for the intermediate and high-frequency regimes. The main novel idea for the fast evaluation of the preconditioner is to interpolate its symbol, not as a function of the (high-dimensional) phase-space variables, but as a function of the wave speed itself. Since the wave speed is a real-valued function, this approach allows us to interpolate in a <i>univariate</i> setting even when the original problem is posed in a multidimensional physical space. As a result, the needed number of interpolation points is small, and the interpolation coefficients can be computed using the fast Fourier transform. The overall computational complexity is log-linear with respect to the degrees of freedom as inherited from the fast Fourier transform. We present some numerical experiments to illustrate the effectiveness of the preconditioner to solve the discrete Helmholtz equation using the GMRES iterative method. The implementation of an absorbing layer for scattering problems using a complex-valued wave speed is also developed. Limitations and possible extensions are also discussed.