Title :

Un algorithme d'échange pour l'optimisation simultanée des erreur d'approximation et d'évaluation en précision finie de polynômes d'approximation

Author(s) :

Arzelier, Denis [Auteur]
Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes [LAAS-ROC]
Bréhard, Florent [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Hubrecht, Tom [Auteur]
Arithmétiques des ordinateurs, méthodes formelles, génération de code [ARIC]
Département d'informatique - ENS-PSL [DI-ENS]
Joldes, Mioara [Auteur]
Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes [LAAS-ROC]

English keyword(s) :

Polynomial approximation
Finite precision evaluation
Evaluation error
Semi-infinite linear programming
Remez exchange algorithm
Mathematical library

HAL domain(s) :

Informatique [cs]

English abstract : [en]

The finite precision implementation of mathematical functions frequently depends on polynomial approximations. A key characteristic of this approach is that rounding errors occur both when representing the coefficients of ...
Show more >The finite precision implementation of mathematical functions frequently depends on polynomial approximations. A key characteristic of this approach is that rounding errors occur both when representing the coefficients of the polynomial on a finite number of bits, and when evaluating it in finite precision arithmetic. Hence, to find a best polynomial, for a given fixed degree, norm and interval, it is necessary to account for both the approximation error and the floating-point evaluation error. While efficient algorithms were already developed for taking into account the approximation error, the evaluation part is usually a posteriori handled, in an ad-hoc manner. Here, we formulate a semi-infinite linear optimization problem whose solution is a best polynomial with respect to the supremum norm of the sum of both errors. This problem is then solved with an iterative exchange algorithm, which can be seen as an extension of the well-known Remez exchange algorithm. An open-source C implementation using the Sollya library is presented and tested on several examples, which are then analyzed and compared against state-of-the-art Sollya routines.Show less >

Language :

Anglais

ANR Project :

Sûreté numérique pour les preuves assistées par ordinateur

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL