An output-sensitive algorithm for persistent homology (Q1940704)

The authors study the computation of persistent homology of a simplicial complex over \(\mathbb Z_2\). In this direction, the first algorithm by \textit{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.