Changeset e40da9f in git for kernel/GBEngine

Timestamp:

Aug 10, 2016, 12:36:45 PM (8 years ago)

Author:

Adi Popescu <adi_popescum@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

cc94f7e8ad1f5795a4149ec66525d5a5a3dfd6c2

Parents:

ef27298cfb747d136e3418af99edf58c03b12a05

Message:

trying to fix Christian sba algorithm

Location:

kernel/GBEngine

Files:

• kspoly.cc (modified) (3 diffs)
• kstd1.cc (modified) (3 diffs)
• kstd2.cc (modified) (31 diffs)
• kutil.cc (modified) (9 diffs)
• kutil.h (modified) (3 diffs)

kernel/GBEngine/kspoly.cc

@@ -175 +175 @@
  *
  ***************************************************************/
+ 
 int ksReducePolySig(LObject* PR,
                  TObject* PW,
@@ -182 +183 @@
                  kStrategy strat)
 {
-#ifdef ADIDEBUG
-printf("\nksReducePolySig\n");
-pWrite(PR->p);pWrite(PR->sig);
-pWrite(PW->p);pWrite(PW->sig);
-#endif
 #ifdef KDEBUG
   red_count++;
@@ -242 +238 @@
 #endif
     p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
+//#if 1
+#ifdef DEBUGF5
+    printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
+    pWrite(pHead(f1));
+    pWrite(pHead(f2));
+    pWrite(sigMult);
+    pWrite(PR->sig);
+    printf("--------------\n");
+#endif
+    int sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
+    // now we can delete the copied polynomial data used for checking for
+    // sig-safeness of the reduction step
+//#if 1
+#ifdef DEBUGF5
+    printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
+
+#endif
+    //pDelete(&f1);
+    pDelete(&sigMult);
+    // go on with the computations only if the signature of p2 is greater than the
+    // signature of fm*p1
+    if(sigSafe != 1)
+    {
+      PR->is_redundant = TRUE;
+      return 3;
+    }
+    //PW->is_sigsafe  = TRUE;
+  }
+  PR->is_redundant = FALSE;
+  poly p1 = PR->GetLmTailRing();   // p2 | p1
+  poly p2 = PW->GetLmTailRing();   // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
+  poly t2 = pNext(p2), lm = p1;    // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
+  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
+  p_CheckPolyRing(p1, tailRing);
+  p_CheckPolyRing(p2, tailRing);
+
+  pAssume1(p2 != NULL && p1 != NULL &&
+      p_DivisibleBy(p2,  p1, tailRing));
+
+  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
+      (p_GetComp(p2, tailRing) == 0 &&
+       p_MaxComp(pNext(p2),tailRing) == 0));
+
+#ifdef HAVE_PLURAL
+  if (rIsPluralRing(currRing))
+  {
+    // for the time being: we know currRing==strat->tailRing
+    // no exp-bound checking needed
+    // (only needed if exp-bound(tailring)<exp-b(currRing))
+    if (PR->bucket!=NULL)  nc_kBucketPolyRed(PR->bucket, p2,coef);
+    else
+    {
+      poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
+      assume(_p != NULL);
+      nc_PolyPolyRed(_p, p2, coef, currRing);
+      if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
+      PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
+    }
+    return 0;
+  }
+#endif
+
+  if (t2==NULL)           // Divisor is just one term, therefore it will
+  {                       // just cancel the leading term
+    PR->LmDeleteAndIter();
+    if (coef != NULL) *coef = n_Init(1, tailRing);
+    return 0;
+  }
+
+  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
+
+  if (tailRing != currRing)
+  {
+    // check that reduction does not violate exp bound
+    while (PW->max != NULL && !p_LmExpVectorAddIsOk(lm, PW->max, tailRing))
+    {
+      // undo changes of lm
+      p_ExpVectorAdd(lm, p2, tailRing);
+      if (strat == NULL) return 2;
+      if (! kStratChangeTailRing(strat, PR, PW)) return -1;
+      tailRing = strat->tailRing;
+      p1 = PR->GetLmTailRing();
+      p2 = PW->GetLmTailRing();
+      t2 = pNext(p2);
+      lm = p1;
+      p_ExpVectorSub(lm, p2, tailRing);
+      ret = 1;
+    }
+  }
+
+  // take care of coef buisness
+  if (! n_IsOne(pGetCoeff(p2), tailRing))
+  {
+    number bn = pGetCoeff(lm);
+    number an = pGetCoeff(p2);
+    int ct = ksCheckCoeff(&an, &bn, tailRing->cf);    // Calculate special LC
+    p_SetCoeff(lm, bn, tailRing);
+    if ((ct == 0) || (ct == 2))
+      PR->Tail_Mult_nn(an);
+    if (coef != NULL) *coef = an;
+    else n_Delete(&an, tailRing);
+  }
+  else
+  {
+    if (coef != NULL) *coef = n_Init(1, tailRing);
+  }
+
+
+  // and finally,
+  PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
+  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
+  PR->LmDeleteAndIter();
+
+  // the following is commented out: shrinking
+#ifdef HAVE_SHIFTBBA_NONEXISTENT
+  if ( (currRing->isLPring) && (!strat->homog) )
+  {
+    // assume? h->p in currRing
+    PR->GetP();
+    poly qq = p_Shrink(PR->p, currRing->isLPring, currRing);
+    PR->Clear(); // does the right things
+    PR->p = qq;
+    PR->t_p = NULL;
+    PR->SetShortExpVector();
+  }
+#endif
+
+#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
+  if (TEST_OPT_DEBUG)
+  {
+    Print(" to: "); PR->wrp(); Print("\n");
+  }
+#endif
+  return ret;
+}
+ 
+int ksReducePolySigRing(LObject* PR,
+                 TObject* PW,
+                 long /*idx*/,
+                 poly spNoether,
+                 number *coef,
+                 kStrategy strat)
+{
+#ifdef ADIDEBUG
+printf("\nksReducePolySig\n");
+pWrite(PR->p);pWrite(PR->sig);
+pWrite(PW->p);pWrite(PW->sig);
+#endif
+#ifdef KDEBUG
+  red_count++;
+#ifdef TEST_OPT_DEBUG_RED
+  if (TEST_OPT_DEBUG)
+  {
+    Print("Red %d:", red_count); PR->wrp(); Print(" with:");
+    PW->wrp();
+  }
+#endif
+#endif
+  int ret = 0;
+  ring tailRing = PR->tailRing;
+  kTest_L(PR);
+  kTest_T(PW);
+
+  // signature-based stuff:
+  // checking for sig-safeness first
+  // NOTE: This has to be done in the current ring
+  //
+  /**********************************************
+   *
+   * TODO:
+   * --------------------------------------------
+   * if strat->sbaOrder == 1
+   * Since we are subdividing lower index and
+   * current index reductions it is enough to
+   * look at the polynomial part of the signature
+   * for a check. This should speed-up checking
+   * a lot!
+   * if !strat->sbaOrder == 0
+   * We are not subdividing lower and current index
+   * due to the fact that we are using the induced
+   * Schreyer order
+   *
+   * nevertheless, this different behaviour is
+   * taken care of by is_sigsafe
+   * => one reduction procedure can be used for
+   * both, the incremental and the non-incremental
+   * attempt!
+   * --------------------------------------------
+   *
+   *********************************************/
+  //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
+  if (!PW->is_sigsafe)
+  {
+    poly sigMult = pCopy(PW->sig);   // copy signature of reducer
+//#if 1
+#ifdef DEBUGF5
+    printf("IN KSREDUCEPOLYSIG: \n");
+    pWrite(pHead(f1));
+    pWrite(pHead(f2));
+    pWrite(sigMult);
+    printf("--------------\n");
+#endif
+    p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
     //I have also to set the leading coeficient for sigMult (in the case of rings)
     if(rField_is_Ring(currRing))

kernel/GBEngine/kstd1.cc

@@ -1539 +1539 @@
   // for sig-safe reductions in signature-based
   // standard basis computations
-  strat->red          = redSig;
+  if(rField_is_Ring(currRing))
+    strat->red = redSigRing;
+  else
+    strat->red        = redSig;
   //strat->sbaOrder  = 1;
   strat->currIdx      = 1;
@@ -2520 +2523 @@
       else
       {
+        strat->sigdrop = FALSE;
         if (w!=NULL)
           r=sba(F,Q,*w,hilb,strat);
@@ -2544 +2548 @@
   {
     //--------------------------RING CASE-------------------------
+    assume(sbaOrder == 1);
+    assume(arri == 0);
     if(idIs0(F))
       return idInit(1,F->rank);

kernel/GBEngine/kstd2.cc

@@ -668 +668 @@
   pWrite(Red->GetLmCurrRing());
   */
-  ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
+  if(rField_is_Ring(currRing))
+    ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
+  else
+    ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
   if (!ret)
   {
@@ -691 +694 @@
 *  signatures
 */
+
 int redSig (LObject* h,kStrategy strat)
+{
+  if (strat->tl<0) return 1;
+  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
+  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
+  assume(h->FDeg == h->pFDeg());
+//#if 1
+#ifdef DEBUGF5
+  Print("------- IN REDSIG -------\n");
+  Print("p: ");
+  pWrite(pHead(h->p));
+  Print("p1: ");
+  pWrite(pHead(h->p1));
+  Print("p2: ");
+  pWrite(pHead(h->p2));
+  Print("---------------------------\n");
+#endif
+  poly h_p;
+  int i,j,at,pass, ii;
+  int start=0;
+  int sigSafe;
+  unsigned long not_sev;
+  // long reddeg,d;
+
+  pass = j = 0;
+  // d = reddeg = h->GetpFDeg();
+  h->SetShortExpVector();
+  int li;
+  h_p = h->GetLmTailRing();
+  not_sev = ~ h->sev;
+  loop
+  {
+    j = kFindDivisibleByInT(strat, h, start);
+    if (j < 0)
+    {
+      return 1;
+    }
+
+    li = strat->T[j].pLength;
+    ii = j;
+    /*
+     * the polynomial to reduce with (up to the moment) is;
+     * pi with length li
+     */
+    i = j;
+#if 1
+    if (TEST_OPT_LENGTH)
+    loop
+    {
+      /*- search the shortest possible with respect to length -*/
+      i++;
+      if (i > strat->tl)
+        break;
+      if (li<=1)
+        break;
+      if ((strat->T[i].pLength < li)
+         &&
+          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
+                               h_p, not_sev, strat->tailRing))
+      {
+        /*
+         * the polynomial to reduce with is now;
+         */
+        li = strat->T[i].pLength;
+        ii = i;
+      }
+    }
+    start = ii+1;
+#endif
+
+    /*
+     * end of search: have to reduce with pi
+     */
+#ifdef KDEBUG
+    if (TEST_OPT_DEBUG)
+    {
+      PrintS("red:");
+      h->wrp();
+      PrintS(" with ");
+      strat->T[ii].wrp();
+    }
+#endif
+    assume(strat->fromT == FALSE);
+//#if 1
+#ifdef DEBUGF5
+    Print("BEFORE REDUCTION WITH %d:\n",ii);
+    Print("--------------------------------\n");
+    pWrite(h->sig);
+    pWrite(strat->T[ii].sig);
+    pWrite(h->GetLmCurrRing());
+    pWrite(pHead(h->p1));
+    pWrite(pHead(h->p2));
+    pWrite(pHead(strat->T[ii].p));
+    Print("--------------------------------\n");
+    printf("INDEX OF REDUCER T: %d\n",ii);
+#endif
+    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
+#if SBA_PRINT_REDUCTION_STEPS
+    if (sigSafe != 3)
+      sba_reduction_steps++;
+#endif
+#if SBA_PRINT_OPERATIONS
+    if (sigSafe != 3)
+      sba_operations  +=  pLength(strat->T[ii].p);
+#endif
+    // if reduction has taken place, i.e. the reduction was sig-safe
+    // otherwise start is already at the next position and the loop
+    // searching reducers in T goes on from index start
+//#if 1
+#ifdef DEBUGF5
+    Print("SigSAFE: %d\n",sigSafe);
+#endif
+    if (sigSafe != 3)
+    {
+      // start the next search for reducers in T from the beginning
+      start = 0;
+#ifdef KDEBUG
+      if (TEST_OPT_DEBUG)
+      {
+        PrintS("\nto ");
+        h->wrp();
+        PrintLn();
+      }
+#endif
+
+      h_p = h->GetLmTailRing();
+      if (h_p == NULL)
+      {
+        if (h->lcm!=NULL) pLmFree(h->lcm);
+#ifdef KDEBUG
+        h->lcm=NULL;
+#endif
+        return 0;
+      }
+      h->SetShortExpVector();
+      not_sev = ~ h->sev;
+      /*
+      * try to reduce the s-polynomial h
+      *test first whether h should go to the lazyset L
+      *-if the degree jumps
+      *-if the number of pre-defined reductions jumps
+      */
+      pass++;
+      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
+      {
+        h->SetLmCurrRing();
+        at = strat->posInL(strat->L,strat->Ll,h,strat);
+        if (at <= strat->Ll)
+        {
+          int dummy=strat->sl;
+          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
+          {
+            return 1;
+          }
+          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
+#ifdef KDEBUG
+          if (TEST_OPT_DEBUG)
+            Print(" lazy: -> L%d\n",at);
+#endif
+          h->Clear();
+          return -1;
+        }
+      }
+    }
+  }
+}
+
+
+int redSigRing (LObject* h,kStrategy strat)
 {
   //Since reduce is really bad for SBA we use the following idea:
   // We first check if we can build a gcd pair between h and S
   //where the sig remains the same and replace h by this gcd poly
+  assume(rField_is_Ring(currRing));
   #if GCD_SBA
   #ifdef ADIDEBUG
   printf("\nBefore sbaCheckGcdPair ");pWrite(h->p);
   #endif
-  //sbaCheckGcdPair(h,strat);
   while(sbaCheckGcdPair(h,strat)) 
   {
@@ -713 +885 @@
   #endif
   poly beforeredsig;
-  if(rField_is_Ring(currRing)) 
-    beforeredsig = pCopy(h->sig);
+  beforeredsig = pCopy(h->sig);
     
   if (strat->tl<0) return 1;
@@ -758 +929 @@
       printf("\nBefore sbaCheckGcdPair ");pWrite(h->p);
       #endif
-      //sbaCheckGcdPair(h,strat);
       while(sbaCheckGcdPair(h,strat)) 
       {
@@ -788 +958 @@
           return 0;
         }
-        if(rField_is_Ring(currRing))
-        {
-          //Check for sigdrop after reduction
-          if(pLtCmp(beforeredsig,h->sig) == 1)
+        //Check for sigdrop after reduction
+        if(pLtCmp(beforeredsig,h->sig) == 1)
+        {
+          #ifdef ADIDEBUG
+          printf("\nSigDrop after reduce\n");pWrite(beforeredsig);pWrite(h->sig);
+          #endif
+          strat->sigdrop = TRUE;
+          //Reduce it as much as you can
+          int red_result = redRing(h,strat);
+          if(red_result == 0)
+          {
+            //It reduced to 0, cancel the sigdrop
+            #ifdef ADIDEBUG
+            printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
+            #endif
+            strat->sigdrop = FALSE;
+            p_Delete(&h->sig,currRing);h->sig = NULL;
+            return 0;
+          }
+          else
           {
             #ifdef ADIDEBUG
-            printf("\nSigDrop after reduce\n");pWrite(beforeredsig);pWrite(h->sig);
+            printf("\nReduced to this via redRing.SIGDROP\n");pWrite(h->p);
             #endif
-            strat->sigdrop = TRUE;
-            //Reduce it as much as you can
-            int red_result = redRing(h,strat);
-            if(red_result == 0)
-            {
-              //It reduced to 0, cancel the sigdrop
-              #ifdef ADIDEBUG
-              printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
-              #endif
-              strat->sigdrop = FALSE;
-              p_Delete(&h->sig,currRing);h->sig = NULL;
-              return 0;
-            }
-            else
-            {
-              #ifdef ADIDEBUG
-              printf("\nReduced to this via redRing.SIGDROP\n");pWrite(h->p);
-              #endif
-              //strat->enterS(*h, strat->sl+1, strat, strat->tl);
-              return 0;
-            }
+            //strat->enterS(*h, strat->sl+1, strat, strat->tl);
+            return 0;
           }
-          p_Delete(&beforeredsig,currRing);
-        }
+        }
+        p_Delete(&beforeredsig,currRing);
         return 1;
       }
@@ -832 +999 @@
     i = j;
     if (TEST_OPT_LENGTH)
-    if(rField_is_Ring(currRing))
-    {
-      loop
-      {
-        /*- search the shortest possible with respect to length -*/
-        i++;
-        if (i > strat->tl)
-          break;
-        if (li<=1)
-          break;
-        if ((strat->T[i].pLength < li)
-           && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
-           && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
-                                 h_p, not_sev, strat->tailRing))
-        {
-          /*
-           * the polynomial to reduce with is now;
-           */
-          li = strat->T[i].pLength;
-          ii = i;
-        }
-      }
-    }
-    else
-    {
-      loop
-      {
-        /*- search the shortest possible with respect to length -*/
-        i++;
-        if (i > strat->tl)
-          break;
-        if (li<=1)
-          break;
-        if ((strat->T[i].pLength < li)
-           && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
-                                 h_p, not_sev, strat->tailRing))
-        {
-          /*
-           * the polynomial to reduce with is now;
-           */
-          li = strat->T[i].pLength;
-          ii = i;
-        }
-      }
-    }
+    loop
+    {
+      /*- search the shortest possible with respect to length -*/
+      i++;
+      if (i > strat->tl)
+        break;
+      if (li<=1)
+        break;
+      if ((strat->T[i].pLength < li)
+         && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
+         && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
+                               h_p, not_sev, strat->tailRing))
+      {
+        /*
+         * the polynomial to reduce with is now;
+         */
+        li = strat->T[i].pLength;
+        ii = i;
+      }
+    }
+    
     start = ii+1;
 
@@ -908 +1051 @@
     printf("\nWe reduce it with:\n");p_Write(strat->T[ii].p,strat->tailRing);pWrite(strat->T[ii].sig);
     #endif
-    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
+    sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
     #ifdef ADIDEBUG
     printf("\nAfter small reduction:\n");pWrite(h->p);pWrite(h->sig);
     #endif
-    if(rField_is_Ring(currRing) && h->p == NULL && h->sig == NULL)
+    if(h->p == NULL && h->sig == NULL)
     {
       //Trivial case catch
@@ -1080 +1223 @@
       strat->redTailChange=TRUE;
       #ifdef ADIDEBUG
-      printf("\nWill TAILreduce * with *:\n");pWrite(Ln.p);pWrite(Ln.sig);
-      pWrite(With->p);pWrite(With->sig);pWrite(L->sig);
+      printf("\nWill TAILreduce * with *:\n");p_Write(Ln.p,strat->tailRing);pWrite(Ln.sig);
+      p_Write(With->p,strat->tailRing);pWrite(With->sig);pWrite(L->sig);
       #endif
       int ret = ksReducePolyTailSig(L, With, &Ln, strat);
@@ -2052 +2195 @@
   sba_interreduction_operations = 0;
 #endif
-  
+
   ideal F1 = F0;
   ring sRing, currRingOld;
@@ -2065 +2208 @@
     }
   }
-  ideal F;
   // sort ideal F
-  //Put the SigDrop element on the correct position (think of sbaEnterS)
-  //We also sort them
-  if(rField_is_Ring(currRing) && strat->sigdrop)
-  {
-    #if 1
-    F = idInit(IDELEMS(F1),F1->rank);
-    for (int i=0; i<IDELEMS(F1);++i)
-      F->m[i] = F1->m[i];
-    if(strat->sbaEnterS >= 0)
-    {
-      poly dummy;
-      dummy = pCopy(F->m[0]); //the sigdrop element
-      for(int i = 0;i<strat->sbaEnterS;i++)
-        F->m[i] = F->m[i+1];
-      F->m[strat->sbaEnterS] = dummy;
-    }
-    #else
-    F = idInit(1,F1->rank);
-    //printf("\nBefore the initial block sorting:\n");idPrint(F1);
-    F->m[0] = F1->m[0];
-    int pos;
-    if(strat->sbaEnterS >= 0)
-    {
-      for(int i=1;i<=strat->sbaEnterS;i++)
-      {
-        pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
-        idInsertPolyOnPos(F,F1->m[i],pos);
-      }
-      for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
-      {
-        pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
-        idInsertPolyOnPos(F,F1->m[i],pos);
-      }
-      poly dummy;
-      dummy = pCopy(F->m[0]); //the sigdrop element
-      for(int i = 0;i<strat->sbaEnterS;i++)
-        F->m[i] = F->m[i+1];
-      F->m[strat->sbaEnterS] = dummy;
-    }
-    else
-    {
-      for(int i=1;i<IDELEMS(F1);i++)
-      {
-        pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
-        idInsertPolyOnPos(F,F1->m[i],pos);
-      }
-    }
-    #endif
-    //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
-  }
-  else
-  {
-    F       = idInit(IDELEMS(F1),F1->rank);
-    intvec *sort  = idSort(F1);
-    for (int i=0; i<sort->length();++i)
-      F->m[i] = F1->m[(*sort)[i]-1];
-  // put the monomials after the sbaEnterS polynomials
-  //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
-  int nrmon = 0;
-  for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
-  {
-    //pWrite(F->m[i]);
-    if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
-    {
-      poly mon = F->m[i];
-      for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
-      {
-        F->m[j] = F->m[j-1];
-      }
-      F->m[j] = mon;
-      nrmon++;
-    }
-    //idPrint(F);
-  }
-  }
-    //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
-  #ifdef HAVE_RINGS
-  if(rField_is_Ring(currRing))
-    strat->sigdrop = FALSE;
-  strat->nrsyzcrit = 0;
-  strat->nrrewcrit = 0;
-  #endif
+  ideal F       = idInit(IDELEMS(F1),F1->rank);
+  intvec *sort  = idSort(F1);
+  for (int i=0; i<sort->length();++i)
+    F->m[i] = F1->m[(*sort)[i]-1];
 #if SBA_INTERRED_START
   F = kInterRed(F,NULL);
@@ -2158 +2222 @@
   printf("\n");
 #endif
+#ifdef KDEBUG
+  bba_count++;
+  int loop_count = 0;
+#endif /* KDEBUG */
   int   srmax,lrmax, red_result = 1;
   int   olddeg,reduc;
@@ -2164 +2232 @@
   BOOLEAN withT     = TRUE;
   strat->max_lower_index = 0;
+
   //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
   initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
   initSbaPos(strat);
+  //initBuchMoraPos(strat);
   initHilbCrit(F,Q,&hilb,strat);
   initSba(F,strat);
@@ -2174 +2244 @@
   srmax = strat->sl;
   reduc = olddeg = lrmax = 0;
+
 #ifndef NO_BUCKETS
   if (!TEST_OPT_NOT_BUCKETS)
@@ -2186 +2257 @@
   kTest_TS(strat);
 
+#ifdef KDEBUG
+#if MYTEST
+  if (TEST_OPT_DEBUG)
+  {
+    PrintS("bba start GB: currRing: ");
+    // rWrite(currRing);PrintLn();
+    rDebugPrint(currRing);
+    PrintLn();
+  }
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
 #ifdef HAVE_TAIL_RING
   if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
@@ -2196 +2279 @@
     kDebugPrint(strat);
   }
