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 |
| Summary: | 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. |
|---|