red bullet all things design

January 2012

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.

Algorithm image



Last week at the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) a new Fast Fourier Transform algorithm 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 digital camera, 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.

Reprinted with some small edits from a Fast Company article written by Kit Eaton entitled “How Speeding The “Most Important Algorithm Of Our Lifetime” Could Change This Modern World – because he wrote it much better than I could.

‘til next time, take care.
Bob

 

Insert your comment

Author Name (required):

Author Web Site:

Comment (required):

Please Type In Secure Code:

archives

red bulletall things design - Oct 2009 - What is Design?

red bulletall things design - Nov 2009 - Form & Function
red bulletall things design - Dec 2009 - Juices Flowing
red bulletall things design - Dec 2009 - Wrapping It Up
red bulletall things design - Jan 2010 - Green-er in 2010
red bulletall things design - Feb 2010 - Graphics Tools
red bulletall things design - Mar 2010 - Smart Marketing
red dotall things design - Apr 2010 - Adobe CS5
red bulletall things design - Jun 2010 - Print Obsolete?
red bulletall things design - Aug 2010 - New Publishing
red bulletall things design - Sep 2010 - Masters of Design
red bulletall things design - Nov 2010 - Adobe MAX
red bullet2009-2010 Holiday Image
red bulletall things design - Dec 2010 - Technology 2011
red bulletall things design - Feb 2011 - Websites to Die For

red bulletall things design - Mar 2011 - 4G Ready?
red bulletall things design - Apr 2011 - Google Art Project
red bulletall things design - Jun 2011 - Plenoptic Lenses
red bulletall things design - Oct 2011 - Adobe MAX

 

check this out

Here is another article about MIT's breakthrough algorithm, this time from Popular Science.

 

Massachusetts Institute of Technology's (MIT) online newsletter does a fairly good job of reporting on the new algorithm without spinning your head too much.

 

If you understand what a Discrete Fourier Transform is and math is your thing or if you just want experience an acute case of wtf, this site is for you.

 

Here is a geeky look at a practical application of FFT - the analysis of sound; the wails of London police whistles.

Think you've seen everything on YouTube? How about a tutorial on Fast Fourier Transform!

 

If you are interested in the physics of sound then this tutorial by Bartosz Milewski is for you.

 

Don't let the title "Simple FFT and Filtering Tutorial..." fool you; the first couple of paragraphs seem simple but then it falls off the deep end.

 

Here is the Engineering Joke of the Day about Fourier Transform:
Q: What did the Fourier transform of the arbitrary signal say to the Fourier transform of the sinc function?
A: "You're such a square!"

 

Explanation - The sinc function, sinc(x) = (sin x)/x, has Fourier transform typically called a "rectangle" function, which looks like a single cycle of a square wave. If the constants are all picked properly, it is a square.
GOT IT?