@inproceedings{5bf7dc95a6d24987a4df43afe34977e8,
title = "A Data Structure for Monomial Ideals with Applications to Signature Gr{\"o}bner Bases",
abstract = "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{\"o}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.",
keywords = "data structures, Gr{\"o}bner bases, monomial ideals, signatures, symbolic computation",
author = "Pierre Lairez and Rafael Mohr and Th{\'e}o Ternier",
note = "Publisher Copyright: {\textcopyright} 2026 Copyright held by the owner/author(s).; International Symposium on Symbolic and Algebraic Computation, ISSAC 2026 ; Conference date: 13-07-2026 Through 17-07-2026",
year = "2026",
month = jul,
day = "12",
doi = "10.1145/3815436.3815473",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "246--255",
editor = "Christoph Koutschan and Alin Bostan and Clement Pernet and Vu, \{Thi Xuan\}",
booktitle = "ISSAC 2026 - Proceedings of the 2026 International Symposium on Symbolic and Algebraic Computation",
}