Crate nalgebra_block_triangularization 

Block triangularization of sparse matrices using graph algorithms.

This library computes row and column permutations that reveal the block triangular structure of a sparse matrix, supporting both upper and lower block triangular forms.

Examples

use nalgebra::DMatrix;
use nalgebra_block_triangularization::upper_triangular_permutations;

let m = DMatrix::from_row_slice(3, 3, &[1, 1, 0, 0, 1, 1, 0, 0, 1]);
let (pr, pc) = upper_triangular_permutations(&m);

let mut u = m.clone();
pr.permute_rows(&mut u);
pc.permute_columns(&mut u);

Modules

adjacency

Graph construction from matrix sparsity patterns.

matching

Maximum bipartite matching algorithms.

ordering

Topological sorting and column ordering.

permutation

Conversion to nalgebra permutation sequences.

scc

Strongly connected components algorithms.

Structs

LowerBtfStructure

Structural information from lower block triangular decomposition.

UpperBtfStructure

Structural information from upper block triangular decomposition.

Functions

lower_block_triangular_structure

Compute the lower block triangular structure of a matrix.

lower_triangular_permutations

Return row/column permutations P, Q (as PermutationSequence) such that: L = P * mat * Q is (lower) block triangular with respect to the SCC block structure induced by a maximum matching.

upper_block_triangular_structure

Compute the upper block triangular structure of a matrix.

upper_triangular_permutations

Return row/column permutations P, Q (as PermutationSequence) such that: U = P * mat * Q is (upper) block triangular with respect to the SCC block structure induced by a maximum matching.