×
Weispfenning, Volker

Comprehensive Gröbner bases. (English) Zbl 0784.13013

J. Symb. Comput. 14, No. 1, 1-29 (1992).
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.
Reviewer: A.Dickenstein (Buenos Aires)

Cited in 10 Reviews
Cited in 75 Documents

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
68W30 Symbolic computation and algebraic computation
14Q20 Effectivity, complexity and computational aspects of algebraic geometry

Keywords:

polynomial ideal; comprehensive Gröbner basis; fast elimination of quantifier blocks
PDF BibTeX XML Cite
\textit{V. Weispfenning}, J. Symb. Comput. 14, No. 1, 1--29 (1992; Zbl 0784.13013)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Apel, J.; Lassner, W., An extension of Buchberger’s algorithm and calculations in enveloping fields of Lie algebras, J. Symb. Comp, 6, 361-370 (1988) · Zbl 0663.68044
[2] Böge, W.; Gebauer, R.; Kredel, H., Some examples for solving systems of algebraic equations by calculating Gröbner bases, J. Symb. Comp, 1, 83-98 (1986) · Zbl 0602.65032
[3] Buchberger, B., Gröbner bases: An algorithmic method in polynomial ideal theory, (Bose, N. K., Recent Trends in Multidimensional System Theory (1985), Reidel Publ. Comp), chap. 6 · Zbl 0587.13009
[4] Buchberger, B., Application of Gröbner bases in non-linear computational geometry, (Janssen, R., Trends in Computer Algebra, vol. 296 (1987), Springer LNCS), 52-80
[5] Buchberger, B., Gröbner bases and generalized Sylvester matrices (1988), Universität Linz, unpublished notes
[6] (Buchberger, B.; Collins, G. E.; Loos, R., Computer Algebra, Symbolic abd Algebraic Computation (1982/1983), Springer Verlag) · Zbl 0491.00019
[7] Davenport, J. H.; Heintz, J., Real quantifier elimination is doubly exponential, J. Symb. Comp, 5, 29-36 (1988) · Zbl 0663.03015
[8] Faas, W., Implementierung eines Algorithmus zur Berechnung umfassender Gröbner basen unter Scratchpad II, (Diploma thesis (1992), University of Passau)
[9] Ferro, A.; Gallo, G., Gröbner bases, Ritt’s algorithm and decision procedures for algebraic theories, (Huguet, L.; Poli, A., Proc. AAECC-5, Menorca, 1987, vol. 356 (1988), Springer LNCS), 230-237
[10] Fitchas, N.; Galligo, A., Nullstellensatz effectif et conjecture de Serre (theoreme de Quillen-Suslin) pour le calcul formel, Mathem, Nachrichten, 149, 231-253 (1990) · Zbl 0729.14001
[11] Gianni, P., Properties of Gröbner bases under specialization, (Davenport, J. H., EUROCAL ’87, vol. 378 (1989), Springer LNCS), 293-297 · Zbl 1209.13033
[12] Gianni, P.; Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases, (Huguet, L.; Poli, A., Proc. AAECC-5, Menorca, 1987, vol. 356 (1988), Springer LNCS), 247-257
[13] Giusti, M., Some effectivity problems in polynomial ideal theory, (Fitch, J., EUROSAM ’84, vol. 174 (1984), Springer LNCS), 159-171 · Zbl 0585.13010
[15] Kandri-Rody, A.; Weispfenning, V., Non-commutative Gröbner in algebras of solvable type, J. Symb. Comp, 9, 1-26 (1990) · Zbl 0715.16010
[16] Kredel, H.; Weispfenning, V., Computing dimension and independent sets for polynomial ideals, J. Symb. Comp, 6, 231-248 (1988) · Zbl 0665.68024
[17] Kredel, H.; Weispfenning, V., Parametric Gröbner bases in rings of solvable type, (Proc. IV. International Conference on Computer Algebra in Physical Research, Joint Institute for Nuclear Research Dubna. Proc. IV. International Conference on Computer Algebra in Physical Research, Joint Institute for Nuclear Research Dubna, USSR, May 1990 (1991), World Scientific: World Scientific Singapore), 236-244
[18] Möller, H. M.; Mora, T., Upper and lower bounds for the degree of Gröbner bases, (Fitch, J., EUROSAM 84, vol. 174 (1984), Springer LNCS), 172-183
[19] Möller, H. M.; Mora, T., New constructive methods in classical ideal theory, J. of Algebra, 100, 138-178 (1986) · Zbl 0621.13007
[20] Mora, T., Gröbner bases for non-commutative polynomial rings, (Calmet, J., Proc. AAECC-3, Grenoble, 1985, vol. 229 (1986), Springer LNCS), 353-362
[21] Mora, T., Standard bases and non-Noetherianity: Non-commutative polynomial rings, (Beth, Th.; Clausen, M., Proc. AAECC-4, Karlsruhe, 1986, vol. 307 (1988), Springer LNCS), 98-109
[22] Mora, T.; Robbiano, L., The Gröbner Fan of an ideal, J. Symb. Comp, 6, 183-208 (1988) · Zbl 0668.13017
[23] Rabin, M. O., Decidable theories, (Barwise, J., Handbook of Mathematical Logic (1977), North-Holland), 595-630
[24] Robbiano, L., Term orderings on the polynomial ring, (Caviness, B. F., EUROCAL ’85, vol. 204 (1985), Springer LNCS), 513-517
[25] Rump, S. M., Algebraic computation, numerical computation and verified inclusions, (Janssen, R., Trends in Computer Algebra, vol. 296 (1987), Springer LNCS), 177-197
[26] Schmmel, K.-P., An extension of Buchberger’s algorithm to compute all reduced Gröbner bases of a polynomial ideal, (Davenport, J. H., EUROCAL ’87, vol. 378 (1989), Springer LNCS), 300-310 · Zbl 1209.13008
[27] Schönfeld, E., Parametrische Gröbnerbasen im Computeralgebra System ALDES/SAC-2, (Diploma thesis (1991), University of Passau)
[28] Schwartz, N., Stability of Gröbner bases, J. pure and appl. Algebra, 53, 171-186 (1988) · Zbl 0664.13006
[29] van der Waerden, B. L., (Moderne Algebra, Teil II (1940), Springer Verlag) · Zbl 0022.29801
[30] Weispfenning, V., Admissible orders and linear forms, ACM SIGSAM Bulletin, 21, 2, 16-18 (1987) · Zbl 0655.13017
[31] Weispfenning, V., Some bounds for the construction of Gröbner bases, 1987, (Beth, Th.; Clausen, M., Proc. AAECC-4, Karlsruhe, 1986, vol. 307 (1988), Springer LNCS), 195-201
[32] Weispfenning, V., Constructing Universal Gröbner bases, (Huguet, L.; Poli, A., Proc. AAECC-5, Menorca, 1987, vol. 356 (1989), Springer LNCS), 408-417
[33] Weispfenning, V., Gröbner bases in polynomial rings over commutative regular rings, (Davenport, J. H., EUROCAL ’87, vol. 378 (1989), Springer LNCS), 336-347 · Zbl 1209.13036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.