DROPS

Document

Compensated Horner Scheme

Authors: Philippe Langlois, Stef Graillat, and Nicolas Louvet

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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.

Cite as

Philippe Langlois, Stef Graillat, and Nicolas Louvet. Compensated Horner Scheme. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.05391.3},
  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}
}

Search Results

Documents authored by Graillat, Stef

Compensated Horner Scheme

Abstract

Cite as

Thanks for your feedback!

Could not send message