Univariate real root isolation in an extension field and applications

Adam Strzebonski 1 Elias Tsigaridas 2
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 in $B_{\alpha} \in L[y]$, where $L=\QQ(\alpha)$ is a simple algebraic extension of the rational numbers. We revisit two approaches for the problem. In the first approach, using resultant computations, we perform a reduction to a polynomial with integer coefficients and we deduce a bound of $\sOB(N^{8})$ for isolating the real roots of $B_{\alpha}$, where $N$ is an upper bound on all the quantities (degree and bitsize) of the input polynomials. The bound becomes $\sOB(N^{7})$ if we use Pan's algorithm for isolating the real roots. %% In the second approach we isolate the real roots working directly on the polynomial of the input. We compute improved separation bounds for the roots and we prove that they are optimal, under mild assumptions. For isolating the real roots we consider a modified Sturm algorithm, and a modified version of \func{descartes}' algorithm. For the former we prove a Boolean complexity bound of $\sOB(N^{12})$ and for the latter a bound of $\sOB(N^{5})$. %% We present aggregate separation bounds and complexity results for isolating the real roots of all polynomials $B_{\alpha_k}$, when $\alpha_k$ runs over all the real conjugates of $\alpha$. We show that we can isolate the real roots of all polynomials in $\sOB(N^5)$. %% Finally, we implemented the algorithms in \func{C} as part of the core library of \mathematica and we illustrate their efficiency over various data sets.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, In press
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01248390
Contributeur : Elias Tsigaridas <>
Soumis le : jeudi 14 décembre 2017 - 12:57:55
Dernière modification le : mercredi 21 mars 2018 - 18:58:22

Fichier

st-rsef-jsc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01248390, version 2

Collections

Citation

Adam Strzebonski, Elias Tsigaridas. Univariate real root isolation in an extension field and applications. Journal of Symbolic Computation, Elsevier, In press. 〈hal-01248390v2〉

Partager

Métriques

Consultations de la notice

82

Téléchargements de fichiers

23