HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Saturday, November 23, 2013 - 7:18:01 PM
Last modification on : Monday, May 16, 2022 - 4:46:01 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