Skip to content

Release v0.3.0: Fix H2 Spurious Features and Infinite Loops

Choose a tag to compare

View all tags
@Routhleck Routhleck released this 22 Aug 06:56
· 69 commits to master since this release
v0.3.0
566db51

🎉 Major Release: Complete Algorithm Correctness

This release achieves complete algorithmic correctness for persistent homology computation, with exact matching to the original C++ Ripser implementation.

🔧 Critical Algorithm Fixes

Core Issues Resolved:

  • ✅ Fixed H2 spurious features - No more false positive H2 homology features
  • ✅ Eliminated infinite loops - All computations complete in reasonable time
  • ✅ Corrected heap ordering - DiameterEntryT now matches C++ behavior exactly
  • ✅ Fixed pivot indexing - Using IndexT instead of EntryT for proper column tracking
  • ✅ Improved factor calculation - Uses stored coefficients for accurate matrix reduction
  • ✅ Enhanced H0 processing - Better edge ordering for connectivity analysis

🧪 Comprehensive Validation

Regression Tests: 6/6 passing with exact match to original ripser

  • Triangle topology ✅
  • Square topology ✅
  • Circle homology ✅
  • Tetrahedron H2 ✅
  • Different coefficients ✅
  • Threshold behavior ✅

Complex Topology Tests: All passing

  • Torus: H0=80, H1=22, H2=4 (exact match with original)
  • Sphere: H0=60, H1=14, H2=1 (exact match with original)
  • Double Circles: H0=50, H1=2, H2=0 (exact match with original)
  • Linked Circles: H0=40, H1=3, H2=0 (exact match with original)
  • Cube Boundary: H0=57, H1=53, H2=1
  • Performance: <0.01s on 40-point datasets
  • Noise Robustness: Stable across multiple noise levels

📊 Performance & Stability

  • Zero infinite loops - All test cases complete instantly
  • Memory efficient - Optimized data structures
  • Robust error handling - Graceful handling of edge cases
  • Production ready - Comprehensive test coverage (34 tests passing)

🛠️ Code Quality Improvements

  • Fixed all clippy warnings and formatting issues
  • Removed debug files and temporary tests
  • Improved code documentation and organization
  • Clean codebase ready for production use

🔬 Technical Details

Key algorithmic changes:

  • Heap priority queue now uses proper min-heap semantics
  • Pivot column indexing stores both position and coefficient
  • Matrix reduction uses correct factor calculation from stored coefficients
  • Union-Find processes edges in ascending diameter order

Compatibility:

  • Drop-in replacement for original ripser.py
  • Same API and output format
  • Supports all major homology dimensions (H0, H1, H2+)
  • Compatible with Python 3.11+

🚀 What's New

This release represents a complete rewrite of the core algorithm based on detailed analysis of the original C++ implementation. Previous versions had fundamental issues with infinite loops and spurious H2 features that are now completely resolved.

Use Cases:

  • Topological data analysis with complex 3D structures
  • Persistent homology of point clouds
  • Torus, sphere, and other non-trivial topologies
  • High-performance computation on large datasets

📦 Installation

pip install canns-ripser==0.3.0

🔍 Migration from v0.2.0

No API changes required - this is a drop-in replacement with identical interface but correct algorithmic behavior.

Full Changelog: v0.2.0...v0.3.0

Assets 2
Loading