[Back]

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.