Talks and Poster Presentations (with Proceedings-Entry):
C. Chen, M. Kerber:
"An output-sensitive algorithm for persistent homology";
Talk: 27th Annual Symposium on Computational Geometry (SoCG 2011),
Paris, Frankreich;
2011-06-13
- 2011-06-15; in: "27th Annual Symposium on Computational Geometry (SoCG 2011)",
(2011),
1
- 9.
English 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×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.
Created from the Publication Database of the Vienna University of Technology.