Special SSO Seminar - Leslie Greengard, NYU - “Adaptive, multilevel, Fourier-based fast transforms”

The last few decades have seen the development of a variety of fast algorithms for computing convolutional transforms - that is, evaluating the fields induced by a collection of sources at a collection of targets, with an interaction specified by some radial function (such as the 1/r kernel of gravitation or electrostatics).

The earliest such scheme was Ewald summation, which relies on Fourier analysis for its performance and is best suited for uniform distributions of sources and targets. To overcome this limitation, approximation-theory based algorithms emerged,
which organized the sources and targets on an adaptive tree data structure. By carefully separating source and target clusters at each length scale in the spatial hierarchy, linear scaling methods were developed to compute all pairwise interactions, more or less independent of the statistics of the distribution of points. (The fast multipole method is one such scheme.)

In this talk, we introduce a new class of methods for computing fast transforms that can be applied to a broad class of kernels, from the Green’s functions for constant coefficient partial differential equations to power functions and radial basis functions such as those used in statistics and machine learning. The DMK (dual-space multilevel kernel-splitting) framework combines features from fast multipole methods, Ewald summation, multilevel summation methods and asymptotic analysis to achieve speeds comparable to the FFT in work per gridpoint, even in a fully adaptive context. We will discuss both the algorithm and some of its applications to physical modeling in complex geometry. This is joint work with Shidong Jiang.