Discrete Fourier Transform

Summary

MotivationLet’s take a look at how we multiply two polynomials of degree \(N\): \[\begin{align*} f(x) &= 4x^{4}-2x^{3}-6x^{2}\ +4x\ +\ 3\\ g(x) &= -x^{4}+11x^{3}-9x^{2}+-1x\ +\ 6\\ \end{align*}\]We can use the distributive property to multiply two polynomials and then sum up coefficients for identical terms. \[\begin{align*} f(x) &\cdot g(x) = \\ (4x^{4}-2x^{3}-6x^{2}\ +4x\ +\ 3) &\cdot (-x^{4}+11x^{3}-9x^{2}+-1x\ +\ 6) = \\ -4x^{8}+46x^{7}-52x^{6}-56x^{5} &+ 121x^{4}-9x^{3}-67x^{2}+21x+18 \end{align*}\]However, this leads to \(O(N^2)\) operations to compute the coefficients. In this section, we are going to look at how we can accomplish polynomial multiplication in \(O(NlogN)\) using Fast Fourier Transform (FFT) (an algorithm to compute DFT). We will also look at how we can solve this problem in ~10 lines of code!Polynomial RepresentationsA polynomial of degree \(n-1\) can be represented via:Coefficient Representation: \(n\) coefficients \([a_0, a_1, a_2, \cdots, a_{n-1}]\)Value Representation: \(n\) sample points \([(x_1, f(x_1)), (x_2, f(x_2)), \cdots, (x_{n-1}, f(x_{n-1}))]\)Note that any \(n\) unique points uniquely identify one and only one polynomial of degree \(n-1\) (Interpolation Theorem).Polynomial MultiplicationWe observe that computing polynomial multiplication using the coefficients leads to \(O(N^2)\) operations. Now, let’s try the value representation.These are the polynomials f(x) and g(x) that we want to multiply:Step1: Sample \(n\) points on each polynomial (at the same x coordinates).Step2: Compute the pairwise product of samples. Step3: Find the unique polynomial of degree \(n-1\) (\(n\) coefficients) that goes through these \(n\) red points (interpolation).This new red curve is our polynomial \(f(x) \cdot g(x)\) and performing the multiplication using the value representation allowed us to multiply the two polynomials in \(O(N)\) operations.Now we need two magical operations to take us from the coefficient representation to the value representa...