A near-optimal algorithm for computing real roots of sparse polynomials

DOI10.1145/2608628.2608632zbMath1325.65068arXiv1401.6011OpenAlexW2059357470MaRDI QIDQ3452416

Michael Sagraloff

Publication date: 11 November 2015

Published in: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.6011

zbMATH Keywords

numerical algorithmsarithmetic complexitybit complexityroot isolationsparse polynomialsroot refinement

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items (6)

Bounded-degree factors of lacunary multivariate polynomials ⋮ SOME ANALYTICAL AND NUMERICAL RESULTS FOR THE ZEROS OF A CLASS OF FIBONACCI-LIKE POLYNOMIALS ⋮ Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields ⋮ A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration ⋮ Computing real roots of real polynomials ⋮ Root separation for trinomials

Uses Software

• Jordan

Cites Work

• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• The Jordan Curve Theorem, Formally and Informally
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic
• Unnamed Item
• Unnamed Item

This page was built for publication: A near-optimal algorithm for computing real roots of sparse polynomials