Computing persistent homology in parallel with a functional language
| dc.contributor.author | von Brömssen, Erik | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för matematiska vetenskaper | sv |
| dc.contributor.examiner | Raum, Martin | |
| dc.contributor.supervisor | Hughes, John | |
| dc.contributor.supervisor | Sheeran, Mary | |
| dc.date.accessioned | 2021-06-18T12:12:12Z | |
| dc.date.available | 2021-06-18T12:12:12Z | |
| dc.date.issued | 2021 | sv |
| dc.date.submitted | 2020 | |
| dc.description.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: | sv |
| dc.identifier.coursecode | MVEX03 | sv |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/302628 | |
| dc.language.iso | eng | sv |
| dc.setspec.uppsok | PhysicsChemistryMaths | |
| dc.subject | Persistent homology, functional programming, GPU, Futhark, sparse matrix. | sv |
| dc.title | Computing persistent homology in parallel with a functional language | sv |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.uppsok | H | |
| local.programme | Engineering mathematics and computational science (MPENM), MSc |