×

zbMATH — the first resource for mathematics

Phat – persistent homology algorithms toolbox. (English) Zbl 1348.68181
Summary: Phat is an open-source C++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.

MSC:
68T05 Learning and adaptive systems in artificial intelligence
55N35 Other homology theories in algebraic topology
68-04 Software, source code, etc. for problems pertaining to computer science
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, H.; Tausz, A.; Vejdemo-Johansson, M., Javaplex: a research software package for persistent (co)homology, (Hong, H.; Yap, C., Mathematical Software - ICMS 2014, Lecture Notes in Computer Science, vol. 8592, (2014), Springer Berlin, Heidelberg), 129-136 · Zbl 1402.65186
[2] Alexandrescu, A., Modern C++ design: generic programming and design patterns applied, (2001), Addison-Wesley
[3] Austern, M. H., Generic programming and the \scstl, (1999), Addison-Wesley
[4] Bauer, U.; Kerber, M.; Reininghaus, J., Clear and compress: computing persistent homology in chunks, (Topological Methods in Data Analysis and Visualization III, Mathematics and Visualization, (2014), Springer), 103-117 · Zbl 1326.68299
[5] Bauer, U.; Kerber, M.; Reininghaus, J., Distributed computation of persistent homology, (2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2014, Portland, Oregon, USA, January 5, 2014, (2014)), 31-38
[6] Boissonnat, J.; Dey, T. K.; Maria, C., The compressed annotation matrix: an efficient data structure for computing persistent cohomology, (Algorithms - ESA 2013 - 21st Annual European Symposium, Proceedings, Sophia Antipolis, France, September 2-4, 2013, (2013)), 695-706 · Zbl 1331.68056
[7] Boissonnat, J.; Maria, C., The simplex tree: an efficient data structure for general simplicial complexes, (Algorithms - ESA 2012 - 20th Annual European Symposium, Proceedings, Ljubljana, Slovenia, September 10-12, 2012, (2012)), 731-742 · Zbl 1365.68171
[8] Chen, C.; Kerber, M., Persistent homology computation with a twist, (27th European Workshop on Computational Geometry (EuroCG), (2011)), 197-200, URL
[9] Chen, C.; Kerber, M., An output-sensitive algorithm for persistent homology, Comput. Geom., 46, 4, 435-447, (2013) · Zbl 1264.65023
[10] Cohen-Steiner, D.; Edelsbrunner, H.; Morozov, D., Vines and vineyards by updating persistence in linear time, (Proceedings of the Twenty-second Annual Symposium on Computational Geometry, SCG’06, (2006), ACM New York, NY, USA), 119-126 · Zbl 1153.68388
[11] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to algorithms, (2009), The MIT Press · Zbl 1187.68679
[12] de Silva, V.; Morozov, D.; Vejdemo-Johansson, M., Dualities in persistent (co)homology, Inverse Probl., 27, 12, (2011) · Zbl 1247.68307
[13] Edelsbrunner, H.; Harer, J., Persistent homology - a survey, (Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics, (2008)), 257-282 · Zbl 1145.55007
[14] Edelsbrunner, H.; Harer, J., Computational topology. an introduction, (2010), American Mathematical Society · Zbl 1193.55001
[15] Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 4, 511-533, (2002) · Zbl 1011.68152
[16] Fasy, B. T.; Kim, J.; Lecci, F.; Maria, C., Introduction to the R package TDA, (2015)
[17] Forman, R., Morse theory for cell complexes, Adv. Math., 134, 1, 90-145, (1998) · Zbl 0896.57023
[18] Günther, D.; Reininghaus, J.; Hotz, I.; Wagner, H., Memory-efficient computation of persistent homology for 3D images using discrete Morse theory, (24th SIBGRAPI Conference on Graphics, Patterns and Images, Sibgrapi 2011, Alagoas, Maceió, Brazil, August 28-31, 2011, (2011)), 25-32
[19] Günther, D.; Reininghaus, J.; Wagner, H.; Hotz, I., Efficient computation of 3D Morse-Smale complexes and persistent homology using discrete Morse theory, Vis. Comput., 28, 10, 959-969, (2012)
[20] Kasten, J.; Reininghaus, J.; Reich, W.; Scheuermann, G., Toward the extraction of saddle periodic orbits, (Topological Methods in Data Analysis and Visualization III, Mathematics and Visualization, (2014), Springer), 55-69 · Zbl 1326.68309
[21] Lewis, R. H.; Zomorodian, A., Multicore homology via Mayer Vietoris, (2014)
[22] Lipsky, D.; Skraba, P.; Vejdemo-Johansson, M., A spectral sequence for parallelized persistence, (2011)
[23] Maria, C.; Boissonnat, J.; Glisse, M.; Yvinec, M., The gudhi library: simplicial complexes and persistent homology, (Mathematical Software - ICMS 2014 - 4th International Congress, Proceedings, Seoul, South Korea, August 5-9, 2014, (2014)), 167-174 · Zbl 1402.57001
[24] Milosavljevic, N.; Morozov, D.; Skraba, P., Zigzag persistent homology in matrix multiplication time, (Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, (2011)), 216-225 · Zbl 1283.68373
[25] Mischaikow, K.; Nanda, V., Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput. Geom., 50, 2, 330-353, (2013) · Zbl 1278.57030
[26] Morozov, D., Dionysus, (2010), URL
[27] Nanda, V., Perseus: the persistent homology software, (2013), Accessed 30/01/15. URL
[28] Wagner, H.; Dłotko, P., Towards topological analysis of high-dimensional feature spaces, Comput. Vis. Image Underst., 121, 21-26, (2014)
[29] Zomorodian, A.; Carlsson, G. E., Computing persistent homology, Discrete Comput. Geom., 33, 2, 249-274, (2005) · Zbl 1069.55003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.