symamd¶

sksparse.colamd.symamd(A, 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 COLAMD 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 colamd. The column ordering of M is then returned as the row and column ordering P of A.

Parameters:: A ((N, N) {array_like, 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.

dense_row_thresh, dense_col_threshfloat, optional: Threshold for considering a row/column dense. If None, use the default value from COLAMD. 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 COLAMD. The default value is True.

Returns:

q ((N,) ndarray) – The permutation vector.
stats (COLAMDStats, optional) – If return_info is True, returns an object containing statistics about the ordering.

See also

colamd, ccolamd, csymamd

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from sksparse.colamd import symamd
>>> # 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 it symmetric
>>> p, info = symamd(A, return_info=True)
>>> p
array([4, 6, 7, 0, 1, 2, 3, 5], dtype=int32)
>>> info
COLAMDStats(N_rows_ignored=0, N_cols_ignored=0, Ncmpa=0, status=0, info1=-1,
    info2=-1, info3=0)