Distributed computation of persistent homology

Ulrich Bauer, Michael Kerber, Jan Reininghaus

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

80 Scopus citations

Abstract

Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically - as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems [1], we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (109) elements within seconds on a cluster with 32 nodes using less than 6GB of memory per node.

Original languageEnglish
Title of host publication2014 Proceedings of the 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014
EditorsCatherine C. McGeoch, Ulrich Meyer
PublisherSociety for Industrial and Applied Mathematics Publications
Pages31-38
Number of pages8
ISBN (Electronic)9781611973198
DOIs
StatePublished - 2014
Externally publishedYes
Event16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014 - Portland, United States
Duration: 5 Jan 20145 Jan 2014

Publication series

NameProceedings of the Workshop on Algorithm Engineering and Experiments
ISSN (Print)2164-0300

Conference

Conference16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014
Country/TerritoryUnited States
CityPortland
Period5/01/145/01/14

Fingerprint

Dive into the research topics of 'Distributed computation of persistent homology'. Together they form a unique fingerprint.

Cite this