Computing persistent homology with various coefficient fields in a single pass (Q2324603): Difference between revisions

This paper is concerned with the computation of persistent homology of a filtered complex with various coefficient fields in a single matrix reduction. The standard persistent homology algorithm was made famous by the book by \textit{H. Edelsbrunner} and \textit{J. L. Harer} [Computational topology. An introduction. Providence, RI: American Mathematical Society (AMS) (2010; Zbl 1193.55001), Chapter VII], where the boundary matrix \(\mathbf{M}_{\partial}\) obtained from a filtered complex \(\mathbf{K}\) is reduced to a column echelon form to obtain a persistence diagram. The standard persistent homology algorithm is based on a fixed coefficient field, \(\mathbb{F}\), where \(\mathbb{F}\) are prime numbers. Torsion subgroups may not be reported in persistence diagrams for a fixed coefficient field. A workaround would be to compute the persistent homology algorithm for various coefficient fields and keep track of the changes in the persistence diagrams. However, this approach increases the computation time. The computation of persistent homology with various \(\mathbb{F}\) is denoted as a brute-force algorithm in this paper. In order to overcome this problem, the authors modify the existing persistent homology algorithm by using the Chinese Remainder Isomorphism and call this the modular reconstruction algorithm. This algorithm is currently freely available in the GUDHI software online. Thus, users will be able to compute multi-field persistent homology directly, without need to repeatedly generate persistence diagrams with various coefficient fields. The authors describe the construction of this algorithm in detail by first explaining the extension of elementary matrix operations, then putting them together as a pseudo-code. They also report on the complexity of the proposed modular reconstruction algorithm. In order to show its usability, experiments were conducted on real/synthetic geometric data built on Rips complexes and also random symplicial complexes. In conclusion, for medium to large field coefficients, the modular reconstruction algorithm is faster than the brute force algorithm.