%0 Journal Article
%J ACM Transactions on Mathematical Software (also LAWN 246)
%D 2013
%T Accelerating Linear System Solutions Using Randomization Techniques
%A Marc Baboulin
%A Jack Dongarra
%A Julien Herrmann
%A Stanimire Tomov
%K algorithms
%K dense linear algebra
%K experimentation
%K graphics processing units
%K linear systems
%K lu factorization
%K multiplicative preconditioning
%K numerical linear algebra
%K performance
%K randomization
%X 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.
%B ACM Transactions on Mathematical Software (also LAWN 246)
%V 39
%8 2013-02
%G eng
%U http://dl.acm.org/citation.cfm?id=2427025
%N 2
%R 10.1145/2427023.2427025