Changeset 649021 in git

Timestamp:

Dec 8, 2018, 9:57:54 AM (5 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

a548d67bbd30d76652bb8a6596850125133a2374

Parents:

ac8f852ee98f3d2c31345586af75ef366f73758d5529319cbb0358eaef7fc55c04b6726e9cba7e09

Message:

Merge branch 'rightGB' into christmas-release

Files:

• Singular/LIB/fpalgebras.lib (modified) (1 diff)
• Singular/LIB/freegb.lib (modified) (1 diff)
• Singular/extra.cc (modified) (1 diff)
• kernel/GBEngine/kstd1.cc (modified) (2 diffs)
• kernel/GBEngine/kstd1.h (modified) (1 diff)
• kernel/GBEngine/kstd2.cc (modified) (5 diffs)
• kernel/GBEngine/kutil.cc (modified) (26 diffs)
• kernel/GBEngine/kutil.h (modified) (3 diffs)
• kernel/GBEngine/shiftgb.cc (modified) (1 diff)
• kernel/GBEngine/shiftgb.h (modified) (1 diff)
• libpolys/polys/shiftop.cc (modified) (4 diffs)

Singular/LIB/fpalgebras.lib

@@ -4 +4 @@
 info="
 LIBRARY: fpalgebras.lib    Definitions of some finitely presented algebras and groups (Letterplace)
-AUTHORS: Karim Abou Zeid,       karim.abou.zeid at rwth-aachen.de
-         Viktor Levandovskyy,   viktor.levandovskyy at math.rwth-aachen.de
+AUTHORS: Karim Abou Zeid,       karim.abou.zeid at rwth-aachen.de@*
+         Viktor Levandovskyy,   viktor.levandovskyy at math.rwth-aachen.de@*
          Grischa Studzinski,    grischa.studzinski at rwth-aachen.de
 

Singular/LIB/freegb.lib

@@ -444 +444 @@
   ideal J = letplaceGBasis(I);
   J;
+}
+
+proc lpRightStd(ideal F, ideal Q)
+{
+  return (system("rightgb", F, Q));
 }
 

Singular/extra.cc

@@ -1243 +1243 @@
     else
   #endif
-  /*==================== rightgb for freeGB  ====================*/
+ /*==================== freeAlgebra for freeGB  ==================*/
   #ifdef HAVE_SHIFTBBA
-    if (strcmp(sys_cmd, "rightgb") == 0)
-    {
-      const short t[]={2,IDEAL_CMD,IDEAL_CMD};
+    if (strcmp(sys_cmd, "freeAlgebra") == 0)
+    {
+      // copied from freegb.cc
+      const short t[]={2,RING_CMD,INT_CMD};
       if (iiCheckTypes(h,t,1))
       {
-        ideal F=(ideal)h->CopyD();
-        ideal Q=(ideal)(h->next->CopyD());
-        res->rtyp = IDEAL_CMD;
-        res->data = rightgb(F, Q);
-        return FALSE;
+        ring r=(ring)h->Data();
+        int d=(int)((long)h->next->Data());
+        if (d<2)
+        {
+          WerrorS("degree must be >=2");
+          return TRUE;
+        }
+        int i=0;
+        while(r->order[i]!=0)
+        {
+          if ((r->order[i]==ringorder_c) ||(r->order[i]==ringorder_C)) i++;
+          else if ((r->block0[i]==1)&&(r->block1[i]==r->N)) i++;
+          else
+          {
+            WerrorS("only for rings with a global ordering of one block");
+            return TRUE;
+          }
+        }
+        if ((r->order[i]!=0)
+            || (rHasLocalOrMixedOrdering(r)))
+        {
+          //WerrorS("only for rings with a global ordering of one block");
+          Werror("only for rings with a global ordering of one block,i=%d, o=%d",i,r->order[i]);
+          return TRUE;
+        }
+        ring R=freeAlgebra(r,d);
+        res->rtyp=RING_CMD;
+        res->data=R;
+        return R==NULL;
       }
       else return TRUE;

kernel/GBEngine/kstd1.cc

@@ -2568 +2568 @@
 #ifdef HAVE_SHIFTBBA
 ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
-                int newIdeal, intvec *vw)
+                int newIdeal, intvec *vw, BOOLEAN rightGB)
 {
   ideal r;
@@ -2575 +2575 @@
   kStrategy strat=new skStrategy;
   intvec* temp_w=NULL;
+
+  strat->rightGB = rightGB;
 
   if(!TEST_OPT_RETURN_SB)

kernel/GBEngine/kstd1.h

@@ -39 +39 @@
           int syzComp=0,int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL);
 
-ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
-                int newIdeal, intvec *vw);
+ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** mw, intvec *hilb=NULL,
+    int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE);
 
 /* the following global data are defined in kutil.cc */

