I am learning about the Fast Fourier Transform, which converts a polynomial from its coefficient representation into its point-wise form using divide-and-conquer. The Fast Fourier Transform evaluates a polynomial of degree $n$ at $n$ distinct points. The $n$ distinct points are the $n$-th roots of unity.
I know that a root of unity is a complex number that when raised to some positive integer power $n$ is equal to $1$. However, I am not sure what is the advantage of using roots of unity in the Fast Fourier Transform. Any insights are appreciated.
In principle, To evaluate a polynomial $A(x)$ of degree $n$, you can use $n+1$ arbitrary values. For example: $2$ points to determine a line; $3$ points for a parabola etc. But reconstructing the coefficients of $A(x)$ from these $n+1$ arbitrary values like $A(x_0 ),A(x_1 ),…, A(x_n)$ requires Lagrangian interpolation. If the calculation complexity for these operations is analyzed, one requires $\mathcal O(n)$ operations for the evaluation step and $\mathcal O(n^2)$ for the reconstruction step. If instead of these ‘arbitrary’ values, when $x_i,i\in[0,n]$ s are chosen cleverly, the $\mathcal O(n^2)$ complexity can be reduced to $\mathcal O(n \log n)$. But How?
One idea that could immediately come to mind is choosing positive-negative pairs $\pm x_0,\pm x_1,...,\pm x_{n-1}$. So when a polynomial is evaluated like this, the even powers coincide with the odd ones like $A(x)=A_\text{even} (x^2 )+xA_\text{odd} (x^2)$ where $A_\text{even}$ is the polynomial with even-numbered coefficients ($\text{degree} \le n/2-1$) and where $A_\text{odd}$ is the polynomial with odd-numbered coefficients (degree $\le n/2-1$). This is because, for each squared number, the negative value is the reflection of that positive number. So by squaring, one is able to halve the evaluation points. To give an example:
$A(x)=6x^6+5x^5+4x^4+3x^3+2x^2+x+1$ can be represented as
$A(x)=(6x^6+4x^4+2x^2+1)+x(5x^4+3x^2+1)$
To put in other words, evaluating at $n$ paired points $\pm x_0,\pm x_1,...,\pm x_{n-1}$ reduces to evaluate the $A_\text{even}(x)$ and $A_\text{odd}(x)$ which has only half the degree at $n/2$ points. So now the original problem has been modified into two subproblems of size $n/2$ with the linear operations. By using this principle, the polynomial can be broken down into sub problems until no such division is possible iteratively or via recursion. So the complexity comes down to $T(n)=2T(n/2)+\mathcal O(n)$ which is $\mathcal O(n \log n)$.
The plus-minus trick or choosing positive-negative pairs $\pm x_0,\pm x_1,⋯,\pm x_{(n-1)}$ only works at the top level of the recursion. It works for $x^2=\pm x$ for the smaller stages and what can we do when we need to simplify higher values like $x^4=\pm x^2$? How can a square be negative? Complex roots of unity can solve this problem. In this case for $x^4=\pm x^2=(+x,-x,+ix,-ix)$. This is elaborated briefly below.
The $n^{th}$ roots of unity are the complex numbers $1,ω,ω^2,⋯,ω^{(n-1)}$ where $ω=e^{(2πi/n)}$.
Note that the $n^{th}$ roots are plus-minus paired: $ω^{(n/2+j)}=-ω^j$ and
Squaring them produces the $n/2$ nd roots of unity.
Voila! Complex roots of unity fulfill the properties (paired and squaring then produces $n/2$ nd roots) which means, the evaluation needs only $\mathcal O(n \log n)$ operations. So FFT exploits these amazing properties of the complex roots of unity hence reducing the computation time.
Finally for the reconstruction back to the coefficient representation, the interpolation can be done using the inverse FFT which requires again $\mathcal O(n \log n)$ operations compared to the $\mathcal O(n^2)$ required by the Lagrangian. Hope this answer helps, Cheers! Please feel free to improve this answer.