Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology. (English) Zbl 1498.55006

Lesnick, Michael; Wright, Matthew

SIAM J. Appl. Algebra Geom. 6, No. 2, 267-298 (2022).

Suppose that \(M\) is a bigraded persistence module over the field \(K\). That is, \(M\) is a direct sum of \(K\)-vector spaces \(M_{\mathbf{z}}\) indexed by pairs of integers \(\mathbf{z}=(z_1,z_2)\), and is equipped with a \(K[x_1,x_2]\)-module structure such that \(x_1^ix_2^jM_{(z_1,z_2)}\) lies in \(M_{(z_1+i,z_2+j)}\). Let \(I\!M\) denote the submodule generated by elements of the form \(pm\), where \(p\) is a monomial of positive degree and \(m\) is in \(M\). Given a left resolution \(\cdots\xrightarrow{\partial_3}F_2\xrightarrow{\partial_2}F_1\xrightarrow{\partial_1}F_0 \rightarrow M\rightarrow 0 \) by free bigraded persistence modules such that the image of \(\partial_i\) is contained in \(I\!F_{i-1}\), the \(i\)-th bigraded Betti number \(\beta_i(\mathbf{z})\) of \(M\) at grade \(\mathbf{z}\) is taken to be the \(K\)-vector space dimension of \((F_i/I\!F_i)_{\mathbf{z}}\). In the case when there is a chain complex \(X\xrightarrow{f}Y\xrightarrow{g}Z\) of free bigraded persistence modules with \(M=\ker\,g/\mathrm{im}\,f\), the authors of the article provide an algorithm for computing the \(0\)-th and \(1\)-st bigraded Betti numbers of \(M\). Correctness of the algorithm is shown, and spacial and computational efficiency analyses are given. Numerical experiments performed indicate that the algorithm significantly outperforms standard methods.

Reviewer: Jason Hanson (Redmond)

MSC:

55N31	Persistent homology and applications, topological data analysis
13D02	Syzygies, resolutions, complexes and commutative rings

Keywords:

minimal presentations; multiparameter persistent homology; topological data analysis

Software:

Magma; Eirene; RIVET; Ripser; GitHub; Macaulay2; PHAT; CoCoA; SINGULAR; rhomboidtiling; orderkdelaunay

References:

