Reducing elimination tree height for parallel LU factorization of sparse unsymmetric matrices

Enver Kayaaslan 1, 2 Bora Uçar 2, 1
Abstract : The elimination tree for unsymmetric matrices is a recent model playing important roles in sparse LU factorization. This tree captures the dependencies between the tasks of some well-known variants of sparse LU factorization. Therefore, the height of the elimination tree corresponds to the critical path length of the task dependency graph in the corresponding parallel LU factorization methods. We investigate the problem of finding minimum height elimination trees to expose a maximum degree of parallelism by minimizing the critical path length. This problem has recently been shown to be NP-complete. Therefore, we propose heuristics, which generalize the most successful approaches used for symmetric matrices to unsymmetric ones. We test the proposed heuristics on a large set of real world matrices and report 28% reduction in the elimination tree heights with respect to a common method, which exploits the state of the art tools used in Cholesky factorization.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01114413
Contributeur : Equipe Roma <>
Soumis le : lundi 9 février 2015 - 13:48:53
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : mercredi 27 mai 2015 - 17:50:42

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01114413, version 1

Collections

Citation

Enver Kayaaslan, Bora Uçar. Reducing elimination tree height for parallel LU factorization of sparse unsymmetric matrices. HiPC 2014, Dec 2014, Goa, India. pp.1--10. 〈hal-01114413〉

Partager

Métriques

Consultations de la notice

549

Téléchargements de fichiers

248