Algorithms for Accurate, Validated and Fast Polynomial EvaluationReportar como inadecuado

Algorithms for Accurate, Validated and Fast Polynomial Evaluation - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Stef Graillat - Philippe Langlois - Nicolas Louvet -



Documentos relacionados