Computing persistent homology in parallel with a functional language

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/302628
Download file(s):
File Description SizeFormat 
Master_thesis_Erik_von_Bromssen.pdf1.29 MBAdobe PDFThumbnail
View/Open
Bibliographical item details
FieldValue
Type: Examensarbete för masterexamen
Title: Computing persistent homology in parallel with a functional language
Authors: von Brömssen, Erik
Abstract: Abstract Persistent homology, first developed at the beginning of the millennium, is a tool within the field of topological data analysis. It is an extension of simplicial homology to filtrations of simplicial complexes, which allows one to, in a sense, compute topological features of finite sets of points in a metric space at a variety of scales. More precisely, persistent homology is concerned with sequences of homomorphisms between homology groups induced by inclusions on the underlying groups of cycles. Persistent homology is well suited for data analysis since it can be efficiently computed via a certain matrix reduction. Graphics processing units (GPUs), originally designed for tasks such as image rendering, have recently become an integral part of high performance computing due to their massively parallel design. Futhark is a statically typed purely functional language that compiles to efficient code for GPUs. The goal of Futhark is to simplify the implementation of algorithms for GPUs, by giving a high-level functional perspective and hiding low-level concepts from the programmer. In this thesis we present a massively parallel algorithm for computing persistent homology on GPUs, and we describe an implementation in Futhark. Our algorithm is conceptually simple, and its main parts are all entirely massively parallel. Our implementation utilises a sparse matrix data structure and exemplifies that nontrivial sparse matrix computations can be efficiently implemented in Futhark. We compare the performance of our algorithm to that of OpenPH, an existing GPUbased persistent homology algorithm, and achieve speedups of 2.3 to 5. Lastly, we briefly investigate the potential to use our algorithm for approximating persistent homology via early stopping. Keywords:
Keywords: Persistent homology, functional programming, GPU, Futhark, sparse matrix.
Issue Date: 2021
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
URI: https://hdl.handle.net/20.500.12380/302628
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.