Persistent homology computation with a twist

C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published | English
Department
Abstract
The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.
Publishing Year
Date Published
2011-01-01
Page
197 - 200
Conference
EuroCG: European Workshop on Computational Geometry
Conference Location
Morschach, Switzerland
Conference Date
2011-03-28 – 2011-03-30
IST-REx-ID

Cite this

Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund; 2011:197-200.
Chen, C., & Kerber, M. (2011). Persistent homology computation with a twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland: TU Dortmund.
Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a Twist,” 197–200. TU Dortmund, 2011.
C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland, 2011, pp. 197–200.
Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG: European Workshop on Computational Geometry 197–200.
Chen, Chao, and Michael Kerber. Persistent Homology Computation with a Twist. TU Dortmund, 2011, pp. 197–200.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar