Computing the Skyscraper Invariant
This work addresses computational bottlenecks in topological data analysis for researchers in applied mathematics and data science, though it is incremental as it builds on existing methods like Cheng's algorithm.
The paper tackles the problem of computing the Skyscraper Invariant for multiparameter persistence modules, which was previously infeasible due to high computational costs, and develops algorithms including an FPT ε-approximate method with runtime O(1/ε^d · T_dec) and an exact computation with runtime roughly O(n^d · T_dec), implementing them for 2-parameter modules and applying to biomedical data.
We develop the first algorithms for computing the Skyscraper Invariant [FJNT24]. This is a filtration of the classical rank invariant for multiparameter persistence modules defined by the Harder-Narasimhan filtrations along every central charge supported at a single parameter value. Cheng's algorithm [Cheng24] can be used to compute HN filtrations of arbitrary acyclic quiver representations in polynomial time in the total dimension, but in practice, the large dimension of persistence modules makes this direct approach infeasible. We show that by exploiting the additivity of the HN filtration and the special central charges, one can get away with a brute-force approach. For $d$-parameter modules, this produces an FPT $\varepsilon$-approximate algorithm with runtime dominated by $O( 1/\varepsilon^d \cdot T_{\mathsc{dec}})$, where $T_{\mathsc{dec}}$ is the time for decomposition, which we compute with \textsc{aida} [DJK25]. We show that the wall-and-chamber structure of the module can be computed via lower envelopes of degree $d - 1$ polynomials. This allows for an exact computation of the Skyscraper Invariant whose runtime is roughly $O(n^d \cdot T_{\mathsc{dec}})$ for $n$ the size of the presentation of the modules and enables a faster hybrid algorithm to compute an approximation. For 2-parameter modules, we have implemented not only our algorithms but also, for the first time, Cheng's algorithm. We compare all algorithms and, as a proof of concept for data analysis, compute a filtered version of the Multiparameter Landscape for biomedical data.