Efficient computation of persistent homology

Efficient computation of persistent homology

Bibliographic description

title:	Efficient computation of persistent homology
alternative title:	Efektywne metody obliczeń homologii persystentnych
author:	Wagner Hubert
reviewer:	Grytczuk Jarosław , Marzantowicz Wacław
advisor:	Mrozek Marian
institution:	Jagiellonian University. Faculty of Mathematics and Computer Science
place of creation:	Kraków
date of submittion :	2014-11-20
pages:	[1], 69
callnumber :	Dokt. 2014/217
notes:	Dostęp do publikacji jest możliwy w Archiwum UJ
language:	English
abstract in english:	The main problem tackled in my thesis was the efficiency of computational topology algorithms. I focused on persistent homology, which is currently the most widely applicable topological tool. However, efficiency is still a major challenge. I assumed an algorithm engineering perspective, namely focused on the efficiency of practical implementations. This was an effective strategy, which resulted in significant improvements, compared to the existing algorithms and their implementations. In Chapter 6, I presented specialized methods for cubical data, which reduce memory and time requirements by several orders of magnitude, compared to the pre-existing state of the art. This makes analysis of large images, counted in billions (109 ) of voxels feasible even on commodity hardware. Previous, unspecialized methods could only handle millions of voxels. This is especially useful in the context of medical imaging, which starts adopting topological methods. In Chapter 5, I introduced a new technique for matrix reduction, which is applicable for any type of data. Used in conjunction with other recent developments, such as the twist technique, it yields considerable practical speedup, up to a factor of a thousand. Additionally, for an important class of inputs, the observed time complexity is reduced from quadratic to linear. As an additional benefit, modern implementations of computational topology software reduce the number of control parameters. For example, the default configuration of the PHAT library efficiently handles a vast majority of inputs, without the need of manual tuning. This is important, if computational topology software is to be used by non-experts in the field. Summarizing, in the light of the new developments, including the techniques described in this thesis, computational topology is becoming more and more useful. In particular, it starts to supply tools applicable for large amount of data present in current applications.
keywords in polish:	homologie persystentne, dyskretna teoria Morse'a, homologie kostkowe
keywords in english:	persistent homology, discrete Morse theory, cubical homology
affiliation:	Wydział Matematyki i Informatyki : Instytut Informatyki i Matematyki Komputerowej
type:	dissertation, thesis