O(n log3 n) algorithm for the real root problem


Journal Article

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.

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • December 1, 1993

Published In

Start / End Page

  • 626 - 635

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus