

last edited 6 years ago by Bill Page 
1 2 3 4 5 6 7 8  
Editor: Bill Page
Time: 2014/02/19 01:40:36 GMT+0 

Note: Parameters and Variables 
changed: m:List DMP(vars,param) := [x^2+y^2r1^2,(x+lab*ca)^2+(y+lab*sa)^2r2^2,(x+lac*(ca*cbsa*sb))^2+(y+lac*(sa*cb+ca*sb))^2r3^2,ca^2+sa^21] b := groebner(m); #b mm:List DMP(vars,param) := [x^2+y^2r1^2,(x+lab*ca)^2+(y+lab*sa)^2r2^2,(x+lac*(ca*cbsa*sb))^2+(y+lac*(sa*cb+ca*sb))^2r3^2,ca^2+sa^21] b := groebner(mm); #b
Adapted from Ideals, Varieties, and Algorithms Third Edition, 2007
Computer Algebra Systems
1 AXIOM
For us, the most important AXIOM commands are [normalForm]?, for doing the division algorithm, and [groebner]?, for computing a Groebner basis.
A distinctive feature of AXIOM is that every object has a specific type. In particular, this affects the way AXIOM works with monomial orders: an order is encoded in a special kind of type. For example, suppose we want to use lex order on with . This is done using the type:
DMP([x,y,z], FRAC INT)
(remember that AXIOM encloses a list inside brackets [...]).
Here DMP
stands for "Distributed Multivariate Polynomial", and
FRAC INT
means fractions of integers, i.e. rational numbers.
Similarly, grevlex for with means
using the type:
HDMP([x,y,z],FRAC INT)
where HDMP
stands for
"Homogeneous Distributed Multivariate Polynomial". At the end of
the section, we will explain how to get AXIOM to work with grlex
order.
To see how this works in practice, we will divide by and using grevlex order with . We first give the three polynomials names and declare their types:
f : HDMP([x,y], FRAC INT) := x^3+3*y^2
(1) 
g : HDMP([x,y], FRAC INT) := x^2+y
(2) 
h : HDMP([x,y], FRAC INT) := x+2*x*y
(3) 
(Here colon : indicates a type declaration. You can save typing by giving:
HDMP([x,y], FRAC INT)
a symbolic name.) Then the remainder is computed by the command:
normalForm(f,[g, h])
(4) 
The output is the remainder of f
on division by g
, h
. In
general the syntax of the command is:
normalForm(poly, polylist)
where poly
is the polynomial to be divided by the polynomials in
the list polylist
(assuming that everything has been declared to
be of the appropriate type).
To do the same computation using lex order with , first issue the command:
Lex := DMP([x,y], FRAC INT)
(5) 
to give:
DMP([x,y], FRAC INT)
the symbolic name Lex
, and then type:
normalForm(f::Lex,[g::Lex, h::Lex])
(6) 
Here, we are using AXIOM's type conversion facility ::
to convert
from one type to another.
The syntax for the groebner
command is:
groebner(polylist)
This computes a Groebner basis for the ideal generated by the
polynomials in polylist
(of the appropriate type). The answer
is reduced in the sense of Chapter 2, 7. For example,
if g
, h
are as above, then the command:
gb := groebner([g,h])
(7) 
computes a list (and gives it the symbolic name gb
) which is a
Groebner basis for the ideal
with respect to grevlex for . Also, if you want information
about the intermediate stages of the calculation, you can include
the options "redcrit" or "info" in the groebner
command. For
example, the command:
groebner([g,h], "redcrit")
reduced Critpair  Polynom :
2 1 y +  y 2
reduced Critpair  Polynom :
0
THE GROEBNER BASIS POLYNOMIALS
(8) 
will print out the remainders of Spolynomials (only one in this case) generated during the course of the computation. Adding the "info" option yields even more information.
AXIOM can also work with coefficients in a variety of fields besides
. this is easily done by replacing FRAC INT
in the
type declarations. For instance, to compute Groebner basis over the
field of rational functions in polynomials with integer coefficients,
one uses FRAC POLY INT
. To see how this works, let us compute a
Groebner basis for the ideal
using lex order with . This is accomplished by the following
AXIOM commands:
m : List DMP([x,y], FRAC POLY INT)
m := [v*x^2 + y,u*x*y + y^2]
(9) 
groebner(m)
(10) 
Notice that this illustrates another method for declaring the type of polynomials used in a Grobner basis computation.
Other fields are just as easy: one uses FRAC COMPLEX INT
for
the field of Gaussian rational numbers
(note that AXIOM writes as %i
) and PrimeField(p)
for a finite field with p
elements (where p
is a prime). It
is also possible to compute Groebner bases over arbitrary finite
fields. AXIOM's method of working with finite fields is explained
in Section 8.11 of JENKS and SUTOR (1992) (See:
Axiom Documentation). The ability to "insert" the field you want
to compute Groebner bases over is a good illustration of the power
of AXIOM.
Besides working with lists of polynomials, AXIOM also allows the user to declare a list of polynomials to be an ideal. The syntax of the ideal command is:
ideal polylist
where polylist
is a list of polynomials of the appropriate type.
This is useful because AXIOM has a number of commands which apply
to ideals (PolynomialIdeals?):
intersect
, which computes the intersection of a list of ideals.zeroDim?
, which determines (using the methods of Chapter 5,
3) if the equations have finitely many solutions over an
algebraically closed field.dimension
, which computes the dimension of the variety
defined by an ideal.prime?
, which determines whether an ideal is prime.radical
, which computes the radical of an ideal.primaryDecomp
, which computes the primary decomposition of
an ideal.Examples of how to use these and other related commands can be
found in Section 8.12 of JENKS and SUTOR (1992). We should
also mention that there are the commands leadingMonomial
and
leadingCoefficient
for extracting the leading term and
coefficient of a polynomial.
All of the commands described so far require that you declare
in advance the type of polynomial you'll be using. However, if
you only need Groebner bases in lex or grevlex order with
rational coefficients, then a simpler approach is to use the
AXIOM commands lexGroebner
and totalGroebner
. For example,
the command:
lexGroebner([2*x^2+y,2*y^2+x], [x, y])
(11) 
computes a Greobner basis (reduced up to constants) for the
ideal
using lex order with . Notice that we didn't have to
declare the type of the polynomials in advance  lexGroebner
takes care of this. To do the same computation using grevlex,
simply replace lexGroebner
with totalGoebner
.
We will end this section by explaining how to get AXIOM to work with grlex order. All of the raw material need is present in AXIOM, though it takes a little work to put it together. For concreteness, suppose we want grlex order on x>y$. Then issue the commands:
)set expose add constructor GDMP
GeneralDistributedMultivariatePolynomial is now explicitly exposed in frame initial
)set expose add constructor ODP
OrderedDirectProduct is now explicitly exposed in frame initial Grlex := GDMP([x,y], FRAC INT, ODP(2, NNI, totalLex$ORDFUNS(2, NNI)));
The basic idea here is that GDMP
stands for "Generalized
Distributed Multivariate Polynomial", this can be used to
create an AXIOM type for any monomial order, and totalLex
is the function which orders exponent vectors using grlex.
By declaring polynomials to be of type Grlex
, you can now
compute Groebner bases using grlex with .
groebner([g::Grlex,h::Grlex])
Cannot convert from type HomogeneousDistributedMultivariatePolynomial([x,y], Fraction( Integer)) to GeneralDistributedMultivariatePolynomial([x, y], Fraction(Integer), OrderedDirectProduct(2, NonNegativeInteger, theMap(ORDFUNS;totalLex;2VB;2, 303))) for value 2 x + y
We should caution that type conversion doesn't work between
Grlex and the monomial orders created by DMP
and HDMP
,
though it is possible to write type conversion routines.
j : Grlex := x^2+y
(12) 
k : Grlex := x+2*x*y
(13) 
groebner([j,k])
(14) 
Using the AXIOM concept of a package, one could write a package which knows all of the monomial orders mentioned in the exercises to Chapter 2, 4, along with commands to convert one type to the other.
param := FRAC POLY INT
(15) 
vars := [ca,cb, sa, sb, x, y, r1, r2, r3, lab, lac] vars := [ca, sa, x, y] vars := [ca, cb, sa, sb, x, y]
(16) 
mm:List DMP(vars,param) := [x^2+y^2r1^2, (x+lab*ca)^2+(y+lab*sa)^2r2^2, (x+lac*(ca*cbsa*sb))^2+(y+lac*(sa*cb+ca*sb))^2r3^2, ca^2+sa^21]
(17) 
b := groebner(mm); #b
(18) 
for i in b repeat outputAsTex i
(19) 
(20) 
(21) 
(22) 
(23) 
(24) 
(25) 
(26) 
(27) 
(28) 
(29) 
(30) 