Kerber Michael, Schreiber Hannah
Graz University of Technology, Kopernikusgasse 24, 8010 Graz, Austria.
Discrete Comput Geom. 2019;61(4):852-879. doi: 10.1007/s00454-018-0030-0. Epub 2018 Oct 1.
A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG, 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.
塔是由单纯映射连接的一系列单纯复形。我们展示了如何计算一个过滤，即一系列嵌套的单纯复形，其持久条形码与塔相同。我们的方法基于Dey等人（SoCG，2014）的锥化策略。我们表明，这种方法的一个变体产生的过滤在渐近意义上仅比塔略大，并且在理论和实践中都可以通过流算法有效地计算。此外，我们表明我们的方法可以与流算法相结合，通过矩阵约简来计算塔的条形码。该算法的空间复杂度不依赖于塔的长度，而是依赖于塔内任何子复形的最大大小。实验评估表明，我们的方法可以有效地处理包含数十亿个复形的塔。