kernel/GBEngine/kstd2.cc

@@ -4178 +4178 @@
   initBbaShift(strat); /* DONE */
   /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
-  /*Shdl=*/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
-  updateSShift(strat); /* initializes T */
+  /*Shdl=*/initBuchMora(F, Q,strat);
   if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
   reduc = olddeg = 0;
@@ -4352 +4351 @@
         // posInS only depends on the leading term
         strat->enterS(strat->P, pos, strat, strat->tl);
-        enterTShift(strat->P, strat);
+        if (!strat->rightGB)
+          enterTShift(strat->P, strat);
       }
 
@@ -4369 +4369 @@
           // and add pairs
           int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
-          int atR=strat->tl+1; // enterTShift introduces P.p=T[tl+1], T[tl+2]...
-          enterTShift(strat->P,strat,-1);
-          enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, atR);
-          strat->enterS(strat->P, pos, strat, atR);
+          enterT(strat->P, strat);
+          enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+          strat->enterS(strat->P, pos, strat, strat->tl);
+          if (!strat->rightGB)
+            enterTShift(strat->P,strat);
         }
       }
@@ -4393 +4394 @@
     for (int k = 0; k <= strat->sl; ++k)
     {
+      if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
       for (int j = 0; j<=strat->tl; ++j)
       {
@@ -4457 +4459 @@
 
 
-ideal freegb(ideal I)
+ideal freegb(ideal F)
 {
   assume(rIsLPRing(currRing));
-  assume(idIsInV(I));
-  ideal RS = kStdShift(I,NULL, testHomog, NULL,NULL,0,0,NULL);
+  assume(idIsInV(F));
+  ideal RS = kStdShift(F, NULL, testHomog, NULL);
+  idSkipZeroes(RS); // is this even necessary?
+  assume(idIsInV(RS));
+  return(RS);
+}
+
+ideal rightgb(ideal F, ideal Q)
+{
+  assume(rIsLPRing(currRing));
+  assume(idIsInV(F));
+  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
   idSkipZeroes(RS); // is this even necessary?
   assume(idIsInV(RS));

kernel/GBEngine/kutil.cc

@@ -8035 +8035 @@
       Print("\n  %d:",i);
       p_wrp(strat->S[i], currRing, strat->tailRing);
+      if (strat->fromQ!=NULL && strat->fromQ[i])
+        Print(" (from Q)");
     }
     strat->news = FALSE;
@@ -9151 +9153 @@
         enterT(h,strat);
         strat->S_2_R[i] = strat->tl;
+#ifdef HAVE_SHIFTBBA
+        if (currRing->isLPring)
+          enterTShift(h, strat);
+#endif
       }
     }
@@ -9247 +9253 @@
       enterT(h,strat);
       strat->S_2_R[i] = strat->tl;
+#ifdef HAVE_SHIFTBBA
+      if (currRing->isLPring)
+        enterTShift(h, strat);
+#endif
     }
     if (suc!= -1) updateS(toT,strat);
@@ -9361 +9371 @@
 void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR)
 {
-  int toInsert = itoInsert(p.p, strat->tailRing);
-  for (int i = toInsert; i > 0; i--)
+  int maxPossibleShift = p_mLPmaxPossibleShift(p.p, strat->tailRing);
+  for (int i = maxPossibleShift; i > 0; i--)
   {
     LObject qq;
@@ -10204 +10214 @@
   strat->cp = 0;
   strat->c3 = 0;
+#ifdef HAVE_SHIFTBBA
+  strat->cv = 0;
+#endif
   strat->tail = pInit();
   /*- set s -*/
@@ -10267 +10280 @@
     updateS(TRUE,strat);
   }
-  if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
-  strat->fromQ=NULL;
+#ifdef HAVE_SHIFTBBA
+  if (!(rIsLPRing(currRing) && strat->rightGB)) // for right GB, we need to check later whether a poly is from Q
+#endif
+  {
+    if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
+    strat->fromQ=NULL;
+  }
   assume(kTest_TS(strat));
 }
@@ -10288 +10306 @@
   pLmFree(&strat->tail);
   strat->syzComp=0;
+
+#ifdef HAVE_SHIFTBBA
+  if (rIsLPRing(currRing) && strat->rightGB)
+  {
+    if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
+    strat->fromQ=NULL;
+  }
+#endif
 }
 
@@ -12180 +12206 @@
 
 #ifdef HAVE_SHIFTBBA
