perspt_sdk/
spectral.rs

1//! Spectral energy-slope constant `mu` (PSP-8 System 2 / Gate G).
2//!
3//! For the quadratic residual energy `V(x) = x^T A x` with `A = B^T W B`, the
4//! energy-slope constant `mu = 2 * lambda_min+(A)` is combinatorial rather than
5//! embedding-dependent. In the identity-restriction case `A` reduces to the
6//! weighted Laplacian of the verification graph and `mu` is twice its algebraic
7//! connectivity (Fiedler value).
8//!
9//! `mu` is a diagnostic, not an input to the acceptance gate. It SHALL be
10//! computed off the critical path and SHALL NOT block dispatch or the gate.
11//! This module is therefore a pure, side-effect-free computation a runtime can
12//! schedule on graph-revision commit or asynchronously.
13
14use nalgebra::DMatrix;
15use serde::{Deserialize, Serialize};
16
17use crate::error::{check_positive_finite, Result, SdkError};
18
19/// One weighted edge of the verification graph. An edge `(i, j)` couples the
20/// local states of two nodes/verifiers; its weight is the residual weight
21/// `w_e > 0`.
22#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
23pub struct VerificationEdge {
24    pub src: usize,
25    pub dst: usize,
26    pub weight: f64,
27}
28
29impl VerificationEdge {
30    pub fn new(src: usize, dst: usize, weight: f64) -> Self {
31        Self { src, dst, weight }
32    }
33}
34
35/// A verification graph over `node_count` local-state components.
36#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
37pub struct VerificationGraph {
38    pub node_count: usize,
39    pub edges: Vec<VerificationEdge>,
40}
41
42impl VerificationGraph {
43    pub fn new(node_count: usize) -> Self {
44        Self {
45            node_count,
46            edges: Vec::new(),
47        }
48    }
49
50    pub fn with_edge(mut self, src: usize, dst: usize, weight: f64) -> Self {
51        self.edges.push(VerificationEdge::new(src, dst, weight));
52        self
53    }
54
55    pub fn add_edge(&mut self, src: usize, dst: usize, weight: f64) {
56        self.edges.push(VerificationEdge::new(src, dst, weight));
57    }
58
59    /// Build the weighted graph Laplacian `A = B^T W B` (identity-restriction
60    /// case), an `n x n` symmetric positive-semidefinite matrix.
61    fn laplacian(&self) -> Result<DMatrix<f64>> {
62        if self.node_count == 0 {
63            return Err(SdkError::Spectral("verification graph has no nodes".into()));
64        }
65        let n = self.node_count;
66        let mut a = DMatrix::<f64>::zeros(n, n);
67        for e in &self.edges {
68            if e.src >= n || e.dst >= n {
69                return Err(SdkError::Spectral(format!(
70                    "edge ({}, {}) out of range for {} nodes",
71                    e.src, e.dst, n
72                )));
73            }
74            if e.src == e.dst {
75                return Err(SdkError::Spectral(format!("self-loop at node {}", e.src)));
76            }
77            check_positive_finite(e.weight, "edge weight")?;
78            let w = e.weight;
79            a[(e.src, e.src)] += w;
80            a[(e.dst, e.dst)] += w;
81            a[(e.src, e.dst)] -= w;
82            a[(e.dst, e.src)] -= w;
83        }
84        Ok(a)
85    }
86
87    /// Sorted ascending eigenvalues of the Laplacian.
88    fn eigenvalues_sorted(&self) -> Result<Vec<f64>> {
89        let a = self.laplacian()?;
90        // The Laplacian is symmetric; use the symmetric eigensolver.
91        let mut eigs: Vec<f64> = a.symmetric_eigenvalues().iter().copied().collect();
92        eigs.sort_by(|x, y| x.partial_cmp(y).unwrap_or(std::cmp::Ordering::Equal));
93        Ok(eigs)
94    }
95
96    /// Smallest non-zero eigenvalue `lambda_min+(A)` of the Laplacian.
97    ///
98    /// Returns `None` when the graph is disconnected or empty of edges (the
99    /// spectral gap is then zero, so `mu` is not informative). Eigenvalues
100    /// within `tol` of zero are treated as zero.
101    pub fn smallest_nonzero_eigenvalue(&self, tol: f64) -> Result<Option<f64>> {
102        let eigs = self.eigenvalues_sorted()?;
103        Ok(eigs.into_iter().find(|&v| v > tol))
104    }
105
106    /// The spectral energy-slope constant `mu = 2 * lambda_min+(A)`.
107    ///
108    /// Returns `None` for a disconnected verification graph, where the gap is
109    /// zero and `mu` is uninformative (a disconnected verifier component cannot
110    /// be driven to consensus by the others).
111    pub fn mu(&self, tol: f64) -> Result<Option<f64>> {
112        Ok(self
113            .smallest_nonzero_eigenvalue(tol)?
114            .map(|lambda| 2.0 * lambda))
115    }
116
117    /// Algebraic connectivity (Fiedler value) — the smallest non-zero
118    /// eigenvalue; `mu = 2 * fiedler`.
119    pub fn fiedler_value(&self, tol: f64) -> Result<Option<f64>> {
120        self.smallest_nonzero_eigenvalue(tol)
121    }
122
123    /// Change in `mu` produced by adding a candidate verifier edge.
124    ///
125    /// An independent verifier that raises the spectral gap yields a positive
126    /// delta; a redundant verifier that does not yields ~0. Used to distinguish
127    /// independent from redundant verifiers (PSP-8 System 2).
128    pub fn edge_mu_sensitivity(
129        &self,
130        src: usize,
131        dst: usize,
132        weight: f64,
133        tol: f64,
134    ) -> Result<f64> {
135        Ok(self.edge_sensitivity(src, dst, weight, tol)?.gap_delta)
136    }
137
138    /// Both of Lemma 2's levers for a candidate verifier edge (PSP-9
139    /// system 17): a new check helps insofar as it **raises**
140    /// `λ⁺_min(A)` *or shrinks* `ker(A)` — the safe set is exactly
141    /// `ker(A)`. For a coding workspace the second lever is the common
142    /// case: a verifier for a property nothing previously constrained
143    /// removes an unverified direction from the nominal safe set without
144    /// moving the gap at all. A verifier that changes neither is redundancy
145    /// in the exact sense Corollary 5.2 prices probabilistically.
146    pub fn edge_sensitivity(
147        &self,
148        src: usize,
149        dst: usize,
150        weight: f64,
151        tol: f64,
152    ) -> Result<EdgeSensitivity> {
153        let gap_before = self.mu(tol)?.unwrap_or(0.0);
154        let nullity_before = self.nullity(tol)?;
155        let mut candidate = self.clone();
156        candidate.add_edge(src, dst, weight);
157        let gap_after = candidate.mu(tol)?.unwrap_or(0.0);
158        let nullity_after = candidate.nullity(tol)?;
159        Ok(EdgeSensitivity {
160            gap_delta: gap_after - gap_before,
161            nullity_before,
162            nullity_after,
163        })
164    }
165
166    /// Dimension of `ker(L)` — the unverified directions of the nominal
167    /// safe set. Eigenvalues within `tol` of zero count as zero.
168    pub fn nullity(&self, tol: f64) -> Result<usize> {
169        Ok(self
170            .eigenvalues_sorted()?
171            .into_iter()
172            .filter(|e| e.abs() <= tol)
173            .count())
174    }
175}
176
177/// Both deltas for one candidate edge (Paper II Lemma 2).
178#[derive(Debug, Clone, Copy, PartialEq)]
179pub struct EdgeSensitivity {
180    /// Change in the spectral gap `λ⁺_min`.
181    pub gap_delta: f64,
182    /// `dim ker(A)` before and after: a shrink is Lemma 2's second lever.
183    pub nullity_before: usize,
184    pub nullity_after: usize,
185}
186
187impl EdgeSensitivity {
188    /// Whether the candidate verifier earns its cost by either lever.
189    pub fn earns_cost(&self, tol: f64) -> bool {
190        self.gap_delta > tol || self.nullity_after < self.nullity_before
191    }
192}
193
194#[cfg(test)]
195mod tests {
196    use super::*;
197
198    const TOL: f64 = 1e-9;
199
200    #[test]
201    fn path_graph_has_expected_fiedler_value() {
202        // Unweighted path on 3 nodes: Laplacian eigenvalues are 0, 1, 3.
203        let g = VerificationGraph::new(3)
204            .with_edge(0, 1, 1.0)
205            .with_edge(1, 2, 1.0);
206        let fiedler = g.fiedler_value(TOL).unwrap().unwrap();
207        assert!((fiedler - 1.0).abs() < 1e-6, "fiedler={fiedler}");
208        let mu = g.mu(TOL).unwrap().unwrap();
209        assert!((mu - 2.0).abs() < 1e-6, "mu={mu}");
210    }
211
212    #[test]
213    fn complete_triangle_connectivity() {
214        // Unweighted triangle: eigenvalues 0, 3, 3 -> fiedler = 3.
215        let g = VerificationGraph::new(3)
216            .with_edge(0, 1, 1.0)
217            .with_edge(1, 2, 1.0)
218            .with_edge(0, 2, 1.0);
219        let fiedler = g.fiedler_value(TOL).unwrap().unwrap();
220        assert!((fiedler - 3.0).abs() < 1e-6, "fiedler={fiedler}");
221    }
222
223    #[test]
224    fn disconnected_graph_has_no_spectral_gap() {
225        // Two isolated edges over 4 nodes -> two zero eigenvalues, but the
226        // second smallest is still 0 -> disconnected.
227        let g = VerificationGraph::new(4)
228            .with_edge(0, 1, 1.0)
229            .with_edge(2, 3, 1.0);
230        // smallest nonzero exists (the within-component value) but the graph is
231        // disconnected: there are two zero eigenvalues. We detect disconnection
232        // by counting zeros.
233        let eigs = g.eigenvalues_sorted().unwrap();
234        let zeros = eigs.iter().filter(|&&v| v.abs() <= TOL).count();
235        assert_eq!(
236            zeros, 2,
237            "disconnected graph has multiplicity-2 zero eigenvalue"
238        );
239    }
240
241    #[test]
242    fn independent_verifier_raises_mu_more_than_redundant() {
243        // Base: path 0-1-2.
244        let g = VerificationGraph::new(3)
245            .with_edge(0, 1, 1.0)
246            .with_edge(1, 2, 1.0);
247        // Adding the closing edge 0-2 (independent cross-check) raises the gap.
248        let independent = g.edge_mu_sensitivity(0, 2, 1.0, TOL).unwrap();
249        // Strengthening an existing coupling 0-1 (redundant) raises it less.
250        let redundant = g.edge_mu_sensitivity(0, 1, 1.0, TOL).unwrap();
251        assert!(independent > 0.0);
252        assert!(
253            independent >= redundant,
254            "independent={independent} redundant={redundant}"
255        );
256    }
257
258    #[test]
259    fn weighted_edges_scale_gap() {
260        let g1 = VerificationGraph::new(2).with_edge(0, 1, 1.0);
261        let g2 = VerificationGraph::new(2).with_edge(0, 1, 2.0);
262        let m1 = g1.mu(TOL).unwrap().unwrap();
263        let m2 = g2.mu(TOL).unwrap().unwrap();
264        assert!((m2 - 2.0 * m1).abs() < 1e-6);
265    }
266
267    #[test]
268    fn rejects_self_loop_and_out_of_range() {
269        assert!(VerificationGraph::new(2)
270            .with_edge(0, 0, 1.0)
271            .mu(TOL)
272            .is_err());
273        assert!(VerificationGraph::new(2)
274            .with_edge(0, 5, 1.0)
275            .mu(TOL)
276            .is_err());
277    }
278
279    #[test]
280    fn a_connecting_verifier_shrinks_the_nullspace_even_without_moving_mu() {
281        // Two disconnected components: nullity 2. Connecting them removes an
282        // unverified direction — Lemma 2's second lever.
283        let g = VerificationGraph::new(4)
284            .with_edge(0, 1, 1.0)
285            .with_edge(2, 3, 1.0);
286        assert_eq!(g.nullity(TOL).unwrap(), 2);
287        let sensitivity = g.edge_sensitivity(1, 2, 1.0, TOL).unwrap();
288        assert_eq!(sensitivity.nullity_before, 2);
289        assert_eq!(sensitivity.nullity_after, 1);
290        assert!(sensitivity.earns_cost(TOL));
291    }
292
293    #[test]
294    fn a_redundant_verifier_changes_neither_lever() {
295        // Doubling an existing edge with negligible weight: no rank change,
296        // negligible gap change — redundancy in the Corollary 5.2 sense.
297        let g = VerificationGraph::new(2).with_edge(0, 1, 1.0);
298        let sensitivity = g.edge_sensitivity(0, 1, 1e-12, TOL).unwrap();
299        assert_eq!(sensitivity.nullity_before, sensitivity.nullity_after);
300        assert!(!sensitivity.earns_cost(1e-6));
301    }
302}
perspt_sdk/spectral.rs

perspt_sdk/
spectral.rs
