TY - GEN

T1 - Distributed computation of persistent homology

AU - Bauer, Ulrich

AU - Kerber, Michael

AU - Reininghaus, Jan

N1 - Publisher Copyright:
Copyright © 2014. by the Society for Industrial and Applied Mathematics.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84916893505&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973198.4

DO - 10.1137/1.9781611973198.4

M3 - Conference contribution

AN - SCOPUS:84916893505

T3 - Proceedings of the Workshop on Algorithm Engineering and Experiments

SP - 31

EP - 38

BT - 2014 Proceedings of the 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014

A2 - McGeoch, Catherine C.

A2 - Meyer, Ulrich

PB - Society for Industrial and Applied Mathematics Publications

T2 - 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014

Y2 - 5 January 2014 through 5 January 2014

ER -