License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-4423
URL: http://drops.dagstuhl.de/opus/volltexte/2006/442/

Langlois, Philippe ; Graillat, Stef ; Louvet, Nicolas

Compensated Horner Scheme

pdf-format:
Dokument 1.pdf (255 KB)


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:DSP:2006:442,
  author =	{Philippe Langlois and Stef Graillat and Nicolas Louvet},
  title =	{Compensated Horner Scheme},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  year =	{2006},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  number =	{05391},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/442},
  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
Seminar: 05391 - Algebraic and Numerical Algorithms and Computer-assisted Proofs
Issue date: 2006
Date of publication: 31.01.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI