A near-optimal algorithm for computing real roots of sparse polynomials
From MaRDI portal
Publication:3452416
DOI10.1145/2608628.2608632zbMath1325.65068arXiv1401.6011OpenAlexW2059357470MaRDI QIDQ3452416
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
numerical algorithmsarithmetic complexitybit complexityroot isolationsparse polynomialsroot refinement
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
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