-/* including the self pairs */
-void updateSShift(kStrategy strat)
-{
-  /* to use after updateS(toT=FALSE,strat) */
-  /* fills T with shifted elt's of S */
-  int i;
-  LObject h;
-  int atT = -1; // or figure out smth better
-  strat->tl = -1; // init
-  for (i=0; i<=strat->sl; i++)
-  {
-    memset(&h,0,sizeof(h));
-    h.p =  strat->S[i];
-    strat->initEcart(&h);
-    h.sev = strat->sevS[i];
-    h.t_p = NULL;
-    h.GetTP(); // creates correct t_p
-    /*puts the elements of S with their shifts to T*/
-    //    int atT, int uptodeg, int lV)
-    strat->S_2_R[i] = strat->tl + 1; // the el't with shift 0 will be inserted first
-    // need a small check for above; we insert >=1 elements
-    // insert this check into kTest_TS ?
-    enterTShift(h,strat,atT);
-  }
-  /* what about setting strat->tl? */
+// creates if possible (q,p), (shifts(q),p)
+static void enterOnePairWithShifts (int q_inS /*also i*/, poly q, poly p, int ecartp, int p_isFromQ, kStrategy strat, int atR, int p_lastVblock, int q_lastVblock)
+{
+  // note: ecart and isFromQ is for p
+  assume(q_inS < 0 || strat->S[q_inS] == q); // if q is from S, q_inS should be the index of q in S
+  assume(pmFirstVblock(p) == 1);
+  assume(pmFirstVblock(q) == 1);
+  assume(p_lastVblock == pmLastVblock(p));
+  assume(q_lastVblock == pmLastVblock(q));
+
+  // TODO: is ecartq = 0 still ok?
+  int ecartq = 0; //Hans says it's ok; we're in the homog case, no ecart
+
+  int q_isFromQ = 0;
+  if (strat->fromQ != NULL && q_inS >= 0)
+    q_isFromQ = strat->fromQ[q_inS];
+
+  int degbound = currRing->N/currRing->isLPring;
+  int neededShift = p_lastVblock - 1;
+  int maxPossibleShift = degbound - q_lastVblock;
+  int maxShift = si_min(neededShift, maxPossibleShift);
+  int firstShift = (q == p ? 1 : 0); // do not add (q,p) if q=p
+  for (int j = firstShift; j <= maxShift; j++) 
+  {
+    poly qq = pLPCopyAndShiftLM(q, j);
+    enterOnePairShift(qq, p, ecartp, p_isFromQ, strat, -1, ecartq, q_isFromQ, j, q_inS);
+  }
 }
 #endif
 
 #ifdef HAVE_SHIFTBBA
-void initBuchMoraShift (ideal F,ideal Q,kStrategy strat)
-{
-  strat->interpt = BTEST1(OPT_INTERRUPT);
-  strat->kHEdge=NULL;
-  if (rHasGlobalOrdering(currRing)) strat->kHEdgeFound=FALSE;
-  /*- creating temp data structures------------------- -*/
-  strat->cp = 0;
-  strat->c3 = 0;
-  strat->cv = 0;
-  strat->tail = pInit();
-  /*- set s -*/
-  strat->sl = -1;
-  /*- set L -*/
-  strat->Lmax = setmaxL;
-  strat->Ll = -1;
-  strat->L = initL();
-  /*- set B -*/
-  strat->Bmax = setmaxL;
-  strat->Bl = -1;
-  strat->B = initL();
-  /*- set T -*/
-  strat->tl = -1;
-  strat->tmax = setmaxT;
-  strat->T = initT();
-  strat->R = initR();
-  strat->sevT = initsevT();
-  /*- init local data struct.---------------------------------------- -*/
-  strat->P.ecart=0;
-  strat->P.length=0;
-  if (rHasLocalOrMixedOrdering(currRing))
-  {
-    if (strat->kHEdge!=NULL) pSetComp(strat->kHEdge, strat->ak);
-    if (strat->kNoether!=NULL) pSetComp(strat->kNoetherTail(), strat->ak);
-  }
-  if(rField_is_Ring(currRing))
-  {
-    /*Shdl=*/initSL(F, Q,strat); /*sets also S, ecartS, fromQ */
-  }
-  {
-    if(TEST_OPT_SB_1)
-    {
-      int i;
-      ideal P=idInit(IDELEMS(F)-strat->newIdeal,F->rank);
-      for (i=strat->newIdeal;i<IDELEMS(F);i++)
-      {
-        P->m[i-strat->newIdeal] = F->m[i];
-        F->m[i] = NULL;
-      }
-      initSSpecial(F,Q,P,strat);
-      for (i=strat->newIdeal;i<IDELEMS(F);i++)
-      {
-        F->m[i] = P->m[i-strat->newIdeal];
-        P->m[i-strat->newIdeal] = NULL;
-      }
-      idDelete(&P);
-    }
-    else
-    {
-      /*Shdl=*/initSL(F, Q,strat); /*sets also S, ecartS, fromQ */
-      // /*Shdl=*/initS(F, Q,strat); /*sets also S, ecartS, fromQ */
-    }
-  }
-  strat->fromT = FALSE;
-  if (!TEST_OPT_SB_1)
-  {
-    /* the only change: we do not fill the set T*/
-    if(!rField_is_Ring(currRing)) updateS(FALSE,strat);
-  }
-  if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
-  strat->fromQ=NULL;
-  /* more changes: fill the set T with all the shifts of elts of S*/
-  /* is done by other procedure */
+// creates if possible (q,p), use it when q is already shifted
+static void enterOnePairWithoutShifts (int p_inS /*also i*/, poly q, poly p, int ecartq, int q_isFromQ, kStrategy strat, int atR, int p_lastVblock, int q_shift)
+{
+  // note: ecart and isFromQ is for p
+  assume(p_inS < 0 || strat->S[p_inS] == p); // if p is from S, p_inS should be the index of p in S
+  assume(pmFirstVblock(p) == 1);
+  assume(p_lastVblock == pmLastVblock(p));
+  assume(q_shift == pmFirstVblock(q) - 1);
+
+  // TODO: is ecartp = 0 still ok?
+  int ecartp = 0; //Hans says it's ok; we're in the homog e:, no ecart
+
+  int p_isFromQ = 0;
+  if (strat->fromQ != NULL && p_inS >= 0)
+    p_isFromQ = strat->fromQ[p_inS];
+
+  int maxNeededShift = p_lastVblock - 1;
+  if (q_shift <= maxNeededShift)
+    enterOnePairShift(q, p, ecartp, p_isFromQ, strat, -1, ecartq, q_isFromQ, q_shift, -1);
 }
 #endif
 
 #ifdef HAVE_SHIFTBBA
-/*1
-* put the pairs (sh \dot s[i],p)  into the set B, ecart=ecart(p)
-*/
-static void enterOnePairManyShifts (int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
-{
-  poly s = strat->S[i];
-  assume(i<=strat->sl); // from OnePair
-
-  /* cycles through all shifts of s[i] until uptodeg - lastVblock(s[i]) */
-  /* that is create the pairs (f, s \dot g)  */
-
-  //  poly q = pCopy(pHead(strat->S[i])); // lm in currRing
-  //  pNext(q) = prCopyR(pNext(strat->S[i]),strat->tailRing,currRing); // zero shift
-
- /* determine how many elements we have to insert for a given s[i] */
-  /* x(0)y(1)z(2) : lastVblock-1=2, to add until lastVblock=uptodeg-1 */
-  /* hence, a total number of elt's to add is: */
-  /*  int toInsert = 1 + (uptodeg-1) - (pLastVblock(p.p, lV) -1);  */
-  int toInsert =  itoInsert(s, currRing);
-
-
-  /* these vars hold for all shifts of s[i] */
-  int ecartq = 0; //Hans says it's ok; we're in the homog case, no ecart
-
-  int qfromQ;
-  if (strat->fromQ != NULL)
-  {
-    qfromQ = strat->fromQ[i];
-  }
-  else
-  {
-    qfromQ = -1;
-  }
-
-  // for the 0th shift: insert the orig. pair
-  enterOnePairShift(s, p, ecart, isFromQ, strat, -1, ecartq, qfromQ, 0, i);
-
-  for (int j = 1; j <= toInsert; j++)
-  {
-    poly q = pLPCopyAndShiftLM(s, j);
-    enterOnePairShift(q, p, ecart, isFromQ, strat, -1, ecartq, qfromQ, j, i);
-  }
-}
-#endif
-
-#ifdef HAVE_SHIFTBBA
-/*1
-* put the pairs (sh \dot qq,p)  into the set B, ecart=ecart(p)
-* despite the name, not only self shifts
-*/
-void enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int /*atR*/)
-{
-  /* should cycle through all shifts of q until uptodeg - lastVblock(q) */
-  /* that is create the pairs (f, s \dot g)  */
-
-  int toInsert =  itoInsert(qq, currRing);
-
-  /* these vars hold for all shifts of s[i] */
-  int ecartq = 0; //Hans says it's ok; we're in the homog case, no ecart
-  int qfromQ = 0; // strat->fromQ[i];
-
-  /* since this proc is applied twice for (h, s*g) and (g,s*h), init j with 1 */
-  for (int j = 1; j<= toInsert; j++)
-  {
-    poly q = pLPCopyAndShiftLM(qq, j);
-    enterOnePairShift(q, p, ecart, isFromQ, strat, -1, ecartq, qfromQ, j, -1);
-  }
-}
-#endif
-
-#ifdef HAVE_SHIFTBBA
+
+#ifdef KDEBUG
+// enable to print which pairs are considered or discarded and why
+/* #define CRITERION_DEBUG */
+#endif
 /*2
 * put the pair (q,p)  into the set B, ecart=ecart(p), q is the shift of some s[i]
@@ -12361 +12270 @@
 void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS)
 {
+#ifdef CRITERION_DEBUG
+  if (TEST_OPT_DEBUG)
+  {
+    PrintS("Consider pair ("); wrp(q); PrintS(", "); wrp(p); PrintS(")"); PrintLn();
+    // also write the LMs in separate lines:
+    poly lmq = pHead(q);
+    poly lmp = pHead(p);
+    pSetCoeff(lmq, n_Init(1, currRing->cf));
+    pSetCoeff(lmp, n_Init(1, currRing->cf));
+    Print("    %s\n", pString(lmq));
+    Print("    %s\n", pString(lmp));
+    pLmDelete(lmq);
+    pLmDelete(lmp);
+  }
+#endif
 
   /* Format: q and p are like strat->P.p, so lm in CR, tail in TR */
@@ -12370 +12294 @@
   assume(p_CheckIsFromRing(pNext(p),strat->tailRing));
 
-#ifdef KDEBUG
-//    if (TEST_OPT_DEBUG)
-//    {
-//       PrintS("enterOnePairShift(q,p) invoked with q = ");
-//       wrp(q); //      wrp(pHead(q));
-//       PrintS(", p = ");
-//       wrp(p); //wrp(pHead(p));
-//       PrintLn();
-//    }
-#endif
-
   /* poly q stays for s[i], ecartq = ecart(q), qisFromQ = applies to q */
 
@@ -12397 +12310 @@
   Lp.lcm = p_Lcm(p,q, currRing); // q is what was strat->S[i], so a poly in LM/TR presentation
 
-  /* apply the V criterion */
-  if (!pIsInV(Lp.lcm))
-  {
-#ifdef KDEBUG
-    if (TEST_OPT_DEBUG)
-    {
-      PrintS("V crit applied to q = ");
-      wrp(q); //      wrp(pHead(q));
-      PrintS(", p = ");
-      wrp(p); //wrp(pHead(p));
-      PrintLn();
-    }
-#endif
+  /* the V criterion */
+  if (!pmIsInV(Lp.lcm))
+  {
+    strat->cv++; // counter for applying the V criterion
     pLmFree(Lp.lcm);
-    /* + counter for applying the V criterion */
-    strat->cv++;
+#ifdef CRITERION_DEBUG
+    if (TEST_OPT_DEBUG) PrintS("--- V crit\n");
+#endif
     return;
   }
@@ -12437 +12342 @@
       strat->cp++;
       pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+      if (TEST_OPT_DEBUG) PrintS("--- prod crit\n");
+#endif
       return;
     }
@@ -12444 +12352 @@
     {
       pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+      if (TEST_OPT_DEBUG) PrintS("--- ecartq > ecart\n");
+#endif
       return;
       /*the pair is (s[i],t[.]), discard it if the ecart is too big*/
@@ -12466 +12377 @@
           {
             pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+            if (TEST_OPT_DEBUG) Print("--- divided by B[%d]\n", j);
+#endif
             return;
           }
@@ -12475 +12389 @@
         {
           deleteInL(strat->B,&strat->Bl,j,strat);
+#ifdef CRITERION_DEBUG
+          if (TEST_OPT_DEBUG) Print("divides B[%d] -> delete B[%d]\n", j, j);
+#endif
           strat->c3++;
         }
@@ -12504 +12421 @@
           strat->cp++;
           pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+          if (TEST_OPT_DEBUG) PrintS("--- prod crit\n");
+#endif
           return;
       }
@@ -12509 +12429 @@
       {
         pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+        if (TEST_OPT_DEBUG) PrintS("--- ecartq > ecart\n");
+#endif
         return;
         /*the pair is (s[i],t[.]), discard it if the ecart is too big*/
@@ -12527 +12450 @@
           {
             pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+            if (TEST_OPT_DEBUG) Print("--- divided by B[%d]\n", j);
+#endif
             return;
           }
@@ -12535 +12461 @@
         {
           deleteInL(strat->B,&strat->Bl,j,strat);
+#ifdef CRITERION_DEBUG
+          if (TEST_OPT_DEBUG) Print("divides B[%d] -> delete B[%d]\n", j, j);
+#endif
           strat->c3++;
         }
@@ -12547 +12476 @@
     pNorm(p);
   if ((q==NULL) || (p==NULL))
+  {
+#ifdef CRITERION_DEBUG
+    if (TEST_OPT_DEBUG) PrintS("--- q == NULL || p == NULL\n");
+#endif
     return;
+  }
   if ((strat->fromQ!=NULL) && (isFromQ!=0) && (qfromQ!=0))
+  {
     Lp.p=NULL;
+#ifdef CRITERION_DEBUG
+    if (TEST_OPT_DEBUG) PrintS("--- pair from Q\n");
+#endif
+  }
   else
   {
@@ -12607 +12546 @@
     */
     if (Lp.lcm!=NULL) pLmFree(Lp.lcm);
+#ifdef CRITERION_DEBUG
+    if (TEST_OPT_DEBUG) PrintS("--- S-poly = 0\n");
+#endif
   }
   else
@@ -12643 +12585 @@
     l = strat->posInL(strat->B,strat->Bl,&Lp,strat);
     enterL(&strat->B,&strat->Bl,&strat->Bmax,Lp,l);
+#ifdef CRITERION_DEBUG
+    if (TEST_OPT_DEBUG) PrintS("+++ Entered pair\n");
+#endif
   }
 }
@@ -12655 +12600 @@
 void initenterpairsShift (poly h,int k,int ecart,int isFromQ, kStrategy strat, int atR)
 {
+  int h_lastVblock = pmLastVblock(h);
+  assume(h_lastVblock != 0 || pLmIsConstantComp(h));
+  // TODO: is it allowed to skip pairs with constants? also with constants from other components?
+  if (h_lastVblock == 0) return;
+  assume(pmFirstVblock(h) == 1);
   /* h comes from strat->P.p, that is LObject with LM in currRing and Tail in tailRing */
   //  atR = -1;
@@ -12660 +12610 @@
   || (pGetComp(h)<=strat->syzComp))
   {
-    int j;
+    int i,j;
     BOOLEAN new_pair=FALSE;
 
+    int degbound = currRing->N/currRing->isLPring;
+    int maxShift = degbound - h_lastVblock;
+
     if (pGetComp(h)==0)
     {
+      if (strat->rightGB)
+      {
+        if (isFromQ)
+        {
+          // pairs (shifts(h),s[1..k]), (h, s[1..k])
+          for (i=0; i<=maxShift; i++)
+          {
+            poly hh = pLPCopyAndShiftLM(h, i);
+            for (j=0; j<=k; j++)
+            {
+              if (strat->fromQ == NULL || !strat->fromQ[j])
+              {
+                new_pair=TRUE;
+                poly s = strat->S[j];
+                enterOnePairWithoutShifts(j, hh, s, ecart, isFromQ, strat, atR, pmLastVblock(s), i);
+              }
+            }
+          }
+        }
+        else
+        {
+          new_pair=TRUE;
+          for (j=0; j<=k; j++)
+          {
+            poly s = strat->S[j];
+            if (strat->fromQ != NULL && strat->fromQ[j])
+            {
+              // pairs (shifts(s[j]),h), (s[j],h)
+              enterOnePairWithShifts(j, s, h, ecart, isFromQ, strat, atR, h_lastVblock, pmLastVblock(s));
+            }
+            else
+            {
+              // pair (h, s[j])
+              enterOnePairWithoutShifts(j, h, s, ecart, isFromQ, strat, atR, pmLastVblock(s), 0);
+            }
+          }
+        }
+      }
       /* for Q!=NULL: build pairs (f,q),(f1,f2), but not (q1,q2)*/
-      if ((isFromQ)&&(strat->fromQ!=NULL))
-      {
-        for (j=0; j<=k; j++)
-        {
+      else if ((isFromQ)&&(strat->fromQ!=NULL))
+      {
+        // pairs (shifts(s[1..k]),h), (s[1..k],h)
+        for (j=0; j<=k; j++) {
           if (!strat->fromQ[j])
           {
             new_pair=TRUE;
-            enterOnePairManyShifts(j,h,ecart,isFromQ,strat, atR);
-            // other side pairs:
-            enterOnePairSelfShifts(h,strat->S[j],ecart,isFromQ,strat, atR);
-          //Print("j:%d, Ll:%d\n",j,strat->Ll);
+            poly s = strat->S[j];
+            enterOnePairWithShifts(j, s, h, ecart, isFromQ, strat, atR, h_lastVblock, pmLastVblock(s));
           }
         }
+        // pairs (shifts(h),s[1..k])
+        if (new_pair)
+        {
+          for (i=1; i<=maxShift; i++)
+          {
+            poly hh = pLPCopyAndShiftLM(h, i);
+            for (j=0; j<=k; j++)
+            {
+              if (!strat->fromQ[j])
+              {
+                poly s = strat->S[j];
+                enterOnePairWithoutShifts(j, hh, s, ecart, isFromQ, strat, atR, pmLastVblock(s), i);
+              }
+            }
+          }
+        }
       }
       else
       {
         new_pair=TRUE;
+        // pairs (shifts(s[1..k]),h), (s[1..k],h)
+        for (j=0; j<=k; j++) {
+          poly s = strat->S[j];
+          // TODO: cache lastVblock of s[1..k] for later use
+          enterOnePairWithShifts(j, s, h, ecart, isFromQ, strat, atR, h_lastVblock, pmLastVblock(s));
+        }
+        // pairs (shifts(h),s[1..k]), (shifts(h), h)
+        for (i=1; i<=maxShift; i++)
+        {
+          poly hh = pLPCopyAndShiftLM(h, i);
+          for (j=0; j<=k; j++)
+          {
+            poly s = strat->S[j];
+            enterOnePairWithoutShifts(j, hh, s, ecart, isFromQ, strat, atR, pmLastVblock(s), i);
+          }
+          enterOnePairWithoutShifts(-1, hh, h, ecart, isFromQ, strat, atR, h_lastVblock, i);
+        }
+      }
+    }
+    else
+    {
+      new_pair=TRUE;
+      if (strat->rightGB)
+      {
         for (j=0; j<=k; j++)
         {
-          enterOnePairManyShifts(j,h,ecart,isFromQ,strat, atR);
-          // other side pairs
-          enterOnePairSelfShifts(h,strat->S[j],ecart,isFromQ,strat, atR);
-        }
-        /* HERE we put (h, s*h) pairs */
-       /* enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV); */
-       enterOnePairSelfShifts (h, h, ecart, isFromQ, strat, atR);
-      }
-    }
-    else
-    {
-      for (j=0; j<=k; j++)
-      {
-        if ((pGetComp(h)==pGetComp(strat->S[j]))
-        || (pGetComp(strat->S[j])==0))
-        {
-          new_pair=TRUE;
-          enterOnePairManyShifts(j,h,ecart,isFromQ,strat, atR);
-          // other side pairs
-          enterOnePairSelfShifts(h,strat->S[j],ecart,isFromQ,strat, atR);
-        //Print("j:%d, Ll:%d\n",j,strat->Ll);
-        }
-      }
-      /* HERE we put (h, s*h) pairs */
-      enterOnePairSelfShifts (h, h, ecart, isFromQ, strat, atR);
+          if ((pGetComp(h)==pGetComp(strat->S[j]))
+              || (pGetComp(strat->S[j])==0))
+          {
+            assume(isFromQ == 0); // this case is not handeled here and should also never happen
+            poly s = strat->S[j];
+            if (strat->fromQ != NULL && strat->fromQ[j])
+            {
+              // pairs (shifts(s[j]),h), (s[j],h)
+              enterOnePairWithShifts(j, s, h, ecart, isFromQ, strat, atR, h_lastVblock, pmLastVblock(s));
+            }
+            else
+            {
+              // pair (h, s[j])
+              enterOnePairWithoutShifts(j, h, s, ecart, isFromQ, strat, atR, pmLastVblock(s), 0);
+            }
+          }
+        }
+      }
+      else
+      {
+        // pairs (shifts(s[1..k]),h), (s[1..k],h)
+        for (j=0; j<=k; j++) {
+          if ((pGetComp(h)==pGetComp(strat->S[j]))
+              || (pGetComp(strat->S[j])==0))
+          {
+            poly s = strat->S[j];
+            enterOnePairWithShifts(j, s, h, ecart, isFromQ, strat, atR, h_lastVblock, pmLastVblock(s));
+          }
+        }
+        // pairs (shifts(h),s[1..k]), (shifts(h), h)
+        for (i=1; i<=maxShift; i++)
+        {
+          poly hh = pLPCopyAndShiftLM(h, i);
+          for (j=0; j<=k; j++)
+          {
+            if ((pGetComp(h)==pGetComp(strat->S[j]))
+                || (pGetComp(strat->S[j])==0))
+            {
+              poly s = strat->S[j];
+              enterOnePairWithoutShifts(j, hh, s, ecart, isFromQ, strat, atR, pmLastVblock(s), i);
+            }
+          }
+          enterOnePairWithoutShifts(-1, hh, h, ecart, isFromQ, strat, atR, h_lastVblock, i);
+        }
+      }
     }
 
@@ -12738 +12787 @@
     ||(pGetComp(h)<=strat->syzComp)))
   {
-    //Print("start clearS k=%d, pos=%d, sl=%d\n",k,pos,strat->sl);
     unsigned long h_sev = pGetShortExpVector(h);
     loop
     {
       if (j > k) break;
-      clearS(h,h_sev, &j,&k,strat);
+      // TODO this currently doesn't clear all possible elements because of commutative division
+      if (!(strat->rightGB && strat->fromQ != NULL && strat->fromQ[j]))
+        clearS(h,h_sev, &j,&k,strat);
       j++;
     }
-    //Print("end clearS sl=%d\n",strat->sl);
-  }
- // PrintS("end enterpairs\n");
+  }
 }
 #endif
