nesdis

sksparse.cholmod.nesdis(A, *, kind=None, return_separator=False, nd_small=None, nd_components=None, nd_oksep=None, nd_camd=None)

Nested dissection ordering of a sparse matrix.

Parameters:

• A ((M, N) csc_array) – The input matrix in Compressed Sparse Column (CSC) format. Must be square and symmetric if kind is None or "sym". No check is made for symmetry.

• kind (str in {“sym”, “row”, “col”}, optional) – The type of factorization for which to analyze the matrix:

  • sym: Symmetric factorization. Only the upper triangular part of A is used, and no check is made for symmetry.

  • row: Unsymmetric factorization of \(A A^{\top}\).

  • col: Unsymmetric factorization of \(A^{\top} A\).

  If kind is None, it defaults to sym.

• return_separator (bool, optional) – If True, the function returns the separator tree and component membership vector. Default is False.

Returns:

• p ((M or N,) ndarray of int) – The permutation vector that gives the nested dissection ordering of the nodes in the graph represented by the sparse matrix A.

• septree (SeparatorTree, optional) – The separator tree and component membership vector, returned if return_separator is True.

Other Parameters:

• nd_small (int, optional) – The smallest subgraph that should not be partitioned (default is 200).

• nd_components (bool, optional) – True if connected components should be split independently (default is False).

• nd_oksep (double, optional) – Controls when a separator is kept. A separator is kept if nsep < nd_oksep * n, where nsep is the number of nodes in the separator and n is the number of nodes in the graph being cut (default is 1).

• nd_camd (int, optional) – Controls whether the smallest subgraphs should be ordered. If 0, they are not ordered. For the “sym” case, 1 to order by camd, 2 to order by csymamd (default 1). For other cases: 0 to order naturally, or 1 to order by colamd.

See also

bisect, metis

Notes

This function is based on the SuiteSparse CHOLMOD MATLAB interface [1].

Added in version 0.5.0.

References

[1]

nesdis.c - CHOLMOD MATLAB nesdis function https://github.com/DrTimothyAldenDavis/SuiteSparse/blob/dev/CHOLMOD/MATLAB/nesdis.c

Examples

>>> import numpy as np
>>> from scipy.sparse import coo_array
>>> from sksparse.cholmod import nesdis
>>> # 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(56)
>>> 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, s = nesdis(A, return_separator=True)
>>> p
array([ 1,  4,  6,  8,  0,  3,  5,  2,  9, 10,  7])
>>> s
SeparatorTree(components=1, nodes=11)