On Wed, 25 Jan 2012 05:58:52 -0600, Marco Leise <[email protected]> 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.
