# Fill-in reduction in sparse matrix factorizations using hypergraphs

* Auteur correspondant
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Keywords :
Type de document :
Rapport
[Research Report] RR-8448, INRIA. 2014
Domaine :

Littérature citée [33 références]

https://hal.inria.fr/hal-00932882
Contributeur : Equipe Roma <>
Soumis le : mercredi 30 avril 2014 - 09:07:18
Dernière modification le : samedi 21 avril 2018 - 01:27:13
Document(s) archivé(s) le : mercredi 30 juillet 2014 - 10:40:20

### Fichier

RR-8448.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-00932882, version 1

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

### Métriques

Consultations de la notice

## 706

Téléchargements de fichiers