Accelerating linear system solutions using randomization techniques

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 Butter y 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 latest generation of hybrid multicore/GPU machines and we compare its Gfl op/s performance with a solver implemented in a current parallel library.
Type de document :
[Research Report] RR-7616, INRIA. 2011
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger
Contributeur : Marc Baboulin <>
Soumis le : vendredi 13 mai 2011 - 20:16:25
Dernière modification le : mardi 24 avril 2018 - 13:38:26
Document(s) archivé(s) le : dimanche 14 août 2011 - 02:45:51


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00593306, version 1



Marc Baboulin, Jack Dongarra, Julien Herrmann, Stanimire Tomov. Accelerating linear system solutions using randomization techniques. [Research Report] RR-7616, INRIA. 2011. 〈inria-00593306〉



Consultations de la notice


Téléchargements de fichiers