Accelerating linear system solutions using randomization techniques

Marc Baboulin; Jack Dongarra; Julien Herrmann; Stanimire Tomov

inria-00593306, version 1

Accelerating linear system solutions using randomization techniques

Marc Baboulin ( Author to contact preferably )^a^, 1, Jack Dongarra ()^b^, 2, Julien Herrmann ()^c^, 1, Stanimire Tomov ()^b^, 2

N° RR-7616 (2011)

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 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.

a – INRIA/University Paris-Sud
b – University of Tennessee
c – École Normale Supérieure de Lyon
1: Laboratoire de Recherche en Informatique (LRI)
CNRS : UMR8623 – Université Paris XI - Paris Sud
2: Innovative Computing Laboratory (ICL)
University of Tennessee

inria-00593306, version 1
http://hal.inria.fr/inria-00593306
oai:hal.inria.fr:inria-00593306
From: Marc Baboulin <>
Submitted on: Friday, 13 May 2011 20:16:25
Updated on: Tuesday, 17 May 2011 09:27:27

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00593306"><monogr>
<author><persName><forename>Marc</forename><surname>Baboulin</surname></persName>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
</author>
<author><persName><forename>Jack</forename><surname>Dongarra</surname></persName>
<affiliation>
<orgName type="laboratory">ICL</orgName>
<orgName type="team">Innovative Computing Laboratory</orgName>
<country>US</country>
<orgName type="institution">University of Tennessee</orgName>
</affiliation>
</author>
<author><persName><forename>Julien</forename><surname>Herrmann</surname></persName>
<affiliation>
<orgName type="laboratory">LRI</orgName>
<orgName type="team">Laboratoire de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8623</orgName>
<orgName type="institution">Université Paris XI - Paris Sud</orgName>
</affiliation>
</author>
<author><persName><forename>Stanimire</forename><surname>Tomov</surname></persName>
<affiliation>
<orgName type="laboratory">ICL</orgName>
<orgName type="team">Innovative Computing Laboratory</orgName>
<country>US</country>
<orgName type="institution">University of Tennessee</orgName>
</affiliation>
</author>
<title type="main" level="m">Accelerating linear system solutions using randomization techniques</title><title type="main" level="m">Accelerating linear system solutions using randomization techniques</title><imprint><biblScope type="publicationDate">2011-05-13</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00593306</idno><idno type="HALFile">http://hal.inria.fr/inria-00593306/PDF/RR-7616.pdf</idno></biblStruct>
</listBibl>
</listBibl>