MuPAD File ConstraintStore.mu  Documentation
Description
This file implements a new data type representing a set of Constraints. Thereby, a constraint
is meant to be of the form polynomial = 0 or polynomial <> 0. A set of such
constraints ist meant to be their logical conjungtion. Such sets are called constraint stores.
The data structure provides methods to construct constraint stores by incrementally defining
polynomials to be zero or constant (i.e. nonzero). It further provides methods for reasoning
about polynomials, i.e. you can determine whether a given polynomial is equal to zero or
constant (or nothing at all) with respect to a particular constraint store object. This
reasoning is compleet and corrent. Finally, you have the possibility to
simplify a polynomial with respect to a particular constraint store object, e.g.
x^{2}  x may be reduced to x if your constraint store
contains x^{2} = 0. However, the simplification algorithm
is not necessarily optimal, e.g. x^{2} = 0 implies
x = 0 and thus the polynomial of the last example could have been even
simplified to 0. But of course, you won't get a result that is more complicated that
your input.
How to deal with constraint stores?
You can easily construct a new ConstraintStore object by saying
>> C := ConstraintStore();
{}
This would give you a new empty constraint store which is extensible by adding polynomials
to it. All of the polynomials you want to add to a constraint store must belong to the same
ring. By default, [x, y, z, cs_var.i $ i = 1..20] is used as polynomial variables,
but you can pass your own variable list to the ConstraintStore constructor.
Note that the constraint store needs some "private" variables to
handle constraints about constant polynomials or to reason about zero polynomials. Those
variables are named cs_var1, cs_var2, cs_var3, ... assuming that you will
hardly ever need to used such variables for your own purposes.
If you want to add up to n Constraints to a store, we need n + 1
private variables.
Now, assume that we want to define the polynomial x^{2}  1 to be
zero. We can achive this by stating
>> C := addZero(C, poly(x^2  1, [x]));
{x^{2}  1 = 0}
This statement is possible although the given polynom is strictly speaking not a member of the
right polynommial ring because [x] is a sublist of
[x, y, z, cs_var.i $ i =1..20] and addZero is thus able to "lift"
the polynomial to a corresponding member of the right ring.
If this is not possible, an error occures:
>> C := addZero(C, poly(a^2, [a]));
Error: Illegal argument: poly(a^2, [a]) does not have proper variables.
[ConstraintStore::new]
If you want to find out if x  1 is zero with respect to C, just type
>> isZero(C, poly(x  1, [x]));
FALSE
and you find out that this is not necessarily the case. But if we add another constraint
>> C := addConstant(C, poly(x + 1, [x]));
{x + 1 <> 0,
x^{2}  1 = 0}
then we will get a different result:
>> isZero(C, poly(x  1, [x]));
TRUE
since
(x + 1) (x + 1) x^{2}  1.
One may want to define x  1 to be constant w.r.t. C, but this would
lead to an inconsistent store:
>> C := addConstant(C, poly(x  1, [x])): isConsistent(C);
FALSE
What does internally go on?
This is a secret :)
(Consult my Studienarbeit Ausarbeitung on
http://www.kauers.de/
or inspect the code)
Tools
Here is the list of all the methods that the ConstraintStore data structure provides and that
are defined within this file:
1. Public tools.

ConstraintStore([vars])
Constructs a new, empty ConstraintStore object over the polynomial ring with vars as
variable list.

addZero(C, p)
Constructs a new constraint store where additionaly p = 0 is assumed.

addConstant(C, p)
Constructs a new constraint store where additionaly p is assumed to be constant.

isZero(C, p)
Checks whether or not the given polynomial is zero with respect to C.

isConstant(C, p)
Checks whether or not the given polynomial is constant with respect to C.

isConsistent(C)
Returns TRUE iff there exists specializations for the variables of C's
polynomial ring that fulfill all the constraints of C.
Apart from that, there are some "private" tools which are described below.
Cascading Gröbner Bases
Our Groebner basis implementation is incremental, that means that a root Constraint Store
has a Groebner basis for its polynomial (the polynomial itself) but if a Constraint Store
has a parent, it does only need to have a partial Groebner basis, i.e. a set of polynomials
that extend the Groebner basis of the ancestors to a groebner basis of the new constraint
store.
Where possible, we have recycled the procedures of the MuPAD groebner package, for further
information consult
[1] Geddes et.al. Algorithms for Computer Clgebra, Kluwer, 1992
[2] Cox et.al. Ideals, Varieties, and Algorithms, Springer, 1992
[3] Becker et.al. Groebner Bases, Springer, 1993
Throughout the implementation we use DegInvLexOrder as monomial order.
Caching Intermediate Results
Another data type called Cache is provided to store intermediate results that may
be used again in near future.
There is one global cache object that is a list of cache entries. A cache entry is
a list [C, a, b, c, d, e, f] with

