The faster-than-fast Fourier transform
web.mit.edu
The faster-than-fast Fourier transform
1–10 of 33 posts
Re: The faster-than-fast Fourier transform
#2I guess this is the project page, also contains the papers and some benchmarks:
Re: The faster-than-fast Fourier transform
#3Today's pedantic minute is sponsored by Carl Friedrich Gauss.
The FFT algorithm was rediscovered in the 60's. Gauss discovered it in the early 19th century while studying the phase of the moon, before Fourier described his transform. He published it in latin, and the text was lost until 1984.
Re: The faster-than-fast Fourier transform
#4Is the algorithm patented?
Re: The faster-than-fast Fourier transform
#5Spare transforms like this are very interesting, and these seem like some very good performance results. It's worth noting, though, that FFTW (http://www.fftw.org/) is still much faster on the sizes of transforms that many (most?) applications do - less than 2^15 or so entries. Also, as the number of non-zero frequencies climbs, sparse algorithms very quickly get overtaken by good implementations of more standard FFT algorithms.
Still, very cool stuff.
Re: The faster-than-fast Fourier transform
#6Paper: http://arxiv.org/pdf/1201.2501v1
It starts by dividing the spectrum into frequency bins, and assumes that there is usually 0 or 1 non-zero coefficients in each bin. It wasn't clear to me what happens when a large number of non-zero coefficients are clustered together in one bin. Can O(k log n) still be achieved when most frequencies are clustered?
Re: The faster-than-fast Fourier transform
#7Today's pedantic minute is sponsored by Carl Friedrich Gauss. The FFT algorithm was re discovered in the 60's. Gauss discovered it in the early 19th century while studying the phase of the moon, before Fourier described his transform. He published it in latin, and the text was lost until 1984.
You can find descriptions of the FFT algorithm's history in [1, 2]. Both are available for free only for subscribers, sorry.
[1] http://www.springerlink.com/content/j30x8k122v828w87
[2] http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1162...
Re: The faster-than-fast Fourier transform
#8Today's pedantic minute is sponsored by Carl Friedrich Gauss. The FFT algorithm was re discovered in the 60's. Gauss discovered it in the early 19th century while studying the phase of the moon, before Fourier described his transform. He published it in latin, and the text was lost until 1984.
Gauss again!
Re: The faster-than-fast Fourier transform
#9For the plain ol' FFT, I've found the "Fastest Fourier in the West": http://www.fftw.org/ to be an excellent library, which implements a whole bunch of different solvers, and picks the appropriate ones to use for your data.
Hopefully this new algorithm can be added to their toolbox in the future.
Re: The faster-than-fast Fourier transform
#10[deleted]