Compression aims to reduce the size of an input, while maintaining its relevant properties. For multi-parameter persistent homology, compression is a necessary step in any computational pipeline, since standard constructions lead to large inputs, and computational tasks in this area tend to be expensive. We propose two compression methods for chain complexes of free 2-parameter persistence modules. The first method extends the multi-chunk algorithm for one-parameter persistent homology, returning the smallest chain complex among all the ones quasi-isomorphic to the input. The second method produces minimal presentations of the homology of the input; it is based on an algorithm of Lesnick and Wright, but incorporates several improvements that lead to dramatic performance gains. The two methods are complementary, and can be combined to compute minimal presentations for complexes with millions of generators in a few seconds. The methods have been implemented, and the software is publicly available. We report on experimental evaluations, which demonstrate substantial improvements in performance compared to previously available compression strategies.
翻译:对于多参数的持久性同质学,压缩是任何计算管道中的必要步骤,因为标准构造导致大量投入,而这一领域的计算任务往往费用昂贵。我们为自由的2度持久性模块的链状综合体提出了两种压缩方法。第一种方法扩展了单参数持久性同质学的多整英法算法,将所有准同质体中最小的链状综合体返回到输入中。第二种方法生成了最小的输入同质性的表述;它以Lesnick和Right的算法为基础,但包含了若干改进,从而带来显著的性能收益。这两种方法是相辅相成的,可以在几秒钟内对数百万发电机的复杂体进行最小的计算。这些方法已经实施,软件是公开的。我们报告了实验性评估情况,这些评估表明与以往的压缩战略相比,业绩有了很大的改进。