Zigzag Persistent Homology in Matrix Multiplication Time
Résumé
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.
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...