Univariate real root isolation over a single logarithmic extension of real algebraic numbers

Adam Strzebonski 1 Elias Tsigaridas 2
1 Wolfram Research
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial B ∈ L[x], where L = Q[lg(α)] and α is a positive real algebraic number. The algorithm approximates the coefficients of B up to a sufficient accuracy and then solves the approximate polynomial. For this we derive worst case (aggregate) separation bounds. We also estimate the expected number of real roots when we draw the coefficients from a specific distribution and illustrate our results experimentally. A generalization to bivariate polynomial systems is also presented. We implemented the algorithm in C as part of the core library of mathematica for the case B ∈ Z[lg(q)][x] where q is positive rational number and we demonstrate its efficiency over various data sets.
Type de document :
Communication dans un congrès
Ilias S. Kotsireas; Edgar Martínez-Moro. ACA 2015 - Applications of Computer Algebra, Jul 2015, Kalamata, Greece. Springer, Applications of Computer Algebra: July 20-23, 2015, Kalamata, Greece, 198, pp.425-445, 2017, Springer Proceedings in Mathematics & Statistics. 〈10.1007/978-3-319-56932-1_27〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01001820
Contributeur : Elias Tsigaridas <>
Soumis le : samedi 24 décembre 2016 - 08:26:01
Dernière modification le : mardi 11 décembre 2018 - 01:22:38
Document(s) archivé(s) le : mardi 21 mars 2017 - 11:44:54

Fichiers

st-rs-log (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UPMC | LIP6 | INRIA | INRIA-ROCQ | SORBONNE-UNIVERSITE

Citation

Adam Strzebonski, Elias Tsigaridas. Univariate real root isolation over a single logarithmic extension of real algebraic numbers. Ilias S. Kotsireas; Edgar Martínez-Moro. ACA 2015 - Applications of Computer Algebra, Jul 2015, Kalamata, Greece. Springer, Applications of Computer Algebra: July 20-23, 2015, Kalamata, Greece, 198, pp.425-445, 2017, Springer Proceedings in Mathematics & Statistics. 〈10.1007/978-3-319-56932-1_27〉. 〈hal-01001820v3〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

346

Téléchargements de fichiers

141

Contact


archive-ouverte@inria.fr