Zigzag Persistent Homology in Matrix Multiplication Time - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2010

Zigzag Persistent Homology in Matrix Multiplication Time

(1) , (2) , (3)
1
2
3

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.
Nous présentons un algorithme pour calculer l'homologie persistante des zigzags, une structure algébrique qui code les changements survenant dans l'homologie d'un complexe simplicial lors d'une séquence d'insertions et de suppressions de simplexes. Sous l'hypothèse qu'il existe des algorithmes capables de multiplier deux matrices $n\times n$ en temps $M(n)$, notre algorithme tourne en temps $O(M(n))\log n$ si $M(n)=O(n^2)$ et $O(M(n))$ sinon, pour une séquence de n additions et suppressions. En particulier, le temps de calcul est $O(n^{2.376})$ par le résultat de Coppersmith et Winograd. L'algorithme le plus rapide connu jusqu'à présent pour ce problème prenait un temps $O(n^3)$ dans le cas le pire.
Fichier principal
Vignette du fichier
RR-7393.pdf (272.89 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00520171 , version 1 (22-09-2010)

Identifiers

  • HAL Id : inria-00520171 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More