%ADey, Tamal%AKim, Woojin%AMémoli, Facundo%BJournal Name: Discrete & Computational Geometry; Journal Volume: 71; Journal Issue: 1; Related Information: CHORUS Timestamp: 2024-01-06 15:02:29
%D2023%ISpringer Science + Business Media
%JJournal Name: Discrete & Computational Geometry; Journal Volume: 71; Journal Issue: 1; Related Information: CHORUS Timestamp: 2024-01-06 15:02:29
%K
%MOSTI ID: 10468074
%PMedium: X; Size: p. 67-94
%TComputing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications
%XAbstract
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 intervalIof a$$\textbf{Z}^2$$${Z}^{2}$-indexed persistence moduleMis equal to the generalized rank of the zigzag module that is induced on a certain path inItracing mostly its boundary. Hence, we can compute the generalized rank ofMoverIby computing the barcode of the zigzag module obtained by restricting to that path. IfMis the homology of a bifiltrationFof$$t$$$t$simplices (while accounting for multi-criticality) andIconsists of$$t$$$t$points, this computation takes$$O(t^\omega )$$$O\left({t}^{\omega}\right)$time where$$\omega \in [2,2.373)$$$\omega \in [2,2.373)$is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a moduleM, determine whetherMis interval decomposable and, if so, compute all intervals supporting its indecomposable summands.

%0Journal Article