User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Zigzag Persistent Homology in Matrix Multiplication Time


Milosavljevic,  Nikola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Milosavljevic, N., Morozov, D., & Skraba, P. (2011). Zigzag Persistent Homology in Matrix Multiplication Time. In Proceedings of the 27th Annual Symposium on Computational Geometry (SCG'11) (pp. 216-225). New York, NY: ACM. doi:10.1145/1998196.1998229.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-12C6-B
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) + n^2 \log^2 n)$ time 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.