**Matrix Operations**

**GROEBNER BASES** _ _ _ _ _ _ _ _ _ _ _ _ **introduction**

The GROEBNER package calculates *Groebner bases* using the
*Buchberger algorithm* and provides related algorithms
for arithmetic with ideal bases, such as ideal quotients,
Hilbert polynomials ( *Hollmann algorithm*),
basis conversion (
*Faugere-Gianni-Lazard-Mora algorithm*), independent
variable set ( *Kredel-Weispfenning algorithm*).

Some routines of the Groebner package are used by solve - in that context the package is loaded automatically. However, if you want to use the package by explicit calls you must load it by

load_package groebner;

For the common parameter setting of most operators in this package see ideal parameters.

**IDEAL PARAMETERS**

Most operators of the *Groebner* package compute expressions in a
polynomial ring which given as <R>[<var>,<var>,...] where
<R> is the current REDUCE coefficient domain. All algebraically
exact domains of REDUCE are supported. The package can operate over rings
and fields. The operation mode is distinguished automatically. In
general the ring mode is a bit faster than the field mode. The factoring
variant can be applied only over domains which allow you factoring of
multivariate polynomials.

The variable sequence <var> is either declared explicitly as argument in form of a list in torder, or it is extracted automatically from the expressions. In the second case the current REDUCE system order is used (see korder) for arranging the variables. If some kernels should play the role of formal parameters (the ground domain <R> then is the polynomial ring over these), the variable sequences must be given explicitly.

All REDUCE
kernels can be used as variables. But please
note,
that all variables are considered as independent. E.g. when using
*sin(a)* and *cos(a)* as variables, the basic relation
*sin(a)^2+cos(a)^2-1=0* must be explicitly added to an equation set
because the Groebner operators don't include such knowledge automatically.

The terms (monomials) in polynomials are arranged according to the current term order. Note that the algebraic propertie s of the computed results only are valid as long as neither the ordering nor the variable sequence changes.

The input expressions <exp> can be polynomials <p>, rational
functions <n>/<d> or equations <lh>=<rh> built from
polynomials or rational functions. Apart from the *tracing*
algorithms
groebnert and
preducet, where the equations
have a specific meaning, equations are converted to simple expressions by
taking the difference of the left-hand and right-hand sides
<lh>-<rh>=><p>. Rational functions are converted to
polynomials by converting the expression to a common denominator form
first, and then using the numerator only <n>=><p>. So eventual
zeros of the denominators are ignored.

A basis on input or output of an algorithm is coded as list of expressions {<exp>,<exp>,...} .

**TERM ORDER** _ _ _ _ _ _ _ _ _ _ _ _ **introduction**

For all *Groebner* operations the polynomials are
represented in distributive form: a sum of terms (monomials).
The terms are ordered corresponding to the actual *term order*
which is set by the
torder operator, and to the
actual variable sequence which is either given as explicit
parameter or by the system
kernel order.

**TORDER** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

The operator *torder* sets the actual variable sequence and term order.

1. simple term order:

*torder*(<vl>, <m>)

where <vl> is a list of variables ( kernels) and <m> is the name of a simple term order mode lex term order, gradlex term order, revgradlex term order or another implemented parameterless mode.

2. stepped term order:

*torder*(<vl>,<m>,<n>)

where <m> is the name of a two step term order, one of gradlexgradlex term order, gradlexrevgradlex term order, lexgradlex term order or lexrevgradlex term order, and <n> is a positive integer.

3. weighted term order

*torder*(<vl>, *weighted*, <n>,<n>,...);

where the <n> are positive integers, see weighted term order.

4. matrix term order

*torder*(<vl>, *matrix*, <m>);

where <m> is a matrix with integer elements, see torder_compile.

5. compiled term order

*torder*(<vl>, *co*);

where <co> is the name of a routine generated by torder_compile.

*torder*sets the variable sequence and the term order mode. If the
an empty list is used as variable sequence, the automatic variable extraction
is activated. The defaults are the empty variable list an the
lex term order.
The previous setting is returned as a list.

