Document Open Access Logo

Swap, Shift and Trim to Edge Collapse a Filtration

Authors Marc Glisse , Siddharth Pritam

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.44.pdf
  • Filesize: 1.09 MB
  • 15 pages

Document Identifiers

Author Details

Marc Glisse
  • Université Paris-Saclay, CNRS, Inria, Laboratoire de Mathématiques d'Orsay, 91405, Orsay, France
Siddharth Pritam
  • School of Engineering, Department of Computer Science, Shiv Nadar University, Delhi NCR, India

Cite As Get BibTex

Marc Glisse and Siddharth Pritam. Swap, Shift and Trim to Edge Collapse a Filtration. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.44

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 use of edge collapse for efficient computation of persistent 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Algebraic topology
Keywords
  • edge collapse
  • flag complex
  • graph
  • persistent homology

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. M. Aggarwal and V. Periwal. Dory: Overcoming barriers to computing persistent homology, 2021. URL: http://arxiv.org/abs/2103.05608.
  2. J. A. Barmak and E. G. Minian. Strong homotopy types, nerves and collapses. Discrete and Computational Geometry, 47:301-328, 2012. URL: https://doi.org/10.1007/s00454-011-9357-5.
  3. U. Bauer. Ripser: efficient computation of Vietoris-Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3):391-423, 2021. URL: https://doi.org/10.1007/s41468-021-00071-5.
  4. U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. PHAT - persistent homology algorithms toolbox. Journal of Symbolic Computation, 78, 2017. URL: https://doi.org/10.1016/j.jsc.2016.03.008.
  5. J-D. Boissonnat and S. Pritam. Computing persistent homology of flag complexes via strong collapses. International Symposium on Computational Geometry (SoCG), 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.55.
  6. J-D. Boissonnat and S. Pritam. Edge collapse and persistence of flag complexes. International Symposium on Computational Geometry (SoCG), 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.19.
  7. M. Botnan and G. Spreemann. Approximating persistent homology in Euclidean space through collapses. In: Applicable Algebra in Engineering, Communication and Computing, 26:73-101, 2015. URL: https://doi.org/10.1007/s00200-014-0247-y.
  8. G. Carlsson and V. de Silva. Zigzag persistence. Found Comput Math, 10, 2010. URL: https://doi.org/10.1007/s10208-010-9066-0.
  9. F. Chazal, V. de Silva, M. Glisse, and S. Oudot. The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Springer, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-42545-0.
  10. F. Chazal and S. Oudot. Towards persistence-based reconstruction in Euclidean spaces. International Symposium on Computational Geometry (SoCG), 2008. URL: https://doi.org/10.1145/1377676.1377719.
  11. A. Choudhary, M. Kerber, and S. Raghvendra:. Polynomial-sized topological approximations using the permutahedron. Discrete and Computational Geometry, 61:42-80, 2019. URL: https://doi.org/10.1007/s00454-017-9951-2.
  12. H. Derksen and J. Weyman. Quiver representations. Notices of the American Mathematical Society, 52(2):200-206, February 2005. URL: https://www.ams.org/journals/notices/200502/fea-weyman.pdf.
  13. T. K. Dey, D. Shi, and Y. Wang. Simba: An efficient tool for approximating Rips-filtration persistence via simplicial batch collapse. ACM J. Exp. Algorithmics, 24, January 2019. URL: https://doi.org/10.1145/3284360.
  14. P. Dłotko and H. Wagner. Simplification of complexes for persistent homology computations. Homology, Homotopy and Applications, 16:49-63, 2014. URL: https://doi.org/10.4310/HHA.2014.v16.n1.a3.
  15. H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. American Mathematical Society, 2010. Google Scholar
  16. Gudhi: Geometry understanding in higher dimensions. URL: https://gudhi.inria.fr/.
  17. A. Hatcher. Algebraic Topology. Univ. Press Cambridge, 2001. URL: https://pi.math.cornell.edu/~hatcher/AT/ATpage.html.
  18. A. Hylton, G. Henselman-Petrusek, J. Sang, and R. Short. Tuning the performance of a computational persistent homology package. Software: practice & experience, 49(5):885-905, May 2019. URL: https://doi.org/10.1002/spe.2678.
  19. M. Kerber and R. Sharathkumar. Approximate Čech complex in low and high dimensions. In Algorithms and Computation, pages 666-676. By Leizhen Cai, Siu-Wing Cheng, and Tak-Wah Lam. Vol. 8283. Lecture Notes in Computer Science, 2013. URL: https://doi.org/10.1007/978-3-642-45030-3_62.
  20. C. Maria and S. Oudot. Zigzag persistence via reflections and transpositions. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 181-199, January 2015. URL: https://doi.org/10.1145/1542362.1542408.
  21. K. Mischaikow and V. Nanda. Morse theory for filtrations and efficient computation of persistent homology. Discrete and Computational Geometry, 50:330-353, September 2013. URL: https://doi.org/10.1007/s00454-013-9529-6.
  22. D. Mozozov. Dionysus. URL: http://www.mrzv.org/software/dionysus/.
  23. J. Munkres. Elements of Algebraic Topology. Perseus Publishing, 1984. Google Scholar
  24. N. Otter, M. Porter, U. Tillmann, P. Grindrod, and H. Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, Springer Nature, 6:17, 2017. URL: https://doi.org/10.1140/epjds/s13688-017-0109-5.
  25. J. B. Pérez, S. Hauke, U. Lupo, M. Caorsi, and A. Dassatti. Giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris-Rips Filtrations. CoRR, 2021. URL: http://arxiv.org/abs/2107.05412.
  26. M. Xiao S. Zhang and H. Wang. GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes. International Symposium on Computational Geometry (SoCG), 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.70.
  27. D. Sheehy. Linear-size approximations to the Vietoris-Rips filtration. Discrete and Computational Geometry, 49:778-796, 2013. URL: https://doi.org/10.1007/s00454-013-9513-1.
  28. A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete and Computational Geometry, 33:249-274, 2005. URL: https://doi.org/10.1007/s00454-004-1146-y.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact