[Back]


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 nn 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.