Alternatively to the above syntax the arguments of *torder* may be
collected in a
list and passed as one argument to
*torder*.

**TORDER_COMPILE** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

A matrix can be converted into a compilable LISP program for faster execution by using

*torder_compile*(<name>,<mat>)

where <name> is an identifier for the new term order and <mat>
is an integer matrix to be used as
matrix term order. Afterwards
the term order can be activated by using <name> in a
torder
expression. The resulting program is compiled if the switch
comp
is on, or if the *torder_compile* expression is part of a compiled
module.

**LEX TERM ORDER**

The terms are ordered lexicographically: two terms t1 t2
are compared for their degrees
along the fixed variable sequence: t1 is higher than t2
if the first different degree is higher in t1.
This order has the *elimination property*
for *groebner basis* calculations.
If the ideal has a univariate polynomial in the last
variable the groebner basis will contain
such polynomial. *Lex* is best
suited for solving of polynomial equation systems.

**GRADLEX TERM ORDER**

The terms are ordered first with their total
degree, and if the total degree is identical
the comparison is
lex term order.
With *groebner* basis calculations this term order
produces polynomials of lowest degree.

**REVGRADLEX TERM ORDER**

The terms are ordered first with their total degree (degree sum), and if the total degree is identical the comparison is the inverse of lex term order. With groebner and groebnerf calculations this term order is similar to gradlex term order; it is known as most efficient ordering with respect to computing time.

**GRADLEXGRADLEX TERM ORDER**

The terms are separated into two groups where the second parameter of the torder call determines the length of the first group. For a comparison first the total degrees of both variable groups are compared. If both are equal gradlex term order comparison is applied to t he first group, and if that does not decide gradlex term order is applied for the second group. This order has the elimination property for the variable groups. It can be used e.g. for separating variables from parameters.

**GRADLEXREVGRADLEX TERM ORDER**

Similar to gradlexgradlex term order, but using revgradlex term order for the second group.

**LEXGRADLEX TERM ORDER**

Similar to gradlexgradlex term order, but using lex term order for the first group.

**LEXREVGRADLEX TERM ORDER**

Similar to gradlexgradlex term order, but using lex term order for the first group revgradlex term order for the second group.

**WEIGHTED TERM ORDER**

establishes a graduated ordering similar to gradlex term order, where the exponents first are multiplied by the given weights. If there are less weight values than variables, the weight list is extended by ones. If the weighted degree comparison is not decidable, the lex term order is used.

**GRADED TERM ORDER**

establishes a cascaded term ordering: first a graduated ordering similar to gradlex term order is used, where the exponen ts first are multiplied by the given weights. If there are less weight values than variables, the weight list is extended by ones. If the weighted degree comparison is not decidable, the term ordering described in the following parameters of the torder command is used.

**MATRIX TERM ORDER**

Any arbitrary term order mode can be installed by a matrix with integer elements where the row length corresponds to the variable number. The matrix must have at least as many rows as columns. It must have full rank, and the top nonzero element of each column must be positive.

The matrix *term order mode*
defines a term order where the exponent vectors of the monomials are
first multiplied by the matrix and the resulting vectors are compared
lexicographically.

If the switch comp is on, the matrix is converted into a compiled LISP program for faster execution. A matrix can also be compiled explicitly, see torder_compile.

**Term order**

**GVARS** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*gvars*({<exp>,<exp>,... })

where <exp> are expressions or equations.

*gvars*extracts from the expressions the
kernel*s*
which can
play the role of variables for a
groebner or
groebnerf
calculation.

**GROEBNER** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

where {*exp*, ... } is a list of
expressions or equations.

The operator *groebner* implements the Buchberger algorithm
for computing Groebner bases for a given set of
expressions with respect to the given set of variables in the order
given. As a side effect, the sequence of variables is stored as a REDUCE list
in the shared variable
gvarslast - this is important in cases
where the algorithm rearranges the variable sequence because
groebopt
is *on*.

groebner({x**2+y**2-1,x-y}) {X - Y,2*Y**2 -1}

_ _ _ groebnerfoperator

_ _ _ gvarslast variable

