Reducing complexes in multidimensional persistent homology theory

DOI10.1016/J.JSC.2015.11.020zbMATH Open1382.55005arXiv1310.8089OpenAlexW151084626MaRDI QIDQ739614FDOQ739614

Authors: Madjid Allili, Tomasz Kaczynski, C. Landi 

Publication date: 18 August 2016

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: The Discrete Morse Theory of Forman appeared to be useful for providing filtration-preserving reductions of complexes in the study of persistent homology. So far, the algorithms computing discrete Morse matchings have only been used for one-dimensional filtrations. This paper is perhaps the first attempt in the direction of extending such algorithms to multidimensional filtrations. Initial framework related to Morse matchings for the multidimensional setting is proposed, and a matching algorithm given by King, Knudson, and Mramor is extended in this direction. The correctness of the algorithm is proved, and its complexity analyzed. The algorithm is used for establishing a reduction of a simplicial complex to a smaller but not necessarily optimal cellular complex. First experiments with filtrations of triangular meshes are presented.

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

Recommendations

• Morse theory for filtrations and efficient computation of persistent homology
• Acyclic partial matchings for multidimensional persistence: algorithm and combinatorial interpretation
• Discrete Morse theoretic algorithms for computing homology of complexes and maps
• Simplification of complexes for persistent homology computations
• Homological shape analysis through discrete Morse theory

zbMATH Keywords

discrete Morse theorymultidimensional persistent homologyacyclic partial matchingsmatching algorithm

Mathematics Subject Classification ID

Other homology theories in algebraic topology (55N35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Chain complexes in algebraic topology (55U15) Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc. (57Q10)

Cites Work

• Morse theory for cell complexes
• Computing persistent homology
• Topological persistence and simplification
• On the use of size functions for shape analysis
• Betti numbers in multidimensional persistent homology are stable functions
• Comparison of persistent homologies for vector functions: from continuous to discrete and back
• PERSISTENCE BARCODES FOR SHAPES
• One-dimensional reduction of multidimensional persistent homology
• Computational homology
• Topological sorting of large networks
• Title not available (Why is that?)
• Computing multidimensional persistence
• Morse theory for filtrations and efficient computation of persistent homology
• Coreduction homology algorithm
• Generating Discrete Morse Functions from Point Data
• Simplification of complexes for persistent homology computations
• A user's guide to discrete Morse theory
• Computing Optimal Morse Matchings
• Title not available (Why is that?)
• Homology computation by reduction of chain complexes
• A global method for reducing multidimensional size graphs

Cited In (16)

• Acyclic partial matchings for multidimensional persistence: algorithm and combinatorial interpretation
• Homological shape analysis through discrete Morse theory
• Computing multiparameter persistent homology through a discrete Morse-based approach
• Computing Homology: A Global Reduction Approach
• Discrete stratified Morse theory. Algorithms and a user's guide
• Morse theory for filtrations and efficient computation of persistent homology
• Relative-perfectness of discrete gradient vector fields and multi-parameter persistent homology
• Title not available (Why is that?)
• Multiparameter discrete Morse theory
• Discrete Stratified Morse Theory: Algorithms and A User's Guide
• Algorithmic construction of acyclic partial matchings for multidimensional persistence
• Combinatorial presentation of multidimensional persistent homology
• Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology
• Morse inequalities for the Koszul complex of multi-persistence
• Morse-based fibering of the persistence rank invariant
• Compression for \(2\)-parameter persistent homology

Uses Software

• GTS

This page was built for publication: Reducing complexes in multidimensional persistent homology theory

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