metis¶

sksparse.cholmod.metis(A, *, kind=None)[source]¶

Nested dissection ordering of a sparse matrix using METIS.

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:

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.

See also

bisect, nesdis

Notes

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

Added in version 0.5.0.

References

Examples

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