Nested dissection is a way of solving systems of linear equations by divide and conquer. For many linear systems that occur naturally in many settings, nested dissection gives a guaranteed improvement over naive Gaussian elimination. These are the so-called beta-separable systems, where beta is a constant that governs how big the improvement will be. In this talk, I will give some historical background, going back to Strassen's fast matrix multiplication algorithm. Then, I will show how one might apply this technique to computing persistent homology. Moreover, I will show that for a wide class of inputs that come up in persistent homology, the resulting systems are beta-separable, yielding an improvement in the asymptotic running time of the persistence algorithm.

This is joint work with Primoz Skraba and Michael Kerber.