Exchange algorithm for evaluation and approximation error-optimized polynomials

Denis Arzelier 1 Florent Bréhard 2, 3, 4, 5 Mioara Joldes 2
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
2 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
3 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 PLUME - Preuves et Langages
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Machine implementation of mathematical functions often relies on polynomial approximations. The particularity is that rounding errors occur both when representing the polynomial coefficients on a finite number of bits, and when evaluating it in finite precision. Hence, for finding the best polynomial (for a given fixed degree, norm and interval), one has to consider both types of errors: approximation and evaluation. 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 the 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 algorithm. A discussion and comparison of the obtained results on different examples are finally presented.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02006606
Contributor : Mioara Joldes <>
Submitted on : Monday, February 4, 2019 - 4:53:19 PM
Last modification on : Friday, June 14, 2019 - 6:31:29 PM
Long-term archiving on : Sunday, May 5, 2019 - 4:30:25 PM

File

ExchangeEvalApprox.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02006606, version 1

Citation

Denis Arzelier, Florent Bréhard, Mioara Joldes. Exchange algorithm for evaluation and approximation error-optimized polynomials. 2019. ⟨hal-02006606⟩

Share

Metrics

Record views

111

Files downloads

107