Jagiellonian University Repository

Efficient computation of persistent homology


Efficient computation of persistent homology

Show full item record

dc.contributor.advisor Mrozek, Marian [SAP11008942] pl
dc.contributor.author Wagner, Hubert [USOS777] pl
dc.date.accessioned 2018-11-22T12:35:59Z
dc.date.available 2018-11-22T12:35:59Z
dc.date.submitted 2014-11-20 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/61277
dc.language eng pl
dc.rights Copyright *
dc.rights.uri http://ruj.uj.edu.pl/4dspace/License/copyright/licencja_copyright.pdf *
dc.title Efficient computation of persistent homology pl
dc.title.alternative Efektywne metody obliczeń homologii persystentnych pl
dc.type Thesis pl
dc.place Kraków pl
dc.description.physical [1], 69 pl
dc.description.additional Dostęp do publikacji jest możliwy w Archiwum UJ pl
dc.abstract.en 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. pl
dc.subject.pl homologie persystentne pl
dc.subject.pl dyskretna teoria Morse'a pl
dc.subject.pl homologie kostkowe pl
dc.subject.en persistent homology pl
dc.subject.en discrete Morse theory pl
dc.subject.en cubical homology pl
dc.identifier.callnumber Dokt. 2014/217 pl
dc.contributor.institution Jagiellonian University. Faculty of Mathematics and Computer Science pl
dc.contributor.reviewer Grytczuk, Jarosław [SAP11019186] pl
dc.contributor.reviewer Marzantowicz, Wacław pl
dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki i Matematyki Komputerowej pl
dc.rights.original bez licencji pl
dc.identifier.project ROD UJ / O pl

Files in this item

This item appears in the following Collection(s)

Copyright Except where otherwise noted, this item's license is described as Copyright