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

DOI10.1016/J.JSC.2011.08.022MaRDI QIDQ655566zbMATH OpenOpenAlexFDO

Authors 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

adaptive analysiscomplexitycontinuous amortizationintegral analysisMahler-Davenport root boundsreal rootsroot isolationSqFreeEVAL algorithmSturm or Descartes methodssubdivision algorithmunivariate polynomial

Mathematics Subject Classification ID

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

Recommendations

• Near optimal subdivision algorithms for real root isolation
• Near optimal tree size bounds on a simple real root isolation algorithm
• Near optimal subdivision algorithms for real root isolation
• A simple but exact and efficient algorithm for complex root isolation
• Continuous amortization and extensions: with applications to bisection-based root isolation

Cites work

• A note on the complexity of real algebraic hypersurfaces
• A simple but exact and efficient algorithm for complex root isolation
• A survey of subdivision-based tools for surface modeling
• Adaptive isotopic approximation of nonsingular curves: the parametrizability and nonlocal isotopy approach
• Almost tight recursion tree bounds for the Descartes method
• Amortized bound for root isolation via Sturm sequences
• Complete subdivision algorithms, II
• Complexity of real root isolation using continued fractions
• Domain decomposition methods for a complementarity problem
• Efficient isolation of polynomial's real roots.
• scientific article; zbMATH DE number 54251 (Why is no real title available?)
• scientific article; zbMATH DE number 1253989 (Why is no real title available?)
• scientific article; zbMATH DE number 1157659 (Why is no real title available?)
• scientific article; zbMATH DE number 1952042 (Why is no real title available?)
• scientific article; zbMATH DE number 1446863 (Why is no real title available?)
• scientific article; zbMATH DE number 5019917 (Why is no real title available?)
• scientific article; zbMATH DE number 3281219 (Why is no real title available?)
• Interval arithmetic in cylindrical algebraic decomposition
• Localization of an algebraic hypersurface by the exclusion algorithm
• Methods of Search for Solving Polynomial Equations
• New bounds for the Descartes method
• Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
• On the complexity of real root isolation using continued fractions
• On the distance between the roots of a polynomial
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• Solving a Polynomial Equation: Some History and Recent Progress
• Sylvester-Habicht sequences and fast Cauchy index computation

Cited in

(20)

• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• SqFreeEVAL
• The complexity of subdivision for diameter-distance tests
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• On soft predicates in subdivision motion planning
• On the complexity of the Descartes method when using approximate arithmetic
• A symbolic-numerical algorithm for isolating real roots of certain radical expressions
• Continuous amortization and extensions: with applications to bisection-based root isolation
• Empirical study of an evaluation-based subdivision algorithm for complex root isolation
• Near optimal subdivision algorithms for real root isolation
• Amortized bound for root isolation via Sturm sequences
• Soft subdivision search in motion planning. II: Axiomatics
• Computing real roots of real polynomials
• Near optimal tree size bounds on a simple real root isolation algorithm
• A simple but exact and efficient algorithm for complex root isolation
• Certified simultaneous isotopic approximation of pairs of curves via subdivision
• Computing the intersection between a rational parametric curve and a rational parametric surface
• Range Functions of Any Convergence Order and Their Amortized Complexity Analysis
• Novel range functions via Taylor expansions and recursive Lagrange interpolation with application to real root isolation
• Certified simultaneous isotopic approximation of algebraic curves via subdivision

Describes a project that uses

Uses Software

• ISOLATE

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q655566)