论文标题
双级持久性模块的快速最小呈现
Fast Minimal Presentations of Bi-graded Persistence Modules
论文作者
论文摘要
多参数持续的同源性是拓扑数据分析的最新分支。在该领域，有关两个或多个比例参数的同源性镜头研究了数据集。许多算法的高计算成本需要一个预处理步骤来减少输入大小。通常，最小呈现是持久模块的最小可能表示。莱斯尼克（Lesnick）和赖特（Wright）最近提出了一种算法（LW-Algorithm），用于计算基于矩阵还原的最低介绍。在这项工作中，我们提出，实施和基准对LW-Algorithm进行了一些改进。最值得注意的是，我们建议使用优先队列以避免对矩阵列进行广泛的扫描，该矩阵列构成了LW-Algorithm中的计算瓶颈，我们将其算法与Fugacci和Kerber的多参数块算法的想法与来自多参数块的构想相结合。我们的广泛实验表明，我们的算法的表现优于LW-Algorithm，并在几秒钟内计算了数百万个简单的数据集的最小呈现。我们的软件已公开可用。
Multi-parameter persistent homology is a recent branch of topological data analysis. In this area, data sets are investigated through the lens of homology with respect to two or more scale parameters. The high computational cost of many algorithms calls for a preprocessing step to reduce the input size. In general, a minimal presentation is the smallest possible representation of a persistence module. Lesnick and Wright proposed recently an algorithm (the LW-algorithm) for computing minimal presentations based on matrix reduction. In this work, we propose, implement and benchmark several improvements over the LW-algorithm. Most notably, we propose the use of priority queues to avoid extensive scanning of the matrix columns, which constitutes the computational bottleneck in the LW-algorithm, and we combine their algorithm with ideas from the multi-parameter chunk algorithm by Fugacci and Kerber. Our extensive experiments show that our algorithm outperforms the LW-algorithm and computes the minimal presentation for data sets with millions of simplices within a few seconds. Our software is publicly available.
