Tag: Programming

‘Life as we know it would be very different without the FFT.’

— Charles Van Loan

I’m not an expert in the Fast Fourier Transform (FFT). I first used it in 1985(ish) and have then used it in most decades since, including 2020. All facets of modern life are touched by the FFT, which is a fast way of doing a Discrete Fourier Transform (DFT), which is a non-continuous way to do the Fourier Transform (which most people learn in Differential Equations math course in college (if they learn it at all).

FFTs are generally used to turn time-series data (for instance a recording of your voice) into frequency domain (showing how much energy was in each frequency range measured in the sample). But that’s just the tip of the iceberg, and probably poorly explained!

My most recent use was to evaluate using certain characteristics of the FFT to replace expensive tensor convolutions in a convolutional neural network. It would have saved about 2/3rds of the convolution operations, which is terrific, except that in our particular network architecture the convolutions were a tiny fraction of the computational expense, so we opted for simple over perfect.

This article describes the FFT in one sentence… impressive! And this article is an overview of how it’s used.