New Resultant Inequalities and Complex Polynomial Factorization
Victor Ya. Pan · SIAM Journal on Computing · 1994
The author deduces some new probabilistic estimates on the distances between the zeros of a polynomial $P(x)$ by using some properties of the discriminant of $P(x)$ and applies these estimates to improve the fastest deterministic algorithm for approximating polynomial factorization over the complex field. Namely, given a natural n, positive $ \in $, such that $\log ({1 / \epsilon }) = O(n\log n)$, and the complex coefficients of a polynomial $P(x) = \sum _{i = 0}^n p_i x^i $, such that $p_n e 0$, $\sum _i |p_i | \leqslant 1$, a factorization of $p(x)$ (within the error norm $ \in $) is computed as a product of factors of degrees at most ${n / 2}$, by using $O(\log ^2 )$) time and $n^3 $ processors under the PRAM arithmetic model of parallel computing or by using $O(n^2 \log ^2 n)$ arithmetic operations. The algorithm is randomized, of Las Vegas type, allowing a failure with a probability at most $\delta < 1$, for any positive $\delta < 1$ such that $\log ({1 / \delta }) = O(\log n)$. Except for a narrow class of polynomials $p(x)$, these results can be also obtained for $ \epsilon $ such that $O(n^2 \log n)$.