Floating-Point $L^2$-Approximations

Nicolas Brisebarre 1, 2 Guillaume Hanrot 3
1 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Computing good polynomial approximations to usual functions is an important topic for the computer evaluation of those functions. These approximations can be good under several criteria, the most desirable being probably that the relative error is as small as possible in the $L^{\infty}$ sense, i.e. everywhere on the interval under study. In the present paper, we investigate a simpler criterion, the $L^2$ case. Though finding a best polynomial $L^2$-approximation with real coefficients is quite easy, we show that if the coefficients are restricted to be floating point numbers to some precision, the problem becomes a general instance of the CVP problem, and hence is NP-hard. We investigate the practical behaviour of exact and approximate algorithms for this problem. The conclusion is that it is possible in a short amount of time to obtain a relative or absolute best $L^2$-approximation. The main applications are for large dimension, as a preliminary step of finding $L^{\infty}$-approximations and for functions with large variations, for which relative best approximation is by far more interesting than absolute.
Type de document :
Communication dans un congrès
Peter Kornerup and Jean-Michel Muller. 18th IEEE Symposium in Computer Arithmetic, Jun 2007, Montpellier, France. IEEE, pp.177-186, 2007, 〈10.1109/ARITH.2007.38〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00119254
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 11 décembre 2006 - 10:02:33
Dernière modification le : mardi 16 janvier 2018 - 15:50:51
Document(s) archivé(s) le : lundi 20 septembre 2010 - 17:58:10

Fichiers

RR-6058.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nicolas Brisebarre, Guillaume Hanrot. Floating-Point $L^2$-Approximations. Peter Kornerup and Jean-Michel Muller. 18th IEEE Symposium in Computer Arithmetic, Jun 2007, Montpellier, France. IEEE, pp.177-186, 2007, 〈10.1109/ARITH.2007.38〉. 〈inria-00119254v2〉

Partager

Métriques

Consultations de la notice

306

Téléchargements de fichiers

119