A new iterative algorithm for comprehensive Gröbner systems

Anna Maria Bigatti; Elisa Palezzato; Michele Torielli

doi:10.1007/s00200-025-00684-8

A new iterative algorithm for comprehensive Gröbner systems

Anna Maria Bigatti, Elisa Palezzato, Michele Torielli

Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

Abstract

A comprehensive Gröbner system for a parametric ideal I in K(A)[X] represents the collection of all Gröbner bases of the ideals I′ in K[X] obtained as the values of the parameters A vary in K. The recent algorithms for computing them consider the corresponding ideal J in K[A, X], and are based on stability of Gröbner bases of ideals under specializations of the parameters A. Starting from a Gröbner basis of J, the computation splits recursively depending on the vanishing of the evaluation of some “coefficients” in K[A]. In this paper, taking inspiration from the algorithm described by Nabeshima, we create a new iterative algorithm to compute comprehensive Gröbner systems. We show how we keep track of the sub-cases to be considered, and how we avoid some redundant computation branches using “comparatively-cheap” ideal-membership tests, instead of radical-membership tests.

Original language	English (US)
Journal	Applicable Algebra in Engineering, Communications and Computing
DOIs	https://doi.org/10.1007/s00200-025-00684-8
State	Accepted/In press - 2025

Keywords

Algorithm
Comprehensive Gröbner systems
Gröbner basis
Radical membership

ASJC Scopus subject areas

Algebra and Number Theory
Applied Mathematics

Access to Document

10.1007/s00200-025-00684-8

Cite this

@article{e03f32e231e746f59e06b70ed4f438d7,

title = "A new iterative algorithm for comprehensive Gr{\"o}bner systems",

abstract = "A comprehensive Gr{\"o}bner system for a parametric ideal I in K(A)[X] represents the collection of all Gr{\"o}bner bases of the ideals I′ in K[X] obtained as the values of the parameters A vary in K. The recent algorithms for computing them consider the corresponding ideal J in K[A, X], and are based on stability of Gr{\"o}bner bases of ideals under specializations of the parameters A. Starting from a Gr{\"o}bner basis of J, the computation splits recursively depending on the vanishing of the evaluation of some “coefficients” in K[A]. In this paper, taking inspiration from the algorithm described by Nabeshima, we create a new iterative algorithm to compute comprehensive Gr{\"o}bner systems. We show how we keep track of the sub-cases to be considered, and how we avoid some redundant computation branches using “comparatively-cheap” ideal-membership tests, instead of radical-membership tests.",

keywords = "Algorithm, Comprehensive Gr{\"o}bner systems, Gr{\"o}bner basis, Radical membership",

author = "Bigatti, {Anna Maria} and Elisa Palezzato and Michele Torielli",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2025.",

year = "2025",

doi = "10.1007/s00200-025-00684-8",

language = "English (US)",

journal = "Applicable Algebra in Engineering, Communications and Computing",

issn = "0938-1279",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - A new iterative algorithm for comprehensive Gröbner systems

AU - Bigatti, Anna Maria

AU - Palezzato, Elisa

AU - Torielli, Michele

N1 - Publisher Copyright: © The Author(s) 2025.

PY - 2025

Y1 - 2025

N2 - A comprehensive Gröbner system for a parametric ideal I in K(A)[X] represents the collection of all Gröbner bases of the ideals I′ in K[X] obtained as the values of the parameters A vary in K. The recent algorithms for computing them consider the corresponding ideal J in K[A, X], and are based on stability of Gröbner bases of ideals under specializations of the parameters A. Starting from a Gröbner basis of J, the computation splits recursively depending on the vanishing of the evaluation of some “coefficients” in K[A]. In this paper, taking inspiration from the algorithm described by Nabeshima, we create a new iterative algorithm to compute comprehensive Gröbner systems. We show how we keep track of the sub-cases to be considered, and how we avoid some redundant computation branches using “comparatively-cheap” ideal-membership tests, instead of radical-membership tests.

AB - A comprehensive Gröbner system for a parametric ideal I in K(A)[X] represents the collection of all Gröbner bases of the ideals I′ in K[X] obtained as the values of the parameters A vary in K. The recent algorithms for computing them consider the corresponding ideal J in K[A, X], and are based on stability of Gröbner bases of ideals under specializations of the parameters A. Starting from a Gröbner basis of J, the computation splits recursively depending on the vanishing of the evaluation of some “coefficients” in K[A]. In this paper, taking inspiration from the algorithm described by Nabeshima, we create a new iterative algorithm to compute comprehensive Gröbner systems. We show how we keep track of the sub-cases to be considered, and how we avoid some redundant computation branches using “comparatively-cheap” ideal-membership tests, instead of radical-membership tests.

KW - Algorithm

KW - Comprehensive Gröbner systems

KW - Gröbner basis

KW - Radical membership

UR - http://www.scopus.com/inward/record.url?scp=105001493181&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=105001493181&partnerID=8YFLogxK

U2 - 10.1007/s00200-025-00684-8

DO - 10.1007/s00200-025-00684-8

M3 - Article

AN - SCOPUS:105001493181

SN - 0938-1279

JO - Applicable Algebra in Engineering, Communications and Computing

JF - Applicable Algebra in Engineering, Communications and Computing

ER -

A new iterative algorithm for comprehensive Gröbner systems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this