H J Gay Lecture
Friday, April 5th, 2024
11:00am
Salisbury Labs 406
Speaker: Leslie Greengard, Professor, Courant Inst. of Mathematical Sciences (NYU), Director, Center for Computational Mathematics, Flatiron Institute (Simons Found.)
Title: Adaptive, multilevel, Fourier-based fast transforms
Abstract: 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 organize 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.
On demand video link of talk https://echo360.org/media/67fb6fe8-1822-4bf6-a6e7-1eff7eb0b8ff/public