Fast integral equation methods and the DMK framework

Shidong Jiang (Center for Computational Mathematics, Flatiron Institute, Simons Foundation)

In this talk, we will first present an overview of fast integral equation methods (FIEMs). Fast algorithms, such as the fast multipole methods and their descendants, have made profound impacts on many areas of scientific computing. Boundary integral equations of the second kind are the natural formulation for boundary value problems of elliptic partial differential equations due to the reduction of dimensionality by one, automatic satisfaction of conditions at infinity for exterior and scattering problems and well conditioning. The computational bottleneck that arises because the resulting linear system is dense due to the nonlocal and long-range nature of integral operators is largely removed by fast algorithms. FIEMs have been highly successful in solving a large class of problems in fluid mechanics, elasticity, acoustics and electromagnetics.

Second, we introduce a new class of multilevel, adaptive, dual-space methods for computing fast convolutional transforms. The DMK (dual-space multilevel kernel-splitting) framework uses a hierarchy of grids, computing a smoothed interaction at the coarsest level, followed by a sequence of corrections at finer and finer scales until the problem is entirely local, at which point direct summation is applied. Unlike earlier multilevel summation schemes, DMK exploits the fact that the interaction at each scale is diagonalized by a short Fourier transform, permitting the use of separation of variables without relying on the FFT. The DMK framework substantially simplifies the algorithmic structure of the fast multipole method (FMM) and unifies the FMM, Ewald summation and multilevel summation, achieving speeds comparable to the FFT in work per grid point, even in a fully adaptive context.