# Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark

arXiv: https://arxiv.org/abs/2206.13932 · HTML: https://mlsanity.com/paper/2206.13932/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 109 references that are in the map.
- First posted on arXiv 27 Jun 2022.

## Builds on (most cited first, 21 of 21)

- [Ripser: efficient computation of Vietoris-Rips persistence barcodes](https://mlsanity.com/paper/1908.02518/) (2019)
- [giotto-tda: A Topological Data Analysis Toolkit for Machine Learning and Data Exploration](https://mlsanity.com/paper/2004.02551/) (2020)
- [The Topology ToolKit](https://mlsanity.com/paper/1805.09110/) (2018)
- [Cubical Ripser: Software for computing persistent homology of image and volume data](https://mlsanity.com/paper/2005.12692/) (2020)
- [Task-based Augmented Contour Trees with Fibonacci Heaps](https://mlsanity.com/paper/1902.04805/) (2019)
- [Progressive Wasserstein Barycenters of Persistence Diagrams](https://mlsanity.com/paper/1907.04565/) (2019)
- [The Simplex Tree: an Efficient Data Structure for General Simplicial Complexes](https://mlsanity.com/paper/2001.02581/) (2020)
- [Ranking Viscous Finger Simulations to an Acquired Ground Truth with Topology-aware Matchings](https://mlsanity.com/paper/1908.07841/) (2019)
- [TopoMap: A 0-dimensional Homology Preserving Projection of High-Dimensional Data](https://mlsanity.com/paper/2009.01512/) (2020)
- [Distributed computation of persistent homology](https://mlsanity.com/paper/1310.0710/) (2013)
- [Persistence Atlas for Critical Point Variability in Ensembles](https://mlsanity.com/paper/1807.11212/) (2018)
- [Lifted Wasserstein Matcher for Fast and Robust Topology Tracking](https://mlsanity.com/paper/1808.05870/) (2018)
- [Localized Topological Simplification of Scalar Data](https://mlsanity.com/paper/2009.00083/) (2020)
- [Duality in Persistent Homology of Images](https://mlsanity.com/paper/2005.04597/) (2020)
- [Persistent 1-Cycles: Definition, Computation, and Its Application](https://mlsanity.com/paper/1810.04807/) (2018)
- [Topologically Controlled Lossy Compression](https://mlsanity.com/paper/1802.02731/) (2018)
- [Persistent Homology Guided Force-Directed Graph Layouts](https://mlsanity.com/paper/1712.05548/) (2017)
- [The Compressed Annotation Matrix: an Efficient Data Structure for Computing Persistent Cohomology](https://mlsanity.com/paper/1304.6813/) (2013)
- [Statistical Parameter Selection for Clustering Persistence Diagrams](https://mlsanity.com/paper/1910.08398/) (2019)
- [A Progressive Approach to Scalar Field Topology](https://mlsanity.com/paper/2007.14766/) (2020)
- [Fast Approximation of Persistence Diagrams with Guarantees](https://mlsanity.com/paper/2108.05766/) (2021)

## Built on by (most cited first, 11 of 11)

- [On the Limitations of Fractal Dimension as a Measure of Generalization](https://mlsanity.com/paper/2406.02234/) (2024)
- [Wasserstein Dictionaries of Persistence Diagrams](https://mlsanity.com/paper/2304.14852/) (2023)
- [Topological Autoencoders++: Fast and Accurate Cycle-Aware Dimensionality Reduction](https://mlsanity.com/paper/2502.20215/) (2025)
- [Wasserstein Auto-Encoders of Merge Trees (and Persistence Diagrams)](https://mlsanity.com/paper/2307.02509/) (2023)
- [TTK is Getting MPI-Ready](https://mlsanity.com/paper/2310.08339/) (2023)
- [A Practical Solver for Scalar Data Topological Simplification](https://mlsanity.com/paper/2407.12399/) (2024)
- [BondMatcher: H-Bond Stability Analysis in Molecular Systems](https://mlsanity.com/paper/2504.03205/) (2025)
- [Topology Aware Neural Interpolation of Scalar Fields](https://mlsanity.com/paper/2508.17995/) (2025)
- [Continuous Edit Distance, Geodesics and Barycenters of Time-varying Persistence Diagrams](https://mlsanity.com/paper/2512.12939/) (2025)
- [DebrisTracer: Reliable Tracking in Hypervelocity Impact Fast Imaging](https://mlsanity.com/paper/2607.15986/) (2026)
- [Sierpi'nski--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation](https://mlsanity.com/paper/2609.01528/) (2026)

## Abstract (arXiv)

This paper introduces an efficient algorithm for persistence diagram computation, given an input piecewise linear scalar field f defined on a d-dimensional simplicial complex K, with d ≤ 3. Our work revisits the seminal algorithm "PairSimplices" [31], [103] with discrete Morse theory (DMT) [34], [80], which greatly reduces the number of input simplices to consider. Further, we also extend to DMT and accelerate the stratification strategy described in "PairSimplices" for the fast computation of the 0th and (d - 1)th diagrams, noted D0(f) and Dd-1(f). Minima-saddle persistence pairs (D0(f)) and saddle-maximum persistence pairs (Dd-1(f)) are efficiently computed by processing, with a Union-Find, the unstable sets of 1-saddles and the stable sets of (d - 1)-saddles. This fast pre-computation for the dimensions 0 and (d - 1) enables an aggressive specialization of [4] to the 3D case, which results in a drastic reduction of the number of input simplices for the computation of D1(f), the intermediate layer of the sandwich. Finally, we document several performance improvements via shared-memory parallelism. We provide an open-source implementation of our algorithm for reproducibility purposes. We also contribute a reproducible benchmark package, which exploits three-dimensional data from a public repository and compares our algorithm to a variety of publicly available implementations. Extensive experiments indicate that our algorithm improves by two orders of magnitude the time performance of the seminal "PairSimplices" algorithm it extends. Moreover, it also improves memory footprint and time performance over a selection of 14 competing approaches, with a substantial gain over the fastest available approaches, while producing a strictly identical output.