Accelerating Linear System Solutions Using Randomization Techniques

TitleAccelerating Linear System Solutions Using Randomization Techniques
Publication TypeJournal Article
Year of Publication2012
AuthorsBaboulin, M., J. Dongarra, J. Herrmann, and S. Tomov
JournalACM Transactions on Mathematical Software (accepted) (also LAWN 246)
Date Published03-2012
Keywordsalgorithms, dense linear algebra, experimentation, graphics processing units, linear systems, lu factorization, multiplicative preconditioning, numerical linear algebra, performance, randomization

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.