6698

Accelerating linear system solutions using randomization techniques

Marc Baboulin, Jack Dongarra, Julien Herrmann, Stanimire Tomov
Laboratoire de Recherche en Informatique – Universite Paris-Sud 11 (LRI), Universite Paris XI – Paris Sud
inria-00593306, 2011

@techreport{BABOULIN:2011:INRIA-00593306:1,

   hal_id={inria-00593306},

   url={http://hal.inria.fr/inria-00593306/en/},

   title={Accelerating linear system solutions using randomization techniques},

   author={Baboulin, Marc and Dongarra, Jack and Herrmann, Julien and Tomov, Stanimire},

   keywords={dense linear algebra; linear systems; LU factorization; randomization; multiplicative preconditioning; Graphics Processing Units},

   language={Anglais},

   affiliation={Laboratoire de Recherche en Informatique – Universit{‘e} Paris-Sud 11 – LRI , Innovative Computing Laboratory – ICL},

   type={Rapport de recherche},

   institution={INRIA},

   number={RR-7616},

   year={2011},

   month={May},

   pdf={http://hal.inria.fr/inria-00593306/PDF/RR-7616.pdf}

}

Download Download (PDF)   View View   Source Source   

599

views

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 Butter y 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 latest generation of hybrid multicore/GPU machines and we compare its Gfl op/s performance with a solver implemented in a current parallel library.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: