Accelerating linear system solutions using randomization techniques

Marc Baboulin, Jack Dongarra, Julien Herrmann, Stanimire Tomov

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

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.

Original languageEnglish
Article number8
JournalACM Transactions on Mathematical Software
Volume39
Issue number2
DOIs
StatePublished - Feb 2013

Keywords

  • Dense linear algebra
  • Graphics processing units
  • LU factorization
  • Linear systems
  • Multiplicative preconditioning
  • Randomization

Fingerprint

Dive into the research topics of 'Accelerating linear system solutions using randomization techniques'. Together they form a unique fingerprint.

Cite this