On solving univariate sparse polynomials in logarithmic time

DOI10.1016/j.jco.2004.03.004zbMath1101.68610OpenAlexW2108397696MaRDI QIDQ1763426

Yinyu Ye, J. Maurice Rojas

Publication date: 22 February 2005

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2004.03.004

zbMATH Keywords

Newton's methodComplexityTrinomialDiscriminantSpeed upAlpha theoryApproximate rootComputational real algebraic geometryFewnomialLacunary polynomialLogarithmicm-nomialReal root countingSmale's 17th ProblemSparse polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\), Root separation for trinomials, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields

Uses Software

• Kronecker

Cites Work

• A tight bound for approximating the square root
• High probability analysis of the condition number of sparse polynomial systems
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Combining binary search and Newton's method to compute real roots for a class of real functions
• Complexity of Bezout's theorem. V: Polynomial time
• Counting real connected components of trinomial curve intersections and \(m\)-nomial hypersurfaces
• Mathematical problems for the next century
• Complexity of the Havas, Majewski, Matthews LLL Hermite normal form algorithm
• Some speed-ups and speed limits for real algebraic geometry
• Solving degenerate sparse polynomial systems faster
• An efficient algorithm for the complex roots problem
• Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• On asymptotic estimates for arithmetic cost functions
• Asymptotic acceleration of solving multivariate polynomial systems of equations
• Accelerated Solution of Multivariate Polynomial Systems of Equations
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The cost of computing integers
• Sylvester-Habicht sequences and fast Cauchy index computation
• A Gröbner free alternative for polynomial system solving
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item