| Up | Next | Prev | PrevTail | Tail |
XIDEAL constructs Gröbner bases for solving the left ideal membership problem: Gröbner left ideal bases or GLIBs. For graded ideals, where each form is homogeneous in degree, the distinction between left and right ideals vanishes. Furthermore, if the generating forms are all homogeneous, then the Gröbner bases for the non-graded and graded ideals are identical. In this case, XIDEAL is able to save time by truncating the Gröbner basis at some maximum degree if desired.
The method of Gröbner bases in commutative polynomial rings introduced by Buchberger (e.g. [Buc85]) is a well-known and very important tool in polynomial ideal theory, for example in solving the ideal membership problem. XIDEAL extends the method to exterior algebras using algorithms from [HT93] and [Ape92].
There are two main departures from the commutative polynomial case. First, owing to the non-commutative product in exterior algebras, ideals are no longer automatically two-sided, and it is necessary to distinguish between left and right ideals. Secondly, because there are zero divisors, confluent reduction relations are no longer sufficient to solve the ideal membership problem: a unique normal form for every polynomial does not guarantee that all elements in the ideal reduce to zero. This leads to two possible definitions of Gröbner bases as pointed out by Stokes [Sto90].
XIDEAL constructs Gröbner bases for solving the left ideal membership problem: Gröbner left ideal bases or GLIBs. For graded ideals, where each form is homogeneous in degree, the distinction between left and right ideals vanishes. Furthermore, if the generating forms are all homogeneous, then the Gröbner bases for the non-graded and graded ideals are identical. In this case, XIDEAL is able to save time by truncating the Gröbner basis at some maximum degree if desired.
XIDEAL uses the exterior calculus package EXCALC of E. Schrüfer [Sch85a]
to provide the exterior algebra definitions. EXCALC is loaded automatically
with XIDEAL. The exterior variables may be specified explicitly, or extracted
automatically from the input polynomials. All distinct exterior variables in the input are
assumed to be linearly independent – if a dimension has been fixed (using the
EXCALC spacedim or coframe statements), then input containing distinct
exterior variables with degrees totaling more than this number will generate an
error.
xorder sets the term ordering for all other calculations. The syntax is
xorder k
where k is one of lex, gradlex or deglex. The lexicographical ordering lex is
based on the prevailing EXCALC kernel ordering for the exterior variables. The
EXCALC kernel ordering can be changed with the REDUCE korder or EXCALC
forder declarations. The graded lexicographical ordering gradlex puts terms with
more factors first (irrespective of their exterior degrees) and sorts terms of the same
grading lexicographically. The degree lexicographical ordering deglex takes
account of the exterior degree of the variables, putting highest degree first and
then sorting terms of the same degree lexicographically. The default ordering is
deglex.
It is possible to consider scalar and 0-form variables in exterior polynomials in two
ways: as variables or as coefficient parameters. This difference is crucial for Gröbner
basis calculations. By default, all scalar variables which have been declared as
0-forms are treated as exterior variables, along with any EXCALC kernels of
degree 0. This division can be changed with the xvars declaration. The syntax
is
xvars U,V,W,...
where the arguments are either kernels or lists of kernels. All variables specified in
the xvars declaration are treated as exterior variables in subsequent XIDEAL
calculations with exterior polynomials, and any other scalars are treated as parameters.
This is true whether or not the variables have been declared as 0-forms. The
declaration
xvars {}
causes all degree 0 variables to be treated as parameters, and
xvars nil
restores the default. Of course, \(p\)-form kernels with \(p\not =0\) are always considered as exterior
variables. The order of the variables in an xvars declaration has no effect on the
REDUCE kernel ordering or XIDEAL term ordering.
xideal calculates a Gröbner left ideal basis in an exterior algebra. The syntax
is
xideal(\(\langle \)S:list of forms\(\rangle \)[,\(\langle \)V:list of kernels\(\rangle \)][,\(\langle \)R:integer\(\rangle \)]) :list of forms.xideal calculates a Gröbner basis for the left ideal generated by \(\langle \)S\(\rangle \) using the current
term ordering. The resulting list can be used for subsequent reductions with xmod as
long as the term ordering is not changed. Which 0-form variables are to be regarded as
exterior variables can be specified in an optional argument \(\langle \)V\(\rangle \) (just like an xvars
declaration). The order of variables in \(\langle \)V\(\rangle \) has no effect on the term ordering. If the set of
generators \(\langle \)S\(\rangle \) is graded, an optional parameter \(\langle \)R\(\rangle \) can be given, and xideal produces a
truncated basis suitable for reducing exterior forms of degree less than or equal to \(\langle \)R\(\rangle \) in
the left ideal. This can save time and space with large problems, but the result
cannot be used for exterior forms of degree greater than \(\langle \)R\(\rangle \). The forms returned by
xideal are sorted in increasing order. See also the switches trxideal and
xfullreduction.
xmodideal reduces exterior forms to their (unique) normal forms modulo a left ideal.
The syntax is
xmodideal(\(\langle \)F:form\(\rangle \), \(\langle \)S:list of forms\(\rangle \)):form |
or |
xmodideal(\(\langle \)F:list of forms\(\rangle \), \(\langle \)S:list of forms\(\rangle \)) :list of forms. |
An alternative infix syntax is also available:
xmodideal(\(\langle \)F\(\rangle \),\(\langle \)S\(\rangle \)) first calculates a Gröbner basis for the left ideal generated by \(\langle \)S\(\rangle \), and
then reduces \(\langle \)F\(\rangle \). \(\langle \)F\(\rangle \) may be either a single exterior form, or a list of forms, and \(\langle \)S\(\rangle \) is a list of
forms. If \(\langle \)F\(\rangle \) is a list of forms, each element is reduced, and any which vanish are deleted
from the result. If the set of generators \(\langle \)S\(\rangle \) is graded, then a truncated Gröbner
basis is calculated using the degree of \(\langle \)F\(\rangle \) (or the maximal degree in \(\langle \)F\(\rangle \)). See also
trxmod.
xmod reduces exterior forms to their (not necessarily unique) normal forms modulo a
set of exterior polynomials. The syntax is
xmod(\(\langle \)F:form\(\rangle \), \(\langle \)S:list of forms\(\rangle \)):form |
or |
xmod(\(\langle \)F:list of forms\(\rangle \), \(\langle \)S:list of forms\(\rangle \)):list of forms. |
An alternative infix syntax is also available:
xmod\(\langle \)S\(\rangle \) .xmod(\(\langle \)F\(\rangle \),\(\langle \)S\(\rangle \)) reduces \(\langle \)F\(\rangle \) with respect to the set of exterior polynomials \(\langle \)S\(\rangle \), which is not
necessarily a Gröbner basis. \(\langle \)F\(\rangle \) may be either a single exterior form, or a list of forms, and
\(\langle \)S\(\rangle \) is a list of forms. This operator can be used in conjunction with xideal to produce
the same effect as xmodideal: for a single homogeneous form \(\langle \)F\(\rangle \) and a set of exterior
forms \(\langle \)S\(\rangle \), \(\langle \)F\(\rangle \) xmodideal\(\langle \)S\(\rangle \) is equivalent to \(\langle \)F\(\rangle \) xmodxideal(\(\langle \)S\(\rangle \),exdegree\(\langle \)F\(\rangle \)). See also
trxmod.
xauto autoreduces a set of exterior forms. The syntax is
xauto(\(\langle \)S:list of forms\(\rangle \)):list of forms.xauto\(\langle \)S\(\rangle \) returns a set of exterior polynomials which generate the same left ideal, but
which are in normal form with respect to each other. For linear expressions,
this is equivalent to finding the reduced row echelon form of the coefficient
matrix.
The operator excoeffs, with syntax
excoeffs(\(\langle \)F:form\(\rangle \)):list of expressionsreturns the coefficients from an exterior form as a list. The coefficients are always
scalars, but which degree 0 variables count as coefficient parameters is controlled by the
command xvars.
The operator exvars, with syntax
exvars(\(\langle \)F:form\(\rangle \)):list of kernelsreturns the exterior powers from an exterior form as a list. All non-scalar variables are
returned, but which degree 0 variables count as coefficient parameters is controlled by
the command xvars.
onxfullreduce allows xideal and xmodideal to calculate reduced, monic
Gröbner bases, which speeds up subsequent reductions, and guarantees a unique
form for the Gröbner basis. offxfullreduce turns of this feature, which
may speed up calculation of some Gröbner basis. xfullreduce is on by
default.
ontrxideal produces a trace of the calculations done by xideal and
xmodideal, showing the basis polynomials and the results of the critical element
calculations. This can generate profuse amounts of output. trxideal is off by
default.
ontrxmod produces a trace of reductions to normal form during calculations by
XIDEAL operators. trxmod is off by default.
Suppose XIDEAL has been loaded, the switches are at their default settings, and the following exterior variables have been declared:
pform x=0,y=0,z=0,t=0,f(i)=1,h=0,hx=0,ht=0;
In a commutative polynomial ring, a single polynomial is its own Gröbner basis. This is no longer true for exterior algebras because of the presence of zero divisors, and can lead to some surprising reductions:
xideal {d x^d y - d z^d t};
{d t^d z + d x^d y,
d x^d y^d z,
d t^d x^d y}
f(3)^f(4)^f(5)^f(6)
xmodideal {f(1)^f(2) + f(3)^f(4) + f(5)^f(6)};
0
The heat equation, \(h_{xx}=h_t\) can be represented by the following exterior differential system.
S := {d h - ht*d t - hx*d x,
d ht^d t + d hx^d x,
d hx^d t - ht*d x^d t};
xmodideal can be used to check that the exterior differential system is closed under
exterior differentiation.
d S xmodideal S;
{}
xvars, or a second argument to xideal can be used to change the division between
exterior variables of degree 0 and parameters.
xideal {a*d x+y*d y};
d x*a + d y*y
{---------------}
a
xvars {a};
xideal {a*d x+y*d y};
{d x*a + d y*y,d x^d y}
xideal({a*d x+y*d y},{a,y});
{d x*a + d y*y,
d x^d y*y}
xvars {}; % all 0-forms are coefficients
excoeffs(d u - (a*p - q)*d y);
{1, - a*p + q}
exvars(d u - (a*p - q)*d y);
{d u,d y}
xvars {p,q}; % p,q are no longer coefficients
excoeffs(d u - (a*p - q)*d y);
{ - a,1,1}
exvars(d u - (a*p - q)*d y);
{d y*p,d y*q,d u}
xvars nil;
Non-graded left and right ideals are no longer the same:
d t^(d z+d x^d y) xmodideal {d z+d x^d y};
0
(d z+d x^d y)^d t xmodideal {d z+d x^d y};
- 2*d t^d z
Any form containing a 0-form term generates the whole ideal:
xideal {1 + f(1) + f(1)^f(2) + f(2)^f(3)^f(4)};
{1}
| Up | Next | Prev | PrevTail | Front |
Hosted by