cat.

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