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.
