C. Chen, M. Kerber:

"Persistent homology computation with a twist";

Talk: 27th European Workshop on Computational Geometry (EuroCG 2011), Morschach, Schweiz; 2011-03-20 - 2011-03-30; in: "27th European Workshop on Computational Geometry (EuroCG 2011)", (2011), 1 - 4.

The persistence diagram of a filtered simplicial complex

is usually computed by reducing the boundary

matrix of the complex. We introduce a simple optimization

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 algorithm

which yields to sub-cubic asymptotic bounds

under certain assumptions.

Created from the Publication Database of the Vienna University of Technology.