-  // We add the elements directly in S from the previous loop
-  if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
-  {
-    for(int i = 0;i<strat->sbaEnterS;i++)
-    {
-      //Update: now the element is at the corect place
-      //i+1 because on the 0 position is the sigdrop element
-      enterT(strat->L[strat->Ll-(i)],strat);
-      strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
-    }
-    strat->Ll = strat->Ll - strat->sbaEnterS; 
-    strat->sbaEnterS = -1;
-  }
-  kTest_TS(strat);
+
+
 #ifdef KDEBUG
   //kDebugPrint(strat);
@@ -2216 +2287 @@
   while (strat->Ll >= 0)
   {
-    #ifdef ADIDEBUG
-    printf("\n      ------------------------NEW LOOP\n");
-    printf("\nShdl = \n");
-    #if 0
-    idPrint(strat->Shdl);
-    #else
-    for(int ii = 0; ii<=strat->sl;ii++)
-    {
-      printf("\nS[%i]:  ",ii);p_Write(strat->S[ii],strat->tailRing);
-      printf("sig:   ");pWrite(strat->sig[ii]);
-    }
-    #endif
-    #if 0
-    for(int iii = 0; iii< strat->syzl; iii++)
-    {
-        printf("\nsyz[%i]:\n",iii);
-        p_Write(strat->syz[iii], currRing);
-    }
-    #endif
-    #if 0
-    for(int iii = 0; iii<= strat->tl; iii++)
-    {
-        printf("\nT[%i]:\n",iii);
-        p_Write(strat->T[iii].p, currRing);
-    }
-    #endif
-    printf("\n   list   L\n");
-    int iii;
-    #if 1
-    for(iii = 0; iii<= strat->Ll; iii++)
-    {
-        printf("\nL[%i]:\n",iii);
-        p_Write(strat->L[iii].p, currRing);
-        p_Write(strat->L[iii].p1, currRing);
-        p_Write(strat->L[iii].p2, currRing);
-        p_Write(strat->L[iii].sig, currRing);
-    }
-    #else
-    {
-        printf("L[%i]:",strat->Ll);
-        p_Write(strat->L[strat->Ll].p, strat->tailRing);
-        p_Write(strat->L[strat->Ll].p1, strat->tailRing);
-        p_Write(strat->L[strat->Ll].p2, strat->tailRing);
-        p_Write(strat->L[strat->Ll].sig, strat->tailRing);
-    }
-    #endif
-    //getchar();
-    #endif
     if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
     #ifdef KDEBUG
+      loop_count++;
       if (TEST_OPT_DEBUG) messageSets(strat);
     #endif
@@ -2274 +2298 @@
             || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
     {
-
        //stops computation if
        // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
@@ -2299 +2322 @@
       // initialize new syzygy rules for the next iteration step
       initSyzRules(strat);
+
     }
     /*********************************************************************
@@ -2307 +2331 @@
     strat->P = strat->L[strat->Ll];
     strat->Ll--;
-    
-    if(rField_is_Ring(currRing))
-      strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
-    
-    #ifdef ADIDEBUG
-    printf("\n-------------------------\nThis is the current element P\n");
-    pWrite(strat->P.p);
-    pWrite(strat->P.p1);
-    pWrite(strat->P.p2);
-    pWrite(strat->P.sig);
-    #endif
-    /* reduction of the element chosen from L */
-    // We do not delete via RewCrit strong pairs or extended spolys over rings 
-    // these should have .lcm = NULL
-    if (strat->P.lcm == NULL || !strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
+    /* reduction of the element choosen from L */
+
+    if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
       //#if 1
 #ifdef DEBUGF5
@@ -2336 +2348 @@
         // deletes the short spoly
         /*
+#ifdef HAVE_RINGS
         if (rField_is_Ring(currRing))
           pLmDelete(strat->P.p);
         else
+#endif
           pLmFree(strat->P.p);
 */
@@ -2370 +2384 @@
           strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
         // for input polys, prepare reduction
-        if(!rField_is_Ring(currRing))
-          strat->P.PrepareRed(strat->use_buckets);
+        strat->P.PrepareRed(strat->use_buckets);
       }
       if (strat->P.p == NULL && strat->P.t_p == NULL)
@@ -2409 +2422 @@
       red_result = 2;
     }
