apex_solver/linalg/sparse/
pattern.rs

1//! Structural fingerprints for sparse-matrix caches.
2//!
3//! Several solvers cache work keyed on "the sparsity pattern hasn't changed":
4//! the normal-equations symbolic product, the chunk-wise Schur layout, the
5//! `H_ee` block-diagonality verdict and the implicit-Schur visibility index.
6//! All of them used to key on the `(nrows, ncols, nnz)` triple, which aliases
7//! patterns that permute entries at equal nonzero count — reusing a stale
8//! cache for such a pattern silently produces a wrong step.
9//!
10//! [`PatternFingerprint`] keeps the triple as a fast reject but adds a
11//! deterministic FNV-1a hash over the full column-row structure, so equality
12//! means "same pattern" and not just "same shape". The hash costs one O(nnz)
13//! integer pass per check — negligible next to the floating-point assembly it
14//! guards. (FNV, not `std`'s `DefaultHasher`: the latter is randomly seeded
15//! per instance and cannot be compared across caches.)
16
17use faer::sparse::SparseColMat;
18
19/// Fold one value into an FNV-1a hash.
20///
21/// Values are pre-mixed with a golden-ratio multiply because raw structural
22/// indices (0, 1, 2, …) carry entropy only in their low bits; without the mix
23/// consecutive columns would cancel each other out of the hash.
24#[inline]
25fn fold(mut hash: u64, value: usize) -> u64 {
26    const PRIME: u64 = 0x100000001b3;
27    const MIX: u64 = 0x9E3779B97F4A7C15;
28    hash ^= (value as u64).wrapping_mul(MIX);
29    hash.wrapping_mul(PRIME)
30}
31
32/// Structural identity of a sparse matrix: dimensions, nonzero count, and a
33/// hash of the full sparsity pattern.
34///
35/// Compare with `==`: the three cheap fields reject first, so the common
36/// "same pattern" case costs three integer compares and the "different shape"
37/// case never touches the hash.
38///
39/// `Default` is the all-zero placeholder (never equal to a real fingerprint);
40/// caches holding it must overwrite it at build time, as before.
41#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
42pub struct PatternFingerprint {
43    nrows: usize,
44    ncols: usize,
45    nnz: usize,
46    hash: u64,
47}
48
49impl PatternFingerprint {
50    /// Fingerprint the sparsity pattern of `matrix` (values ignored).
51    pub fn of(matrix: &SparseColMat<usize, f64>) -> Self {
52        let symbolic = matrix.symbolic();
53        // One xor-multiply per structural integer — the same pass `compute_nnz`
54        // style checks already pay, against O(nnz) floating-point assembly
55        // plus factorization downstream.
56        let mut hash: u64 = 0xcbf29ce484222325;
57        hash = fold(hash, matrix.nrows());
58        hash = fold(hash, matrix.ncols());
59        let mut nnz = 0usize;
60        for col in 0..matrix.ncols() {
61            let rows = symbolic.row_idx_of_col_raw(col);
62            hash = fold(hash, rows.len());
63            for &row in rows {
64                hash = fold(hash, row);
65                nnz += 1;
66            }
67        }
68        Self {
69            nrows: matrix.nrows(),
70            ncols: matrix.ncols(),
71            nnz,
72            hash,
73        }
74    }
75
76    /// Rows of the fingerprinted matrix.
77    pub fn nrows(&self) -> usize {
78        self.nrows
79    }
80
81    /// Columns of the fingerprinted matrix.
82    pub fn ncols(&self) -> usize {
83        self.ncols
84    }
85
86    /// Nonzero count of the fingerprinted matrix.
87    pub fn nnz(&self) -> usize {
88        self.nnz
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95    use faer::sparse::Triplet;
96
97    type TestResult = Result<(), Box<dyn std::error::Error>>;
98
99    #[test]
100    fn equal_patterns_agree() -> TestResult {
101        let t = vec![
102            Triplet::new(0usize, 0usize, 1.0f64),
103            Triplet::new(1, 0, 2.0),
104            Triplet::new(1, 1, 3.0),
105        ];
106        let a = SparseColMat::try_new_from_triplets(2, 2, &t)?;
107        let b = SparseColMat::try_new_from_triplets(2, 2, &t)?;
108        assert_eq!(PatternFingerprint::of(&a), PatternFingerprint::of(&b));
109        // Values are ignored: same pattern, different values still match.
110        let t2 = vec![
111            Triplet::new(0usize, 0usize, 9.0f64),
112            Triplet::new(1, 0, 8.0),
113            Triplet::new(1, 1, 7.0),
114        ];
115        let c = SparseColMat::try_new_from_triplets(2, 2, &t2)?;
116        assert_eq!(PatternFingerprint::of(&a), PatternFingerprint::of(&c));
117        Ok(())
118    }
119
120    #[test]
121    fn permuted_pattern_at_equal_nnz_disagrees() -> TestResult {
122        let t = vec![
123            Triplet::new(0usize, 0usize, 1.0f64),
124            Triplet::new(1, 0, 2.0),
125            Triplet::new(1, 1, 3.0),
126        ];
127        let a = SparseColMat::try_new_from_triplets(2, 2, &t)?;
128        // Same shape (2x2) and same nnz (3), but column 1 holds row 0
129        // instead of row 1: a genuinely different pattern.
130        let t2 = vec![
131            Triplet::new(0usize, 0usize, 1.0f64),
132            Triplet::new(1, 0, 2.0),
133            Triplet::new(0, 1, 3.0),
134        ];
135        let b = SparseColMat::try_new_from_triplets(2, 2, &t2)?;
136        assert_eq!((a.nrows(), a.ncols(), 3), (b.nrows(), b.ncols(), 3));
137        assert_ne!(
138            PatternFingerprint::of(&a),
139            PatternFingerprint::of(&b),
140            "equal-nnz permutation must invalidate the fingerprint"
141        );
142        Ok(())
143    }
144}
apex_solver/linalg/sparse/pattern.rs

apex_solver/linalg/sparse/
pattern.rs
