Skip to Main content Skip to Navigation
Reports

Fill-in reduction in sparse matrix factorizations using hypergraphs

Abstract : We discuss the use of hypergraph partitioning based methods in fill-reducing orderings of sparse matrices for Cholesky, LU and QR factorizations. For the Cholesky factorization, we investigate a recent result on pattern-wise decomposition of sparse matrices, generalize the result, and develop algorithmic tools to obtain more effective ordering methods. The generalized results help us formulate the fill-reducing ordering problem for LU factorization as we do for the Cholesky case, without ever symmetrizing the given matrix $A$ as $|A| + |A^T|$ or $|^AT ||A|$. For the QR factorization, we adopt a recently proposed technique to use hypergraph models in a fairly standard manner. The method again does not form the possibly much denser matrix $|A^T ||A|$. We also discuss alternatives for LU and QR factorization cases where the symmetrized matrix can be used. We provide comparisons with the most common alternatives in all three cases.
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-00932882
Contributor : Equipe Roma <>
Submitted on : Wednesday, April 30, 2014 - 9:07:18 AM
Last modification on : Wednesday, November 20, 2019 - 2:35:52 AM
Long-term archiving on: : Wednesday, July 30, 2014 - 10:40:20 AM

File

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

Identifiers

  • HAL Id : hal-00932882, version 1

Collections

Citation

Oguz Kaya, Enver Kayaaslan, Bora Uçar, Iain S. Duff. Fill-in reduction in sparse matrix factorizations using hypergraphs. [Research Report] RR-8448, INRIA. 2014. ⟨hal-00932882⟩

Share

Metrics

Record views

799

Files downloads

4190