Complexity of real root isolation using continued fractions

DOI10.1016/j.tcs.2008.09.017zbMath1158.68055OpenAlexW2048184489MaRDI QIDQ2378508

Vikram Sharma

Publication date: 8 January 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.017

zbMATH Keywords

continued fractionspolynomial real root isolationDavenport-Mahler boundthe Descartes' rule of signs

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Related Items (18)

A symbolic-numerical algorithm for isolating real roots of certain radical expressions ⋮ A deterministic algorithm for isolating real roots of a real polynomial ⋮ Improved bounds for the CF algorithm ⋮ A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration ⋮ On the computing time of the continued fractions method ⋮ On the complexity of the Descartes method when using approximate arithmetic ⋮ A general approach to isolating roots of a bitstream polynomial ⋮ SqFreeEVAL: An (almost) optimal real-root isolation algorithm ⋮ Estimations of positive roots of polynomials ⋮ Computing real roots of real polynomials ⋮ Continued fraction real root isolation using the Hong root bound ⋮ A quadratic clipping step with superquadratic convergence for bivariate polynomial systems ⋮ On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers ⋮ Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach ⋮ Faster algorithms for computing Hong's bound on absolute positiveness ⋮ Logcf: an efficient tool for real root isolation ⋮ On the Complexity of Reliable Root Approximation ⋮ A Lower Bound for Computing Lagrange’s Real Root Bound

Uses Software

• na20

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implementations of a new theorem for computing bounds for positive roots of polynomials
• Bounds for positive roots of polynomials
• Bounds for absolute positiveness of multivariate polynomials
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• A new proof of Vincent's theorem
• New bounds for the Descartes method
• On the complexity of real root isolation using continued fractions
• Note on Vincent's theorem
• Almost tight recursion tree bounds for the Descartes method
• Polynomial Minimum Root Separation
• On the Problem of Runs
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
• Rational approximations to algebraic numbers
• Algorithms in real algebraic geometry

This page was built for publication: Complexity of real root isolation using continued fractions