conference paper
Persistent homology computation with a twist
published
yes
Chao
Chen
author 3E92416E-F248-11E8-B48F-1D18A9856A87
Michael
Kerber
author 36E4574A-F248-11E8-B48F-1D18A9856A870000-0002-8030-9299
HeEd
department
EuroCG: European Workshop on Computational Geometry
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.
TU Dortmund2011Morschach, Switzerland
eng
197 - 200
C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.
Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG: European Workshop on Computational Geometry 197–200.
Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund; 2011:197-200.
Chen, Chao, and Michael Kerber. <i>Persistent Homology Computation with a Twist</i>. TU Dortmund, 2011, pp. 197–200.
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, Chao, and Michael Kerber. “Persistent Homology Computation with a Twist,” 197–200. TU Dortmund, 2011.
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.
32702018-12-11T12:02:22Z2019-08-02T12:38:07Z