S4C1/MA-INF 1205 Graduate Seminar Discrete Optimization - Efficient algorithms for computing persistent homology

Offered by Anne Driemel and Benedikt Kolbe


The first meeting for the seminar will take on Friday April 14, 2023, at 2:15 pm in room 2.050 (Informatik V, 2. OG) . The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8. The assignment of topics and the schedule of talks will be decided in or shortly after the first meeting. If you are interested to participate in the seminar and want to receive updates please attend the first meeting or get in touch with Dr. Benedikt Kolbe or Prof. Dr. Anne Driemel. There is also a course page in eCampus.


The seminar is centered around topics in computational topology that relate to persistent homology. We will investigate recent algorithms for the computation of invariants of persistence modules, including the current state-of-the-art software Ripser for the computation of Vietoris-Rips barcodes associated to point clouds. From a slightly different perspective, we also consider novel algorithms that focus on optimizing different shortcomings of the standard reduction algorithm for the computation of a barcode. Here, the main focuses are strategies for optimizing memory usage by preprocessing and new algorithms for special kinds of persistence modules such as zigzag and biparameter modules. These works focus on practical aspects of the computation of special instances of persistence. To complement this approach, we also analyze other recent theoretical results relating to the computation of persistence. One is a generalization of the Laplacian to contexts involving persistence. Recent algorithms for its computation give rise to a novel algorithm for the computation of persistent Betti numbers.

To be able to follow the seminar, you should have a solid background in the aspects of computational topology relating to persistent homology, as covered in the course computational topology that took place in the winter semester 22/23.

Literature (tentative)

- Kerber, M., & Schreiber, H. (2019). Barcodes of Towers and a Streaming Algorithm for Persistent Homology. Discrete and Computational Geometry, 61(4), 852–879. https://doi.org/10.1007/s00454-018-0030-0

- Kerber, M., & Nigmetov, A. (2020). Efficient Approximation of the Matching Distance for 2-Parameter Persistence. In S. Cabello & D. Z. Chen (Eds.), 36th International Symposium on Computational Geometry (SoCG 2020) (Vol. 164, pp. 53:1–53:16). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.53

- Dey, T. K., & Hou, T. (2022). Fast Computation of Zigzag Persistence. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (Vol. 244, pp. 43:1–43:15). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.43

- Mémoli, F., Wan, Z., & Wang, Y. (2022). Persistent Laplacians: Properties, Algorithms and Implications. SIAM Journal on Mathematics of Data Science, 4(2), 858–884. https://doi.org/10.1137/21m1435471

- Fugacci, U., & Kerber, M. (2019). Chunk Reduction for Multi-Parameter Persistent Homology. In G. Barequet & Y. Wang (Eds.), 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129, pp. 37:1–37:14). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.37

- Bauer, U. (2021). Ripser: efficient computation of Vietoris–Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3), 391–423. https://doi.org/10.1007/s41468-021-00071-5

Page Tools