How AI is improving chip production
Explainer
Peter Hess
How IBM Research first demonstrated the revolutionary Cooley-Tukey FFT
It’s the algorithm that made internet videos possible. The Cooley-Tukey Fast Fourier Transform was first demonstrated at IBM Research in 1964.
If you're reading this, you’re interacting with the Cooley-Tukey Fast Fourier Transform (FFT) algorithm right now. You probably interact with it online dozens of times every day. Originally deployed to detect underground nuclear testing, it’s become crucial to the routine file compression that makes internet image sharing possible. The Cooley-Tukey FFT also enables diverse signal processing tasks for atmospheric research, radio astronomy, and more.
The algorithm was first demonstrated in 1964 at IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York. It could be used to calculate Fourier transforms at least two orders of magnitude faster than had been previously shown. To commemorate that first demonstration, the Institute of Electrical and Electronics Engineers (IEEE) is presenting IBM Research with a Milestone Award, a program of the IEEE History Committee. The event will be marked with a plaque outside the office where mathematician James Cooley used to work at IBM Research headquarters.
John Tukey was a statistician who taught and worked at Princeton and at Bell Labs. He is credited with coining the computer term ‘bit’ and introducing the box plot, among many other computational and mathematical contributions that bear his name, like Tukey’s range test.
James Cooley was born and raised in the Woodside neighborhood of Queens, New York. He went to Manhattan College on the G.I. Bill, earned his Ph.D. at Columbia University, and worked at IBM research for three decades.
Together, the two mathematicians devised the Cooley-Tukey FFT, an algorithm used to quickly discern the varied frequencies in waveforms, like a prism or a rain cloud separating out the different visible wavelengths of light. “The FFT is a mathematical version of this effect, one that can be executed on a computer,” said Harold Stone, former IBM Research staff member.
Cooley, who enlisted in the U.S. Army fresh out of high school, went on to work as a programmer at the Institute for Advanced Study in Princeton, New Jersey, from 1953 to 1956, where he was part of John von Neumann’s group that built Princeton’s first electronic computer, the IAS machine. During that time, he met his wife Ingrid, an au pair from Sweden.
In 1961, Cooley took a job at IBM Research, where he worked until his retirement in 1991. He passed away in 2016.
Lars Cooley recalled his father as a smiling, friendly man who could keep up his end of a conversation with anyone. He was handy, too, and a quick study. After chatting with the stonemasons who worked on the Thomas J. Watson Research Center, IBM Research’s new permanent home, Cooley enlisted Lars to mix up their own mortar and build a retaining wall for the home swimming pool. “Growing up I saw a person who wasn’t just committed to the FFT — he had a lot of different loves of life,” Lars said.
At the same time, he was “modest to a fault,” according to Lars. “People had no idea he was this brilliant mathematician.” Neighbors and family friends often knew his father worked with computers, but even those who knew about the Cooley-Tukey FFT sometimes didn’t make the connection. “They didn’t know he was the James Cooley,” said Lars. “People who knew his work would tell me what a great mathematician he was, but to me, he was just Dad.”
The algorithm is named for two people, but a third was responsible for linking them: Dick Garwin. In 1963 Garwin, who was head of the IBM Watson Scientific Laboratory at Columbia University at the time, met John Tukey at a meeting of President John F. Kennedy’s Science Advisory Committee in Washington, D.C. They were there for a classified discussion about how to detect rival nations’ underground nuclear tests — and glean data on their nuclear weapons programs.
Enter the Fourier equations, a 19th-century series which expand or approximate periodic functions — including light or sound waves — as a sum of trigonometric functions. These equations made it possible to take the amplitude of a wave at various timepoints and calculate its frequency. This method can be applied to detect earthquakes (or underground explosions) by differentiating primary waves and secondary waves from surface waves on a seismograph recording. Each type of wave travels through the Earth at a different velocity, which shows up as different frequencies on a seismograph. Given these measurements, the Fourier transform, a generalization of the series, can solve for the amplitude of the earthquake at its source.
Back in 1963, though, this wasn’t enough to solve the problem at hand. “The Fourier transform was far too slow to calculate in practice,” said Stone. “It couldn’t keep up with the seismic data.” What they needed was a fast Fourier transform, an FFT.
Garwin inquired with IBM Research to find someone who could write numerical analysis code for high-speed scientific computers. Word came back that Cooley was the man he was looking for, so Garwin introduced him to Tukey. Cooley and Tukey met at Princeton, and Cooley returned to the Watson Research Center. Not long after, he had written a Fortran program for the FFT. They published their paper on the FFT in 1965 in the journal Mathematics of Computation. In 2024, Garwin told IEEE Spectrum that this introduction between the two was the achievement he was most proud of.
“Maybe it would have happened eventually, but he made it happen,” said Stone.
Six decades later, Cooley, Tukey, and Garwin are all no longer with us, but the Cooley-Tukey FFT lives on. It is used in the chemical and materials simulations that impact drug and material design, and the computer-aided design (CAD) used to design cars, airplanes, and buildings. All modern image reconstructions for magnetic resonance imaging (MRI) and computed tomography (CT) scans are based on the FFT or its variants, as well as the compression and decompression of photos and videos to share on the internet, and it’s still widely used in seismology. The JPEG and MPEG standards are based on FFT algorithms. Videos and images comprise the bulk of internet traffic, and their transmission depends on the FFT algorithm, defined at a time when the earliest version of the internet wasn’t even yet an idea.
