9
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

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 the 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 sub problems of size $n/2$ with the linear operations. By using this principle, the polynomial can be broken down into sub problem 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.

  1. The $n^{th}$ roots of unity are the complex numbers $1,ω,ω^2,⋯,ω^{(n-1)}$ where $ω=e^{(2πi/n)}$.

  2. Note that the $n^{th}$ roots are plus-minus paired: $ω^{(n/2+j)}=-ω^j$ and

  3. Squaring them produces the $n/2$ nd roots of unity.

Voila! Complex roots of unity fulfil the properties (paired and squaring then produces $n/2$ nd roots) which mean, the evaluation needs only $\mathcal O(n logn)$ 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.

$\endgroup$
2
  • $\begingroup$ I started editing your answer to include MathJax formatting. However, some other edit was made while I was working, so I don't know if it has been preserved. I would suggest that you read the MathJax tutorial, and try to familiarize yourself with good formatting. $\endgroup$
    – Xander Henderson
    May 6, 2019 at 21:41
  • $\begingroup$ sorry for the interruption. please continue the good job and i would greatly appreciate $\endgroup$
    – pretty
    May 6, 2019 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.