pith. sign in

arxiv: 2410.20565 · v2 · submitted 2024-10-27 · 💻 cs.CG · math.AT

A Fast Algorithm for Computing Zigzag Representatives

Tamal K. Dey , Tao Hou , Dmitriy Morozov This is my paper

Pith reviewed 2026-05-23 19:11 UTC · model grok-4.3

classification 💻 cs.CG math.AT
keywords zigzag filtrationrepresentative cyclespersistent homologysimplicial complexesalgorithmboundary matrixtopological data analysis
0
0 comments X

The pith

An O(m²n) algorithm computes compatible representative cycles for each bar in a zigzag filtration.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to produce representative cycles that remain compatible under the maps induced by each insertion or deletion step in a zigzag filtration. Existing fast barcode algorithms do not guarantee this compatibility, and the classical matrix reduction methods that work for ordinary filtrations have no known O(m³) counterpart when deletions are allowed. A reader interested in tracking concrete homological features through dynamic data would therefore need an explicit construction of cycles that map correctly from one index to the next. The presented algorithm achieves the construction in O(m²n) time, where n is the size of the largest complex appearing in the filtration.

Core claim

Given a zigzag filtration presented by boundary matrices over a field, the algorithm maintains and updates a basis of cycles so that each bar in the resulting zigzag barcode is equipped with a sequence of representative cycles that are sent to one another by the inclusion or deletion maps between consecutive complexes; the total running time is bounded by O(m²n).

What carries the argument

Matrix operations on the boundary matrices of the complexes in the filtration, used to maintain and update compatible cycle bases across insertion and deletion steps.

If this is right

  • Representative cycles for zigzag barcodes become available at a cost that depends quadratically on the number of changes rather than cubically.
  • The same data structures that compute the barcode can be extended to output the cycles without changing the asymptotic dependence on n.
  • Applications that require the actual cycles, such as feature tracking or visualization, can now operate on zigzag filtrations at the same practical scale as ordinary persistence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the underlying linear-algebra primitives can be replaced by faster matrix multiplication, the same compatibility maintenance might drop below quadratic dependence on m.
  • The technique may adapt to other persistence variants that mix additions and deletions, such as multiparameter or dynamic filtrations.
  • The O(m²n) bound suggests that, when n remains small relative to m, computing the cycles is no longer the dominant bottleneck compared with barcode computation.

Load-bearing premise

The zigzag filtration arrives explicitly as boundary matrices over a field whose arithmetic and rank operations scale with the size of the largest complex.

What would settle it

An explicit zigzag filtration of size m=100 on which an implementation of the algorithm either produces a cycle that fails to map to its neighbor or exceeds the stated O(m²n) operation count.

Figures

Figures reproduced from arXiv: 2410.20565 by Dmitriy Morozov, Tamal K. Dey, Tao Hou.

