Improved bounds for the CF algorithm

Elias Tsigaridas 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using the classic variant of the continued fraction algorithm (CF), introduced by Akritas. %% We compute a lower bound on the positive real roots of univariate polynomials using exponential search. This allows us to derive a worst case bound of $\sOB( d^4\tau^2)$ for isolating the real roots of a polynomial with integer coefficients using the {\em classic variant of CF}, where $d$ is the degree of the polynomial and $\tau$ the maximum bitsize of its coefficients. This improves the previous bound of Sharma by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray for another variant of CF which is combined with subdivision; it also matches the worst case bound of the classical subdivision-based solvers \func{sturm}, \func{descartes}, and \func{bernstein}.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, pp.1-12
Liste complète des métadonnées

https://hal.inria.fr/hal-00776230
Contributeur : Elias Tsigaridas <>
Soumis le : mardi 15 janvier 2013 - 11:42:43
Dernière modification le : lundi 9 mars 2015 - 15:12:37

Fichier

et-improve-bd-cf.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00776230, version 1

Collections

Citation

Elias Tsigaridas. Improved bounds for the CF algorithm. Theoretical Computer Science, Elsevier, 2012, pp.1-12. <hal-00776230>

Partager

Métriques

Consultations de
la notice

133

Téléchargements du document

121