Les algorithmes compensés améliorent la précision des résultats
calculés en arithmétique flottante, tout en n'utilisant qu'une seule
précision de travail, typiquement la double precision IEEE-754. Des
résultats récents concernent la sommation, le produit scalaire et
l'évaluation compensée de polynômes. Pour ces algorithmes, il a été
prouvé que la solution compensée est aussi précise que si elle avait
été calculée par l'algorithme classique en précision de travail doublée.
Ces algorithmes se montrent en outre deux fois plus rapides que leurs
équivalents basés sur l'arithmétique double-double, tout en fournissant
la même précision de sortie.
Dans cet exposé, on considérera la résolution compensée de systèmes
linéaires triangulaires Tx=b, où les coefficients de la matrice triangulaire
T et ceux du vecteur b sont exactement représentés par des nombres
flottants. Nous présenterons nos premiers résultats, ainsi que nos travaux
en cours sur ce sujet.
Lorsqu'on manipule une expression numérique telle que sin(x+0.1) ou
2*pi/7 dans un logiciel informatique, il faut être extrêmement prudent.
En effet, ces expressions font intervenir des nombres qui ne sont pas
exactement représentables dans la mémoire de l'ordinateur. Le logiciel
va alors stocker puis travailler avec une expression inexacte. Il s'agit
d'une source de confusion et même de possibles erreurs pour l'utilisateur.
De même, certains calculs très mal conditionnés peuvent conduire à des
résultats complètement faux si la précision n'est pas soigneusement
choisie. L'utilisateur non averti risque de prendre pour argent comptant
les résultats donnés par son logiciel ce qui le conduira à prendre pour
vrais des résultat potentiellement très inexacts.
Sollya est un logiciel conçu pour permettre la manipulation
d'expressions numériques de façon sure et efficace. Sollya se présente
sous forme d'un shell interactif dans lequel on peut manipuler des
expressions numériques et utiliser des algorithmes numériques. On peut
ainsi définir des fonctions numériques, en trouver les zéros, en
calculer la norme infinie, etc. Sollya utilise l'arithmétique par
intervalle et choisit automatiquement la précision nécessaire pour
chaque calcul afin de garantir la qualité du résultat renvoyé.
Cet exposé sera constitué d'une présentation des principales
fonctionnalités de Sollya sous forme d'une démonstration du logiciel.
L'implantation de fonctions mathématiques, comme exp(x), sin(x),
erf(x) ou log2(1 + 2^x), dans une arithmétique flottante a longtemps
été un travail manuel et fastidieux. Comme l'expérience avec
l'implantation de la bibliothèque CRLibm a montré, un spécialiste
avait besoin d'à peu près un mois par fonction.
Étant donnés une fonction, un domaine et une borne d'erreur maximale
ciblée, la tâche consiste à trouver une réduction d'argument
appropriée, à calculer un polynôme d'approximation et à implanter ce
polynôme dans une arithmétique flottante. La preuve de cette
implantation nécessite du travail supplémentaire.
Dans cet exposé, un outil sera présenté qui en permet
l'automatisation. Ce prototype est capable de gérer l'approximation
polynomiale, l'implantation du polynôme et la preuve pour des
fonctions définies sur un petit domaine et des erreurs cibles allant
jusqu'à 140 bits. Avec cet outil, le temps d'implantation d'une
fonction dans CRLibm est réduit à 2 jours.
L'implantation automatique de fonctions mathématiques est un nouveau
domaine d'algorithmique numérique. Ce n'est plus l'algorithme
d'évaluation d'une fonction qui est au centre de l'intérêt mais
l'algorithme qui le génère.
Cette automatisation ouvre également la voie vers des transformations
numériques de codes flottants. La fonction donnée en entrée à
l'algorithme d'implantation peut elle-même être définie par un code
numérique, éventuellement itératif et peut-être
inefficace. L'algorithme génère alors un code optimisé approchant ce
code de base donné. Le résultat est une transformation de code de haut
niveau, remplaçant des boucles par des polynômes.
Le temps le permettant, une démonstration de l'outil sera faite
pendant l'exposé.
Dans cet exposé, nous présenterons un algorithme compensé pour le calcul du produit de nombres flottants. Nous montrerons que cet algorithme renvoie un arrondi fidèle du résultat exact.
Nous proposons une approche pour résoudre un système linéaire et
certifier la solution calculée en même temps. L'idée est
d'utiliser l'arithmétique flottante pour calculer la solution, et
d'utiliser l'arithmétique par intervalle pour résoudre le
système vérifié par le résidu, ce qui nous permet d'obtenir une borne
garantie de l'erreur.
À cet effet, on a utilisé les méthodes de raffinement itératif.
À partir d'un raffinement pour l'approximation flottante de la solution,
nous utilisons un raffinement par intervalle pour l'erreur de cette
approximation. Ces deux raffinements produisent une solution plus
précise que la solution flottante seule et de surcroît dotée d'une borne
d'erreur.
De façon plus détaillée, une approximation flottante
initiale de la solution est calculée en utilisant simplement la
décomposition LU de la matrice du système.
Ensuite, on passe à l'arithmétique par intervalle.
Le résidu du système est calculé en utilisant l'arithmétique par
intervalle et le système est ensuite préconditionné par l'inverse approché de la matrice du système (en utilisant la décomposition LU calculée en
arithmétique flottante). Cela nous donne un système par
intervalle dont la solution est la borne d'erreur du système original.
Sous l'hypothèse que l'on a une bonne approximation de la matrice inverse,
à savoir que la matrice préconditionnée est une H-matrice,
une proposition de Neumaier [2] permet d'assurer qu'il est possible
d'obtenir une solution initiale du système par intervalle.
Cette solution initiale est raffinée par un nombre constant et faible
d'itérations de Gauss-Seidel.
L'approximation flottante du système original est corrigée en
lui ajoutant le point milieu de la borne d'erreur.
La borne d'erreur est mise à jour en même temps par un
recentrage (en lui soustrayant son point milieu).
Les résultats expérimentaux illustrent que notre approche donne des
solutions très fines.
[1] N.J. Higham; Accuracy and Stability
of Numerical Algorithms, 2nd edition, SIAM Press, 2002.
Chapter 12: Iterative Refinement.
[2] A. Neumaier; Interval methods for
systems of equations, Cambridge University Press, 1990.
Chapter 4: The solution of square linear systems of equations.
