Based on The Geobucket Data Structure for Polynomials by Thomas Yan (1996).
A geobucket is a polynomial represented in a C++ vector of buckets:
a bucket contains a polynomial and some other info
(see below geobucket bucket)
This construction is particularly useful for
adding many short polynomials to a long one
(in particular the reduction process) because it lowers the number of calls
of cmp between PPMonoidElems.
geobucket(const SparsePolyRing&);
IsZero(g) -- true iff g is the zero polynomial (potentially costly because it compares the buckets)
Let gbk be a geobucket, f a RingElem& (see RingElem)
CoeffRing(gbk) -- the ring of coefficients of the ring of gbk
PPM(gbk) -- the PPMonoid of the ring of gbk
LC(gbk) -- the leading coeff of gbk; it is an element of CoeffRing(gbk) (potentially costly because it compares the buckets)
content(gbk) -- the gcd of all coefficients in gbk; it is an element of CoeffRing(gbk) (it is the gcd of all bucket contents)
RemoveBigContent(gbk) -- if gbk has a big content, gbk is divided by it
AddClear(f, gbk) -- assign the polynomial value of gbk to f,
and set 0 to gbk
MoveLM(f, gbk); -- moves the LM of gbk to f (as a PushFront)
ReductionStep(gbk, f, RedLen); -- reduces gbk with f
ReductionStepGCD(gbk, f, FScale, RedLen); -- same as above, but multiplies by a scalar if needed
operator<<(std::ostream&, gbk) -- prints the buckets (mainly for debugging)
PrintLengths(std::ostream&, gbk) -- just for debugging
myAddClear(f, len) -- mainly used for assigning to a geobucket
myDeleteLM(void)
myPushBackZeroBucket(MaxLen)
myBucketIndex(len) -- the index for the bucket with length len
myAddMul(monom, g, std::gLen, SkipLMFlag) -- *this += monom*g
myDivByCoeff(coeff) -- content MUST be divisible by coeff
myMulByCoeff(coeff)
myCascadeFrom(std::size_t i)
mySize(void) -- the number of buckets
mySetLM() -- Sets the LM of *this in the 0-th bucket
and set IhaveLM to true;
*this will be normalized
After calling gbk.mySetLM() the leading monomial of gbk is in
gbk.myBuckets[0]
(and then gbk is zero iff gbk.myBuckets[0]=0)
gbk.myBuckets[i] contains at most gbk_minlen * gbk_factor^i summands
myPolyRing -- the SparsePolyRing gbk lives in
IhaveLM -- true if certified that LM(gbk) = LM(gbk[0])
myBuckets -- the bucket vector
This class is to be used only by geobuckets.
A bucket represents a polynomial as a product of a polynomial and
a coefficient, two RingElem respectivey in a SparsePolyRing
P and CoeffRing(P).
The coeffient factor is used for fast multiplication of a geobucket by a coefficient and it comes useful in the reduction process over a field of fraction of a GCD ring.
We normalize the bucket (i.e. multiply the polynomial by the
coefficient) only when it is necessary: e.g. to compute a reference to
the LC of the bucket.
All methods are private (to be used only by geobuckets, friend)
Methods on buckets (weak exception guarantee)
myNormalize(void) -- myPoly *=myCoeff; myCoeff 1
myAddClear(RingElem& f, int FLen) -- *this += f; f = 0; *this normalized
myAddClear(bucket& b) -- *this += b; b = 0; *this normalized
myMul(ConstRefRingElem coeff) -- *this *= coeff
myDiv(ConstRefRingElem coeff) -- *this /= coeff; assumes *this divisible by coeff
IsZero(const bucket&) --
content(const bucket& b) --
poly(bucket& b) -- normalize b and return a reference to the polynomial
Dirty method and function for efficiency (b1 and b2 will be normalized))
myIsZeroAddLCs(const SparsePolyRing&, bucket& b1, bucket& b2) --
b1 += LM(b2); b2 -= LM(b2); return LC(b1)+LC(b2)==0;
it assumes LPP(b1) == LPP(b2)
MoveLM(const SparsePolyRing&, bucket& b1, bucket& b2) --
b1 += LM(b2); b2 -= LM(b2); it assumes LPP(b1)<LPP(b2)
myPoly -- the polynomial (a RingElem in P)
myCoeff -- the coefficient factor (a RingElem in CoeffRing(P))
myMaxLen -- the maximal length allowed for the polynomial of this bucket
myApproxLen -- an upper bound for the current length of the polynomial of this bucket
2013
2004
myDivMaskImplPtr for computing LPPwMask:
LPP with DivMask if this pointer is 0 LPPwMask returns an error
(through CoCoA_ASSERT?)