Computing persistent homology in parallel with a functional language
Examensarbete för masterexamen
Please use this identifier to cite or link to this item:
Bibliographical item details
|Type: ||Examensarbete för masterexamen|
|Title: ||Computing persistent homology in parallel with a functional language|
|Authors: ||von Brömssen, Erik|
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: ||Persistent homology, functional programming, GPU, Futhark, sparse matrix.|
|Issue Date: ||2021|
|Publisher: ||Chalmers tekniska högskola / Institutionen för matematiska vetenskaper|
|Collection:||Examensarbeten för masterexamen // Master Theses|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.