O(n log3 n) algorithm for the real root problem
Given a univariate complex polynomial f(x) of degree n with rational coefficients expressed as a ratio of two integers <2m, the root problem is to find all the roots of f(x) up to specified precision 2-μ. In this paper we assume the arithmetic model for computation. We give an algorithm for the real-root problem: where all the roots of the polynomial are real. Our real root algorithm has time cost of O(n log2 n(log n+log b)), where b = m+μ, thus has time bound O(n log3 n) even in the case of high precision m+μ≤nO(1). This is within a small polylog factor of optimality, thus (perhaps surprisingly) upper bounding the arithmetic complexity of our real root problem to nearly the same as basic arithmetic operations on polynomials. We require only π = O(n(μ+m+n)) bits of precision to carry out our computations. The Boolean complexity of our algorithm is a multiplicative factor of M(π) = O(π(log π) log log π) more.