[1]	J. Abbott, A. M. Bigatti, and L. Robbiano, CoCoA: A System for Doing Computations in Commutative Algebra, http://cocoa.dima.unige.it.
[2]	M. Allili, T. Kaczynski, and C. Landi, Reducing complexes in multidimensional persistent homology theory, J. Symbolic Comput., 78 (2017), pp. 61-75. · Zbl 1382.55005
[3]	U. Bauer, Ripser: A Lean C++ Code for the Computation of Vietoris-Rips Persistence Barcodes, https://github.com/Ripser/ripser, 2016-2018.
[4]	U. Bauer, Ripser: Efficient computation of Vietoris-Rips persistence barcodes, J. Appl. Comput. Topol., 5 (2021), pp. 391-423. · Zbl 1476.55012
[5]	U. Bauer, M. Kerber, and J. Reininghaus, Distributed computation of persistent homology, in 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), SIAM, Philadelphia, 2014, pp. 31-38, https://doi.org/10.1137/1.9781611973198.4. · Zbl 1429.68328
[6]	U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, PHAT-persistent homology algorithms toolbox, J. Symbolic Comput., 78 (2017), pp. 76-90. · Zbl 1348.68181
[7]	D. Bayer and D. Mumford, What can be computed in algebraic geometry?, in Computational Algebraic Geometry and Commutative Algebra, Cambridge University Press, Cambridge, UK, 1993, pp. 1-48. · Zbl 0846.13017
[8]	S. Biasotti, A. Cerri, P. Frosini, and D. Giorgi, A new algorithm for computing the 2-dimensional matching distance between size functions, Pattern Recognition Lett., 32 (2011), pp. 1735-1746.
[9]	H. B. Bjerkevik and M. B. Botnan, Computational complexity of the interleaving distance, in Proceedings of the 34th International Symposium on Computational Geometry (SoCG), 2018, https://doi.org/10.4230/LIPIcs.SoCG.2018.13. · Zbl 1489.68103
[10]	H. B. Bjerkevik, M. B. Botnan, and M. Kerber, Computing the interleaving distance is NP-hard, Found. Comput. Math., 20 (2020), pp. 1237-1271, https://doi.org/10.1007/s10208-019-09442-y. · Zbl 1460.55006
[11]	H. B. Bjerkevik and M. Kerber, Asymptotic Improvements on the Exact Matching Distance for 2-Parameter Persistence, preprint, https://arxiv.org/abs/2111.10303, 2021.
[12]	A. J. Blumberg and M. Lesnick, Stability of 2-Parameter Persistent Homology, preprint, https://arxiv.org/abs/2010.09628, 2020.
[13]	J.-D. Boissonnat, F. Chazal, and M. Yvinec, Geometric and Topological Inference, Cambridge Texts Appl. Math. 57, Cambridge University Press, Cambridge, UK, 2018. · Zbl 1457.62006
[14]	W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), pp. 235-265, https://doi.org/10.1006/jsco.1996.0125. · Zbl 0898.68039
[15]	M. Botnan and M. Lesnick, Algebraic stability of zigzag persistence modules, Algebr. Geom. Topol., 18 (2018), pp. 3133-3204. · Zbl 1432.55011
[16]	G. Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.), 46 (2009), pp. 255-308. · Zbl 1172.62002
[17]	G. Carlsson, G. Singh, and A. J. Zomorodian, Computing multidimensional persistence, J. Comput. Geom., 1 (2010), pp. 72-100. · Zbl 1374.68649
[18]	G. Carlsson and A. Zomorodian, The theory of multidimensional persistence, Discrete Comput. Geom., 42 (2009), pp. 71-93. · Zbl 1187.55004
[19]	A. Cerri, B. Di Fabio, M. Ferri, P. Frosini, and C. Landi, Betti numbers in multidimensional persistent homology are stable functions, Math. Methods Appl. Sci., 36 (2013), pp. 1543-1557. · Zbl 1278.55012
[20]	W. Chacholski, M. Scolamiero, and F. Vaccarino, Combinatorial presentation of multidimensional persistent homology, J. Pure Appl. Algebra, 221 (2017), pp. 1055-1075. · Zbl 1373.55027
[21]	C. Chen and M. Kerber, Persistent homology computation with a twist, in Proceedings of the 27th European Workshop on Computational Geometry, Vol. 11, 2011, pp. 197-200.
[22]	J. Cochoy and S. Oudot, Decomposition of exact PFD persistence bimodules, Discrete Comput. Geom., 63 (2020), pp. 255-293, https://doi.org/10.1007/s00454-019-00165-z. · Zbl 1435.62453
[23]	R. Corbet, M. Kerber, M. Lesnick, and G. Osang, Computing the multicover bifiltration, in Proceedings of the 37th International Symposium on Computational Geometry (SoCG), LIPIcs. Leibniz Int. Proc. Inform. 189, K. Buchin and E. Colin de Verdière, eds., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2021, art. 7, https://doi.org/10.4230/LIPIcs.SoCG.2021.27.
[24]	D. Cox, J. Little, and D. O’Shea, Using Algebraic Geometry, Grad. Texts in Math. 185, Springer-Verlag, New York, 1998. · Zbl 0920.13026
[25]	V. De Silva, D. Morozov, and M. Vejdemo-Johansson, Dualities in persistent (co) homology, Inverse Problems, 27 (2011), 124003. · Zbl 1247.68307
[26]	T. K. Dey and C. Xin, Computing bottleneck distance for \(2\)-D interval decomposable modules, in Proceedings of the 34th International Symposium on Computational Geometry (SoCG), 2018, https://doi.org/10.4230/LIPIcs.SoCG.2018.32. · Zbl 1492.55005
[27]	H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010. · Zbl 1193.55001
[28]	H. Edelsbrunner and G. Osang, The multi-cover persistence of Euclidean balls, in Proceedings of the 34th International Symposium on Computational Geometry (SoCG), 2018, https://doi.org/10.4230/LIPIcs.SoCG.2018.34. · Zbl 1493.55003
[29]	H. Edelsbrunner and G. Osang, A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes, preprint, https://arxiv.org/abs/2011.03617, 2020.
[30]	D. Eisenbud, Commutative Algebra: With a View Toward Algebraic Geometry, Grad. Texts in Math. 150, Springer, New York, 1995. · Zbl 0819.13001
[31]	D. Eisenbud, The Geometry of Syzygies: A Second Course in Algebraic Geometry and Commutative Algebra, Grad. Texts in Math. 229, Springer, New York, 2005. · Zbl 1066.14001
[32]	D. Eisenbud, D. R. Grayson, M. Stillman, and B. Sturmfels, Computations in Algebraic Geometry with Macaulay 2, Algorithms Comput. Math. 8, Springer, New York, 2001. · Zbl 0973.00017
[33]	B. Eröcal, O. Motsak, F.-O. Schreyer, and A. Steenpaß, Refined algorithms to compute syzygies, J. Symbolic Comput., 74 (2016), pp. 308-327. · Zbl 1405.14138
[34]	J. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero \((F_5)\), in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, 2002, pp. 75-83. · Zbl 1072.68664
[35]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases \((F_4)\), J. Pure Appl. Algebra, 139 (1999), pp. 61-88. · Zbl 0930.68174
[36]	U. Fugacci and M. Kerber, Chunk reduction for multi-parameter persistent homology, in Proceedings of the 35th International Symposium on Computational Geometry (SoCG), LIPIcs. Leibniz Int. Proc. Inform. 129, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2019, art. 37, https://doi.org/10.4230/LIPIcs.SoCG.2019.37.
[37]	G.-M. Greuel and G. Pfister, A Singular Introduction to Commutative Algebra, Springer, New York, 2012.
[38]	H. A. Harrington, N. Otter, H. Schenck, and U. Tillmann, Stratifying multiparameter persistent homology, SIAM J. Appl. Algebra Geom., 3 (2019), pp. 439-471, https://doi.org/10.1137/18M1224350. · Zbl 1450.55002
[39]	G. Henselman and R. Ghrist, Matroid Filtrations and Computational Persistent Homology, preprint, https://arxiv.org/abs/1606.00199, 2016.
[40]	A. Hylton, G. Henselman-Petrusek, J. Sang, and R. Short, Performance enhancement of a computational persistent homology package, in Proceedings of the 36th International IEEE Performance Computing and Communications Conference (IPCCC), 2017, pp. 1-8.
[41]	B. Keller, M. Lesnick, and T. L. Willke, Persistent Homology for Virtual Screening, ChemRxiv, 2018.
[42]	M. Kerber, M. Lesnick, and S. Oudot, Exact computation of the matching distance on 2-parameter persistence modules, in Proceedings of the 35th International Symposium on Computational Geometry (SoCG ), LIPIcs. Leibniz Int. Proc. Inform. 129, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2019, art. 46, https://doi.org/10.4230/LIPIcs.SoCG.2019.46. · Zbl 1476.55016
[43]	M. Kerber and A. Nigmetov, Efficient approximation of the matching distance for \(2\)-parameter persistence, in Proceedings of the 36th International Symposium on Computational Geometry (SoCG), LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2020, art. 53. · Zbl 1430.68376
[44]	M. Kerber and A. Rolle, Fast minimal presentations of bi-graded persistence modules, in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, Philadelphia, 2021, pp. 207-220, https://doi.org/10.1137/1.9781611976472.16. · Zbl 07302448
[45]	W. Kim and F. Mémoli, Spatiotemporal persistent homology for dynamic metric spaces, Discrete Comput. Geom., 66 (2021), pp. 831-875. · Zbl 1480.55007
[46]	R. La Scala and M. Stillman, Strategies for computing minimal free resolutions, J. Symbolic Comput., 26 (1998), pp. 409-431. · Zbl 1034.68716
[47]	M. Lesnick and M. Wright, Interactive Visualization of \(2\)-D Persistence Modules, preprint, https://arxiv.org/abs/1512.00180, 2015.
[48]	E. Miller, Homological Algebra of Modules over Posets, preprint, https://arxiv.org/abs/2008.00063, 2020.
[49]	E. Miller and B. Sturmfels, Combinatorial Commutative Algebra, Springer-Verlag, New York, 2005. · Zbl 1090.13001
[50]	N. Otter, PH-Roadmap, Github Repository, https://github.com/n-otter/PH-roadmap.
[51]	N. Otter, M. A. Porter, U. Tillmann, P. Grindrod, and H. A. Harrington, A roadmap for the computation of persistent homology, EPJ Data Science, 6 (2017), art. 17.
[52]	S. Y. Oudot, Persistence Theory: From Quiver Representations to Data Analysis, Math. Surveys Monogr. 209, American Mathematical Society, Providence, RI, 2015. · Zbl 1335.55001
[53]	I. Peeva, Graded Syzygies, Springer-Verlag, London, 2011. · Zbl 1213.13002
[54]	S. Scaramuccia, F. Iuricich, L. De Floriani, and C. Landi, Computing multiparameter persistent homology through a discrete Morse-based approach, Comput. Geom., 89 (2020), 101623, https://doi.org/10.1016/j.comgeo.2020.101623. · Zbl 1479.55014
[55]	Y. Schiff, P. Das, V. Chenthamarakshan, and K. N. Ramamurthy, Characterizing the latent space of molecular deep generative models with persistent homology metrics, in NeurIPS Workshop on Topological Data Analysis and Beyond, 2020.
[56]	F.-O. Schreyer, Die berechnung von syzygien mit dem verallgemeinerten weierstraßschen divisionssatz und eine anwendung auf analytische Cohen-Macaulay stellenalgebren minimaler multiplizität, Ph.D. thesis, 1980.
[57]	D. R. Sheehy, A multicover nerve for geometric inference, in Proceedings of the Canadian Conference in Computational Geometry (CCCG), 2012.
[58]	D. Singmaster, Notes on binomial coefficients III-any integer divides almost all binomial coefficients, J. London Math. Soc. (2), 8 (1974), pp. 555-560. · Zbl 0293.05007
[59]	J. Skryzalin, Numeric Invariants from Multidimensional Persistence, Ph.D. dissertation, Stanford University, Stanford, CA, 2016. · Zbl 1439.55007
[60]	The RIVET Developers, RIVET: Software for Visualization and Analysis of \(2\)-Parameter Persistent Homology, https://github.com/rivetTDA/, 2016-2020.
[61]	O. Vipond, Multiparameter persistence landscapes, J. Mach. Learn. Res., 21 (2020), art. 61. · Zbl 1505.55015
[62]	O. Vipond, J. A. Bull, P. S. Macklin, U. Tillmann, C. W. Pugh, H. M. Byrne, and H. A. Harrington, Multiparameter persistent homology landscapes identify immune cell spatial patterns in tumors, Proc. Natl. Acad. Sci. USA, 118 (2021), e2102166118.
[63]	L. Wasserman, Topological data analysis, Annu. Rev. Stat. Appl., 5 (2018), pp. 501-535.
[64]	M. Wright and X. Zheng, Topological data analysis on simple English Wikipedia articles, PUMP J. Undergrad. Res., 3 (2020), pp. 308-328. · Zbl 1465.62192
[65]	A. Zomorodian and G. Carlsson, Computing persistent homology, Discrete Comput. Geom., 33 (2005), pp. 249-274. · Zbl 1069.55003