The compressed annotation matrix: an efficient data structure for computing persistent cohomology

DOI10.1007/978-3-642-40450-4_59zbMATH Open1330.68050arXiv1304.6813OpenAlexW2155796097MaRDI QIDQ893322FDOQ893322

Jean-Daniel Boissonnat, Clément Maria, Tamal K. Dey

Publication date: 19 November 2015

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: The persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose heuristics to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

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

Recommendations

• The compressed annotation matrix: an efficient data structure for computing persistent cohomology
• Computing persistent homology with various coefficient fields in a single pass
• Computing persistent homology with various coefficient fields in a single pass
• Dualities in persistent (co)homology
• Computing persistent homology

zbMATH Keywords

algorithmdata structuresimplicial compleximplementationpersistent cohomologyannotation

Mathematics Subject Classification ID

Other homology theories in algebraic topology (55N35) Data structures (68P05) Simplicial sets and complexes in algebraic topology (55U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• The Gudhi Library: Simplicial Complexes and Persistent Homology
• Computational topology. An introduction
• Stability of persistence diagrams
• The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
• Computing persistent homology
• Topological persistence and simplification
• An output-sensitive algorithm for persistent homology
• Dualities in persistent (co)homology
• Zigzag persistent homology in matrix multiplication time
• Persistent cohomology and circular coordinates
• Clear and Compress: Computing Persistent Homology in Chunks
• Computing Topological Persistence for Simplicial Maps
• PHAT – Persistent Homology Algorithms Toolbox
• Annotating Simplices with a Homology Basis and Its Applications

Cited In (13)

• Barcodes of towers and a streaming algorithm for persistent homology
• A heuristic for short homology basis of digital objects
• Computing multiparameter persistent homology through a discrete Morse-based approach
• Persistent homology for low-complexity models
• Discrete Morse theory for computing zigzag persistence
• Persistent Cohomology for Data With Multicomponent Heterogeneous Information
• SimBa
• Computing persistent homology with various coefficient fields in a single pass
• Homological Shape Analysis Through Discrete Morse Theory
• \textsc{Phat} -- persistent homology algorithms toolbox
• The Offset Filtration of Convex Objects
• The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
• Compression for \(2\)-parameter persistent homology

Uses Software

• Gudhi
• PHAT
• Dionysus

This page was built for publication: The compressed annotation matrix: an efficient data structure for computing persistent cohomology

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