A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions

The state-of-the-art, large-scale numerical simulations of the scattering problem for the Helmholtz equation in two dimensions rely on iterative solvers for the Lippmann-Schwinger integral equation, with an optimal CPU time O(m(3) log(m)) for an m-by-m wavelength problem. We present a method to solve the same problem directly, as opposed to iteratively, with the obvious advantage in efficiency for multiple right-hand sides corresponding to distinct incident waves. Analytically, this direct method is a hierarchical, recursive scheme consisting of the so-called splitting and merging processes. Algebraically, it amounts to a recursive matrix decomposition, for a cost of O(m(3)), of the discretized Lippmann-Schwinger operator. With this matrix decomposition, each back substitution requires only O(m(2) log(m)); therefore, a scattering problem with m incident waves can be solved, altogether, in O(m(3) log(m)) flops.