ccolamd

sksparse.ccolamd.ccolamd(A, constraints=None, dense_row_thresh=None, dense_col_thresh=None, aggressive=None, opt_lu=None, return_info=False)[source]

Compute the column approximate minimum degree ordering of a sparse matrix.

Adapted from the CCOLAMD documentation [1]:

This function computes a column ordering for a sparse matrix A that is appropriate for LU factorization of symmetric or unsymmetric matrices, QR factorization, least squares, interior point methods for linear programming problems, and other related problems.

CCOLAMD computes a permutation Q such that the Cholesky factorization of \((AQ)^{\top}(AQ)\) has less fill-in and requires fewer floating point operations than \(A^{\top}A\). This also provides a good ordering for sparse partial pivoting methods, \(P(AQ) = LU\), where Q is computed prior to numerical factorization, and P is computed during numerical factorization via conventional partial pivoting with row interchanges.

Parameters:

  • A ((M, N) {array_like, sparse matrix}) – The input matrix for which to compute the column ordering. Must be 2D and convertible to CSC format. Need not be square.

  • contraints ((N,) array_like, optional) – A 1D array of constraints for the ordering. Each column i in A has a constraint, constraints[i], in the range [0, N-1]. All columns 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 colamd(), except that the default values of dense_row_thresh, dense_col_thresh, and aggressive may differ.

  • dense_row_thresh, dense_col_thresh (float, optional) – Threshold for considering a row/column dense. If None, use the default value from CCOLAMD. The default value is 10. The actual number of entries in a row/column is to be considered “dense” is max(dense_row_thresh * sqrt(M), 16) where M is the number of rows (or N for columns). Dense rows/columns are ignored during ordering and moved to the end of the matrix.

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

  • opt_lu ({‘lu’, ‘cholesky’}, optional) – If ‘lu’, the ordering is optimized for LU factorization of A. If ‘cholesky’, the ordering is optimized for Cholesky factorization of \(A^{\top} A\). If None, uses the default value from CCOLAMD, which is ‘cholesky’.

Returns:

  • q ((N,) ndarray) – The permutation vector.

  • stats (CCOLAMDStats, optional) – If return_info is True, returns an object containing statistics about the ordering.

See also

csymamd, colamd, symamd

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from sksparse.ccolamd import ccolamd
>>> # Create a non-symmetric matrix
>>> N = 11
>>> rng = np.random.default_rng(56)
>>> A = random_array((N, N - 3), density=0.5, format='csc', rng=rng)
>>> A.setdiag(N)  # make the diagonal non-zero
>>> # Constrain the first K nodes to be ordered first
>>> K = 4
>>> C = np.full(A.shape[1], K)
>>> C[:K] = np.arange(K)  # constrained nodes
>>> p, info = ccolamd(A, constraints=C, return_info=True)
>>> p
array([0, 1, 2, 3, 4, 7, 6, 5], dtype=int32)
>>> info
CCOLAMDStats(N_rows_ignored=0, N_cols_ignored=0, Ncmpa=0, status=0, info1=-1,
    info2=-1, info3=0)