On Isolating Roots in a Multiple Field Extension
International audience 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-compl...
| Published in: | Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation |
|---|---|
| Main Authors: | , |
| Other Authors: | , , , , |
| Format: | Conference Object |
| Language: | English |
| Published: |
HAL CCSD
2023
|
| Subjects: | |
| Online Access: | https://hal.science/hal-04116621 https://hal.science/hal-04116621/document https://hal.science/hal-04116621/file/Isolating_roots_in_a_multiple_field_extension__HAL_.pdf https://doi.org/10.1145/3597066.3597107 |
| Summary: | International audience 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)$. |
|---|