Constrained Column Approximate Minimum Degree (CCOLAMD) Ordering (sksparse.ccolamd)

The sksparse.ccolamd module provides efficient an implementation of the Column Approximate Minimum Degree (CCOLAMD) ordering algorithm for sparse matrices.

It exposes the main functions of the CCOLAMD package, which computes a column ordering \(Q\) of a sparse matrix that minimizes the fill-in of the Cholesky decomposition of \((AQ)^{\top}(AQ)\). The ccolamd() function is appropriate for use with non-symmetric and non-square matrices, for LU factorization, QR factorization, and other decompositions that require a column ordering.

This module also provides a symmetric variant, csymamd(), which computes a permutation P of a symmetric matrix A such that the Cholesky factorization of \(PAP^{\top}\) has less fill-in and requires fewer floating point operations than A. This function assumes that its input is symmetric.

The ccolamd() and csymamd() functions accept both real and complex matrices, in any format supported by scipy.sparse (CSC format is most efficient).

These function are identical to that of the COLAMD package (sksparse.colamd), except that they allow the user to specify a set of constraints on the ordering of the matrix.

Quickstart

If \(A\) is a sparse matrix, then the following code computes the CCOLAMD ordering of \(A\):

from sksparse.ccolamd import ccolamd
A = ...  # some sparse matrix
# Set some constraints, e.g., to fix the first K rows and columns
N = A.shape[0]
K = N // 2                     # number of constrained variables
C = np.full(N, K)              # none are constrained (all == K)
C[:K] = np.arange(K)           # first K variables are constrained
q = ccolamd(A, constraints=C)
AQ = A[:, q]                   # permute the columns of A

to give the permuted matrix \(AQ\), where \(Q\) is the permutation matrix corresponding to the ordering \(q\).

We can then continue from above to compute the LU decompositions of the original and permuted matrix, and compare the number of non-zeros in each:

from scipy.sparse.linalg import splu
lu = splu(A)
luq = splu(A[:, q])
L, U = lu.L, lu.U
Lq, Uq = luq.L, luq.U
print("Number of non-zeros in L + U:  ", (L + U).nnz)
print("Number of non-zeros in Lq + Uq:", (Lq + Uq).nnz)

The number of non-zeros in the LU factorization of the permuted matrix should be less than or equal to the number of non-zeros in the LU factorization of the original matrix, but this is not guaranteed.

CCOLAMDStats Objects

An CCOLAMDStats object is a dataclass returned by the ccolamd() function when the return_info parameter is set to True. It contains information about the ordering, including the return status.

Typically, the CCOLAMDStats object is unnecessary, and you can just use the permutation vector returned by ccolamd().

Convenience Methods

The CCOLAMD package also provides a convenience function, ccolamd_get_defaults() to get the default control parameters from the CCOLAMD package. Most users will not need to use this function, as the default control parameters are used automatically by ccolamd().

Error Handling

Errors raised by the CCOLAMD package are converted into Python exceptions. See the Exceptions and Warnings for details.