Sparse Fast Fourier Transform, The fasterthanfast Fourier transform 
Sparse Fast Fourier Transform, The fasterthanfast Fourier transform 
Feb 10 2012, 19:55
Post
#1


Group: Members Posts: 8 Joined: 27November 09 From: Argentina Member No.: 75344 
Hello.
I don't know if this topic was already mentioned here (I wasn't able to find it). Somebody here could find it interesting: MIT news article: The fasterthanfast Fourier transform sFFT web page: sFFT: Sparse Fast Fourier Transform Best regards. Omar 


Sep 23 2012, 00:25
Post
#2


Group: Members Posts: 22 Joined: 14January 12 Member No.: 96431 
I'm just wondering if any power savings are expected to be significant in typical consumer uses...phones, tablets etc or in more general scientific and engineering computation? Probably not. The FFT isn't really the bottleneck in anything consumers do that I can think of. Yes, video and audio codecs often use them, but they're usually only a small part of the entire codec time, and for these applications approximations to the FFT are already available. I didn't look at the math but my guess is that something like this becomes more useful for very large FFT sizes or for more then 1 or 2 dimensional transforms. Science, engineering and maybe telcom applications might be a completely different story though. Well, on Rockbox at least the FFT part of decoding can take up to 50% of CPU time (http://www.rockbox.org/wiki/FasterMDCT). It's true that audio decoding is not really that much CPU intensive, but video encoding/decoding probably is another mater. 


Sep 23 2012, 00:30
Post
#3


Group: Members Posts: 5528 Joined: 2September 02 Member No.: 3264 
Well, on Rockbox at least the FFT part of decoding can take up to 50% of CPU time (http://www.rockbox.org/wiki/FasterMDCT). Well it did until stripwax, mt and I rewrote it using a modern, efficient split radix FFT. Now its quite a bit faster. It's true that audio decoding is not really that much CPU intensive, but video encoding/decoding probably is another mater. Sure, but the DCT is usually only a pretty small portion of that. And of course you can already use approximations if you want (though usually people don't since its not very slow to begin with). 


LoFi Version  Time is now: 28th July 2015  15:01 