Pi in the sky

In 2000, IEEE’s Computing in Science & Engineering journal published a list of the 20th century’s top 10 algorithms. No. 8 was the fast Fourier transform (FFT), described as “an algorithm the whole family could use.” The FFT was noted as a go-to method for analyzing and manipulating digital data.

Despite its ubiquity in a variety of fields, the FFT might not have achieved its pop status, especially in climate modeling, if not for scientific computing pioneers like Paul Swarztrauber.

IBM and AT&T Bell Labs created the FFTin 1965. It computes the discrete Fourier transform (DFT), which originated from Jean-Baptiste Joseph Fourier’s 1822 work analyzing heat flow. DFT converts arbitrary signals from their original domain – for instance, time or space – to representations as frequencies and vice versa. In the process, waveforms are transformed to radians, where 2π represents one complete cycle.

The DFT for the size of a specific number (N) requires roughly N² operations. But exploiting algebraic redundancies inherent in DFT, FFT slashes the same task to N log N. (If N is, say, 10,000, the task goes from 100 million operations to 40,000.)  “This shortcut drastically reduces the time needed for calculations,” says Bill Spotz, a Department of Energy (DOE) Office of Science program manager and a former Swarztrauber mentee.

Swarztrauber was a scientific programmer at the National Center for Atmospheric Research (NCAR) in the 1970s when he first encountered FFT. Although he earned his mathematics doctorate at the University of Colorado while at NCAR, for many years Swarztrauber mainly wrote computer programs in support of NCAR’s scientists, who in those days didn’t directly interact with the center’s computers.

Swarztrauber quickly recognized the FFT’s utility for NCAR, especially for colleagues whose work involved elliptic partial differential equations, used to model everything from atmospheric pressure to wind strength and direction.

Although it was easy to write codes that compute FFTs, Swarztrauber found that if he gave them to colleagues, they would inevitably ask him how to make sense of the results. “So,” Swarztrauber said in a 2005 Society for Industrial and Applied Mathematics (SIAM) oral history of numerical analysis and scientific computing, “I would sit down. I would go through the process of telling them what they had. This usually amounted to expressing the complex transform in terms of the real trigonometric representation of their data. I did that a number of times, and finally decided to write both a program and documentation for this process.”

The result: a series of freely available Fortran subroutine libraries that greatly simplified the process of applying FFTs to a range of climate-modeling problems.

These libraries, called FISHPACK, FFTPACK and SPHEREPACK, were co-authored with NCAR colleagues Roland Sweet and John Adams. NCAR researchers found the libraries so helpful that they often reformulated their models specifically to incorporate them.

“There are all kinds of scientific computing packages these days, but at that time they were rare,” Spotz says. “Using a package like the ones Paul created meant you had a guarantee that it was going to be bug-free, efficient and fast.”

‘It would have been obvious to a lot of people in the community that these were hugely important resources.’

And whether users knew it or not, each library was meticulously researched. Swarztrauber and his colleagues would scour the literature for the best methods and then test and implement them on NCAR’s computers.

The first library Swarztrauber officially released with Adams and Sweet, FISHPACK borrowed its name from the mathematician Siméon Denis Poisson, whose last name is French for fish. The Poisson equation is common in physics. It describes wind movement and other diffusion processes that readily lend themselves to solutions that are Fourier series.

FFTPACK simplified the calculation of partial differential equations for determining spatial derivatives of pressure, velocity, temperature, and other variables in Cartesian x, y, and z coordinates. Earth, however, is most closely approximated by a sphere, meaning that geophysical processes are most appropriately modeled using spherical coordinates. When working with these, it’s necessary to replace the Fourier transform with the harmonic transform. SPHEREPACK, written with Adams, computes the appropriate spatial derivatives that can be substituted into the equations, which can then be integrated in time to compute the evolution of the geophysical process under consideration.

The libraries were initially distributed on reel-to-reel tape, one at a time, to other NCAR programmers. When word spread, an administrative assistant mailed the tapes out upon request. “It would have been obvious to a lot of people in the community that these were hugely important resources,” Spotz says.

The libraries are now hosted online at several software repositories, including Netlib, where they have been accessed more than 3 million times. Given the massive interest, the libraries have been used in applications far beyond climate modeling – everything from neuroscience to oil exploration. Swarztrauber mentions one specific example in the SIAM oral history: a high-end speaker manufacturer used SPHEREPACK to model the reflective surfaces of individual concert halls and analyze sound wave propagation.

Swarztrauber eventually moved into full-time research at NCAR, publishing more than 60 papers in computational fluid dynamics, parallel computation and communication algorithms, computational aspects of weather and climate modeling, and multicomputer design. Swarztrauber retired in 2004 with the title of senior scientist emeritus. He died in 2011.

Beyond the FFT libraries, Swarztrauber’s other major contribution to scientific computing at NCAR involved bringing cutting-edge systems online, including a Cray-1 supercomputer in 1977.

“Paul was dogged in his determination that NCAR get one of these machines,” Spotz says. “He was also instrumental in figuring out how to use it to model the climate. Paul and his group really led the way in getting computers to solve physics problems faster than people had ever seen at the time.”

In the late 1980s, NCAR acquired a Connection Machine 2, which boasted 8,192 parallel processors, sparking Swarztrauber’s fascination with parallel computing algorithms. This interest eventually led to a collaboration among NCAR and Oak Ridge, Argonne, Los Alamos, and Pacific Northwest national laboratories to compare the performance of different atmospheric models on massively parallel computers at each lab. This later evolved into the DOE Computer Hardware Applied Mathematics and Model Physics project.

“Paul really was a pioneer in scientific computing,” Spotz says. “And I think it’s a no-brainer that we all benefitted from him being in the right place at the right time.”