FFT in D (using SIMD) and benchmarks

[Robert Jacques]

On Wed, 25 Jan 2012 05:58:52 -0600, Marco Leise <Marco.Leise at gmx.de> wrote:
> If you want to, you can take a look at the link in this forum post:
> http://encode.ru/threads/1461-New-Fast-Fourier-Transform-Algorithm?highlight=FFT
> It looks like MIT has a new FFT algorithm.

For those who want the short version. MIT has developed a faster method of doing a sparse FFT transform. Since many applications (like compression) work by throwing away the 'little' frequencies, those algorithms can get a practical speed-up of ~10x, depending on compression level by switching from the FFT's O(n log n) algorithm to MIT's new O(k log n) algorithm. The new algorithm is still slower for doing all n frequencies, so it's not going to replace all FFT usage, just lossy FFT usage.