[Zurück]

C. Chen, M. Kerber:
"An output-sensitive algorithm for persistent homology";
Vortrag: 27th Annual Symposium on Computational Geometry (SoCG 2011), Paris, Frankreich; 13.06.2011 - 15.06.2011; in: "27th Annual Symposium on Computational Geometry (SoCG 2011)", (2011), S. 1 - 9.

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.