An output-sensitive algorithm for persistent homology

作者：Chen Chao; Kerber Michael^*

来源：Computational Geometry-Theory and Applications, 2013, 46(4): 435-447.

DOI：10.1016/j.comgeo.2012.02.010

• Computational topology
• Persistent homology
• Randomized algorithms
• Rank computation

In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Gamma > 0, it returns only those homology classes with persistence at least Gamma. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant delta is an element of (0, 1), the running time is O (C(1-delta)Gamma Rd(n) log n), where C(1-delta)Gamma is the number of homology classes with persistence at least (1 - delta)Gamma, n is the total number of simplices in the complex, d its dimension, and R-d(n) is the complexity of computing the rank of an n x n matrix with O (dn) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C(1-delta))(Gamma)n(2.376)) algorithm, an O (C((1-delta)Gamma)n(2.28)) Las-Vegas algorithm, or an O (C((1-delta)Gamma)n(2+epsilon)) Monte-Carlo algorithm for an arbitrary epsilon > 0. The space complexity of the Monte-Carlo version is bounded by O (dn) = O (n log n).

• 出版日期2013-5