Swap, Shift and Trim to Edge Collapse a filtration | Shiv Nadar University
Enquire Now
Apply Now
UG Admissions 2023 (Deadline: 31 March)UG International Admissions 2023PhD Admissions Spring 2023MBA Admissions 2023 (Deadline: 31 March)MBA Information SessionMBA (Online) Admissions (Deadline: 31 March)Lateral Admission -2023

Swap, Shift and Trim to Edge Collapse a filtration

03 May 2022

Citation: M. Glisse, S. Pritam. "Swap, Shift and Trim to Edge Collapse a filtration", 38th International Symposium on Computational Geometry, SoCG 2022.

Abstract: Boissonnat and Pritam introduced an algorithm to reduce a filtration of flag (or clique) complexes, which can in particular speed up the computation of its persistent homology. They used so-called edge collapse to reduce the input flag filtration and their reduction method required only the 1-skeleton of the filtration. In this paper we revisit the usage of edge collapse for efficient computation of persistence homology. We first give a simple and intuitive explanation of the principles underlying that algorithm. This in turn allows us to propose various extensions including a zigzag filtration simplification algorithm. We finally show some experiments to better understand how it behaves.

Link: https://arxiv.org/abs/2203.07022