An output-sensitive algorithm for persistent homology

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).