Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology

Motivated by applications to topological data analysis, we give an efficient algorithm for computing a (minimal) presentation of a bigraded \(K[x,y]\)-module \(M\), where \(K\) is a field. The algorithm takes as input a short chain complex of free modules \(\displaystyle F_2\xrightarrow{\partial_2} F_1 \xrightarrow{\partial_1} F_0\) such that \(M\cong \ker{\partial_1}/\im{\partial_2}\). It runs in time \(O(\sum_i |F_i|^3)\) and requires \(O(\sum_i |F_i|^2)\) memory, where \(|F_i|\) denotes the size of a basis of \(F_i\). We observe that, given the presentation computed by our algorithm, the bigraded Betti numbers of \(M\) are readily computed. These algorithms have been implemented in RIVET, a software tool for the visualization and analysis of two-parameter persistent homology. In experiments on topological data analysis problems, our approach outperforms the standard computational commutative algebra packages Singular and Macaulay2 by a wide margin.