CVXOPT includes an interface to the AMD library for computing approximate minimum degree orderings of sparse matrices.

See also:

• AMD code, documentation, copyright and license.
• P. R. Amestoy, T. A. Davis, I. S. Duff, Algorithm 837: AMD, An Approximate Minimum Degree Ordering Algorithm, ACM Transactions on Mathematical Software, 30(3), 381-388, 2004.

order(A[, uplo='L'])

Computes the approximate mimimum degree ordering of a symmetric sparse matrix A. The ordering is returned as an integer dense matrix with length equal to the order of A. Its entries specify a permutation that reduces fill-in during the Cholesky factorization. More precisely, if p = order(A), then A[p,p] has sparser Cholesky factors than A.

As an example we consider the matrix

>>> from cvxopt.base import spmatrix
>>> from cvxopt import amd 
>>> A = spmatrix([10,3,5,-2,5,2], [0,2,1,2,2,3], [0,0,1,1,2,3])
>>> P = amd.order(A)
>>> print P
[ 1]
[ 0]
[ 2]
[ 3]