GNU Free Documentation License, Version 1.2

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.

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`i`

th 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 `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 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**

- Added example

**2004**

- October: introduction of
`myDivMaskImplPtr`

for computing`LPPwMask`

: LPP with DivMask if this pointer is 0 LPPwMask returns an error (through`CoCoA_ASSERT`

?)