colamd

sksparse.colamd.colamd(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 matrix.

Adapted from the COLAMD 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.

COLAMD 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 or sparse matrix) – The input matrix for which to compute the column ordering. Must be 2D and convertible to CSC format. Need not be square.

  • dense_row_thresh, dense_col_thresh (float, 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.

  • aggressive (bool, 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

symamd, ccolamd, csymamd

Added in version 0.5.0.

References

Examples

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