TDA II: Matrix Reduction Algorithm and Morozov's Worst Case Example

Abstract: 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.

Part II of a sequence on Topological Data Analysis (TDA).

algebraic topologycategory theory

Audience: researchers in the topic

Bilkent Topology Seminar

Series comments: Contact the organizer to get access to Zoom.

Recordings of talks available at www.youtube.com/channel/UCLrmyGpqxyeVpTcA1b5HcMw/videos