English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Zigzag Persistent Homology in Matrix Multiplication Time

MPS-Authors
/persons/resource/persons45051

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
Citation

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
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) + 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.