On the complexity of the Descartes method when using approximate arithmetic
From MaRDI portal
Publication:2447639
DOI10.1016/j.jsc.2014.01.005zbMath1321.65080OpenAlexW1983396187MaRDI QIDQ2447639
Publication date: 28 April 2014
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jsc.2014.01.005
error boundcomplexity boundssquare-free polynomialroot isolationsubdivision methodsapproximate coefficientsDescartes method
Numerical computation of solutions to single equations (65H05) Real polynomials: location of zeros (26C10) Numerical computation of roots of polynomial equations (65H04)
Related Items (8)
Continuous amortization and extensions: with applications to bisection-based root isolation ⋮ A symbolic-numerical algorithm for isolating real roots of certain radical expressions ⋮ Improved bounds for the CF algorithm ⋮ A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration ⋮ Virtuous smoothing for global optimization ⋮ Root refinement for real polynomials using quadratic interval refinement ⋮ Computing real roots of real polynomials ⋮ Counting and Testing Dominant Polynomials
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic algorithm for isolating real roots of a real polynomial
- A general approach to isolating roots of a bitstream polynomial
- SqFreeEVAL: An (almost) optimal real-root isolation algorithm
- Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
- A worst-case bound for topology computation of algebraic curves
- On multiple roots in Descartes' rule and their distance to roots of higher derivatives
- Faster algorithms for computing Hong's bound on absolute positiveness
- Quasi-gcd computations
- Efficient isolation of polynomial's real roots.
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- A new proof of Vincent's theorem
- Numerical methods for roots of polynomials. II
- 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
- From approximate factorization to root isolation
- Solving a Polynomial Equation: Some History and Recent Progress
- An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
- When Newton meets Descartes
- Univariate real root isolation in multiple extension fields
- Efficient real root approximation
- Univariate real root isolation in an extension field
- A simple but exact and efficient algorithm for complex root isolation
- Computer Algebra in Scientific Computing
- Algorithms in real algebraic geometry
This page was built for publication: On the complexity of the Descartes method when using approximate arithmetic