|
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.)
lideal<A | L> : AlgFr, List -> AlgFr
rideal<A | L> : AlgFr, List -> AlgFr
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.
Groebner(I: parameters) : AlgFr ->
(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: true
Magma has two algorithms for computing noncommutative GBs:
- (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.
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.
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).
GroebnerBasis(I: parameters) : AlgFr -> AlgFrElt
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.
GroebnerBasis(S: parameters) : { AlgFrElt } -> [ AlgFrElt ]
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.
GroebnerBasis(S, d: parameters) : [ AlgFr ], RngInt -> AlgFrElt
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.
Reduce(S) : [ AlgFrElt ] -> [ AlgFrElt ]
Reduce(S) : { AlgFrElt } -> [ AlgFrElt ]
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.
For a certain sequence B of noncommutative polynomials, we create the
left-, right- and two-sided ideals generated by B. We note that for
the first two cases, the GB is no different from B, but for the two-sided
case, the GB contains several more elements.
> 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|