FoCM 2014 conference
Workshop B2 - Computational Topology and Geometry
December 17, 16:00 ~ 16:25 - Room A22
Practical efficiency of persistent homology computations
Hubert Wagner
IST Austria, Austria - hub.wag@gmail.com
In this talk I summarize a number of algorithmic techniques that enhance the efficiency of persistent homology computations. While the existing algorithms are at least quadratic in the number of input cells in the worst case, careful optimizations yield roughly linear behavior for practical data sets. I focus on discrete Morse theoretical preprocessing, which is especially useful for cubical (e.g. image) data. Additionally, efficient variants of the standard matrix reduction algorithm are discussed.
Joint work with Uli Bauer (IST Austria), David Gunther (Télécom ParisTech), Michael Kerber (MPI Saarbrücken) and Jan Reininghaus (IST Austria).