Efektywne metody obliczeń homologii persystentnych

Dostęp do publikacji jest możliwy w Archiwum UJ

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.