LIPIcs.SoCG.2019.37.pdf
- Filesize: 0.69 MB
- 14 pages
Document
Chunk Reduction for Multi-Parameter Persistent Homology
Authors
Ulderico Fugacci 
,
Michael Kerber
-
Part of:
Volume:
35th International Symposium on Computational Geometry (SoCG 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-06-11
File
Document Identifiers
Author Details
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
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)
0PDF Downloads
References
- 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.
-
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.
-
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.
-
U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner. Phat - persistent homology algorithms toolbox. Journal of Symbolic Computation, 78:76-90, 2017.
-
G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete &Computational Geometry, 42(1):71-93, 2009.
-
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.
-
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.
-
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.
- Digital Shape WorkBench. AIM@SHAPE project, 2006. URL: http://visionair.ge.imati.cnr.it.
- F. Iuricich. FG-multi, 2018. URL: http://github.com/IuricichF/fg_multi.
-
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.
-
K. P. Knudson. A refinement of multi-dimensional persistence. Homology, Homotopy and Applications, 10(1):259 – 281, 2008.
-
M. Lesnick and M. Wright. Computing minimal presentations of bipersistence modules in cubic time. In preparation.
- M. Lesnick and M. Wright. Interactive visualization of 2-D persistence modules. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.00180.
- E. Miller. Data structures for real multiparameter persistence modules. arXiv preprint, 2017. URL: http://arxiv.org/abs/1709.08155.
- 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.
- 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.