Resources for Understanding Fast Fourier Transforms (FFT)
Tags: computerscience, omscs
Published: 2019-06-02 17:33:28

In the [Graduate Algorithms course](https://www.omscs.gatech.edu/cs-8803-ga-graduate-algorithms) I'm currently taking we've been learning a lot about [Fast Fourier Transforms](https://en.wikipedia.org/wiki/Fast_Fourier_transform) and [divide-and-conquer](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm) algorithms for conducting them. Although I've known about FFT at the highest-levels (like that you might use it to isolate frequencies from a signal), this is the first time I've had to learn about it in-depth and I've found it pretty challenging.  Thankfully there are lots of resources on the subject online if you know where to find them. And that's a big _if_.

This post is my attempt at aggregating some of the resources I found particularly helpful. They're listed in order of requiring the least prerequisite knowledge to the most.

## What is a Fast Fourier Transform?
The lectures and textbook for my class tackled FFT from primarily a mathematical perspective and I found it difficult to understand the _how_ it helped in practice. The following [video from 3 Blue 1 Brown](https://www.youtube.com/watch?v=spUNpyF58BY) really helped explain it to me at this high level:

{% youtube spUNpyF58BY %}

## Understanding What Are the Nth Roots of Unity
Another thing I had trouble with was understanding the Nth Roots of Unity. With my weaker match background I did not have much exposure to the [complex plane](https://en.wikipedia.org/wiki/Complex_plane) and I honestly don't think I had ever heard the term "Roots of Unity." Well it turns out they're pretty important for FFT and a lot of resources consider them to be prerequisite knowledge. I found [the following video](https://www.youtube.com/watch?v=1BjDKRrR8-E) helpful for getting me on the same page:

{% youtube 1BjDKRrR8-E %}

## Doing Fourier Transforms by Hand
The next thing I found useful was a step-by-step guide of how you might use Fourier Transforms to multiply two polynomials by hand. Most examples explain generalized solutions to the problem using variables and don't actually explain using concrete examples. Someone shared the following StackExchange post with me and I found it was just what I needed.

* [Show how to do FFT by hand](https://cs.stackexchange.com/a/103626/3082)

## Lectures for Understanding FFT by Divide-and-Conquer
Lastly, I watched some lectures from other programs to see the material explained in different ways. I found [this lecture by Erik Demaine](https://www.youtube.com/watch?v=iTMn0Kt18tg) useful, but only after digesting some of those other resources I mentioned earlier.

{% youtube iTMn0Kt18tg %}

I also found [these lectures](https://classroom.udacity.com/courses/ud061/lessons/3495828730/concepts/11787587860923) from a different Georgia Tech class ([CS 6505: Computability, Complexity & Algorithms](https://www.omscs.gatech.edu/cs-6505-computability-algorithms)), but I believe you'll need to create a free Udacity account to view them.

## Summary

I typically prefer explaining topics on my own (see my [Solving the Knapsack Problem with Dynamic Programming](https://dev.to/downey/solving-the-knapsack-problem-with-dynamic-programming-4hce) post) to solidify my own understanding, but for this one I'm still working through that bit myself! Again, I've found this list of resources helpful and hopefully by recording it all in one place it will be easier for other folks (myself included) to find in the future.