A data structure for monomial ideals with applications to signature Gröbner bases
For researchers working on computational commutative algebra and Gröbner basis algorithms, this provides a more efficient data structure for monomial ideal operations, leading to faster computations.
The paper introduces monomial divisibility diagrams (MDDs), a data structure for monomial ideals that supports fast membership tests and insertion. Integrating MDDs into the signature Gröbner basis implementation in AlgebraicSolving.jl yields substantial speed-ups compared to existing list-based representations.
We introduce monomial divisibility diagrams (MDDs), a data structure for monomial ideals that supports insertion of new generators and fast membership tests. MDDs stem from a canonical tree representation by maximally sharing equal subtrees, yielding a directed acyclic graph. We establish basic complexity bounds for membership and insertion, and study empirically the size of MDDs. As an application, we integrate MDDs into the signature Gröbner basis implementation of the Julia package AlgebraicSolving.jl. Membership tests in monomial ideals are used to detect some reductions to zero, and the use of MDDs leads to substantial speed-ups compared to the existing representation by lists of generators with divmasks.