An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem

Given a univariate polynomial f(z) of degree n with complex coefficients, whose real and imaginary parts can be expressed as a ratio of two integers less than 2/sup m/ in magnitude, the root problem is to find all the roots of f(z) up to specified precision 2/sup -/spl mu//. Assuming the arithmetic model for computation, we provide, for any /spl epsiv/>0, an algorithm which has complexity O(n/sup 1+/spl epsiv// log b), where b=m+/spl mu/. This improves on the previous best known algorithm for the problem which has complexity O(n/sup 2/ log b). We claim it that it 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(n/sup 2+/spl epsiv//(n+b) log/sup 2/ b log log b). >

Authors

• C. Andrew Neff
• John H. Reif

Keywords

• Arithmetic
• Computational modeling
• Polynomials
• Computer science
• Information services
• Web sites
• Internet
• Fasteners
• Read-write memory
• Subcontracting
• Imaginary Part
• Divide-and-conquer
• Binary Search
• Univariate Polynomial
• Central Point
• Proof Of Theorem
• Finite Set
• Relative Length
• Positive Real
• Number Of Roots
• Arithmetic Operations
• Outer Radius
• Real Roots
• Rational Numbers
• Split Point
• Split Set
• Root-finding
• Constants C1
• Asymptotic Complexity
• Constants C2