Analyzing multifiltering functions using multiparameter Discrete Morse Theory
DOI:
https://doi.org/10.12775/TMNA.2025.020Słowa kluczowe
Discrete Morse theory, multiparameter persistent homology, multifiltering functions, discrete gradient field, Pareto set, critical components, topological data analysisAbstrakt
A multiparameter filtration, or a multifiltration, may in many cases be seen as the collection of sublevel sets of a vector function, which we call a multifiltering function. The main objective of this paper is to obtain a better understanding of such functions through multiparameter discrete Morse (mdm) theory, which is an extension of Morse-Forman theory to vector-valued functions. Notably, we prove algorithmically that any multifiltering function defined on a simplicial complex can always be approximated by a compatible mdm function. Moreover, we define the Pareto set of a discrete multifiltering function and show that the concept links directly to that of critical simplices of a mdm function. Finally, we experiment with these notions using triangular meshes.Bibliografia
J. Ahrens, B. Geveci and C. Law, ParaView : An end-user tool for large-data visualization, Visualization Handbook, Elsevier, 2005, Chapter 36, pp. 717–731.
M. Allili, D. Corriveau, S. Derivière, T. Kaczynski and A. Trahan, Discrete dynamical system framework for construction of connections between critical regions in lattice height data, J. Math. Imaging Vision 28 (2007), 99–111.
M. Allili, T. Kaczynski and C. Landi, Reducing complexes in multidimensional persistent homology theory, J. Symbolic Comput. 78 (2017), 61–75.
M. Allili, T. Kaczynski, C. Landi and F. Masoni, Acyclic partial matchings for multidimensional persistence: Algorithm and combinatorial interpretation, J. Math. Imaging Vision 61 (2019), 174–192.
M. Assif P.K. and Y. Baryshnikov, Biparametric persistence for smooth filtrations, preprint, DOI: 10.48550/arXiv.2110.09602, 2021.
R. Ayala, D. Fernández-Ternero and J.A. Vilches, Perfect discrete Morse functions on 2-complexes, Pattern Recognit. Lett. 33 (2012), 1495–1500.
J.A. Barmak, Algebraic Topology of Finite Topological Spaces and Applications, Lecture Notes in Mathematics, vol. 2032, Springer, Berlin, Heidelberg, 2011.
B. Batko, T. Kaczynski, M. Mrozek and T. Wanner, Linking combinatorial and classical dynamics: Conley index and Morse decompositions, Found. Comput. Math. 20 (2020),967–1012.
U. Bauer, C. Lange and M. Wardetzky, Optimal topological simplification of discrete functions on surfaces, Discrete Comput. Geom. 47 (2012), 347–377.
U. Bauer and F. Roll, Wrapping cycles in Delaunay complexes: Bridging persistent homology and discrete Morse theory, 40th International Symposium on Computational Geometry (SoCG 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 239, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2024, pp. 15:1–15:16.
M. Bestvina, PL Morse theory, Math. Commun. 13 (2008), 149–162.
E.D. Bloch, Polyhedral representation of discrete Morse functions, Discrete Math. 313 (2013), 1342–1348.
M.B. Botnan and M. Lesnick, An introduction to multiparameter persistence, Representations of Algebras and Related Structures: International Conference on Representations of Algebras, ICRA 2020, 9–25 November 2020, EMS Series of Congress Reports, EMS Press, 2023, pp. 77–150.
G. Brouillette, M. Allili, and T. Kaczynski, Multiparameter discrete Morse theory, J. Appl. Comput. Topol. 8 (2024), 2155–2196.
R. Budney and T. Kaczynski, Bifiltrations and persistence paths for 2-Morse functions, Algebr. Geom. Topol. 23 (2023), 2895–2924.
F. Cagliari, B. Di Fabio and M. Ferri, One-dimensional reduction of multidimensional persistent homology, Proc. Amer. Math. Soc. 138 (2010), 3003–3017.
G. Carlsson, G. Singh and A.J. Zomorodian, Computing multidimensional persistence, J. Comput. Geom. 1 (2010), 72–100.
G. Carlsson and M. Vejdemo-Johansson, Topological Data Analysis with Applications, Cambridge University Press, 2021.
G. Carlsson and A. Zomorodian, The theory of multidimensional persistence, Discrete Comput. Geom. 42 (2009), 71–93.
A. Cerri, M. Ethier, and P. Frosini, On the geometrical properties of the coherent matching distance in 2D persistent homology, J. Appl. Comput. Topol., 3 (2019), pp. 381–422.
A. Cerri, P. Frosini, W.G. Kropatsch and C. Landi, A global method for reducing multidimensional size graphs, Graph-Based Representations in Pattern Recognition, Lecture Notes in Computer Science, vol. 6658, Springer, Berlin, Heidelberg, 2011, pp. 1–11.
M.M. Cohen, A Course in Simple-Homotopy Theory, Graduate Texts in Mathematics, vol. 10, Springer, New York, 1973.
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, The MIT Press, Cambridge, Massachusetts, fourth ed., 2022.
O. Delgado-Friedrichs, V. Robins and A. Sheppard, Skeletonization and partitioning of digital images using discrete Morse theory, IEEE Trans. Pattern Anal. Mach. Intell. 37 (2015), 654–666.
H. Edelsbrunner and J. Harer, Persistent homology — a survey, Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics, vol. 453, American Mathematical Society, 2008, pp. 257–282.
H. Edelsbrunner and J. Harer, Computational Topology: An Introduction, American Mathematical Society, 2010.
H. Edelsbrunner, J. Harer and A.K. Patel, Reeb spaces of piecewise linear mappings, SCG ’08: Proceedings of 24th Annual Symposium on Computational Geometry, Association for Computing Machinery, 2008, pp. 242–250.
H. Edelsbrunner, D. Letscher and A. Zomorodian, Topological persistence and simplification, Discrete Comput. Geom. 28 (2002), 511–533.
R. Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), 90–145.
U. Fugacci and M. Kerber, Chunk reduction for multi-parameter persistent homology, 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 129, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2019, pp. 37:1–37:14.
U. Fugacci, M. Kerber and A. Rolle, Compression for 2-parameter persistent homology, Comput. Geom. 109 (2023), p. 101940.
U. Fugacci, C. Landi, and H. Varlı, Critical sets of PL and discrete Morse theory: A correspondence, Comput. Graph. 90 (2020), 43–50.
R. Grunert, W. Kühnel and G.Rote, PL Morse theory in low dimensions, Adv. Geom. 23 (2023), 135–150.
A. Guidolin and C. Landi, Morse inequalities for the Koszul complex of multipersistence, J. Pure Appl. Algebra 227 (2023), p. 107319.
A. Gyulassy, D. Gunther, J.A. Levine, J. Tierny and V. Pascucci, Conforming Morse–Smale complexes, IEEE Trans. Vis. Comput. Graph. 20 (2014), 2595–2603.
A. Hatcher, Algebraic Topology, Cambridge University Press, 2002.
X. Hu, Y. Wang, L. Fuxin, D. Samaras and C. Chen, Topology-aware segmentation using discrete Morse theory, International Conference on Learning Representations, 2021.
L. Huettenberger, C. Heine, H. Carr, G. Scheuermann and C. Garth, Towards multifield scalar topology based on Pareto optimality, Comput. Graph. Forum 32 (2013), 341–350.
M. Joswig and M.E. Pfetsch, Computing optimal Morse matchings, SIAM J. Discrete Math. 20 (2006), 11–25.
T. Kaczynski, K. Mischaikow and M. Mrozek, Computational Homology, Applied Mathematical Sciences, vol. 157, Springer, New York, 2004.
T. Kaczynski, M. Mrozek and T. Wanner, Towards a formal tie between combinatorial and classical vector field dynamics, J. Comput. Dyn. 3 (2016), 17–50.
M. Kerber and A. Rolle, Fast minimal presentations of bi-graded persistence modules, 2021 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Society for Industrial and Applied Mathematics, 2021, pp. 207–220.
H. King, K. Knudson and N.M. Kosta, Birth and death in discrete Morse theory, J. Symbolic Comput. 78 (2017), 41–60.
H. King, K. Knudson and N. Mramor, Generating discrete Morse functions from point data, Exp. Math. 14 (2005), 435–444.
K.P. Knudson, Morse Theor y: Smooth and Discrete, World Scientific Publishing Company, 2015.
C. Landi and S. Scaramuccia, Relative-perfectness of discrete gradient vector fields and multi-parameter persistent homology, J. Comb. Optim. 44 (2022), 2347–2374.
J.M. Lee, Introduction to Smooth Manifolds, Graduate Texts in Mathematics, vol. 218, second ed., Springer, New York, 2012.
M. Lesnick and M. Wright, Computing minimal presentations and bigraded betti numbers of 2-parameter persistent homology, SIAM J. Appl. Algebra Geom. 6 (2022), 267–298.
T. Lewiner, Critical sets in discrete Morse theories: Relating Forman and piecewiselinear approaches, Comput. Aided Geom. Design 30 (2013), 609–621.
T. Lewiner, H. Lopes and G. Tavares, Optimal discrete Morse functions for 2-manifolds, Comput. Geom. 26 (2003), 221–233.
T. Lewiner, H. Lopes and G. Tavares, Toward optimality in discrete Morse theory, Exp. Math. 12 (2003), 271–285.
M. Lipiński, J. Kubica, M. Mrozek and T. Wanner, Conley–Morse–Forman theory for generalized combinatorial multivector fields on finite topological spaces, J. Appl. Comput. Topol. 7 (2023), 139–184.
D. Loiseaux, L. Scoccola, M. Carrière, M.B. Botnan and S. Oudot, Stable vectorization of multiparameter persistent homology using signed barcodes as measures, Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 68316–68342.
Y. Matsumoto, An Introduction to Morse Theory, Translations of Mathematical Monographs, vol. 208, American Mathematical Society, 2002.
M.C. McCord, Singular homology groups and homotopy groups of finite topological spaces, Duke Math. J. 33 (1966), 465–474.
K. Mischaikow and V. Nanda, Morse theory for filtrations and efficient computation of persistent homology, Discrete Comput. Geom. 50 (2013), 330–353.
L. Moresi and B. Mather, Stripy: A Python module for (constrained) triangulation in Cartesian coordinates and on a sphere , J. Open Source Software 4 (2019), p. 1410.
M. Mrozek, Conley–Morse–Forman theory for combinatorial multivector fields on Lefschetz complexes, Found. Comput. Math. 17 (2017), 1585–1633.
R. Peikert, H. Hauser, H. Carr and R. Fuchs (eds.). Topological Methods in Data Analysis and Visualization II: Theory, Algorithms, and Applications, Mathematics and Visualization, Springer, Berlin, Heidelberg, 2012.
S. Popinet, The GNU triangulated surface library, https://gts.sourceforge.net/samples.html, 2000.
V. Robins, P.J. Wood and A.P. Sheppard, Theory and algorithms for constructing discrete Morse complexes from grayscale digital images, IEEE Trans. Pattern Anal. Mach. Intell. 33 (2011), 1646–1658.
S. Scaramuccia, Computational and Theoretical Issues of Multiparameter Persistent Homology for Data Analysis, PhD thesis, Università di Genova, Italy, 2018.
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.
W. Schroeder, K. Martin and B. Lorensen, The Visualization Toolkit, 4th ed., Kitware, New York, 2006.
S. Smale, Global analysis and economics: Pareto optimum and a generalization of Morse theory, Synthese 31 (1975), 345–358.
R.E. Stong, Finite topological spaces, Trans. Amer. Math. Soc. 123 (1966), 325–340.
The GUDHI Project, GUDHI User and Reference Manual, GUDHI Editorial Board, 3.9.0 ed., 2023.
J. Tierny, Topological Data Analysis for Scientific Visualization, Mathematics and Visualization, Springer International Publishing, 2017.
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.
Y.-H. Wan, Morse theory for two functions, Topology 14 (1975), 217–228.
K. Xia and G.-W. Wei, Multidimensional persistence in biomolecular data, J. Comput. Chem. 36 (2015), 1502–1520.
Pobrania
Opublikowane
Jak cytować
Numer
Dział
Statystyki
Liczba wyświetleń i pobrań: 0
Liczba cytowań: 0
