30-5 Polynomial evaluation at multiple points

We have seen how to evaluate a polynomial of degree-bound $n$ at a single point in $O(n)$ time using Horner's rule. We have also discovered how to evaluate such a polynomial at all $n$ complex roots of unity in $O(n\lg n)$ time using the $\text{FFT}$. We shall now show how to evaluate a polynomial of degree-bound $n$ at $n$ arbitrary points in $O(n\lg^2 n)$ time.

To do so, we shall assume that we can compute the polynomial remainder when one such polynomial is divided by another in $O(n\lg n)$ time, a result that we state without proof. For example, the remainder of $3x^3 + x^2 - 3x + 1$ when divided by $x^2 + x + 2$ is

$$(3x^3 + x^2 - 3x + 1) \mod (x^2 + x + 2) = -7x + 5.$$

Given the coefficient representation of a polynomial $A(x) = \sum_{k = 0}^{n - 1} a_kx^k$ and $n$ points $x_0, x_1, \dots, x_{n - 1}$, we wish to compute the $n$ values $A(x_0), A(x_1), \dots, A(x_{n - 1})$. For $0 \le i \le j \le n - 1$, define the polynomials $P_{ij}(x) = \prod_{k = i}^j (x - x_k)$ and $Q_{ij}(x) = A(x) \mod P_{ij}(x)$. Note that $Q_{ij}(x)$ has degree at most $j - i$.

a. Prove that $A(x) \mod (x - z) = A(z)$ for any point $z$.

b. Prove that $Q_{kk}(x) = A(x_k)$ and that $Q_{0, n - 1}(x) = A(x)$.

c. Prove that for $i \le k \le j$, we have $Q_{ik}(x) = Q_{ij}(x) \mod P_{ik}(x)$ and $Q_{kj}(x) = Q_{ij}(x) \mod P_{kj}(x)$.

d. Give an $O(n\lg^2 n)$-time algorithm to evaluate $A(x_0), A(x_1), \dots, A(x_{n - 1})$.

(Omit!)