Accelerating Linear System Solutions Using Randomization Techniques

We illustrate how linear algebra calculations can be enhanced by statistical techniques in the case of a square linear system Axa=ab. 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 randomiza...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on mathematical software 2013-02, Vol.39 (2), p.1-13
Main Authors: BABOULIN, Marc, DONGARRA, Jack, HERRMANN, Julien, TOMOV, Stanimire
Format: Article
Language:English
Subjects:
Algebra
Applied sciences
Computer science
control theory
systems
Data storage
Exact sciences and technology
Factorization
Linear and multilinear algebra, matrix theory
Linear systems
Mathematical analysis
Mathematical models
Mathematics
Memory and file management (including protection and security)
Memory organisation. Data processing
Randomization
Sciences and techniques of general use
Software
Solvers
Transformations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We illustrate how linear algebra calculations can be enhanced by statistical techniques in the case of a square linear system Axa=ab. 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.
ISSN:0098-3500
1557-7295
DOI:10.1145/2427023.2427025