Conference
Fast evaluation and root finding for polynomials with floating-point coefficients
| العنوان: | 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) |
| المصدر: | 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 |
| بيانات النشر: | HAL CCSD |
| سنة النشر: | 2023 |
| المجموعة: | Université de Lorraine: HAL |
| مصطلحات موضوعية: | Polynomial evaluation, Complex root finding, Condition number, Newton polygon, Floating-point arithmetic, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] |
| جغرافية الموضوع: | Tromsø, Norway |
| الوصف: | 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 |
| اللغة: | English |
| Relation: | info:eu-repo/semantics/altIdentifier/arxiv/2302.06244; ARXIV: 2302.06244 |
| الاتاحة: | https://inria.hal.science/hal-03980098 https://inria.hal.science/hal-03980098v1/document https://inria.hal.science/hal-03980098v1/file/preprint_pw.pdf |
| Rights: | http://creativecommons.org/licenses/by/ ; info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.15A9FA7C |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |