Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization

Laura Grigori 1 Erik Boman 2 Simplice Donfack 3 Timothy Davis 4
1 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In this paper we present HUND, a hypergraph-based unsymmetric nested dissection ordering algorithm for reducing the fill-in incurred during Gaussian elimination. HUND has several important properties. It takes a global perspective of the entire matrix, as opposed to local heuristics. It takes into account the assymetry of the input matrix by using a hypergraph to represent its structure. It is suitable for performing Gaussian elimination in parallel, with partial pivoting. This is possible because the row permutations performed due to partial pivoting do not destroy the column separators identified by the nested dissection approach. Experimental results on 27 medium and large size highly unsymmetric matrices compare HUND to four other well-known reordering algorithms. The results show that HUND provides a robust reordering algorithm, in the sense that it is the best or close to the best (often within $10\%$) of all the other methods.
Type de document :
Rapport
[Technical Report] RR-6520, INRIA. 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00271394
Contributeur : Laura Grigori <>
Soumis le : mercredi 30 avril 2008 - 10:50:02
Dernière modification le : vendredi 23 février 2018 - 13:41:42
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 21:34:53

Fichier

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

Identifiants

  • HAL Id : inria-00271394, version 3

Collections

Citation

Laura Grigori, Erik Boman, Simplice Donfack, Timothy Davis. Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization. [Technical Report] RR-6520, INRIA. 2008. 〈inria-00271394v3〉

Partager

Métriques

Consultations de la notice

381

Téléchargements de fichiers

190