maxtrans

sksparse.btf.maxtrans(A)

Compute the maximum transversal of a sparse matrix.

This function finds a permutation of the columns of a sparse matrix so that it has a zero-free diagonal, if possible [1].

Parameters:

A ((M, N) {array-like, sparse array}) – An array convertible to a sparse matrix in Compressed Sparse Column (CSC) format.

Returns:

• jmatch ((M,) ndarray) – Array containing the maximum transversal.

  Adapted from the BTF maxtrans documentation [1]:

  The output is an array jmatch of size N. If row i is matched with column j, then A[i, j] is nonzero, and then jmatch[i] = j. If the matrix is structurally nonsingular, all entries in the jmatch array are unique, and jmatch can be viewed as a column permutation if A is square. That is, column k of the original matrix becomes column jmatch[k] of the permuted matrix.

  If row i is not matched with any column, then jmatch[i] = -1.

• .. versionadded:: 0.5.0

References

[1] (1,2)

BTF maxtrans header file: https://github.com/DrTimothyAldenDavis/SuiteSparse/blob/dev/BTF/Include/btf.h

Examples

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from sksparse.btf import maxtrans
>>> # Create a non-symmetric matrix
>>> N = 11
>>> rng = np.random.default_rng(56)
>>> A = random_array((N, N - 3), density=0.5, format='csc', rng=rng)
>>> jmatch = maxtrans(A)
>>> jmatch
array([ 0,  2,  1,  3,  4,  5,  7, -1,  6, -1, -1], dtype=int32)