Documentation Center |
Computation of a reduced Gröbner basis
This functionality does not run in MATLAB.
groebner::gbasis(polys, <order>, options)
groebner::gbasis(polys) computes a reduced Gröbner basis of the ideal generated by the polynomials in the list polys.
The rules laid down in the introduction to the groebner package concerning the polynomial types and the ordering apply.
The polynomials in the list polys must all be of the same type. In particular, do not mix polynomials created via poly and polynomial expressions!
The ordering strategy indicated by Reorder is used automatically when polynomial expressions are used.
We demonstrate the effect of various input formats. First, we use polynomial expressions to define the polynomial ideal. The Gröbner basis is returned as a list of polynomial expressions:
groebner::gbasis([x^2 - y^2, x^2 + y], LexOrder)
Next, the same polynomials are defined via poly. Note that poly fixes the ordering of the variables.
groebner::gbasis([poly(x^2 - y^2, [x, y]), poly(x^2 + y, [x, y])], LexOrder)
Changing the ordering of the variables in poly changes the lexicographical ordering. This results in a different basis:
groebner::gbasis([poly(x^2 - y^2, [y, x]), poly(x^2 + y, [y, x])], LexOrder)
With Reorder the ordering of the variables may be changed internally:
groebner::gbasis([poly(x^2 - y^2, [x, y]), poly(x^2 + y, [x, y])], LexOrder, Reorder)
Polynomials over arbitrary fields are allowed. In particular, you can use the field of rational functions in some given variable(s):
F := Dom::Fraction(Dom::DistributedPolynomial([y])): F::Name := "Q(y)": groebner::gbasis( [poly(y*z^2 + 1, [x, z], F), poly((y^2 + 1)*x^2 - y - z^3, [x, z], F)])
delete F:
polys |
A list or set of polynomials or polynomial expressions of the same type. The coefficients in these polynomials and polynomial expressions can be arbitrary arithmetical expressions. If polys are polynomials over an arbitrary domain, then their coefficients must be domain elements and the domain must be a field. |
order |
One of the identifiers DegInvLexOrder, DegreeOrder, and LexOrder, or a user-defined term ordering of type Dom::MonomOrdering. The default ordering is DegInvLexOrder. |
Factor |
With this option, groebner::gbasis returns a set of lists, such that each list is the Gröbner basis of an ideal. The union of these ideals is a superset of the ideal given as input, and a subset of the radical of that ideal. In other words, it has the same variety (only the multiplicity of points can change). |
IgnoreSpecialCases |
With this option, groebner::gbasis handles all coefficients in all intermediate results as nonzero unless these coefficients are equal to zero for all parameter values. In other words, if the coefficients are rational functions of the free parameters, then results are correct on all of the parameter space except on an algebraic variety of lower dimension. |
Reorder |
With this option groebner::gbasis internally may change the lexicographical ordering of variables to decrease running time. With this option the variables are sorted internally such that they have a "heuristic optimal" ordering. Consequently, the ordering of the variables in the output polynomials may differ from their ordering in the input polynomials. For details on the ordering strategy, see W. Boege, R. Gebauer und H. Kredel: "Some Examples for Solving Systems of Algebraic Equations by Calculating Groebner Bases" im J. Symbolic Comp. (1986) Vol. 1, 83-98. Re-ordering is always applied when polynomial expressions are used for input. |
Monic |
Option, specified as Monic = N This option sets the normalizing routine to N. For every polynomial f in the polynomial ring, N(f, o) must return some associate of f, where o is the chosen order. The method N should be chosen such that it produces simple output. By default, polylib::primpart is used for polynomials with integer coefficients; other polynomials are divided by their leading coefficient. |
Order |
Option, specified as Order = order This option is equivalent to passing order as an argument. |
List of polynomials. The output polynomials have the same type as the polynomials of the input list.
In most cases, groebner::gbasis computes the basis via the Buchberger algorithm with the "sugar" selection strategy being used.
For general information, see T. Becker and V. Weispfenning: "Gröbner Bases", Springer (1993). For details on the sugar selection strategy, see A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. Traverso: "One sugar cube, please — or Selection strategies in the Buchberger algorithm", Proc. ISSAC '91, Bonn, 49-54 (1991).