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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(m^\omega )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mi>ω</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\omega < 2.373$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo><</mo> <mn>2.373</mn> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(m^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, which can be improved to <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(m^\omega )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mi>ω</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. However, no known algorithm for zigzag filtrations computes the representatives with the <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(m^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time bound. We present an <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(m^2n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>m</mi> <mn>2</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time algorithm for this problem, where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$n\le m$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≤</mo> <mi>m</mi> </mrow> </math></EquationSource> </InlineEquation> is the size of the largest complex in the filtration.

A Fast Algorithm for Computing Zigzag Representatives

期刊论文
出版模式：

开放获取
发表日期：

2026年4月9日

查看全文

Tamal K. Dey,
Tao Hou,
Dmitriy Morozov

摘要

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 )$ $O (m^{ω})$ time, where $\omega < 2.373$ $ω < 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)$ $O (m^{3})$ time, which can be improved to $O(m^\omega )$ $O (m^{ω})$ . However, no known algorithm for zigzag filtrations computes the representatives with the $O(m^3)$ $O (m^{3})$ time bound. We present an $O(m^2n)$ $O (m^{2} n)$ time algorithm for this problem, where $n\le m$ $n \leq m$ is the size of the largest complex in the filtration.