A deterministic algorithm for isolating real roots of a real polynomial

DOI10.1016/j.jsc.2010.09.004zbMath1207.65048OpenAlexW1990564835MaRDI QIDQ607163

Kurt Mehlhorn, Michael Sagraloff

Publication date: 19 November 2010

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2010.09.004

zbMATH Keywords

algorithmreal polynomialroot isolationasymptotic complexitybitstream coefficientsDescartes' rule of signVincent-Collins-Akritas bisection algorithm

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04)

Related Items

Efficient Predicate Evaluation Using Randomized Degeneracy Detection, Improved bounds for the CF algorithm, Condition numbers for the cube. I: Univariate polynomials and hypersurfaces, Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers, On the complexity of the Descartes method when using approximate arithmetic, A general approach to isolating roots of a bitstream polynomial, From approximate factorization to root isolation with application to cylindrical algebraic decomposition, Univariate real root isolation in an extension field and applications, Logcf: an efficient tool for real root isolation, Counting and Testing Dominant Polynomials, On the determination of the number of positive and negative polynomial zeros and their isolation, Sampling polynomial trajectories for LTL verification

Uses Software

• CGAL
• ISOLATE
• na20

Cites Work

• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Faster algorithms for computing Hong's bound on absolute positiveness
• Quasi-gcd computations
• The fastest exact algorithms for the isolation of the real roots of a polynomial equation
• Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
• Efficient isolation of polynomial's real roots.
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• A new proof of Vincent's theorem
• Zur Abzählung der reellen Wurzeln algebraischer Gleichungen
• Complexity of real root isolation using continued fractions
• New bounds for the Descartes method
• Cylindrical algebraic decomposition using validated numerics
• On the complexity of real root isolation using continued fractions
• Modular algorithms in symbolic summation and symbolic integration
• Note on Vincent's theorem
• Almost tight recursion tree bounds for the Descartes method
• Exact geometric-topological analysis of algebraic surfaces
• Solving a Polynomial Equation: Some History and Recent Progress
• Computer Algebra in Scientific Computing
• Algorithms in real algebraic geometry
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item