Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The faster-than-fast Fourier transform

web.mit.edu

Post reply on HN
Print view View original

11–20 of 33 posts

Re: The faster-than-fast Fourier transform

#11

Post by mitmatt »

mjb wrote: post #5

Spare 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 F…

They actually point out a specific comparison to FFTW in the paper: their "preliminary implementation" is faster than FFTW for n=2^22 and kI don't know how to estimate what values of n would be relevant for today's applications, but n=2^22≈4M doesn't seem like such a big number for images or video (if signal length roughly corresponds to number of pixels). Any thoughts?

Re: The faster-than-fast Fourier transform

#12

Post by rasur »

Interesting. I've a friend in Australia who's been doing some work analysing rainfall using arrays of wire across long distances (details somewhere here: http://wiredlab.org/), and during a recent conversation he pointed me at this paper: http://www.icita.org/icita2004/abstracts/128-5.htm which seems to use another method (involving Primes) for calculating Fourier Transforms, and claims a 95% speed up.

Sadly I haven't had a chance to look into it in any great detail yet, although it's "in the queue" of things to poke at. I thought it worth pointing out in case anyone else might find it useful.

Re: The faster-than-fast Fourier transform

#13

Post by te_platt »

mafribe wrote: post #7
pygy_ wrote: post #3

Today'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...

Or here for no fee.

http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf

As a Gauss fanboy let me just say wow. Especially note that from 1828 to 1965 there a various versions of the FFT presented for special cases but Gauss had the complete version in 1805.

Re: The faster-than-fast Fourier transform

#14

Post by astrange »

As usual the article misrepresents video compression. Almost l useful coding tools are spatial and not frequency based; the only famous one (DCT) was replaced with a rough approximation in H.264 and it works just as well.

This is because lots of realistic images don't really have meaningful frequency-based content. (imagine sampling every 8 or 16 pixels - would their values be in any way related to each other?)

Re: The faster-than-fast Fourier transform

#16

Post by Geee »

There's lots of things you can do with practical algorithms when you start thinking data-first approaches and try to fit the optimizations to the probability distribution of the data, i.e. fastest path for the most probable or important input and vice versa. Many approximations are based on the idea of ignoring input data which is improbable or has little effect on the outcome, and can be quite safely pruned out early.

Re: The faster-than-fast Fourier transform

#17

Post by dmarquis »

pygy_ wrote: post #3

Today'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.

Not to detract from Gauss' remarkable discovery but there is no relation between Gauss' FFT algorithm and the continuous Fourier transform that Fourier discovered. It is also worth mentioning that credit for the discrete Fourier transform goes to Vandermode and pre-dates Gauss' FFT algorithm by about 30 years.

Re: The faster-than-fast Fourier transform

#18

Post by edge17 »

Geee wrote: post #16

There's lots of things you can do with practical algorithms when you start thinking data-first approaches and try to fit the optimizations to the probability distribution of the data, i.e. fastest path for the most probable or important input and vice versa. Many approximations are based on the idea of ignoring input data which is improbable or has little effect on the outcome, and can be quite safely pruned out earl…

Or as they say in computer architecture 101, optimizing for the common case :)

Re: The faster-than-fast Fourier transform

#19

Post by pbhjpbhj »

brlewis wrote: post #4

Is the algorithm patented?

Mathematical methods (as such!) are a specific exclusion in Europe (EPC 52(2) &(3)).

Of course that as such gives you somewhere to hang your patent application if you can afford the patent lawyers fees to protect the monopoly.

Re: The faster-than-fast Fourier transform

#20

Post by brlewis »

pbhjpbhj wrote: post #19
brlewis wrote: post #4

Is the algorithm patented?

Mathematical methods ( as such !) are a specific exclusion in Europe (EPC 52(2) &(3)). Of course that as such gives you somewhere to hang your patent application if you can afford the patent lawyers fees to protect the monopoly.

Mathematical methods are excluded in the U.S. too by case law (Benson, Flook, Diehr). But "law" in terms of what's on the books and "law" in terms of what happens when you go to court are two different things.
Post reply on HN