An output sensitive algorithm for persistent homology

C. Chen, M. Kerber, in:, ACM, 2011, pp. 207–216.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Department
Abstract
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 x 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.
Publishing Year
Date Published
2011-06-13
Page
207 - 216
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Paris, France
Conference Date
2011-06-13 – 2011-06-15
IST-REx-ID

Cite this

Chen C, Kerber M. An output sensitive algorithm for persistent homology. In: ACM; 2011:207-216. doi:10.1145/1998196.1998228
Chen, C., & Kerber, M. (2011). An output sensitive algorithm for persistent homology (pp. 207–216). Presented at the SoCG: Symposium on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998228
Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology,” 207–16. ACM, 2011. https://doi.org/10.1145/1998196.1998228.
C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,” presented at the SoCG: Symposium on Computational Geometry, Paris, France, 2011, pp. 207–216.
Chen C, Kerber M. 2011. An output sensitive algorithm for persistent homology. SoCG: Symposium on Computational Geometry 207–216.
Chen, Chao, and Michael Kerber. An Output Sensitive Algorithm for Persistent Homology. ACM, 2011, pp. 207–16, doi:10.1145/1998196.1998228.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar