Result: Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods

Title:
Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
Authors:
Baboulin, Marc, Li, Xiaoye S., Rouet, François-Henry
Contributors:
Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Performance Optimization by Software Transformation and Algorithms & Librairies Enhancement (POSTALE), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de Saclay, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Lawrence Berkeley National Laboratory [Berkeley] (LBNL), Inria, R-LAS
Source:
[Research Report] RR-8481, Inria. 2014
Publisher Information:
CCSD, 2014.
Publication Year:
2014
Collection:
collection:EC-PARIS
collection:CNRS
collection:INRIA
collection:UNIV-PSUD
collection:INRIA-RRRT
collection:INRIA-SACLAY
collection:INRIA_TEST
collection:TESTALAIN1
collection:UMR8623
collection:INRIA2
collection:LRI-PARSYS
collection:LARA
collection:UNIV-PARIS-SACLAY
collection:UNIV-PSUD-SACLAY
collection:INRIA-ETATSUNIS
Subject Terms:
Sparse direct methods, LU factorization, randomized algorithms, ACM: G.: Mathematics of Computing, G.1: NUMERICAL ANALYSIS, G.1.3: Numerical Linear Algebra, G.1.3.4: Linear systems (direct and iterative methods), [INFO.INFO-NA]Computer Science [cs], Numerical Analysis [cs.NA]
Original Identifier:
HAL: hal-00950612
Document Type:
Report report<br />Reports
Language:
English
Access URL:
https://inria.hal.science/hal-00950612
https://inria.hal.science/hal-00950612v1/document
https://inria.hal.science/hal-00950612v1/file/RR-8481.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.00950612v1
Database:
HAL

Further Information

Also appeared as Lapack Working Note 285
We consider the solution of sparse linear systems using direct methods via LU factorization. Unless the matrix is positive definite, numerical pivoting is usually needed to ensure stability, which is costly to implement especially in the sparse case. The Random Butterfly Transformations (RBT) technique provides an alternative to pivoting and is easily parallelizable. The RBT transforms the original matrix into another one that can be factorized without pivoting with probability one. This approach has been successful for dense matrices; in this work, we investigate the sparse case. In particular, we address the issue of fill-in in the transformed system.