zbMATH — the first resource for mathematics

An output-sensitive algorithm for persistent homology. (English) Zbl 1264.65023
The authors study the computation of persistent homology of a simplicial complex over \(\mathbb Z_2\). In this direction, the first algorithm by H. Edelsbrunner et al. [Discrete Comput. Geom. 28, No. 4, 511–533 (2002; Zbl 1011.68152)], was based on column-wise matrix reduction of a boundary matrix of the simplicial complex. The first output-sensitive analysis of an algorithm to compute a persistent homology that ignores homology classes of low persistence is presented here. Proposing a problem for further investigations, it is observed that although the authors’ complexity results do not improve the worst-case time complexity of the problem, the approach of using state-of-the-art methods from symbolic computation can lead to more efficient algorithms.

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y20 Complexity and performance of numerical algorithms
68W30 Symbolic computation and algebraic computation
Full Text: DOI