Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Efficient and accurate computation of upper bounds of approximation errors

Sylvain Chevillard 1 John Harrison 2 Mioara Joldes 3 Christoph Lauter 2
1 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : For purposes of actual evaluation, mathematical functions f are commonly replaced by approximation polynomials p. Examples include floating-point implementations of elementary functions, quadrature or more theoretical proof work involving transcendental functions. Replacing f by p induces a relative error epsilon =p/f - 1. In order to ensure the validity of the use of p instead of f, the maximum error, i.e. the supremum norm of epsilon must be safely bounded above. Numerical algorithms for supremum norms are efficient but cannot offer the required safety. Previous validated approaches often require tedious manual intervention. If they are automated, they have several drawbacks, such as the lack of quality guarantees. In this article a novel, automated supremum norm algorithm with a priori quality is proposed. It focuses on the validation step and paves the way for formally certified supremum norms. Key elements are the use of intermediate approximation polynomials with bounded truncation remainder and a non-negativity test based on a Sum-of-squares expression of polynomials. The new algorithm was implemented in the tool Sollya. The article includes experimental results on real-life examples.
Complete list of metadatas

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00445343
Contributor : Mioara Joldes <>
Submitted on : Friday, January 8, 2010 - 11:48:17 AM
Last modification on : Thursday, January 17, 2019 - 3:16:03 PM
Document(s) archivé(s) le : Thursday, June 17, 2010 - 10:30:48 PM

File

RRLIP2010-2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00445343, version 1

Collections

Citation

Sylvain Chevillard, John Harrison, Mioara Joldes, Christoph Lauter. Efficient and accurate computation of upper bounds of approximation errors. 2010. ⟨ensl-00445343v1⟩

Share

Metrics

Record views

60

Files downloads

127