Abstract

Superfast Fourier transforms.

Ingrid Daubechies
Princeton University
Mathematics

Although the FFT is "Fast" (as its name indicates), its O(NlogN)complexity can still be too slow for truly large, three-dimensional data sets. When the function to be transformed can be well approximated by a sparse Fourier expansion (using B<O(BlogN) complexity bas been constructed by Gilbert, Muthukrishnan, Strauss and various collaborators, that gives the desired result with
high probability. The talk will quickly review the algorithm, present a testbed developed by Jing Zou that studies the dependence on different
parameters of the speed of an implementation of this algorithm, and touch upon preliminary results that indicate how this could be useful
for solving certain types of PDE.