Skip to Main content Skip to Navigation
Reports

Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods

Abstract : 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.
Document type :
Reports
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00950612
Contributor : Marc Baboulin <>
Submitted on : Tuesday, February 25, 2014 - 10:07:33 PM
Last modification on : Thursday, July 8, 2021 - 3:47:54 AM
Long-term archiving on: : Sunday, May 25, 2014 - 10:43:14 AM

File

RR-8481.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00950612, version 1

Collections

Citation

Marc Baboulin, Xiaoye S. Li, François-Henry Rouet. Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods. [Research Report] RR-8481, Inria. 2014. ⟨hal-00950612⟩

Share

Metrics

Record views

686

Files downloads

455