Title: High Performance Computing for Persistent Homology Computation
Speaker: Simon Zhang, OSU
Abstract: The computation of persistent homology (PH) is a challenging and exciting field of research. In this presentation I will look into the computational nature of computing PH and how it can be accelerated by advanced hardware devices such as multicore and GPU.
A fundamental component of PH computation involves an algorithm for matrix reduction which we term PH matrix reduction. Explicit PH matrix reduction is PH matrix reduction on an in-memory (co) boundary matrix. We have developed HYPHA, a HYbrid Persistent Homology matrix reduction Accelerator, to make parallel processing of explicit PH matrix reduction highly efficient on both GPU and multicore. The essential foundation of our algorithm design and implementation is the separation of SIMT and MIMD parallelisms in explicit PH matrix reduction computation. With such a separation, we are able to perform massive parallel scanning operations on GPU in a super-fast manner, which also collects rich information from an input boundary matrix for further parallel reduction operations on multicore with high efficiency.
Ripser is known to be the fastest software to compute PH barcodes for a Rips filtration from a distance matrix or point cloud of data. Recently, we have evaluated Ripser from the mathematical properties that it uses and its computation. We have developed new algorithms under the HYPHA framework to exploit parallelism and locality in Ripser by GPU acceleration to make this fast software even faster in a significant way. I will discuss this ongoing work in addition to HYPHA.