Accelerating linear system solutions using randomization technique

Marc Baboulin 1, 2 Jack Dongarra 3 Julien Herrmann 4, 5 Stanimire Tomov 3
1 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
2 ParSys - LRI - Systèmes parallèles (LRI)
LRI - Laboratoire de Recherche en Informatique
3 ICL - Innovative Computing Laboratory [Knoxville]
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We illustrate how linear algebra calculations can be enhanced by statistical techniques in the case of a square linear system Ax = b. We study a random transformation of A that enables us to avoid pivoting and then to reduce the amount of communication. Numerical experiments show that this randomization can be performed at a very affordable computational price while providing us with a satisfying accuracy when compared to partial pivoting. This random transformation called Partial Random Butterfly Transformation (PRBT) is optimized in terms of data storage and flops count. We propose a solver where PRBT and the LU factorization with no pivoting take advantage of the current hybrid multicore/GPU machines and we compare its Gflop/s performance with a solver implemented in a current parallel library.
Keywords : graphics processing units randomization multiplicative preconditioning Dense linear algebra linear systems LU factorization
Type de document :
Article dans une revue
ACM Transactions on Mathematical Software, Association for Computing Machinery, 2013, 39 (2), 〈10.1145/2427023.2427025〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00908496
Contributeur : Marc Baboulin <>
Soumis le : samedi 23 novembre 2013 - 19:18:01
Dernière modification le : vendredi 20 avril 2018 - 15:44:26

Identifiants

Collections

INRIA | LIP | ENS-LYON | UMR8623 | UNIV-LILLE3 | UNIV-LYON1 | LRI-PARSYS | INRIA-RENGRE

Citation

Marc Baboulin, Jack Dongarra, Julien Herrmann, Stanimire Tomov. Accelerating linear system solutions using randomization technique. ACM Transactions on Mathematical Software, Association for Computing Machinery, 2013, 39 (2), 〈10.1145/2427023.2427025〉. 〈hal-00908496〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

367

Contact


archive-ouverte@inria.fr