License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.70
URN: urn:nbn:de:0030-drops-122287
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12228/
Go to the corresponding LIPIcs Volume Portal

Zhang, Simon ; Xiao, Mengbai ; Wang, Hao

GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes

pdf-format:
LIPIcs-SoCG-2020-70.pdf (1 MB)

Abstract

The computation of Vietoris-Rips persistence barcodes is both execution-intensive and memory-intensive. In this paper, we study the computational structure of Vietoris-Rips persistence barcodes, and identify several unique mathematical properties and algorithmic opportunities with connections to the GPU. Mathematically and empirically, we look into the properties of apparent pairs, which are independently identifiable persistence pairs comprising up to 99% of persistence pairs. We give theoretical upper and lower bounds of the apparent pair rate and model the average case. We also design massively parallel algorithms to take advantage of the very large number of simplices that can be processed independently of each other. Having identified these opportunities, we develop a GPU-accelerated software for computing Vietoris-Rips persistence barcodes, called Ripser++. The software achieves up to 30x speedup over the total execution time of the original Ripser and also reduces CPU-memory usage by up to 2.0x. We believe our GPU-acceleration based efforts open a new chapter for the advancement of topological data analysis in the post-Moore’s Law era.

BibTeX - Entry

@InProceedings{zhang_et_al:LIPIcs:2020:12228,
  author =	{Simon Zhang and Mengbai Xiao and Hao Wang},
  title =	{{GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{70:1--70:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12228},
  URN =		{urn:nbn:de:0030-drops-122287},
  doi =		{10.4230/LIPIcs.SoCG.2020.70},
  annote =	{Keywords: Parallel Algorithms, Topological Data Analysis, Vietoris-Rips, Persistent Homology, Apparent Pairs, High Performance Computing, GPU, Random Graphs}
}

Keywords: Parallel Algorithms, Topological Data Analysis, Vietoris-Rips, Persistent Homology, Apparent Pairs, High Performance Computing, GPU, Random Graphs
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020
Supplementary Material: Open Source Software: https://www.github.com/simonzhang00/ripser-plusplus

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI