numr 0.5.1

High-performance numerical computing with multi-backend GPU acceleration (CPU/CUDA/WebGPU)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//! Traits for bipartite matching algorithms.

use crate::error::Result;

/// Trait for bipartite matching algorithms on sparse matrices.
///
/// These algorithms find maximum matchings in the bipartite graph formed by
/// the row-column structure of a sparse matrix. A matching pairs rows with
/// columns such that each row and column appears in at most one pair.
pub trait BipartiteMatching {
    /// Compute maximum transversal (row permutation for diagonal nonzeros).
    ///
    /// Given a sparse matrix A, finds a row permutation P such that P*A has
    /// maximum number of nonzeros on the diagonal. This is equivalent to finding
    /// a maximum matching in the bipartite graph where rows and columns are
    /// vertices and nonzeros are edges.
    ///
    /// # Arguments
    ///
    /// * `n_rows` - Number of rows in the matrix
    /// * `n_cols` - Number of columns in the matrix
    /// * `col_ptrs` - CSC column pointers (length n_cols + 1)
    /// * `row_indices` - CSC row indices
    ///
    /// # Returns
    ///
    /// Tuple of (row_perm, col_match) where:
    /// - `row_perm[i]` = row index that should be in position i (or -1 if unmatched)
    /// - `col_match[j]` = row matched to column j (or -1 if unmatched)
    fn maximum_transversal(
        &self,
        n_rows: usize,
        n_cols: usize,
        col_ptrs: &[i64],
        row_indices: &[i64],
    ) -> Result<(Vec<i32>, Vec<i32>)>;

    /// Compute structural rank of a sparse matrix.
    ///
    /// The structural rank is the maximum number of nonzeros that can be placed
    /// on the diagonal by row and column permutations. It equals the size of
    /// the maximum matching.
    ///
    /// # Arguments
    ///
    /// * `n_rows` - Number of rows in the matrix
    /// * `n_cols` - Number of columns in the matrix
    /// * `col_ptrs` - CSC column pointers
    /// * `row_indices` - CSC row indices
    ///
    /// # Returns
    ///
    /// The structural rank (0 to min(n_rows, n_cols)).
    fn structural_rank(
        &self,
        n_rows: usize,
        n_cols: usize,
        col_ptrs: &[i64],
        row_indices: &[i64],
    ) -> Result<usize>;
}