_ _ _ groebopt switch

_ _ _ groebprereduce switch

_ _ _ groebfullreduction switch

_ _ _ gltbasis switch

_ _ _ gltb variable

_ _ _ glterms variable

_ _ _ groebstat switch

_ _ _ trgroeb switch

_ _ _ trgroebs switch

_ _ _ groebprot switch

_ _ _ groebprotfile variable

_ _ _ groebnert operator

**GROEBNER\_WALK** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

The operator *groebner_walk* computes a *lex* basis
from a given *graded* (or *weighted*) one.

*groebner_walk*(<g>)

where <g> is a *graded* basis (or *weighted* basis
with a weight vector with one repeated element) of the polynomial ideal.
*Groebner_walk* computes a sequence of monomial bases, each
time lifting the full system to a complete basis. *Groebner_walk*
should be called only in cases, where a normal *kex* computation
would take too much computer time.

The operator torder has to be called before in order to define the variable sequence and the term order mode of <g>.

The variable gvarslast is not set.

Do not call *groebner_walk* with *on*
groebopt.

*Groebner_walk*includes some overhead (such as e. g.
computation with division). On the other hand, sometimes
*groebner_walk* is faster than a direct *lex* computation.

**GROEBOPT** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

If *groebopt* is set ON, the sequence of variables is optimized
with respect to execution speed of *groebner* calculations;
note that the final list of variables is available in
gvarslast.
By default *groebopt* is off, conserving the original variable
sequence.

An explicitly declared dependency using the depend declaration supersedes the variable optimization.

guarantees that a will be placed in front of x and y.

**GVARSLAST** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

After a
groebner or
groebnerf calculation
the actual variable sequence is stored in the variable
*gvarslast*. If
groebopt is *on*
*gvarslast* shows the variable sequence after reordering.

**GROEBPREREDUCE** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

If *groebprereduce* set ON,
groebner
and
groebnerf try to simplify the
input expressions: if the head term of an input expression is a
multiple of the head term of another expression, it can be reduced;
these reductions are done cyclicly as long as possible in order to
shorten the main part of the algorithm.

By default *groebprereduce* is off.

**GROEBFULLREDUCTION** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

If *groebfullreduction* set off, the polynomial reduction steps during
groebner and
groebnerf are limited to the pure head
term reduction; subsequent terms are reduced otherwise.

By default *groebfullreduction* is on.

**GLTBASIS** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

If *gltbasis* set on, the leading terms of the result basis
of a
groebner or
groebnerf calculation are
extracted. They are collected as a basis of monomials, which is
available as value of the global variable
gltb.

**GLTB** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

See gltbasis

**GLTERMS** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

If the expressions in a
groebner or
groebnerf
call contain parameters (symbols
which are not member of the variable list), the share variable
*glterms* is set to a list of expression which during the
calculation were assumed to be nonzero. The calculated bases
are valid only under the assumption that all these expressions do
not vanish.

**GROEBSTAT** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

if *groebstat* is on, a summary of the
groebner or
groebnerf computation is printed
at the end
including the computing time, the number of intermediate
H polynomials and the counters for the criteria hits.

**TRGROEB** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

if *trgroeb* is on, intermediate H polynomials are
printed during a
groebner
or
groebnerf calculation.

**TRGROEBS** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

if *trgroebs* is on, intermediate H and S polynomials are
printed during a
groebner or
groebnerf calculation.

**GZERODIM?** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*gzerodim!?*(<basis>)

where <bas> is a Groebner basis in the current term order with the actual setting (see ideal parameters).

*gzerodim!?*tests whether the ideal spanned by the given basis
has dimension zero. If yes, the number of zeros is returned,
nil otherwise.

**GDIMENSION** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

where <bas> is a
groebner basis in the current
term order (see
ideal parameters).
*gdimension* computes the dimension of the ideal
spanned by the given basis and returns the dimension as an integer
number. The Kredel-Weispfenning algorithm is used: the dimension
is the length of the longest independent variable set,
see
gindependent_sets

**GINDEPENDENT\_SETS** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

