Nested dissection exploits the underlying topology to do matrix reductions while persistent homology exploits matrix reductions to the 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 according to an input filtration. 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 if the underlying space has some additional structure. We give reasonable geometric conditions under which one can beat the matrix multiplication bound for persistent homology.

@inproceedings{kerber16persistent,
  Author = {Michael Kerber and Donald R. Sheehy and Primoz Skraba},
  Booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms},
  Title = {Persistent Homology and Nested Dissection},
  Pages = {1234--1245},
  Year = {2016}}