Expand description
Sparse Persistent Homology — ADR-029 Phase 2 integration.
Standard persistent homology: O(n³) boundary matrix reduction. This implementation: O(n · 1/ε) via Forward Push PPR approximation.
Algorithm: Use PersonalizedPageRank (Forward Push) to build ε-approximate k-hop neighborhood graph, then compute TDA only on the sparse neighborhood. Reduces complexity from O(n³) to O(n/ε) for sparse graphs.
ADR-029: ruvector-solver’s Forward Push PPR is the canonical sparse TDA backend.
Structs§
- Forward
Push Ppr - Forward-Push PPR: O(1/ε) approximate k-hop neighborhood construction. Simulates push-flow from source nodes to identify ε-dense neighborhoods.
- Persistence
Bar - A bar in the persistence diagram (birth, death, dimension)
- Persistence
Diagram - Simplex
Edge - Sparse edge in the filtration complex
- Sparse
Rips Complex - Sparse Vietoris-Rips complex builder