The Compressed Annotation Matrix : an Efficient Data Structure for Computing Persistent Cohomology

Jean-Daniel Boissonnat 1 Tamal K. Dey 2 Clément Maria 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : 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 a heuristic 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.
Type de document :
Communication dans un congrès
Hans L. Bodlaender and Giuseppe F. Italiano. ESA - European Symposium on Algorithms - 2013, Sep 2013, Sophia Antipolis, France. Springer, 8125, pp.695-706, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-40450-4_59〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00923325
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : jeudi 2 janvier 2014 - 13:49:06
Dernière modification le : samedi 27 janvier 2018 - 01:31:27
Document(s) archivé(s) le : samedi 8 avril 2017 - 10:01:29

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, Tamal K. Dey, Clément Maria. The Compressed Annotation Matrix : an Efficient Data Structure for Computing Persistent Cohomology. Hans L. Bodlaender and Giuseppe F. Italiano. ESA - European Symposium on Algorithms - 2013, Sep 2013, Sophia Antipolis, France. Springer, 8125, pp.695-706, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-40450-4_59〉. 〈hal-00923325〉

Partager

Métriques

Consultations de la notice

414

Téléchargements de fichiers

400