The faster-than-fast Fourier transform

For a large range of practically useful cases, MIT researchers find a way to increase the speed of one of the most important algorithms in the information sciences. The Fourier transform is one of the most fundamental concepts in the information sciences. It's a method for representing an irregular signal - such as the voltage fluctuations in the wire that connects an MP3 player to a loudspeaker - as a combination of pure frequencies. It's universal in signal processing, but it can also be used to compress image and audio files, solve differential equations and price stock options, among other things. The reason the Fourier transform is so prevalent is an algorithm called the fast Fourier transform (FFT), devised in the mid-1960s, which made it practical to calculate Fourier transforms on the fly. Ever since the FFT was proposed, however, people have wondered whether an even faster algorithm could be found. 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.