CISE Submissions

Item: REP-2008-449

Item:REP-2008-449

Title:Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization

Laura Grigori
INRIA
Saclay - Ile de France, Laboratoire de Recherche en Informatique Universite Paris-Sud 11, France
Erik Boman
Scalable Algorithms Dept., Sandia National Laboratories
Sandia National Laboratories, NM 87185-1318, USA
Simplice Donfack
Universite de Yaounde I, Computer Science Department
B.P 812 Yaounde - Cameroun
Timothy A. Davis
CISE Dept, Univ. of Florida
E301 CSE, PO Box 116120, Univ. of Florida, Gainesvile FL, 32611

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.

Additional Information: here

Select Departmental Reports

To select a single entry given the item reference number, enter the reference number in the Item: box. Other select options will then be ignored.

The other select options (Category:, Select by Time:, and Select by Author: can be used in any combination. However, only one of the Select by Author: options can be used. You can either select entries from a specific CISE faculty member, or from any (non faculty) CISE user, or you can enter in part or all of the author's name <-- ' --> (which is case insensitive). But only the FIRST one will be used. For many entries, the username may not have been entered, and in this case the first two options will not work for those entries, but selecting by last name will.

The Display Level: option tells how much information to display for each entry ranging from the lease (Index) to the most (Full Listing).

Item:

Category:

Select by Time:

Select by Author:

CISE Faculty Member:
CISE Member:
Name:

Display Level:

Index
Short Listing
Full Listing

Departmental Report Categories

Technical Reports
	Coordinator: Alexander M Thompson Coordinator: Dan H. Eicher Coordinator: John L. Kramer Jr.

To submit items for this page, please log in on the CISE submit page.