CISE Submissions

Item: REP-2000-397

Item:REP-2000-397

Title:A column approximate minimum degree ordering algorithm

Timothy A. Davis
John R. Gilbert
Stefan I. Larimore
Esmond G. Ng

Abstract:
Sparse Gaussian elimination with partial pivoting computes the factorization PAQ=LU of a sparse matrix A, where the row ordering P is selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column preordering, Q, based solely on the nonzero pattern of A such that the factorization remains as sparse as possible, regardless of the subsequent choice of P. The choice of Q can have a dramatic impact on the number of nonzeros in L and U. One scheme for determining a good column ordering for A is to compute a symmetric ordering that reduces fill-in in the Cholesky factorization of A'A (A transpose times A). This approach, which requires the sparsity structure of A'A to be computed, can be expensive both in terms of space and time since A'A may be much denser than A. An alternative is to compute Q directly from the sparsity structure of A; this strategy is is used by Matlab's colmmd preordering algorithm. A new ordering algorithm, colamd, is presented. It is based on the same strategy but uses a better ordering heuristic. Colamd is faster and computes better orderings, with fewer nonzeros in the factors of the matrix.

Supporting File: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.