# geobucket

© 2006-2012 Anna Bigatti
GNU Free Documentation License, Version 1.2

CoCoALib Documentation Index

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

### Constructors

• geobucket(const SparsePolyRing&);

### Queries

• IsZero(g) -- true iff g is the zero polynomial (potentially costly because it compares the buckets)

### Operations

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

#### Member functions

• 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

## 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 in
• IhaveLM -- true if certified that LM(gbk) = LM(gbk[0])
• myBuckets -- the bucket vector

### bucket

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

#### 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); 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)

#### Member fields

• 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