@@ -12765 +12813 @@
   pAssume(p.p != NULL);
 
-  int toInsert = itoInsert(p.p, strat->tailRing);
-
-  for (int i = 1; i <= toInsert; i++)
+  int maxPossibleShift = p_mLPmaxPossibleShift(p.p, strat->tailRing);
+
+  for (int i = 1; i <= maxPossibleShift; i++)
   {
     LObject qq;

kernel/GBEngine/kutil.h

@@ -368 +368 @@
   #ifdef HAVE_SHIFTBBA
   int cv; // in shift bases: counting V criterion
+  /*BOOLEAN*/ char rightGB;
   #endif
   /*BOOLEAN*/ char interpt;
@@ -852 +853 @@
 void enterTShift(LObject p, kStrategy strat, int atT = -1);
 
-void initBuchMoraShift (ideal F,ideal Q,kStrategy strat);
-
-void enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR);
-
 void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS);
 
 void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
 
-void updateSShift(kStrategy strat);
-
 void initBbaShift(kStrategy strat);
 
@@ -868 +863 @@
 int redFirstShift (LObject* h,kStrategy strat); // ok
 
-ideal freegb(ideal I);
+ideal freegb(ideal F);
+ideal rightgb(ideal F, ideal Q);
 
 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);

kernel/GBEngine/shiftgb.cc

