Slashdot Mirror

← Back to Stories (view on slashdot.org)

Faster-Than-Fast Fourier Transform

Posted by samzenpus on from the greased-lightning dept.

First time accepted submitter CanEHdian writes "MIT news reports on research done resulting in a Faster-than-fast Fourier Transform algorithm. 'At the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. The new algorithm could be particularly useful for image compression, enabling, say, smartphones to wirelessly transmit large video files without draining their batteries or consuming their monthly bandwidth allotments.'"

12 of 271 comments (clear)

  1. Doesn't sound THAT useful by tempmpi · · Score: 5, Interesting

    It doesn't improve the regular FFT but only sparse variants. Image or Audio compression nearly always uses the regular non-sparse FFT.

    --
    Jan
    1. Re:Doesn't sound THAT useful by MojoRilla · · Score: 5, Informative

      This isn't right. The proposed algorithm is better on sparser signals, but is a regular FFT. The point is that many things we want to compress are sparse, or at least have pieces that are sparse. In JPEG, for example, images are broken into 8x8 pixel blocks and then DCT'ed (which is similar to FFT). Many of those blocks might be sparse, and benefit from this new approach, even if the most complex blocks aren't and don't benefit.

    2. Re:Doesn't sound THAT useful by Anonymous Coward · · Score: 5, Interesting

      I'm only awake due to a bathroom break, so I may not be the most clear-minded at the moment, but subtracting coefficients from the bins seems like a pretty obvious permutation of algorithmic techniques to try, and having 2/3 probability of a correct FT analysis doesn't seem like an inspiring trade-off (skimmed... perhaps they explain ways to improve this?) Is this anything more than a highly specialized, not particularly practical version of the algorithm? I'm used to working on algorithms which are much more general-case (e.g., new solutions for SCALAPACK problems).

  2. Wonder how it'd "work" on cats. by sethstorm · · Score: 5, Funny

    So the cat gets transformed even faster.

    (apologies to XKCD)

    --
    Twitter supports and protects racists - by smearing their critics with the "Hate Speech" label.
  3. Re:Can it be done effectivly without an FPU? by Alex+Belits · · Score: 5, Insightful

    DSP with Arduino

    What is wrong with this picture?

    Processors used in Arduino (Atmel 8-bit AVR series) are minimal, general-purpose microcontrollers, a replacement for earlier PIC microcontrollers. Using them for DSP is only slightly less stupid than building DSP boards entirely out of individual discrete transistors. There is A WHOLE FUCKING CATEGORY OF IC dedicated to DSP, plenty of microcontroller-style yet high-performance SoC suitable for DSP, and FPGA with DSP-specific blocks.

    But noooo, ignorant people such as yourself, would rather recommend the most un-DSP-ish device in the world just because it comes bundled with Java-based IDE that runs on your beloved wiiiiiiiiindows and has the ugliest editor ever written since xedit.

    --
    Contrary to the popular belief, there indeed is no God.
  4. Whoa by HappyClown · · Score: 5, Funny

    Let me get this straight - you're saying you woke up in the middle of the night intending to take a dump, and somehow ended up posting about complex mathematical algorithms on the Internet instead? Respect.

  5. Re:Wish I could understand the details of FFTs by lachlan76 · · Score: 5, Informative

    "Sit down and work out the maths" is really just code for "here's one I prepared earlier". If you're keen on this sort of thing, read a bit about solving systems of linear equations, and you will hopefully be able to look at the problem, exclaim "this is trivial!" and live forever happy in the knowledge that it is indeed theoretically soluble (as I tried to describe above) without having to concern ones self with the computational subtleties that suck all of the fun out of it.

    MIT OCW have a set of videos on linear algebra if your curiosity is sufficient to justify chewing up some time on it. Probably some of the most useful partially-post-high-school maths that one can learn. Here is a free textbook on it.

  6. Re:Potentially huge digital A/V benefits by drinkypoo · · Score: 5, Insightful

    Video encoding doesn't scale well to multiple cores either,

    Welp, that is patently false. Video encoding is embarassingly parallel in any case where video has keyframes and the video is sufficiently long to hand a roughly equal number of chunks of video (keyframe to keyframe) to each core.

    --
    "You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
  7. Comment removed by account_deleted · · Score: 5, Insightful

    Comment removed based on user account deletion

  8. Re:Can it be done effectivly without an FPU? by ThatsLoseNotLoose · · Score: 5, Insightful

    Slashdot could really use a +1 Insightful but Unnecessarily Dickish mod.

  9. Re:Can it be done effectivly without an FPU? by Anonymous Coward · · Score: 5, Funny

    Slashdot could REALLY use a +1 Insightful but Unnecessarily Dickish mod.

  10. Re:Can it be done effectivly without an FPU? by Asmodae · · Score: 5, Informative

    I think the parent is getting at a problem I see at my job fairly frequently. Professional Firmware and DSP developers that have no knowledge about the effects or consequence of their code on the hardware itself. Ultimately re-implementing something that used to run fine in 1/10th the ram, and 1/40th the processor cycles (or less) in a brand new dual core DSP and still can't figure out why they aren't meeting performance requirements. I've seen these guys demand a bigger, faster, more power hungry CPU to run their code when a previous version that was literally a fraction of the capability ran the same algorithm.

    True Story: I'm an FPGA dev, and I was helping out software guys debug why the DSP was completely missing messages and seemed to be dropping data. Turns out doing a thousand lines of heavy DSP INSIDE the interrupt handler is probably going to hang up the CPU and cause it to miss interrupts. The worst part was the blank stares we got when we told them this, and had to explain why that was a bad thing.

    It seems the idea of actually writing good, fast, and power efficient code is a dying art because it's perceived as 'not necessary'. In some instances this thinking is correct (e.g. desktop computers), but in the embedded space where you're trying to keep the cost of final products down and minimize power usage, grabbing the fastest DSP part that TI makes is probably not always the best solution... but it's what you get when you think it's automatically OK/good to 'do everything in software'. There are costs and penalties to account for.

    For pure hobbyists, none of this really applies, but I suspect that a good many of the people that do this stuff as a hobby are also at least tangentially involved in it in some way at their jobs, so it serves to bring up the considerations.