Zigzag Persistent Homology in Matrix Multiplication Time

Résumé : 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.
Type de document :
Rapport
[Research Report] RR-7393, INRIA. 2010
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520171
Contributeur : Primoz Skraba <>
Soumis le : mercredi 22 septembre 2010 - 16:03:24
Dernière modification le : samedi 27 janvier 2018 - 01:30:50
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 11:15:43

Fichier

RR-7393.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

469

Téléchargements de fichiers

460