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.
For summing many big integers or rationals see also SumBigRat in BigRatOps,
and SumBigInt in BigIntOps.
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
MoveLMToFront(f, gbk); -- moves the LM of gbk to f (using PushFront)
MoveLMToBack(f, gbk); -- moves the LM of gbk to f (using PushBack)
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, gLen, SkipLMFlag) -- *this += monom*g
myDivByCoeff(coeff) -- content MUST be divisible by coeff
myMulByCoeff(coeff)
myCascadeFrom(i) -- start cascade from ith bucket
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?)