Math @ Duke
|
Publications [#361469] of Woojin Kim
Papers Published
- Dey, TK; Kim, W; Mémoli, F, Computing Generalized Rank Invariant for 2-Parameter Persistence Modules
via Zigzag Persistence and its Applications
(November, 2021)
(last updated on 2023/07/05)
Abstract: The notion of generalized rank invariant in the context of multiparameter
persistence has become an important ingredient for defining interesting
homological structures such as generalized persistence diagrams. Naturally,
computing these rank invariants efficiently is a prelude to computing any of
these derived structures efficiently. We show that the generalized rank over a
finite interval $I$ of a $\mathbb{Z}^2$-indexed persistence module $M$ is equal
to the generalized rank of the zigzag module that is induced on a certain path
in $I$ tracing mostly its boundary. Hence, we can compute the generalized rank
over $I$ by computing the barcode of the zigzag module obtained by restricting
the bifiltration inducing $M$ to that path. If the bifiltration and $I$ have at
most $t$ simplices and points respectively, this computation takes
$O(t^\omega)$ time where $\omega\in[2,2.373)$ is the exponent of matrix
multiplication. Among others, we apply this result to obtain an improved
algorithm for the following problem. Given a bifiltration inducing a module
$M$, determine whether $M$ is interval decomposable and, if so, compute all
intervals supporting its summands.
|
|
dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
| |
Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320
|
|