An O(n^1+ε log B) algorithm for the complex roots problem

Abstract

Given a univariate polynomial f(z) of degree n with complex coefficients, whose real ana imaginary parts can be expressed as a ratio of two integers 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, for any ε > 0, an algorithm which has complexity O(n1+ε logb), where b = m + μ. This improves on the previous best known algorithm for the problem which has complexity O(n2 log 6). We claim it then follows from the fact that we can bound the precision required in all the arithmetic computations, that the complexity of our algorithm in the Boolean model of computation is O (n2+ε(n + b) log2 blog log 6). The details of the proof of this claim will appear in a subsequent version of this paper. We introduce some techniques (splitting sets and binary search for 'centered' points) which hinge on a recent result of Coppersmith and Neff [CN 94], along with an unbalanced divide and conquer strategy.