Magma supports left-sided, right-sided, and two-sided ideals of free algebras. In general, there are not many operations applicable to single-sided ideals: quotients are supported only in the case of two-sided ideals.
Within the general context of fp-algebras, the term "basis" will refer to an ordered sequence of polynomials which generate an ideal. (Thus a basis may contain duplicates and zero elements so it is dissimilar to a basis of a vector space.)
Given a free algebra A over a field K, return the two-sided (ideal), left-sided (lideal), or right-sided (rideal) of A generated by the elements of A specified by the list L. Each term of the list L must be an expression defining an object of one of the following types:
- (a)
- An element of A;
- (b)
- A set or sequence of elements of A;
- (c)
- An ideal of A;
- (d)
- A set or sequence of ideals of A.
Given an ideal I, return the current basis of I. If a Gröbner basis of I has been computed, that is returned.
Given an ideal I together with an integer i, return the i-th element of the current basis of I. This the same as Basis(I)[i].
Gröbner bases (GBs) may be computed for any kind of ideal (left-, right-, or two-sided), but for single-sided ideals, the GBs are generally weak (i.e., they rarely differ much from the original generators of the ideals).
Unfortunately, the GB of a given ideal may not be finite. Thus the Buchberger or F4 algorithms below will run forever in such cases. One can interrupt any GB computation by pressing Ctrl-C. Alternatively, the function GroebnerBasis(S,d) below, which creates a truncated degree-d Gröbner basis, can be used to set a limit on the degrees of the pairs considered, so the computation will always terminate.
As in the commutative case, when Magma constructs a GB G of an ideal I, then G is always the unique sorted minimal reduced GB of I. Before this happens, an ideal will usually possess a basis which is not a Gröbner basis, but that will be changed into the unique Gröbner basis when the GB is computed. Thus the original basis will be discarded. See the procedure Groebner below for details on the algorithms available.
The unique Gröbner basis will be computed automatically when necessary; the Groebner procedure below simply allows control of the algorithms used to compute the Gröbner basis.
(Procedure.) Explicitly force a Gröbner basis (GB) for I to be constructed. This procedure is normally not necessary, as Magma will automatically compute the GB when needed, but it does allow one to control how the GB is constructed.Faugere: BoolElt Default: trueMagma has two algorithms for computing noncommutative GBs:
If the parameter Faugere is set to true, then the Faugère F4 algorithm will be used (if the field is a finite field or the rational field); otherwise the Buchberger algorithm is used.
- (1)
- A noncommutative generalization (due to Allan Steel) of the Faugère F4 algorithm [Fau99], which works by specialized sparse linear algebra and is applicable to two-sided ideals defined over a finite field or the rational field;
- (2)
- The noncommutative Buchberger algorithm [CLO96, Chap. 2, Para 7] for ideals defined over any field.
The current implementation of the Faugère algorithm is usually very much faster than the Buchberger algorithm and usually does not take much more memory, so that it is why it is selected by default. However, there may be examples for which it may be more desirable to use the Buchberger algorithm (particularly to save some memory).
Given an ideal I, force the Gröbner basis of I to be computed, and then return that. The parameters are the same as those for the procedure Groebner.
Given a set or sequence S of polynomials, return the unique Gröbner basis of the two-sided ideal generated by S as a sorted sequence. This function is useful for computing Gröbner bases without the need to construct ideals. The parameters are the same as those for the procedure Groebner. See also the function GroebnerBasis(S,d) below, which creates a truncated degree-d Gröbner basis.
Given a set or sequence S of polynomials, return the degree-d Gröbner basis of the ideal generated by S, which is the truncated Gröbner basis obtained by ignoring S-polynomial pairs whose total degree is greater than d.If the ideal is homogeneous, then it is guaranteed that the result is equal to the set of all polynomials in the full Gröbner basis of the ideal whose total degree is less than or equal to d, and a polynomial whose total degree is less than or equal to d is in the ideal if and only if its normal form with respect to this truncated basis is zero. But if the ideal is not homogeneous, these last properties may not hold, but it may still be useful to construct the truncated basis.
The parameters are the same as those for the procedure Groebner.
This subsection describes the verbose flags available for the Gröbner basis algorithms. There are separate verbose flags for each algorithm (Buchberger, etc.), but the all-encompassing verbose flag Groebner includes all these flags implicitly.
For each procedure provided for setting one of these flags, the value false is equivalent to level 0 (nothing), and true is equivalent to level 1 (minimal verbosity). For each Set- procedure, there is also a corresponding Get- function to return the value of the corresponding flag.
(Procedure.) Change the verbose printing level for all Gröbner basis algorithms to be v. This includes all of the algorithms whose verbosity is controlled by flags subsequently listed, as well as some other minor related algorithms. Currently the legal levels are 0, 1, 2, 3, or 4. One would normally set this flag to 1 for minimal verbosity for Gröbner basis-type computations, and possibly also set one or more of the following flags to levels higher than 1 for more verbosity.
(Procedure.) Change the verbose printing level for the Buchberger algorithm to be v. Currently the legal levels are 0, 1, 2, 3, or 4. If the value w of the Groebner verbose flag is greater than v, then w is taken to be the current value of this flag.
(Procedure.) Change the verbose printing level for the Faugère algorithm to be v. Currently the legal levels are 0, 1, 2, or 3. If the value w of the Groebner verbose flag is greater than v, then w is taken to be the current value of this flag.
The following functions and procedures perform operations related to Gröbner bases.
(Procedure.) Given an ideal I, mark the current basis of I to be the Gröbner basis of the ideal with respect to the monomial order of the ideal. Note that the current basis must exactly equal the unique (reverse) sorted minimal reduced Gröbner basis for the ideal, as returned by the function GroebnerBasis. This procedure is useful when one creates an ideal with a basis known to be the Gröbner basis of the ideal from a previous computation or for other reasons. If the basis is not the unique Gröbner basis, the results are unpredictable.
Given a set or sequence S of polynomials, return the sequence consisting of the reduction of S. The reduction is obtained by reducing to normal form each element of S with respect to the other elements and sorting the resulting non-zero elements left. Note that all Gröbner bases returned by Magma are automatically reduced so that this function would usually only be used just to simplify a set or sequence of polynomials which is not a Gröbner basis.
> K := RationalField();
> F<x,y,z> := FreeAlgebra(K, 3);
> B := [x^2 - y*z, x*y - y*z, y*x - z^2, y^3 - x*z];
> I := lideal<F | B>;
> I;
Left ideal of Finitely presented algebra of rank 3 over Rational Field
Non-commutative Graded Lexicographical Order
Variables: x, y, z
Basis:
[
x^2 - y*z,
x*y - y*z,
y*x - z^2,
y^3 - x*z
]
> GroebnerBasis(I);
[
y^3 - x*z,
x^2 - y*z,
x*y - y*z,
y*x - z^2
]
> I := rideal<F | B>;
> GroebnerBasis(I);
[
y^3 - x*z,
x^2 - y*z,
x*y - y*z,
y*x - z^2
]
> I := ideal<F | B>;
> Groebner(I);
> I;
Two-sided ideal of Finitely presented algebra of rank 3 over Rational Field
Non-commutative Graded Lexicographical Order
Variables: x, y, z
Groebner basis:
[
y*z^2*y - y*z^2,
y*z^3 - y*z^2,
z*y*z^2 - y*z^2,
z^2*y^2 - y*z^2,
z^2*y*z - y*z^2,
z^3*y - y*z^2,
z^4 - y*z^2,
x*z*x - y*z^2,
x*z*y - z^3,
x*z^2 - y*z^2,
y^3 - x*z,
y^2*z - z^2*y,
y*z*x - y*z^2,
y*z*y - y*z^2,
z^2*x - z^2*y,
x^2 - y*z,
x*y - y*z,
y*x - z^2
]
> NormalForm(x*y, I);
y*z
> NormalForm(y*x, I);
z^2
Finally, we compute some truncated bases of the two-sided ideal.
For degree 2, the truncated GB has no new polynomials while for degree 3,
some are added. Only at degree 5 do we obtain the full GB.
> GroebnerBasis(B, 2);
[
y^3 - x*z,
x^2 - y*z,
x*y - y*z,
y*x - z^2
]
> GroebnerBasis(B, 3);
[
x*z^2 - y*z^2,
y^3 - x*z,
y^2*z - z^2*y,
y*z*x - y*z^2,
y*z*y - y*z^2,
z^2*x - z^2*y,
x^2 - y*z,
x*y - y*z,
y*x - z^2
]
> #GroebnerBasis(I);
18
> #GroebnerBasis(B, 4);
16
> #GroebnerBasis(B, 5);
18
> GroebnerBasis(B, 5) eq GroebnerBasis(I);
true