inria-00520171, version 1
Zigzag Persistent Homology in Matrix Multiplication Time
N° RR-7393 (2010)
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.
- 1 :
- Max-Planck-Institut
- 2 :
- Stanford University
- 3 :
- INRIA
- Domaine : Informatique/Géométrie algorithmique
- Référence interne : RR-7393
- inria-00520171, version 1
- http://hal.inria.fr/inria-00520171
- oai:hal.inria.fr:inria-00520171
- Contributeur :
- Soumis le : Mercredi 22 Septembre 2010, 16:03:24
- Dernière modification le : Jeudi 23 Septembre 2010, 11:21:40
Documents associés
Exporter