Chunk Reduction for Multi-Parameter Persistent Homology

Authors Ulderico Fugacci , Michael Kerber



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.37.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Ulderico Fugacci
  • Graz University of Technology, Graz, Austria
Michael Kerber
  • Graz University of Technology, Graz, Austria

Acknowledgements

We thank Sara Scaramuccia for initial discussions on this project, Wojciech Chacholski, Michael Lesnick and Francesco Vaccarino for helpful suggestions, and Federico Iuricich for his help on the experimental comparison with [Iuricich, 2018]. The datasets used in the experimental evaluation are courtesy of the AIM@SHAPE data repository [Digital Shape WorkBench, 2006].

Cite AsGet BibTex

Ulderico Fugacci and Michael Kerber. Chunk Reduction for Multi-Parameter Persistent Homology. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.37

Abstract

The extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Computing methodologies → Shared memory algorithms
Keywords
  • Multi-parameter persistent homology
  • Matrix reduction
  • Chain complexes

Metrics

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

References

  1. M. Allili, T. Kaczynski, and C. Landi. Reducing complexes in multidimensional persistent homology theory. Journal of Symbolic Computation, 78:61-75, 2017. URL: http://dx.doi.org/10.1016/j.jsc.2015.11.020.
  2. M. Allili, T. Kaczynski, C. Landi, and F. Masoni. Acyclic partial matchings for multidimensional persistence: algorithm and combinatorial interpretation. Journal of Mathematical Imaging and Vision, pages 1-19, 2018. Google Scholar
  3. U. Bauer, M. Kerber, and J. Reininghaus. Clear and compress: computing persistent homology in chunks. In Topological methods in data analysis and visualization III, pages 103-117. Springer, 2014. Google Scholar
  4. U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. Phat - persistent homology algorithms toolbox. Journal of Symbolic Computation, 78:76-90, 2017. Google Scholar
  5. G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete &Computational Geometry, 42(1):71-93, 2009. Google Scholar
  6. A. Cerri and C. Landi. The persistence space in multidimensional persistent homology. In R. Gonzalez-Diaz, M.-J. Jimenez, and B. Medrano, editors, Discrete Geometry for Computer Imagery, pages 180-191. Springer Berlin Heidelberg, 2013. Google Scholar
  7. W. Chachólski, M. Scolamiero, and F. Vaccarino. Combinatorial presentation of multidimensional persistent homology. Journal of Pure and Applied Algebra, 221(5):1055-1075, 2017. Google Scholar
  8. C. Chen and M. Kerber. Persistent homology computation with a twist. In Proceedings 27th European Workshop on Computational Geometry, volume 11, pages 197-200, 2011. Google Scholar
  9. Digital Shape WorkBench. AIM@SHAPE project, 2006. URL: http://visionair.ge.imati.cnr.it.
  10. F. Iuricich. FG-multi, 2018. URL: http://github.com/IuricichF/fg_multi.
  11. F. Iuricich, S. Scaramuccia, C. Landi, and L. De Floriani. A discrete Morse-based approach to multivariate data analysis. In SIGGRAPH ASIA 2016 Symposium on Visualization, pages 5-12. ACM, 2016. Google Scholar
  12. K. P. Knudson. A refinement of multi-dimensional persistence. Homology, Homotopy and Applications, 10(1):259 – 281, 2008. Google Scholar
  13. M. Lesnick and M. Wright. Computing minimal presentations of bipersistence modules in cubic time. In preparation. Google Scholar
  14. M. Lesnick and M. Wright. Interactive visualization of 2-D persistence modules. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.00180.
  15. E. Miller. Data structures for real multiparameter persistence modules. arXiv preprint, 2017. URL: http://arxiv.org/abs/1709.08155.
  16. S. Scaramuccia. Computational and theoretical issues of multiparameter persistent homology for data analysis. PhD thesis, University of Genova, Italy, 2018. URL: http://hdl.handle.net/11567/929143.
  17. S. Scaramuccia, F. Iuricich, L. De Floriani, and C. Landi. Computing multiparameter persistent homology through a discrete Morse-based approach. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.05396.
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