Polynomial Evaluation by Divide and Conquer

🔥

Naive evaluation takes

O(n^2)

time

We have to pick $n$ points to evaluate a polynomial $A(x)$ with degree $d \le n-1$ , we can pick positive negative pairs

\pm x_0, \pm x_1, \dots, \pm x_{n/2-1}

Then the computations required for each $A(x_i)$ and $A(−x_i)$ overlap a lot, because the even powers of $x_i$ coincide with those of $−x_i$ .

To generalize, write

A(x)=A_e(x^2)+xA_o(x^2)

Runtime analysis:

T(n)=2T(n/2)+O(n) \in O(n \log n)

⚠️

Problem: For recursion to work we need

x_0^2, x_1^2, \dots, x_{n/2-1}^2

to be positive-negative pairs!

We use complex numbers!

By reverse-engineering from the bottom, we eventually reach the initial set of $n$ points. Perhaps you have already guessed what they are: the complex nth roots of unity, that is, the $n$ complex solutions to the equation $z^n = 1$ .

Figure 2.6 is a pictorial review of some basic facts about complex numbers. The third panel of this figure introduces the nth roots of unity: the complex numbers $$1, \omega, \omega^2, \dots , $\omega^{n−1}$ , where $\omega = e^{2\pi i/n}$ . If $n$ is even,

1. The nth roots are plus-minus paired, $\omega^{n/2+j} = −\omega^j$

2. Squaring them produces the $(n/2)$ -nd roots of unity.

Therefore, if we start with these numbers for some n that is a power of 2, then at successive levels of recursion we will have the $(n/2k)$ -th roots of unity, for $k = 0, 1, 2, 3, \dots$ All these sets of numbers are plus-minus paired, and so our divide-and-conquer, as shown in the last panel, works perfectly. The resulting algorithm is the fast Fourier transform.