Changeset 9e806f in git for kernel/kutil.h


Ignore:
Timestamp:
Jul 12, 2012, 3:24:21 PM (12 years ago)
Author:
Oleksandr Motsak <motsak@…>
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
Children:
010b3f834f90fe0815d115c4a3a4c6934a96ac81
Parents:
cffd3e2f630fbc7b0e35afee97d6fa948cfd0b3e19609cce8ae122e920a77ead0ddc3ea3984ecc0d
Message:
Merge pull request #152 from ederc/sw-sba-ssg

Signature-based algorithms in spielwiese
File:
1 edited

Legend:

Unmodified
Added
Removed

  • kernel/kutil.h

    rcffd3e r9e806f  
    6767{
    6868public:
     69  unsigned long sevSig;
     70  poly sig;   // the signature of the element
    6971  poly p;       // Lm(p) \in currRing Tail(p) \in tailRing
    7072  poly t_p;     // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
    … …  
    7779    i_r;        // index of TObject in R set, or -1 if not in T
    7880  BOOLEAN is_normalized; // true, if pNorm was called on p, false otherwise
     81  // used in incremental sba() with F5C:
     82  // we know some of the redundant elements in
     83  // strat->T beforehand, so we can just discard
     84  // them and do not need to consider them in the
     85  // interreduction process
     86  BOOLEAN is_redundant;
     87  // used in sba's sig-safe reduction:
     88  // sometimes we already know that a reducer
     89  // is sig-safe, so no need for a real
     90  // sig-safeness check
     91  BOOLEAN is_sigsafe;
     92
    7993
    8094#ifdef HAVE_PLURAL 
    … …  
    167181public:
    168182  unsigned long sev;
     183  unsigned long from; // from which polynomial it comes from
     184            // this is important for signature-based
     185            // algorithms
     186  unsigned long checked; // this is the index of S up to which
     187                      // the corresponding LObject was already checked in
     188                      // critical pair creation => when entering the
     189                      // reduction process it is enough to start a second
     190                      // rewritten criterion check from checked+1 onwards
    169191  poly  p1,p2; /*- the pair p comes from,
    170192                 lm(pi) in currRing, tail(pi) in tailring -*/
    … …  
    252274  kStrategy next;
    253275  int (*red)(LObject * L,kStrategy strat);
     276  int (*red2)(LObject * L,kStrategy strat);
    254277  void (*initEcart)(LObject * L);
    255278  int (*posInT)(const TSet T,const int tl,LObject &h);
     279  int (*posInLSba)(const LSet set, const int length,
     280                LObject* L,const kStrategy strat);
    256281  int (*posInL)(const LSet set, const int length,
    257282                LObject* L,const kStrategy strat);
    … …  
    262287  void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
    263288  void (*chainCrit) (poly p,int ecart,kStrategy strat);
     289  BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
     290  BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
     291  BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
    264292  pFDegProc pOrigFDeg;
    265293  pLDegProc pOrigLDeg;
    … …  
    272300  ideal M; /*set of minimal generators*/
    273301  polyset S;
     302  polyset syz;
     303  polyset sig;
    274304  intset ecartS;
     305  intset fromS; // from which S[i] S[j] comes from
     306                // this is important for signature-based
     307                // algorithms
     308  intset syzIdx;// index in the syz array at which the first
     309                // syzygy of component i comes up
     310                // important for signature-based algorithms
     311  BOOLEAN incremental;
     312  unsigned long currIdx;
     313  int max_lower_index;
    275314  intset lenS;
    276315  wlen_set lenSw; /* for tgb.ccc */
    277316  intset fromQ;
    278317  unsigned long* sevS;
     318  unsigned long* sevSyz;
     319  unsigned long* sevSig;
    279320  unsigned long* sevT;
    280321  TSet T;
    … …  
    306347  int cv; // in shift bases: counting V criterion
    307348  int sl,mu;
     349  int syzl,syzmax,syzidxmax;
    308350  int tl,tmax;
    309351  int Ll,Lmax;
    … …  
    367409void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
    368410void deleteInS (int i,kStrategy strat);
     411void deleteInSSba (int i,kStrategy strat);
    369412void cleanT (kStrategy strat);
    370413static inline LSet initL (int nr=setmaxL)
    … …  
    373416void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
    374417void enterSBba (LObject p,int atS,kStrategy strat, int atR = -1);
     418void enterSSba (LObject p,int atS,kStrategy strat, int atR = -1);
    375419void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
    376420void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
    … …  
    381425int posInT2 (const TSet set,const int length,LObject &p);
    382426int posInT11 (const TSet set,const int length,LObject &p);
     427int posInTSig (const TSet set,const int length,LObject &p);
    383428int posInT110 (const TSet set,const int length,LObject &p);
    384429int posInT13 (const TSet set,const int length,LObject &p);
    … …  
    396441
    397442void reorderS (int* suc,kStrategy strat);
     443int posInLF5C (const LSet set, const int length,
     444               LObject* L,const kStrategy strat);
     445int posInLSig (const LSet set, const int length,
     446               LObject* L,const kStrategy strat);
    398447int posInL0 (const LSet set, const int length,
    399448             LObject* L,const kStrategy strat);
    … …  
    437486int redLazy (LObject* h,kStrategy strat);
    438487int redHomog (LObject* h,kStrategy strat);
     488int redSig (LObject* h,kStrategy strat);
     489//adds hSig to be able to check with F5's criteria when entering pairs!
     490void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
    439491void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
    440492void entersets (LObject h);
    … …  
    452504void initS (ideal F, ideal Q,kStrategy strat);
    453505void initSL (ideal F, ideal Q,kStrategy strat);
     506void initSLSba (ideal F, ideal Q,kStrategy strat);
     507/*************************************************
     508 * when initializing a new bunch of principal
     509 * syzygies at the beginning of a new iteration
     510 * step in a signature-based algorithm we
     511 * compute ONLY the leading elements of those
     512 * syzygies, NOT the whole syzygy
     513 * NOTE: this needs to be adjusted for a more
     514 * general approach on signature-based algorithms
     515 ***********************************************/
     516void initSyzRules (kStrategy strat);
    454517void updateS(BOOLEAN toT,kStrategy strat);
     518void enterSyz (LObject p,kStrategy strat);
    455519void enterT (LObject p,kStrategy strat, int atT = -1);
    456520void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
    457521void HEckeTest (poly pp,kStrategy strat);
    458522void initBuchMoraCrit(kStrategy strat);
     523void initSbaCrit(kStrategy strat);
    459524void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
    460525void initBuchMoraPos(kStrategy strat);
     526void initSbaPos(kStrategy strat);
    461527void initBuchMora (ideal F, ideal Q,kStrategy strat);
     528void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
    462529void exitBuchMora (kStrategy strat);
     530void exitSba (kStrategy strat);
    463531void updateResult(ideal r,ideal Q,kStrategy strat);
    464532void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
    465533void kFreeStrat(kStrategy strat);
    466534void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
     535void enterOnePairSig (int i,poly p,poly pSig,int ecart, int isFromQ,kStrategy strat, int atR);
    467536void chainCritNormal (poly p,int ecart,kStrategy strat);
     537void chainCritSig (poly p,int ecart,kStrategy strat);
    468538BOOLEAN homogTest(polyset F, int Fmax);
    469539BOOLEAN newHEdge(kStrategy strat);
     540BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
     541BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
     542KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
     543BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
     544BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
     545BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
    470546// returns index of p in TSet, or -1 if not found
    471547int kFindInT(poly p, TSet T, int tlength);
    … …  
    541617poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
    542618ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
     619ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    543620poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
    544621ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
    545622void initBba(ideal F,kStrategy strat);
     623void initSba(ideal F,kStrategy strat);
     624void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
     625          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
     626          intvec *w,intvec *hilb );
    546627
    547628/***************************************************************
    … …  
    569650                 kStrategy strat = NULL);
    570651
     652// Reduces PR with PW
     653// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
     654// Changes: PR
     655// Const:   PW
     656// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
     657// If strat != NULL, tailRing is changed if reduction would violate exp bound
     658// of tailRing
     659// Returns: 0 everything ok, no tailRing change
     660//          1 tailRing has successfully changed (strat != NULL)
     661//          2 no reduction performed, tailRing needs to be changed first
     662//            (strat == NULL)
     663//          3 no reduction performed, not sig-safe!!!
     664//         -1 tailRing change could not be performed due to exceeding exp
     665//            bound of currRing
     666int ksReducePolySig(LObject* PR,
     667                 TObject* PW,
     668                 long idx,
     669                 poly spNoether = NULL,
     670                 number *coef = NULL,
     671                 kStrategy strat = NULL);
     672
    571673// Reduces PR at Current->next with PW
    572674// Assumes PR != NULL, Current contained in PR
    … …  
    638740void kDebugPrint(kStrategy strat);
    639741
     742// getting sb order for sba computations
     743ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
    640744
    641745KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
Note: See TracChangeset for help on using the changeset viewer.