Annual Report 2019

Making a Fast Computational Tool Even Faster

Center for Computational Mathematics

Alex Barnett takes a small silver tuning fork from his backpack, thwacks it against his desk and holds it to a microphone. On his computer, the musical tone appears as a steady succession of identical sine waves.

“It’s an A4, or the A above middle C,” says Barnett, who plays classical and jazz piano in addition to serving as group leader for numerical analysis at the Flatiron Institute’s Center for Computational Mathematics (CCM). “That’s 440 hertz, or 440 oscillations per second.”

A chord — with multiple notes — struck on a piano, however, would yield a distinctly different pattern. Instead of a monotonous series of rises and falls, the microphone would record a mountain range of varying canyons, peaks and plateaus. The various frequencies that make up a chord stack on top of each other, amplifying each other or canceling each other out in different places. This so-called ‘wave interference’ is what produces the complex signal.

Untangling the many waves that make up such complex signals appears daunting at first. Thankfully, mathematicians and scientists have the Fourier transform. Invented by Joseph Fourier in 1822, the function takes a signal and churns out a graph with spikes at the signal’s constituent frequencies. For instance, a Fourier transform could reveal that a given chord comprises an A (440 hertz), a C-sharp (277 hertz) and an E (330 hertz).

Adding two waves (top and middle) together can result in a complex signal (bottom). An algorithm known as the fast Fourier transform can decipher the wave frequencies that make up such complex signals. The algorithm, though, only works when the signal is evenly sampled along a uniform grid.

The Fourier transform has far more uses than just deconstructing harmonies. The transform is used in everything from medical imaging to quantum mechanics to image compression. At the CCM, Barnett and his colleagues have developed and released a new set of software libraries to tackle a thornier subset of applications known as non-uniform discrete Fourier transforms. The software is called the Flatiron Institute Nonuniform Fast Fourier Transform, or FINUFFT, and for many tasks it’s faster than anything else available.

“Tool building is a big part of what CCM is doing, and the Flatiron Institute as a whole is doing,” Barnett says. “We’re building general-purpose numerical tools that people need, are the best quality and, in this case, are the fastest available.”

FINUFFT is “an important mathematical kernel for lots of different applications,” says CCM director Leslie Greengard, who co-wrote one of FINUFFT’s predecessors. Nonuniform Fourier transforms are essential for many applications such as interpreting data from MRI machines, analyzing the distribution of stars across the universe and reconstructing 3D terrain maps using aerial radar.

Such applications can’t be handled solely by the original fast Fourier transform (FFT) algorithm invented in 1965. That algorithm “revolutionized digital signal processing,” Barnett says, but it has limitations. The algorithm requires data inputs that are regularly sampled — meaning they lie on a uniform grid. (CD-quality audio, for instance, records sound pressure values regularly every 22.68 microseconds.)

Many data sources aren’t so orderly, though, with ‘off-grid’ points that don’t align to a uniform structure. Other times, researchers need to switch between regular-grid and off-grid data to run certain calculations. Such was the case for the initial motivator for building FINUFFT: analyzing the unruly data collected by cryo-electron microscopy (cryo-EM) research. Cryo-EM determines the 3D structure of chilled proteins by bombarding them with electrons. In order to rotate a protein model of interest in 3D and accurately match it to hundreds of thousands of noisy images, Fourier transforms need to be evaluated on a variety of grid systems.

FINUFFT generalizes the regular-grid FFT algorithm to handle off-grid input or output data while maintaining a fast processing speed. The code accomplishes this using a so-called spreading function, which controls how the creation of ongrid data points is influenced by the values at neighboring off-grid points: The closer the neighbor, the stronger its influence. The design of this function is crucial to obtaining high accuracy and efficiency. Once all the on-grid points are filled in, the usual FFT can work its magic.

“The heart of the algorithm is how fast you can do that spreading,” says Jeremy Magland, a senior data scientist at the CCM who contributed to FINUFFT’s development.

FINUFFT users can choose any accuracy level they prefer: Low accuracies run fastest, whereas higher accuracies take longer because more neighboring spreading points are used in the calculations.

Using a spreading function introduces error, though, because it ‘smooths out’ the signal. This smoothing dampens higher frequencies, so FINUFFT boosts higher frequencies after the fast Fourier transform does its work. Since the spreading function is known, the code can directly tweak the final result to compensate for the introduced error.

Although other software libraries exist for non-uniform Fourier transforms, many are made only for specific applications, such as MRI. Barnett, Magland and colleagues designed FINUFFT to be multipurpose, documented and easy to access from all of the major scientific programming languages. FINUFFT works in 1D, 2D or 3D and is entirely open source, so any project can freely use it.

Fourier transforms are crucial to fields such as medical imaging. This mathematical tool breaks down a complex signal into its constituent frequencies, represented by the spikes in this graph.

Some scientists are already leveraging FINUFFT in their projects, including in the code used in 2019 to produce the first-ever image of a black hole. At the Flatiron Institute, David Stein, a research scientist at the Center for Computational Biology, uses FINUFFT to convert between the classic Cartesian grid coordinate system and a curved coordinate system that conforms around oddly shaped objects sitting in flowing fluids. Using such custom coordinate systems makes his fluid dynamics calculations more accurate, and FINUFFT allows Stein to move between the two grid shapes freely.

FINUFFT isn’t just flexible; it’s also blazingly fast. It’s designed to remove bottlenecks found in previous code libraries and to take full advantage of the parallel processing capability of a computer’s hardware.

In September 2019, Barnett, Magland and collaborator Ludvig af Klinteberg, now of the KTH Royal Institute of Technology in Stockholm, published a paper in the SIAM Journal on Scientific Computing showing just how fast FINUFFT is. In tests, FINUFFT was faster than every other tested code at all but the lowest accuracy levels, they found. That included the library co-written by Greengard. “It’s one of the codes we beat quite successfully,” Barnett says. “He’s fine about that.”

FINUFFT interpolates the values of on-grid points using off-grid data. The tool accomplishes this using a spreading function (pink curve). The function determines how strongly each off-grid point (pink circle) influences values on the grid (white lines). The final value of each on-grid point is the weighted sum of all neighboring off-grid data.

Barnett and his team are currently working to release an even faster version of FINUFFT written by Flatiron Institute summer intern Yu-Hsuan Shih that runs on graphics processing units (GPUs).

One remaining challenge, Barnett says, is spreading the word about FINUFFT. “You have to rely on some word-of-mouth and people finding it online when they need a tool,” he says. Unfortunately, many people don’t realize that what they’re doing is actually a nonuniform Fourier transform. “It’s like making a better hammer, but many people are still hammering with rocks,” Barnett says.

At the end of our interview, Barnett scribbles a few outreach ideas on a sticky note, such as including tutorial use cases in FINUFFT’s documentation and making installation easier. “Outreach is sometimes as hard as doing new research,” he says, “but it’s also an exciting part of what we do at the Flatiron Institute. We’re trying to make the programs that people need now, and get them out there.”