The Compressed Annotation Matrix : an Efficient Data Structure for Computing Persistent Cohomology - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

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

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 935453
Clément Maria
  • Fonction : Auteur
  • PersonId : 926304
  • IdHAL : cmaria

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (204.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00923325 , version 1 (02-01-2014)

Identifiants

Citer

Jean-Daniel Boissonnat, Tamal K. Dey, Clément Maria. The Compressed Annotation Matrix : an Efficient Data Structure for Computing Persistent Cohomology. ESA - European Symposium on Algorithms - 2013, Sep 2013, Sophia Antipolis, France. pp.695-706, ⟨10.1007/978-3-642-40450-4_59⟩. ⟨hal-00923325⟩
214 Consultations
230 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More