Fill-in reduction in sparse matrix factorizations using hypergraphs - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2014

## Fill-in reduction in sparse matrix factorizations using hypergraphs

(1) , (2) , (2) , (3, 4)
1
2
3
4
Oguz Kaya
• Function : Author
• PersonId : 937471
Enver Kayaaslan
• Function : Correspondent author
• PersonId : 951280

Connectez-vous pour contacter l'auteur
Bora Uçar

Connectez-vous pour contacter l'auteur
Iain S. Duff
• Function : Author
• PersonId : 862853

#### 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.

### Dates and versions

hal-00932882 , version 1 (30-04-2014)
hal-00932882 , version 2 (14-01-2021)

### Identifiers

• HAL Id : hal-00932882 , version 2

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

438 View