Fast evaluation and root finding for polynomials with floating-point coefficients
International audience Evaluating or finding the roots of a polynomial $f(z) = f_0 + \cdots + f_d z^d$ with floating-point number coefficients is a ubiquitous problem. By using a piecewise approximation of $f$ obtained with a careful use of the Newton polygon of $f$, we improve state-of-the-art uppe...
Main Authors: | , |
---|---|
Other Authors: | , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2023
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-03980098 https://inria.hal.science/hal-03980098/document https://inria.hal.science/hal-03980098/file/preprint_pw.pdf |
id |
ftunilorrainehal:oai:HAL:hal-03980098v1 |
---|---|
record_format |
openpolar |
spelling |
ftunilorrainehal:oai:HAL:hal-03980098v1 2023-10-09T21:56:18+02:00 Fast evaluation and root finding for polynomials with floating-point coefficients Imbach, Rémi Moroz, Guillaume Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ) Inria Nancy - Grand Est Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO) Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) Tromsø, Norway 2023-07-24 https://inria.hal.science/hal-03980098 https://inria.hal.science/hal-03980098/document https://inria.hal.science/hal-03980098/file/preprint_pw.pdf en eng HAL CCSD info:eu-repo/semantics/altIdentifier/arxiv/2302.06244 ISBN: 979-8-4007-0039-2 hal-03980098 https://inria.hal.science/hal-03980098 https://inria.hal.science/hal-03980098/document https://inria.hal.science/hal-03980098/file/preprint_pw.pdf ARXIV: 2302.06244 http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation ISSAC 2023 https://inria.hal.science/hal-03980098 ISSAC 2023, Jul 2023, Tromsø, Norway Polynomial evaluation Complex root finding Condition number Newton polygon Floating-point arithmetic [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftunilorrainehal 2023-09-19T22:40:14Z International audience Evaluating or finding the roots of a polynomial $f(z) = f_0 + \cdots + f_d z^d$ with floating-point number coefficients is a ubiquitous problem. By using a piecewise approximation of $f$ obtained with a careful use of the Newton polygon of $f$, we improve state-of-the-art upper bounds on the number of operations to evaluate and find the roots of a polynomial. In particular, if the coefficients of $f$ are given with $m$ significant bits, we provide for the first time an algorithm that finds all the roots of $f$ with a relative condition number lower than $2^m$, using a number of bit operations quasi-linear in the bit-size of the floating-point representation of $f$. Notably, our new approach handles efficiently polynomials with coefficients ranging from $2^{-d}$ to $2^d$, both in theory and in practice. Conference Object Tromsø Université de Lorraine: HAL Norway Tromsø |
institution |
Open Polar |
collection |
Université de Lorraine: HAL |
op_collection_id |
ftunilorrainehal |
language |
English |
topic |
Polynomial evaluation Complex root finding Condition number Newton polygon Floating-point arithmetic [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
spellingShingle |
Polynomial evaluation Complex root finding Condition number Newton polygon Floating-point arithmetic [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Imbach, Rémi Moroz, Guillaume Fast evaluation and root finding for polynomials with floating-point coefficients |
topic_facet |
Polynomial evaluation Complex root finding Condition number Newton polygon Floating-point arithmetic [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
description |
International audience Evaluating or finding the roots of a polynomial $f(z) = f_0 + \cdots + f_d z^d$ with floating-point number coefficients is a ubiquitous problem. By using a piecewise approximation of $f$ obtained with a careful use of the Newton polygon of $f$, we improve state-of-the-art upper bounds on the number of operations to evaluate and find the roots of a polynomial. In particular, if the coefficients of $f$ are given with $m$ significant bits, we provide for the first time an algorithm that finds all the roots of $f$ with a relative condition number lower than $2^m$, using a number of bit operations quasi-linear in the bit-size of the floating-point representation of $f$. Notably, our new approach handles efficiently polynomials with coefficients ranging from $2^{-d}$ to $2^d$, both in theory and in practice. |
author2 |
Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ) Inria Nancy - Grand Est Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO) Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) |
format |
Conference Object |
author |
Imbach, Rémi Moroz, Guillaume |
author_facet |
Imbach, Rémi Moroz, Guillaume |
author_sort |
Imbach, Rémi |
title |
Fast evaluation and root finding for polynomials with floating-point coefficients |
title_short |
Fast evaluation and root finding for polynomials with floating-point coefficients |
title_full |
Fast evaluation and root finding for polynomials with floating-point coefficients |
title_fullStr |
Fast evaluation and root finding for polynomials with floating-point coefficients |
title_full_unstemmed |
Fast evaluation and root finding for polynomials with floating-point coefficients |
title_sort |
fast evaluation and root finding for polynomials with floating-point coefficients |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
https://inria.hal.science/hal-03980098 https://inria.hal.science/hal-03980098/document https://inria.hal.science/hal-03980098/file/preprint_pw.pdf |
op_coverage |
Tromsø, Norway |
geographic |
Norway Tromsø |
geographic_facet |
Norway Tromsø |
genre |
Tromsø |
genre_facet |
Tromsø |
op_source |
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation ISSAC 2023 https://inria.hal.science/hal-03980098 ISSAC 2023, Jul 2023, Tromsø, Norway |
op_relation |
info:eu-repo/semantics/altIdentifier/arxiv/2302.06244 ISBN: 979-8-4007-0039-2 hal-03980098 https://inria.hal.science/hal-03980098 https://inria.hal.science/hal-03980098/document https://inria.hal.science/hal-03980098/file/preprint_pw.pdf ARXIV: 2302.06244 |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
_version_ |
1779320926922342400 |