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.

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