Computing persistent homology in parallel with a functional language
Typ
Examensarbete för masterexamen
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2021
Författare
von Brömssen, Erik
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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:
Beskrivning
Ämne/nyckelord
Persistent homology, functional programming, GPU, Futhark, sparse matrix.