The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite interval
 Award ID(s):
 2049010
 NSFPAR ID:
 10348047
 Editor(s):
 Xavier Goaoc; Michael Kerber
 Date Published:
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 224
 ISSN:
 18688969
 Page Range / eLocation ID:
 34:134:17
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract I of a indexed persistence module$$\textbf{Z}^2$$ ${Z}^{2}$M is equal to the generalized rank of the zigzag module that is induced on a certain path inI tracing mostly its boundary. Hence, we can compute the generalized rank ofM overI by computing the barcode of the zigzag module obtained by restricting to that path. IfM is the homology of a bifiltrationF of simplices (while accounting for multicriticality) and$$t$$ $t$I consists of points, this computation takes$$t$$ $t$ time where$$O(t^\omega )$$ $O\left({t}^{\omega}\right)$ is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module$$\omega \in [2,2.373)$$ $\omega \in [2,2.373)$M , determine whetherM is interval decomposable and, if so, compute all intervals supporting its indecomposable summands. 
We first introduce the notion of metarank for a 2parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the metadiagram of a 2parameter persistence module to be the Möbius inversion of the metarank, resulting in a function that takes values from signed 1parameter persistence modules. We show that the metarank and metadiagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the metarank and metadiagram of a 2parameter module M indexed by a bifiltration of n simplices in O(n^3) time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has O(n^4) time complexity. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of M from O(n^4) to O(n^3). In addition, we define notions of erosion distance between metaranks and between metadiagrams, and show that under these distances, metaranks and metadiagrams are stable with respect to the interleaving distance. Lastly, the metadiagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the wellunderstood persistent diagram in the 1parameter setting.more » « less

Abstract Commutative diagrams of vector spaces and linear maps over
are objects of interest in topological data analysis (TDA) where this type of diagrams are called 2parameter persistence modules. Given that quiver representation theory tells us that such diagrams are of wild type, studying informative invariants of a 2parameter persistence module$$\mathbb {Z}^2$$ ${Z}^{2}$M is of central importance in TDA. One of such invariants is the generalized rank invariant, recently introduced by Kim and Mémoli. Via the Möbius inversion of the generalized rank invariant ofM , we obtain a collection of connected subsets with signed multiplicities. This collection generalizes the well known notion of$$I\subset \mathbb {Z}^2$$ $I\subset {Z}^{2}$persistence barcode of a persistence module over from TDA. In this paper we show that the bigraded Betti numbers of$$\mathbb {R}$$ $R$M , a classical algebraic invariant ofM , are obtained by counting the corner points of these subsetsI s. Along the way, we verify that an invariant of 2parameter persistence modules called the interval decomposable approximation (introduced by Asashiba et al.) also encodes the bigraded Betti numbers in a similar fashion. We also show that the aforementioned results are optimal in the sense that they cannot be extended tod parameter persistence modules for .$$d \ge 3$$ $d\ge 3$ 
null (Ed.)Graphs model realworld circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly lineartime algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in nearlinear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0dimension runs in O(mlog² n+mlog m) time and the algorithm for 1dimension runs in O(mlog⁴ n) time. The algorithm for 0dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2manifolds. The algorithm for 1dimension pairs a negative edge with the earliest positive edge so that a 1cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al. In the end, using Alexander duality, we extend the algorithm for 0dimension to compute the (p1)dimensional zigzag persistence for ℝ^pembedded complexes in O(mlog² n+mlog m+nlog n) time.more » « less

Zigzag persistence is a powerful extension of the standard persistence which allows deletions of simplices besides insertions. However, computing zigzag persistence usually takes considerably more time than the standard persistence. We propose an algorithm called FastZigzag which narrows this efficiency gap. Our main result is that an input simplexwise zigzag filtration can be converted to a cellwise nonzigzag filtration of a ∆complex with the same length, where the cells are copies of the input simplices. This conversion step in FastZigzag incurs very little cost. Furthermore, the barcode of the original filtration can be easily read from the barcode of the new cellwise filtration because the conversion embodies a series of diamond switches known in topological data analysis. This seemingly simple observation opens up the vast possibilities for improving the computation of zigzag persistence because any efficient algorithm/software for standard persistence can now be applied to computing zigzag persistence. Our experiment shows that this indeed achieves substantial performance gain over the existing stateoftheart softwares.more » « less