"Super Fast Fourier Transforms and Sparse Spectral Methods for Multiscale PDEs"

Olof Runborg
Royal Institute of Technology (KTH)

We discuss a recent algorithm for the discrete Fourier transform of signals that can be well approximated by a sparse Fourier expansion using B terms, where B is much smaller than the signal
length N. The algorithm's complexity is just O(BlogN), i.e. significantly faster than the O(NlogN) complexity of the standard FFT, when N is large.We show how this algorithm can be useful as the main component in a spectral method for PDEs with rapidly varying coefficients.


Back to Long Programs