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<
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.