Skip to Main content Skip to Navigation
Journal articles

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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
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.
Document type :
Journal articles
Complete list of metadata
Contributor : Marc Baboulin <>
Submitted on : Saturday, November 23, 2013 - 7:18:01 PM
Last modification on : Wednesday, September 16, 2020 - 5:37:39 PM

Links full text



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⟩



Record views