csymamd

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

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

Adapted from the CCOLAMD documentation [1]:

This function computes an approximate minimum degree ordering for Cholesky factorization of symmetric matrices.

Symamd 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. Symamd constructs a matrix M such that \(M^{\top}M\) has the same nonzero pattern of A, and then orders the columns of M using ccolamd. The column ordering of M is then returned as the row and column ordering P of A.

Parameters:

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

Note

This routine only accesses the lower triangular part of A, which is assumed to be symmetric. If it is not, the results may be incorrect or undefined.

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_threshfloat, 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.

aggressivebool, optional

If True, use aggressive absorption. If None, uses the default value from CCOLAMD. The default value is True.

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

ccolamd, colamd, symamd

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from sksparse.ccolamd import csymamd
>>> # 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
>>> A = (A.T @ A).tocsc()  # make A symmetric
>>> # 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 = csymamd(A, constraints=C, return_info=True)
>>> p
array([0, 1, 2, 3, 7, 6, 5, 4], dtype=int32)
>>> info
CCOLAMDStats(N_rows_ignored=0, N_cols_ignored=0, Ncmpa=0, status=0, info1=-1,
    info2=-1, info3=0)