-    if(rField_is_Ring(currRing))
-    {
-      if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
-      {
-        strat->P.p = pNeg(strat->P.p);
-        strat->P.sig = pNeg(strat->P.sig);
-      }
-      strat->P.pLength = pLength(strat->P.p);
-      if(strat->P.sig != NULL)
-        strat->P.sevSig = pGetShortExpVector(strat->P.sig);
-      if(strat->P.p != NULL)
-        strat->P.sev = pGetShortExpVector(strat->P.p);
-    }
-    #ifdef ADIDEBUG
-    printf("\nAfter reduce (redresult=%i): \n",red_result);pWrite(strat->P.p);pWrite(strat->P.sig);
-    #endif
-    //sigdrop case
-    if(rField_is_Ring(currRing) && strat->sigdrop)
-    {
-      //First reduce it as much as one can
-      #ifdef ADIDEBUG
-      printf("\nSigdrop in the reduce. Trying redring\n");
-      #endif
-      red_result = redRing(&strat->P,strat);
-      if(red_result == 0)
-      {
-        #ifdef ADIDEBUG
-        printf("\nSigdrop cancelled since redRing reduced to 0\n");
-        #endif
-        strat->sigdrop = FALSE;
-        pDelete(&strat->P.sig);
-        strat->P.sig = NULL;
-      }
-      else
-      {
-        #ifdef ADIDEBUG
-        printf("\nStill Sigdrop - redRing reduced to:\n");pWrite(strat->P.p);
-        #endif
-        strat->enterS(strat->P, 0, strat, strat->tl);
-        if (TEST_OPT_PROT)
-          PrintS("-");
-        break;
-      }
-    }
-    if(strat->blockred > strat->blockredmax)
-    {
-      #ifdef ADIDEBUG
-      printf("\nToo many blocked reductions\n");
-      #endif
-      strat->sigdrop = TRUE;
-      break;
-    }
-    
     if (errorreported)  break;
 
@@ -2474 +2434 @@
     }
 #endif
-    if (TEST_OPT_PROT)
-    {
-      if(strat->P.p != NULL)
-        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
-                &olddeg,&reduc,strat, red_result);
-      else
-        message((strat->honey ? strat->P.ecart : 0),
-                &olddeg,&reduc,strat, red_result);
-    }
 
     if (strat->overflow)
@@ -2488 +2439 @@
         if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
     }
+
     // reduction to non-zero new poly
     if (red_result == 1)
@@ -2510 +2462 @@
       int pos = strat->sl+1;
 
+#ifdef KDEBUG
+#if MYTEST
+      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
       // reduce the tail and normalize poly
       // in the ring case we cannot expect LC(f) = 1,
       // therefore we call pContent instead of pNorm
