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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用