Persistent Homology and Nested Dissection
Presented at the 23rd Fall Workshop on Computational Geometry, New York City, October 2013.
Nested dissection exploits underlying topology to do matrix reductions while persistent homology exploits matrix reductions to reveal underlying topology. It seems natural that one should be able to combine these techniques to beat the currently best bound of matrix multiplication time for computing persistent homology. However, nested dissection works by fixing a reduction order, whereas persistent homology generally constrains the ordering. Despite this obstruction, we show that it is possible to combine these two theories. This shows that one can improve the computation of persistent homology of a filtration by exploiting information about the underlying space. It gives reasonable geometric conditions under which one can beat the matrix multiplication bound for persistent homology. This is a purely theoretical result, but it's a valuable one. We also give a topological view of nested dissection, which should be interesting to the wider theory community. For example, separators are covers, sparsification is simplification, asymmetric reduction is morse reduction, graph separators can be extended to complex separators.