Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology

DOI10.1137/20M1388425MaRDI QIDQ5864696zbMATH OpenOpenAlexFDO

Authors

Publication date 8 June 2022

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.05708

zbMATH Keywords

minimal presentationsmultiparameter persistent homologytopological data analysis

Mathematics Subject Classification ID

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

Abstract: Motivated by applications to topological data analysis, we give an efficient algorithm for computing a (minimal) presentation of a bigraded $K[x,y]$-module $M$, where $K$ is a field. The algorithm takes as input a short chain complex of free modules $XxrightarrowfYxrightarrowgZ$ such that $Mcongkerg/mathrmimf$. It runs in time $O(|X{|}^3+|Y{|}^3+|Z{|}^3)$ and requires $O(|X{|}^2+|Y{|}^2+|Z{|}^2)$ memory, where $|cdot|$ denotes the rank. Given the presentation computed by our algorithm, the bigraded Betti numbers of $M$ are readily computed. Our approach is based on a simple matrix reduction algorithm, slight variants of which compute kernels of morphisms between free modules, minimal generating sets, and Gr"obner bases. Our algorithm for computing minimal presentations has been implemented in RIVET, a software tool for the visualization and analysis of two-parameter persistent homology. In experiments on topological data analysis problems, our implementation outperforms the standard computational commutative algebra packages Singular and Macaulay2 by a wide margin.

Recommendations

• Compression for \(2\)-parameter persistent homology
• Generalized persistence algorithm for decomposing multiparameter persistence modules
• Computing persistent homology
• Value-offset bifiltrations for digital images
• Exact computation of the matching distance on 2-parameter persistence modules

Cites work

• \textsc{Phat} -- persistent homology algorithms toolbox
• A new efficient algorithm for computing Gröbner bases (F₄)
• Algebraic stability of zigzag persistence modules
• Betti numbers in multidimensional persistent homology are stable functions
• Combinatorial presentation of multidimensional persistent homology
• Computational complexity of the interleaving distance
• Computational topology. An introduction
• Computations in algebraic geometry with Macaulay 2
• Computing bottleneck distance for 2-D interval decomposable modules
• Computing multidimensional persistence
• Computing multiparameter persistent homology through a discrete Morse-based approach
• Computing persistent homology
• Computing the interleaving distance is NP-hard
• Decomposition of exact pfd persistence bimodules
• Distributed computation of persistent homology
• Dualities in persistent (co)homology
• Exact computation of the matching distance on 2-parameter persistence modules
• Fast Minimal Presentations of Bi-graded Persistence Modules
• Geometric and topological inference
• Geometry Helps to Compare Persistence Diagrams
• Graded syzygies
• scientific article; zbMATH DE number 1206418 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• scientific article; zbMATH DE number 7559237 (Why is no real title available?)
• scientific article; zbMATH DE number 2190625 (Why is no real title available?)
• Multiparameter Persistence Landscapes
• Notes on Binomial Coefficients Iii-Any Integer Divides Almost All Binomial Coefficients†
• Numeric invariants from multidimensional persistence
• Persistence theory. From quiver representations to data analysis
• Reducing complexes in multidimensional persistent homology theory
• Refined algorithms to compute syzygies
• Ripser: efficient computation of Vietoris-Rips persistence barcodes
• Spatiotemporal persistent homology for dynamic metric spaces
• Strategies for computing minimal free resolutions
• Stratifying multiparameter persistent homology
• The Geometry of Syzygies
• The Magma algebra system. I: The user language
• The multi-cover persistence of Euclidean balls
• The theory of multidimensional persistence
• Topological data analysis on simple English Wikipedia articles
• Topology and data
• What can be computed in algebraic geometry?

Cited in

(24)

• Morse-based fibering of the persistence rank invariant
• Generalized persistence algorithm for decomposing multiparameter persistence modules
• Compression for \(2\)-parameter persistent homology
• Topological data analysis for the string landscape
• Morse inequalities for the Koszul complex of multi-persistence
• Realizations of indecomposable persistence modules of arbitrarily large dimension
• The multi-cover persistence of Euclidean balls
• A density-based approach to feature detection in persistence diagrams for firn data
• Computing the multicover bifiltration
• Persistence and the Sheaf-Function Correspondence
• On the Stability of Multigraded Betti Numbers and Hilbert Functions
• The shift-dimension of multipersistence modules
• Bigraded Betti numbers and generalized persistence diagrams
• Analyzing multifiltering functions using multiparameter discrete Morse theory
• Multi-parameter module approximation: an efficient and interpretable invariant for multi-parameter persistence modules with guarantees
• Probabilistic analysis of multiparameter persistence decompositions into intervals
• On minimal flat-injective presentations over local graded rings
• On the support of Betti tables of multiparameter persistent homology modules
• Multi-parameter persistence modules are generically indecomposable
• Koszul complexes and relative homological algebra of functors over posets
• Relative Koszul coresolutions and relative Betti numbers
• Decomposing multiparameter persistence modules
• Computing Betti tables and minimal presentations of zero-dimensional persistent homology
• Estimating the persistent homology of \(\mathbb{R}^n\)-valued functions using function-geometric multifiltrations

Describes a project that uses

Uses Software

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

This page was built for publication: Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864696)