.png){kind=icon}
返回
A Fast Algorithm for Computing Zigzag Representatives
.png){kind=icon}
PRE
AI
DOI：10.1007/s00453-026-01386-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Zigzag滤筒的单纯复形推广了通常的滤筒，允许单纯形删除和插入。从Zigzag滤筒计算出的条形码编码了同调特征的发展。尽管现有的算法可以定位滤筒中任意索引的特定特征，但结果表示可能与Zigzag不兼容：一个索引的代表循环可能不会映射到其相邻索引的代表循环。为此，需要计算条形码中每条杆的兼容代表循环。已知具有m次插入和删除的Zigzag滤筒的条形码可以在O(m(omega))时间内计算，其中omega < 2.373是矩阵乘法的指数。然而，尚不清楚如何如此高效地计算兼容代表。对于非Zigzag滤筒，经典的基于矩阵的算法可以在O(m(3))时间内提供代表，可改进至O(m(omega))。然而，目前尚无已知算法能在O(m(3))时间内为Zigzag滤筒计算代表。我们提出了一个O(m(2)n)时间算法来解决这个问题，其中n <= m是滤筒中最大复形的大小。
Keyword:
Persistent homology
Zigzag persistence
Representatives
Topological data analysis
期刊
A
IF:
0.7
论文数:
56
被引数:
2.7K
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容