The Fast Fourier Transform: an algorithm that has changed your life

Alex Barnett

Mathematics, Dartmouth College.


The Fast Fourier Transform (FFT) has revolutionized signal processing since it reduced the cost of extracting the frequency spectrum of a signal of length N from O(N^2) to O(N log N). It was recently voted one of the "top 10 algorithms of the 20th century". It is an essential part of any applied mathematician's toolkit. I will explain in simple terms how the algorithm works, and show a couple of applications.

Back to ACMS schedule