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:

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

⌊                ⌋
  10    0  3   0
||  0    5  0 - 2 ||.
⌈  3    0  5   0 ⌉
   0  - 2  0   2

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