Document Open Access Logo

Efficient Two-Parameter Persistence Computation via Cohomology

Authors Ulrich Bauer , Fabian Lenzen , Michael Lesnick

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.15.pdf
  • Filesize: 1.05 MB
  • 17 pages

Document Identifiers

Author Details

Ulrich Bauer
  • Department of Mathematics, TUM School of Computation, Information and Technology, and Munich Data Science Institute, Technical University of Munich, Germany
  • www.ulrich-bauer.org
Fabian Lenzen
  • Department of Mathematics, TUM School of Computation, Information and Technology, Technical University of Munich, Germany
Michael Lesnick
  • Department of Mathematics, SUNY Albany, NY, USA

Funding

  • Bauer, Ulrich: Supported by the German Research Foundation (DFG) through the Collaborative Research Center SFB/TRR 109 Discretization in Geometry and Dynamics - 195170736.

Cite As Get BibTex

Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient Two-Parameter Persistence Computation via Cohomology. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.15

Abstract

Clearing is a simple but effective optimization for the standard algorithm of persistent homology (ph), which dramatically improves the speed and scalability of ph computations for Vietoris-Rips filtrations. Due to the quick growth of the boundary matrices of a Vietoris-Rips filtration with increasing dimension, clearing is only effective when used in conjunction with a dual (cohomological) variant of the standard algorithm. This approach has not previously been applied successfully to the computation of two-parameter ph.
We introduce a cohomological algorithm for computing minimal free resolutions of two-parameter ph that allows for clearing. To derive our algorithm, we extend the duality principles which underlie the one-parameter approach to the two-parameter setting. We provide an implementation and report experimental run times for function-Rips filtrations. Our method is faster than the current state-of-the-art by a factor of up to 20.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
  • Theory of computation → Computational geometry
Keywords
  • Persistent homology
  • persistent cohomology
  • two-parameter persistence
  • clearing

Metrics

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

Related Versions

Supplementary Materials

