SqFreeEVAL: An (almost) optimal real-root isolation algorithm

DOI10.1016/j.jsc.2011.08.022zbMath1269.65046OpenAlexW2084184830MaRDI QIDQ655566

Michael A. Burr, Felix Krahmer

Publication date: 4 January 2012

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

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

zbMATH Keywords

complexityunivariate polynomialsubdivision algorithmreal rootscontinuous amortizationroot isolationadaptive analysisintegral analysisMahler-Davenport root boundsSqFreeEVAL algorithmSturm or Descartes methods

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 (12)

Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ Soft Subdivision Search in Motion Planning, II: Axiomatics ⋮ A symbolic-numerical algorithm for isolating real roots of certain radical expressions ⋮ A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration ⋮ Certified simultaneous isotopic approximation of pairs of curves via subdivision ⋮ The complexity of subdivision for diameter-distance tests ⋮ Computing the intersection between a rational parametric curve and a rational parametric surface ⋮ On the complexity of the Descartes method when using approximate arithmetic ⋮ Computing real roots of real polynomials ⋮ From approximate factorization to root isolation with application to cylindrical algebraic decomposition ⋮ SqFreeEVAL ⋮ On soft predicates in subdivision motion planning

Uses Software

• ISOLATE

Cites Work

• A note on the complexity of real algebraic hypersurfaces
• Localization of an algebraic hypersurface by the exclusion algorithm
• Efficient isolation of polynomial's real roots.
• Interval arithmetic in cylindrical algebraic decomposition
• On the distance between the roots of a polynomial
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Complexity of real root isolation using continued fractions
• New bounds for the Descartes method
• On the complexity of real root isolation using continued fractions
• Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
• Almost tight recursion tree bounds for the Descartes method
• Domain Decomposition Methods for a Complementarity Problem*
• Solving a Polynomial Equation: Some History and Recent Progress
• A simple but exact and efficient algorithm for complex root isolation
• Complete subdivision algorithms, II
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• Adaptive isotopic approximation of nonsingular curves
• Methods of Search for Solving Polynomial Equations
• Sylvester-Habicht sequences and fast Cauchy index computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: SqFreeEVAL: An (almost) optimal real-root isolation algorithm