where <bas> is a
groebner basis in any *term order*
(which must be the current *term order*) with the specified
variables (see
ideal parameters).

*Gindependent_sets*computes the maximal
left independent variable sets of the ideal, that are
the variable sets which play the role of free parameters in the
current ideal basis. Each set is a list which is a subset of the
variable list. The result is a list of these sets. For an
ideal with dimension zero the list is empty.
The Kredel-Weispfenning algorithm is used.

**DD_GROEBNER** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

For a homogeneous system of polynomials under graded term order, gradlex term order, revgradlex term order

or weighted term order a Groebner Base can be computed with limiting the grade of the intermediate S polynomials:

*dd_groebner*(<d1>,<d2>,<plist>)

where <d1> is a non negative integer and <d2> is an integer
or ``infinity". A pair of polynomials is considered
only if the grade of the lcm of their head terms is between
<d1> and <d2>.
For the term orders *graded* or *weighted* the (first) weight
vector is used for the grade computation. Otherwise the total
degree of a term is used.

**GLEXCONVERT** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

where <bas> is a groebner basis in the current term order, <mx> (optional) is a positive integer and <nvl> (optional) is a list of variables (see ideal parameters).

The operator *glexconvert* converts the basis
of a zero-dimensional ideal (finite number
of isolated solutions) from arbitrary ordering into a basis under
lex term order.

The parameter <newvars> defines the new variable sequence. If omitted, the original variable sequence is used. If only a subset of variables is specified here, the partial ideal basis is evaluated.

If <newvars> is a list with one element, the minimal
*univariate polynomial* is computed.

<maxdeg> is an upper limit for the degrees. The algorithm stops with an error message, if this limit is reached.

A warning occurs, if the ideal is not zero dimensional.

During the call the *term order* of the input basis must
be active.

**GREDUCE** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*greduce*(exp, {exp1, exp2, ... , expm})

where exp is an expression, and {exp1, exp2, ... , expm} is a list of expressions or equations.

*greduce*is functionally equivalent with a call to
groebner and then a call to
preduce.

**PREDUCE** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*preduce*(<p>, {<exp>, ... })

where <p> is an expression, and {<exp>, ... } is a list of expressions or equations.

*Preduce*computes the remainder of *exp*
modulo the given set of polynomials resp. equations.
This result is unique (canonical) only if the given set
is a *groebner* basis under the current
term order

see also: preducet operator.

**IDEALQUOTIENT** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*idealquotient*({<exp>, ...}, <d>)

where {<exp>,...} is a list of expressions or equations, <d> is a single expression or equation.

*Idealquotient*computes the ideal quotient:
ideal spanned by the expressions {<exp>,...}
divided by the single polynomial/expression <f>. The result
is the
groebner basis of the quotient ideal.

**HILBERTPOLYNOMIAL** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

where <bas> is a groebner basis in the current term order.

The degree of the *Hilbert polynomial* is the
dimension of the ideal spanned by the basis. For an
ideal of dimension zero the Hilbert polynomial is a
constant which is the number of common zeros of the
ideal (including eventual multiplicities).
The *Hollmann algorithm* is used.

**SATURATION** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*saturation*({<exp>, ...}, <p>)

where {<exp>,...} is a list of expressions or equations, <p> is a single polynomial.

*Saturation*computes the quotient of the polynomial <p>
and a power (with unknown but finite exponent) of the ideal built from
{<exp>, ...}. The result is the computed quotient. *Saturation*
calls
idealquotient several times until the result
does not change
any more.

**Basic Groebner operators**

**GROEBNERF** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*groebnerf*({<exp>, ...}[,{},{<nz>, ... }]);

where {<exp>, ... } is a list of expressions or equations, and {<nz>,... } is an optional list of polynomials to be considered as non zero for this calculation. An empty list must be passed as second argument if the non-zero list is specified.

*groebnerf*tries to separate polynomials into individual factors and
to branch the computation in a recursive manner (factorization tree).
The result is a list of partial Groebner bases.
Multiplicities (one factor with a higher power, the same partial basis
twice) are deleted as early as possible in order to speed up the
calculation.