-      #ifdef HAVE_RINGS
-      poly beforetailred;
-      if(rField_is_Ring(currRing))
-        beforetailred = pCopy(strat->P.sig);
-      #endif
 #if SBA_TAIL_RED
-      if(rField_is_Ring(currRing))
-      {  
-        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
-          strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
-      }
-      else
-      {
-        if (strat->sbaOrder != 2) {
-          if (TEST_OPT_INTSTRATEGY)
+      if (strat->sbaOrder != 2) {
+        if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
+        {
+          strat->P.pCleardenom();
+          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
           {
+            strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
             strat->P.pCleardenom();
-            if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
-            {
-              strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
-              strat->P.pCleardenom();
-            }
           }
-          else
-          {
-            strat->P.pNorm();
-            if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
-              strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
-          }
-        }
-      }
-      // It may happen that we have lost the sig in redtailsba
-      // It cannot reduce to 0 since here we are doing just tail reduction. 
-      // Best case scenerio: remains the leading term
-      if(rField_is_Ring(currRing) && strat->sigdrop)     
-      {
-        #ifdef ADIDEBUG
-        printf("\n Still sigdrop after redtailSba - it reduced to \n");pWrite(strat->P.p);
-        #endif
-        strat->enterS(strat->P, 0, strat, strat->tl);
-        break;
-      }
-#endif
-    if(rField_is_Ring(currRing))
-    {
-      if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
-      {
-        #ifdef ADIDEBUG
-        printf("\nSigDrop after TAILred\n");pWrite(beforetailred);pWrite(strat->P.sig);
-        #endif
-        strat->sigdrop = TRUE;
-        //Reduce it as much as you can
-        red_result = redRing(&strat->P,strat);
-        if(red_result == 0)
-        {
-          //It reduced to 0, cancel the sigdrop
-          #ifdef ADIDEBUG
-          printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
-          #endif
-          strat->sigdrop = FALSE;
-          p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
         }
         else
         {
-          #ifdef ADIDEBUG
-          printf("\nReduced to this via redRing.SIGDROP\n");pWrite(strat->P.p);
-          #endif
-          strat->enterS(strat->P, 0, strat, strat->tl);
-          break;
-        }
-      }
-      p_Delete(&beforetailred,currRing);
-      // strat->P.p = NULL may appear if we had  a sigdrop above and reduced to 0 via redRing
-      if(strat->P.p == NULL)
-        goto case_when_red_result_changed;
-    }
-    #ifdef ADIDEBUG
-    printf("\nNach redTailSba: \n");
-    pWrite(strat->P.p);pWrite(strat->P.sig);
-    #endif
+          strat->P.pNorm();
+          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+            strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
+        }
+      }
+#endif
+
     // remove sigsafe label since it is no longer valid for the next element to
     // be reduced
@@ -2614 +2512 @@
 #ifdef KDEBUG
       if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
+#if MYTEST
+//#if 1
+      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
+#endif /* MYTEST */
 #endif /* KDEBUG */
 
@@ -2646 +2548 @@
       pWrite(strat->P.sig);
       */
+#ifdef HAVE_RINGS
       if (rField_is_Ring(currRing))
-        superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
       else
+#endif
         enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
-      #ifdef ADIDEBUG
-        printf("\nThis element is added to S\n");
-        p_Write(strat->P.p, strat->tailRing);p_Write(strat->P.p1, strat->tailRing);p_Write(strat->P.p2, strat->tailRing);pWrite(strat->P.sig);
-        getchar();
-        #endif
       // posInS only depends on the leading term
-      
-      if(rField_is_Ring(currRing) && strat->sigdrop)
-        break;
-      strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
       strat->enterS(strat->P, pos, strat, strat->tl);
