Improved bounds for the CF algorithm

DOI10.1016/J.TCS.2012.10.022MaRDI QIDQ385006zbMATH OpenOpenAlexFDO

Authors Elias P. Tsigaridas

Publication date 29 November 2013

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

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

Mathematics Subject Classification ID

Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• Complexity of real root isolation using continued fractions
• Advances on the Continued Fractions Method Using Better Estimations of Positive Root Bounds
• Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
• Logcf: an efficient tool for real root isolation
• On the complexity of real root isolation using continued fractions

Cites work

• A deterministic algorithm for isolating real roots of a real polynomial
• A new proof of Vincent's theorem
• A worst-case bound for topology computation of algebraic curves
• Almost tight recursion tree bounds for the Descartes method
• Amortized bound for root isolation via Sturm sequences
• An implementation of Vincent's theorem
• Bounds for absolute positiveness of multivariate polynomials
• Complexity of real root isolation using continued fractions
• Efficient isolation of polynomial's real roots.
• Faster algorithms for computing Hong's bound on absolute positiveness
• scientific article; zbMATH DE number 3846864 (Why is no real title available?)
• scientific article; zbMATH DE number 3959523 (Why is no real title available?)
• scientific article; zbMATH DE number 42630 (Why is no real title available?)
• scientific article; zbMATH DE number 52304 (Why is no real title available?)
• scientific article; zbMATH DE number 1253962 (Why is no real title available?)
• scientific article; zbMATH DE number 784876 (Why is no real title available?)
• scientific article; zbMATH DE number 1446863 (Why is no real title available?)
• Implementations of a new theorem for computing bounds for positive roots of polynomials
• New bounds for the Descartes method
• On the complexity of real root isolation using continued fractions
• On the complexity of the Descartes method when using approximate arithmetic
• Optimal search for rationals
• Random polynomials and expected complexity of bisection methods for real solving
• Real Algebraic Numbers: Complexity Analysis and Experimentation
• Solving a Polynomial Equation: Some History and Recent Progress
• Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• When Newton meets Descartes

Cited in

(6)

• A tighter bound for FFd algorithm
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• Complexity of real root isolation using continued fractions
• Advances on the Continued Fractions Method Using Better Estimations of Positive Root Bounds
• Improving the performance of the continued fractions method using new bounds of positive roots
• Complexity of real root isolation using continued fractions

Describes a project that uses

Uses Software

• ISOLATE

This page was built for publication: Improved bounds for the CF algorithm

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