---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Chao
foaf_name: Chen, Chao
foaf_surname: Chen
foaf_workInfoHomepage: http://www.librecat.org/personId=3E92416E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Michael
foaf_name: Kerber, Michael
foaf_surname: Kerber
foaf_workInfoHomepage: http://www.librecat.org/personId=36E4574A-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8030-9299
bibo_doi: 10.1145/1998196.1998228
dct_date: 2011^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: An output sensitive algorithm for persistent homology@
...