An output sensitive algorithm for persistent homology Conference Paper


Author(s): Chen, Chao; Kerber, Michael
Title: An output sensitive algorithm for persistent homology
Affiliation IST Austria
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.
Conference Title: SoCG: Symposium on Computational Geometry
Conference Dates: June 13-15, 2011
Conference Location: Paris, France
ISBN: 978-1-4503-2594-3
Publisher: ACM  
Date Published: 2011-06-13
Start Page: 207
End Page: 216
DOI: 10.1145/1998196.1998228
Open access: no
IST Austria Authors
  1. Michael Kerber
    21 Kerber
  2. Chao Chen
    14 Chen
Related IST Austria Work