Examples
User documentation
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 PPMonoidElem
s.
Constructors
geobucket(const SparsePolyRing&)
;
Queries
IsZero(g)
-- true iffg
is the zero polynomial (potentially costly because it compares the buckets)
Operations
Let gbk
be a geobucket
, f
a RingElem&
(see RingElem
)
CoeffRing(gbk)
-- thering
of coefficients of the ring ofgbk
PPM(gbk)
-- thePPMonoid
of the ring ofgbk
LC(gbk)
-- the leading coeff ofgbk
; it is an element ofCoeffRing(gbk)
(potentially costly because it compares the buckets)content(gbk)
-- the gcd of all coefficients ingbk
; it is an element ofCoeffRing(gbk)
(it is the gcd of all bucket contents)RemoveBigContent(gbk)
-- ifgbk
has a big content,gbk
is divided by itAddClear(f, gbk)
-- assign the polynomial value ofgbk
tof
, and set 0 togbk
MoveLMToFront(f, gbk)
; -- moves the LM ofgbk
tof
(using PushFront)MoveLMToBack(f, gbk)
; -- moves the LM ofgbk
tof
(using PushBack)ReductionStep(gbk, f, RedLen)
; -- reducesgbk
withf
ReductionStepGCD(gbk, f, FScale, RedLen)
; -- same as above, but multiplies by a scalar if neededoperator<<(std::ostream&, gbk)
-- prints the buckets (mainly for debugging)PrintLengths(std::ostream&, gbk)
-- just for debugging
Member functions
myAddClear(f, len)
-- mainly used for assigning to a geobucketmyDeleteLM(void)
myPushBackZeroBucket(MaxLen)
myBucketIndex(len)
-- the index for thebucket
with lengthlen
myAddMul(monom, g, gLen, SkipLMFlag)
--*this += monom*g
myDivByCoeff(coeff)
-- content MUST be divisible by coeffmyMulByCoeff(coeff)
myCascadeFrom(i)
-- start cascade fromi
th bucketmySize(void)
-- the number of bucketsmySetLM()
-- Sets the LM of*this
in the 0-thbucket
and setIhaveLM
to true;*this
will be normalized
Maintainer documentation
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 inIhaveLM
-- true if certified that LM(gbk) = LM(gbk[0])myBuckets
-- the bucket vector
bucket
This class is to be used only by geobucket
s.
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 geobucket
s, friend)
Methods on buckets (weak exception guarantee)
myNormalize(void)
-- myPoly *=myCoeff; myCoeff 1myAddClear(RingElem& f, int FLen)
-- *this += f; f = 0; *this normalizedmyAddClear(bucket& b)
-- *this += b; b = 0; *this normalizedmyMul(ConstRefRingElem coeff)
-- *this *= coeffmyDiv(ConstRefRingElem coeff)
-- *this /= coeff; assumes *this divisible by coeff
Functions on buckets
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);
returnLC(b1)+LC(b2)==0
; it assumesLPP(b1) == LPP(b2)
MoveLM(const SparsePolyRing&, bucket& b1, bucket& b2)
--b1 += LM(b2); b2 -= LM(b2);
it assumesLPP(b1)<LPP(b2)
Member fields
changes
2013
- Added example
2004
- October: introduction of
myDivMaskImplPtr
for computingLPPwMask
: LPP with DivMask if this pointer is 0 LPPwMask returns an error (throughCoCoA_ASSERT
?)