12
$\begingroup$

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(n^2)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct with each other. 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(n\log^2(n))$ time.

I want to ask whether there is any more efficient algorithm better than $O(n^2)$? 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$.

$\endgroup$
22
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Thanks for the comments. This is not a problem for me as the polynomial is over some prime finite field $\mathbf{F}_q$. This task (expanding a polynomial given its roots) is quite common in set accumulator or zero-knowledge proof in the cryptographic settings. $\endgroup$ – xucheng Nov 4 '19 at 10:30

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.