Posts Tagged ‘fft’

Faster-than-fast Fourier transform

At the upcoming ACM Symposium on Discrete Algorithms conference, a group of MIT researchers is presenting a new Fourier Transform algorithm that can improve on the now-standard “Fast Fourier Transform” (FFT) algorithm by a full order of magnitude. In the SODA paper, they do this by repeatedly cutting the slice of spectrum into smaller pieces […]