Milestone-Proposal talk:First Demonstration of the Fast Fourier Transform (FFT), 1964

Advocates’ Checklist

1. Is proposal for an achievement rather than for a person? If the citation includes a person's name, have the proposers provided the required justification for inclusion of the person's name?
2. Was proposed achievement a significant advance rather than an incremental improvement to an existing technology?
3. Were there prior or contemporary achievements of a similar nature?
4. Has the achievement truly led to a functioning, useful, or marketable technology?
5. Is proposal adequately supported by significant references (minimum of five) such as patents, contemporary newspaper articles, journal articles, or citations to pages in scholarly books? At least one of the references from a peer-reviewed scholarly book or journal article. The full text of the material, not just the references, shall be present. If the supporting texts are copyright-encumbered and cannot be posted on the ETHW for intellectual property reasons, the proposers shall email a copy to the History Center so that it can be forwarded to the advocate. If the advocate does not consider the supporting references sufficient, the advocate may ask the proposer(s) for additional ones.
6. Are the scholarly references sufficiently recent?
7. Is proposed citation readable and understandable by the general public?
8. Does the proposed plaque site fulfill the requirements? Is the address complete? Are the GPS coordinates correct and in decimal format?
9. Is the proposal quality comparable to that of IEEE publications?
10. Scientific and technical units correct? (e.g. km, mm, hertz, etc.) Are acronyms correct and properly upperercased or lowercased?
11. Date formats correct as specified in Section 6 of Milestones Program Guidelines? https://ieeemilestones.ethw.org/Helpful_Hints_on_Citations,_Plaque_Locations

Independent Expert Reviewers’ Checklist

1. Is suggested wording of the Plaque Citation accurate?
2. Is evidence presented in the proposal of sufficient substance and accuracy to support the Plaque Citation?
3. Does proposed milestone represent a significant technical achievement?
4. Were there similar or competing achievements? If so, have the proposers adequately described these and their relationship to the achievement being proposed?

In answering these questions, the History Committee asks that independent expert reviewers apply a similar level of rigor to that used to peer-review an article, or evaluate a research proposal. Some elaboration is desirable. Of course the Committee would welcome any additional observations that you may have regarding this proposal.

Submission and Approval Log

Submitted date: 5 September 2024
Advocate approval date: 12 September 2024
History Committee approval date: 25 September 2024
Board of Directors approval date: 25 November 2024

Original Citation and Text as Submitted -- Administrator4 (talk) 17:15, 11 September 2024 (UTC)

First Demonstration of the Fast Fourier Transform (FFT), 1964

In 1964, a computer program implementing a highly-efficient Fourier analysis algorithm was demonstrated at IBM Research. Developed using a Princeton University professor's contributions to IBM collaborators, the technique calculated discrete Fourier transforms at least two orders of magnitude faster than had been previously demonstrated. Named the Fast Fourier Transform (FFT), its speed enabled numerous applications including computerized tomography, audio and video compression, signal processing, scientific computing, and real-time data streaming.

Expert Review #1: Alex Barnett -- Bberg (talk) 17:18, 30 August 2024 (UTC)

Alex Barnett is an applied mathematician and numerical analyst. He is a Senior Research Scientist, and Group Leader for Numerical Analysis at the Center for Computational Mathematics at the Flatiron Institute in New York, NY. After a Ph.D in physics from Harvard, he did postdoctoral work in radiology at Massachusetts General Hospital, and as a Courant Instructor at New York University. He then served on the mathematics faculty at Dartmouth College for 12 years, reaching the rank of full professor, and creating several new courses on topics such as the mathematics of music and sound. His main research areas are scientific computing, partial differential equations (including wave scattering and viscous fluid flow), boundary integral equations, fast algorithms, signal processing, statistics, imaging, inverse problems, biomathematics, and quantum chaos. In several of these areas he has released popular software implementations. He has authored or coauthored over 70 academic articles. His awards include several NSF grants, Dartmouth's Karen E. Wetterhahn Memorial Award for Distinguished Creative or Scholarly Achievement, and 1st prize in the 1990 International Physics Olympiad.

1) Is the suggested wording of the Plaque Citation accurate?
Yes. The citation now cites "scientific computing" as a key application enabled by the FFT.

2) Is evidence presented in the proposal of sufficient substance and accuracy to support the Plaque Citation?
Yes. The history (going back to Gauss and Danielson-Lanczos), and the basic technical review are all great. From the '60s to the '90s, the reduction in arithmetic operations was the key goal, and the FFT achieved it brilliantly. The FFT is the paradigm "fast algorithm" which transformed numerical computing and image processing. The quotes chosen and societal examples (CT imaging, etc.) are excellent for showing this.

3) Does the proposed milestone represent a significant technical achievement?
Certainly! The FFT has had a massive positive effect on society, through imaging, signal processing, and computing.

4) Were there similar or competing achievements? If so, have the proposers adequately described these and their relationship to the achievement being proposed?
I can't think of a competing method. The FFT is really the paradigm "fast algorithm"; there is no competition (apart from sub-variants of the algorithm).

Expert Review #2: Matthias Kabel -- Bberg (talk) 11:59, 5 September 2024 (UTC)

Matthias Kabel is an applied mathematician and holds a PhD from the University of Hamburg, Germany. He is deputy head of the Department of Fluid and Material Simulation, and team leader for Lightweight Design and Insulating Materials at the Fraunhofer Institute for Industrial Mathematics (ITWM) in Kaiserslautern, Germany. His research interests include partial differential equations (with FFT-based methods), digital rock physics (DRP), model order reduction (MOR), high performance computing (HPC), and quantum computing. He has authored or co-authored over 40 scientific articles. His developments are distributed as part of the GeoDict software (www.geodict.com) by the Fraunhofer spin-off Math2Market.

