Comprehensive Gröbner bases
type: Item
instance of: scholarly article
title: Comprehensive Gröbner bases
zbMATH Open document ID: 0784.13013
DOI: 10.1016/0747-7171(92)90023-W
author: Volker Weispfenning
published in: Journal of Symbolic Computation
publication date: 1993-01-16T00:00:00Z
review text: The method of Gröbner bases is one of the fundamental algorithmic tools in polynomial algebra and algebraic geometry. The construction of a Gröbner basis of the ideal generated by a finite set of polynomials is very unstable under variation of the coefficients of the input polynomials. With the aim of solving parametric problems, the author introduces the notion of a ``comprehensive Gröbner basis'': Let \(K\) be an integral domain and \(S\) be the polynomial ring \(K[U_ 1,\ldots,U_ m;X_ 1,\ldots,X_ n]\). Given a finite set \(F\subseteq S\) and a term order \(\leq\) in the main variables \(X_ 1,\ldots,X_ n\), a comprehensive Gröbner basis \(G\) of the ideal \(Id(F)\) is a finite ideal basis of \(Id(F)\) that is a Gröbner basis of \(Id(F)\) in \(K'[X_ 1,\ldots,X_ n]\) (with respect to the term order \(\leq)\), for every specialization of the parameters \(U_ 1,\ldots,U_ m\) in an arbitrary field \(K'\). The main result of the paper is an explicit algorithmic construction over a computable ring \(K\) of a comprehensive Gröbner basis \(G\) from any finite set \(F\) and any decidable term order \(\leq\). The author shows that this construction can be performed with the same worst case degree bounds in the main variables as for ordinary Gröbner bases and presents some examples computed in an ALDES/SAC-2 implementation. Applications of comprehensive Gröbner bases are given to several parametric problems in polynomial algebra and algebraic geometry; in particular, to ``fast'' elimination of quantifier blocks in algebraically closed fields.
reviewed by: Alicia Dickenstein
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 13F20
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 14Q20
zbMATH DE Number: 94726
zbMATH Keywords: polynomial ideal
zbMATH Keywords: comprehensive Gröbner basis
zbMATH Keywords: fast elimination of quantifier blocks
MaRDI profile type: Publication
cites work: An extension of Buchberger's algorithm and calculations in enveloping fields of Lie algebras
cites work: Some examples for solving systems of algebraic equations by calculating Gröbner bases
cites work: Q3714165
cites work: Q3798767
cites work: Q3952057
cites work: Real quantifier elimination is doubly exponential
cites work: Q3033873
cites work: Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
cites work: Properties of Gröbner bases under specializations
cites work: Q3033872
cites work: Q3710617
cites work: Solving systems of algebraic equations by using gröbner bases
cites work: Non-commutative Gröbner bases in algebras of solvable type
cites work: Computing dimension and independent sets for polynomial ideals
cites work: Q3678669
cites work: New constructive methods in classical ideal theory
cites work: Q3808248
cites work: Q3804185
cites work: The Gröbner fan of an ideal
cites work: Q3708893
cites work: Q3813151
cites work: An extension of buchberger's algorithm to compute all reduced gröbner bases of a polynomial ideal
cites work: Stability of Gröbner bases
cites work: Q5776125
cites work: Admissible orders and linear forms
cites work: Q3801690
cites work: Q3470575
cites work: Gröbner bases for polynomial ideals over commutative regular rings
description: scientific article; zbMATH DE number 94726