btf

sksparse.btf.btf(A)[source]

Permute the square sparse matrix into Block Triangular Form (BTF).

This function finds a permutation of a sparse matrix so that PAQ (A[p][:, q]) is block upper triangular form with a zero-free diagonal, or with a maximum number of nonzeros on the diagonal if a zero-free permutation does not exist [1].

Parameters:

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

Returns:

  • p ((N,) ndarray of int) – The row permutation vector such that A[p][:, q] is in block upper triangular form.

  • q ((N,) ndarray of int) – The column permutation vector. If A is structurally nonsingular, A[p][:, q] has a zero-free diagonal. If A is structurally singular, q will contain negative entries. The permuted matrix is A[p][:, abs(q)]. If q[k] < 0, then PAQ[k, k] is zero.

  • r ((Nb+1,) ndarray of int) – The array of indices of the start of each block in the permuted matrix. Block b is in rows/columns r[b] to r[b+1] - 1. The number of blocks is len(r) - 1.

Notes

Adapted from the BTF documentation [1]:

The function finds a maximum matching (or perhaps a limited matching if the work is limited), via the maxtrans() function. If a complete matching is not found, btf() completes the permutation, but flags the columns of A[p][:, q] to denote which columns are not matched. If the matrix is structurally rank deficient, some of the entries on the diagonal of the permuted matrix will be zero.

Added in version 0.5.0.

References

Examples

>>> import numpy as np
>>> from scipy.sparse import random_array, block_diag
>>> from sksparse.btf import btf
>>> # Create a matrix with at least 2 strongly connected components
>>> M, N = 4, 7
>>> rng = np.random.default_rng(56)
>>> A0 = random_array((M, M), density=0.5, rng=rng)
>>> A1 = random_array((N, N), density=0.5, rng=rng)
>>> A = block_diag((A0, A1), format='csc')
>>> # The first M rows/columns are ordered together, then the last N
>>> p, q, r = btf(A)
>>> p
array([ 0,  3,  1,  2, 10,  4,  5,  6,  7,  8,  9], dtype=int32)
>>> q
array([ 0,  1,  2, -5, 10,  6,  5,  7,  8,  4,  9], dtype=int32)
>>> r
array([ 0,  2,  3,  4,  5, 11,  9, 10,  0,  0,  0,  0], dtype=int32)