Skip to Main content Skip to Navigation
Reports

Zigzag Persistent Homology in Matrix Multiplication Time

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
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

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

Collections

Citation

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

Share

Metrics

Record views

556

Files downloads

743