Tamal Dey (8/24): Computing Generalized Ranks of Persistence Modules via Unfolding to Zigzag Modules
For a persistence module M indexed by a finite poset P, the (generalized) rank is defined as the rank of the limit-to-colimit map for the diagram of vector spaces of M over the poset P. For 2-parameter persistence modules, a zigzag persistence based algorithm has been proposed that takes advantage of the fact that generalized rank for 2-parameter modules is equal to the number of full intervals in a zigzag module defined on the boundary of the poset. Analogous definition of boundary for d-parameter persistence modules or general persistence modules indexed by posets does not seem plausible. To overcome this difficulty, we first unfold a given module M into a zigzag module M_{ZZ} and then check how many full interval modules in a decomposition of M_{ZZ} can be folded back to remain full in a decomposition of M. This number determines the generalized rank of M. We give an efficient algorithm to compute this number for the case when M is induced by a filtration of a simplicial complex over a finite poset. For special cases where M is the homology functor in degree d applied to a filtration of a d-complex, we obtain a more efficient algorithm including a linear time algorithm for graphs in degree-1 homology.