An efficient algorithm for the complex roots problem

Given a univariate polynomial f(z) of degree n with complex coefficients, whose norms are less than 2m in magnitude, the root problem is to find all the roots of f(z) up to specified precision 2-μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexity O(n log5 n log B), where b = χ + μ, and χ = max{n, m}. This improves on the previous best known algorithm of Pan for the problem, which has complexity O(n2 log2 n log(m + μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation of f, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = [n(B + log n + 3)] bits of the binary representations of the real and imaginary parts of each of the coefficients of f. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where φ = π + 2n2χ + 3(n + log n + 1) + n2 + 2 log n) + log log n. and π = μ 2n + nχ + log log n + 5. Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor of M(φ) (where M(ψ) = O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and "centered" points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel time O(log6 n log B) using n processors. © 1996 Academic Press, Inc.

Duke Scholars

Author John H. Reif Computer Science