On the computing time of the continued fractions method

DOI10.1016/j.jsc.2012.03.003zbMath1250.65066OpenAlexW2005451469MaRDI QIDQ438690

George E. Collins, Werner Krandick

Publication date: 31 July 2012

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

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

zbMATH Keywords

symmetric functionsFibonacci numberssubadditivitycomputing time lower boundscontinued fractions methodloxodromic transformationsmatrix factorization algorithmMignotte polynomialspolynomial real root isolation

Mathematics Subject Classification ID

Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Continued fractions (11A55) Real polynomials: location of zeros (26C10) Complexity and performance of numerical algorithms (65Y20) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Numerical computation of roots of polynomial equations (65H04)

Related Items (2)

Continued fraction real root isolation using the Hong root bound ⋮ On the maximum computing time of the bisection method for real root isolation

Uses Software

• OEIS
• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The fastest exact algorithms for the isolation of the real roots of a polynomial equation
• Efficient isolation of polynomial's real roots.
• A new proof of Vincent's theorem
• Zur Abzählung der reellen Wurzeln algebraischer Gleichungen
• On the distance between the roots of a polynomial
• Complexity of real root isolation using continued fractions
• New bounds for the Descartes method
• On the complexity of real root isolation using continued fractions
• Almost tight recursion tree bounds for the Descartes method
• Advances on the Continued Fractions Method Using Better Estimations of Positive Root Bounds
• A short note on a new method for polynomial real root isolation
• On the Problem of Runs
• The Computing Time of the Euclidean Algorithm
• Architecture-aware classical Taylor shift by 1

This page was built for publication: On the computing time of the continued fractions method