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.

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.