Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation

Many applications lead to large systems of linear equations with dense matrices. Direct matrix-vector products become prohibitive, since the computational cost increases quadratically with the size of the problem. By exploiting specific kernel properties fast algorithms can be constructed.A directional multilevel algorithm for translation-invariant oscillatory kernels of the type K(x, y) = G(x − y)eık∣x−y∣, with G(x − y) being any smooth kernel, will be presented. We will first present a general approach to build fast multipole methods (FMMs) based on Chebyshev interpolation and the adaptive cross approximation (ACA) for smooth kernels. The Chebyshev interpolation is used to transfer information up and down the levels of the FMM. The scheme is further accelerated by compressing the information stored at Chebyshev interpolation points using ACA and QR decompositions. This leads to a nearly optimal computational cost with a small pre-processing time due to the low computational cost of ACA. This approach is in particular faster than performing singular value decompositions.This does not address the difficulties associated with the oscillatory nature of K. For that purpose, we consider the following modification of the kernel Ku = K(x, y)e−ıku·(x−y), where u is a unit vector (see Brandt [1]). We proved that the kernel Ku can be interpolated efficiently when x − y lies in a cone of direction u. This result is used to construct an FMM for the kernel K.Theoretical error bounds will be presented to control the error in the computation as well as the computational cost of the method. The paper ends with the presentation of 2D and 3D numerical convergence studies, and computational cost benchmarks.