The computation of Vietoris-Rips persistence barcodes is both
execution-intensive and memory-intensive. In this paper, we study the
computational structure of Vietoris-Rips persistence barcodes, and identify
several unique mathematical properties and algorithmic opportunities with
connections to the GPU. Mathematically and empirically, we look into the
properties of apparent pairs, which are independently identifiable persistence
pairs comprising up to 99% of persistence pairs. We give theoretical upper and
lower bounds of the apparent pair rate and model the average case. We also
design massively parallel algorithms to take advantage of the very large number
of simplices that can be processed independently of each other. Having
identified these opportunities, we develop a GPU-accelerated software for
computing Vietoris-Rips persistence barcodes, called Ripser++. The software
achieves up to 30x speedup over the total execution time of the original Ripser
and also reduces CPU-memory usage by up to 2.0x. We believe our
GPU-acceleration based efforts open a new chapter for the advancement of
topological data analysis in the post-Moore's Law era.

本文提出了一种基于 GPU 并行计算的软件 Ripser++，它能够对 Vietoris-Rips persistence barcodes 进行计算，相较于原版 Ripser 在执行时间和 CPU - 内存使用方面分别提高了 30 倍和 2 倍，使拓扑数据分析在后摩尔定律时代得到了新的发展。

GPU 加速的 Vietoris-Rips 坚持条形码计算

GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes

We present massively parallel (MPC) algorithms and hardness of approximation
results for computing Single-Linkage Clustering of $n$ input $d$-dimensional
vectors under Hamming, $\ell_1, \ell_2$ and $\ell_\infty$ distances. All our
algorithms run in $O(\log n)$ rounds of MPC for any fixed $d$ and achieve
$(1+\epsilon)$-approximation for all distances (except Hamming for which we
show an exact algorithm). We also show constant-factor inapproximability
results for $o(\log n)$-round algorithms under standard MPC hardness
assumptions (for sufficiently large dimension depending on the distance used).
Efficiency of implementation of our algorithms in Apache Spark is demonstrated
through experiments on a variety of datasets exhibiting speedups of several
orders of magnitude.

介绍了用 Apache Spark 实现的高效的大规模并行算法来计算单链接聚类问题，该算法在 Hamming 距离，L1，L2 和 L∞ 距离下均能实现单轮 MPC，和（除了 Hamming 距离的精确算法外）都能实现（1+ε）- 近似，同时证明了在标准 MPC 难度假设下，o（log n）轮算法的常数近似难度结果。