7.1 Matrix Orderings (cvxopt.amd)

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

\begin{displaymath}
\left[ \begin{array}{rrrr}
10 & 0 & 3 & 0 \\
0 & 5 & 0 & -2 \\
3 & 0 & 5 & 0 \\
0 & -2 & 0 & 2
\end{array}\right].
\end{displaymath}

>>> 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