What is the most efficient algorithm to compute polynomial coefficients from its roots?

Question

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is

$$y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$$

To get the coefficients, i.e., $y = \sum_{i}^n a_i x^i$, a straightforward expansion requires $O \left(n^2\right)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct, the problem is equivalent to polynomial interpolation with $n$ points: $(x_1, 0), (x_2, 0), \dotsc, (x_n, 0)$. The fast polynomial interpolation algorithm can be run in $O \left( n \log^2(n) \right)$ time.

I want to ask whether there is any more efficient algorithm better than $O \left(n^2\right)$? Even if there are duplicated values among $\{x_i\}$? If it helps, we can assume that the polynomial is over some prime finite field, i.e., $x_i \in \mathbf{F}_q$.

Answer 1

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method.

First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$. Next, compute the coefficients of $f(x)=f_0(x)f_1(x)$ using FFT-based polynomial multiplication.

This yields an algorithm whose running time satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n \log n).$$

The solution to this recurrence is $T(n) = O(n \log^2 n)$. This all works even if there are duplicates in the $x_i$.

(You might also be interested in Multi-point evaluations of a polynomial mod p.)

Answer 2

You should also look at what you actually want to achieve. The coefficients can grow very quickly, meaning that evaluating the polynomial can have large rounding errors. Given the roots, you can evaluate the polynomial quite quickly without knowing the coefficients, and with high precision.