An output-sensitive algorithm for persistent homology

In this paper, we present the first output-sensitive algorithmto compute the persistence diagram of a filtered simplicialcomplex. For any 􀀀 > 0, it returns only those homologyclasses with persistence at least 􀀀. Instead of the classicalreduction via column operations, our algorithm performsrank computations on submatrices of the boundary matrix.For an arbitrary constant δ ∈ (0, 1), the running time isO(C(1−δ)􀀀R(n) log n), where C(1−δ)􀀀 is the number of homologyclasses with persistence at least (1−δ)􀀀, n is the totalnumber of simplices, and R(n) is the complexity of computingthe rank of an n×n matrix with O(n) nonzero entries.Depending on the choice of the rank algorithm, this yields adeterministic O(C(1−δ)􀀀n2.376) algorithm, a O(C(1−δ)􀀀n2.28)Las-Vegas algorithm, or a O(C(1−δ)􀀀n2+ǫ) Monte-Carlo algorithmfor an arbitrary ǫ > 0.