非表示:
キーワード:
-
要旨:
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.
