|
Magma incorporates an implementation of the Hilbert-driven
Buchberger Algorithm [Tra96].
This algorithm constructs the Gröbner basis
of an homogeneous ideal I whose Hilbert series is known. The algorithm
is often much more efficient than the conventional Buchberger algorithm
since knowledge of the Hilbert series eliminates many unnecessary reductions
of S-polynomials. The algorithm can also be used as an alternative
to the Gröbner Walk algorithm for changing order since one can compute the
Hilbert series of the ideal with respect to an easy monomial order, and then
start again with the Hilbert-driven algorithm to compute the Gröbner basis
with respect to the desired final order. Furthermore, the algorithm
can sometimes be used to test whether an ideal has a particular Hilbert series
and abort early if this is proven to be false.
The algorithm is also used extensively internally in the Invariant Theory
algorithms of Magma.
HilbertGroebnerBasis(S, N) : [ RngMPolElt ], RngUPolElt -> BoolElt, [ RngMPolElt ]
Let S be a set or sequence of homogeneous polynomials from the
multivariate polynomial ring P=K[x1, ..., xn], where K is a field,
and let I be the ideal of P generated by S.
Let either H be the Hilbert series HP/I(t) of I (as a rational
function in Z(t))
or let N∈Z[t] be a univariate integer polynomial
such that the weighted numerator of the Hilbert series of I is N.
This function attempts to construct the (reduced) Gröbner basis of I
using the given Hilbert series.
The weighted numerator of the Hilbert series of I is the Hilbert series
HP/I(t) of I, multiplied by the denominator
∏i=1n 1 - tdi, where di is the weighted degree of the
i-th variable xi (this denominator is thus (1 - t)n if P has
the default grading).
If the function returns false, then H (or N) cannot be the correct
Hilbert series (or weighted numerator of the Hilbert series) of I.
Otherwise, the function returns true and
a sequence B of polynomials which generates the same ideal as S; if
H or N is correct, B will be the (reduced) Gröbner basis of I.
In more detail, let fH be the power series
corresponding to the true Hilbert series of I
and let fN be the power series corresponding to
N/(∏i=1n 1 - tdi).
If fH = fN, then the function returns true and the correct
(reduced) Gröbner basis of I.
Otherwise, consider the first term at which fN and
fH differ: if the coefficient of fN is greater than that of fH, then
the function returns false (since it will not be able to construct the
extra Gröbner basis polynomials needed), otherwise the function will
return true with a partial Gröbner basis (since it concludes that it
has enough Gröbner basis polynomials when it hasn't).
Consequently, the algorithm is usually used when the correct Hilbert series
or weighted numerator of the Hilbert series is known,
or when there is a weighted numerator which
is known to be greater than or equal to the correct weighted numerator
of the Hilbert series.
Change verbose printing for the Hilbert-driven Buchberger algorithm to be v.
Currently the legal values for v are true, false, 0, or 1.
We illustrate a subalgorithm of the Invariant Theory module of
Magma which uses the Hilbert-driven Buchberger Algorithm.
Let R be the invariant ring of the (permutation) cyclic group G of order 4
over the field K = GF(2). Suppose we have a sequence L of 4 homogeneous
invariants of degrees 1, 2, 2, and 4 respectively. We wish to determine
efficiently whether the polynomials of L constitute primary invariants for
R. To check this, the ideal generated by L must be zero-dimensional
and the elements of L must be algebraically independent. This is equivalent
to the condition that the weighted numerator of the Hilbert series of the
ideal is the product (1 - t)(1 - t2)2(1 - t4). If that is not the
correct weighted numerator, it will be less than the correct weighted numerator
so the algorithm will return whether the polynomials L do
constitute primary invariants for R.
> K := GF(2);
> P<a,b,c,d> := PolynomialRing(K, 4);
> L := [
> a + b + c + d,
> a*b + a*d + b*c + c*d,
> a*c + b*d,
> a*b*c*d
> ];
> // Form potential Hilbert series weighted numerator
> T<t> := PolynomialRing(IntegerRing());
> N := &*[1 - t^Degree(f): f in L];
> N;
t^9 - t^8 - 2*t^7 + 2*t^6 + 2*t^3 - 2*t^2 - t + 1
> time l, B := HilbertGroebnerBasis(L, N);
Time: 0.000
> l;
true
> // Examine Groebner basis B of L:
> B;
[
a + b + c + d,
b^2 + d^2,
b*c + b*d + c^2 + c*d,
c^3 + c^2*d + c*d^2 + d^3,
d^4
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|