PreprintarXiv licencearXiv
Updating zigzag representatives efficiently
Abstract
Computation of zigzag persistence has progressed in recent years, with results showing that complexities of many problems closely align with those in the non-zigzag setting. The major efficiency gap now lies in the updating of zigzag representatives. In this paper, we propose efficient algorithms for updating zigzag representatives based on a recent algorithm for extracting zigzag representatives from a R=DV decomposition of a constructed non-zigzag. The main difficulty for designing our update algorithms lies in the adjacency change occurring in two operations that lengthen or shorten a filtration. Despite the adjacency change, we find that the update can still be done efficiently in quadratic time.
Related
- Coset representatives corresponding to Yetter-Drinfeld modules of modular group and continued fraction
- Dihedral pointed fusion categories: diagrammatics, 3-cocycle representatives, and planar algebras
- Matrix Product State Representatives of Symmetry-Protected Phases
- Complex Representatives, Similarity Invariants, and Iterates in bfU(1,1;ℍ)
- Persistence probabilities of MA(1) sequences with Laplace innovations and q-deformed zigzag numbers
BibTeX
@misc{dey2026updating,
title = {{Updating zigzag representatives efficiently}},
author = {Tamal K. Dey and Tao Hou and Dmitriy Morozov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.16153},
eprint = {2607.16153},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.16153},
}
RIS
TY - UNPB
TI - Updating zigzag representatives efficiently
AU - Tamal K. Dey
AU - Tao Hou
AU - Dmitriy Morozov
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2607.16153
UR - https://arxiv.org/abs/2607.16153
AB - Computation of zigzag persistence has progressed in recent years, with results showing that complexities of many problems closely align with those in the non-zigzag setting. The major efficiency gap now lies in the updating of zigzag representatives. In this paper, we propose efficient algorithms for updating zigzag representatives based on a recent algorithm for extracting zigzag representatives from a R=DV decomposition of a constructed non-zigzag. The main difficulty for designing our update algorithms lies in the adjacency change occurring in two operations that lengthen or shorten a filtration. Despite the adjacency change, we find that the update can still be done efficiently in quadratic time.
ER -