Projet ANR EVA-Flo : 5ème réunion, 20-21 mai 2010 à Canet-en-Roussillon, organisée par Perpignan
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.