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.
Type de document :
Rapport
[Research Report] RR-8448, INRIA. 2014
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

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

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〉

Partager

Métriques

Consultations de la notice

685

Téléchargements de fichiers

2672