amd¶

sksparse.amd.amd(A, dense_thresh=None, aggressive=None, return_info=False)[source]¶

Compute the approximate minimum degree ordering of a sparse matrix.

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

AMD 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.
dense_thresh (float, optional) – Threshold number of entries for considering a row/column dense. If None, use the default value from AMD. The default value is 10.

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

A dense row/column in A + A.T can cause AMD 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 AMD. The default value is True.

Adapted from the SuiteSparse amd.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.
AMDInvalidMatrixError – If the input matrix is invalid for AMD, such as having unsupported data types or formats.
AMDMemoryError – If the AMD algorithm runs out of memory during execution.

See also

camd, colamd, ccolamd

Notes

This function wraps the AMD (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.amd import amd
>>> # 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()
>>> p, info = amd(A, return_info=True)
>>> p
array([ 1,  4,  8,  6,  0,  3,  5,  2,  9, 10,  7])
>>> info
AMDInfo(status=0, N=11, nz=43, symmetry=1.0, nzdiag=11, nz_A_plus_AT=32,
    Ndense=0, memory=1096.0, Ncmpa=0, Lnz=19, Ndiv=19, Nmultsubs_LDL=29,
    Nmultsubs_LU=39, dmax=4)