conference paper
Distributed computation of persistent homology
published
yes
Ulrich
Bauer
author 2ADD483A-F248-11E8-B48F-1D18A9856A870000-0002-9683-0724
Michael
Kerber
author 0000-0002-8030-9299
Jan
Reininghaus
author 4505473A-F248-11E8-B48F-1D18A9856A87
Catherine McGeoch
editor
UlrichMeyer
editor
HeEd
department
ALENEX: Algorithm Engineering and Experiments
Topological Complex Systems
project
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.
Society of Industrial and Applied Mathematics2014Portland, USA
eng
Proceedings of the Workshop on Algorithm Engineering and Experiments10.1137/1.9781611973198.4
31 - 38
Bauer, U., Kerber, M., & Reininghaus, J. (2014). Distributed computation of persistent homology. In C. McGeoch & U. Meyer (Eds.), <i>Proceedings of the Workshop on Algorithm Engineering and Experiments</i> (pp. 31–38). Portland, USA: Society of Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611973198.4">https://doi.org/10.1137/1.9781611973198.4</a>
U. Bauer, M. Kerber, and J. Reininghaus, “Distributed computation of persistent homology,” in <i>Proceedings of the Workshop on Algorithm Engineering and Experiments</i>, Portland, USA, 2014, pp. 31–38.
Bauer U, Kerber M, Reininghaus J. 2014. Distributed computation of persistent homology. Proceedings of the Workshop on Algorithm Engineering and Experiments. ALENEX: Algorithm Engineering and Experiments, 31–38.
Bauer U, Kerber M, Reininghaus J. Distributed computation of persistent homology. In: McGeoch C, Meyer U, eds. <i>Proceedings of the Workshop on Algorithm Engineering and Experiments</i>. Society of Industrial and Applied Mathematics; 2014:31-38. doi:<a href="https://doi.org/10.1137/1.9781611973198.4">10.1137/1.9781611973198.4</a>
Bauer, Ulrich, Michael Kerber, and Jan Reininghaus. “Distributed Computation of Persistent Homology.” In <i>Proceedings of the Workshop on Algorithm Engineering and Experiments</i>, edited by Catherine McGeoch and Ulrich Meyer, 31–38. Society of Industrial and Applied Mathematics, 2014. <a href="https://doi.org/10.1137/1.9781611973198.4">https://doi.org/10.1137/1.9781611973198.4</a>.
Bauer, Ulrich, et al. “Distributed Computation of Persistent Homology.” <i>Proceedings of the Workshop on Algorithm Engineering and Experiments</i>, edited by Catherine McGeoch and Ulrich Meyer, Society of Industrial and Applied Mathematics, 2014, pp. 31–38, doi:<a href="https://doi.org/10.1137/1.9781611973198.4">10.1137/1.9781611973198.4</a>.
U. Bauer, M. Kerber, J. Reininghaus, in:, C. McGeoch, U. Meyer (Eds.), Proceedings of the Workshop on Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics, 2014, pp. 31–38.
20432018-12-11T11:55:23Z2021-01-12T06:54:56Z