Parallel multi-scale reduction of persistent homology

Persistent homology is a mathematical formalism based on algebraic topology and is central to Topological Data Analysis (TDA). Its paradigm consists in estimating the topological features of a shape embedded in an Euclidean space from a point-cloud sampled from it. The estimation is done at multiple scales by reducing a, so-called, boundary matrix which is a sparse binary matrix that encodes a simplicial complex filtration built from the point-cloud. The reduction process is similar to Gaussian elimination and represents an important computational bottleneck in the pipeline. To improve the scalability of the TDA framework, several strategies to accelerate it have been proposed. Herein, we present a number of structural dependencies in boundary matrices and use them to design a novel parallel reduction algorithm. In particular, we show that this structural information: (i) makes part of the reduction immediately apparent, (ii) decreases the total number of column operations required for reduction, (iii) gives a framework for which the process can be massively parallelised. Simulations on synthetic examples show that the computational burden can be conducted in a small fraction of the number of iterations needed by traditional methods. Moreover, whereas the traditional methods reveal barcodes sequentially from a filtration order, this approach gives an alternative method by which barcodes are partly revealed for multiple scales simultaneously and further refined as the algorithm progresses. Specifically, our numerical experiments show that for a Vietoris-Rips filtration with 10^4 simplices, the essential topological information can be estimated with 95% precision in two iterations and that the reduction completed to within 1% in about ten iterations of our algorithm as opposed to nearly approximately eight thousand iterations for traditional methods.