PPMonoidElem are analogous to
PPMonoid represents a (multiplicative) power product
monoid with grading and compatible total arithmetic ordering; a
PPMonoidElem represents an element of a
a power product.
PPMonoidElem are used inside the implementation of
SparsePolyRing (multivariate polynomial rings).
You do not have to deal directly with
PPMonoid unless you want to
work solely with power-products, or use some particular implementation
for a specific need in your
SparsePolyRing -- e.g. huge
exponents, very sparse power-products, fast ordering or fast access to
The implementations of
PPMonoids are optimized for different uses:
PPMonoidEv: stores the Exponent vector; it is good for accessing the exponents, but slow for ordering; with optional 3rd arg
BigExpsthe exponents are stored as
PPMonoidOv: stores the Order vector; it is good for ordering, but slow for accessing the exponents; multiplication and comparison are fast; GCD/LCM are slow.
PPMonoidEvOv: stores the Exponent vector and the Order vector; it is good for accessing the exponents and for ordering but uses more memory and takes more time to assign.
Recall that every
PPMonoid is graded, and has a degree-compatible total
arithmetical ordering; the grading and ordering must be specified when the
PPMonoid is created. For convenient input and output, also the names
of the indeterminates generating the monoid must be specified when the
monoid is created.
If you expect to use large exponents then you should use only the special
PPMonoid created by
PPMonoids should usually be fine for exponents up to 1000 or
more; the true limit depends on the specific monoid, the number of
indeterminates, and the
PPOrdering. At the moment there is no way to
find out what the true limit is (see Bugs section), and no warning
is given should the limit be exceeded: you just get a wrong answer.
To create a
PPMonoid use the function
NewPPMonoid (the default
PPMonoidEv). To create a
PPMonoid object of
a specific type use one of the pseudo-constructors related to the
concrete monoid classes:
NewPPMonoid(IndetNames, PPO)-- same as
NewPPMonoidEv(IndetNames, PPO, BigExps)--
BigExpsis just an enum member.
cout << PPM-- print
NumIndets(PPM)-- number of indeterminates
OrdMat(PPM)-- a matrix defining the ordering used in
GradingDim(PPM)-- the dimension of the grading (zero if ungraded)
GradingMat(PPM)-- the matrix defining the grading
PPM(i.e. names of the indets in order:
k-th entry is
IndetSymbol(PPM, k)-- the
PPM1 == PPM2-- true iff
PPM2are identical (i.e. same addr)
PPM1 != PPM2-- true unless
IsPPMonoidOv(PPM)-- true iff
PPMis internally implemented as a
These pseudo-constructors are described in the section about
IndetPower(PPM, k, exp)
See also some example programs in the
When a new object of type
PPMonoidElem is created the monoid to which it
belongs must be specified either explicitly as a constructor argument, or
implicitly as the monoid associated with some constructor argument. Once
PPMonoidElem object has been created it is not possible to make it
belong to any other monoid. Comparison and arithmetic between objects of
PPMonoidElem is permitted only if they belong to the same identical
Note: when writing a function which has an argument of type
you should specify the argument type as
RefPPMonoidElem if you want to modify its value.
PPM be a
PPMonoid; for convenience, in comments we shall use x[i] to
refer to the i-th indeterminate in
pp be a non-const
const PPMonoidElem (all belonging to
expv be a
vector<long> of size equal to the number of indeterminates.
PPMonoidElem t(PPM)-- create new PP in
PPM, value is 1
PPMonoidElem t(PPM, expv)-- create new PP in
PPM, value is product x[i]^expv[i]
PPMonoidElem t(pp1)-- create a new copy of
pp1, belongs to same PPMonoid as
one(PPM)-- the 1 belonging to
indet(PPM, i)-- create a new copy of x[i] the i-th indeterminate of
IndetPower(PPM, i, n)-- create x[i]^n,
n-th power of
i-th indeterminate of
std::vector(reference) whose n-th entry is n-th indet as a
owner(pp1)-- returns the
IsOne(pp1)-- returns true iff
IsIndet(i, pp1)-- returns true iff
pp1is an indet; if true, puts index of indet into
IsIndetPosPower(i, N, pp1)-- returns true iff
pp1is a positive power of some indet; when the result is true (signed long)
Nare set so that
pp1 == IndetPower(owner(pp), i, N);(otherwise unchanged) if
pp1== 1 then the function throws
IsIndetPosPower(i, n, pp1)-- same as above, where
cmp(pp1, pp2)-- compare
pp2using inherent ordering; result is integer <0 if
pp1 < pp2, =0 if
pp1 == pp2, and >0 if
pp1 > pp2
pp1 == pp2-- the six standard comparison operators...
pp1 != pp2-- ...
pp1 < pp2-- ... (inequalities use the ordering inherent in
pp1 <= pp2-- ...
pp1 > pp2-- ...
pp1 >= pp2-- ...
pp1 * pp2-- product of
pp1 / pp2-- quotient of
pp2, quotient must be exact (see the function
colon(pp1, pp2)-- colon quotient of
gcd(pp1, pp2)-- gcd of
lcm(pp1, pp2)-- lcm of
radical(pp1)-- radical of
n-th power of
pp1(NB: you cannot use
pp1^n, see below)
PowerOverflowCheck(pp1, n)-- throws
ExpTooBigif overflow would occur computing
IsCoprime(pp1, pp2)-- tests whether
IsDivisible(pp1, pp2)-- tests whether
pp1is divisible by
IsSqFree(pp1)-- test whether
pp1is squarefree, i.e. if
pp1 == radical(pp1)
pp = 1
swap(pp, pp_other)-- swaps the values of
pp = pp1-- assignment (
pp1must belong to same PPMonoid)
pp *= pp1-- same as
pp = pp * pp1
pp /= pp1-- same as
pp = pp / pp1
StdDeg(pp1)-- standard degree of
pp1; result is of type
wdeg(pp1)-- weighted degree of
pp1(using specified grading); result is of type
CmpWDeg(pp1, pp2)-- result is integer <0 =0 >0 according as
wdeg(pp1)< = >
wdeg(pp2); order on weighted degrees is lex, see
CmpWDegPartial(pp1, pp2, i)-- result is integer <0 =0 >0 as
CmpWDegwrt the first
icomponents of the weighted degree
exponent(pp1, i)-- exponent of x[i] in
pp1(result is a
BigExponent(pp1, i)-- exponent of x[i] in
pp1(result is a
exponents(expv, pp)-- fills vector (of long)
expv[i] = exponent(pp, i)for i=0,..,NumIndets(PPM)-1
BigExponents(expv, pp)-- fills vector (of BigInt)
expv[i] = BigExponent(pp, i)for i=0,..,NumIndets(PPM)-1
cout << pp1-- print out the value of
IsFactorClosed(S)-- says whether the
std::vector<PPMonoidElem>S is factor closed; error if S is empty.
This section comprises two parts: the first is about creating a new type
of PP monoid; the second comments about calling the member functions of
My first suggestion is to look at the code implementing
This is a simple PP monoid implementation: the values are represented as
C arrays of exponents. Initially you should ignore the class
and those derived from it; they are simply to permit fast comparison of
PPs in certain special cases.
First, a note about "philosophy". As far as we can tell, the programming language C++ does not have a built-in type system sufficiently flexible (and efficient) for our needs, consequently we have to build our own type system on top of what C++ offers. The way we have chosen to do this is as follows (note that the overall scheme used here is similar to that used for rings and their elements).
To fit into CoCoALib your new class must be derived from
Remember that any operation on elements of your PP monoid will be effected
by calling a member function of your new monoid class.
The monoid must be a cartesian power of N, the natural numbers, with the
monoid operation (called "multiplication") being vector addition -- the
vector should be thought of as the vector of exponents in a power product.
The monoid must have a total arithmetic ordering; often this will be specified
when the monoid is created. The class
PPOrdering represents the possible
Here is a summary of the member functions which must be implemented. All
the functions may be called for a const
PPMonoid, for brevity the
qualifier is omitted. I use two abbreviations:
||is short for
||is short for
Note: all arithmetic functions must tolerate argument aliasing (i.e. any pair of arguments may be identical).
Constructors: these all allocate memory which must eventually be freed (by
myDelete); the result is a pointer to the memory allocated.
PPMonoidElemRawPtr PPMonoidBase::myNew()-- initialize pp to the identity
PPMonoidElemRawPtr PPMonoidBase::myNew(const vector<int>& expv)-- initialize pp from exponent vector
PPMonoidElemRawPtr PPMonoidBase::myNew(const RawPP& pp1)-- initialize pp from
Destructor: there is only one of these, its argument must be initialized
void PPMonoidBase::myDelete(PPMonoidElemRawPtr pp)-- destroy
pp, frees memory
void PPMonoidBase::mySwap(RawPP pp1, RawPP pp2)-- swap the values of
void PPMonoidBase::myAssign(RawPP pp, ConstRawPP pp1)-- assign the value of
void PPMonoidBase::myAssign(RawPP pp, const vector<int>& expv)-- assign to
ppthe PP with exponent vector
Arithmetic: in all cases the first arg is where the answer is placed,
aliasing is permitted (i.e. arguments need not be distinct);
myDiv result is undefined if the quotient does not exist!
const PPMonoidElem& myOne()-- reference to 1 in the monoid
void myMul(RawPP pp, ConstRawPP pp1, ConstRawPP pp2)-- effects pp = pp1*pp2
void myMulIndetPower(RawPtr pp, long i, unsigned long exp)-- effects pp *= indet(i)^exp
void myDiv(RawPP pp, ConstRawPP pp1, ConstRawPP pp2)-- effects pp = pp1/pp2 (if it exists)
void myColon(RawPP pp, ConstRawPP pp1, Const RawPP pp2)-- effects pp = pp1/gcd(pp1,pp2)
void myGcd(RawPP pp, ConstRawPP pp1, ConstRawPP pp2)-- effects pp = gcd(pp1, pp2)
void myLcm(RawPP pp, ConstRawPP pp1, ConstRawPP pp2)-- effects pp = lcm(pp1, pp2)
void myPower(RawPP pp, ConstRawPP pp1, int exp)-- effects pp = pp1^exp
void myPowerOverflowCheck(ConstRawPP pp1, int exp)-- throws
myPower(pp,exp)would overflow exponent range
Comparison and testing: each PP monoid has associated with it a term ordering, i.e. a total ordering which respects the monoid operation (multiplication)
bool myIsCoprime(ConstRawPP pp1, ConstRawPP pp2)-- true iff gcd(pp1, pp2) is 1
bool myIsDivisible(ConstRawPP t1, ConstRawPP t2)-- true iff t1 is divisible by t2
int myCmp(ConstRawPP t1, ConstRawPP t2)-- result is <0, =0, >0 according as t1 <,=,> t2
int myHomogCmp(ConstRawPP t1, ConstRawPP t2)-- as cmp, but assumes t1 and t2 have the same degree
degree myDeg(ConstRawPP t)-- total degree
long myExponent(ConstRawPtr rawpp, long i)-- exponent of i-th indet in pp
void myBigExponent(BigInt& EXP, ConstRawPtr rawpp, long i)-- EXP = degree of i-th indet in pp
void myExponents(vector<long>& expv, ConstRawPP t)-- get exponents, put them in expv
void myBigExponents(vector<BigInt>& expv, ConstRawPP t)-- get exponents, put them in expv
ostream& myOutput(ostream& out, const RawPP& t)-- prints t on out; default defn in PPMonoid.C
long myNumIndets()-- number of indeterminates generating the monoid
const symbol& myIndetName(long var)-- name of indet with index var
You will have to edit
PPMonoid.H and possibly
PPMonoid.C (e.g. if there is
to be a default definition). Arguments representing PPs should be of type
RawPP if they may be modified, or of type
ConstRawPP if they are read-only.
See also the Coding Conventions about names of member functions.
If you do add a new pure virtual member function, you will have to add definitions to all the existing concrete PP monoid classes (otherwise they will become uninstantiable). Don't forget to update the documentation too!
Values of type
PPMonoidElem are intended to be simple and safe to use
but with some performance penalty. There is also a "fast, ugly, unsafe"
option which we shall describe here.
The most important fact to heed is that a
PPMonoidElemRawPtr value is not
a C++ object -- it does not generally know enough about itself even to
destroy itself. This places a considerable responsibility on the
programmer, and probably makes it difficult to write exception clean code.
You really must view the performance issue as paramount if you plan to use
raw PPs! In any case the gain in speed will likely be only slight.
The model for creation/destruction and use of raw PPs is as follows:
(NB see Bugs section about exception-safety)
- (1) an uninitialized raw PP is acquired from the system;
- (2) the raw PP is initialized by calling an initialization function (typically called
myNew) -- this will generally acquire further resources;
- (3) now the RawPP may be used for i/o, arithmetic, and so forth;
- (4) finally, when the value is no longer required the extra resources
acquired during initialization should be released by calling the
function -- failure to call
myDelete will probably result in a memory leak.
Here is some pseudo C++ code to give an idea
const PPMonoid& M = ...; // A PPMonoid from somewhere PPMonoidElemRawPtr t; // A wrapped opaque pointer; initially points into hyperspace. t = M->myNew(); // Allocate resources for a new PP belonging to M; // there are two other myNew functions. .... operations on t; always via a member function of the monoid M ... M->myDelete(t); // "destroy" the value t held; t points into hyperspace again.
NOTE: the only functions which take a pointer into hyperspace are
many functions, e.g.
PPMonoidBase::myMul, write their result into the first argument
and require that that first argument be already allocated/initialized.
NOTE: if an exception is thrown after
M->myNew and before
there will be a memory leak (unless you correctly add a
t is just to hold a temporary local
value then it is better to create a full
PPMonoidElem and then let
RawPtr; this should avoid memory leaks.
See subsection below about thread-safety in
The general structure here mirrors that of rings and their elements, so you may find it helpful to read ring.txt if the following seems too opaque. At first sight the design may seem complex (because it comprises several classes), but there's no need to be afraid.
PPMonoid is a reference counting smart pointer to an object
PPMonoidBase. This means that making copies of a
PPMonoid is very cheap, and that it is easy to tell if two
are identical. Assignment of
PPMonoids is disabled because I am not
sure whether it is useful/meaningful.
operator-> allows member
PPMonoidBase to be called using a simple syntax.
PPMonoidBase is what specifies the class interface for each
concrete PP monoid implementation, i.e. the operations that it must offer.
It includes an intrusive reference count for compatibility with
PPMonoid. Since it is inconceivable to have a PP monoid without an
ordering, there is a data member for memorizing the inherent
This data member is
protected so that it is accessible only to friends
and derived classes.
PPMonoidBase::myOutput for printing PPs has a reasonable
The situation for elements of a PP monoid could easily appear horrendously
complicated. The basic idea is that a PP monoid element comprises two
components: one indicating the
PPMonoid to which the value belongs, and
the other indicating the actual value. This allows the user to employ a
notationally convenient syntax for many operations -- the emphasis is on
notational convenience rather than ultimate run-time efficiency.
For an element of a PP monoid, the owning
PPMonoid is specified during
creation and remains fixed throughout the life of the object; in contrast
the value may be varied (if C++ const rules permit). The value is
indicated by an opaque pointer (essentially a wrapped
void*): only the
PPMonoid knows how to interpret the data pointed to, and so all
operations on the value are effected by member functions of the owning
I do not like the idea of having naked
void* values in programs: it is
too easy to get confused about what is pointing to what. Since the
value part of a
PPMonoidElem is an opaque pointer (morally a
I chose to wrap it in a lightweight class; actually there are two classes
depending on whether the pointed to value is
const or not. These
are opaque pointers pointing to a value belonging to some concrete PP
monoid (someone else must keep track of precisely which PP monoid is the
The constructors for
explicit to avoid potentially risky automatic conversion of any
old pointer into one of these types. The naked pointer may be accessed
via the member functions
myRawPtr. Only implementors of new PP
monoid classes are likely to find these two opaque pointer classes useful.
I now return to the classes for representing fully qualified PPs.
There are three very similar yet distinct classes for elements of PP
monoids; the distinction is to keep track of constness and ownership.
I have used inheritance to allow natural automatic conversion among
these three classes (analogously to
PPMonoidElemis the owner of its value; the value will be deleted when the object ceases to exist.
RefPPMonoidElemis not the owner of its value, but the value may be changed (and the owner of the value will see the change too).
ConstRefPPMonoidElemis not the owner of its value, and its value may not be changed (through this reference).
The data layout is determined in
ConstRefPPMonoidElem, and the more
permissive classes inherit the data members. I have deliberately used a
PPMonoidElemRawPtr for the value pointer as it is easier for
ConstRefPPMonoidElem to add in constness appropriately than it
is for the other two classes to remove it. The four assignment operators
must all be defined since C++ does not allow polymorphism in the destination
object (e.g. because of potential problems with slicing). Ideally it would
be enough to define assignment just from a
ConstRefPPMonoidElem, but I
have to define also the "homogeneous" assignment operator since the default
definition would not work properly. It is a bit tedious to have four copies
of the relevant code (but it is only a handful of lines each time).
By convention the member functions of
PPMonoidBase which operate on
raw PP values assume that the values are valid (e.g. belong to the same
PP monoid, division is exact in
myDiv). The validity of the arguments
is checked by the syntactically nice equivalent operations (see the code
in PPMonoid.C). This permits a programmer to choose between safe clean
code (with nice syntax) or faster unsafe code (albeit with uglier syntax).
The impl in
PPMonoidOV using the CPP flag
to select between two impl strategies. If the CPP flag is not set, then
"single-threaded" code is compiled which uses some "global" buffers to
gain speed; if the flag is set then buffers are allocated locally in
The section on "Advanced Use" is a bit out of date and too long.
PPMonoidElems be inlined? With the current design, since speed is not so important for
PPMonoidElems so that they are obviously exception safe, BUT they now make an extra copy of the computed value (as it is returned from a local variable to the caller). Here is an idea for avoiding that extra copy. Create a new type (say PPMonoidElem_local) which offers just raw(..) and a function export(..) which allows the return mechanism to create a full
PPMonoidElem(just by copying pointers) and empty out the PPMonoidElem_local. If the PPMonoidElem_local is not empty then it can destroy the value held within it. By not attempting to make PPMonoidElem_locals behave like full PPMonoidElems I save a lot of "useless" function definitions. Indeed the "export" function need not exist: an implicit ctor for a PPMonoidElem from a PPMonoidElem_local could do all the work. I'll wait to see profiling information before considering implementing.
PPMonoids likely to be useful to anyone? I prefer to forbid it, as I suspect a program needing to use it is really suffering from poor design...
operator^for computing powers because of a significant risk of misunderstanding between programmer and compiler. The syntax/grammar of C++ cannot be changed, and
operator^binds less tightly than (binary)
operator*, so any expression of the form
a*b^cwill be parsed as
(a*b)^c; this is almost certainly not what the programmer intended. To avoid such problems of misunderstanding I have preferred not to define
operator^; it seems too dangerous.
PPMonoidElems is deliberate; you should choose either
wdegaccording to the type of degree you want to compute. This is unnatural; is it a bug?
ConstRefPPMonoidElemand its descendants virtual. This is marginally risky: it might be possible to leak memory if you convert a raw pointer to
PPMonoidEleminto a raw pointer to
ConstRefPPMonoidElem; of course, if you do this you're asking for trouble anyway.
exponentsgive an error if the values exceed the limits for