Real Algebraic Numbers: Complexity Analysis and Experimentations

Ioannis Z. Emiris 1 Bernard Mourrain 1 Elias P. Tsigaridas 1
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree $d$, with integer coefficients of bit size $\le\tau$, using Sturm (-Habicht) sequences and the Bernstein subdivision solver. In particular, we unify and simplify the analysis of both methods and we give an asymptotic complexity bound of $\sOB( d^4 \tau^2)$. This matches the best known bounds. Moreover, we generalize this to cover the non-squarefree polynomials and show that within the same complexity we can also compute the multiplicities of the roots. We also consider algorithms for sign evaluation, comparison of real algebraic numbers and simultaneous inequalities (SI) and we improve the known bounds at least by a factor of $d$. Finally, we present our C++ implementation in Synaps and experiments on various data sets.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071370
Contributor : Bernard Mourrain <>
Submitted on : Tuesday, May 23, 2006 - 4:56:35 PM
Last modification on : Wednesday, April 17, 2019 - 4:08:00 PM
Document(s) archivé(s) le : Sunday, April 4, 2010 - 10:07:33 PM

Identifiers

  • HAL Id : inria-00071370, version 1

Collections

Citation

Ioannis Z. Emiris, Bernard Mourrain, Elias P. Tsigaridas. Real Algebraic Numbers: Complexity Analysis and Experimentations. Reliable Implementations of Real Number Algorithms: Theory and Practice, 2008, Dagsthul, Germany. pp.57-82. ⟨inria-00071370⟩

Share

Metrics

Record views

318

Files downloads

266