-      
       if(strat->sbaOrder != 1)
       {
@@ -2820 +2714 @@
     else
     {
+      // adds signature of the zero reduction to
+      // strat->syz. This is the leading term of
+      // syzygy and can be used in syzCriterion()
+      // the signature is added if and only if the
+      // pair was not detected by the rewritten criterion in strat->red = redSig
+      if (red_result!=2) {
+#if SBA_PRINT_ZERO_REDUCTIONS
+        zeroreductions++;
+#endif
+        int pos = posInSyz(strat, strat->P.sig);
+        enterSyz(strat->P, strat, pos);
+//#if 1
+#ifdef DEBUGF5
+        Print("ADDING STUFF TO SYZ :  ");
+        //pWrite(strat->P.p);
+        pWrite(strat->P.sig);
+#endif
+      }
+      if (strat->P.p1 == NULL && strat->minim > 0)
+      {
+        p_Delete(&strat->P.p2, currRing, strat->tailRing);
+      }
+    }
+
+#ifdef KDEBUG
+    memset(&(strat->P), 0, sizeof(strat->P));
+#endif /* KDEBUG */
+    kTest_TS(strat);
+  }
+#ifdef KDEBUG
+#if MYTEST
+  PrintS("bba finish GB: currRing: "); rWrite(currRing);
+#endif /* MYTEST */
+  if (TEST_OPT_DEBUG) messageSets(strat);
+#endif /* KDEBUG */
+
+  if (TEST_OPT_SB_1)
+  {
+    #ifdef HAVE_RINGS
+    if(!rField_is_Ring(currRing))
+    #endif
+    {
+        int k=1;
+        int j;
+        while(k<=strat->sl)
+        {
+          j=0;
+          loop
+          {
+            if (j>=k) break;
+            clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
+            j++;
+          }
+          k++;
+        }
+    }
+  }
+
+  /* complete reduction of the standard basis--------- */
+  if (TEST_OPT_REDSB)
+  {
+    completeReduce(strat);
+#ifdef HAVE_TAIL_RING
+    if (strat->completeReduce_retry)
+    {
+      // completeReduce needed larger exponents, retry
+      // to reduce with S (instead of T)
+      // and in currRing (instead of strat->tailRing)
+      cleanT(strat);strat->tailRing=currRing;
+      int i;
+      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
+      completeReduce(strat);
+    }
+#endif
+  }
+  else if (TEST_OPT_PROT) PrintLn();
+
+#if SBA_PRINT_SIZE_SYZ
+  // that is correct, syzl is counting one too far
+  size_syz = strat->syzl;
+#endif
+  exitSba(strat);
+//  if (TEST_OPT_WEIGHTM)
+//  {
+//    pRestoreDegProcs(pFDegOld, pLDegOld);
+//    if (ecartWeights)
+//    {
+//      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
+//      ecartWeights=NULL;
+//    }
+//  }
+  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
+  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
+
+#ifdef KDEBUG
+#if MYTEST
+  PrintS("bba_end: currRing: "); rWrite(currRing);
+#endif /* MYTEST */
+#endif /* KDEBUG */
+#if SBA_PRINT_SIZE_G
+  size_g_non_red  = IDELEMS(strat->Shdl);
+#endif
+  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
+  {
+    rChangeCurrRing (currRingOld);
+    F0          = idrMoveR (F1, sRing, currRing);
+    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
+    rDelete (sRing);
+  }
+  id_DelDiv(strat->Shdl, currRing);
+  idSkipZeroes(strat->Shdl);
+  idTest(strat->Shdl);
+
+#if SBA_PRINT_SIZE_G
+  size_g   = IDELEMS(strat->Shdl);
+#endif
+#ifdef DEBUGF5
+  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
+  int oo = 0;
+  while (oo<IDELEMS(strat->Shdl))
+  {
+    printf(" %d.   ",oo+1);
+    pWrite(pHead(strat->Shdl->m[oo]));
+    oo++;
+  }
+#endif
+#if SBA_PRINT_ZERO_REDUCTIONS
+  printf("----------------------------------------------------------\n");
+  printf("ZERO REDUCTIONS:            %ld\n",zeroreductions);
+  zeroreductions  = 0;
+#endif
+#if SBA_PRINT_REDUCTION_STEPS
+  printf("----------------------------------------------------------\n");
+  printf("S-REDUCTIONS:               %ld\n",sba_reduction_steps);
+#endif
+#if SBA_PRINT_OPERATIONS
+  printf("OPERATIONS:                 %ld\n",sba_operations);
+#endif
+#if SBA_PRINT_REDUCTION_STEPS
+  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
+  printf("INTERREDUCTIONS:            %ld\n",sba_interreduction_steps);
+#endif
+#if SBA_PRINT_OPERATIONS
+  printf("INTERREDUCTION OPERATIONS:  %ld\n",sba_interreduction_operations);
+#endif
+#if SBA_PRINT_REDUCTION_STEPS
+  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
+  printf("ALL REDUCTIONS:             %ld\n",sba_reduction_steps+sba_interreduction_steps);
+  sba_interreduction_steps  = 0;
+  sba_reduction_steps       = 0;
+#endif
+#if SBA_PRINT_OPERATIONS
+  printf("ALL OPERATIONS:             %ld\n",sba_operations+sba_interreduction_operations);
+  sba_interreduction_operations = 0;
+  sba_operations                = 0;
+#endif
+#if SBA_PRINT_SIZE_G
+  printf("----------------------------------------------------------\n");
+  printf("SIZE OF G:                  %d / %d\n",size_g,size_g_non_red);
+  size_g          = 0;
+  size_g_non_red  = 0;
+#endif
+#if SBA_PRINT_SIZE_SYZ
+  printf("SIZE OF SYZ:                %ld\n",size_syz);
+  printf("----------------------------------------------------------\n");
+  size_syz  = 0;
+#endif
+#if SBA_PRINT_PRODUCT_CRITERION
+  printf("PRODUCT CRITERIA:           %ld\n",product_criterion);
+  product_criterion = 0;
+#endif
+  return (strat->Shdl);
+}
+
+ideal sbaZ (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
+{
+  // ring order stuff:
+  // in sba we have (until now) two possibilities:
+  // 1. an incremental computation w.r.t. (C,monomial order)
+  // 2. a (possibly non-incremental) computation w.r.t. the
+  //    induced Schreyer order.
+  // The corresponding orders are computed in sbaRing(), depending
+  // on the flag strat->sbaOrder
+#if SBA_PRINT_ZERO_REDUCTIONS
+  long zeroreductions           = 0;
+#endif
+#if SBA_PRINT_PRODUCT_CRITERION
+  long product_criterion        = 0;
+#endif
+#if SBA_PRINT_SIZE_G
+  int size_g                    = 0;
+  int size_g_non_red            = 0;
+#endif
+#if SBA_PRINT_SIZE_SYZ
+  long size_syz                 = 0;
+#endif
+  // global variable
+#if SBA_PRINT_REDUCTION_STEPS
+  sba_reduction_steps           = 0;
+  sba_interreduction_steps      = 0;
+#endif
+#if SBA_PRINT_OPERATIONS
+  sba_operations                = 0;
+  sba_interreduction_operations = 0;
+#endif
+  
+  ideal F1 = F0;
+  ring sRing, currRingOld;
+  currRingOld  = currRing;
+  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
+  {
+    sRing = sbaRing(strat);
+    if (sRing!=currRingOld)
+    {
+      rChangeCurrRing (sRing);
+      F1 = idrMoveR (F0, currRingOld, currRing);
+    }
+  }
+  ideal F;
+  // sort ideal F
+  //Put the SigDrop element on the correct position (think of sbaEnterS)
+  //We also sort them
+  if(rField_is_Ring(currRing) && strat->sigdrop)
+  {
+    #if 1
+    F = idInit(IDELEMS(F1),F1->rank);
+    for (int i=0; i<IDELEMS(F1);++i)
+      F->m[i] = F1->m[i];
+    if(strat->sbaEnterS >= 0)
+    {
+      poly dummy;
+      dummy = pCopy(F->m[0]); //the sigdrop element
+      for(int i = 0;i<strat->sbaEnterS;i++)
+        F->m[i] = F->m[i+1];
+      F->m[strat->sbaEnterS] = dummy;
+    }
+    #else
+    F = idInit(1,F1->rank);
+    //printf("\nBefore the initial block sorting:\n");idPrint(F1);
+    F->m[0] = F1->m[0];
+    int pos;
+    if(strat->sbaEnterS >= 0)
+    {
+      for(int i=1;i<=strat->sbaEnterS;i++)
+      {
+        pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
+        idInsertPolyOnPos(F,F1->m[i],pos);
+      }
+      for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
+      {
+        pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
+        idInsertPolyOnPos(F,F1->m[i],pos);
+      }
+      poly dummy;
+      dummy = pCopy(F->m[0]); //the sigdrop element
+      for(int i = 0;i<strat->sbaEnterS;i++)
+        F->m[i] = F->m[i+1];
+      F->m[strat->sbaEnterS] = dummy;
+    }
+    else
+    {
+      for(int i=1;i<IDELEMS(F1);i++)
+      {
+        pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
+        idInsertPolyOnPos(F,F1->m[i],pos);
+      }
+    }
+    #endif
+    //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
+  }
+  else
+  {
+    F       = idInit(IDELEMS(F1),F1->rank);
+    intvec *sort  = idSort(F1);
+    for (int i=0; i<sort->length();++i)
+      F->m[i] = F1->m[(*sort)[i]-1];
+    if(rField_is_Ring(currRing))
+    {
+      // put the monomials after the sbaEnterS polynomials
+      //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
+      int nrmon = 0;
+      for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
+      {
+        //pWrite(F->m[i]);
+        if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
+        {
+          poly mon = F->m[i];
+          for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
+          {
+            F->m[j] = F->m[j-1];
+          }
+          F->m[j] = mon;
+          nrmon++;
+        }
+        //idPrint(F);
+      }
+    }
+  }
+    //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
+  if(rField_is_Ring(currRing))
+    strat->sigdrop = FALSE;
+  strat->nrsyzcrit = 0;
+  strat->nrrewcrit = 0;
+#if SBA_INTERRED_START
+  F = kInterRed(F,NULL);
+#endif
+#if F5DEBUG
+  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
+  rWrite (currRing);
+  printf("ordSgn = %d\n",currRing->OrdSgn);
+  printf("\n");
+#endif
+  int   srmax,lrmax, red_result = 1;
+  int   olddeg,reduc;
+  int hilbeledeg=1,hilbcount=0,minimcnt=0;
+  LObject L;
+  BOOLEAN withT     = TRUE;
+  strat->max_lower_index = 0;
+  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
+  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
+  initSbaPos(strat);
+  initHilbCrit(F,Q,&hilb,strat);
+  initSba(F,strat);
+  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
+  /*Shdl=*/initSbaBuchMora(F, Q,strat);
+  idTest(strat->Shdl);
+  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
+  srmax = strat->sl;
+  reduc = olddeg = lrmax = 0;
+#ifndef NO_BUCKETS
+  if (!TEST_OPT_NOT_BUCKETS)
+    strat->use_buckets = 1;
+#endif
+
+  // redtailBBa against T for inhomogenous input
+  // if (!TEST_OPT_OLDSTD)
+  //   withT = ! strat->homog;
+
+  // strat->posInT = posInT_pLength;
+  kTest_TS(strat);
+
+#ifdef HAVE_TAIL_RING
+  if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
+    kStratInitChangeTailRing(strat);
+#endif
+  if (BVERBOSE(23))
+  {
+    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
+    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
+    kDebugPrint(strat);
+  }
+  // We add the elements directly in S from the previous loop
+  if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
+  {
+    for(int i = 0;i<strat->sbaEnterS;i++)
+    {
+      //Update: now the element is at the corect place
+      //i+1 because on the 0 position is the sigdrop element
+      enterT(strat->L[strat->Ll-(i)],strat);
+      strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
+    }
+    strat->Ll = strat->Ll - strat->sbaEnterS; 
+    strat->sbaEnterS = -1;
+  }
+  kTest_TS(strat);
+#ifdef KDEBUG
+  //kDebugPrint(strat);
+#endif
+  /* compute------------------------------------------------------- */
+  while (strat->Ll >= 0)
+  {
+    #ifdef ADIDEBUG
+    printf("\n      ------------------------NEW LOOP\n");
+    printf("\nShdl = \n");
+    #if 0
+    idPrint(strat->Shdl);
+    #else
+    for(int ii = 0; ii<=strat->sl;ii++)
+    {
+      printf("\nS[%i]:  ",ii);p_Write(strat->S[ii],strat->tailRing);
+      printf("sig:   ");pWrite(strat->sig[ii]);
+    }
+    #endif
+    #if 0
+    for(int iii = 0; iii< strat->syzl; iii++)
+    {
+        printf("\nsyz[%i]:\n",iii);
+        p_Write(strat->syz[iii], currRing);
+    }
+    #endif
+    #if 0
+    for(int iii = 0; iii<= strat->tl; iii++)
+    {
+        printf("\nT[%i]:\n",iii);
+        p_Write(strat->T[iii].p, currRing);
+    }
+    #endif
+    printf("\n   list   L\n");
+    int iii;
+    #if 0
+    for(iii = 0; iii<= strat->Ll; iii++)
+    {
+        printf("\nL[%i]:\n",iii);
+        p_Write(strat->L[iii].p, currRing);
+        p_Write(strat->L[iii].p1, currRing);
+        p_Write(strat->L[iii].p2, currRing);
+        p_Write(strat->L[iii].sig, currRing);
+    }
+    #else
+    {
+        printf("L[%i]:",strat->Ll);
+        p_Write(strat->L[strat->Ll].p, strat->tailRing);
+        p_Write(strat->L[strat->Ll].p1, strat->tailRing);
+        p_Write(strat->L[strat->Ll].p2, strat->tailRing);
+        p_Write(strat->L[strat->Ll].sig, currRing);
+    }
+    #endif
+    //getchar();
+    #endif
+    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
+    #ifdef KDEBUG
+      if (TEST_OPT_DEBUG) messageSets(strat);
+    #endif
+    if (strat->Ll== 0) strat->interpt=TRUE;
+    /*
+    if (TEST_OPT_DEGBOUND
+        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
+            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
+    {
+
+       //stops computation if
+       // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
+       //a predefined number Kstd1_deg
+      while ((strat->Ll >= 0)
+        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
+        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
+            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
+        )
+        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
+      if (strat->Ll<0) break;
+      else strat->noClearS=TRUE;
+    }
+    */
+    if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
+    {
+      strat->currIdx  = pGetComp(strat->L[strat->Ll].sig);
+#if F5C
+      // 1. interreduction of the current standard basis
+      // 2. generation of new principal syzygy rules for syzCriterion
+      f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
+          lrmax, reduc, Q, w, hilb );
+#endif
+      // initialize new syzygy rules for the next iteration step
+      initSyzRules(strat);
+    }
+    /*********************************************************************
+      * interrreduction step is done, we can go on with the next iteration
+      * step of the signature-based algorithm
+      ********************************************************************/
+    /* picks the last element from the lazyset L */
+    strat->P = strat->L[strat->Ll];
+    strat->Ll--;
+    
+    if(rField_is_Ring(currRing))
+      strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
+    
+    #ifdef ADIDEBUG
+    printf("\n-------------------------\nThis is the current element P\n");
+    p_Write(strat->P.p,strat->tailRing);
+    p_Write(strat->P.p1,strat->tailRing);
+    p_Write(strat->P.p2,strat->tailRing);
+    p_Write(strat->P.sig,currRing);
+    #endif
+    /* reduction of the element chosen from L */
+    // We do not delete via RewCrit strong pairs or extended spolys over rings 
+    // these should have .lcm = NULL
+    if (strat->P.lcm == NULL || !strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
+      //#if 1
+#ifdef DEBUGF5
+      Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
+      Print("-------------------------------------------------\n");
+      pWrite(strat->P.sig);
+      pWrite(pHead(strat->P.p));
+      pWrite(pHead(strat->P.p1));
+      pWrite(pHead(strat->P.p2));
+      Print("-------------------------------------------------\n");
+#endif
+      if (pNext(strat->P.p) == strat->tail)
+      {
+        // deletes the short spoly
+        /*
+        if (rField_is_Ring(currRing))
+          pLmDelete(strat->P.p);
+        else
+          pLmFree(strat->P.p);
+*/
+          // TODO: needs some masking
+          // TODO: masking needs to vanish once the signature
+          //       sutff is completely implemented
+          strat->P.p = NULL;
+        poly m1 = NULL, m2 = NULL;
+
+        // check that spoly creation is ok
+        while (strat->tailRing != currRing &&
+            !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
+        {
+          assume(m1 == NULL && m2 == NULL);
+          // if not, change to a ring where exponents are at least
+          // large enough
+          if (!kStratChangeTailRing(strat))
+          {
+            WerrorS("OVERFLOW...");
+            break;
+          }
+        }
+        // create the real one
+        ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
+            strat->tailRing, m1, m2, strat->R);
+
+      }
+      else if (strat->P.p1 == NULL)
+      {
+        if (strat->minim > 0)
+          strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
+        // for input polys, prepare reduction
+        if(!rField_is_Ring(currRing))
+          strat->P.PrepareRed(strat->use_buckets);
+      }
+      if (strat->P.p == NULL && strat->P.t_p == NULL)
+      {
+        red_result = 0;
+      }
+      else
+      {
+        //#if 1
+#ifdef DEBUGF5
+        Print("Poly before red: ");
+        pWrite(pHead(strat->P.p));
+        pWrite(strat->P.sig);
+#endif
+#if SBA_PRODUCT_CRITERION
+        if (strat->P.prod_crit) {
+#if SBA_PRINT_PRODUCT_CRITERION
+          product_criterion++;
+#endif
+          int pos = posInSyz(strat, strat->P.sig);
+          enterSyz(strat->P, strat, pos);
+          if (strat->P.lcm!=NULL)
+            pLmFree(strat->P.lcm);
+          red_result = 2;
+        } else {
+          red_result = strat->red(&strat->P,strat);
+        }
+#else
+        red_result = strat->red(&strat->P,strat);
+#endif
+      }
+    } else {
+      /*
+      if (strat->P.lcm != NULL)
+        pLmFree(strat->P.lcm);
+        */
+      red_result = 2;
+    }
+    if(rField_is_Ring(currRing))
+    {
+      if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
+      {
+        strat->P.p = pNeg(strat->P.p);
+        strat->P.sig = pNeg(strat->P.sig);
+      }
+      strat->P.pLength = pLength(strat->P.p);
+      if(strat->P.sig != NULL)
+        strat->P.sevSig = pGetShortExpVector(strat->P.sig);
+      if(strat->P.p != NULL)
+        strat->P.sev = pGetShortExpVector(strat->P.p);
+    }
+    #ifdef ADIDEBUG
+    printf("\nAfter reduce (redresult=%i): \n",red_result);pWrite(strat->P.p);pWrite(strat->P.sig);
+    #endif
+    //sigdrop case
+    if(rField_is_Ring(currRing) && strat->sigdrop)
+    {
+      //First reduce it as much as one can
+      #ifdef ADIDEBUG
+      printf("\nSigdrop in the reduce. Trying redring\n");
+      #endif
+      red_result = redRing(&strat->P,strat);
+      if(red_result == 0)
+      {
+        #ifdef ADIDEBUG
+        printf("\nSigdrop cancelled since redRing reduced to 0\n");
+        #endif
+        strat->sigdrop = FALSE;
+        pDelete(&strat->P.sig);
+        strat->P.sig = NULL;
+      }
+      else
+      {
+        #ifdef ADIDEBUG
+        printf("\nStill Sigdrop - redRing reduced to:\n");pWrite(strat->P.p);
+        #endif
+        strat->enterS(strat->P, 0, strat, strat->tl);
+        if (TEST_OPT_PROT)
+          PrintS("-");
+        break;
+      }
+    }
+    if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
+    {
+      #ifdef ADIDEBUG
+      printf("\nToo many blocked reductions\n");
+      #endif
+      strat->sigdrop = TRUE;
+      break;
+    }
+    
+    if (errorreported)  break;
+
+//#if 1
+#ifdef DEBUGF5
+    if (red_result != 0) {
+        Print("Poly after red: ");
+        pWrite(pHead(strat->P.p));
+        pWrite(strat->P.GetLmCurrRing());
+        pWrite(strat->P.sig);
+        printf("%d\n",red_result);
+    }
+#endif
+    if (TEST_OPT_PROT)
+    {
+      if(strat->P.p != NULL)
+        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
+                &olddeg,&reduc,strat, red_result);
+      else
+        message((strat->honey ? strat->P.ecart : 0),
+                &olddeg,&reduc,strat, red_result);
+    }
+
+    if (strat->overflow)
+    {
+        if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
+    }
+    // reduction to non-zero new poly
+    if (red_result == 1)
+    {
+      // get the polynomial (canonicalize bucket, make sure P.p is set)
+      strat->P.GetP(strat->lmBin);
+
+      // sig-safe computations may lead to wrong FDeg computation, thus we need
+      // to recompute it to make sure everything is alright
+      (strat->P).FDeg = (strat->P).pFDeg();
+      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
+      // but now, for entering S, T, we reset it
+      // in the inhomogeneous case: FDeg == pFDeg
+      if (strat->homog) strat->initEcart(&(strat->P));
+
+      /* statistic */
+      if (TEST_OPT_PROT) PrintS("s");
+
+      //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
+      // in F5E we know that the last reduced element is already the
+      // the one with highest signature
+      int pos = strat->sl+1;
+
+      // reduce the tail and normalize poly
+      // in the ring case we cannot expect LC(f) = 1,
+      // therefore we call pContent instead of pNorm
+      #ifdef HAVE_RINGS
+      poly beforetailred;
+      if(rField_is_Ring(currRing))
+        beforetailred = pCopy(strat->P.sig);
+      #endif
+#if SBA_TAIL_RED
+      if(rField_is_Ring(currRing))
+      {  
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+          strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
+      }
+      else
+      {
+        if (strat->sbaOrder != 2) {
+          if (TEST_OPT_INTSTRATEGY)
+          {
+            strat->P.pCleardenom();
+            if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+            {
+              strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
+              strat->P.pCleardenom();
+            }
+          }
+          else
+          {
+            strat->P.pNorm();
+            if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+              strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
+          }
+        }
+      }
+      // It may happen that we have lost the sig in redtailsba
+      // It cannot reduce to 0 since here we are doing just tail reduction. 
+      // Best case scenerio: remains the leading term
+      if(rField_is_Ring(currRing) && strat->sigdrop)     
+      {
+        #ifdef ADIDEBUG
+        printf("\n Still sigdrop after redtailSba - it reduced to \n");pWrite(strat->P.p);
+        #endif
+        strat->enterS(strat->P, 0, strat, strat->tl);
+        break;
+      }
+#endif
+    if(rField_is_Ring(currRing))
+    {
+      if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
+      {
+        #ifdef ADIDEBUG
+        printf("\nSigDrop after TAILred\n");pWrite(beforetailred);pWrite(strat->P.sig);
+        #endif
+        strat->sigdrop = TRUE;
+        //Reduce it as much as you can
+        red_result = redRing(&strat->P,strat);
+        if(red_result == 0)
+        {
+          //It reduced to 0, cancel the sigdrop
+          #ifdef ADIDEBUG
+          printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
+          #endif
+          strat->sigdrop = FALSE;
+          p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
+        }
+        else
+        {
+          #ifdef ADIDEBUG
+          printf("\nReduced to this via redRing.SIGDROP\n");pWrite(strat->P.p);
+          #endif
+          strat->enterS(strat->P, 0, strat, strat->tl);
+          break;
+        }
+      }
+      p_Delete(&beforetailred,currRing);
+      // strat->P.p = NULL may appear if we had  a sigdrop above and reduced to 0 via redRing
+      if(strat->P.p == NULL)
+        goto case_when_red_result_changed;
+    }
+    #ifdef ADIDEBUG
+    printf("\nNach redTailSba: \n");
+    p_Write(strat->P.p,strat->tailRing);p_Write(strat->P.sig,currRing);
+    #endif
+    // remove sigsafe label since it is no longer valid for the next element to
+    // be reduced
+    if (strat->sbaOrder == 1)
+    {
+      for (int jj = 0; jj<strat->tl+1; jj++)
+      {
+        if (pGetComp(strat->T[jj].sig) == strat->currIdx)
+        {
+          strat->T[jj].is_sigsafe = FALSE;
+        }
+      }
+    }
+    else
+    {
+      for (int jj = 0; jj<strat->tl+1; jj++)
+      {
+        strat->T[jj].is_sigsafe = FALSE;
+      }
+    }
+#ifdef KDEBUG
+      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
+#endif /* KDEBUG */
+
+      // min_std stuff
+      if ((strat->P.p1==NULL) && (strat->minim>0))
+      {
+        if (strat->minim==1)
+        {
+          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
+          p_Delete(&strat->P.p2, currRing, strat->tailRing);
+        }
+        else
+        {
+          strat->M->m[minimcnt]=strat->P.p2;
+          strat->P.p2=NULL;
+        }
+        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
+          pNext(strat->M->m[minimcnt])
+            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
+                                           strat->tailRing, currRing,
+                                           currRing->PolyBin);
+        minimcnt++;
+      }
+
+      // enter into S, L, and T
+      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
+      enterT(strat->P, strat);
+      strat->T[strat->tl].is_sigsafe = FALSE;
+      /*
+      printf("hier\n");
+      pWrite(strat->P.GetLmCurrRing());
+      pWrite(strat->P.sig);
+      */
+      if (rField_is_Ring(currRing))
+        superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+      else
+        enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+      #ifdef ADIDEBUG
+        printf("\nThis element is added to S\n");
+        p_Write(strat->P.p, strat->tailRing);p_Write(strat->P.p1, strat->tailRing);p_Write(strat->P.p2, strat->tailRing);pWrite(strat->P.sig);
+        //getchar();
+        #endif
+      if(rField_is_Ring(currRing) && strat->sigdrop)
+        break;
+      if(rField_is_Ring(currRing))
+        strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
+      strat->enterS(strat->P, pos, strat, strat->tl);
+      if(strat->sbaOrder != 1)
+      {
+        BOOLEAN overwrite = FALSE;
+        for (int tk=0; tk<strat->sl+1; tk++)
+        {
+          if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
+          {
+            //printf("TK %d / %d\n",tk,strat->sl);
+            overwrite = FALSE;
+            break;
+          }
+        }
+        //printf("OVERWRITE %d\n",overwrite);
+        if (overwrite)
+        {
+          int cmp = pGetComp(strat->P.sig);
+          int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
+          pGetExpV (strat->P.p,vv);
+          pSetExpV (strat->P.sig, vv);
+          pSetComp (strat->P.sig,cmp);
+
+          strat->P.sevSig = pGetShortExpVector (strat->P.sig);
+          int i;
+          LObject Q;
+          for(int ps=0;ps<strat->sl+1;ps++)
+          {
+
+            strat->newt = TRUE;
+            if (strat->syzl == strat->syzmax)
+            {
+              pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
+              strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
+                  (strat->syzmax)*sizeof(unsigned long),
+                  ((strat->syzmax)+setmaxTinc)
+                  *sizeof(unsigned long));
+              strat->syzmax += setmaxTinc;
+            }
+            Q.sig = pCopy(strat->P.sig);
+            // add LM(F->m[i]) to the signature to get a Schreyer order
+            // without changing the underlying polynomial ring at all
+            if (strat->sbaOrder == 0)
+              p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
+            // since p_Add_q() destroys all input
+            // data we need to recreate help
+            // each time
+            // ----------------------------------------------------------
+            // in the Schreyer order we always know that the multiplied
+            // module monomial strat->P.sig gives the leading monomial of
+            // the corresponding principal syzygy
+            // => we do not need to compute the "real" syzygy completely
+            poly help = p_Copy(strat->sig[ps],currRing);
+            p_ExpVectorAdd (help,strat->P.p,currRing);
+            Q.sig = p_Add_q(Q.sig,help,currRing);
+            //printf("%d. SYZ  ",i+1);
+            //pWrite(strat->syz[i]);
+            Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
+            i = posInSyz(strat, Q.sig);
+            enterSyz(Q, strat, i);
+          }
+        }
+      }
+      // deg - idx - lp/rp
+      // => we need to add syzygies with indices > pGetComp(strat->P.sig)
+      if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
+      {
+        int cmp     = pGetComp(strat->P.sig);
+        int max_cmp = IDELEMS(F);
+        int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
+        pGetExpV (strat->P.p,vv);
+        LObject Q;
+        int pos;
+        int idx = p_GetComp(strat->P.sig,currRing);
+        //printf("++ -- adding syzygies -- ++\n");
+        // if new element is the first one in this index
+        if (strat->currIdx < idx) {
+          for (int i=0; i<strat->sl; ++i) {
+            Q.sig = p_Copy(strat->P.sig,currRing);
+            p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
+            poly help = p_Copy(strat->sig[i],currRing);
+            p_ExpVectorAdd(help,strat->P.p,currRing);
+            Q.sig = p_Add_q(Q.sig,help,currRing);
+            //pWrite(Q.sig);
+            pos = posInSyz(strat, Q.sig);
+            enterSyz(Q, strat, pos);
+          }
+          strat->currIdx = idx;
+        } else {
+          // if the element is not the first one in the given index we build all
+          // possible syzygies with elements of higher index
+          for (int i=cmp+1; i<=max_cmp; ++i) {
+            pos = -1;
+            for (int j=0; j<strat->sl; ++j) {
+              if (p_GetComp(strat->sig[j],currRing) == i) {
+                pos = j;
+                break;
+              }
+            }
+            if (pos != -1) {
+              Q.sig = p_One(currRing);
+              p_SetExpV(Q.sig, vv, currRing);
+              // F->m[i-1] corresponds to index i
+              p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
+              p_SetComp(Q.sig, i, currRing);
+              poly help = p_Copy(strat->P.sig,currRing);
+              p_ExpVectorAdd(help,strat->S[pos],currRing);
+              Q.sig = p_Add_q(Q.sig,help,currRing);
+              if (strat->sbaOrder == 0) {
+                if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn) {
+                  pos = posInSyz(strat, Q.sig);
+                  enterSyz(Q, strat, pos);
+                }
+              } else {
+                pos = posInSyz(strat, Q.sig);
+                enterSyz(Q, strat, pos);
+              }
+            }
+          }
+          //printf("++ -- done adding syzygies -- ++\n");
+        }
+      }
+//#if 1
+#if DEBUGF50
+    printf("---------------------------\n");
+    Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
+    Print("LEAD POLY:  "); pWrite(pHead(strat->S[strat->sl]));
+    Print("SIGNATURE:  "); pWrite(strat->sig[strat->sl]);
+#endif
+      /*
+      if (newrules)
+      {
+        newrules  = FALSE;
+      }
+      */
+#if 0
+      int pl=pLength(strat->P.p);
+      if (pl==1)
+      {
+        //if (TEST_OPT_PROT)
+        //PrintS("<1>");
+      }
+      else if (pl==2)
+      {
+        //if (TEST_OPT_PROT)
+        //PrintS("<2>");
+      }
+#endif
+      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
+//      Print("[%d]",hilbeledeg);
+      if (strat->P.lcm!=NULL)
+#ifdef HAVE_RINGS
+        pLmDelete(strat->P.lcm);
+#else
+        pLmFree(strat->P.lcm);
+#endif
+      if (strat->sl>srmax) srmax = strat->sl;
+    }
+    else
+    {
       case_when_red_result_changed:
       // adds signature of the zero reduction to
@@ -2935 +3802 @@
 #endif
   
-  idTest(strat->Shdl);
   // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
   #ifdef HAVE_RINGS
@@ -2955 +3821 @@
     //  {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
     //idPrint(strat->Shdl);
-  idTest(strat->Shdl);
     //printf("\nk = %i\n",k);
     for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
@@ -2980 +3845 @@
   //idSkipZeroes(strat->Shdl);
   //idPrint(strat->Shdl);
-  idTest(strat->Shdl);
   
   if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)

