SIAM Journal on Applied Algebra and Geometry · 2022 · 41 citations · 36 references
Natural SciencesComputer ScienceMathematicsAlgorithmsComputational GeometryTopologyGroup TheoryHomological AlgebraHomology TheoryKnot TheoryBetti NumbersComputable PresentationsHomologyHomology ComputationKernel ModulesPersistent CohomologyPersistent HomologyTopological Data Structures
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 $X\xrightarrow{f} Y \xrightarrow{g} Z$ such that $M\cong \ker{g}/\operatorname{im}{f}$. It runs in time $O(|X|^3+|Y|^3+|Z|^3)$ and requires $O(|X|^2+|Y|^2+|Z|^2)$ memory, where $|\cdot |$ denotes the rank. Given the presentation computed by our algorithm, the bigraded Betti numbers of $M$ are readily computed. Our approach is based on a simple matrix reduction algorithm, slight variants of which compute kernels of morphisms between free modules, minimal generating sets, and Gröbner bases. Our algorithm for computing minimal presentations has been implemented in RIVET, a software tool for the visualization and analysis of 2-parameter persistent homology. In experiments on topological data analysis problems, our implementation outperforms the standard computational commutative algebra packages Singular and Macaulay2 by a wide margin.
36
The Magma Algebra System I: The User Language
Wieb Bosma, John Cannon, Catherine Playoust · Journal of Symbolic Computation · 1997 · 7.4K citations
Commutative algebra with a view toward algebraic geometry
Choice Reviews Online · 1996 · 4.2K citations
Gunnar Carlsson · Bulletin of the American Mathematical Society · 2009 · 2.3K citations · Full text
Afra Zomorodian, Gunnar Carlsson · Discrete & Computational Geometry · 2004 · 1.6K citations · Full text