论文标题
离散的莫尔斯三明治：标量数据的持久图快速计算 - 算法和基准测试
Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark
论文作者
论文摘要
本文介绍了一种用于持久图计算的有效算法，给定一个输入分段线性标量字段$ f $ f $定义在$ d $ d $二维的简单复杂$ k $，带有$ d \ d \ leq 3 $。我们的工作与离散的莫尔斯理论（DMT）[34]，[80]重新审阅了开创性算法“ Pairsimplices” [31]，[103]，这大大减少了要考虑的输入简单的数量。此外，我们还扩展到DMT并加速“ Pairsimplices”中描述的分层策略，以快速计算$ 0^{th} $和$（d -1）^{th} $图，指出$ d_0（f）$和$ d_ {d_ {d_ {d -1}（f）$。 minima-saddle持久对（$ d_0（f）$）和鞍 - 最大持久对（$ d_ {d_ {d-1}（f）$）是通过处理有效地计算的，并使用Union-find（Union-find），不稳定的$ 1 $ -SADDDLES和稳定的集合（D-1）$（D-1）$（D-1）$ - saddles $ - saddles。尺寸$ 0 $和$（d -1）$的快速预发行使[4]对3D案例进行了积极的专业化，从而导致计算$ d_1（f）$的输入简单数量的大幅减少，这是三明治的中层层。最后，我们通过共享记忆并行性记录了几项绩效改进。我们为可重复性目的提供了算法的开源实现。我们还贡献了可重现的基准软件包，该基准软件包利用了公共存储库中的三维数据，并将我们的算法与各种公开可用的实现进行了比较。广泛的实验表明，我们的算法提高了两个数量级，即它扩展的开创性“ PiairSimplices”算法的时间性能。此外，它还改善了14种竞争方法的选择，改善了记忆足迹和时间性能，比最快的可用方法具有可观的增长，同时产生了严格的输出。
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 \leq 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 $0^{th}$ and $(d - 1)^{th}$ diagrams, noted $D_0(f)$ and $D_{d-1}(f)$. Minima-saddle persistence pairs ($D_0(f)$) and saddle-maximum persistence pairs ($D_{d-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 $D_1(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.