References

  1. Manu Aggarwal and Vipul Periwal. Dory: Overcoming Barriers to Computing Persistent Homology, March 2021. URL: https://arxiv.org/abs/2103.05608.
  2. Ángel Javier Alonso, Michael Kerber, and Siddharth Pritam. Filtration-domination in bifiltered graphs. In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 27-38, 2023. URL: https://doi.org/10.1137/1.9781611977561.ch3.
  3. Ibrahim Assem, Daniel Simson, and Andrzej Skowronski. Elements of the Representation Theory of Associative Algebras, volume 1 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2006. Google Scholar
  4. Ulrich Bauer. Ripser: efficient computation of Vietoris-Rips persistence barcodes. J. Appl. Comput. Topol., 5(3):391-423, 2021. URL: https://doi.org/10.1007/s41468-021-00071-5.
  5. Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Clear and Compress: Computing Persistent Homology in Chunks. In Peer-Timo Bremer, Ingrid Hotz, Valerio Pascucci, and Ronald Peikert, editors, Topological Methods in Data Analysis and Visualization III, pages 103-117. Springer International Publishing, Cham, 2014. URL: https://doi.org/10.1007/978-3-319-04099-8_7.
  6. Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Distributed Computation of Persistent Homology. In Catherine C. McGeoch and Ulrich Meyer, editors, 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 31-38. Society for Industrial and Applied Mathematics, Philadelphia, PA, May 2014. URL: https://doi.org/10.1137/1.9781611973198.4.
  7. Ulrich Bauer, Michael Kerber, Jan Reininghaus, and Hubert Wagner. Phat - persistent homology algorithms toolbox. J. Symbolic Comput., 78:76-90, 2017. URL: https://doi.org/10.1016/j.jsc.2016.03.008.
  8. Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient two-parameter persistence computation via cohomology, March 2023. URL: https://arxiv.org/abs/2303.11193.
  9. Ulrich Bauer and Michael Lesnick. Induced matchings and the algebraic stability of persistence barcodes. Journal of Computational Geometry, 6(2):162-191, March 2015. URL: https://doi.org/10.20382/jocg.v6i2a9.
  10. Ulrich Bauer and Maximilian Schmahl. Lifespan Functors and Natural Dualities in Persistent Homology, October 2021. To appear in Homology, Homotopy and Applications. URL: https://arxiv.org/abs/2012.12881.
  11. Katherine Benjamin, Aneesha Bhandari, Zhouchun Shang, Yanan Xing, Yanru An, Nannan Zhang, Yong Hou, Ulrike Tillmann, Katherine R Bull, and Heather A Harrington. Multiscale topology classifies and quantifies cell types in subcellular spatial transcriptomics. arXiv preprint arXiv:2212.06505, 2022. Google Scholar
  12. Andrew J. Blumberg and Michael Lesnick. Stability of 2-Parameter Persistent Homology. Foundations of Computational Mathematics, October 2022. URL: https://doi.org/10.1007/s10208-022-09576-6.
  13. Magnus Bakke Botnan and Michael Lesnick. An Introduction to Multiparameter Persistence, March 2022. URL: https://arxiv.org/abs/2203.14289.
  14. Gunnar Carlsson and Afra Zomorodian. The Theory of Multidimensional Persistence. Discrete & Computational Geometry, 42(1):71-93, July 2009. URL: https://doi.org/10.1007/s00454-009-9176-0.
  15. Chao Chen and Michael Kerber. Persistent Homology Computation with a Twist. In 27th European Workshop on Computational Geometry, 2011. URL: https://eurocg11.inf.ethz.ch/abstracts/22.pdf.
  16. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37:103-120, January 2007. URL: https://doi.org/10.1007/s00454-006-1276-5.
  17. René Corbet, Michael Kerber, Michael Lesnick, and Georg Osang. Computing the multicover bifiltration. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl endash Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.27.
  18. Vin de Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Dualities in persistent (co)homology. Inverse Problems, 27(12):124003, December 2011. URL: https://doi.org/10.1088/0266-5611/27/12/124003.
  19. Edelsbrunner, Letscher, and Zomorodian. Topological Persistence and Simplification. Discrete & Computational Geometry, 28(4):511-533, November 2002. URL: https://doi.org/10.1007/s00454-002-2885-2.
  20. Herbert Edelsbrunner and John Harer. Persistent homologyemdash a survey. In Jacob E. Goodman, János Pach, and Richard Pollack, editors, Contemporary Mathematics, volume 453, pages 257-282. American Mathematical Society, Providence, Rhode Island, 2008. URL: https://doi.org/10.1090/conm/453/08802.
  21. David Eisenbud. Commutative Algebra, volume 150 of Graduate Texts in Mathematics. Springer New York, New York, NY, 1995. URL: https://doi.org/10.1007/978-1-4612-5350-1.
  22. Ulderico Fugacci and Michael Kerber. Chunk reduction for multi-parameter persistent homology. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 37:1-37:14, Dagstuhl, Germany, 2019. Schloss Dagstuhlendash Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.37.
  23. Ulderico Fugacci, Michael Kerber, and Alexander Rolle. Compression for 2-parameter persistent homology. Computational Geometry, 109:101940, February 2023. URL: https://doi.org/10.1016/j.comgeo.2022.101940.
  24. Victor Ginzburg. Calabi-Yau algebras, 2007. URL: https://arxiv.org/abs/math/0612139.
  25. Barbara Giunti and Jānis Lazovskis. TDA-Applications (An online database of papers on applications of TDA outside of math), 2021. URL: https://www.zotero.org/groups/2425412/tda-applications.
  26. Gregory Henselman and Robert Ghrist. Matroid Filtrations and Computational Persistent Homology, October 2017. URL: https://arxiv.org/abs/1606.00199.
  27. Gregory Henselman-Petrusek. Eirene, 2021. URL: https://github.com/Eetion/Eirene.jl.
  28. Michael Höppner and Helmut Lenzing. Projective diagrams over partially ordered sets are free. Journal of Pure and Applied Algebra, 20(1):7-12, January 1981. URL: https://doi.org/10.1016/0022-4049(81)90045-1.
  29. Bernhard Keller. CalabiendashYau triangulated categories. In Andrzej Skowroński, editor, Trends in Representation Theory of Algebras and Related Topics, EMS Series of Congress Reports, pages 467-489. EMS Press, first edition, September 2008. URL: https://doi.org/10.4171/062-1/11.
  30. Michael Kerber. Multi-parameter persistent homology is practical. In NeurIPS 2020 Workshop on Topological Data Analysis and Beyond, 2020. URL: https://openreview.net/pdf?id=TDU6UycGYxR.
  31. Michael Kerber. mpfree, 2021. URL: https://bitbucket.org/mkerber/mpfree.
  32. Michael Kerber and Alexander Rolle. Fast Minimal Presentations of Bi-graded Persistence Modules. In Martin Farach-Colton and Sabine Storandt, editors, 2021 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Proceedings, pages 207-220. Society for Industrial and Applied Mathematics, January 2021. URL: https://doi.org/10.1137/1.9781611976472.16.
  33. Fabian Lenzen. 2-parameter persistent cohomology, 2023. URL: https://gitlab.com/flenzen/2-parameter-persistent-cohomology.
  34. Michael Lesnick and Matthew Wright. Interactive Visualization of 2-D Persistence Modules, December 2015. URL: https://arxiv.org/abs/1512.00180.
  35. Michael Lesnick and Matthew Wright. Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology. SIAM Journal on Applied Algebra and Geometry, 6(2):267-298, June 2022. URL: https://doi.org/10.1137/20M1388425.
  36. Dmitriy Morozov and Arnur Nigmetov. Towards Lockfree Persistent Homology. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 555-557, Virtual Event USA, July 2020. ACM. URL: https://doi.org/10.1145/3350755.3400244.
  37. Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather A Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6(1):17, December 2017. URL: https://doi.org/10.1140/epjds/s13688-017-0109-5.
  38. Irena Peeva. Graded Syzygies. Springer London, London, 2011. URL: https://doi.org/10.1007/978-0-85729-177-6.
  39. Julián Burella Pérez, Sydney Hauke, Umberto Lupo, Matteo Caorsi, and Alberto Dassatti. giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris-Rips Filtrations, August 2021. URL: https://arxiv.org/abs/2107.05412.
  40. Daniel Quillen. Projective modules over polynomial rings. Inventiones Mathematicae, 36(1):167-171, December 1976. URL: https://doi.org/10.1007/BF01390008.
  41. Alexander Rolle. Multi-parameter hierarchical clustering and beyond. In NeurIPS 2020 Workshop on Topological Data Analysis and Beyond, 2020. URL: https://openreview.net/pdf?id=g0-tBxQTPRy.
  42. Sara Scaramuccia, Federico Iuricich, Leila De Floriani, and Claudia Landi. Computing multiparameter persistent homology through a discrete Morse-based approach. Computational Geometry, 89:101623, August 2020. URL: https://doi.org/10.1016/j.comgeo.2020.101623.
  43. Donald R. Sheehy. A multicover nerve for geometric inference. In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, Prince Edward Island, Canada, August 8-10, 2012, pages 309-314, 2012. URL: http://2012.cccg.ca/papers/paper52.pdf.
  44. Andrei Suslin. Projective modules over polynomial rings are free. Soviet Mathematics, 17(4):1160-1164, 1976. Google Scholar
  45. The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 3.6.0 edition, 2022. URL: https://gudhi.inria.fr/doc/3.6.0/.
  46. Oliver Vipond, Joshua A Bull, Philip S Macklin, Ulrike Tillmann, Christopher W Pugh, Helen M Byrne, and Heather A Harrington. Multiparameter persistent homology landscapes identify immune cell spatial patterns in tumors. Proceedings of the National Academy of Sciences, 118(41):e2102166118, 2021. Google Scholar
  47. Cary Webb. Decomposition of Graded Modules. Proceedings of the American Mathematical Society, 94(4):565-571, 1985. URL: https://doi.org/10.2307/2044864.
  48. Charles A. Weibel. An Introduction to Homological Algebra. Number 38 in Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, Cambridge, reprint. 1997, transf. to digital print edition, 2003. Google Scholar
  49. Simon Zhang, Mengbai Xiao, and Hao Wang. GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1-70:17, Dagstuhl, Germany, 2020. Schloss Dagstuhlendash Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.70.
  50. Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33:249-274, February 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