Expand description
Approximate minimum degree column ordering algorithms.
colamd: an approximate minimum degree column ordering algorithm, for LU factorization of symmetric or unsymmetric matrices, QR factorization, least squares, interior point methods for linear programming problems, and other related problems.
symamd: an approximate minimum degree ordering algorithm for Cholesky factorization of symmetric matrices.
Colamd computes a permutation Q
such that the Cholesky factorization of
(AQ)'(AQ)
has less fill-in and requires fewer floating point operations
than A'A
. This also provides a good ordering for sparse partial
pivoting methods, P(AQ) = LU
, where Q
is computed prior to numerical
factorization, and P
is computed during numerical factorization via
conventional partial pivoting with row interchanges.
Symamd computes a permutation P
of a symmetric matrix A such that the
Cholesky factorization of PAP'
has less fill-in and requires fewer
floating point operations than A
. Symamd constructs a matrix M
such
that M'M
has the same nonzero pattern of A
, and then orders the columns
of M
using colmmd. The column ordering of M
is then returned as the
row and column ordering P
of A
.
The authors of the code itself are Stefan I. Larimore and Timothy A. Davis (davis at cise.ufl.edu), University of Florida. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory.
This work was supported by the National Science Foundation, under grants DMS-9504974 and DMS-9803599.
Constants
knobs[]
array. Only knobs[0..1]
are currently used.stats[0..6]
are currently used.Functions
Q
of a sparse matrix
A
such that the LU factorization P(AQ) = LU
remains sparse,
where P
is selected via partial pivoting. The routine can also
be viewed as providing a permutation Q
such that the Cholesky
factorization (AQ)'(AQ) = LL'
remains sparse.colamd
statistics to standard output.colamd
and symamd
.a_len
.P
of a symmetric sparse matrix A
such that
the Cholesky factorization PAP' = LL'
remains sparse.symamd
statistics to standard output.