CoCoALib-0.9905 date: 23 May 2007


geobucket.H

Go to the documentation of this file.
00001 #ifndef CoCoA_geobucket_H
00002 #define CoCoA_geobucket_H
00003 
00004 //   Copyright (c)  2005  Anna Bigatti
00005 
00006 //   This file is part of the source of CoCoALib, the CoCoA Library.
00007 
00008 //   CoCoALib is free software; you can redistribute it and/or modify
00009 //   it under the terms of the GNU General Public License (version 2)
00010 //   as published by the Free Software Foundation.  A copy of the full
00011 //   licence may be found in the file COPYING in this directory.
00012 
00013 //   CoCoALib is distributed in the hope that it will be useful,
00014 //   but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 //   GNU General Public License for more details.
00017 
00018 //   You should have received a copy of the GNU General Public License
00019 //   along with CoCoA; if not, write to the Free Software
00020 //   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00021 
00022 
00023 #include "CoCoA/SparsePolyRing.H"
00024 
00025 #include <iosfwd>
00026 // using std::ostream;
00027 #include <vector>
00028 // using std::vector;
00029 
00030 namespace CoCoA
00031 {
00032 
00033   /*-- class geobucket ----------------------------------------------*/
00034   /**
00035 
00036   \brief Implementation of polynomials for fast summation of many short polynomials
00037 
00038   A geobucket is a polynomial represented in a C++ vector of buckets:
00039   a \em bucket contains a polynomial (and some other info)
00040 
00041   This construction is useful when adding many short polynomials
00042   to a long one (in particular the reduction process) because it
00043   lowers the number of calls of "cmp".
00044 
00045   AFTER CALLING  SetLM()
00046   LM(gbk) is in gbk.myBuckets[0], the first bucket
00047   [and then  gbk==0  iff  gbk.myBuckets[0]=0 ]
00048 
00049   gbk.myBuckets[i] contains at most gbk_minlen * gbk_factor^i summands
00050 
00051   */
00052   /*-----------------------------------------------------------------*/
00053 
00054   class geobucket
00055   {
00056   public:
00057 
00058     /*-- class bucket -------------------------------------------------*/
00059     /**
00060         \brief used only in geobuckets
00061 
00062         A bucket represents a polynomial as a product of a polynomial and
00063         a coefficient.
00064 
00065         The coeffient factor is used for fast multiplication of a geobucket
00066         by a coefficient and it comes useful in the reduction process over
00067         a field of fraction of a GCD ring.
00068 
00069         We normalize the bucket only when it is necessary: e.g. to compute
00070         a reference to the LC of the bucket.
00071 
00072         All methods are private (to be used only by geobuckets)
00073 
00074         \*-----------------------------------------------------------------*/
00075 
00076     class bucket
00077     {
00078       friend class geobucket;
00079     public:
00080       bucket(const SparsePolyRing&, std::size_t MaxLen);
00081       bucket(const bucket&);    ///< copy constructor to use C++ vectors of buckets
00082 
00083       ~bucket();
00084 
00085     private:
00086       void myNormalize();    ///< myPoly *= myCoeff; myCoeff = 1
00087       /**< \li \em weak exception guarantee */
00088       void myAddClear(RefRingElem f, std::size_t FLen);    ///< *this += f; f = 0
00089       /**< \li *this will be normalized
00090          \li \em weak exception guarantee */
00091       void myAddClear(bucket& b);                          ///< *this += b; b = 0
00092       /**< \li *this will be normalized
00093          \li \em weak exception guarantee */
00094       void myMulByCoeff(ConstRefRingElem coeff);           ///< *this *= coeff
00095       /**< \li \em weak exception guarantee */
00096       void myDivByCoeff(ConstRefRingElem coeff);           ///< *this /= coeff
00097       /**< \li assumes *this is divisible by coeff
00098          \li \em weak exception guarantee */
00099 
00100 
00101       friend bool IsZero(const bucket& b);
00102       friend RingElem content(const bucket& b);
00103       friend ConstRefRingElem poly(bucket& b);  ///< it normalizes the bucket and returns a reference to the polynomial
00104 
00105       ///@name Dirty functions for efficiency
00106       //@{
00107       static bool myIsZeroAddLCs(const SparsePolyRing&, bucket& b1, bucket& b2);  ///<  b1 += LM(b2);  b2 -= LM(b2);  return LC(b1)+LC(b2)==0
00108       /**< \li it assumes LPP(b1) == LPP(b2)
00109          \li b1 and b2 will be normalized */
00110       friend void MoveLM(bucket& b1, bucket& b2); ///< b1 += LM(b2); b2 -= LM(b2)
00111       friend void MoveLM(const SparsePolyRing&, bucket& b1, bucket& b2); ///< b1 += LM(b2); b2 -= LM(b2)
00112       /**< \li it assumes LPP(b1)<LPP(b2)
00113          \li b1 and b2 will be normalized */
00114       //@}
00115 
00116       ///@name Friends functions on geobuckets
00117       //@{
00118       friend ConstRefPPMonoidElem LPP(const geobucket& gbk);
00119       friend void AddClear(RefRingElem f, geobucket& gbk);
00120       friend void ReductionStep(geobucket& gbk, ConstRefRingElem f, std::size_t RedLen);
00121       friend void MoveLM(RefRingElem f, geobucket& gbk);
00122 
00123       friend std::ostream& operator<<(std::ostream& out, const geobucket& g);
00124       friend void PrintLengths(std::ostream& out, const geobucket& g);
00125       //@}
00126 
00127 
00128       ///@name data members of geobucket::bucket
00129       //@{
00130     private: // data members
00131       RingElem myCoeff;       ///< the coefficient factor
00132       RingElem myPoly;        ///< the polynomial (a "clean" RingElem)
00133       std::size_t myMaxLen;   ///< the maximal length allowed for the polynomial of this bucket
00134       std::size_t myApproxLen;///< an upper bound for the current length of the polynomial of this bucket
00135       //@}
00136 
00137     }; // class geobucket::bucket
00138 
00139 
00140   public:
00141     geobucket(const SparsePolyRing&);
00142     ~geobucket();
00143 
00144     std::size_t mySize(void) const;
00145 
00146     friend std::ostream& operator<<(std::ostream&, const geobucket&);
00147     friend void PrintLengths(std::ostream&,const geobucket&); ///< just for debugging
00148 
00149     void myPushBackZeroBucket(std::size_t MaxLen);
00150     void myAddClear(RefRingElem, std::size_t len);
00151     void myDeleteLM(void);
00152     std::size_t myBucketIndex(std::size_t len); ///< \return the bucket index for a polynomial of length \a len
00153     void myAddMul(ConstRefRingElem monom, ConstRefRingElem g, std::size_t gLen); ///< *this += monom*g
00154     void myAddMul(ConstRefRingElem monom, ConstRefRingElem g, std::size_t gLen, SparsePolyRingBase::SkipLMFlag); ///< *this += monom*g
00155 
00156     friend RingElem content(const geobucket&);
00157     friend void RemoveBigContent(geobucket&);
00158     void myDivByCoeff(ConstRefRingElem coeff); ///< content MUST be divisible by \a coeff
00159     void myMulByCoeff(ConstRefRingElem coeff);
00160     friend const ring& CoeffRing(const geobucket& g);
00161     friend const PPMonoid& PPM(const geobucket& g);
00162     friend void AddClear(RefRingElem f, geobucket& gbk);
00163     friend bool IsZero(const geobucket&);
00164     friend ConstRefRingElem LC(const geobucket&);
00165     friend ConstRefPPMonoidElem LPP(const geobucket&);
00166     void myCascadeFrom(std::size_t i);
00167     friend void MoveLM(RefRingElem g, geobucket& gbk);
00168 
00169     friend void ReductionStep(geobucket& gbk, ConstRefRingElem g, std::size_t RedLen);
00170     friend void ReductionStepGCD(geobucket& gbk, ConstRefRingElem g, RefRingElem FScale, std::size_t RedLen);
00171 
00172     ///@name data members of geobucket
00173     //@{
00174   private: // data members
00175     SparsePolyRing myPolyRing; ///< the SparsePolyRing gbk lives in
00176     mutable  bool IhaveLM; ///< true if certified  that LM(gbk) = LM(gbk[0])
00177     mutable  std::vector<bucket> myBuckets;  ///< the bucket vector
00178     //@}
00179 
00180     void mySetLM() const;  /**< Sets the LM of *this in the 0-th bucket and set IhaveLM to true
00181                             *this will be normalized */
00182 
00183   }; // end of class geobucket
00184 
00185   std::ostream& operator<<(std::ostream&, const geobucket&);
00186   void AddClear(RefRingElem f, geobucket& gbk);
00187   void ReductionStep(geobucket& gbk, ConstRefRingElem g, std::size_t RedLen);
00188   void ReductionStepGCD(geobucket& gbk, ConstRefRingElem g, RefRingElem FScale, std::size_t RedLen);
00189 
00190   //----------------------------------------------------------------------//
00191   // inline functions
00192   //----------------------------------------------------------------------//
00193 
00194   //----------  bucket functions  ----------//
00195 
00196   inline bool IsZero(const geobucket::bucket& b)
00197   { return IsZero(b.myPoly); }
00198 
00199   //----------  geobucket functions  ----------//
00200 
00201 
00202   inline ConstRefPPMonoidElem LPP(const geobucket& gbk)
00203   {
00204     if (!gbk.IhaveLM) gbk.mySetLM();
00205     return LPP(gbk.myBuckets[0].myPoly);
00206     //    return gbk.myPolyRing->myLPP(raw(gbk.myBuckets[0].myPoly));
00207   }
00208 
00209 
00210   inline std::size_t geobucket::mySize(void) const
00211   { return myBuckets.size(); }
00212 
00213 
00214   inline const ring& CoeffRing(const geobucket& g)
00215   { return CoeffRing(g.myPolyRing); }
00216 
00217 
00218   inline const PPMonoid& PPM(const geobucket& g)
00219   { return PPM(g.myPolyRing); }
00220 
00221   // must be inline for efficiency (I checked!)
00222   inline bool IsZero(const geobucket& g)
00223   {
00224     if (!g.IhaveLM) g.mySetLM();
00225     return IsZero(g.myBuckets[0]);
00226   }
00227 
00228 } // end of namespace CoCoA
00229 
00230 
00231 
00232 // RCS header/log in the next few lines
00233 // $Header: /Volumes/Home/cocoa/cvs-repository/CoCoALib-0.99/include/CoCoA/geobucket.H,v 1.1.1.1 2007/03/09 15:16:11 abbott Exp $
00234 // $Log: geobucket.H,v $
00235 // Revision 1.1.1.1  2007/03/09 15:16:11  abbott
00236 // Imported files
00237 //
00238 // Revision 1.6  2007/02/12 19:04:49  cocoa
00239 // Very minor mods to geobucket.
00240 //
00241 // Revision 1.5  2006/12/20 18:58:48  cocoa
00242 // -- only white space differences
00243 //
00244 // Revision 1.4  2006/12/06 17:17:44  cocoa
00245 // -- removed #include "config.H"
00246 //
00247 // Revision 1.3  2006/10/06 14:04:15  cocoa
00248 // Corrected position of #ifndef in header files.
00249 // Separated CoCoA_ASSERT into assert.H from config.H;
00250 // many minor consequential changes (have to #include assert.H).
00251 // A little tidying of #include directives (esp. in Max's code).
00252 //
00253 // Revision 1.2  2006/06/20 17:25:27  cocoa
00254 // -- added function geobucket::myAddMul(monom, g, gLen);   [without SkipLMFlag]
00255 //
00256 // Revision 1.1.1.1  2006/05/30 11:39:36  cocoa
00257 // Imported files
00258 //
00259 // Revision 1.12  2006/04/27 15:57:43  cocoa
00260 // -- minor tidying
00261 //
00262 // Revision 1.11  2006/04/27 14:15:07  cocoa
00263 // -- added constant [ gbk_numbuckets = 20 ] to avoid realloc of geobuckets
00264 //
00265 // Revision 1.10  2006/04/27 13:42:26  cocoa
00266 // Parameter name change for better readability.
00267 //
00268 // Revision 1.9  2006/04/10 10:24:12  cocoa
00269 // -- changed all unsigned int/short into size_t (ex-bug for 4x4)
00270 //
00271 // Revision 1.8  2006/03/24 14:21:49  cocoa
00272 // -- added declarations of ReductionStep, and ReductionStepGCD
00273 //
00274 // Revision 1.7  2006/03/16 12:43:01  cocoa
00275 // -- changed: myMul, myDiv --> myMulByCoeff, myDivByCoeff
00276 //
00277 // Revision 1.6  2006/03/13 16:57:49  cocoa
00278 // -- changed: member data  myPolyRing  is no longer a reference
00279 //
00280 // Revision 1.5  2006/03/07 16:50:44  cocoa
00281 // -- changed: LPP returns a ConstRefPPMonoidElem (as all LPP functions)
00282 //
00283 // Revision 1.4  2006/03/01 14:24:17  cocoa
00284 // -- removed DivMask from geobuckets (not generally useful)
00285 //
00286 // Revision 1.3  2006/01/17 10:23:08  cocoa
00287 // Updated DivMask; many consequential changes.
00288 // A few other minor fixes.
00289 //
00290 // Revision 1.2  2005/12/31 12:22:18  cocoa
00291 // Several minor tweaks to silence the Microsoft compiler:
00292 //  - added some missing #includes and using directives
00293 //  - moved some function defns into the right namespace
00294 //  - etc.
00295 //
00296 // Revision 1.1.1.1  2005/10/17 10:46:54  cocoa
00297 // Imported files
00298 //
00299 // Revision 1.3  2005/07/01 16:08:16  cocoa
00300 // Friday check-in.  Major change to structure under PolyRing:
00301 // now SparsePolyRing and DUPolyRing are separated (in preparation
00302 // for implementing iterators).
00303 //
00304 // A number of other relatively minor changes had to be chased through
00305 // (e.g. IndetPower).
00306 //
00307 // Revision 1.2  2005/06/22 14:47:56  cocoa
00308 // PPMonoids and PPMonoidElems updated to mirror the structure
00309 // used for rings and RingElems.  Many consequential changes.
00310 //
00311 // Revision 1.1.1.1  2005/05/03 15:47:30  cocoa
00312 // Imported files
00313 //
00314 // Revision 1.3  2005/04/19 14:06:04  cocoa
00315 // Added GPL and GFDL licence stuff.
00316 //
00317 // Revision 1.2  2005/02/11 14:15:20  cocoa
00318 // New style ring elements and references to ring elements;
00319 // I hope I have finally got it right!
00320 //
00321 // Revision 1.1.1.1  2005/01/27 15:12:13  cocoa
00322 // Imported files
00323 //
00324 // Revision 1.8  2004/11/11 13:24:01  cocoa
00325 // -- change: PrintLengths now takes an ostream as first argument
00326 //
00327 // Revision 1.7  2004/11/02 14:49:50  cocoa
00328 // -- just a little fix for doxygen (\return -> return)
00329 //
00330 // Revision 1.6  2004/10/29 16:17:11  cocoa
00331 // -- new function LPPwMask  (a bit dirty for allowing geobuckets without DivMask
00332 // -- new constructor with DivMask::base
00333 //
00334 // Revision 1.5  2004/09/20 15:31:51  cocoa
00335 // -- only an "\a" for doxygen
00336 //
00337 // Revision 1.4  2004/07/27 16:03:38  cocoa
00338 // Added IsCommutative test and IamCommutative member function
00339 // to all rings.  Tidied geobuckets a little.
00340 //
00341 // Revision 1.3  2003/10/09 13:32:15  cocoa
00342 // A few glitches which slipped through the first major merge.
00343 //
00344 // Revision 1.2  2003/09/30 09:35:26  cocoa
00345 // - new coding convention "my"
00346 //
00347 // Revision 1.1.1.1  2003/09/24 12:55:43  cocoa
00348 // Imported files
00349 //
00350 // Revision 1.15  2003/06/27 10:59:09  bigatti
00351 // - added short documentation for geobucket fields
00352 //
00353 // Revision 1.14  2003/06/23 17:11:08  abbott
00354 // Minor cleaning prior to public release.
00355 // Reindented.
00356 //
00357 // Revision 1.13  2003/05/15 12:04:39  bigatti
00358 // - Poly(b) --> poly(b)
00359 //
00360 // Revision 1.12  2003/05/14 16:34:49  bigatti
00361 // - new ring syntax
00362 // - doxygen documentation syntax
00363 // - ..LPP --> ..LM
00364 // - cleaning
00365 //
00366 // Revision 1.11  2002/11/18 18:03:26  bigatti
00367 // - code for reduction on GCD rings
00368 // - removed default length in some funcion calls
00369 // - removed flag  IamNormalized
00370 //
00371 // Revision 1.10  2002/09/19 17:14:25  bigatti
00372 // - Optimizations with: myApproxLen, myMaxLen, IamNormalized
00373 //
00374 // Revision 1.9  2002/04/29 16:13:04  bigatti
00375 // - added function: "bucket::normalize()"
00376 // - modified function: "CascadeFrom" [was "cascade"]
00377 //
00378 // Revision 1.8  2002/04/15 15:18:37  bigatti
00379 // - new function: cascade
00380 // - class bucket made public
00381 // - SetLPP adds LC*LPP into myBuckets[0]
00382 // - myBuckets[0] of length gbk_minlen (used to be just 1)
00383 // - works for GCD rings (mul not optimized yet)
00384 //
00385 // Revision 1.7  2002/03/21 15:21:07  bigatti
00386 // - new: bucket class
00387 //
00388 // Revision 1.6  2002/01/10 13:20:23  bigatti
00389 // - new structure of reduction
00390 //
00391 // Revision 1.5  2001/12/07 13:12:09  bigatti
00392 // - applied coding conventions
00393 //
00394 // Revision 1.4  2001/12/04 17:39:23  bigatti
00395 // - changed "IsZero"
00396 //
00397 // Revision 1.3  2001/11/30 21:16:53  bigatti
00398 // - changed names: myBuckets, myR, myPPM
00399 // - added init_clear(DMP& f)
00400 //
00401 // Revision 1.2  2001/11/16 19:21:43  bigatti
00402 // added:  std::
00403 // for compatibility with gcc-3
00404 //
00405 // Revision 1.1  2001/11/07 12:54:33  abbott
00406 // Initial revision
00407 //
00408 
00409 #endif

Generated on Wed May 23 13:45:22 2007 for CoCoALib by  doxygen 1.4.6