On Isolating Roots in a Multiple Field Extension - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

On Isolating Roots in a Multiple Field Extension

Résumé

We address univariate root isolation when the polynomial's coefficients are in a multiple field extension. We consider a polynomial $F \in L[Y]$, where $L$ is a multiple algebraic extension of $\mathbb{Q}$. We provide aggregate bounds for $F$ and algorithmic and bit-complexity results for the problem of isolating its roots. For the latter problem we follow a common approach based on univariate root isolation algorithms. For the particular case where $F$ does not have multiple roots, we achieve a bit-complexity in $\tilde{\mathcal{O}}_B(n d^{2n+2}(d+n\tau))$, where $d$ is the total degree and $\tau$ is the bitsize of the involved polynomials. In the general case we need to enhance our algorithm with a preprocessing step that determines the number of distinct roots of $F$. We follow a numerical, yet certified, approach that has bit-complexity $\tilde{\mathcal{O}}_B(n^2d^{3n+3}\tau + n^3 d^{2n+4}\tau)$.
Fichier principal
Vignette du fichier
Isolating_roots_in_a_multiple_field_extension__HAL_.pdf (612.57 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04116621 , version 1 (05-06-2023)

Licence

Paternité

Identifiants

Citer

Christina Katsamaki, Fabrice Rouillier. On Isolating Roots in a Multiple Field Extension. ISSAC '23: 2023 International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway. pp.363-371, ⟨10.1145/3597066.3597107⟩. ⟨hal-04116621⟩
36 Consultations
24 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More