×

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
Software:
LinBox
PDF BibTeX XML Cite
Full Text: DOI