camd

sksparse.camd.camd(A, constraints=None, dense_thresh=None, aggressive=None, return_info=False)[source]

Compute the approximate minimum degree ordering of a sparse matrix.

Adapted from the SuiteSparse camd.h documentation [0]:

CAMD finds a fill-reducing ordering of a sparse matrix A, using the approximate minimum degree algorithm. The output is a permutation vector p such that the Cholesky factor of A[p][:, p] has fewer nonzeros than the Cholesky factor of A. If A is not symmetric, the algorithm computes an ordering of A + A.T.

For more details on the entire package, see the SuiteSparse homepage [1] and Github repository [2].

Parameters:

  • A ((N, N) array_like or sparse matrix) – A square matrix in CSC format or convertible to CSC.

  • constraints ((N,) array_like, optional) – A 1D array of constraints for the ordering. Each node i in the graph of A has a constraint, constraints[i], in the range [0, N-1]. All nodes with constraints[i] = 0 are ordered first, followed by nodes with C(i) = 1, and so on. Thus, constraints[p] is monotonically non-decreasing. If None, no constraints are applied, and the ordering will be similar to amd(), except that the post-ordering is different.

  • dense_thresh (float, optional) – Threshold number of entries for considering a row/column dense. If None, use the default value from CAMD. The default value is 10.

    Adapted from the SuiteSparse camd.h documentation [0]:

    A dense row/column in A + A.T can cause CAMD to spend a lot of time in ordering the matrix. If dense_thresh >= 0, rows/columns with more than max(dense_thresh * sqrt(N), 16) entries are ignored during the ordering, and placed last in the output order. The default value of dense_thresh is 10. If negative, no rows/columns are treated as “dense”. Rows/columns with 16 or fewer off-diagonal entries are never considered “dense”.

  • aggressive (bool, optional) – If True, use aggressive absorption. If None, uses the default value from CAMD. The default value is True.

    Adapted from the SuiteSparse camd.h documentation [0]:

    Controls whether or not to use aggressive absorption, in which a prior element is absorbed into the current element if is a subset of the current element, even if it is not adjacent to the current pivot element (refer to Amestoy, Davis, & Duff, 1996, for more details). The default value is True, which means to perform aggressive absorption. This nearly always leads to a better ordering (because the approximate degrees are more accurate) and a lower execution time. There are cases where it can lead to a slightly worse ordering, however.

  • return_info (bool, optional) – If True, returns additional information about the ordering process. Default is False.

Returns:

  • p (ndarray) – The permutation vector such that the Cholesky factor of A[p][:, p] has fewer nonzeros than the Cholesky factor of A.

  • info (ndarray, optional) – Additional information about the ordering process, returned if return_info is True. Contains various statistics and status codes.

Raises:

  • SparseEfficiencyWarning – If the input matrix is not in CSC format, a warning is raised and the matrix is converted to CSC format.

  • ValueError – If the input matrix is not square or cannot be converted to CSC format.

  • CAMDInvalidMatrixError – If the input matrix is invalid for CAMD, such as having unsupported data types or formats.

  • CAMDMemoryError – If the CAMD algorithm runs out of memory during execution.

See also

amd, colamd, ccolamd

Notes

This function wraps the CAMD (Approximate Minimum Degree) algorithm from the SuiteSparse by Timothy A. Davis. For details, see the SuiteSparse repository [2].

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import coo_array
>>> from sksparse.camd import camd
>>> # Create a symmetric positive definite matrix from (Davis, Eqn 2.1)
>>> N = 11
>>> rows = np.array([5, 6, 2, 7, 9, 10, 5, 9, 7, 10, 8, 9, 10, 9, 10, 10])
>>> cols = np.array([0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 9])
>>> rng = np.random.default_rng(565656)
>>> vals = rng.random(len(rows), dtype=np.float64)
>>> L = coo_array((vals, (rows, cols)), shape=(N, N))
>>> A = L + L.T   # make it symmetric
>>> A.setdiag(N)  # make it strongly positive definite
>>> A = A.tocsc()
>>> # Constrain the first K nodes to be ordered first
>>> K = 4
>>> C = np.full(N, K)
>>> C[:K] = np.arange(K)  # constrained nodes
>>> p, info = camd(A, constraints=C, return_info=True)
>>> p
array([ 0,  1,  2,  3,  8,  5,  6,  9,  4, 10,  7])
>>> info
CAMDInfo(status=0, N=11, nz=43, symmetry=1.0, nzdiag=11, nz_A_plus_AT=32,
    Ndense=0, memory=1248.0, Ncmpa=0, Lnz=19, Ndiv=19, Nmultsubs_LDL=29,
    Nmultsubs_LU=39, dmax=4)