How Speeding The "Most Important Algorithm Of Our Lifetime" Could Change This Modern World

Math breakthroughs don't often capture the headlines—but MIT researchers have just made one that could lead to all sorts of amazing technological breakthroughs that in just a few years will touch every hour of your life.

Last week at the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) a new way of calculating Fast Fourier Transforms was presented by a group of MIT researchers. It's possible that under certain situations it may be up to ten times faster than the current way we do these. At this point you are probably wondering: What the hell is he talking about? Let me explain, because improving these three little letters—FFT—may change your life.

Here's a quickie explainer: Fourier transforms are a mathematical trick to simplify how you represent a complicated signal—say the waves of sound made by speaking. They work by reducing the complex wave pattern to a simple and pretty short list of numbers that, when run through the system again, result in a very good approximation of the original signal. FFTs (Fast Fourier Transforms) are simply a way of making this magic happen in a digital computer, but the combination of math and machine means the FFT has revolutionized science and many industries that have technology at their core. Which is why it's been labeled the "most important algorithm of our lifetime."

How so? Well, here's just one example plucked from an average interaction with our daily tech: You're certainly familiar with a type of image format called JPEG. They're much smaller than other sorts of digital image format, which is why they're used all over web pages like this one (that way less data has to get to your home from the Net speedily). The magic happens because the original complicated digital picture—an array of pixels with color and brightness—is squeezed by some clever math so that the JPEG looks at lot like it, with small errors you normally ignore, but it takes up less memory space. The core bit of this transformation is an FFT, treating the original image as a complicated signal.

Now, you should remember that sound waves, and both picture and video signals, are all handled by processors in your TV, PC, and phone, and that the radio waves that whizz through the air to keep us all connected to the Internet need digital processing too. That's every compressed sound signal that you listen to as an MP3 or similar format, most every image that you snap with your smartphone or DSLR, every image frame in the video you're watching on your TV streamed over the Net, many images—such as those from an MRI—your doctor uses to diagnose your disease and every burst of radio that connects your cell phone to the nearest tower or your PC to its Wi-Fi router.

So calculating FFTs up to ten times faster is a big deal. It means that if you use existing hardware to do the math, it'll be quicker at solving the problem you've set—so you need less compute time to do the task. If you're talking about a portable computer like the one in your smartphone, that means it can spend more time doing other things instead. And with the valuable computing and battery resources of these portable devices under such pressure (you wouldn't want your phone to be laggy now, would you?) that's a good thing.

On the other hand, it also could let you use slower, cheaper computing hardware to do many of the same tasks we use today's hardware to do—meaning the cost could tumble on some everyday objects.

Think about the kind of computer graphics that could be enabled by this innovation: By clever application of FFTs in mobile graphics processors, the kind of 3-D rendering that you're used to on your laptop could appear on your tablet PC. The radar systems that are vital for tech like self-driving cars also rely heavily on FFTs—and a significant speed and efficiency boost could really improve both their accuracy and effectiveness (and possibly price). The trillions of calculations that are used to predict the environment so your weather presenter can deliver you a weekly forecast over your breakfast coffee also rely on this sort of math. Faster calculations means you can do more calculations more effectively, so the weather model accuracy could go up—which also has implications for the kinds of crazy math used in global weather simulations to understand climate damage and global warming.

There are secondary implications too—the new system could lead to new more efficient image, sound, and video compression techniques, which could impact everything from the amount of data you consume monthly by using your smartphone to the quality of video streamed over your digital TV connection at home. Even image and voice recognition systems could get a boost, which may prove vital for the expected robot revolution and how we'll speak to our phones and even TVs soon.

It's almost impossible to scope how enormous an impact this new FFT technique could have. To give you a similar example of how a subtle math innovation like this can impact real world innovations, look at the stealth fighter and the stealth bomber. When the F117 fighter was being designed in the 1970s, we understood the technique to design it to be invisible to radar, but the computer power simply wasn't available to run the algorithms (which certainly employed FFTs) to high levels of detail. That's why the F117 is faceted and oddly shaped—which impacted its design and maneuverability. Just a handful of years later, when the B2 stealth bomber was in design our math had improved and so had our computing power, and thus the B2 is actually stealthier than its much smaller cousin, and has that incredibly smooth aerodynamic shape.

[Image: Flickr user hazure]

• Hi Kit

I've just started researching data compression technology, as an arts graduate its brain frying! Am I right in thinking that there are no companies in the U.K making headway in this field?

Michelle Porter

• But is the FFT actually mathematically correct when applied to sampled data? The answer would seem to be no because of the need to do windowing and such. Does it make more sense to fit the data using evolutionary methods for example?

• Was it necessary to take this subject into weaponry?

Hate to beat a dead horse (WISH he were a dead horse) but once mused over a short story dealing with an engineer and George Bush. The engineer was walking the parking lot at 3 am listening to the crunch, crunch of his footsteps on crispy snow. The sound was quieting and comforting, the lone sound bouncing off nearby office buildings. As he searched for the right key to his car he looked up at the lights still on in isolated offices - other engineers still working their designs and formulas. He had worked long, dedicated hours but others were still at it - watching the clock was a distant concept.

As he looked down at his car keys a discarded newspaper caught his eye. The byline - Bush never heard of Sunni and Shia.

Bush thought there were only Muslims. A short list of two items. TWO. Bush couldn't give enough attention to an issue that would crush his designs for Iraq and the Middle East to ponder and learn a list of two.

Millions upon millions of dedicated manhours given to designing the machinery of defense and the final product is given over to a Decider that cannot be bothered to contemplate a list of two items.

• The election of GW Bush was a revolution by the people of the US and an emphatic rejection of many prior ideals.

• You are an idiot. So is your current president. You both need to crawl back into your holes.

•  might be a lame story but I don't know if it qualifies as 'idiot' but you sure qualify as a jackass

• My preference would be that with faster calculations, rather than speedier computing (though I wouldn't mind that, naturally), the end result of image and sound quality will be improved 10x.  MP3s do the trick in a more-or-less passable way, but I wouldn't mind filling my phone up with 24bit/192khz sound files and family photos comprable to RAW file format that take up that same room as current MP3s and JPGs. And I want it all to run 10x faster. And I want this all on a spaceship.

• yeah! ULTRA High Definition NOW! (perhaps Sony and Microsoft are already negotiating with MIT's people (in order to include this ins their new consoles!)

• Very interesting. But I'm not sure it will translate to 3d, they are different types of transformations. For JPEG and MP3 - ok - BUT - and it's a big BUT - these take up only a small fractions of today's processor power. Even on a mobile. So the impact will not be anywhere like as big as is being suggested. More important is power management. Had this idea come a decade earlier it would have been a lot different. Whether it has any other applications we will have to wait and see.

• This method is not a new way to compute the Fast Fourier Transform.  Rather, it's an entirely new algorithm that is applicable in certain specialized cases.  It is, however, a new optimization for computing a Discrete Fourier Transform, which is what I believe the author meant.