# A note on the complexity of univariate root isolation

2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper presents the average-case bit complexity of subdivision-based univariate solvers, namely those named after Sturm, Descartes, and Bernstein. By real solving we mean real root isolation. We prove bounds of $\sOB(N^5)$ for all methods, where $N$ bounds the polynomial degree and the coefficient bitsize, whereas their worst-case complexity is in $\sOB(N^6)$. In the case of the Sturm solver, our bound depends on the number of real roots. Our work is a step towards understanding the practical complexity of real root isolation. This enables a better juxtaposition against numerical solvers, the latter having worst-case complexity in $\sOB(N^4)$. % Our approach extends to complex root isolation, where we offer a simple proof leading to bounds % for the number of steps that the subdivision algorithm performs on the worst and average-case complexities of $\sOB(N^7 )$ and $\sOB(N^6)$ respectively, where the latter is output-sensitive.
Keywords :
Type de document :
Rapport
[Research Report] RR-6043, INRIA. 2006, pp.18
Domaine :

Littérature citée [34 références]

https://hal.inria.fr/inria-00116985
Contributeur : Elias Tsigaridas <>
Soumis le : dimanche 10 décembre 2006 - 18:05:28
Dernière modification le : samedi 27 janvier 2018 - 01:30:53
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 11:58:11

### Fichier

RR-6043.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00116985, version 5

### Citation

Ioannis Emiris, Elias P. Tsigaridas. A note on the complexity of univariate root isolation. [Research Report] RR-6043, INRIA. 2006, pp.18. 〈inria-00116985v5〉

### Métriques

Consultations de la notice

## 300

Téléchargements de fichiers