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

Boissonnat, Jean-Daniel, Dey, Tamal K. and Maria, Clement (2013). The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology. In: Algorithms - Esa 2013. 21st Annual European Symposium on Algorithms (ESA), Sophia Antipolis, France, (695-706). 02 - 04 September 2013. doi:10.1007/978-3-642-40450-4_59


Author Boissonnat, Jean-Daniel
Dey, Tamal K.
Maria, Clement
Title of paper The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
Conference name 21st Annual European Symposium on Algorithms (ESA)
Conference location Sophia Antipolis, France
Conference dates 02 - 04 September 2013
Proceedings title Algorithms - Esa 2013   Check publisher's open access policy
Series Lecture Notes in Computer Science
Place of Publication Berlin / Heidelberg, Germany
Publisher Springer
Publication Year 2013
Year available 2013
Sub-type Fully published paper
DOI 10.1007/978-3-642-40450-4_59
Open Access Status
ISBN 9783642404498
9783642404504
ISSN 0302-9743
Volume 8125
Start page 695
End page 706
Total pages 12
Chapter number 59
Total chapters 69
Collection year 2013
Language eng
Formatted Abstract/Summary
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.
Keyword Homology
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Conference Paper
Collection: Centre for Integrative Legume Research Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 2 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 16 Feb 2015, 10:48:54 EST by Clement Maria on behalf of Centre for Integrative Legume Research