HPC in the Cloud: MIT Researchers Speed Up FFT Algorithm

Dedicated to covering high-end cloud computing
in science, industry and the datacenter

Translation Disclaimer

Subscribe | Sign In

January 18, 2012

MIT Researchers Speed Up FFT Algorithm

CAMBRIDGE, Mass., Jan. 18 -- 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. 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.

Like the FFT, the new algorithm works on digital signals. A digital signal is just a series of numbers — discrete samples of an analog signal, such as the sound of a musical instrument. The FFT takes a digital signal containing a certain number of samples and expresses it as the weighted sum of an equivalent number of frequencies.

“Weighted” means that some of those frequencies count more toward the total than others. Indeed, many of the frequencies may have such low weights that they can be safely disregarded. That’s why the Fourier transform is useful for compression. An eight-by-eight block of pixels can be thought of as a 64-sample signal, and thus as the sum of 64 different frequencies. But as the researchers point out in their new paper, empirical studies show that on average, 57 of those frequencies can be discarded with minimal loss of image quality.

Heavyweight division

Signals whose Fourier transforms include a relatively small number of heavily weighted frequencies are called “sparse.” The new algorithm determines the weights of a signal’s most heavily weighted frequencies; the sparser the signal, the greater the speedup the algorithm provides. Indeed, if the signal is sparse enough, the algorithm can simply sample it randomly rather than reading it in its entirety.

“In nature, most of the normal signals are sparse,” says Dina Katabi, one of the developers of the new algorithm. Consider, for instance, a recording of a piece of chamber music: The composite signal consists of only a few instruments each playing only one note at a time. A recording, on the other hand, of all possible instruments each playing all possible notes at once wouldn’t be sparse — but neither would it be a signal that anyone cares about.

The new algorithm — which associate professor Katabi and professor Piotr Indyk, both of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), developed together with their students Eric Price and Haitham Hassanieh — relies on two key ideas. The first is to divide a signal into narrower slices of bandwidth, sized so that a slice will generally contain only one frequency with a heavy weight.

In signal processing, the basic tool for isolating particular frequencies is a filter. But filters tend to have blurry boundaries: One range of frequencies will pass through the filter more or less intact; frequencies just outside that range will be somewhat attenuated; frequencies outside that range will be attenuated still more; and so on, until you reach the frequencies that are filtered out almost perfectly.

If it so happens that the one frequency with a heavy weight is at the edge of the filter, however, it could end up so attenuated that it can’t be identified. So the researchers’ first contribution was to find a computationally efficient way to combine filters so that they overlap, ensuring that no frequencies inside the target range will be unduly attenuated, but that the boundaries between slices of spectrum are still fairly sharp.

Zeroing in

Once they’ve isolated a slice of spectrum, however, the researchers still have to identify the most heavily weighted frequency in that slice. In the SODA paper, they do this by repeatedly cutting the slice of spectrum into smaller pieces and keeping only those in which most of the signal power is concentrated. But in an as-yet-unpublished paper, they describe a much more efficient technique, which borrows a signal-processing strategy from 4G cellular networks. Frequencies are generally represented as up-and-down squiggles, but they can also be though of as oscillations; by sampling the same slice of bandwidth at different times, the researchers can determine where the dominant frequency is in its oscillatory cycle.

Two University of Michigan researchers — Anna Gilbert, a professor of mathematics, and Martin Strauss, an associate professor of mathematics and of electrical engineering and computer science — had previously proposed an algorithm that improved on the FFT for very sparse signals. “Some of the previous work, including my own with Anna Gilbert and so on, would improve upon the fast Fourier transform algorithm, but only if the sparsity k” — the number of heavily weighted frequencies — “was considerably smaller than the input size n,” Strauss says. The MIT researchers’ algorithm, however, “greatly expands the number of circumstances where one can beat the traditional FFT,” Strauss says. “Even if that number k is starting to get close to n — to all of them being important — this algorithm still gives some improvement over FFT.”

-----

Source: Larry Hardesty, MIT News Office

Share Options

Subscribe

Subscribe to HPC in the Cloud

Discussion

There are 0 discussion items posted.

Join the Discussion

Become a Registered User Today!

Registered Users Log in join the Discussion

RSS Feeds

Feeds by Topic

Feeds by Content Type

Subscribe to All Content

All

May 16, 2012

May 15, 2012

May 14, 2012

May 11, 2012

AWS, SAP Announce Certification of AWS Infrastructure for SAP Business All-in-One Solutions

May 10, 2012

May 09, 2012

May 08, 2012

May 07, 2012

Feature Articles

Cloud Services Satisfy a Higher Calling

Higher education involves many collaborative projects that lend themselves to cloud services, however often those services are not tailored to the uniqueness of an academic environment. That's where the Internet2 NET+ project comes in. By partnering with 16 major cloud providers, the networking consortium is seeking to expedite the delivery of cloud services and by doing so advance research and innovation in the United States.
Read more...

Univa CEO Gary Tyreman on the Evolution of HPC, Big Data and Cloud

It's been a little over a year since Univa took over stewardship of the open source workload manager and acquired the founding Sun Grid Engine team from Oracle, and the company just announced its third production release. CEO Gary Tyreman discusses the latest enhancements as well as the company's plans around cloud, big data and the enterprise.
Read more...

Read more HPC in the Cloud features...

Around the Web

Breaking the Cloud Barrier

May 15, 2012 | New Microsoft report shows that beyond the expected financial benefits, cloud services may offer more comprehensive security features compared to in-house IT operations.
Read more...

Vendors Demo Next-Gen Sequencing Platforms for Pharma

May 14, 2012 | During the second annual Pistoia Alliance conference, three teams demonstrated their newly-implemented cloud-based next-generation sequencing platforms.
Read more...

Zunicore Offers Bare Metal by the Hour

May 10, 2012 | PEER1's cloud division, Zunicore, will soon be offering GPU-equipped servers on-demand.
Read more...

US Cloud Providers Struggle With Data Privacy Laws

May 08, 2012 | The Patriot Act leads foreign governments to question the security of US cloud services.
Read more...

Genomic Data Gets Comfy in the Cloud

May 07, 2012 | Startup DNANexus is helping to bring personalized medicine to the masses with its cloud-based next-gen sequencing platform.
Read more...

Read more headlines...

Appro White Paper: Enabling Performance-per-Watt Gains in HPC

04/05/2012 | Appro | Designed to meet the growing global demand for HPC solutions, Appro's Xtreme-X™ Supercomputer delivers superior performance-per-watt and reduced I/O latency while bringing significant flexibility to HPC workload configurations including capacity, hybrid, data intensive and capability computing.

Exploring the Potential of Heterogeneous Computing

04/02/2012 | AMD | Developers today are just beginning to explore the potential of heterogeneous computing, but the potential for this new paradigm is huge. This brief article reviews how the technology might impact a range of application development areas, including client experiences and cloud-based data management. As platforms like OpenCL continue to evolve, the benefits of heterogeneous computing will become even more accessible. Use this quick article to jump-start your own thinking on heterogeneous computing.