Abstract
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.
Reference
Chen, C., & Kerber, M. (2011). An output-sensitive algorithm for persistent homology. In 27th Annual Symposium on Computational Geometry (SoCG 2011) (pp. 1–9). http://hdl.handle.net/20.500.12708/53719