On solving univariate sparse polynomials in logarithmic time Academic Article

abstract

• Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m = 3 we can approximate within all the roots of f in the interval [0,R] using just O(log(D)log(D log R/)) arithmetic operations. In particular, we can count the number of roots in any bounded interval using just O(log2 D) arithmetic operations. Our speed-ups are significant and near-optimal: The asymptotically sharpest previous complexity upper bounds for both problems were super-linear in D, while our algorithm has complexity close to the respective complexity lower bounds. We also discuss conditions under which our algorithms can be extended to general m, and a connection to a real analogue of Smale's 17th Problem. 2004 Elsevier Inc.All rights reserved.

authors

• Rojas, Joseph

published proceedings

• JOURNAL OF COMPLEXITY

author list (cited authors)

• Rojas, J. M., & Ye, Y. Y.

citation count

• 11

complete list of authors

• Rojas, JM||Ye, YY

publication date

• January 2005

publisher

• Elsevier  Publisher

published in

• Journal of Complexity  Journal

keywords

• Alpha Theory
• Approximate Root
• Complexity
• Computational Real Algebraic Geometry
• Discriminant
• Few-nomial
• Lacunary Polynomial
• Logarithmic
• M-nomial
• Newton's Method
• Real Root Counting
• Smale's 17th Problem
• Sparse Polynomial
• Speed Up
• Trinomial

Digital Object Identifier (DOI)

• 10.1016/j.jco.2004.03.004

start page

• 87

end page

• 110

volume

• 21

issue

• 1

URL

• http://dx.doi.org/10.1016/j.jco.2004.03.004