Generalized persistence algorithm for decomposing multiparameter persistence modules (Q2082448)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalized persistence algorithm for decomposing multiparameter persistence modules |
scientific article |
Statements
Generalized persistence algorithm for decomposing multiparameter persistence modules (English)
0 references
4 October 2022
0 references
It is well-known that there is no complete discrete invariant for multiparameter persistence modules [\textit{G. Carlsson} and \textit{A. Zomorodian}, Discrete Comput. Geom. 42, No. 1, 71--93 (2009; Zbl 1187.55004)], unlike what we have in the 1-dimensional case. Still, applications in Topological Data Analysis need meaningful (and fast enough computable) ``fingerprints'' also in multiparameter persistence: this is the goal of the present paper. The environment is strictly algebraic, but the attention is often directed on the typical case of persistent homology of a filtered simplicial complex, as in the simple but significant examples that accompany the exposition. The proposed algorithm yields a \textit{total decomposition} of a persistence module \(M\) indexed by grades, i.e. \(d\)-tuples of integers. The graded module \(M\) is provided as a presentation matrix, with the condition that no two generators and no two relators correspond to the same grade. This limitation is carefully discussed by the authors: if the condition is not satisfied, the algorithm yields a decomposition of an arbitrarily small perturbation of the original module. The keystone of the algorithm is Theorem 1, stating that there is a 1-1 correspondence between decompositions of the persistence module, of the presentation map, and of the presentation matrix, when the given presentation is minimal. In applications of the classical, 1-parameter persistence, the main tools are persistence diagrams [\textit{H. Edelsbrunner} et al., Discrete Comput. Geom. 28, No. 4, 511--533 (2002; Zbl 1011.68152)] or barcodes [\textit{G. Carlsson} et al., Int. J. Shape Model. 11, No. 2, 149--187 (2005; Zbl 1092.68688)]. The paper provides a multi-dimensional analogue of persistence diagrams, called \textit{persistent graded Betti numbers}, i.e. the multisets of the grades of homogeneous basis elements for the modules in a minimal free resolution of \(M\). The dimension function yields a generalization of a barcode, called \textit{blockcode}. The authors dutifully specify that neither is sufficient for classifying multiparameter persistence modules. The strong point of the paper is time complexity: \(O(n^{(d-1)(2\omega +1)})\), where \(n\) is the number of simplices of the filtered complex under study, \(d \ge 2\) is the number of filtration parameters, \(\omega<2.373\) is the exponent in the complexity of matrix multiplication. There is a comparison with the more general but slower Meataxe algorithm [\textit{D.F. Holt}, Lond. Math. Soc. Lect. Note Ser. 249, 74--81 (1998; Zbl 0915.20005)].
0 references
multiparameter persistence
0 references
computational topology
0 references
topological data analysis
0 references
persistence module
0 references
indecomposables
0 references
matrix reduction
0 references
presentations
0 references
0 references
0 references
0 references
0 references