Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport Technique) Année : 2008

Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization

Résumé

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.
Fichier principal
Vignette du fichier
RR-6520.pdf (539.66 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00271394 , version 1 (09-04-2008)
inria-00271394 , version 2 (28-04-2008)
inria-00271394 , version 3 (30-04-2008)

Identifiants

  • HAL Id : inria-00271394 , version 3

Citer

Laura Grigori, Erik G. Boman, Simplice Donfack, Timothy A. Davis. Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization. [Technical Report] RR-6520, INRIA. 2008. ⟨inria-00271394v3⟩
219 Consultations
575 Téléchargements

Partager

Gmail Facebook X LinkedIn More