Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

The Twist Algorithm and Clearing Optimisation

2 minute read

Published:

TL;DR: Standard boundary matrix reduction reduces each column left-to-right, taking O(n³) worst case. The twist algorithm (Chen & Kerber 2011) processes columns in two passes — forwards for high dimensions and backwards for low — to exploit that positive simplices never need full reduction. The clearing optimisation (Cohen-Steiner et al.) zeros columns for "positive" simplices immediately, halving work in practice.

Standard Reduction Recap

The persistence algorithm reduces the boundary matrix \(R = \partial\) (columns indexed by simplices, entries in \(\mathbb{F}_2\)):

for j = 1 to n:
    while there exists i < j with low(R[j]) == low(R[i]):
        R[j] += R[i]  (add column i to column j)

where \(\mathrm{low}(v)\) is the index of the lowest 1-entry in column \(v\). After reduction, the non-zero columns give the pairing: \(\mathrm{pivot}(R_j) = i\) means \((\sigma_i, \sigma_j)\) is a persistence pair.

Complexity: \(O(n^3)\) field operations in the worst case (\(n\) columns, each reduced \(O(n)\) times, each reduction takes \(O(n)\) time).

The Clearing Optimisation

Observation: If \((\sigma_i, \sigma_j)\) is a persistence pair, then the column for \(\sigma_i\) (a positive simplex) reduces to zero. We can detect this during the reduction of \(\sigma_j\)’s column: once we find a pivot at row \(i\) that corresponds to a known pair, we know \(\sigma_i\)’s column will reduce to zero.

Clearing: After processing \(\sigma_j\) and finding its pivot at \(i\), set \(R[i] = 0\) immediately. This avoids reducing \(R[i]\) entirely.

In practice, clearing eliminates about half of all column reductions on typical inputs, giving a roughly \(2\times\) speedup with no asymptotic change.

The Twist Algorithm

The twist algorithm (Chen & Kerber 2011) exploits Poincaré duality on closed manifolds: if \((\sigma_i, \sigma_j)\) is a pair in dimension \(n\), there is a corresponding dual pair in dimension \(d-n-1\).

The algorithm processes dimensions from high to low. After reducing all \(n\)-dimensional columns, it uses the discovered pairings to immediately clear the corresponding \((n-1)\)-dimensional columns. This significantly reduces the number of actual column reductions required.

Effect: On Vietoris-Rips complexes of manifold data, the twist algorithm combined with clearing reduces the practical complexity from \(O(n^3)\) to nearly linear in the size of the output (number of persistence pairs).

Key Insight: Ripser (Bauer 2021) implements both clearing and the cohomology algorithm (which runs in the opposite reduction direction and benefits even more from clearing). On typical benchmarks, Ripser is 10–1000× faster than earlier implementations. The key insight is that most columns are either cleared before reduction (positive simplices) or reduce quickly in cohomology (because the generators appear naturally in reverse order).

References

  • C. Chen & M. Kerber, “Persistent Homology Computation with a Twist,” EuroCG, 2011.
  • U. Bauer, “Ripser: Efficient Computation of Vietoris-Rips Persistence Barcodes,” J. Applied and Computational Topology, 2021. arXiv:1908.02518.

You May Also Enjoy

GAPE: Remember to Forget — Gated Adaptive Positional Encoding

4 minute read

Published:

GAPE is a drop-in RoPE augmentation that adds content-aware attention logit biases: a query-gate suppresses irrelevant distant context while a key-gate preserves salient distant tokens. Provably sharper attention and improved long-context robustness — no architecture changes needed.

PolyNSD: Polynomial Neural Sheaf Diffusion

4 minute read

Published:

PolyNSD replaces the NSD propagation operator with a degree-K Chebyshev polynomial in the normalised sheaf Laplacian, achieving SOTA on homo- and heterophilic benchmarks with only diagonal restriction maps and dramatically lower memory usage.

TDA in Materials Science: Topology of Structure and Phase

3 minute read

Published:

Persistent homology characterises the multi-scale structure of materials — from pore geometry in catalysts to glass transition in amorphous materials. H₀ captures connectivity, H₁ captures channels and rings, H₂ captures enclosed voids. These topological descriptors predict mechanical properties, adsorption capacity, and phase transitions more accurately than geometric averages.

TDA in Drug Discovery: Molecular Topology

3 minute read

Published:

Persistent homology provides multi-scale topological fingerprints of molecular structures — capturing rings, cavities, and protein pockets that traditional cheminformatics descriptors miss. Applications include binding site detection, ADMET property prediction, and protein-ligand interaction modelling.