{"id":"b9ad1f1d-5a3a-44d8-99d5-09574610d1aa","arxiv_id":"2412.02591","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New batched Gaussian-elimination algorithms compute the cycle representatives of ordinary persistent (co)homology in O(n^ω) time.","lead":"This paper gives fast algorithms that compute persistent homology cycle representatives in matrix multiplication time, matching the speed of computing persistence diagrams. This matters because applications need explicit cycles, not just the diagrams, and these representatives were previously not known to be computable this fast.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 5's batch row update applies the identity entries of Λ to columns that should not be reduced, corrupting the lazy reduction; a valid 4-simplex filtration already gives R different from Algorithm 4.","rationale":"The reader flagged the invariant in Remark 5.2 and the sketchy proof of Theorem 5.3 as the weakest assumption. My stress-test agrees that this is the weak spot, but goes further: the invariant, even if true, is insufficient to establish correctness of Algorithm 5, because the batch row update in line 11 applies the identity/self-carry entries of Λ to columns that should not be reduced. On a valid 4-simplex filtration, the literal algorithm produces a reduced matrix different from the standard lazy reduction, contradicting Theorem 5.3 and undermining the paper's central claim that lazy reduction representatives can be computed in matrix multiplication time.\n\nI do not see a problem with the column algorithm or the running-time analysis, and the issue may be fixable by a relatively small modification to line 11 (e.g., using only the off-identity part of P·Λ·P in the row update). However, as written, the main theorem for the lazy reduction is false, so the current version should not be accepted. The proposed concrete test is cheap and would settle whether the discrepancy is real; if the test reproduces my counterexample, a revised version must either fix the update rule or substantially change the claimed algorithm and proof.","tokens_in":14090,"tokens_out":45110,"duration_ms":467002,"concrete_test":"Implement Algorithm 5 exactly as written, with the identity-entry 1 at column n−i+1 included in (P·Λ·P), and run it on the valid n=4 filtration over F2 with D columns c1=c2=c4=0, c3=(1,1,0,0), augmented with I4. Compare the output R with Algorithm 4 on the same augmented matrix. If column 7 of the Algorithm 5 output has a nonzero entry in row 1 while Algorithm 4 leaves it as (0,0,1,0), then Theorem 5.3 is false as stated. A minimal patch would be to restrict line 11 to use only the strictly-upper (non-identity) part of P·Λ·P, and to re-prove correctness with that restriction; the test should be repeated after any such patch.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim requires Algorithm 5 (the fast row algorithm) to reproduce the lazy reduction. In Algorithm 5, line 11 performs the row update as\n(R·P)[Cr, ·] ← (R·P)[Cr, ·] + (R·P)[Cr, B] · (P·Λ·P)[B, ·],\nusing the full row of P·Λ·P, including the entry set to 1 at column n−i+1 in the base case (Section 5.1). That entry is a self/identity coefficient, not a reduction coefficient. Applying it in the batched update adds the pivot column's entries to columns that should not be modified, even when those columns have already been assigned pivots below the current row and moved to the left.\n\nConcrete counterexample over F2 with n=4 and boundary matrix D with columns c1=c2=c4=0, c3=(1,1,0,0), augmented with I4. Algorithm 4 (and standard lazy reduction) returns reduced R with c7 = (0,0,1,0). Running Algorithm 5 literally: after processing row 2, the line-11 update on row 1 adds R[1,3]·(P·Λ·P)[3,:] = 1·[0,1,0,0,0,1,0,0], so column 7 (I3) becomes (1,0,1,0). The row-1 base case then pivots on column 5 and zeroes only entries to its right, leaving I3 corrupted. Thus Algorithm 5 does not compute the lazy reduction even for this valid filtration.\n\nThe invariant in Remark 5.2 does not prevent this failure: I3 has its pivot below row 1 and lies to the left of the row-1 pivot, so it is never zeroed, but it was already modified by the spurious identity-entry update. The proof of Theorem 5.3 does not address why such identity entries should be excluded from the batch row update, and the pseudocode as written includes them.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents two algorithms for computing the R = DV decomposition in persistent (co)homology in matrix multiplication time, with the goal of recovering cycle representatives in the same asymptotic time as computing the persistence diagram. Algorithm 3 is a fast \"exhaustive\" reduction based on Schur complements, and Algorithm 5 is a fast \"lazy\" reduction based on bottom-up batched row updates. The authors claim that the latter reproduces exactly the lazy reduction of the standard persistence algorithm, including its cycle representatives, in O(n^ω) time (O(n^2 log n) when ω = 2).","tokens_in":14490,"tokens_out":8175,"duration_ms":85658,"significance":"If both algorithms were correct, the paper would close a notable gap: persistence diagrams were already known to be computable in matrix multiplication time, but extracting the specific cycle representatives used in applications was not known to have the same bound. The column algorithm in Section 4 is an elegant and apparently correct specialization of the zigzag algorithm of Milosavljevic et al., and the running-time analysis for it is convincing. However, the row algorithm in Section 5 is the load-bearing contribution for the lazy reduction, and it has a concrete correctness problem that is not addressed by the proof of Theorem 5.3. Since the central claim of the paper depends on this algorithm, the manuscript needs substantial revision before the claimed result can be accepted.","major_comments":[{"comment":"The batched row update in line 11 applies the full row (P·Λ·P)[B,·], including the diagonal identity entries that Λ inherits from its initialization as I_{m+n}. These identity entries are self/pivot coefficients, not reduction coefficients, and using them adds the pivot columns themselves to the rows in Cr. This corrupts the lazy reduction. Concretely, over F_2 with n = 4 and D having columns c1 = c2 = c4 = 0 and c3 = (1,1,0,0), augmented with I_4, running Algorithm 5 literally makes column 7 (the third identity column) equal to (1,0,1,0) after the row-2 update, whereas Algorithm 4 and standard lazy reduction leave R[1,7] = 0. Thus Algorithm 5, as written, does not compute the lazy reduction.","section":"§5.1, Algorithm 5, line 11"},{"comment":"The proof of Theorem 5.3 asserts that the batched operations reproduce Algorithm 4, but it never explains why the identity entries on the diagonal of P·Λ·P should not be applied during the row updates. Remark 5.2 only guarantees that columns whose pivots lie below the current row have been moved to the left of the current pivot; it does not guarantee that those columns are not modified. In the example above, the corrupted column lies to the left of the row-1 pivot and is therefore never zeroed by the base-case row clearing, so the invariant cannot catch the error. A correct proof must either exclude the diagonal entries from the row update or show they cancel through some additional mechanism.","section":"Theorem 5.3 and Remark 5.2"},{"comment":"Because Theorem 5.4 and the claimed recovery of lazy cycle representatives from U and V depend on Algorithm 5 actually performing the lazy reduction, the failure described above invalidates the advertised representative-recovery result for the lazy reduction. The paper's central claim in the introduction that Algorithm 5 computes the lazy reduction is therefore not established by the current manuscript.","section":"Theorem 5.4 and §2.2"}],"minor_comments":[{"comment":"The proof contains a duplicated sentence about a column that 'has not been used to reduce any other column'; the repetition should be removed.","section":"Theorem 5.4 proof"},{"comment":"The sentence about using the column algorithm to compute the lazy basis and the row algorithm for the exhaustive basis is easy to misread as reversing the roles of the two algorithms; consider rephrasing for clarity.","section":"Section 6"},{"comment":"The proof of Lemma 5.1 is a bare citation to [3, Theorem 3.1]. Since the terminology 'lazy reduction' may not match the cited theorem's conventions, a short explanation of the correspondence would improve readability.","section":"Lemma 5.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript builds on two earlier papers with overlapping authors ([1] and [3]) for its key equivalences. This is not in itself a problem, because those results are published and have stated assumptions, but it does mean that the novelty of the row algorithm rests almost entirely on the new batching argument, which is precisely where the concrete error appears. I would be willing to review a revised version that fixes the row update and supplies a complete correctness proof; the column algorithm appears sound and should be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The column algorithm (Algorithm 3) is the real contribution. The Schur-complement batching is clean, the proof of Lemmas 4.3–4.4 and Theorem 4.5 holds up, and the running time O(n^ω) is sound. This gives cycle representatives for exhaustive reduction in matrix multiplication time, which is genuinely new and useful. I also like the observation U = 2I − Λ in Theorem 5.4, and the Dey–Hou connection is a nice extra.\n\nThe trouble is Algorithm 5, the fast lazy-reduction row algorithm. The proof of Theorem 5.3 is a sketch that leans on an invariant in Remark 5.2 and a citation to [3, Theorem 3.1]. The concrete F2 counterexample in the stress-test note looks real to me: line 11 multiplies by the full row of P·Λ·P, including the identity/diagonal entries, so the pivot column’s entries get added to columns that should not be touched. In the n=4 example, column 7 (I3) is corrupted and the final R does not match lazy reduction. Even if the notational ambiguity about P·Λ·P might rescue the algorithm in some modified form, the proof does not explain why those identity entries should be excluded from the batch update, and the pseudocode as written includes them. That is a load-bearing gap, not a minor typo.\n\nThere are also formatting issues in Section 5.1 (the initialization of R and Λ is nearly unreadable), which make it even harder to verify the algorithm.\n\nWho gets value from this: computational topologists who care about asymptotic bounds for persistence with representatives. The exhaustive half is worth citing and building on. The lazy half, as written, should not be trusted until it is either fixed or given a much more careful proof that explicitly handles the diagonal of Λ. I would send this to a serious referee—the column algorithm alone justifies referee time—but the referee should be instructed to focus on Algorithm 5 and the stress-test-style counterexample, and to demand a corrected version or a fully formal proof.","headline":"Solid exhaustive-reduction algorithm, but the lazy-reduction row algorithm looks broken as written and is not adequately proven.","tokens_in":15064,"tokens_out":11719,"would_cite":false,"duration_ms":111724,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["55N31","55-08","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Persistent homology representatives can be computed in matrix multiplication time, matching the cost of the persistence diagram itself.","keywords":["persistent homology","persistent cohomology","cycle representatives","R=DV decomposition","lazy reduction","exhaustive reduction","matrix multiplication time"],"falsifier":"Implement Algorithm 5 over a fixed field and compare its output against Algorithm 4 (the incremental lazy reduction) on all simplicial complexes with up to six vertices and every total-order extension of their face posets; any filtration where the pivot positions (the low values) of the two algorithms differ, or where the recovered cycle representatives differ, would refute Theorem 5.3. A smaller targeted check is to construct a boundary matrix where the row algorithm's column permutation places a column with a lower pivot to the right of the current pivot and verify that the batched row zeroing in Line 5 still matches the lazy reduction.","tokens_in":13854,"feed_emoji":"⏱️","tokens_out":12369,"duration_ms":116988,"temperature":0.7,"pith_summary":"The paper's central claim is that the full $R=DV$ decomposition of a persistent (co)homology boundary matrix—including the cycle and cocycle representatives it encodes—can be computed in matrix multiplication time, matching the asymptotic cost of computing the persistence diagram alone. Concretely, it gives two algorithms: a column algorithm for the exhaustive reduction and a row algorithm for the lazy reduction, each running in $O(n^\\omega)$ over a fixed field, or $O(n^2\\log n)$ when the matrix multiplication exponent $\\omega$ equals 2. This matters because applications routinely use the specific representatives produced by these reductions for attribution, point-cloud triangulation, and topological optimization, and previously only the diagram, not the representatives, was known to admit this bound. The paper also observes that applying the same algorithms to the anti-transpose of the boundary matrix gives persistent cohomology, and that the fast zigzag construction makes this another route to zigzag persistence in matrix multiplication time.","feed_headline":"Cycle representatives join diagrams at matrix-multiplication speed","feed_subtitle":"Lazy and exhaustive reductions both hit matrix-multiplication speed — cycle representatives at last match the diagram's cost.","key_machinery":"The load-bearing identity is $R=DV$, where $D$ is the filtration-ordered boundary matrix, $V$ is a full-rank upper-triangular matrix of column operations, and $R$ is column-reduced; the columns of $V$ and $R$ provide the cycle and cocycle representatives. The second mechanism is the Schur complement: when a submatrix of pivot rows is lower triangular (hence invertible), the update $R[\\bar{L},C] \\leftarrow R[\\bar{L},C] - R[\\bar{L},B]\\cdot R[L,B]^{-1}\\cdot R[L,C]$ applies all column reductions from block $B$ to block $C$ in one matrix product. The row algorithm replaces inversion with column permutations that keep every column with a lower pivot to the left of the current pivot, allowing one batched row-zeroing update per pivot. These batch operations are what bring the complexity down from cubic time to matrix multiplication time.","core_discovery":"On its own terms, the paper establishes that there is no asymptotic price for the standard representatives in ordinary persistent (co)homology. For the exhaustive reduction, Algorithm 3 uses batched Schur-complement updates that reduce blocks of columns at once after permuting pivot rows to the bottom, yielding $R=DV$ with the same column-reduced form as a full look-ahead reduction. For the lazy reduction, Algorithm 5 works bottom-up on rows, using column permutations to align leftmost eligible pivots and then zeroing whole rows in one batch; Lemma 5.1 and Theorem 5.3 assert this reproduces exactly the standard lazy reduction's $R$, $V$, and hence its representatives. Because $V$ is upper triangular and $U = 2I - \\Lambda$ in the lazy case, representatives, pairings, and the persistence diagram all come out of the same $O(n^\\omega)$ computation.","pith_inferences":["With both target reductions at the matrix-multiplication bound, the practical bottleneck shifts from asymptotic complexity to constant factors and the cost of field operations; implementations could plausibly switch between block matrix products and standard column reduction depending on block size, a trade-off the paper does not explore.","The invariant behind the row algorithm suggests a general recipe: batched reductions are safe exactly when the permutation removes all later columns with lower pivots to the left. Adapting that recipe to other reduction orders, such as output-sensitive or parallel schemes, could yield additional algorithms with the same complexity bound, though the paper makes no such claim.","If the paper's stated open question about transforming exhaustive representatives into lazy ones (and vice versa) without rerunning the reduction is resolved, a single matrix-multiplication-time reduction would serve every application that needs either basis."],"forward_implications":["Persistence diagrams and the cycle representatives produced by either the lazy or exhaustive reduction become simultaneously available in $O(n^\\omega)$ time, so applications that currently run a second, slower reduction to obtain representatives pay no asymptotic extra cost.","All the algorithms transfer to persistent cohomology by applying the same reduction to the anti-transpose of the boundary matrix, giving cocycle representatives with the same time bound.","Combined with the fast zigzag construction for reducing zigzag persistence to ordinary persistence, these algorithms provide another matrix-multiplication-time route to zigzag persistence, extending the reach of the $R=DV$ formulation beyond ordinary filtrations.","Because the row algorithm returns the same representatives as the standard lazy persistence algorithm, it can serve as a drop-in replacement for standard pipelines that need the usual basis, not just the barcode.","The exhaustive reduction's representatives are the lexicographically optimal cycles used in point-cloud triangulation, so those optimal representatives now come with the same asymptotic guarantee as the barcode."],"supporting_citations":[{"why":"Establishes that zigzag persistent homology, and hence ordinary persistence diagrams, can be computed in matrix multiplication time; this paper specializes and simplifies that algorithm for ordinary persistence.","marker":"[1]"},{"why":"Defines persistent homology and the standard reduction algorithm whose cycle representatives the paper aims to recover quickly.","marker":"[2]"},{"why":"Supplies Theorem 3.1 used to prove the row algorithm equals the lazy reduction, and the anti-transpose trick for transferring results to persistent cohomology.","marker":"[3]"},{"why":"Connects persistence computation to Gaussian elimination, setting up the reduction framework the fast algorithms build on.","marker":"[13]"},{"why":"Introduces the $R=DV$ decomposition and the Pairing Uniqueness Lemma used in the correctness proof of the exhaustive algorithm.","marker":"[16]"},{"why":"Provides the fact that matrix inversion (for triangular matrices) can be done in matrix multiplication time, which the column algorithm relies on for Schur complements.","marker":"[27]"}],"fun_headline_variants":["Cycle representatives reach matrix-multiplication speed","Persistent homology: cycle reps now match diagram cost","No asymptotic price for standard cycle representatives","Matrix-multiplication time for persistent homology cycles","Fast cycle extraction for persistent homology diagrams"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The fast row algorithm's correctness rests on the invariant that after every column permutation, every column whose lowest nonzero entry lies below the current row has been moved to the left of the current pivot position; if that invariant ever failed, zeroing the whole row to the right would silently skip reductions that the lazy algorithm would still perform.","fun_headline_variants_meta":{"raw":{"variants":["Cycle representatives reach matrix-multiplication speed","Persistent homology: cycle reps now match diagram cost","No asymptotic price for standard cycle representatives","Matrix-multiplication time for persistent homology cycles","Fast cycle extraction for persistent homology diagrams"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000476,"raw_usage":{"total_tokens":2324,"prompt_tokens":874,"completion_tokens":1450,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":1383}},"tokens_in":490,"tokens_out":1450,"duration_ms":12739,"temperature":1.0,"reasoning_tokens":1383,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:19:28.969124+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement Algorithm 5 over a fixed field and compare its output against Algorithm 4 (the incremental lazy reduction) on all simplicial complexes with up to six vertices and every total-order extension of their face posets; any filtration where the pivot positions (the low values) of the two algorithms differ, or where the recovered cycle representatives differ, would refute Theorem 5.3. A smaller targeted check is to construct a boundary matrix where the row algorithm's column permutation places a column with a lower pivot to the right of the current pivot and verify that the batched row zeroing in Line 5 still matches the lazy reduction.","supporting_citations":[{"cited_title":"Zigzag persistent homology in matrix mul- tiplication time","cited_arxiv_id":null,"evidence_quote":"Establishes that zigzag persistent homology, and hence ordinary persistence diagrams, can be computed in matrix multiplication time; this paper specializes and simplifies that algorithm for ordinary persistence."},{"cited_title":"Edelsbrunner, D","cited_arxiv_id":null,"evidence_quote":"Defines persistent homology and the standard reduction algorithm whose cycle representatives the paper aims to recover quickly."},{"cited_title":"Dualities in persistent (co) homology","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 3.1 used to prove the row algorithm equals the lazy reduction, and the anti-transpose trick for transferring results to persistent cohomology."},{"cited_title":"Vines and vineyards by updating persistence in linear time","cited_arxiv_id":null,"evidence_quote":"Introduces the $R=DV$ decomposition and the Pairing Uniqueness Lemma used in the correctness proof of the exhaustive algorithm."},{"cited_title":"Gaussian elimination is not optimal","cited_arxiv_id":null,"evidence_quote":"Provides the fact that matrix inversion (for triangular matrices) can be done in matrix multiplication time, which the column algorithm relies on for Schur complements."}],"review_version":1}