Skip to Main content Skip to Navigation

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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
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 <>
Submitted on : Wednesday, April 30, 2008 - 10:50:02 AM
Last modification on : Thursday, July 8, 2021 - 3:48:48 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 Boman, Simplice Donfack, Timothy Davis. Hypergraph-based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization. [Technical Report] RR-6520, INRIA. 2008. ⟨inria-00271394v3⟩



Record views


Files downloads