کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
415612 | 681217 | 2013 | 13 صفحه PDF | دانلود رایگان |

In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0Γ>0, it returns only those homology classes with persistence at least Γ . Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ∈(0,1)δ∈(0,1), the running time is O(C(1−δ)ΓRd(n)logn), where C(1−δ)ΓC(1−δ)Γ is the number of homology classes with persistence at least (1−δ)Γ(1−δ)Γ, n is the total number of simplices in the complex, d its dimension, and Rd(n)Rd(n) is the complexity of computing the rank of an n×nn×n matrix with O(dn)O(dn) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1−δ)Γn2.376)O(C(1−δ)Γn2.376) algorithm, an O(C(1−δ)Γn2.28)O(C(1−δ)Γn2.28) Las-Vegas algorithm, or an O(C(1−δ)Γn2+ϵ)O(C(1−δ)Γn2+ϵ) Monte-Carlo algorithm for an arbitrary ϵ>0ϵ>0. The space complexity of the Monte-Carlo version is bounded by O(dn)=O(nlogn).
Journal: Computational Geometry - Volume 46, Issue 4, May 2013, Pages 435–447