# 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. non-zero). 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. x2 - x may be reduced to x if your constraint store contains x2 = 0. However, the simplification algorithm is not necessarily optimal, e.g. x2 = 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 x2 - 1 to be zero. We can achive this by stating

>>  C := addZero(C, poly(x^2 - 1, [x]));

{x2 - 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, x2 - 1 = 0}

then we will get a different result:

>>  isZero(C, poly(x - 1, [x]));

TRUE

since (x + 1) (x + 1) x2 - 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.
Constructs a new constraint store where additionaly p = 0 is assumed.
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.

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

 Geddes et.al. Algorithms for Computer Clgebra, Kluwer, 1992
 Cox et.al. Ideals, Varieties, and Algorithms, Springer, 1992
 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 non-constant 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 S-polynomial 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 ><0-Constraint, otherwise =0-Constraint. If p is the zero polynomial, we won't print it.

top, index

#### 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

#### 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 S-polynomial of a given critical pair.

#### Parameters

 spoly(c) c : a critical pair [p, q, lcm(HT(p), HT(q)), sugar]

#### Description

spoly returns the S-polynomial 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

 USE_CACHE

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!

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 non-constant 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.

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

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