Constructing elimination trees for sparse unsymmetric matrices

Kamer Kaya 1 Bora Uçar 2, 3, 4
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Eisenstat et Liu ont récemment décrit l'arbre d'élimination pour des matrices creuses non symétriques et ont proposé un algorithme pour le construire en temps O(mn) pour une matrice de taille n ayant m éléments non nuls hors diagonaux [Eisenstat and Liu, SIAM J. Matrix Anal. Appl., 26 (2005) and 29 (2008)]. Nous décrivons un algorithme dont la complexité en temps est O(m log n). Nous comparons les deux algorithmes expérimentalement et montrent que les deux sont efficaces en général. L'algorithme de Eisenstat et Liu est plus rapide dans de nombreux cas pratiques, mais il y a des cas dans lesquels la différence entre le temps d'exécution de deux algorithmes est significative en faveur de le nôtre.
Type de document :
Article dans une revue
SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2013, 34 (2), pp.345-354. 〈10.1137/110825443〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00567970
Contributeur : Bora Uçar <>
Soumis le : jeudi 4 octobre 2012 - 12:34:43
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 20:51:06

Fichier

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

Identifiants

Collections

Citation

Kamer Kaya, Bora Uçar. Constructing elimination trees for sparse unsymmetric matrices. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2013, 34 (2), pp.345-354. 〈10.1137/110825443〉. 〈inria-00567970v4〉

Partager

Métriques

Consultations de la notice

424

Téléchargements de fichiers

645