@@ -43 +43 @@
 }
 
-/* for poly in lmCR/tailTR presentation */
-int itoInsert(poly p, const ring r)
+int p_mLPmaxPossibleShift(poly p, const ring r)
 {
-  /* the below situation (commented out) might happen! */
-//   if (r == currRing)
-//   {
-//     "Current ring is not expected in toInsert";
-//     return(0);
-//   }
-  /* compute the number of insertions */
-  int i = p_mLastVblock(p, currRing);
-  if (pNext(p) != NULL)
-  {
-    i = si_max(i, p_LastVblock(pNext(p), r) );
-  }
-  //  i = uptodeg  - i +1;
+  int lastBlock = p_mLastVblock(p, r);
+  if (lastBlock == 0) return 0;
   int uptodeg = r->N/r->isLPring;
-  //  p_wrp(p,currRing,r); Print("----i:%d",i); PrintLn();
-  return uptodeg - i;
+  return uptodeg - lastBlock;
 }
 

kernel/GBEngine/shiftgb.h

@@ -15 +15 @@
 #define pLPCopyAndShiftLM(p, sh) p_LPCopyAndShiftLM(p, sh, currRing)
 
-int itoInsert(poly p, const ring r);
+int p_mLPmaxPossibleShift(poly p, const ring r);
+#define pmLPmaxPossibleShift(p) p_mLPmaxPossibleShift(p, currRing)
 
 #endif

