A data structure for monomial ideals with applications to signature Gröbner bases
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914554900905984 |
|---|---|
| author | Lairez, Pierre Mohr, Rafael Ternier, Théo |
| author_facet | Lairez, Pierre Mohr, Rafael Ternier, Théo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05026 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A data structure for monomial ideals with applications to signature Gröbner bases Lairez, Pierre Mohr, Rafael Ternier, Théo Symbolic Computation Data Structures and Algorithms 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. |
| title | A data structure for monomial ideals with applications to signature Gröbner bases |
| topic | Symbolic Computation Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.05026 |