Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Lecture
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
This lecture covers the Fast Fourier Transform (FFT) algorithm for polynomial multiplication, explaining how it transforms polynomials into vectors, performs element-wise multiplication, and reverts back to the original space. The instructor demonstrates the recursive nature of FFT, splitting polynomials into even and odd parts, and reconstructing coefficients using roots of unity. The complexity analysis of FFT is discussed, highlighting its efficiency in reducing the number of multiplications required for polynomial operations.