用并查集与查表法加速2D/3D图像的立方体同调计算
Fast Cubical Persistent Homology on 2D and 3D Images via Union-Find, Pruning, and Lookup Tables
- 利用并查集和对偶性计算高维同调
- 通过剪枝优化并查集效率，减少冗余计算
- 预存局部信息查表，避免运行时重复计算
我们提出Flash Cubical，一种在$/mathbb{F}_2$上针对2D和3D图像的V-滤链立方体同调的高效计算方法。该实现基于三个核心思想：首先，立方体复形具有可利用并查集与对偶性计算最高维同调的性质；其次，通过剪枝特定边来加速并查集的执行；第三，利用查找表预先计算立方体复形规则结构下的局部信息，避免运行时动态计算。据我们所知，这是目前针对带V-滤链的立方体同调最高效的实现，无论在时间还是内存消耗方面均表现优异。尽管本文聚焦于V-滤链立方体复形的同调计算，其核心思想可自然推广至立方体复形上的T-滤链，并为其他复形提供了有前景的方向。
原文摘要 · Abstract (English)
We present Flash Cubical, a highly efficient computation of cubical persistence on a V-filtration for 2D and 3D images over $\mathbb{F}_2$. The implementation is built around three core ideas. First, cubical complexes satisfy properties that allow for the computation of persistence of the highest dimension via union-find and duality. Second, pruning of certain edges allows for a fast and efficient implementation of union-find. Third, the use of a lookup table, which exploits the regularity of cubical complexes to pre-compute local information. This avoids the need to compute local information at run time. To the best of our knowledge, this is the most efficient implementation of cubical persistence with a V-filtration, both in terms of time and memory costs. Although the paper focuses on persistence for V-filtration cubical complexes, the underlying ideas generalise naturally to T-filtrations on cubical complexes and suggest promising directions for other complexes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。