by Dima Kochkov

# Fast Fourier Transform

O(N log(N)) computation of a discrete fourier transform, fast integer multiplication

## Presentation Summary

In this presentation, I will give a short overview of the Fast Fourier transform algorithm. We will look into different polynomial representations and corresponding computational complexities of simple algebraic operations. The FFT algorithm will gain it’s performance by utilizing the coefficient and point-sample representations as well as an algorithm to compute one given the other.

## References

*“MIT video lecture on FFT,” by Erik Demaine

*“lecture on FFT complexity analysis”

### All Numerical Methods

- by Kiel Williams ·
**Relaxation Methods in the Solution of Partial Differential Equations** - by Kiel Williams ·
**Numerical ODE Solutions** - by Dima Kochkov ·
**Fast Fourier Transform** - by Will Wheeler ·
**Finding Eigenvalues: Arnoldi and QR** - by Brian Busemeyer ·
**Compressed sensing** - by Yubo "Paul" Yang ·
**Automatic Differentiation**

Yubo "Paul" Yang ALGORITHM

numerical method