Skip to Main content Skip to Navigation

Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization

Laura Grigori 1 Erik G. Boman 2 Simplice Donfack 3 Timothy A. 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.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Laura Grigori Connect in order to contact the contributor
Submitted on : Wednesday, April 30, 2008 - 10:50:02 AM
Last modification on : Sunday, June 26, 2022 - 11:48:12 AM
Long-term archiving on: : Friday, November 25, 2016 - 9:34:53 PM


Files produced by the author(s)


  • HAL Id : inria-00271394, version 3


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⟩



Record views


Files downloads