A new data structure for monomial ideals with applications in various domains of algebra
par
318
Efficient computations with monomial ideals, ideals only generated by monomials, often rely on two recurring tasks: inserting new generators and performing fast membership tests. Monomial divisibility diagrams (MDDs) are introduced as a new data structure that supports these operations. Starting from a canonical tree representation, identical subtrees are maximally shared, yielding a compact directed acyclic graph. This data structure leads to applications in several areas of algebra. Firstly, MDDs are integrated into the signature Gröbner basis implementation of the Julia package AlgebraicSolving.jl, where membership tests detect reductions to zero and provide substantial speed-ups. In this setting, maximal sharing often produces small MDDs. Secondly, MDDs support Hilbert series computations by enabling efficient counting of monomials outside a given monomial ideal. Thirdly, the same structure provides a new approach for computing irreducible components of monomial ideals.