symbfact

sksparse.cholmod.symbfact(A, *, kind=None, lower=False, return_factor=False)[source]

Symbolic factorization of a sparse matrix for Cholesky or LDL.

This function performs the symbolic factorization of a sparse matrix A for either Cholesky or LDL factorization. It computes the elimination tree and analyzes the sparsity pattern of the matrix [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.

  • lower (bool, optional) – If True, the symbolic factorization is performed on the lower triangular part of the matrix. If False, the upper triangular part is used. Default is False (upper triangular).

  • return_factor (bool, optional) – If True, the symbolic factorization returns the structure of the Cholesky factor L (or LD for LDL factorization) as a sparse matrix. Default is False.

Returns:

  • count ((N,) ndarray of int) – The count of nonzeros in each column of the Cholesky factor.

  • h (int) – The height of the elimination tree.

  • 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) – The postorder of the elimination tree. The first node in the postorder is the root of the tree.

  • L ((N, N) csc_array) – The symbolic factorization of the matrix. Only returned if return_factor is True.

See also

etree

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import coo_array
>>> from sksparse.cholmod import cholesky, symbfact
>>> # 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()
>>> L = cholesky(A, lower=True)
>>> count, h, parent, post = symbfact(A)
>>> count
array([3, 3, 4, 3, 3, 4, 4, 3, 3, 2, 1])
>>> np.array_equal(count, np.count_nonzero(L.toarray(), axis=0))
True
>>> h
6
>>> 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])