Tradeoffs between Accuracy and Efficiency for Optimized and Parallel Interval Matrix Multiplication - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

Tradeoffs between Accuracy and Efficiency for Optimized and Parallel Interval Matrix Multiplication

(1) , (1, 2) , (1, 2, 3)
1
2
3

Abstract

Interval arithmetic is mathematically defined as set arithmetic. For implementation issues, it is necessary to detail the representation of intervals and to detail formulas for the arithmetic operations. Two main representations of intervals are considered here: inf-sup and midrad. Formulas for the arithmetic operations, using these representations, are studied along with formulas that trade off accuracy for efficiency. This tradeo ff is particularly blatant on the example of interval matrix multiplication, implemented using floating-point arithmetic: depending on the chosen formulas, the effi ciency as well as the accuracy can vary greatly in practice, and not necessarily as predicted by the theory. Indeed, theoretical predictions are often based on exact operations, as opposed to floating-point operations, and on operations count, as opposed to measured execution time. These observations and the recommendations that ensue are further obfuscated by considerations on memory usage, multithreaded computations. . . when these algorithms are implemented on parallel architectures such as multicores.
L'arithmétique par intervalles et une arithmétique sur les ensembles. Pour pouvoir l'implanter, il faut détailler d'une part la représentation choisie pour les intervalles et d'autre part les formules, dépendant de cette représentation, pour les opérations arithmétiques. Essentiellement deux représentations des intervalles sont considérées ici : la représentation inf-sup (par les extrémités) et la représentation mid-rad (par le centre et le rayon). Différentes formules pour les opérations arithmétiques sont présentées, qui offrent différents compromis entre la précision du résultat et la quantité de calculs à effectuer. Ces compromis sont encore plus flagrants quand on considère l'utilisation de ces opérations pour effectuer des produits de matrices à coefficients intervalles, implantés en utilisant l'arithmétique flottante : selon les formules choisies, les performances ainsi que la précision peuvent différer grandement en pratique, mais pas nécessairement comme le prédit la théorie. En effet, les prédictions théoriques sont basées sur l'hypothèse d'une arithmétique sous-jacente qui est exacte et non flottante, ainsi que sur un décompte d'opérations, ce qui ne correspond pas directement aux mesures des temps d'exécution. Ces observations et les recommandations qui en découlent dépendent en outre de considérations sur l'utilisation mémoire, la présence de calculs multithreadés etc. lorsque l'on considère des implantations parallèles sur des architectures telles que des multi-cœurs.
Fichier principal
Vignette du fichier
Nguyen-Revol-Theveny.pdf (202.42 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00704288 , version 1 (05-06-2012)

Identifiers

  • HAL Id : hal-00704288 , version 1

Cite

Hong Diep Nguyen, Nathalie Revol, Philippe Théveny. Tradeoffs between Accuracy and Efficiency for Optimized and Parallel Interval Matrix Multiplication. PARA 2012 - Workshop on the State-of-the-Art in Scientific and Parallel Computing, Jun 2012, Helsinki, Finland. ⟨hal-00704288⟩
173 View
135 Download

Share

Gmail Facebook Twitter LinkedIn More