1) Is the suggested wording of the Plaque Citation accurate?
Yes.

2) Is evidence presented in the proposal of sufficient substance and accuracy to support the Plaque Citation?
Yes, the overview of the development is great and explains the superiority of the FFT algorithm.

3) Does the proposed milestone represent a significant technical achievement?
Definitely! The FFT has a huge impact on society because the Fourier transform is needed for many applications such as medical imaging and scientific computing.

4) Were there similar or competing achievements? If so, have the proposers adequately described these and their relationship to the achievement being proposed?
There is no competing algorithm for computing the Fourier transform.

Expert Review #3: Arjuna Madanayake -- Bberg (talk) 12:15, 5 September 2024 (UTC)

Arjuna Madanayake is Associate Professor of Electrical and Computer Engineering in the College of Engineering and Computing at Florida International University (FIU). He completed his Ph.D. in 2008 and his MSc. in 2004 in Electrical Engineering at the University of Calgary, Canada. His B.Sc. in 2002 in Electronic and Telecommunication Engineering was from the University of Moratuwa, Sri Lanka. He leads the RF, Analog and Digital (RAND) Lab for Advanced Signal Processing Circuits at FIU.

1) Is the suggested wording of the Plaque Citation accurate?
Yes.

2) Is evidence presented in the proposal of sufficient substance and accuracy to support the Plaque Citation?
Yes.

3) Does the proposed milestone represent a significant technical achievement?
Most definitely!

4) Were there similar or competing achievements? If so, have the proposers adequately described these and their relationship to the achievement being proposed?
There is no similar or competing method.

Expert Review #4: Sau-Gee Chen -- Bberg (talk) 16:07, 12 September 2024 (UTC)

Sau-Gee Chen holds a PhD in Electrical Engineering from SUNY at Buffalo, NY. He is currently an Emeritus Professor at National Yang Ming Chiao Tung University, Taiwan, and Chairman of IEEE LMAG in the Taipei Section. He is a board director at ICP DAS, Taiwan, and a board director at intelliGo Technology Inc., Taiwan. His research interests include digital communication, digital signal processing, and VLSI signal processing. He has published over 120 conference and journal papers, and holds 20 US, China and Taiwan patents.

1) Is the suggested wording of the Plaque Citation accurate?
Yes, and I am happy to have had "telecommunications" added to the citation as one of FFT's applications, along with a supporting paragraph in the "historical significance" supporting section.

2) Is evidence presented in the proposal of sufficient substance and accuracy to support the Plaque Citation?
Yes, certainly.

3) Does the proposed milestone represent a significant technical achievement?
Yes. It has been extremely significant in its impact on general society, helping the rapid advancement of telecommunications technology.

4) Were there similar or competing achievements? If so, have the proposers adequately described these and their relationship to the achievement being proposed?
No.

Advocate's Comment -- Bberg (talk) 16:28, 12 September 2024 (UTC)

I am very pleased with the current status of this Milestone proposal. The citation has gone through considerable review by all 4 Expert Reviewers, who each provided important contributions about its wording, including to best ensure that the very broad impact of the FFT is encompassed in the last sentence. This step was preceded by Harold Stone who initiated this proposal in March 2024, and who was co-proposer with Princeton's Ruby B. Lee and IBM's Jim Wynne. They received early encouragement from IEEE History Center Outreach Historian Alex Magoun. Also involved in this process was Ralph Gomory, now in his mid-90s, a former Head of Research at IBM Yorktown, and who along with John Tukey were professors at Princeton University.

Everyone contributed to the considerable documentation provided in the "historical significance" section and the remainder of the background history. It was my pleasure to help shepherd this process as the Advocate. It was also my pleasure to again work with Harold Stone after our excellent experience in 2023 with the Milestone for the IEEE 754 Floating Point Standard, whose plaque joined the earlier RISC Milestone plaque at UC Berkeley.

Expert Review #5: Victor DeBrunner -- Bberg (talk) 15:41, 14 September 2024 (UTC)

Victor DeBrunner is a Professor of Electrical and Computer Engineering at Florida State University. His PhD is from Virginia Polytechnic Institute and State University. His research interests are in Digital Signal and Image Processing, specifically in signal modeling, adaptive and intelligent systems, and special hybrid systems for high fidelity control and filtering. He has published over 250 technical papers in these and related areas. He has been an associate editor for IEEE Signal Processing Transactions, the IEEE Signal Processing Letters, and for the IEEE Transactions on Circuits and Systems I. He is the Board of Directors Vice Chair for the Asilomar Conference on Signals, Systems, and Computers, a Calirfornia non-for-profit corporation.

1) Is the suggested wording of the Plaque Citation accurate?
The current version is fine with me.

2) Is evidence presented in the proposal of sufficient substance and accuracy to support the Plaque Citation?
Yes.

3) Does the proposed milestone represent a significant technical achievement?
It is one of the defining technical achievements of all time.

4) Were there similar or competing achievements? If so, have the proposers adequately described these and their relationship to the achievement being proposed?
The proposers have provided extensive background information. Interestingly, though, recent publications using the Winograd-type DFT Algorithm specifically for sequences of lengths that are powers-of-two have begun appearing. See, e.g., Electronics 2022, 11(9), 1342; https://doi.org/10.3390/electronics11091342 and A. Cariow and M. Raciborski, On Derivation of the Winograd Discrete Fourier Transform Algorithms for N Equal to the Power of Two, 2019 Signal Processing Symposium (SPSympo), Krakow, Poland, 2019, pp. 181-184, doi: 10.1109/SPS.2019.8881971.