Skip to Main content Skip to Navigation

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 metadata
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Thursday, January 14, 2021 - 5:27:41 PM
Last modification on : Thursday, January 20, 2022 - 4:13:52 PM


Files produced by the author(s)


  • HAL Id : hal-00932882, version 2


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-00932882v2⟩



Les métriques sont temporairement indisponibles