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