Persistent homology computation with a twist

The persistence diagram of a filtered simplicial complexis usually computed by reducing the boundarymatrix of the complex. We introduce a simple optimizationtechnique: by processing the simplices ofthe complex in decreasing dimension, we can "kill"columns (i.e., set them to zero) without reducingthem. This technique completely avoids reduction onroughly half of the columns. We demonstrate thatthis idea significantly improves the running time ofthe reduction algorithm in practice. We also give anoutput-sensitive complexity analysis for the new algorithmwhich yields to sub-cubic asymptotic boundsunder certain assumptions.