Algorithms for Accurate, Validated and Fast Polynomial EvaluationReport as inadecuate

Algorithms for Accurate, Validated and Fast Polynomial Evaluation - Download this document for free, or read online. Document in PDF available to download.

1 PEQUAN - Performance et Qualité des Algorithmes Numériques LIP6 - Laboratoire d-Informatique de Paris 6 2 ELIAUS - Electronique, Informatique, Automatique et Systèmes 3 ARENAIRE - Computer arithmetic Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l-Informatique du Parallélisme

Abstract : We survey a class of algorithms to evaluate polynomials with floating point coefficients and for computation performed with IEEE-754 floating point arithmetic. The principle is to apply, once or recursively, an error-free transformation of the polynomial evaluation with the Horner algorithm and to accurately sum the final decomposition. These compensated algorithms are as accurate as the Horner algorithm performed in K times the working precision, for K an arbitrary integer. We prove this accuracy property with an \apriori error analysis. We also provide validated dynamic bounds and apply these results to compute a faithfully rounded evaluation. These compensated algorithms are fast. We illustrate their practical efficiency with numerical experiments on significant environments. Comparing to existing alternatives these K-times compensated algorithms are competitive for K up to 4, i.e., up to 212 mantissa bits.

Keywords : IEEE-754 floating point arithmetic Accurate polynomial evaluation compensated algorithms

Author: Stef Graillat - Philippe Langlois - Nicolas Louvet -



Related documents