kernel/GBEngine/kutil.cc

@@ -2381 +2381 @@
 #else
 void enterOnePairSig (int i, poly p, poly pSig, int, int ecart, int isFromQ, kStrategy strat, int atR = -1)
+#endif
+{
+  assume(i<=strat->sl);
+
+  int      l;
+  poly m1 = NULL,m2 = NULL; // we need the multipliers for the s-polynomial to compute
+              // the corresponding signatures for criteria checks
+  LObject  Lp;
+  poly pSigMult = p_Copy(pSig,currRing);
+  poly sSigMult = p_Copy(strat->sig[i],currRing);
+  unsigned long pSigMultNegSev,sSigMultNegSev;
+  Lp.i_r = -1;
+
+#ifdef KDEBUG
+  Lp.ecart=0; Lp.length=0;
+#endif
+  /*- computes the lcm(s[i],p) -*/
+  Lp.lcm = pInit();
+  k_GetLeadTerms(p,strat->S[i],currRing,m1,m2,currRing);
+#ifndef HAVE_RATGRING
+  pLcm(p,strat->S[i],Lp.lcm);
+#elif defined(HAVE_RATGRING)
+  //  if (rIsRatGRing(currRing))
+  pLcmRat(p,strat->S[i],Lp.lcm, currRing->real_var_start); // int rat_shift
+#endif
+  pSetm(Lp.lcm);
+
+  // set coeffs of multipliers m1 and m2
+  pSetCoeff0(m1, nInit(1));
+  pSetCoeff0(m2, nInit(1));
+//#if 1
+#ifdef DEBUGF5
+  Print("P1  ");
+  pWrite(pHead(p));
+  Print("P2  ");
+  pWrite(pHead(strat->S[i]));
+  Print("M1  ");
+  pWrite(m1);
+  Print("M2  ");
+  pWrite(m2);
+#endif
+  // get multiplied signatures for testing
+  pSigMult = currRing->p_Procs->pp_Mult_mm(pSigMult,m1,currRing);
+  pSigMultNegSev = ~p_GetShortExpVector(pSigMult,currRing);
+  sSigMult = currRing->p_Procs->pp_Mult_mm(sSigMult,m2,currRing);
+  sSigMultNegSev = ~p_GetShortExpVector(sSigMult,currRing);
+
+//#if 1
+#ifdef DEBUGF5
+  Print("----------------\n");
+  pWrite(pSigMult);
+  pWrite(sSigMult);
+  Print("----------------\n");
+  Lp.checked  = 0;
+#endif
+  int sigCmp = p_LmCmp(pSigMult,sSigMult,currRing);
+//#if 1
+#if DEBUGF5
+  Print("IN PAIR GENERATION - COMPARING SIGS: %d\n",sigCmp);
+  pWrite(pSigMult);
+  pWrite(sSigMult);
+#endif
+  if(sigCmp==0)
+  {
+    // printf("!!!!   EQUAL SIGS   !!!!\n");
+    // pSig = sSig, delete element due to Rewritten Criterion
+    pDelete(&pSigMult);
+    pDelete(&sSigMult);
+    if (rField_is_Ring(currRing))
+      pLmDelete(Lp.lcm);
+    else
+      pLmFree(Lp.lcm);
+    Lp.lcm=NULL;
+    pDelete (&m1);
+    pDelete (&m2);
+    return;
+  }
+  // testing by syzCrit = F5 Criterion
+  // testing by rewCrit1 = Rewritten Criterion
+  // NOTE: Arri's Rewritten Criterion is tested below, we need Lp.p for it!
+  if  ( strat->syzCrit(pSigMult,pSigMultNegSev,strat) ||
+        strat->syzCrit(sSigMult,sSigMultNegSev,strat)
+        || strat->rewCrit1(sSigMult,sSigMultNegSev,Lp.lcm,strat,i+1)
+      )
+  {
+    pDelete(&pSigMult);
+    pDelete(&sSigMult);
+    if (rField_is_Ring(currRing))
+      pLmDelete(Lp.lcm);
+    else
+      pLmFree(Lp.lcm);
+    Lp.lcm=NULL;
+    pDelete (&m1);
+    pDelete (&m2);
+    return;
+  }
+  /*
+  *the pair (S[i],p) enters B if the spoly != 0
+  */
+  /*-  compute the short s-polynomial -*/
+  if (strat->fromT && !TEST_OPT_INTSTRATEGY)
+    pNorm(p);
+
+  if ((strat->S[i]==NULL) || (p==NULL))
+    return;
+
+  if ((strat->fromQ!=NULL) && (isFromQ!=0) && (strat->fromQ[i]!=0))
+    Lp.p=NULL;
+  else
+  {
+    #ifdef HAVE_PLURAL
+    if ( rIsPluralRing(currRing) )
+    {
+      if(pHasNotCF(p, strat->S[i]))
+      {
+        if(ncRingType(currRing) == nc_lie)
+        {
+          // generalized prod-crit for lie-type
+          strat->cp++;
+          Lp.p = nc_p_Bracket_qq(pCopy(p),strat->S[i], currRing);
+        }
+        else
+        if( ALLOW_PROD_CRIT(strat) )
+        {
+          // product criterion for homogeneous case in SCA
+          strat->cp++;
+          Lp.p = NULL;
+        }
+        else
+        {
+          Lp.p = // nc_CreateSpoly(strat->S[i],p,currRing);
+                nc_CreateShortSpoly(strat->S[i], p, currRing);
+
+          assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
+          pNext(Lp.p) = strat->tail; // !!!
+        }
+      }
+      else
+      {
+        Lp.p = // nc_CreateSpoly(strat->S[i],p,currRing);
+              nc_CreateShortSpoly(strat->S[i], p, currRing);
+
+        assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
+        pNext(Lp.p) = strat->tail; // !!!
+      }
+    }
+    else
+    #endif
+    {
+      assume(!rIsPluralRing(currRing));
+      Lp.p = ksCreateShortSpoly(strat->S[i], p, strat->tailRing);
+    }
+  }
+  // store from which element this pair comes from for further tests
+  //Lp.from = strat->sl+1;
+  if(sigCmp==currRing->OrdSgn)
+  {
+    // pSig > sSig
+    pDelete (&sSigMult);
+    Lp.sig    = pSigMult;
+    Lp.sevSig = ~pSigMultNegSev;
+  }
+  else
+  {
+    // pSig < sSig
+    pDelete (&pSigMult);
+    Lp.sig    = sSigMult;
+    Lp.sevSig = ~sSigMultNegSev;
+  }
+  if (Lp.p == NULL)
+  {
+    if (Lp.lcm!=NULL) pLmFree(Lp.lcm);
+    int pos = posInSyz(strat, Lp.sig);
+    enterSyz(Lp, strat, pos);
+  }
+  else
+  {
+    // testing by rewCrit3 = Arris Rewritten Criterion (for F5 nothing happens!)
+    if (strat->rewCrit3(Lp.sig,~Lp.sevSig,Lp.p,strat,strat->sl+1))
+    {
+      pLmFree(Lp.lcm);
+      pDelete(&Lp.sig);
+      Lp.lcm=NULL;
+      pDelete (&m1);
+      pDelete (&m2);
+      return;
+    }
+    // in any case Lp is checked up to the next strat->P which is added
+    // to S right after this critical pair creation.
+    // NOTE: this even holds if the 2nd generator gives the bigger signature
+    //       moreover, this improves rewCriterion,
+    //       i.e. strat->checked > strat->from if and only if the 2nd generator
+    //       gives the bigger signature.
+    Lp.checked = strat->sl+1;
+    // at this point it is clear that the pair will be added to L, since it has
+    // passed all tests up to now
+
+  // adds buchberger's first criterion
+    if (pLmCmp(m2,pHead(p)) == 0)
+    {
+      Lp.prod_crit = TRUE; // Product Criterion
+#if 0
+      int pos = posInSyz(strat, Lp.sig);
+      enterSyz(Lp, strat, pos);
+      Lp.lcm=NULL;
+      pDelete (&m1);
+      pDelete (&m2);
+      return;
+#endif
+    }
+    pDelete (&m1);
+    pDelete (&m2);
+#if DEBUGF5
+    PrintS("SIGNATURE OF PAIR:  ");
+    pWrite(Lp.sig);
+#endif
+    /*- the pair (S[i],p) enters B -*/
+    Lp.p1 = strat->S[i];
+    Lp.p2 = p;
+
+    if (
+        (!rIsPluralRing(currRing))
+//      ||  (rIsPluralRing(currRing) && (ncRingType(currRing) != nc_lie))
+       )
+    {
+      assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
+      pNext(Lp.p) = strat->tail; // !!!
+    }
+
+    if (atR >= 0)
+    {
+      Lp.i_r1 = strat->S_2_R[i];
+      Lp.i_r2 = atR;
+    }
+    else
+    {
+      Lp.i_r1 = -1;
+      Lp.i_r2 = -1;
+    }
+    strat->initEcartPair(&Lp,strat->S[i],p,strat->ecartS[i],ecart);
+
+    if (TEST_OPT_INTSTRATEGY)
+    {
+      if (!rIsPluralRing(currRing))
+        nDelete(&(Lp.p->coef));
+    }
+
+    l = strat->posInLSba(strat->B,strat->Bl,&Lp,strat);
+    enterL(&strat->B,&strat->Bl,&strat->Bmax,Lp,l);
+  }
+}
+
+
+#ifdef DEBUGF5
+void enterOnePairSigRing (int i, poly p, poly pSig, int from, int ecart, int isFromQ, kStrategy strat, int atR = -1)
+#else
+void enterOnePairSigRing (int i, poly p, poly pSig, int, int ecart, int isFromQ, kStrategy strat, int atR = -1)
 #endif
 {
@@ -3586 +3843 @@
 *using signatures <= only for signature-based standard basis algorithms
 */
+
 void initenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1)
 {
@@ -3600 +3858 @@
       if ((isFromQ)&&(strat->fromQ!=NULL))
       {
-        for (j=0; j<=k && !strat->sigdrop; j++)
+        for (j=0; j<=k; j++)
         {
           if (!strat->fromQ[j])
@@ -3613 +3871 @@
       {
         new_pair=TRUE;
-        for (j=0; j<=k && !strat->sigdrop; j++)
+        for (j=0; j<=k; j++)
         {
           enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
@@ -3622 +3880 @@
     else
     {
-      for (j=0; j<=k && !strat->sigdrop; j++)
+      for (j=0; j<=k; j++)
       {
         if ((pGetComp(h)==pGetComp(strat->S[j]))
@@ -3629 +3887 @@
           new_pair=TRUE;
           enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+        //Print("j:%d, Ll:%d\n",j,strat->Ll);
+        }
+      }
+    }
+
+    if (new_pair)
+    {
+#ifdef HAVE_RATGRING
+      if (currRing->real_var_start>0)
+        chainCritPart(h,ecart,strat);
+      else
+#endif
+      strat->chainCrit(h,ecart,strat);
+    }
+  }
+}
+
+void initenterpairsSigRing (poly h,poly hSig,int hFrom,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1)
+{
+
+  if ((strat->syzComp==0)
+  || (pGetComp(h)<=strat->syzComp))
+  {
+    int j;
+    BOOLEAN new_pair=FALSE;
+
+    if (pGetComp(h)==0)
+    {
+      /* for Q!=NULL: build pairs (f,q),(f1,f2), but not (q1,q2)*/
+      if ((isFromQ)&&(strat->fromQ!=NULL))
+      {
+        for (j=0; j<=k && !strat->sigdrop; j++)
+        {
+          if (!strat->fromQ[j])
+          {
+            new_pair=TRUE;
+            enterOnePairSigRing(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+          //Print("j:%d, Ll:%d\n",j,strat->Ll);
+          }
+        }
+      }
+      else
+      {
+        new_pair=TRUE;
+        for (j=0; j<=k && !strat->sigdrop; j++)
+        {
+          enterOnePairSigRing(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+          //Print("j:%d, Ll:%d\n",j,strat->Ll);
+        }
+      }
+    }
+    else
+    {
+      for (j=0; j<=k && !strat->sigdrop; j++)
+      {
+        if ((pGetComp(h)==pGetComp(strat->S[j]))
+        || (pGetComp(strat->S[j])==0))
+        {
+          new_pair=TRUE;
+          enterOnePairSigRing(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
         //Print("j:%d, Ll:%d\n",j,strat->Ll);
         }
@@ -4550 +4868 @@
   printf("\n      Trying to add spolys\n");
   #endif
-  initenterpairsSig(h, hSig, hFrom, k, ecart, 0, strat, atR);
+  initenterpairsSigRing(h, hSig, hFrom, k, ecart, 0, strat, atR);
   if(strat->sigdrop) return;
   #ifdef ADIDEBUG
@@ -6860 +7178 @@
     pWrite(pHead(strat->S[k]));
 #endif
-    if (p_LmShortDivisibleBy(strat->sig[k], strat->sevSig[k], sig, not_sevSig, currRing)
-    && (!rField_is_Ring(currRing) || (n_DivBy(pGetCoeff(sig),pGetCoeff(strat->sig[k]),currRing)  && pLmCmp(sig,strat->sig[k]) == 1 )))
+    if (p_LmShortDivisibleBy(strat->sig[k], strat->sevSig[k], sig, not_sevSig, currRing))
     {
 //#if 1
@@ -9051 +9368 @@
   #ifdef ADIDEBUG
   printf("\nenterT: add in position %i\n",atT);
-  pWrite(p.p);pWrite(p.sig);
+  p_Write(p.p,strat->tailRing);p_Write(p.sig,currRing);
   #endif
   //printf("\nenterT: neue hingefÌgt: lÀnge = %i, ecart = %i\n",p.length,p.ecart);

kernel/GBEngine/kutil.h

@@ -521 +521 @@
 int redHomog (LObject* h,kStrategy strat);
 int redSig (LObject* h,kStrategy strat);
+int redSigRing (LObject* h,kStrategy strat);
 //adds hSig to be able to check with F5's criteria when entering pairs!
 void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
@@ -577 +578 @@
 void enterOnePairLift (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
 void enterOnePairSig (int i,poly p,poly pSig,int ecart, int isFromQ,kStrategy strat, int atR);
+void enterOnePairSigRing (int i,poly p,poly pSig,int ecart, int isFromQ,kStrategy strat, int atR);
 void chainCritNormal (poly p,int ecart,kStrategy strat);
 void chainCritOpt_1 (poly,int,kStrategy strat);
@@ -717 +719 @@
                  number *coef = NULL,
                  kStrategy strat = NULL);
+                 
+int ksReducePolySigRing(LObject* PR,
+                 TObject* PW,
+                 long idx,
+                 poly spNoether = NULL,
+                 number *coef = NULL,
+                 kStrategy strat = NULL);
 
 // Reduces PR at Current->next with PW