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

Abstract : Persistent homology with coefficients in a field coincides with the same for cohomology because of duality. We propose an implementation of a recently intro- duced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the represen- tation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the repre- sentation 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 :
Article dans une revue
Algorithmica, Springer Verlag, 2015, 73 (3), pp.607-619. <10.1007/s00453-015-9999-4>
Liste complète des métadonnées



https://hal.inria.fr/hal-01217111
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : mardi 25 octobre 2016 - 22:05:40
Dernière modification le : samedi 18 février 2017 - 01:14:44

Fichiers

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. Algorithmica, Springer Verlag, 2015, 73 (3), pp.607-619. <10.1007/s00453-015-9999-4>. <hal-01217111>

Partager

Métriques

Consultations de
la notice

211

Téléchargements du document

159