Figure 1
Figure 1. Figure 1: an illustrative example. The compression of representatives in our algorithm is made possible by adopting some novel constructs for computing zigzag persistence whose ideas are illustrated in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: An example of wires, bundles, and the boundary zigzag module which are major constructs [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of how summations of representatives for intervals respect the order ‘ [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Summing the two representatives generated by a single wire results in a new representative [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Summing two representatives generated by the bundles [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

Zigzag filtrations of simplicial complexes generalize the usual filtrations by allowing simplex deletions in addition to simplex insertions. The barcodes computed from zigzag filtrations encode the evolution of homological features. Although one can locate a particular feature at any index in the filtration using existing algorithms, the resulting representatives may not be compatible with the zigzag: a representative cycle at one index may not map into a representative cycle at its neighbor. For this, one needs to compute compatible representative cycles along each bar in the barcode. It is known that the barcode for a zigzag filtration with $m$ insertions and deletions can be computed in $O(m^\omega)$ time, where $\omega< 2.373$ is the matrix multiplication exponent. However, it is not known how to compute the compatible representatives so efficiently. For a non-zigzag filtration, the classical matrix-based algorithm provides representatives in $O(m^3)$ time, which can be improved to $O(m^\omega)$. However, no known algorithm for zigzag filtrations computes the representatives with the $O(m^3)$ time bound. We present an $O(m^2n)$ time algorithm for this problem, where $n\leq m$ is the size of the largest complex in the filtration.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper presents an O(m²n) time algorithm for computing compatible representative cycles along each bar in the barcode of a zigzag filtration of simplicial complexes (with m insertions/deletions and n the size of the largest complex), addressing the gap that existing O(m^ω) barcode algorithms and O(m^3) representative methods for ordinary filtrations do not extend to zigzag cases while preserving compatibility under the zigzag maps.

Significance. If correct, the result would be significant for computational topology, as it supplies the first sub-cubic (in m) method for zigzag representatives, enabling applications that require explicit cycles rather than just barcodes; the O(m²n) bound is a concrete improvement over the unknown status of O(m^3) methods for this setting.

major comments (1)
  1. Abstract: the central claim of an O(m²n) algorithm is stated without any pseudocode, matrix-operation details, or complexity proof in the provided manuscript text; this prevents verification of the bound or correctness and is load-bearing for the paper's contribution.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. The major comment concerns the presentation of the central complexity claim. We respond point-by-point below.

read point-by-point responses

  1. Referee: Abstract: the central claim of an O(m²n) algorithm is stated without any pseudocode, matrix-operation details, or complexity proof in the provided manuscript text; this prevents verification of the bound or correctness and is load-bearing for the paper's contribution.

    Authors: The abstract is intended only as a concise summary of the result, which is standard practice. The full manuscript contains the complete algorithm description, including pseudocode for the main procedures (Section 3), explicit matrix-operation details and data structures (Section 3.2), and the full complexity analysis proving the O(m²n) bound via a charging argument over the filtration steps (Section 4). These sections supply all information needed to verify both correctness and the time bound. If the version sent to the referee was truncated or missing these sections, we are happy to provide the complete manuscript. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an independent algorithmic result: an O(m²n) procedure for compatible representatives in zigzag filtrations, building on standard matrix operations over a field. The abstract states the problem, contrasts it with known O(m^ω) barcode computation and O(m^3) non-zigzag representatives, and asserts a new bound without any self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. No derivation step reduces to its own inputs by construction; the claim is a fresh algorithmic construction whose correctness is external to the paper's own fitted values or prior self-references.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The algorithm rests on standard linear algebra assumptions for boundary matrices in simplicial homology and the explicit presentation of the filtration sequence.

axioms (1)
  • standard math Boundary matrices of simplicial complexes admit standard matrix operations over a field for computing homology.
    Invoked implicitly for all persistent homology computations including zigzag.

pith-pipeline@v0.9.0 · 5754 in / 1035 out tokens · 21507 ms · 2026-05-23T19:11:34.651090+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Zigzag persistence

    Gunnar Carlsson and Vin de Silva. Zigzag persistence. Foundations of Computational Mathe- matics, 10(4):367–405, 2010

    work page 2010

  2. [2]

    Zigzag persistent homology and real- valued functions

    Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov. Zigzag persistent homology and real- valued functions. In Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pages 247–256, 2009

    work page 2009

  3. [3]

    Vines and vineyards by updating persistence in linear time

    David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry , pages 119–126, 2006

    work page 2006

  4. [4]

    Dey and Tao Hou

    Tamal K. Dey and Tao Hou. Computing zigzag persistence on graphs in near-linear time. In 37th International Symposium on Computational Geometry , 2021

    work page 2021

  5. [5]

    Dey and Tao Hou

    Tamal K. Dey and Tao Hou. Fast computation of zigzag persistence. In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany , volume 244 of LIPIcs, pages 43:1–43:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022. ∗Ryan Holmes: http://www.holmes3d.net/graphics/offfiles/ 15

    work page 2022

  6. [6]

    Dey and Yusu Wang

    Tamal K. Dey and Yusu Wang. Computational Topology for Data Analysis . Cambridge University Press, 2022

    work page 2022

  7. [7]

    Computational Topology: An Introduction

    Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. American Mathematical Soc., 2010

    work page 2010

  8. [8]

    Topological persistence and simplification

    Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. In Proceedings 41st Annual Symposium on Foundations of Computer Science , pages 454–463. IEEE, 2000

    work page 2000

  9. [9]

    Unzerlegbare Darstellungen I

    Peter Gabriel. Unzerlegbare Darstellungen I. Manuscripta Mathematica, 6(1):71–103, 1972

    work page 1972

  10. [10]

    Cl´ ement Maria and Steve Y. Oudot. Zigzag persistence via reflections and transpositions. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 , pages 181–199. SIAM, 2015

    work page 2015

  11. [11]

    Discrete Morse theory for computing zigzag persistence

    Cl´ ement Maria and Hannah Schreiber. Discrete Morse theory for computing zigzag persistence. In Algorithms and Data Structures - 16th International Symposium, WADS Proceedings, volume 11646 of Lecture Notes in Computer Science , pages 538–552. Springer, 2019

    work page 2019

  12. [12]

    Zigzag persistent homology in matrix multiplication time

    Nikola Milosavljevi´ c, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pages 216–225, 2011

    work page 2011

  13. [13]

    Persistence Theory: From Quiver Representations to Data Analysis , volume 209

    Steve Oudot. Persistence Theory: From Quiver Representations to Data Analysis , volume 209. AMS Mathematical Surveys and Monographs, 2015

    work page 2015

  14. [14]

    Oudot and Donald R

    Steve Y. Oudot and Donald R. Sheehy. Zigzag zoology: Rips zigzags for homology inference. Foundations of Computational Mathematics , 15(5):1151–1186, 2015. A Proof of Proposition 8 First, the fact that [zH 1 ], . . . ,[zH k′ ] is a basis of H(Kj) and zB 1 , . . . , zB k is a basis of B(Kj) follows from the definition of interval decomposition and represen...

    work page 2015

  15. [15]

    Let B[j] = B[j] + B[k], C[j] = C[j] + C[k], and U j = U j ⊞ U k

    Two columns B[j] and B[k] have the same pivot: WLOG, assume that b′ k ≺ b′ j. Let B[j] = B[j] + B[k], C[j] = C[j] + C[k], and U j = U j ⊞ U k

    work page

  16. [16]

    Let Z[j] = Z[j] + B[k] and W j = W j ⊞ U k

    Two columns Z[j] and B[k] have the same pivot: We have b′ k ≺ ˆbj. Let Z[j] = Z[j] + B[k] and W j = W j ⊞ U k

    work page

  17. [17]

    Let Z[j] = Z[j] + Z[k] and W j = W j ⊞ W k

    Two columns Z[j] and Z[k] have the same pivot: WLOG, assume that ˆbk ≺ ˆbj. Let Z[j] = Z[j] + Z[k] and W j = W j ⊞ W k. Since in each iteration of the above loop we change only one column of Z and B, there are at most two columns of Z and B with the same pivot at any time. Hence, the above loop ends in no more than n iterations because the pivot of the tw...

    work page

  18. [18]

    , αℓ ← indices of all columns of C containing σi 18

    α1, . . . , αℓ ← indices of all columns of C containing σi 18

    work page

  19. [19]

    , αℓ s.t

    sort and rename α1, . . . , αℓ s.t. b′ α1 ≺ · · · ≺ b′ αℓ

    work page

  20. [21]

    if pivot(B[α]) > pivot(c2) then:

    work page

  21. [22]

    , B[αℓ] have distinct pivots

    U ← temp U We always maintain the following invariants for the loop: (i) c2 = ∂(c1); (ii) c2 is the last cycle (at index i) in the representative generated by U; (ii) the birth index corresponding to c2 (and U) is always less than b′ α in the total order ‘ ≺’; (iv) c2 along with B[α2], . . . , B[αℓ] have distinct pivots. When the loop terminates, we are l...

    work page

  22. [23]

    , αℓ ← indices of all columns of Z containing σi 19

    α1, . . . , αℓ ← indices of all columns of Z containing σi 19

    work page

  23. [24]

    , αℓ s.t

    sort and rename α1, . . . , αℓ s.t. ˆbα1 ≺ · · · ≺ ˆbαℓ

    work page

  24. [25]

    , αℓ do:

    for α ← α2, . . . , αℓ do:

    work page

  25. [26]

    if pivot(Z[α]) > pivot(z) then:

    work page

  26. [27]

    delete the column Z[α1] from Z In the above pseudocodes, α1 is the index ‘ λ’ as in the corresponding case in Section 4. 20

    work page