bisect

sksparse.cholmod.bisect(A, *, kind=None)

Compute a node separator for a sparse matrix graph.

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.

Returns:

s ((K,) ndarray of int) – The dimension K is either M or N, depending on the kind parameter. The output can take 3 values:

• 0: The node is in the left subgraph.

• 1: The node is in the right subgraph.

• 2: The node is in the separator.

See also

nesdis, metis

Notes

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

Added in version 0.5.0.

References

[1]

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

Examples

>>> import numpy as np
>>> from scipy.sparse import coo_array
>>> from sksparse.cholmod import bisect
>>> # 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()
>>> s = bisect(A)
>>> s
array([0, 1, 1, 0, 1, 0, 0, 1, 0, 2, 2])