Fast evaluation and root finding for polynomials with floating-point coefficients

DOI10.1145/3597066.3597112MaRDI QIDQ6060390zbMATH OpenOpenAlexWikidataFDO

Publication date 3 November 2023

Published in Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.06244

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Abstract: Evaluating or finding the roots of a polynomial

f (z) = f_{0} + c d o t s + 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.

Cites work

Cited in

(6)

This page was built for publication: Fast evaluation and root finding for polynomials with floating-point coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6060390)