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