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 geobuckets, 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