Fast Multipole Method with Complex Coordinates

Abstract

When solving problems of potential theory in unbounded layered media, recently developed integral equation methods rely on coordinate complexification to permit truncation of the computational domain while retaining high order accuracy. As a result, classical fast multipole methods (FMMs) cannot be used to accelerate the evaluation of layer potentials. In this paper, we present a variant of the FMM which applies when the source and target locations have complex coordinates in two and three dimensions. This complex coordinate FMM is based on the analytic continuation of the various special function identities used in the real-space setting. To achieve the same linear-time complexity as in the classical FMM, we construct a hierarchical tree based solely on the real parts of the complex point locations and derive convergence rates for truncated expansions when the imaginary parts of the locations depend Lipschitz-continuously on the corresponding real parts. We demonstrate the efficiency of our approach through several numerical examples and illustrate its application to solving large-scale linearized water wave problems and Helmholtz transmission problems.