libpolys/polys/shiftop.cc

@@ -823 +823 @@
         return NULL;
       }
-      int ** wvhdl=(int**)omAlloc0((r->N+2)*sizeof(int*));
-      rRingOrder_t* ord=(rRingOrder_t*)omAlloc0((r->N+2)*sizeof(rRingOrder_t));
-      int* blk0=(int*)omAlloc0((r->N+2)*sizeof(int));
-      int* blk1=(int*)omAlloc0((r->N+2)*sizeof(int));
+      int ** wvhdl=(int**)omAlloc0((r->N+3)*sizeof(int*));
+      rRingOrder_t* ord=(rRingOrder_t*)omAlloc0((r->N+3)*sizeof(rRingOrder_t));
+      int* blk0=(int*)omAlloc0((r->N+3)*sizeof(int));
+      int* blk1=(int*)omAlloc0((r->N+3)*sizeof(int));
       omFree(R->wvhdl);  R->wvhdl=wvhdl;
       omFree(R->order);  R->order=ord;
@@ -834 +834 @@
       {
         ord[i+p]=ringorder_a;
+        //Print("entry:%d->a\n",i+p);
         blk0[i+p]=1;
         blk1[i+p]=R->N;
@@ -847 +848 @@
       }
       ord[r->N+p]=r->order[p]; /* lp or rp */
+      //Print("entry:%d->lp\n",r->N+p);
       blk0[r->N+p]=1;
       blk1[r->N+p]=R->N;
@@ -857 +859 @@
         return NULL;
       }
+      //if (p==1) PrintS("entry:0 ->c/C\n");
+      //else if (p==0) Print("entry:%d ->c/C\n",r->N+1);
       break;
     }