Projet ANR EVA-Flo : 5ème réunion, 20-21 mai 2010 à Canet-en-Roussillon, organisée par Perpignan

Programme


Transparents des présentations






Résumés des présentations


Marc Daumas : Effect of round-off errors on the accuracy of randomized algorithms
As randomized algorithms such as Monte Carlo quadratures converge slowly they usually involve a large number of sample points and they become increasingly popular on peta- and exa-scale systems using hardware accelerators (GPU, ClearSpeed). Worst case analyses of round-off errors do not necessarily provide much insights on the accuracy of results. They often yield that results carry no significant digits even for programs that have ran for a few minutes without producing any catastrophic cancellation. Failure to yield an accurate result may be due to some inaccurate results of the Monte Carlo method or to a large accumulation of individual round-off errors. We provide a simple bound on the number of significant digits of results based on the number of sample points N and a parameter that bounds the probability of failure.

Sylvain Collange : Intervalle sur GPU
épisode [2;3] : la revanche des signes

Philippe Théveny : Définition et mise en oeuvre de LEMA
L'objectif du Langage pour les Expressions Mathématiques Annotées (LEMA) est de pouvoir exprimer les données nécessaires à la génération automatique de code numérique certifié. Pour cela, nous avons choisi d'étendre le langage MathML qui permet de représenter des expressions mathématiques mais dont l'expressivité dans le domaine des nombres en virgule flottante est rudimentaire. Le langage ainsi défini servira à spécifier le problème et à intégrer les informations produites par des outils externes, comme, par exemple, des approximations polynomiales produites avec Sollya ou des preuves formelles générées par Gappa. Cet exposé présentera l'état des travaux en cours sur LEMA et sur la bibliothèque associée.

Mioara Joldes : Chebyshev Interpolation Polynomial-based, Tools for Rigorous Computing
Performing numerical computations, yet being able to provide rigorous mathematical statements about the obtained result, is required in many domains like global optimization, ODE solving or integration. Taylor models, which associate to a function a pair made of a Taylor approximation polynomial and a rigorous remainder bound, are a widely used rigorous computation tool. This approach benefits from the advantages of numerical methods, but also gives the ability to make reliable statements about the approximated function. A natural idea is to try to replace Taylor polynomials with better approximations such as minimax approximation, Chebyshev truncated series or interpolation polynomials. Despite their features, an analogous to Taylor models, based on such polynomials, has not been yet well-established in the field of validated numerics. In this talk we propose two approaches for computing such models based on interpolation polynomials at Chebyshev nodes. We compare the quality of the obtained remainders and the performance of the approaches to the ones provided by Taylor models. We also present two practical examples where this tool can be used: supremum norm computation of approximation errors and rigorous quadrature. This talk is based on a joint work with N. Brisebarre.

Laurent Thévenoux : Accuracy Versus Time: A Case Study with Summation Algorithms
We focus on numerical algorithms for which, in practice, parallelism and accuracy do not cohabit well. In order to increase parallelism, expressions are reparsed implicitly using mathematical laws like associativity and this reduces the accuracy. Our approach consists in performing an exhaustive study: we generate all the algorithms equivalent to the original one and compatible with our relaxed time constraint. Next we compute the worst errors which may arise during their evaluation, for several relevant sets of data. Our main conclusion is that relaxing very slightly the time constraints by choosing algorithms whose critical paths are a bit longer than the optimal makes it possible to strongly optimize the accuracy. We extend these results to the case of bounded parallelism and to accurate sum algorithms that use compensation techniques.



Retour à la page d'EVA-Flo.