License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05391.3
URN: urn:nbn:de:0030-drops-4423
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/442/
Go to the corresponding Portal |
Langlois, Philippe ;
Graillat, Stef ;
Louvet, Nicolas
Compensated Horner Scheme
Abstract
Using error-free transformations, we improve the classic Horner Scheme (HS)
to evaluate (univariate) polynomials in floating point arithmetic.
We prove that this Compensated Horner Scheme (CHS) is as accurate as HS
performed with twice the working precision.
Theoretical analysis and experiments exhibit a reasonable running time
overhead being also more interesting than double-double implementations.
We introduce a dynamic and validated error bound of the CHS computed value.
The talk presents these results together with a survey about error-free
transformations and related hypothesis.
BibTeX - Entry
@InProceedings{langlois_et_al:DagSemProc.05391.3,
author = {Langlois, Philippe and Graillat, Stef and Louvet, Nicolas},
title = {{Compensated Horner Scheme}},
booktitle = {Algebraic and Numerical Algorithms and Computer-assisted Proofs},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {5391},
editor = {Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/442},
URN = {urn:nbn:de:0030-drops-4423},
doi = {10.4230/DagSemProc.05391.3},
annote = {Keywords: Polynomial evaluation, Horner scheme, error-free transformation, floating point arithmetic, accuracy}
}
Keywords: |
|
Polynomial evaluation, Horner scheme, error-free transformation, floating point arithmetic, accuracy |
Collection: |
|
05391 - Algebraic and Numerical Algorithms and Computer-assisted Proofs |
Issue Date: |
|
2006 |
Date of publication: |
|
31.01.2006 |