etree

sksparse.cholmod.etree(A, *, kind=None, return_post=False)[source]

Symbolic factorization of a sparse matrix for Cholesky or LDL.

This function determines the elimination tree of a sparse matrix A, and optionally postorders the tree [1].

Parameters:

  • A ((N, N) csc_array) – The input matrix in Compressed Sparse Column (CSC) format. Must be square and symmetric. No check is made for symmetry, so the upper (or lower) triangular part of the matrix is used for the factorization, depending on the lower parameter.

  • 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\).

    • lo: Lower triangular factorization. Same as symbfact(A.T). Only the lower triangular part of A is used, and no check is made for symmetry.

    If kind is None, it defaults to sym.

  • return_post (bool, optional) – If True, the function returns the postorder of the elimination tree. Default is False.

Returns:

  • parent ((N,) ndarray of int) – The parent of each node in the elimination tree. The root has no parent (parent[0] = -1).

  • post ((N,) ndarray of int, optional) – The postorder of the elimination tree. The first node in the postorder is the root of the tree.

Added in version 0.5.0.

See also

symbfact

References

Examples

>>> import numpy as np
>>> from scipy.sparse import coo_array
>>> from sksparse.cholmod import etree
>>> # 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()
>>> parent, post = etree(A, return_post=True)
>>> parent
array([ 5,  2,  7,  5,  7,  6,  8,  9,  9, 10, -1])
>>> post
array([ 1,  2,  4,  7,  0,  3,  5,  6,  8,  9, 10])