C a constraint store,

a a list of polynomials that are known to be zero,

b a list of polynomials that are known not to be zero,

c a list of polynomials that are known to be constant,

d a list of polynomials that are known not to be zero,

e a list of pairs [p, b] where b is the partial gbasis when
appending p = 0 to C.

Initially, the cache is empty. An entry is appended to the cache when a constraint store
is created. The caches behaviour is similar to a stack: when a constraint store c is pushed
into the stack, the last item in the cache is deleted as long as there is one and it is not
the parent of c. That is, the cache always represents a path in a constraint store tree.
You can switch the use of the cache on and off by setting the USE_CACHE flag.
Tools
The final part of the file defines useful tools to deal with polynomials and ConstraintStores
Index
ConstraintStore 
:  Constructs a new ConstraintStore object. 
ID 
:  Returns the individual ID of a constraint store 
USE_CACHE 
:  
addConstant 
:  Extends an existing ConstraintStore object by an additional constraint 
addZero 
:  Extends an existing ConstraintStore object by an additional constraint 
appendBasis 
:  inserts a new Gröbner basis partition 
basis 
:  Returns the very last partition of C's incremental Groebner basis 
cacheAddConstant 
:  inserts a new constant polynomial to the cache 
cacheAddNotConstant 
:  inserts a new nonconstant polynomial to the cache 
cacheAddNotZero 
:  inserts a new nonzero polynomial to the cache 
cacheAddZero 
:  inserts a new zero polynomial to the cache 
cacheAppend 
:  internal method to store data into the cache 
cacheGBasis 
:  "calculates" a partitional Gröbner basis by table lookup 
cacheIsConstant 
:  decides isConstant by table lookup 
cacheIsZero 
:  decides isZero by table lookup 
contains 
:  determines whether or not a polynom is member of a list up to a constant factor 
containsAllFactors 
:  tests if p is a product of some of a lists polynomials 
containsFactor 
:  tests if one of the polynomials of a list divides p 
depth 
:  Returns the depth of C, 0 iff C is a root 
fastIsConstant 
:  testing on constance by table lookup 
fastIsZero 
:  testing on zero by table lookup 
gbasis 
:  Calculates a partition for an extension of a ConstraintStore 
gccd 
:  determines the greatest constant common dvisor 
indexOf 
:  Returns the index of a constraint store in the current cache list 
isConsistent 
:  returns TRUE iff 1 <> 0 in C. 
isConstant 
:  checks whether or not the given polynomial is constant with respect to C. 
isZero 
:  checks whether or not the given polynomial is zero with respect to C. 
parent 
:  Returns the ConstraintStore C extends, or NIL if C is a root 
poly 
:  Returnd the very last polynomial in C 
poly2constraint 
:  "typesets" a polynomial as a Constraint expression 
polySeq 
:  Returns the nonzero polynomials of C and all its and all its ancestors as a sequence 
print 
:  Overwrites the default print method for printing ConstraintStores 
push 
:  pushes a new item to the stack 
reduce 
:  reduces a polynomial w.r.t. a given list of partial Groebner bases 
simplifyPoly 
:  returns a simplified version of the given polynomial with respect to C. 
spoly 
:  calculates the Spolynomial of a given critical pair. 
totalBasis 
:  Return a list of all the Groebner basis partitions of C and its ancestors. 
update 
:  updates a critical pair list as needed by gbasis 
varlist 
:  Returns the variable list of the polynomials in C including the private variables 
Declaration
ConstraintStore 
Constructs a new ConstraintStore object. 
Parameters
ConstraintStore(varlist)

