de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Zigzag Persistent Homology in Matrix Multiplication Time

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45051

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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.