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
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.
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

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

385