varlist 
: 
list of variables 
Description
ConstraintStore returns a new ConstraintStore object (with no constraints) over the
polynomial ring with the variables given in varlist.
You can also say ConstraintStore(polynom) which takes the variable list from polynom,
and you can give another ConstraintStore as second argument which is meant to be the
"father" of the new store, but these two possibilities are for internal use only.
top,
index
ID 
Returns the individual ID of a constraint store 
top,
index
parent 
Returns the ConstraintStore C extends, or NIL if C is a root 
top,
index
poly 
Returnd the very last polynomial in C 
top,
index
basis 
Returns the very last partition of C's incremental Groebner basis 
top,
index
depth 
Returns the depth of C, 0 iff C is a root 
top,
index
varlist 
Returns the variable list of the polynomials in C including the private variables 
top,
index
polySeq 
Returns the nonzero polynomials of C and all its and all its ancestors as a sequence 
top,
index
totalBasis 
Return a list of all the Groebner basis partitions of C and its ancestors. 
top,
index
print 
Overwrites the default print method for printing ConstraintStores 
Description
ConstraintStores are printed as sets of constraints, where constraints are of the form
polynomial = 0 or polynomial <> 0.
The polynom2constraint method is used to convert the polynomials to the above described
appearance.
top,
index
poly2constraint 
"typesets" a polynomial as a Constraint expression 
Parameters
poly2constraint(p, d)

