Brief Announcement: Towards Lockfree Persistent Homology

SPAA

Abstract
Persistent homology, which describes the shape of data by quantifying the sizes of its topological features, is one of the most ubiquitous algorithms in topological data analysis. All existing algorithms that compute persistence in parallel rely on the algebraic structure of the problem to subdivide the computation, either by partitioning the range, or the domain of the underlying scalar measurement. Instead, we exploit the inherent parallelism of the reduction algorithm and rely on hardware synchronization primitives, namely compareandswap operations, to develop a lockfree sharedmemory algorithm that avoids having to decide how to partition the underlying data set. We demonstrate the algorithmâ€™s performance and scaling using a set of computational experiments.