The COLAMD column approximate minimum degree ordering algorithm computes
a permutation vector P such that the LU factorization of A (:,P)
tends to be sparser than that of A. The Cholesky factorization of
(A (:,P))'*(A (:,P)) will also tend to be sparser than that of A'*A.
SYMAMD is a symmetric minimum degree ordering method based on COLAMD,
available as a
MATLAB-callable function.
It constructs a matrix M such
that M'*M has the same pattern as A, and then uses COLAMD to compute a column
ordering of M.
Colamd and symamd tend to be faster and generate better orderings than
their MATLAB counterparts, colmmd and symmmd.
Results
-
We compared COLAMD, COLMMD, and AMDBAR on a large set of test
matrices (281 square unsymmetric matrices and 157 rectangular matrices
- including
all Netlib linear programming problems). We looked at A'A (least squares)
if the matrix had more rows than columns, or AA' otherwise (interior point
methods). We compared SYMAMD, SYMMMD, and AMDBAR on a set
of 200 symmetric test matrices.
-
For large square, unsymmetric matrices,
COLAMD is 3.8 times faster than MATLAB's COLMMD
(a median result; up to 110 times faster for a small matrices,
and 52 times faster for a large matrix),
and
2.2 times faster than AMDBAR on A'A
(up to 26 times faster).
It produces
better orderings than MATLAB's COLMMD
(typical reduction of 10%
in nonzeros in L and U, and 30% reduction in flop count), and comparable
orderings as AMDBAR.
AMDBAR also requires the explicit formation of A'A or
AA', but COLAMD does not (and thus COLAMD uses less memory).
- For large, rectangular matrices, COLAMD is typically twice as
fast (a median result) as MATLAB's COLMMD, and slightly faster than AMDBAR.
Its ordering quality is better than COLMMD (typical reduction of 5%
in the nonzeros in the Cholesky factorization of A'A or AA', and 12%
reduction in flop count). It has about the same ordering quality as
AMDBAR. AMDBAR also requires the explicit formation of A'A or
AA', but COLAMD does not (and thus COLAMD uses less memory).
- For large, symmetric matrices,
SYMAMD is 11 times faster than MATLAB's SYMMMD
(a median result; up to 83 times faster).
However, it is much slower than AMDBAR (3.5 times slower; up to 12 times
slower at worst). Using
SYMAMD results in a 20% reduction in nonzeros, compared with MATLAB's SYMMMD,
and a 40% reduction in flop count.
It produces orderings of about the same quality as AMDBAR.
Copyright (c) 1998-2007.
Authors: Stefan I. Larimore and Timothy A. Davis, University of Florida,
in collaboration with
John Gilbert,
Xerox PARC, and
Esmong Ng,
Lawrence Berkeley National Laboratory
(much of this work he did while at Oak Ridge National Laboratory).