p 
: 
a polynomial 
d 
: 
the depth of the ConstraintStore to which p belongs. 
Description
If p contains the variable cs_var.d, then p is assumed to encode an
><0Constraint, otherwise =0Constraint. If p is the zero polynomial, we won't
print it.
top,
index
addZero 
Extends an existing ConstraintStore object by an additional constraint 
Parameters
addZero(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
addZero returns a new ConstraintStore object that extends C by the additional constraint
p = 0.
top,
index
addConstant 
Extends an existing ConstraintStore object by an additional constraint 
Parameters
addConstant(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
addConstant returns a new ConstraintStore object that extends C by the additional
constraint p <> 0.
top,
index
isZero 
checks whether or not the given polynomial is zero with respect to C. 
Parameters
isZero(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
isZero returns TRUE iff C implies that p is zero.
top,
index
isConstant 
checks whether or not the given polynomial is constant with respect to C. 
Parameters
isConstant(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
isConstant returns TRUE iff C implies that p is constant (i.e. never zero).
top,
index
fastIsZero 
testing on zero by table lookup 
Parameters
fastIsZero(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
fastIsZero returns TRUE if it was already calculated that p = 0
in C. This test is correct, but not compleet.
top,
index
fastIsConstant 
testing on constance by table lookup 
Parameters
fastIsConstant(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
fastIsConstant return TRUE if it was already calculated that p is
constant in C. This test is correct, but not compleet.
top,
index
isConsistent 
returns TRUE iff 1 <> 0 in C. 
Parameters
isConsistent(C)

C 
: 
a constraint store 
Description
This method determines whether there exists a specialization of the variables of C that
fulfill all the constraints in C.
It holds that C is consistent if and only if 1<>0 with respect to C.
(This is the condition implemented in the method.)
++
top,
index
simplifyPoly 
returns a simplified version of the given polynomial with respect to C. 
Parameters
simplifyPoly(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
Given a constraint store C and a polynomial p, the method tries to find a
polynomial q, that is equal to p with respect to C, but has a lower
degree. There is no guarantee that the returned polynomial q is by any meaning as
simple as possible. If no simpler polynomial that p is found, then p is
returned itself.
top,
index
gbasis 
Calculates a partition for an extension of a ConstraintStore 
Parameters
gbasis(C, p)

C 
: 
a ConstraintStore 
p 
: 
a polynomial 
Description
gbasis returns a list of polynomials that extend the partitions of C and its ancestors
to a Groebner basis of [C, p].
The corresponding method in MuPAD's groebner package is basis.
top,
index
spoly 
calculates the Spolynomial of a given critical pair. 
Parameters
spoly(c)

c 
: 
a critical pair [p, q, lcm(HT(p), HT(q)), sugar] 
Description
spoly returns the Spolynomial of c using groebner's s_poly
top,
index
reduce 
reduces a polynomial w.r.t. a given list of partial Groebner bases 
Parameters
reduce(p, G)

p 
: 
a polynomial 
G 
: 
a list of partitional Groebner basis 
Description
reduce returns p mod <G> using the algorithm of [2, p63].
top,
index
update 
updates a critical pair list as needed by gbasis 
Parameters
update(totalBasis, G, B, h)

totalBasis 
: 
list of compleeted Groebner basis partitions 
G 
: 
the part of the new partition that was calculated so far 
B 
: 
the current list of critical pairs 
h 
: 
the polynomial to append 
Description
update is the reimplemenation of groebner::update for cascading Groebner bases.
See [3, p230] for further information.
top,
index
top,
index
push 
pushes a new item to the stack 
Parameters
push(C)

C 
: 
a constraint store 
Description
if C has no parent or the cache is empty, the cache is set to [[C,values]].
Otherwise, all the last entries are popped up to the parent of C (or the
empty cache).
top,
index
cacheIsZero 
decides isZero by table lookup 
Parameters
cacheIsZero(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
cacheIsZero returns TRUE if p is zero w.r.t. C and
this fact is known to the cache, FALSE if it is known that p is not
zero and UNKNOWN otherwise.
This method is fast but far from compleet whereas isZero is compleet but far from
fast.
top,
index
cacheAddZero 
inserts a new zero polynomial to the cache 
Parameters
cacheAddZero(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
If C is currently present in the cache (see push), p is
add to C's list of polynomials that are known to be zero.
This method is for internal use only! You may hurt compleetnes if you call this
method with invalid arguments!
cacheAddZero returns null()
top,
index
cacheAddNotZero 
inserts a new nonzero polynomial to the cache 
Parameters
cacheAddNotZero(C, p)

C 
: 
a ConstraintStore 
p 
: 
a polynomial 
Description
Just like cacheAddZero, but for polynomials that are know not to be zero.
top,
index
cacheIsConstant 
decides isConstant by table lookup 
Parameters
cacheIsConstant(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
This is like cacheIsZero, but for "constant".
top,
index
cacheAddConstant 
inserts a new constant polynomial to the cache 
Parameters
cacheAddConstant(C, p)

C 
: 
a ConstraintStore 
p 
: 
a polynomial 
Description
Just like cacheAddZero, but for polynomials that are know to be constant.
top,
index
cacheAddNotConstant 
inserts a new nonconstant polynomial to the cache 
Parameters
cacheAddNotConstant(C, p)

C 
: 
a ConstraintStore 
p 
: 
a polynomial 
Description
Just like cacheAddZero, but for polynomials that are know not to be constant.
top,
index
appendBasis 
inserts a new Gröbner basis partition 
Parameters
appendBasis(C, p, b)

C 
: 
a ConstraintStore 
p 
: 
a polynomial 
b 
: 
a Gröbner basis partition 
Description
b should be the Gröbner basis partition for the store that is created when
p = 0 is added to C.
top,
index
contains 
determines whether or not a polynom is member of a list up to a constant factor 
Parameters
contains(l, p)

l 
: 
a list of polynomials 
p 
: 
a polynomial 
Description
contains returns TRUE if there is some q in l and some
constant r such that p = q * r and FALSE otherwise.
This is an internal method used by cacheIsZero and cacheIsConstant.
top,
index
containsFactor 
tests if one of the polynomials of a list divides p 
Parameters
containsFactor(l, p)

l 
: 
a list of polynomials 
p 
: 
a polynomial 
Description
return TRUE if and only if there is a q in l such that
p/q is a polynomial.
top,
index
containsAllFactors 
tests if p is a product of some of a lists polynomials 
Parameters
containsAllFactors(l, p)

l 
: 
a list of polynomials 
p 
: 
a polynomial 
Description
containsAllFactors returns TRUE if and only if
p=_mult(l[i]^e[i] $ i=1..nops(l)) where e is a list of nonnegative integers.
No factorisation is done.
top,
index
cacheGBasis 
"calculates" a partitional Gröbner basis by table lookup 
Parameters
cacheGBasis(C, p)

C 
: 
a constraint store 
p 
: 
a polynomial 
Description
If the cache list currently contains a partitional basis for adding p to C,
this partition is returend, otherwise, NIL indicates a cache miss.
top,
index
cacheAppend 
internal method to store data into the cache 
Parameters
cacheAppend(C, p, j)

C 
: 
a ConstraintStore 
p 
: 
a polynomial 
j 
: 
an index 
Description
cacheAppend is an abstraction of cacheAddZero,
cacheAddNotZero, cacheAddConstant, cacheAddNotConstant,
cacheAddZeroBasis, cacheAddConstantBasis.
If the cache currently contains an entry for C, p is appended to the cache
entry at index j.
top,
index
indexOf 
Returns the index of a constraint store in the current cache list 
Parameters
indexOf(C)

C 
: 
a constraint store 
Description
If the cache list currently contains an entry for C, then this entries index is
returned. Otherwise, 1 is returned to indicate that there is no cache entry for
C.
top,
index
gccd 
determines the greatest constant common dvisor 
Parameters
gccd(C, p1,..., pn)

C 
: 
a constraint store 
p1,..., pn 
: 
polynomials, at least one 
Description
gccd determines the greatest common divisor of p1..pn which is constant w.r.t.
C.
Caution: You may suffer from a long runtime, because polynomial factorisation is used.
top,
index