TY - GEN
T1 - An output-sensitive algorithm for persistent homology
AU - Chen, Chao
AU - Kerber, Michael
PY - 2011
Y1 - 2011
N2 - In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ > 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), the running time is O(C (1-δ)ΓR(n) log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n×n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C (1-δ)Γn2.376) algorithm, a O(C (1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+∈) Monte-Carlo algorithm for an arbitrary ∈ > 0.
AB - In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ > 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), the running time is O(C (1-δ)ΓR(n) log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n×n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C (1-δ)Γn2.376) algorithm, a O(C (1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+∈) Monte-Carlo algorithm for an arbitrary ∈ > 0.
KW - Computational topology
KW - Persistent homology
KW - Randomized algorithms
KW - Rank computation
UR - https://www.scopus.com/pages/publications/79960165024
U2 - 10.1145/1998196.1998228
DO - 10.1145/1998196.1998228
M3 - Conference contribution
AN - SCOPUS:79960165024
SN - 9781450306829
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 207
EP - 215
BT - Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11
T2 - 27th Annual ACM Symposium on Computational Geometry, SCG'11
Y2 - 13 June 2011 through 15 June 2011
ER -