# Zigzag Persistent Homology in Matrix Multiplication Time

3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We present a new algorithm for computing zigzag persistent homology, an algebraic structure which encodes changes to homology groups of a simplicial complex over a sequence of simplex additions and deletions. Provided that there is an algorithm that multiplies two $n\times n$ matrices in $M(n)$ time, our algorithm runs in $O(M(n) log n)$ time if $M(n) = O(n^2)$, and $O(M(n))$ time otherwise, for a sequence of n additions and deletions. In particular, the running time is $O(n^2.376)$, by result of Coppersmith and Winograd. The fastest previously known algorithm for this problem takes $O(n^3)$ time in the worst case.
Document type :
Reports

Cited literature [23 references]

https://hal.inria.fr/inria-00520171
Contributor : Primoz Skraba <>
Submitted on : Wednesday, September 22, 2010 - 4:03:24 PM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: : Thursday, October 25, 2012 - 11:15:43 AM

### File

RR-7393.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00520171, version 1

### Citation

Nikola Milosavljevic, Dmitriy Morozov, Primoz Skraba. Zigzag Persistent Homology in Matrix Multiplication Time. [Research Report] RR-7393, INRIA. 2010. ⟨inria-00520171⟩

Record views