Lecturer: L. Demanet18-22 August 2014
Title
Fast Multipole Methods and Butterfly Algorithms
Outline
The lectures will cover the high-frequency generalizations of the fast multipole and H-matrix methods.
-
nonuniform direct and inverse fast Fourier transform
-
the box separation (admissibility) criterion in the high-frequency case
-
the FMM seen from the point of view of interpolation and projection operators
-
the butterfly algorithmic architecture as an extension of H-matrices
-
applications to BIE and high-resolution imaging (MRI, CT, and synthetic aperture radar.)
Exercises
References
-
B. Engquist, L. Ying, Fast directional multilevel computation for oscillatory
kernels, SIAM J. Sci. Comput. 29(4), 1710-17372
-
E. Candes, L. Demanet, L. Ying, A Fast Butterfly Algorithm for the Computation of Fourier
Integral Operators,
Multiscale Model. Simul., 7(4), 1727-1750
-
L. Demanet's (incomplete) lecture notes on fast algorithms: pdf file