turkmath.org

Matrix reduction algorithm on a simplicial complex is a fairly new wave in persistent homology due to its implementations on programs like Ripser and many algorithms that have been built upon that. Persistent algorithm dates back to 2002 with a pairing algorithm and its runtime has been shown to be $O(N^3)$. Morozov in his 2005 article gives an explicit example of the existence of this case. In my talk, I will talk about the matrix reduction and how it is done, and explain why the example runs at $O(N^3)$ by combining the logic behind pairing and matrix algorithms. After that, I will also mention an alternative example and in which ways it improves the original example.