Parallel Implementation of Interval Matrix Multiplication

Nathalie Revol 1, * Philippe Théveny 1, 2, *
* Auteur correspondant
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Two main and not necessarily compatible objectives when implementing the product of two dense matrices with interval coefficients are accuracy and efficiency. In this work, we focus on an implementation on multicore architectures. One direction successfully explored to gain performance in execution time is the representation of intervals by their midpoints and radii rather than the classical representation by endpoints. Computing with the midpoint-radius representation enables the use of optimized floating-point BLAS and consequently the performances benefit from the performances of the BLAS routines. Several variants of interval matrix multiplication have been proposed, that correspond to various trade-offs between accuracy and efficiency, including some efficient ones proposed by Rump in 2012. However, in order to guarantee that the computed result encloses the exact one, these efficient algorithms rely on an assumption on the order of execution of floating-point operations which is not verified by most implementations of BLAS. In this paper, an algorithm for interval matrix product is proposed that verifies this assumption. Furthermore, several optimizations are proposed and the implementation on a multicore architecture compares reasonably well with a non-guaranteed implementation based on MKL, the optimized BLAS of Intel: the overhead is most of the time less than 2 and never exceeds 3. This implementation also exhibits a good scalability.
Type de document :
Article dans une revue
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00801890
Contributeur : Nathalie Revol <>
Soumis le : mercredi 11 décembre 2013 - 03:12:36
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : samedi 8 avril 2017 - 05:44:29

Fichiers

parallel-igemm.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00801890, version 2

Collections

Citation

Nathalie Revol, Philippe Théveny. Parallel Implementation of Interval Matrix Multiplication. Reliable Computing, Springer Verlag, 2013, 19 (1), pp.91-106. 〈http://interval.louisiana.edu/reliable-computing-journal/volume-19/reliable-computing-19-pp-091-106.pdf〉. 〈hal-00801890v2〉

Partager

Métriques

Consultations de la notice

290

Téléchargements de fichiers

228