The third parameter of *groebnerf* declares some polynomials
nonzero. If any of these is found in a branch of the calculation
the branch is canceled.

groebnerf({ 3*x**2*y+2*x*y+y+9*x**2+5*x = 3, 2*x**3*y-x*y-y+6*x**3-2*x**2-3*x = -3, x**3*y+x**2*y+3*x**3+2*x**2 }, {y,x}); {{Y - 3,X}, 2 {2*Y + 2*X - 1,2*X - 5*X - 5}}

_ _ _ groebresmaxvariable

_ _ _ groebmonfac variable

_ _ _ groebrestriction variable

_ _ _ groebner operator

_ _ _ gvarslast variable

_ _ _ groebopt switch

_ _ _ groebprereduce switch

_ _ _ groebfullreduction switch

_ _ _ gltbasis switch

_ _ _ gltb variable

_ _ _ glterms variable

_ _ _ groebstat switch

_ _ _ trgroeb switch

_ _ _ trgroebs switch

_ _ _ groebnert operator

**GROEBMONFAC** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

The variable *groebmonfac* is connected to
the handling of monomial factors. A monomial factor is a product
of variable powers as a factor, e.g. x**2*y in x**3*y -
2*x**2*y**2. A monomial factor represents a solution of the type
x = 0 or y = 0 with a certain multiplicity. With
groebnerf the multiplicity of monomial factor
s is lowered
to the value of the shared variable *groebmonfac*
which by default is 1 (= monomial factors remain present, but their
multiplicity is brought down). With
*groebmonfac*:= 0
the monomial factors are suppressed completely.

**GROEBRESMAX** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

The variable *groebresmax*
controls during
groebnerf calculations
the number of partial results. Its default value is 300. If
more partial results are calculated, the calculation is
terminated.

**GROEBRESTRICTION** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

During
groebnerf calculations
irrelevant branches can be excluded
by setting the variable *groebrestriction*. The
following restrictions are implemented:

*groebrestriction*:= *nonnegative*

*groebrestriction*:= *positive*

*groebrestriction*:= *zeropoint*

With *nonnegative* branches are excluded where one
polynomial has no nonnegative real zeros; with *positive*
the restriction is sharpened to positive zeros only.
The restriction *zeropoint* excludes all branches
which do not have the origin (0,0,...0) in their solution
set.

**Factorizing Groebner bases**

**GROEBPROT** _ _ _ _ _ _ _ _ _ _ _ _ **switch**

If *groebprot* is *ON* the computation steps during
preduce,
greduce and
groebner
are collected in a list which is assigned to the variable
groebprotfile.

**GROEBPROTFILE** _ _ _ _ _ _ _ _ _ _ _ _ **variable**

See groebprot switch.

**GROEBNERT** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*groebnert*({<v>=<exp>,...})

where <v> are
kernel*s* (simple or indexed variables
),
<exp> are polynomials.

*groebnert*is functionally equivalent to a
groebner
call for {<exp>,...}, but the result is a set of
equations where the left-hand sides are the basis elements while
the right-hand sides are the same values expressed as combinations
of the input formulas, expressed in terms of the names <v>

groebnert({p1=2*x**2+4*y**2-100,p2=2*x-y+1}); GB1 := {2*X - Y + 1=P2, 2 9*Y - 2*Y - 199= - 2*X*P2 - Y*P2 + 2*P1 + P2}

**PREDUCET** _ _ _ _ _ _ _ _ _ _ _ _ **operator**

*preduce*(<p>,{<v>=<exp>...})

where <p> is an expression, <v> are kernels
(simple or indexed variables),
*exp* are polynomials.

*preducet*computes the remainder of <p> modulo {<exp>,...}
similar to
preduce, but the result is an equation
which expresses the remainder as combination of the polynomials.

GB2 := {G1=2*X - Y + 1,G2=9*Y**2 - 2*Y - 199} preducet(q=x**2,gb2); - 16*Y + 208= - 18*X*G1 - 9*Y*G1 + 36*Q + 9*G1 - G2