Validated Root Enclosures for Interval Polynomials with Multiplicities
International audience Twenty years ago, Zeng [28, 30] proposed floating-point algorithms to compute multiple roots of univariate polynomials with real or complex coefficients beyond the so-called "attainable accuracy barrier". Based on these foundations, we propose a validated numeric poi...
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-04138791 https://hal.science/hal-04138791/document https://hal.science/hal-04138791/file/multrootval.pdf https://doi.org/10.1145/3597066.3597122 |
id |
ftunivlille:oai:HAL:hal-04138791v1 |
---|---|
record_format |
openpolar |
spelling |
ftunivlille:oai:HAL:hal-04138791v1 2024-06-23T07:57:12+00:00 Validated Root Enclosures for Interval Polynomials with Multiplicities Bréhard, Florent Poteaux, Adrien Soudant, Léo Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL) Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS) Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay) Tromso, Norway 2023-07-25 https://hal.science/hal-04138791 https://hal.science/hal-04138791/document https://hal.science/hal-04138791/file/multrootval.pdf https://doi.org/10.1145/3597066.3597122 en eng HAL CCSD info:eu-repo/semantics/altIdentifier/doi/10.1145/3597066.3597122 hal-04138791 https://hal.science/hal-04138791 https://hal.science/hal-04138791/document https://hal.science/hal-04138791/file/multrootval.pdf doi:10.1145/3597066.3597122 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess ISSAC'23 : International Symposium on Symbolic and Algebraic Computation 2023 https://hal.science/hal-04138791 ISSAC'23 : International Symposium on Symbolic and Algebraic Computation 2023, Jul 2023, Tromso, Norway. ⟨10.1145/3597066.3597122⟩ multiple roots of univariate polynomials fixed-point validation [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftunivlille https://doi.org/10.1145/3597066.3597122 2024-06-03T14:47:17Z International audience Twenty years ago, Zeng [28, 30] proposed floating-point algorithms to compute multiple roots of univariate polynomials with real or complex coefficients beyond the so-called "attainable accuracy barrier". Based on these foundations, we propose a validated numeric point of view on this problem. Our first contribution is an improvement of Zeng's multiplicity detection algorithm using a simple trick that allows us to recover much higher multiplicities. As our main contribution, we propose two floating-point validated algorithms to compute rigorous enclosures for multiple roots. They consist in carefully combining the ideas underlying Zeng's numerical algorithms with Newton-like fixed-point validation techniques. We also provide a prototype Julia implementation of these algorithms. Conference Object Tromso Tromso LillOA (HAL Lille Open Archive, Université de Lille) Norway Tromso ENVELOPE(16.546,16.546,68.801,68.801) Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation 90 99 |
institution |
Open Polar |
collection |
LillOA (HAL Lille Open Archive, Université de Lille) |
op_collection_id |
ftunivlille |
language |
English |
topic |
multiple roots of univariate polynomials fixed-point validation [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
spellingShingle |
multiple roots of univariate polynomials fixed-point validation [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Bréhard, Florent Poteaux, Adrien Soudant, Léo Validated Root Enclosures for Interval Polynomials with Multiplicities |
topic_facet |
multiple roots of univariate polynomials fixed-point validation [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
description |
International audience Twenty years ago, Zeng [28, 30] proposed floating-point algorithms to compute multiple roots of univariate polynomials with real or complex coefficients beyond the so-called "attainable accuracy barrier". Based on these foundations, we propose a validated numeric point of view on this problem. Our first contribution is an improvement of Zeng's multiplicity detection algorithm using a simple trick that allows us to recover much higher multiplicities. As our main contribution, we propose two floating-point validated algorithms to compute rigorous enclosures for multiple roots. They consist in carefully combining the ideas underlying Zeng's numerical algorithms with Newton-like fixed-point validation techniques. We also provide a prototype Julia implementation of these algorithms. |
author2 |
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL) Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS) Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay) |
format |
Conference Object |
author |
Bréhard, Florent Poteaux, Adrien Soudant, Léo |
author_facet |
Bréhard, Florent Poteaux, Adrien Soudant, Léo |
author_sort |
Bréhard, Florent |
title |
Validated Root Enclosures for Interval Polynomials with Multiplicities |
title_short |
Validated Root Enclosures for Interval Polynomials with Multiplicities |
title_full |
Validated Root Enclosures for Interval Polynomials with Multiplicities |
title_fullStr |
Validated Root Enclosures for Interval Polynomials with Multiplicities |
title_full_unstemmed |
Validated Root Enclosures for Interval Polynomials with Multiplicities |
title_sort |
validated root enclosures for interval polynomials with multiplicities |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
https://hal.science/hal-04138791 https://hal.science/hal-04138791/document https://hal.science/hal-04138791/file/multrootval.pdf https://doi.org/10.1145/3597066.3597122 |
op_coverage |
Tromso, Norway |
long_lat |
ENVELOPE(16.546,16.546,68.801,68.801) |
geographic |
Norway Tromso |
geographic_facet |
Norway Tromso |
genre |
Tromso Tromso |
genre_facet |
Tromso Tromso |
op_source |
ISSAC'23 : International Symposium on Symbolic and Algebraic Computation 2023 https://hal.science/hal-04138791 ISSAC'23 : International Symposium on Symbolic and Algebraic Computation 2023, Jul 2023, Tromso, Norway. ⟨10.1145/3597066.3597122⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1145/3597066.3597122 hal-04138791 https://hal.science/hal-04138791 https://hal.science/hal-04138791/document https://hal.science/hal-04138791/file/multrootval.pdf doi:10.1145/3597066.3597122 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1145/3597066.3597122 |
container_title |
Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation |
container_start_page |
90 |
op_container_end_page |
99 |
_version_ |
1802650739912212480 |