Implementation of polynomials for fast summation of many short polynomials
A geobucket is a polynomial represented in a C++ vector of buckets:
a bucket
contains a polynomial (and some other info)
This construction is useful when adding many short polynomials to a long one (in particular the reduction process) because it lowers the number of calls of "cmp".
AFTER CALLING SetLM() LM(gbk) is in gbk.myBuckets[0], the first bucket (and then gbk==0 iff gbk.myBuckets[0]=0 ) gbk.myBuckets[i] contains at most gbk_minlen * gbk_factor^i summands
27Oct2004: introduction of myDivMaskImplPtr for computing LPPwMask: LPP with DivMask if this pointer is 0 LPPwMask returns an error (through CoCoA_ASSERT?)
public: geobucket(const SparsePolyRing&); ~geobucket(); std::size_t mySize(void) const; friend std::ostream& operator<<(std::ostream&, const geobucket&); friend void PrintLengths(std::ostream&,const geobucket&); ///< just for debugging void myPushBackZeroBucket(std::size_t MaxLen); void myAddClear(RefRingElem, std::size_t len); void myDeleteLM(void); std::size_t myBucketIndex(std::size_t len); ///< \return the bucket index for a polynomial of length \a len void myAddMul(ConstRefRingElem monom, ConstRefRingElem g, std::size_t gLen, SparsePolyRingBase::SkipLMFlag); ///< *this += monom*g friend RingElem content(const geobucket&); friend void RemoveBigContent(geobucket&); void myDivByCoeff(ConstRefRingElem coeff); ///< content MUST be divisible by \a coeff void myMulByCoeff(ConstRefRingElem coeff); friend const ring& CoeffRing(const geobucket& g); friend const PPMonoid& PPM(const geobucket& g); friend void AddClear(RefRingElem f, geobucket& gbk); friend bool IsZero(const geobucket&); friend ConstRefRingElem LC(const geobucket&); friend ConstRefPPMonoidElem LPP(const geobucket&); void myCascadeFrom(std::size_t i); friend void MoveLM(RefRingElem g, geobucket& gbk); friend void ReductionStep(geobucket& gbk, ConstRefRingElem g, std::size_t RedLen); friend void ReductionStepGCD(geobucket& gbk, ConstRefRingElem g, RefRingElem FScale, std::size_t RedLen); ///@name member fields of geobucket //@{ private: SparsePolyRing myPolyRing; ///< the SparsePolyRing gbk lives in mutable bool IhaveLM; ///< true if certified that LM(gbk) = LM(gbk[0]) mutable std::vector<bucket> myBuckets; ///< the bucket vector //@} void mySetLM() const; /**< Sets the LM of *this in the 0-th bucket and set IhaveLM to true *this will be normalized */ }; std::ostream& operator<<(std::ostream&, const geobucket&); void AddClear(RefRingElem f, geobucket& gbk); void ReductionStep(geobucket& gbk, ConstRefRingElem g, std::size_t RedLen); void ReductionStepGCD(geobucket& gbk, ConstRefRingElem g, RefRingElem FScale, std::size_t RedLen);
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
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)
void myNormalize(void); // myPoly *=myCoeff; myCoeff 1 void myAddClear(RefRingElem f, int FLen); // *this += f; f = 0; *this normalized void myAddClear(bucket& b); // *this += b; b = 0; *this normalized void myMul(ConstRefRingElem coeff); // *this *= coeff void myDiv(ConstRefRingElem coeff); // *this /= coeff; assumes *this divisible by coeff
Functions on buckets
bool IsZero(const bucket&); RingElem content(const bucket& b); ConstRefRingElem poly(bucket& b); // normalize b and return a reference to the polynomial
Dirty method and function for efficiency (b1 and b2 will be normalized))
static bool 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)
void MoveLM(const SparsePolyRing&, bucket& b1, bucket& b2);
b1 += LM(b2); b2 -= LM(b2); \li it assumes LPP(b1)<LPP(b2)
Member fields
RingElem myPoly;// the polynomial (a RingElem in P) RingElem myCoeff;// the coefficient factor (a RingElem in CoeffRing(P)) unsigned short myMaxLen;// the maximal length allowed for the polynomial of this bucket unsigned short myApproxLen;// an upper bound for the current length of the polynomial of this bucket