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 |
id |
ftsorbonneuniv:oai:HAL:hal-04116621v1 |
---|---|
record_format |
openpolar |
spelling |
ftsorbonneuniv:oai:HAL:hal-04116621v1 2024-05-19T07:49:30+00:00 On Isolating Roots in a Multiple Field Extension Katsamaki, Christina Rouillier, Fabrice Sorbonne Université (SU) OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN) Inria de Paris Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)) Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité) Tromso, Norway 2023-07-24 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 en eng HAL CCSD ACM info:eu-repo/semantics/altIdentifier/arxiv/2306.04271 info:eu-repo/semantics/altIdentifier/doi/10.1145/3597066.3597107 hal-04116621 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 ARXIV: 2306.04271 doi:10.1145/3597066.3597107 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess ISSAC '23: 2023 International Symposium on Symbolic and Algebraic Computation https://hal.science/hal-04116621 ISSAC '23: 2023 International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway. pp.363-371, ⟨10.1145/3597066.3597107⟩ Root isolation Field extension Bit-complexity [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftsorbonneuniv https://doi.org/10.1145/3597066.3597107 2024-05-02T02:04:37Z 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)$. Conference Object Tromso Tromso HAL Sorbonne Université Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation 363 371 |
institution |
Open Polar |
collection |
HAL Sorbonne Université |
op_collection_id |
ftsorbonneuniv |
language |
English |
topic |
Root isolation Field extension Bit-complexity [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
spellingShingle |
Root isolation Field extension Bit-complexity [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Katsamaki, Christina Rouillier, Fabrice On Isolating Roots in a Multiple Field Extension |
topic_facet |
Root isolation Field extension Bit-complexity [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
description |
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)$. |
author2 |
Sorbonne Université (SU) OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN) Inria de Paris Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)) Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité) |
format |
Conference Object |
author |
Katsamaki, Christina Rouillier, Fabrice |
author_facet |
Katsamaki, Christina Rouillier, Fabrice |
author_sort |
Katsamaki, Christina |
title |
On Isolating Roots in a Multiple Field Extension |
title_short |
On Isolating Roots in a Multiple Field Extension |
title_full |
On Isolating Roots in a Multiple Field Extension |
title_fullStr |
On Isolating Roots in a Multiple Field Extension |
title_full_unstemmed |
On Isolating Roots in a Multiple Field Extension |
title_sort |
on isolating roots in a multiple field extension |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
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 |
op_coverage |
Tromso, Norway |
genre |
Tromso Tromso |
genre_facet |
Tromso Tromso |
op_source |
ISSAC '23: 2023 International Symposium on Symbolic and Algebraic Computation https://hal.science/hal-04116621 ISSAC '23: 2023 International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway. pp.363-371, ⟨10.1145/3597066.3597107⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/arxiv/2306.04271 info:eu-repo/semantics/altIdentifier/doi/10.1145/3597066.3597107 hal-04116621 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 ARXIV: 2306.04271 doi:10.1145/3597066.3597107 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1145/3597066.3597107 |
container_title |
Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation |
container_start_page |
363 |
op_container_end_page |
371 |
_version_ |
1799468002691776512 |