Changeset 9e806f in git

Timestamp:

Jul 12, 2012, 3:24:21 PM (12 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

010b3f834f90fe0815d115c4a3a4c6934a96ac81

Parents:

cffd3e2f630fbc7b0e35afee97d6fa948cfd0b3e19609cce8ae122e920a77ead0ddc3ea3984ecc0d

Message:

Merge pull request #152 from ederc/sw-sba-ssg

Signature-based algorithms in spielwiese

Files:

• Singular/grammar.cc (modified) (1 diff)
• Singular/grammar.h (modified) (1 diff)
• Singular/grammar.y (modified) (1 diff)
• Singular/iparith.cc (modified) (1 diff)
• Singular/table.h (modified) (5 diffs)
• Tst/Long/cyclic-sba_l.res.gz.uu (added)
• Tst/Long/cyclic-sba_l.stat (added)
• Tst/Long/cyclic-sba_l.tst (added)
• Tst/Long/eco-sba_l.res.gz.uu (added)
• Tst/Long/eco-sba_l.stat (added)
• Tst/Long/eco-sba_l.tst (added)
• Tst/Long/katsura-sba_l.res.gz.uu (added)
• Tst/Long/katsura-sba_l.stat (added)
• Tst/Long/katsura-sba_l.tst (added)
• Tst/Short/sba_s.res.gz.uu (added)
• Tst/Short/sba_s.stat (added)
• Tst/Short/sba_s.tst (added)
• doc/reference.doc (modified) (previous)
• kernel/kInline.h (modified) (1 diff)
• kernel/kspoly.cc (modified) (1 diff)
• kernel/kstd1.cc (modified) (2 diffs)
• kernel/kstd1.h (modified) (1 diff)
• kernel/kstd2.cc (modified) (5 diffs)
• kernel/kutil.cc (modified) (17 diffs)
• kernel/kutil.h (modified) (16 diffs)

Singular/grammar.cc

@@ -396 +396 @@
      PARAMETER = 381,
      SYSVAR = 382,
-     UMINUS = 383
+     UMINUS = 383,
+     SBA_CMD = 384
    };
 #endif

Singular/grammar.h

@@ -164 +164 @@
      PARAMETER = 381,
      SYSVAR = 382,
-     UMINUS = 383
+     UMINUS = 383,
+     SBA_CMD = 384
    };
 #endif

Singular/grammar.y

@@ -262 +262 @@
 %token <i> REGULARITY_CMD
 %token <i> RES_CMD
+%token <i> SBA_CMD
 %token <i> SIMPLIFY_CMD
 %token <i> SORTVEC_CMD

Singular/iparith.cc

@@ -4783 +4783 @@
   //res->data=(char *)t_rep_gb(currRing, u_id);
 
+  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
+  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
+  return FALSE;
+}
+static BOOLEAN jjSBA(leftv res, leftv v)
+{
+  ideal result;
+  ideal v_id=(ideal)v->Data();
+  intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD);
+  tHomog hom=testHomog;
+  if (w!=NULL)
+  {
+    if (!idTestHomModule(v_id,currQuotient,w))
+    {
+      WarnS("wrong weights");
+      w=NULL;
+    }
+    else
+    {
+      hom=isHomog;
+      w=ivCopy(w);
+    }
+  }
+  result=kSba(v_id,currQuotient,hom,&w,1,0);
+  idSkipZeroes(result);
+  res->data = (char *)result;
+  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
+  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
+  return FALSE;
+}
+static BOOLEAN jjSBA_1(leftv res, leftv v, leftv u)
+{
+  ideal result;
+  ideal v_id=(ideal)v->Data();
+  intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD);
+  tHomog hom=testHomog;
+  if (w!=NULL)
+  {
+    if (!idTestHomModule(v_id,currQuotient,w))
+    {
+      WarnS("wrong weights");
+      w=NULL;
+    }
+    else
+    {
+      hom=isHomog;
+      w=ivCopy(w);
+    }
+  }
+  result=kSba(v_id,currQuotient,hom,&w,(int)(long)u->Data(),0);
+  idSkipZeroes(result);
+  res->data = (char *)result;
+  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
+  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
+  return FALSE;
+}
+static BOOLEAN jjSBA_2(leftv res, leftv v, leftv u, leftv t)
+{
+  ideal result;
+  ideal v_id=(ideal)v->Data();
+  intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD);
+  tHomog hom=testHomog;
+  if (w!=NULL)
+  {
+    if (!idTestHomModule(v_id,currQuotient,w))
+    {
+      WarnS("wrong weights");
+      w=NULL;
+    }
+    else
+    {
+      hom=isHomog;
+      w=ivCopy(w);
+    }
+  }
+  result=kSba(v_id,currQuotient,hom,&w,(int)(long)u->Data(),(int)(long)t->Data());
+  idSkipZeroes(result);
+  res->data = (char *)result;
   if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
   if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);

Singular/table.h

@@ -238 +238 @@
 ,{D(jjROWS_BIM),   ROWS_CMD,        INT_CMD,        BIGINTMAT_CMD , ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjCOUNT_IV),   ROWS_CMD,        INT_CMD,        INTVEC_CMD    , ALLOW_PLURAL |ALLOW_RING}
+,{D(jjSBA),        SBA_CMD,         IDEAL_CMD,      IDEAL_CMD     , ALLOW_PLURAL |ALLOW_RING}
+,{D(jjSBA),        SBA_CMD,         MODUL_CMD,      MODUL_CMD     , ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjSLIM_GB),    SLIM_GB_CMD,     IDEAL_CMD,      IDEAL_CMD     , ALLOW_PLURAL }
 ,{D(jjSLIM_GB),    SLIM_GB_CMD,     MODUL_CMD,      MODUL_CMD     , ALLOW_PLURAL }
@@ -662 +664 @@
 ,{D(jjRES),       SRES_CMD,       RESOLUTION_CMD, IDEAL_CMD,  INT_CMD, NO_PLURAL |ALLOW_RING}
 ,{D(jjRES),       SRES_CMD,       RESOLUTION_CMD, MODUL_CMD,  INT_CMD, NO_PLURAL |ALLOW_RING}
+,{D(jjSBA_1),     SBA_CMD,        IDEAL_CMD,      IDEAL_CMD,  INT_CMD, ALLOW_PLURAL |ALLOW_RING}
+,{D(jjSBA_1),     SBA_CMD,        MODUL_CMD,      MODUL_CMD,  INT_CMD, ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjSTD_1),     STD_CMD,        IDEAL_CMD,      IDEAL_CMD,  POLY_CMD, ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjSTD_1),     STD_CMD,        MODUL_CMD,      MODUL_CMD,  VECTOR_CMD, ALLOW_PLURAL |ALLOW_RING}
@@ -760 +764 @@
 ,{D(jjRES3),           SRES_CMD,   NONE,       MODUL_CMD,  INT_CMD,    ANY_TYPE, NO_PLURAL |ALLOW_RING}
 #endif
+,{D(jjSBA_2),          SBA_CMD,    IDEAL_CMD,  IDEAL_CMD,  INT_CMD, INT_CMD, ALLOW_PLURAL |ALLOW_RING}
+,{D(jjSBA_2),          SBA_CMD,    MODUL_CMD,  MODUL_CMD,  INT_CMD, INT_CMD, ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjSTATUS3),        STATUS_CMD, INT_CMD,    LINK_CMD,   STRING_CMD, STRING_CMD, ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjSTD_HILB_W),     STD_CMD,    IDEAL_CMD,  IDEAL_CMD,  INTVEC_CMD, INTVEC_CMD, NO_PLURAL |NO_RING}
@@ -828 +834 @@
 ,{D(loSimplex),   SIMPLEX_CMD,     LIST_CMD,            6      , NO_PLURAL |NO_RING}
 ,{D(nuUResSolve), URSOLVE_CMD,     LIST_CMD,            4      , NO_PLURAL |NO_RING}
+,{D(jjCALL1ARG),  SBA_CMD,         IDEAL_CMD,           1      , ALLOW_PLURAL |ALLOW_RING}
+,{D(jjCALL2ARG),  SBA_CMD,         IDEAL_CMD,           2      , ALLOW_PLURAL |ALLOW_RING}
+,{D(jjCALL3ARG),  SBA_CMD,         IDEAL_CMD,           3      , NO_PLURAL |ALLOW_RING}
 ,{D(jjCALL1ARG),  STD_CMD,         IDEAL_CMD,           1      , ALLOW_PLURAL |ALLOW_RING}
 ,{D(jjCALL2ARG),  STD_CMD,         IDEAL_CMD,           2      , ALLOW_PLURAL |ALLOW_RING}
@@ -1027 +1036 @@
   { "ringlist",    0, RINGLIST_CMD ,      CMD_1},
   { "rvar",        0, IS_RINGVAR ,        CMD_1},
+  { "sba",         0, SBA_CMD ,           CMD_M},
   { "setring",     0, SETRING_CMD ,       SETRING_CMD},
   { "simplex",     0, SIMPLEX_CMD,        CMD_M},

kernel/kInline.h

@@ -1173 +1173 @@
 }
 
+// dummy function for function pointer strat->rewCrit being usable in all
+// possible choices for criteria
+KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, kStrategy strat, int start=0)
+{
+  return FALSE;
+}
+
 #endif // defined(KINLINE) || defined(KUTIL_CC)
 #endif // KINLINE_H

kernel/kspoly.cc

@@ -155 +155 @@
 #endif
   
+#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
+  if (TEST_OPT_DEBUG)
+  {
+    Print(" to: "); PR->wrp(); Print("\n");
+  }
+#endif
+  return ret;
+}
+
+/***************************************************************
+ *
+ * Reduces PR with PW
+ * Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
+ *
+ ***************************************************************/
+int ksReducePolySig(LObject* PR,
+                 TObject* PW,
+                 long idx,
+                 poly spNoether,
+                 number *coef,
+                 kStrategy strat)
+{
+#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->incremental
+   * 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->incremental
+   * 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 f1 = p_Copy(PR->GetLmCurrRing(),currRing);
+    poly f2 = PW->GetLmCurrRing();
+    poly sigMult = pCopy(PW->sig);   // copy signature of reducer
+    p_ExpVectorSub(f1, f2, currRing); // Calculate the Monomial we must multiply to p2
+//#if 1
+#ifdef DEBUGF5
+    printf("IN KSREDUCEPOLYSIG: \n");
+    pWrite(pHead(f1));
+    pWrite(pHead(f2));
+    pWrite(sigMult);
+    printf("--------------\n");
+#endif
+    sigMult = pp_Mult_qq(f1,sigMult,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)

kernel/kstd1.cc

@@ -1098 +1098 @@
 }
 
+
+void initSba(ideal F,kStrategy strat)
+{
+  int i;
+  //idhdl h;
+ /* setting global variables ------------------- */
+  strat->enterS = enterSSba;
+    strat->red2 = redHoney;
+  if (strat->honey)
+    strat->red2 = redHoney;
+  else if (currRing->pLexOrder && !strat->homog)
+    strat->red2 = redLazy;
+  else
+  {
+    strat->LazyPass *=4;
+    strat->red2 = redHomog;
+  }
+#ifdef HAVE_RINGS  //TODO Oliver
+  if (rField_is_Ring(currRing))
+  {
+    strat->red2 = redRing;
+  }
+#endif
+  if (currRing->pLexOrder && strat->honey)
+    strat->initEcart = initEcartNormal;
+  else
+    strat->initEcart = initEcartBBA;
+  if (strat->honey)
+    strat->initEcartPair = initEcartPairMora;
+  else
+    strat->initEcartPair = initEcartPairBba;
+  //strat->kIdeal = NULL;
+  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
+  //else              strat->kIdeal->rtyp=MODUL_CMD;
+  //strat->kIdeal->data=(void *)strat->Shdl;
+  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
+  {
+    //interred  machen   Aenderung
+    strat->pOrigFDeg  = currRing->pFDeg;
+    strat->pOrigLDeg  = currRing->pLDeg;
+    //h=ggetid("ecart");
+    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
+    //{
+    //  ecartWeights=iv2array(IDINTVEC(h));
+    //}
+    //else
+    {
+      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
+      /*uses automatic computation of the ecartWeights to set them*/
+      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights, currRing);
+    }
+    pRestoreDegProcs(currRing, totaldegreeWecart, maxdegreeWecart);
+    if (TEST_OPT_PROT)
+    {
+      for(i=1; i<=(currRing->N); i++)
+        Print(" %d",ecartWeights[i]);
+      PrintLn();
+      mflush();
+    }
+  }
+  // for sig-safe reductions in signature-based
+  // standard basis computations
+  strat->red          = redSig;
+  //strat->incremental  = TRUE;
+  strat->currIdx      = 1;
+}
+
 void initMora(ideal F,kStrategy strat)
 {
@@ -1795 +1862 @@
       else
         r=bba(F,Q,NULL,hilb,strat);
+    }
+  }
+#ifdef KDEBUG
+  idTest(r);
+#endif
+  if (toReset)
+  {
+    kModW = NULL;
+    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
+  }
+  currRing->pLexOrder = b;
+//Print("%d reductions canceled \n",strat->cel);
+  HCord=strat->HCord;
+  delete(strat);
+  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
+  return r;
+}
+
+ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int incremental, int arri, intvec *hilb,int syzComp,
+          int newIdeal, intvec *vw)
+{
+  if(idIs0(F))
+    return idInit(1,F->rank);
+
+  ideal r;
+  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
+  BOOLEAN delete_w=(w==NULL);
+  kStrategy strat=new skStrategy;
+  if (incremental!=0)
+  {
+    strat->incremental = TRUE;
+  }
+  else
+  {
+    strat->incremental = FALSE;
+  }
+  if (arri!=0)
+  {
+    strat->rewCrit1 = arriRewDummy;
+    strat->rewCrit2 = arriRewCriterion;
+  }
+  else
+  {
+    strat->rewCrit1 = faugereRewCriterion;
+    strat->rewCrit2 = faugereRewCriterion;
+  }
+
+  if(!TEST_OPT_RETURN_SB)
+    strat->syzComp = syzComp;
+  if (TEST_OPT_SB_1)
+    strat->newIdeal = newIdeal;
+  if (rField_has_simple_inverse(currRing))
+    strat->LazyPass=20;
+  else
+    strat->LazyPass=2;
+  strat->LazyDegree = 1;
+  strat->enterOnePair=enterOnePairNormal;
+  strat->chainCrit=chainCritNormal;
+  strat->ak = id_RankFreeModule(F,currRing);
+  strat->kModW=kModW=NULL;
+  strat->kHomW=kHomW=NULL;
+  if (vw != NULL)
+  {
+    currRing->pLexOrder=FALSE;
+    strat->kHomW=kHomW=vw;
+    strat->pOrigFDeg = currRing->pFDeg;
+    strat->pOrigLDeg = currRing->pLDeg;
+    pSetDegProcs(currRing,kHomModDeg);
+    toReset = TRUE;
+  }
+  if (h==testHomog)
+  {
+    if (strat->ak == 0)
+    {
+      h = (tHomog)idHomIdeal(F,Q);
+      w=NULL;
+    }
+    else if (!TEST_OPT_DEGBOUND)
+    {
+      h = (tHomog)idHomModule(F,Q,w);
+    }
+  }
+  currRing->pLexOrder=b;
+  if (h==isHomog)
+  {
+    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
+    {
+      strat->kModW = kModW = *w;
+      if (vw == NULL)
+      {
+        strat->pOrigFDeg = currRing->pFDeg;
+        strat->pOrigLDeg = currRing->pLDeg;
+        pSetDegProcs(currRing,kModDeg);
+        toReset = TRUE;
+      }
+    }
+    currRing->pLexOrder = TRUE;
+    if (hilb==NULL) strat->LazyPass*=2;
+  }
+  strat->homog=h;
+#ifdef KDEBUG
+  idTest(F);
+  idTest(Q);
+
+#if MYTEST
+  if (TEST_OPT_DEBUG)
+  {
+    PrintS("// kSTD: currRing: ");
+    rWrite(currRing);
+  }
+#endif
+
+#endif
+#ifdef HAVE_PLURAL
+  if (rIsPluralRing(currRing))
+  {
+    const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
+    strat->no_prod_crit   = ! bIsSCA;
+    if (w!=NULL)
+      r = nc_GB(F, Q, *w, hilb, strat, currRing);
+    else
+      r = nc_GB(F, Q, NULL, hilb, strat, currRing);
+  }
+  else
+#endif
+#ifdef HAVE_RINGS
+  if (rField_is_Ring(currRing))
+    r=bba(F,Q,NULL,hilb,strat);
+  else
+#endif
+  {
+    if (currRing->OrdSgn==-1)
+    {
+      if (w!=NULL)
+        r=mora(F,Q,*w,hilb,strat);
+      else
+        r=mora(F,Q,NULL,hilb,strat);
+    }
+    else
+    {
+      if (w!=NULL)
+        r=sba(F,Q,*w,hilb,strat);
+      else
+                          r=sba(F,Q,NULL,hilb,strat);
     }
   }

kernel/kstd1.h

@@ -29 +29 @@
 /// NOTE: this is just a wrapper which sets currRing for the actual kNF call
 poly kNF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing);
+ideal kSba(ideal F,ideal Q, tHomog h, intvec ** mw, int incremental=0, int arri=0, intvec *hilb=NULL,
+          int syzComp=0,int newIdeal=0, intvec *vw=NULL);
 
 ideal kStd(ideal F, ideal Q, tHomog h, intvec ** mw,intvec *hilb=NULL,

kernel/kstd2.cc

@@ -34 +34 @@
 #define PLURAL_INTERNAL_DECLARATIONS 1
 #endif
+
+#define DEBUGF50  0
+#define DEBUGF51  0
+
+#ifdef DEBUGF5
+#undef DEBUGF5
+//#define DEBUGF5 1
+#endif
+
+#define F5C       1
+#if F5C
+  #define F5CTAILRED 0
+#endif
+
 #include <kernel/kutil.h>
 #include <misc/options.h>
@@ -43 +57 @@
 #include <kernel/khstd.h>
 #include <polys/kbuckets.h>
+#include <polys/prCopy.h>
 //#include "cntrlc.h"
 #include <polys/weight.h>
@@ -478 +493 @@
         h->Clear();
         return -1;
+      }
+    }
+  }
+}
+
+/*2
+*  reduction procedure for signature-based standard
+*  basis algorithms:
+*  all reductions have to be sig-safe!
+*
+*  2 is returned if and only if the pair is rejected by the rewritten criterion
+*  at exactly this point of the computations. This is the last possible point
+*  such a check can be done => checks with the biggest set of available
+*  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->T, strat->sevT, strat->tl, 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 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;
+        }
       }
     }
@@ -1294 +1478 @@
   idTest(strat->Shdl);
 
+  return (strat->Shdl);
+}
+ideal sba (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->incremental
+  ideal F = F0;
+  ring sRing, currRingOld;
+  currRingOld  = currRing; 
+  if (strat->incremental)
+  {
+    sRing = sbaRing(strat);
+    if (sRing!=currRingOld)
+    {
+      rChangeCurrRing (sRing);
+      F = idrMoveR (F0, currRingOld, currRing);
+    }
+  }
+#if 0
+  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
+  rWrite (currRing);
+  printf("\n");
+#endif
+#ifdef KDEBUG
+  bba_count++;
+  int loop_count = 0;
+#endif /* KDEBUG */
+  om_Opts.MinTrack = 5;
+  int   srmax,lrmax, red_result = 1;
+  int   olddeg,reduc;
+  int hilbeledeg=1,hilbcount=0,minimcnt=0;
+  long zeroreductions = 0;
+  LObject L;
+  BOOLEAN withT     = FALSE;
+  BOOLEAN newrules  = FALSE;
+  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);
+  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
+  /*Shdl=*/initSbaBuchMora(F, Q,strat);
+  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 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
+    kStratInitChangeTailRing(strat);
+#endif
+  if (BVERBOSE(23))
+  {
+    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
+    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
+    kDebugPrint(strat);
+  }
+
+
+#ifdef KDEBUG
+  //kDebugPrint(strat);
+#endif
+  /* compute------------------------------------------------------- */
+  arriAgain:
+  while (strat->Ll >= 0)
+  {
+    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
+    #ifdef KDEBUG
+      loop_count++;
+      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->incremental && 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 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
+#ifdef HAVE_RINGS
+      if (rField_is_Ring(currRing))
+        pLmDelete(strat->P.p);
+      else
+#endif
+        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
+      strat->P.PrepareRed(strat->use_buckets);
+    }
+
+    if (strat->P.p == NULL && strat->P.t_p == NULL)
+    {
+      red_result = 0;
+    }
+    else
+    {
+      if (TEST_OPT_PROT)
+        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
+                &olddeg,&reduc,strat, red_result);
+
+//#if 1
+#ifdef DEBUGF5
+      Print("Poly before red: ");
+      pWrite(strat->P.p);
+#endif
+      /* reduction of the element choosen from L */
+      if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat, strat->P.checked+1))
+        red_result = strat->red(&strat->P,strat);
+      else
+      {
+        if (strat->P.lcm!=NULL)
+          pLmFree(strat->P.lcm);
+        red_result = 2;
+      }
+      if (errorreported)  break;
+    }
+
+    if (strat->overflow)
+    {
+        if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
+    }
+    if (strat->incremental)
+    {
+      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;
+      }
+    }
+
+    // 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;
+
+#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
+      /*
+      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
+      {
+        strat->P.pCleardenom();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+        {
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+          strat->P.pCleardenom();
+        }
+      }
+      else
+      {
+        strat->P.pNorm();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+      }
+      */
+#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 */
+
+      // 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))
+      if(!strat->incremental)
+      {
+        BOOLEAN overwrite = TRUE;
+        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);
+          for(int ps=0;ps<strat->sl+1;ps++)
+          {
+            int i = strat->syzl;
+
+            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;
+            }
+            strat->syz[i] = 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
+            p_ExpVectorAdd (strat->syz[i],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 = pCopy(strat->sig[ps]);
+            p_ExpVectorAdd (help,strat->P.p,currRing);  
+            strat->syz[i] = p_Add_q(strat->syz[i],help,currRing);
+            //printf("%d. SYZ  ",i+1);
+            //pWrite(strat->syz[i]);
+            strat->sevSyz[i] = p_GetShortExpVector(strat->syz[i],currRing);
+            strat->syzl++;
+          }
+        }
+      }
+        enterT(strat->P, strat);
+        strat->T[strat->tl].is_sigsafe = FALSE;
+#ifdef HAVE_RINGS
+      if (rField_is_Ring(currRing))
+        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);
+      // posInS only depends on the leading term
+      strat->enterS(strat->P, pos, strat, strat->tl);
+//#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
+    {
+      // 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) {
+        zeroreductions++;
+        enterSyz(strat->P,strat);
+//#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)
+  {
+    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();
+
+  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 */
+  // using F5C it is possible that there is some data stored in the last
+  // entries of strat->Shdl which are dirty, i.e. not correct, but also not NULL
+  // => we need to delete them before return the ideal
+#if F5C
+  for(int i=strat->sl+1;i<IDELEMS(strat->Shdl);i++)
+  {
+    //pDelete (&strat->Shdl->m[i]);
+    strat->Shdl->m[i] = NULL;
+  }
+#endif
+  if (strat->incremental && sRing!=currRingOld)
+  {
+    rChangeCurrRing (currRingOld);
+    F0          = idrMoveR (F, sRing, currRing);
+    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
+    rDelete (sRing);
+  }
+  idTest(strat->Shdl);
+
+#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
+  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
+  zeroreductions  = 0;
   return (strat->Shdl);
 }
@@ -1447 +2175 @@
   return res;
 }
+
+#if F5C
+/*********************************************************************
+* interrreduction step of the signature-based algorithm:
+* 1. all strat->S are interpreted as new critical pairs
+* 2. those pairs need to be completely reduced by the usual (non sig-
+*    safe) reduction process (including tail reductions)
+* 3. strat->S and strat->T are completely new computed in these steps
+********************************************************************/
+void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg, 
+          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
+          intvec *w,intvec *hilb )
+{
+  int Ll_old, red_result = 1;
+  BOOLEAN withT = FALSE;
+  int pos  = 0;
+  hilbeledeg=1;
+  hilbcount=0;
+  minimcnt=0;
+  srmax = 0; // strat->sl is 0 at this point
+  reduc = olddeg = lrmax = 0;
+  // we cannot use strat->T anymore
+  //cleanT(strat);
+  //strat->tl = -1;
+  Ll_old    = strat->Ll;
+  while (strat->tl >= 0)
+  {
+    if(!strat->T[strat->tl].is_redundant)
+    {
+      LObject h;
+      h.p = strat->T[strat->tl].p;
+      h.tailRing = strat->T[strat->tl].tailRing;
+      h.t_p = strat->T[strat->tl].t_p;
+      if (h.p!=NULL)
+      {
+        if (currRing->OrdSgn==-1)
+        {
+          cancelunit(&h);  
+          deleteHC(&h, strat);
+        }
+        if (h.p!=NULL)
+        {
+          if (TEST_OPT_INTSTRATEGY)
+          {
+            //pContent(h.p);
+            h.pCleardenom(); // also does a pContent
+          }
+          else
+          {
+            h.pNorm();
+          }
+          strat->initEcart(&h);
+          pos = strat->Ll+1;
+          h.sev = pGetShortExpVector(h.p);
+          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
+        }
+      }
+    }
+    strat->tl--;
+  }
+  strat->sl = -1;
+#if 0
+//#ifdef HAVE_TAIL_RING
+  if(!rField_is_Ring())  // create strong gcd poly computes with tailring and S[i] ->to be fixed
+    kStratInitChangeTailRing(strat);
+#endif
+  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
+  //strat->sl = -1;
+  /* picks the last element from the lazyset L */
+  while (strat->Ll>Ll_old)
+  {
+    strat->P = strat->L[strat->Ll];
+    strat->Ll--;
+//#if 1
+#ifdef DEBUGF5
+    Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
+    Print("-------------------------------------------------\n");
+    pWrite(pHead(strat->P.p));
+    pWrite(pHead(strat->P.p1));
+    pWrite(pHead(strat->P.p2));
+    printf("%d\n",strat->tl);
+    Print("-------------------------------------------------\n");
+#endif
+    if (pNext(strat->P.p) == strat->tail)
+    {
+      // deletes the short spoly
+#ifdef HAVE_RINGS
+      if (rField_is_Ring(currRing))
+        pLmDelete(strat->P.p);
+      else
+#endif
+        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
+      strat->P.PrepareRed(strat->use_buckets);
+    }
+
+    if (strat->P.p == NULL && strat->P.t_p == NULL)
+    {
+      red_result = 0;
+    }
+    else
+    {
+      if (TEST_OPT_PROT)
+        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
+            &olddeg,&reduc,strat, red_result);
+
+#ifdef DEBUGF5
+      Print("Poly before red: ");
+      pWrite(strat->P.p);
+#endif
+      /* complete reduction of the element choosen from L */
+      red_result = strat->red2(&strat->P,strat);
+      if (errorreported)  break;
+    }
+
+    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);
+      // 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);
+
+#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
+#if F5CTAILRED
+      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
+      {
+        strat->P.pCleardenom();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+        {
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+          strat->P.pCleardenom();
+        }
+      }
+      else
+      {
+        strat->P.pNorm();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+      }
+#endif
+#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 */
+
+      // 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
+      // here we need to recompute new signatures, but those are trivial ones
+      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
+      enterT(strat->P, strat);
+      // posInS only depends on the leading term
+      strat->enterS(strat->P, pos, strat, strat->tl);
+//#if 1
+#ifdef DEBUGF5
+      Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
+      pWrite(pHead(strat->S[strat->sl]));
+      pWrite(strat->sig[strat->sl]);
+#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
+    {
+      // 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 (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 */
+  }
+  int cc = 0;
+  while (cc<strat->tl+1)
+  {
+    strat->T[cc].sig        = pOne();
+    p_SetComp(strat->T[cc].sig,cc+1,currRing);
+    strat->T[cc].sevSig     = pGetShortExpVector(strat->T[cc].sig);
+    strat->sig[cc]          = strat->T[cc].sig;
+    strat->sevSig[cc]       = strat->T[cc].sevSig;
+    strat->T[cc].is_sigsafe = TRUE;  
+    cc++;
+  }
+  strat->max_lower_index = strat->tl;
+  // set current signature index of upcoming iteration step
+  // NOTE:  this needs to be set here, as otherwise initSyzRules cannot compute
+  //        the corresponding syzygy rules correctly
+  strat->currIdx = cc+1;
+  for (int cd=strat->Ll; cd>=0; cd--)
+  {
+    p_SetComp(strat->L[cd].sig,cc+1,currRing);
+    cc++;
+  }
+//#if 1
+#if DEBUGF5
+  Print("------------------- STRAT S ---------------------\n");
+  cc = 0;
+  while (cc<strat->tl+1)
+  {
+    pWrite(pHead(strat->S[cc]));
+    pWrite(strat->sig[cc]);
+    printf("- - - - - -\n");
+    cc++;
+  }
+  Print("-------------------------------------------------\n");
+  Print("------------------- STRAT T ---------------------\n");
+  cc = 0;
+  while (cc<strat->tl+1)
+  {
+    pWrite(pHead(strat->T[cc].p));
+    pWrite(strat->T[cc].sig);
+    printf("- - - - - -\n");
+    cc++;
+  }
+  Print("-------------------------------------------------\n");
+  Print("------------------- STRAT L ---------------------\n");
+  cc = 0;
+  while (cc<strat->Ll+1)
+  {
+    pWrite(pHead(strat->L[cc].p));
+    pWrite(pHead(strat->L[cc].p1));
+    pWrite(pHead(strat->L[cc].p2));
+    pWrite(strat->L[cc].sig);
+    printf("- - - - - -\n");
+    cc++;
+  }
+  Print("-------------------------------------------------\n");
+  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
+#endif
+
+}
+#endif
 
 /* shiftgb stuff */

kernel/kutil.cc

@@ -29 +29 @@
 #undef KDEBUG
 #define KDEBUG 2
+#endif
+
+#ifdef DEBUGF5
+#undef DEBUGF5
+//#define DEBUGF5 1
 #endif
 
@@ -72 +77 @@
 #endif
 
+#ifdef DEBUGF5
+#undef DEBUGF5
+#define DEBUGF5 2
+#endif
+
 denominator_list DENOMINATOR_LIST=NULL;
 
@@ -916 +926 @@
     strat->sevS[j] = strat->sevS[j+1];
     strat->S_2_R[j] = strat->S_2_R[j+1];
+  }
+#endif
+  if (strat->lenS!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->lenS[i]),&(strat->lenS[i+1]),(strat->sl - i)*sizeof(int));
+#else
+    for (j=i; j<strat->sl; j++) strat->lenS[j] = strat->lenS[j+1];
+#endif
+  }
+  if (strat->lenSw!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->lenSw[i]),&(strat->lenSw[i+1]),(strat->sl - i)*sizeof(wlen_type));
+#else
+    for (j=i; j<strat->sl; j++) strat->lenSw[j] = strat->lenSw[j+1];
+#endif
+  }
+  if (strat->fromQ!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->fromQ[i]),&(strat->fromQ[i+1]),(strat->sl - i)*sizeof(int));
+#else
+    for (j=i; j<strat->sl; j++)
+    {
+      strat->fromQ[j] = strat->fromQ[j+1];
+    }
+#endif
+  }
+  strat->S[strat->sl] = NULL;
+  strat->sl--;
+}
+
+
+/*2
+*cancels the i-th polynomial in the standardbase s
+*/
+void deleteInSSba (int i,kStrategy strat)
+{
+#ifdef ENTER_USE_MEMMOVE
+  memmove(&(strat->S[i]), &(strat->S[i+1]), (strat->sl - i)*sizeof(poly));
+  memmove(&(strat->sig[i]), &(strat->sig[i+1]), (strat->sl - i)*sizeof(poly));
+  memmove(&(strat->ecartS[i]),&(strat->ecartS[i+1]),(strat->sl - i)*sizeof(int));
+  memmove(&(strat->sevS[i]),&(strat->sevS[i+1]),(strat->sl - i)*sizeof(unsigned long));
+  memmove(&(strat->sevSig[i]),&(strat->sevSig[i+1]),(strat->sl - i)*sizeof(unsigned long));
+  memmove(&(strat->S_2_R[i]),&(strat->S_2_R[i+1]),(strat->sl - i)*sizeof(int));
+  memmove(&(strat->fromS[i]),&(strat->fromS[i+1]),(strat->sl - i)*sizeof(int));
+#else
+  int j;
+  for (j=i; j<strat->sl; j++)
+  {
+    strat->S[j] = strat->S[j+1];
+    strat->sig[j] = strat->sig[j+1];
+    strat->ecartS[j] = strat->ecartS[j+1];
+    strat->sevS[j] = strat->sevS[j+1];
+    strat->sevSig[j] = strat->sevSig[j+1];
+    strat->S_2_R[j] = strat->S_2_R[j+1];
+    strat->fromS[j] = strat->fromS[j+1];
   }
 #endif
@@ -1668 +1736 @@
 
 /*2
+* put the pair (s[i],p)  into the set B, ecart=ecart(p)
+* NOTE: here we need to add the signature-based criteria
+*/
+
+void enterOnePairSig (int i, poly p, poly pSig, int from, int ecart, int isFromQ, kStrategy strat, int atR = -1)
+{
+  assume(i<=strat->sl);
+  if (strat->interred_flag) return;
+
+  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 last;
+  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("FROM: %d\n", from);
+  Print("P2  ");
+  pWrite(pHead(strat->S[i]));
+  Print("FROM: %d\n", strat->fromS[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,last);
+  pSigMultNegSev = ~p_GetShortExpVector(pSigMult,currRing);
+  sSigMult = currRing->p_Procs->pp_Mult_mm(sSigMult,m2,currRing,last);
+  sSigMultNegSev = ~p_GetShortExpVector(sSigMult,currRing);
+  
+  pDelete (&m1);
+  pDelete (&m2);
+
+//#if 1
+#ifdef DEBUGF5
+  Print("----------------\n");
+  pWrite(pSigMult);
+  pWrite(sSigMult);
+  Print("----------------\n");
+#endif
+  // testing by syzCrit = F5 Criterion 
+  // testing by rewCrit1 = Rewritten Criterion
+  if  ( strat->syzCrit(pSigMult,pSigMultNegSev,strat) ||
+        strat->syzCrit(sSigMult,sSigMultNegSev,strat) 
+        || strat->rewCrit1(sSigMult,sSigMultNegSev,strat,i+1)
+      )
+  {
+    pDelete(&pSigMult);
+    pDelete(&sSigMult);
+    strat->cp++;
+    pLmFree(Lp.lcm);
+    Lp.lcm=NULL;
+    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;
+  int sigCmp = p_LmCmp(pSigMult,sSigMult,currRing);
+//#if 1
+#if DEBUGF5
+  printf("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
+    strat->cp++;
+    pDelete(&pSigMult);
+    pDelete(&sSigMult);
+    pLmFree(Lp.lcm);
+    Lp.lcm=NULL;
+    return;
+  }
+  // at this point it is clear that the pair will be added to L, since it has
+  // passed all tests up to now
+
+  // 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 DEBUGF5
+  printf("SIGNATURE OF PAIR:  ");
+  pWrite(Lp.sig);
+#endif
+  /*
+  *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; // !!!
+
+      }
+
+
+#if MYTEST
+      if (TEST_OPT_DEBUG)
+      {
+        PrintS("enterOnePairNormal::\n strat->S[i]: "); pWrite(strat->S[i]);
+        PrintS("p: "); pWrite(p);
+        PrintS("SPoly: "); pWrite(Lp.p);
+      }
+#endif
+
+    }
+    else
+    #endif
+    {
+      assume(!rIsPluralRing(currRing));
+      Lp.p = ksCreateShortSpoly(strat->S[i], p, strat->tailRing);
+#if MYTEST
+      if (TEST_OPT_DEBUG)
+      {
+        PrintS("enterOnePairNormal::\n strat->S[i]: "); pWrite(strat->S[i]);
+        PrintS("p: "); pWrite(p);
+        PrintS("commutative SPoly: "); pWrite(Lp.p);
+      }
+#endif
+
+      }
+  }
+  if (Lp.p == NULL)
+  {
+    /*- the case that the s-poly is 0 -*/
+    if (strat->pairtest==NULL) initPairtest(strat);
+    strat->pairtest[i] = TRUE;/*- hint for spoly(S^[i],p)=0 -*/
+    strat->pairtest[strat->sl+1] = TRUE;
+    /*hint for spoly(S[i],p) == 0 for some i,0 <= i <= sl*/
+    /*
+    *suppose we have (s,r),(r,p),(s,p) and spoly(s,p) == 0 and (r,p) is
+    *still in B (i.e. lcm(r,p) == lcm(s,p) or the leading term of s does not
+    *devide lcm(r,p)). In the last case (s,r) can be canceled if the leading
+    *term of p devides the lcm(s,r)
+    *(this canceling should be done here because
+    *the case lcm(s,p) == lcm(s,r) is not covered in chainCrit)
+    *the first case is handeled in chainCrit
+    */
+    if (Lp.lcm!=NULL) pLmFree(Lp.lcm);
+  }
+  else
+  {
+    /*- 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);
+  }
+}
+
+/*2
 * put the pair (s[i],p) into the set L, ecart=ecart(p)
 * in the case that s forms a SB of (s)
@@ -1771 +2101 @@
   {
     j = strat->posInL(strat->L,j,&(strat->B[i]),strat);
+    enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
+  }
+  strat->Bl = -1;
+}
+
+/*2
+* merge set B into L
+*/
+void kMergeBintoLSba(kStrategy strat)
+{
+  int j=strat->Ll+strat->Bl+1;
+  if (j>strat->Lmax)
+  {
+    j=((j+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
+    strat->L = (LSet)omReallocSize(strat->L,strat->Lmax*sizeof(LObject),
+                                 j*sizeof(LObject));
+    strat->Lmax=j;
+  }
+  j = strat->Ll;
+  int i;
+  for (i=strat->Bl; i>=0; i--)
+  {
+    j = strat->posInLSba(strat->L,j,&(strat->B[i]),strat);
     enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
   }
@@ -1988 +2341 @@
       j--;
     }
+  }
+}
+/*2
+*the pairset B of pairs of type (s[i],p) is complete now. It will be updated
+*using the chain-criterion in B and L and enters B to L
+*/
+void chainCritSig (poly p,int ecart,kStrategy strat)
+{
+  int i,j,l;
+  kMergeBintoLSba(strat);
+  j = strat->Ll;
+  loop  /*cannot be changed into a for !!! */
+  {
+    if (j <= 0)
+    {
+      /*now L[0] cannot be canceled any more and the tail can be removed*/
+      if (strat->L[0].p2 == strat->tail) strat->L[0].p2 = p;
+      break;
+    }
+    if (strat->L[j].p2 == p)
+    {
+      i = j-1;
+      loop
+      {
+        if (i < 0)  break;
+        if ((strat->L[i].p2 == p) && pLmEqual(strat->L[j].lcm,strat->L[i].lcm))
+        {
+          /*L[i] could be canceled but we search for a better one to cancel*/
+          strat->c3++;
+          if (isInPairsetL(i-1,strat->L[j].p1,strat->L[i].p1,&l,strat)
+              && (pNext(strat->L[l].p) == strat->tail)
+              && (!pLmEqual(strat->L[i].p,strat->L[l].p))
+              && pDivisibleBy(p,strat->L[l].lcm))
+          {
+            /*
+             *"NOT equal(...)" because in case of "equal" the element L[l]
+             *is "older" and has to be from theoretical point of view behind
+             *L[i], but we do not want to reorder L
+             */
+            strat->L[i].p2 = strat->tail;
+            /*
+             *L[l] will be canceled, we cannot cancel L[i] later on,
+             *so we mark it with "tail"
+             */
+            deleteInL(strat->L,&strat->Ll,l,strat);
+            i--;
+          }
+          else
+          {
+            deleteInL(strat->L,&strat->Ll,i,strat);
+          }
+          j--;
+        }
+        i--;
+      }
+    }
+    else if (strat->L[j].p2 == strat->tail)
+    {
+      /*now L[j] cannot be canceled any more and the tail can be removed*/
+      strat->L[j].p2 = p;
+    }
+    j--;
   }
 }
@@ -2342 +2757 @@
 }
 
+/*2
+*(s[0],h),...,(s[k],h) will be put to the pairset L
+*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)
+{
+
+  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; j++)
+        {
+          if (!strat->fromQ[j])
+          {
+            new_pair=TRUE;
+            enterOnePairSig(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; j++)
+        {
+          enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+          //Print("j:%d, Ll:%d\n",j,strat->Ll);
+        }
+      }
+    }
+    else
+    {
+      for (j=0; j<=k; j++)
+      {
+        if ((pGetComp(h)==pGetComp(strat->S[j]))
+        || (pGetComp(strat->S[j])==0))
+        {
+          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);
+    }
+  }
+}
+
 #ifdef HAVE_RINGS
 /*2
@@ -3100 +3579 @@
   }
  // PrintS("end enterpairs\n");
+}
+
+/*2
+*(s[0],h),...,(s[k],h) will be put to the pairset L(via initenterpairs)
+*superfluous elements in S will be deleted
+*this is a special variant of signature-based algorithms including the
+*signatures for criteria checks
+*/
+void enterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR)
+{
+int j=pos;
+
+#ifdef HAVE_RINGS
+assume (!rField_is_Ring(currRing));
+#endif
+
+initenterpairsSig(h,hSig,hFrom,k,ecart,0,strat, atR);
+if ( (!strat->fromT)
+&& ((strat->syzComp==0)
+  ||(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);
+    j++;
+  }
+  //Print("end clearS sl=%d\n",strat->sl);
+}
+// PrintS("end enterpairs\n");
 }
 
@@ -3953 +4464 @@
 * e is the ecart of p
 * set[length] is the smallest element in set with respect
+* to the signature order
+*/
+int posInLSig (const LSet set, const int length,
+            LObject* p,const kStrategy strat)
+{
+if (length<0) return 0;
+if (pLmCmp(set[length].sig,p->sig)== currRing->OrdSgn)
+  return length+1;
+
+int i;
+int an = 0;
+int en= length;
+loop
+{
+  if (an >= en-1)
+  {
+    if (pLmCmp(set[an].sig,p->sig) == currRing->OrdSgn) return en;
+    return an;
+  }
+  i=(an+en) / 2;
+  if (pLmCmp(set[i].sig,p->sig) == currRing->OrdSgn) an=i;
+  else                                      en=i;
+  /*aend. fuer lazy == in !=- machen */
+}
+}
+
+/*2
+* 
+* is only used in F5C, must ensure that the interreduction process does add new
+* critical pairs to strat->L only behind all other critical pairs which are
+* still in strat->L!
+*/
+int posInLF5C (const LSet set, const int length,
+            LObject* p,const kStrategy strat)
+{
+  return strat->Ll+1;
+}
+
+/*2
+* looks up the position of polynomial p in set
+* e is the ecart of p
+* set[length] is the smallest element in set with respect
 * to the ordering-procedure totaldegree,pComp
 */
@@ -4359 +4912 @@
 }
 
+/*
+ * SYZYGY CRITERION for signature-based standard basis algorithms
+ */
+BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
+{
+//#if 1
+#ifdef DEBUGF5
+  Print("syzygy criterion checks:  ");
+  pWrite(sig);
+#endif
+  for (int k=0; k<strat->syzl; k++)
+  {
+//#if 1
+#ifdef DEBUGF5
+    Print("checking with: %d --  ",k);
+    pWrite(pHead(strat->syz[k]));
+#endif
+    if (p_LmShortDivisibleBy(strat->syz[k], strat->sevSyz[k], sig, not_sevSig, currRing))
+    {
+//#if 1
+#ifdef DEBUGF5
+      printf("DELETE!\n");
+#endif
+      return TRUE;
+    }
+  }
+  return FALSE;
+}
+
+/*
+ * SYZYGY CRITERION for signature-based standard basis algorithms
+ */
+BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat)
+{
+//#if 1
+#ifdef DEBUGF5
+  Print("syzygy criterion checks:  ");
+  pWrite(sig);
+#endif
+  int comp = p_GetComp(sig, currRing);
+  int min, max;
+  if (comp<=1)
+    return FALSE;
+  else
+  {
+    min = strat->syzIdx[comp-2];
+    //printf("SYZIDX %d/%d\n",strat->syzIdx[comp-2],comp-2);
+    //printf("SYZIDX %d/%d\n",strat->syzIdx[comp-1],comp-1);
+    //printf("SYZIDX %d/%d\n",strat->syzIdx[comp],comp);
+    if (comp == strat->currIdx)
+    {
+      max = strat->syzl;
+    }
+    else
+    {
+      max = strat->syzIdx[comp-1];
+    }
+    for (int k=min; k<max; k++)
+    {
+#ifdef DEBUGF5
+      printf("COMP %d/%d - MIN %d - MAX %d - SYZL %ld\n",comp,strat->currIdx,min,max,strat->syzl);
+      Print("checking with: %d --  ",k);
+      pWrite(pHead(strat->syz[k]));
+#endif
+      if (p_LmShortDivisibleBy(strat->syz[k], strat->sevSyz[k], sig, not_sevSig, currRing))
+        return TRUE;
+    }
+    return FALSE;
+  }
+}
+
+/*
+ * REWRITTEN CRITERION for signature-based standard basis algorithms
+ */
+BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start=0)
+{
+  //printf("Faugere Rewritten Criterion\n");
+//#if 1
+#ifdef DEBUGF5
+  printf("rewritten criterion checks:  ");
+  pWrite(sig);
+#endif
+  //for(int k = start; k<strat->sl+1; k++)
+  for(int k = strat->sl; k>start; k--)
+  {
+//#if 1
+#ifdef DEBUGF5
+    Print("checking with:  ");
+    pWrite(strat->sig[k]);
+    pWrite(pHead(strat->S[k]));
+#endif
+    if (p_LmShortDivisibleBy(strat->sig[k], strat->sevSig[k], sig, not_sevSig, currRing))
+    //if (p_LmEqual(strat->sig[k], sig, currRing))
+    {
+//#if 1
+#ifdef DEBUGF5
+      printf("DELETE!\n");
+#endif
+      return TRUE;
+    }
+  }
+#ifdef DEBUGF5
+  Print("ALL ELEMENTS OF S\n----------------------------------------\n");
+  for(int kk = 0; kk<strat->sl+1; kk++)
+  {
+    pWrite(pHead(strat->S[kk]));
+  }
+  Print("------------------------------\n");
+#endif
+  return FALSE;
+}
+
+/*
+ * REWRITTEN CRITERION for signature-based standard basis algorithms
+ ***************************************************************************
+ * TODO:This should become the version of Arri/Perry resp. Bjarke/Stillman *
+ ***************************************************************************
+ */
+
+// real implementation of arri's rewritten criterion, only called once in
+// kstd2.cc, right before starting reduction
+// IDEA:  Arri says that it is enough to consider 1 polynomial for each unique
+//        signature appearing during the computations. Thus we first of all go
+//        through strat->L and delete all other pairs of the same signature,
+//        keeping only the one with least possible leading monomial. After this
+//        we check if we really need to compute this critical pair at all: There
+//        can be elements already in strat->S whose signatures divide the
+//        signature of the critical pair in question and whose multiplied
+//        leading monomials are smaller than the leading monomial of the
+//        critical pair. In this situation we can discard the critical pair
+//        completely.
+BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start=0)
+{
+  //printf("Arri Rewritten Criterion\n");
+  while (strat->Ll > 0 && pLmEqual(strat->L[strat->Ll].sig,strat->P.sig))
+  {
+    // deletes the short spoly
+#ifdef HAVE_RINGS
+    if (rField_is_Ring(currRing))
+      pLmDelete(strat->L[strat->Ll].p);
+    else
+#endif
+      pLmFree(strat->L[strat->Ll].p);
+
+    // TODO: needs some masking
+    // TODO: masking needs to vanish once the signature
+    //       sutff is completely implemented
+    strat->L[strat->Ll].p = NULL;
+    poly m1 = NULL, m2 = NULL;
+
+    // check that spoly creation is ok
+    while (strat->tailRing != currRing &&
+          !kCheckSpolyCreation(&(strat->L[strat->Ll]), 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->L[strat->Ll]), NULL, strat->use_buckets,
+                  strat->tailRing, m1, m2, strat->R);
+    if (strat->P.GetLmCurrRing() == NULL)
+    {
+      deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
+    }
+    if (strat->L[strat->Ll].GetLmCurrRing() == NULL)
+    {
+      strat->P.Delete();
+      strat->P = strat->L[strat->Ll];
+      strat->Ll--;
+    }
+
+    if (strat->P.GetLmCurrRing() != NULL && strat->L[strat->Ll].GetLmCurrRing() != NULL)
+    {
+      if (pLmCmp(strat->P.GetLmCurrRing(),strat->L[strat->Ll].GetLmCurrRing()) == -1)
+      {
+        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
+      }
+      else
+      {
+        strat->P.Delete();
+        strat->P = strat->L[strat->Ll];
+        strat->Ll--;
+      }
+    }
+  }
+  for (int ii=strat->sl; ii>-1; ii--)
+  {
+    if (p_LmShortDivisibleBy(strat->sig[ii], strat->sevSig[ii], strat->P.sig, ~strat->P.sevSig, currRing))
+    {
+      if (!(pLmCmp(ppMult_mm(strat->P.sig,pHead(strat->S[ii])),ppMult_mm(strat->sig[ii],strat->P.GetLmCurrRing())) == 1))
+      {
+        strat->P.Delete();
+        return TRUE;
+      }
+    }
+  }
+  return FALSE;
+}
+
 /***************************************************************
  *
@@ -5019 +5777 @@
 }
 
+void initSLSba (ideal F, ideal Q,kStrategy strat)
+{
+  int   i,j,pos, ctr=0, ps=0;
+  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
+  else i=setmaxT;
+  strat->ecartS =   initec(i);
+  strat->fromS  =   initec(i);
+  strat->sevS   =   initsevS(i);
+  strat->sevSig =   initsevS(i);
+  strat->S_2_R  =   initS_2_R(i);
+  strat->fromQ  =   NULL;
+  strat->Shdl   =   idInit(i,F->rank);
+  strat->S      =   strat->Shdl->m;
+  strat->sig    =   (poly *)omAlloc0(i*sizeof(poly));
+  if (!strat->incremental)
+  {
+    strat->syz    = (poly *)omAlloc0(i*sizeof(poly));
+    strat->sevSyz = initsevS(i);
+    strat->syzmax = i;
+    strat->syzl   = 0;
+  }
+  /*- put polys into S -*/
+  if (Q!=NULL)
+  {
+    strat->fromQ=initec(i);
+    memset(strat->fromQ,0,i*sizeof(int));
+    for (i=0; i<IDELEMS(Q); i++)
+    {
+      if (Q->m[i]!=NULL)
+      {
+        LObject h;
+        h.p = pCopy(Q->m[i]);
+        if (currRing->OrdSgn==-1)
+        {
+          deleteHC(&h,strat);
+        }
+        if (TEST_OPT_INTSTRATEGY)
+        {
+          //pContent(h.p);
+          h.pCleardenom(); // also does a pContent
+        }
+        else
+        {
+          h.pNorm();
+        }
+        if (h.p!=NULL)
+        {
+          strat->initEcart(&h);
+          if (strat->sl==-1)
+            pos =0;
+          else
+          {
+            pos = posInS(strat,strat->sl,h.p,h.ecart);
+          }
+          h.sev = pGetShortExpVector(h.p);
+          strat->enterS(h,pos,strat,-1);
+          strat->fromQ[pos]=1;
+        }
+      }
+    }
+  }
+  for (i=0; i<IDELEMS(F); i++)
+  {
+    if (F->m[i]!=NULL)
+    {
+      LObject h;
+      h.p = pCopy(F->m[i]);
+      h.sig = pOne();
+      //h.sig = pInit();
+      //p_SetCoeff(h.sig,nInit(1),currRing);
+      p_SetComp(h.sig,i+1,currRing);
+      // if we are working with the Schreyer order we generate it 
+      // by multiplying the initial signatures with the leading monomial
+      // of the corresponding initial polynomials generating the ideal
+      // => we can keep the underlying monomial order and get a Schreyer 
+      //    order without any bigger overhead
+      if (!strat->incremental)
+      {
+        p_ExpVectorAdd (h.sig,F->m[i],currRing);  
+      }
+      h.sevSig = pGetShortExpVector(h.sig);
+#ifdef DEBUGF5
+      pWrite(h.p);
+      pWrite(h.sig);
+#endif
+      if (h.p!=NULL)
+      {
+        if (currRing->OrdSgn==-1)
+        {
+          cancelunit(&h);  /*- tries to cancel a unit -*/
+          deleteHC(&h, strat);
+        }
+        if (h.p!=NULL)
+        {
+          if (TEST_OPT_INTSTRATEGY)
+          {
+            //pContent(h.p);
+            h.pCleardenom(); // also does a pContent
+          }
+          else
+          {
+            h.pNorm();
+          }
+          strat->initEcart(&h);
+          if (strat->Ll==-1)
+            pos =0;
+          else
+            pos = strat->posInLSba(strat->L,strat->Ll,&h,strat);
+          h.sev = pGetShortExpVector(h.p);
+          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
+        }
+      }
+      /*
+      if (!strat->incremental)
+      {
+        for(j=0;j<i;j++)
+        {
+          strat->syz[ctr] = pCopy(F->m[j]);
+          p_SetCompP(strat->syz[ctr],i+1,currRing);
+          // add LM(F->m[i]) to the signature to get a Schreyer order
+          // without changing the underlying polynomial ring at all
+          p_ExpVectorAdd (strat->syz[ctr],F->m[i],currRing);  
+          // since p_Add_q() destroys all input
+          // data we need to recreate help 
+          // each time
+          poly help = pCopy(F->m[i]);
+          p_SetCompP(help,j+1,currRing);
+          pWrite(strat->syz[ctr]);
+          pWrite(help);
+          printf("%d\n",pLmCmp(strat->syz[ctr],help));
+          strat->syz[ctr] = p_Add_q(strat->syz[ctr],help,currRing);
+          printf("%d. SYZ  ",ctr);
+          pWrite(strat->syz[ctr]);
+          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
+          ctr++;
+        }
+        strat->syzl = ps;
+      }
+      */
+    }
+  }
+  /*- test, if a unit is in F -*/
+
+  if ((strat->Ll>=0)
+#ifdef HAVE_RINGS
+       && n_IsUnit(pGetCoeff(strat->L[strat->Ll].p), currRing->cf)
+#endif
+       && pIsConstant(strat->L[strat->Ll].p))
+  {
+    while (strat->Ll>0) deleteInL(strat->L,&strat->Ll,strat->Ll-1,strat);
+  }
+}
+
+void initSyzRules (kStrategy strat)
+{
+  if( strat->S[0] )
+  {
+    if( strat->S[1] )
+    {
+      omFreeSize(strat->syzIdx,(strat->syzidxmax)*sizeof(int));
+      omFreeSize(strat->sevSyz,(strat->syzmax)*sizeof(unsigned long));
+      omFreeSize(strat->syz,(strat->syzmax)*sizeof(poly));
+    }
+    int i, j, k, diff, comp, comp_old, ps=0, ctr=0;
+    /************************************************************
+     * computing the length of the syzygy array needed
+     ***********************************************************/
+    for(i=1; i<=strat->sl; i++)
+    {
+      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
+      { 
+        ps += i;
+      }
+    }
+    ps += strat->sl+1;
+    //comp              = pGetComp (strat->P.sig);
+    comp              = strat->currIdx;
+    strat->syzIdx     = initec(comp);
+    strat->sevSyz     = initsevS(ps);
+    strat->syz        = (poly *)omAlloc(ps*sizeof(poly));
+    strat->syzl       = strat->syzmax = ps;
+    strat->syzidxmax  = comp;
+#ifdef DEBUGF5 || DEBUGF51
+    printf("------------- GENERATING SYZ RULES NEW ---------------\n");
+#endif
+    i = 1; 
+    j = 0;
+    /************************************************************
+     * generating the leading terms of the principal syzygies
+     ***********************************************************/
+    while (i <= strat->sl)
+    {
+      /**********************************************************
+       * principal syzygies start with component index 2
+       * the array syzIdx starts with index 0
+       * => the rules for a signature with component comp start
+       *    at strat->syz[strat->syzIdx[comp-2]] !
+       *********************************************************/
+      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
+      {
+        comp      = pGetComp(strat->sig[i]);
+        comp_old  = pGetComp(strat->sig[i-1]);
+        diff      = comp - comp_old - 1;
+        // diff should be zero, but sometimes also the initial generating
+        // elements of the input ideal reduce to zero. then there is an
+        // index-gap between the signatures. for these inbetween signatures we
+        // can safely set syzIdx[j] = 0 as no such element will be ever computed
+        // in the following.
+        // doing this, we keep the relation "j = comp - 2" alive, which makes
+        // jumps way easier when checking criteria
+        while (diff>0)
+        {
+          strat->syzIdx[j]  = 0;
+          diff--;
+          j++;
+        }
+        strat->syzIdx[j]  = ctr;
+        j++;
+        for (k = 0; k<i; k++)
+        {
+          poly p          = pOne();
+          pLcm(strat->S[k],strat->S[i],p);
+          strat->syz[ctr] = p;
+          p_SetCompP (strat->syz[ctr], comp, currRing);
+          poly q          = p_Copy(p, currRing);
+          q               = p_Neg (q, currRing);
+          p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
+          strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
+#ifdef DEBUGF5 || DEBUGF51
+          pWrite(strat->syz[ctr]);
+#endif
+          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
+          ctr++;
+        }
+      }
+      i++;
+    }
+    /**************************************************************
+    * add syzygies for upcoming first element of new iteration step
+    **************************************************************/
+    comp      = strat->currIdx;
+    comp_old  = pGetComp(strat->sig[i-1]);
+    diff      = comp - comp_old - 1;
+    // diff should be zero, but sometimes also the initial generating
+    // elements of the input ideal reduce to zero. then there is an
+    // index-gap between the signatures. for these inbetween signatures we
+    // can safely set syzIdx[j] = 0 as no such element will be ever computed
+    // in the following.
+    // doing this, we keep the relation "j = comp - 2" alive, which makes
+    // jumps way easier when checking criteria
+    while (diff>0)
+    {
+      strat->syzIdx[j]  = 0;
+      diff--;
+      j++;
+    }
+    strat->syzIdx[j]  = ctr;
+    for (k = 0; k<strat->sl+1; k++)
+    {
+      strat->syz[ctr] = p_Copy (pHead(strat->S[k]), currRing);
+      p_SetCompP (strat->syz[ctr], comp, currRing);
+      poly q          = p_Copy (pHead(strat->L[strat->Ll].p), currRing);
+      q               = p_Neg (q, currRing);
+      p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
+      strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
+//#if 1
+#if DEBUGF5 || DEBUGF51
+      printf("..");
+      pWrite(strat->syz[ctr]);
+#endif
+      strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
+      ctr++;
+    }
+//#if 1
+#ifdef DEBUGF5
+    Print("Principal syzygies:\n");
+    Print("--------------------------------\n");
+    for(i=0;i<=ps-1;i++)
+    {
+      pWrite(strat->syz[i]);
+    }
+    Print("--------------------------------\n");
+#endif
+
+  }
+}
+
+
 
 /*2
@@ -5037 +6083 @@
   strat->S=strat->Shdl->m;
 
+  /*- put polys into S -*/
+  if (Q!=NULL)
+  {
+    strat->fromQ=initec(i);
+    memset(strat->fromQ,0,i*sizeof(int));
+    for (i=0; i<IDELEMS(Q); i++)
+    {
+      if (Q->m[i]!=NULL)
+      {
+        LObject h;
+        h.p = pCopy(Q->m[i]);
+        //if (TEST_OPT_INTSTRATEGY)
+        //{
+        //  //pContent(h.p);
+        //  h.pCleardenom(); // also does a pContent
+        //}
+        //else
+        //{
+        //  h.pNorm();
+        //}
+        if (currRing->OrdSgn==-1)
+        {
+          deleteHC(&h,strat);
+        }
+        if (h.p!=NULL)
+        {
+          strat->initEcart(&h);
+          if (strat->sl==-1)
+            pos =0;
+          else
+          {
+            pos = posInS(strat,strat->sl,h.p,h.ecart);
+          }
+          h.sev = pGetShortExpVector(h.p);
+          strat->enterS(h,pos,strat, strat->tl+1);
+          enterT(h, strat);
+          strat->fromQ[pos]=1;
+        }
+      }
+    }
+  }
+  /*- put polys into S -*/
+  for (i=0; i<IDELEMS(F); i++)
+  {
+    if (F->m[i]!=NULL)
+    {
+      LObject h;
+      h.p = pCopy(F->m[i]);
+      if (currRing->OrdSgn==-1)
+      {
+        deleteHC(&h,strat);
+      }
+      else
+      {
+        h.p=redtailBba(h.p,strat->sl,strat);
+      }
+      if (h.p!=NULL)
+      {
+        strat->initEcart(&h);
+        if (strat->sl==-1)
+          pos =0;
+        else
+          pos = posInS(strat,strat->sl,h.p,h.ecart);
+        h.sev = pGetShortExpVector(h.p);
+        strat->enterS(h,pos,strat, strat->tl+1);
+        enterT(h,strat);
+      }
+    }
+  }
+  for (i=0; i<IDELEMS(P); i++)
+  {
+    if (P->m[i]!=NULL)
+    {
+      LObject h;
+      h.p=pCopy(P->m[i]);
+      if (TEST_OPT_INTSTRATEGY)
+      {
+        h.pCleardenom();
+      }
+      else
+      {
+        h.pNorm();
+      }
+      if(strat->sl>=0)
+      {
+        if (currRing->OrdSgn==1)
+        {
+          h.p=redBba(h.p,strat->sl,strat);
+          if (h.p!=NULL)
+          {
+            h.p=redtailBba(h.p,strat->sl,strat);
+          }
+        }
+        else
+        {
+          h.p=redMora(h.p,strat->sl,strat);
+        }
+        if(h.p!=NULL)
+        {
+          strat->initEcart(&h);
+          if (TEST_OPT_INTSTRATEGY)
+          {
+            h.pCleardenom();
+          }
+          else
+          {
+            h.is_normalized = 0;
+            h.pNorm();
+          }
+          h.sev = pGetShortExpVector(h.p);
+          h.SetpFDeg();
+          pos = posInS(strat,strat->sl,h.p,h.ecart);
+          enterpairsSpecial(h.p,strat->sl,h.ecart,pos,strat,strat->tl+1);
+          strat->enterS(h,pos,strat, strat->tl+1);
+          enterT(h,strat);
+        }
+      }
+      else
+      {
+        h.sev = pGetShortExpVector(h.p);
+        strat->initEcart(&h);
+        strat->enterS(h,0,strat, strat->tl+1);
+        enterT(h,strat);
+      }
+    }
+  }
+}
+/*2
+*construct the set s from F and {P}
+*/
+
+void initSSpecialSba (ideal F, ideal Q, ideal P,kStrategy strat)
+{
+  int   i,pos;
+
+  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
+  else i=setmaxT;
+  i=((i+IDELEMS(F)+IDELEMS(P)+15)/16)*16;
+  strat->fromS=initec(i);
+  strat->sevS=initsevS(i);
+  strat->sevSig=initsevS(i);
+  strat->S_2_R=initS_2_R(i);
+  strat->fromQ=NULL;
+  strat->Shdl=idInit(i,F->rank);
+  strat->S=strat->Shdl->m;
+  strat->sig=(poly *)omAlloc0(i*sizeof(poly));
   /*- put polys into S -*/
   if (Q!=NULL)
@@ -5665 +6857 @@
 
 /*2
+* -puts p to the standardbasis s at position at
+* -saves the result in S
+*/
+void enterSSba (LObject p,int atS,kStrategy strat, int atR)
+{
+  int i;
+  strat->news = TRUE;
+  /*- puts p to the standardbasis s at position at -*/
+  if (strat->sl == IDELEMS(strat->Shdl)-1)
+  {
+    strat->sevS = (unsigned long*) omRealloc0Size(strat->sevS,
+                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
+                                    (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(unsigned long));
+    strat->sevSig = (unsigned long*) omRealloc0Size(strat->sevSig,
+                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
+                                    (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(unsigned long));
+    strat->ecartS = (intset)omReallocSize(strat->ecartS,
+                                          IDELEMS(strat->Shdl)*sizeof(int),
+                                          (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(int));
+    strat->fromS = (intset)omReallocSize(strat->fromS,
+                                          IDELEMS(strat->Shdl)*sizeof(int),
+                                          (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(int));
+    strat->S_2_R = (int*) omRealloc0Size(strat->S_2_R,
+                                         IDELEMS(strat->Shdl)*sizeof(int),
+                                         (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(int));
+    if (strat->lenS!=NULL)
+      strat->lenS=(int*)omRealloc0Size(strat->lenS,
+                                       IDELEMS(strat->Shdl)*sizeof(int),
+                                       (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                 *sizeof(int));
+    if (strat->lenSw!=NULL)
+      strat->lenSw=(wlen_type*)omRealloc0Size(strat->lenSw,
+                                       IDELEMS(strat->Shdl)*sizeof(wlen_type),
+                                       (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                 *sizeof(wlen_type));
+    if (strat->fromQ!=NULL)
+    {
+      strat->fromQ = (intset)omReallocSize(strat->fromQ,
+                                    IDELEMS(strat->Shdl)*sizeof(int),
+                                    (IDELEMS(strat->Shdl)+setmaxTinc)*sizeof(int));
+    }
+    pEnlargeSet(&strat->S,IDELEMS(strat->Shdl),setmaxTinc);
+    pEnlargeSet(&strat->sig,IDELEMS(strat->Shdl),setmaxTinc);
+    IDELEMS(strat->Shdl)+=setmaxTinc;
+    strat->Shdl->m=strat->S;
+  }
+  // in a signature-based algorithm the following situation will never
+  // appear due to the fact that the critical pairs are already sorted
+  // by increasing signature.
+  if (atS <= strat->sl)
+  {
+#ifdef ENTER_USE_MEMMOVE
+// #if 0
+    memmove(&(strat->S[atS+1]), &(strat->S[atS]),
+            (strat->sl - atS + 1)*sizeof(poly));
+    memmove(&(strat->ecartS[atS+1]), &(strat->ecartS[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    memmove(&(strat->fromS[atS+1]), &(strat->fromS[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    memmove(&(strat->sevS[atS+1]), &(strat->sevS[atS]),
+            (strat->sl - atS + 1)*sizeof(unsigned long));
+    memmove(&(strat->S_2_R[atS+1]), &(strat->S_2_R[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    if (strat->lenS!=NULL)
+    memmove(&(strat->lenS[atS+1]), &(strat->lenS[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    if (strat->lenSw!=NULL)
+    memmove(&(strat->lenSw[atS+1]), &(strat->lenSw[atS]),
+            (strat->sl - atS + 1)*sizeof(wlen_type));
+#else
+    for (i=strat->sl+1; i>=atS+1; i--)
+    {
+      strat->S[i] = strat->S[i-1];
+      strat->ecartS[i] = strat->ecartS[i-1];
+      strat->fromS[i] = strat->fromS[i-1];
+      strat->sevS[i] = strat->sevS[i-1];
+      strat->S_2_R[i] = strat->S_2_R[i-1];
+    }
+    if (strat->lenS!=NULL)
+    for (i=strat->sl+1; i>=atS+1; i--)
+      strat->lenS[i] = strat->lenS[i-1];
+    if (strat->lenSw!=NULL)
+    for (i=strat->sl+1; i>=atS+1; i--)
+      strat->lenSw[i] = strat->lenSw[i-1];
+#endif
+  }
+  if (strat->fromQ!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->fromQ[atS+1]), &(strat->fromQ[atS]),
+                  (strat->sl - atS + 1)*sizeof(int));
+#else
+    for (i=strat->sl+1; i>=atS+1; i--)
+    {
+      strat->fromQ[i] = strat->fromQ[i-1];
+    }
+#endif
+    strat->fromQ[atS]=0;
+  }
+
+  /*- save result -*/
+  strat->S[atS] = p.p;
+  strat->sig[atS] = p.sig; // TODO: get ths correct signature in here!
+  if (strat->honey) strat->ecartS[atS] = p.ecart;
+  if (p.sev == 0)
+    p.sev = pGetShortExpVector(p.p);
+  else
+    assume(p.sev == pGetShortExpVector(p.p));
+  strat->sevS[atS] = p.sev;
+  // during the interreduction process of a signature-based algorithm we do not
+  // compute the signature at this point, but when the whole interreduction
+  // process finishes, i.e. f5c terminates!
+  if (p.sig != NULL)
+  {
+    if (p.sevSig == 0)
+      p.sevSig = pGetShortExpVector(p.sig);
+    else
+      assume(p.sevSig == pGetShortExpVector(p.sig));
+    strat->sevSig[atS] = p.sevSig; // TODO: get the correct signature in here!
+  }
+  strat->ecartS[atS] = p.ecart;
+  strat->fromS[atS] = p.from;
+  strat->S_2_R[atS] = atR;
+  strat->sl++;
+#ifdef DEBUGF5
+  int k;
+  Print("--- LIST S: %d ---\n",strat->sl);
+  for(k=0;k<=strat->sl;k++)
+  {
+    pWrite(strat->sig[k]);
+  }
+  Print("--- LIST S END ---\n");
+#endif
+}
+
+/*2
 * puts p to the set T at position atT
 */
@@ -5735 +7068 @@
   kTest_T(&(strat->T[atT]));
 }
+
+/*2
+* puts signature p.sig to the set syz
+*/
+void enterSyz(LObject p, kStrategy strat)
+{
+  int i = strat->syzl;
+
+  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;
+  }
+  strat->syz[i] = p.sig;
+  strat->sevSyz[i] = p.sevSig;
+  strat->syzl++;
+#ifdef DEBUGF5
+  Print("last element in strat->syz: %d--%d  ",i+1,strat->syzmax);
+  pWrite(strat->syz[i]);
+#endif
+  // recheck pairs in strat->L with new rule and delete correspondingly
+  int cc = strat->Ll;
+  while (cc>-1)
+  {
+    if (p_LmShortDivisibleBy( strat->syz[strat->syzl-1], strat->sevSyz[strat->syzl-1], 
+                              strat->L[cc].sig, ~strat->L[cc].sevSig, currRing))
+    {
+      deleteInL(strat->L,&strat->Ll,cc,strat);
+    }
+    cc--;
+  }
+
+}
+
 
 void initHilbCrit(ideal/*F*/, ideal /*Q*/, intvec **hilb,kStrategy strat)
@@ -5771 +7143 @@
   * - in local rings, - in lex order case, -in ring over extensions */
   strat->noTailReduction = !TEST_OPT_REDTAIL;
+
+#ifdef HAVE_PLURAL
+  // and r is plural_ring
+  //  hence this holds for r a rational_plural_ring
+  if( rIsPluralRing(currRing) || (rIsSCA(currRing) && !strat->z2homog) )
+  {    //or it has non-quasi-comm type... later
+    strat->sugarCrit = FALSE;
+    strat->Gebauer = FALSE;
+    strat->honey = FALSE;
+  }
+#endif
+
+#ifdef HAVE_RINGS
+  // Coefficient ring?
+  if (rField_is_Ring(currRing))
+  {
+    strat->sugarCrit = FALSE;
+    strat->Gebauer = FALSE ;
+    strat->honey = FALSE;
+  }
+#endif
+  #ifdef KDEBUG
+  if (TEST_OPT_DEBUG)
+  {
+    if (strat->homog) PrintS("ideal/module is homogeneous\n");
+    else              PrintS("ideal/module is not homogeneous\n");
+  }
+  #endif
+}
+
+void initSbaCrit(kStrategy strat)
+{
+  //strat->enterOnePair=enterOnePairNormal;
+  strat->enterOnePair = enterOnePairNormal;
+  //strat->chainCrit=chainCritNormal;
+  strat->chainCrit    = chainCritSig;
+  /******************************************
+   * rewCrit1 and rewCrit2 are already set in
+   * kSba() in kstd1.cc
+   *****************************************/
+  //strat->rewCrit1     = faugereRewCriterion;
+  if (strat->incremental)
+  {
+    strat->syzCrit  = syzCriterionInc;
+  }
+  else
+  {
+    strat->syzCrit  = syzCriterion;
+  }
+#ifdef HAVE_RINGS
+  if (rField_is_Ring(currRing))
+  {
+    strat->enterOnePair=enterOnePairRing;
+    strat->chainCrit=chainCritRing;
+  }
+#endif
+#ifdef HAVE_RATGRING
+  if (rIsRatGRing(currRing))
+  {
+     strat->chainCrit=chainCritPart;
+     /* enterOnePairNormal get rational part in it */
+  }
+#endif
+
+  strat->sugarCrit =        TEST_OPT_SUGARCRIT;
+  strat->Gebauer =          strat->homog || strat->sugarCrit;
+  strat->honey =            !strat->homog || strat->sugarCrit || TEST_OPT_WEIGHTM;
+  if (TEST_OPT_NOT_SUGAR) strat->honey = FALSE;
+  strat->pairtest = NULL;
+  /* alway use tailreduction, except:
+  * - in local rings, - in lex order case, -in ring over extensions */
+  strat->noTailReduction = !TEST_OPT_REDTAIL;
+  //strat->noTailReduction = NULL;
 
 #ifdef HAVE_PLURAL
@@ -5987 +7432 @@
 }
 
+void initSbaPos (kStrategy strat)
+{
+  if (currRing->OrdSgn==1)
+  {
+    if (strat->honey)
+    {
+      strat->posInL = posInL15;
+      // ok -- here is the deal: from my experiments for Singular-2-0
+      // I conclude that that posInT_EcartpLength is the best of
+      // posInT15, posInT_EcartFDegpLength, posInT_FDegLength, posInT_pLength
+      // see the table at the end of this file
+      if (TEST_OPT_OLDSTD)
+        strat->posInT = posInT15;
+      else
+        strat->posInT = posInT_EcartpLength;
+    }
+    else if (currRing->pLexOrder && !TEST_OPT_INTSTRATEGY)
+    {
+      strat->posInL = posInL11;
+      strat->posInT = posInT11;
+    }
+    else if (TEST_OPT_INTSTRATEGY)
+    {
+      strat->posInL = posInL11;
+      strat->posInT = posInT11;
+    }
+    else
+    {
+      strat->posInL = posInL0;
+      strat->posInT = posInT0;
+    }
+    //if (strat->minim>0) strat->posInL =posInLSpecial;
+    if (strat->homog)
+    {
+       strat->posInL = posInL110;
+       strat->posInT = posInT110;
+    }
+  }
+  else
+  {
+    if (strat->homog)
+    {
+      strat->posInL = posInL11;
+      strat->posInT = posInT11;
+    }
+    else
+    {
+      if ((currRing->order[0]==ringorder_c)
+      ||(currRing->order[0]==ringorder_C))
+      {
+        strat->posInL = posInL17_c;
+        strat->posInT = posInT17_c;
+      }
+      else
+      {
+        strat->posInL = posInL17;
+        strat->posInT = posInT17;
+      }
+    }
+  }
+  if (strat->minim>0) strat->posInL =posInLSpecial;
+  // for further tests only
+  if ((BTEST1(11)) || (BTEST1(12)))
+    strat->posInL = posInL11;
+  else if ((BTEST1(13)) || (BTEST1(14)))
+    strat->posInL = posInL13;
+  else if ((BTEST1(15)) || (BTEST1(16)))
+    strat->posInL = posInL15;
+  else if ((BTEST1(17)) || (BTEST1(18)))
+    strat->posInL = posInL17;
+  if (BTEST1(11))
+    strat->posInT = posInT11;
+  else if (BTEST1(13))
+    strat->posInT = posInT13;
+  else if (BTEST1(15))
+    strat->posInT = posInT15;
+  else if ((BTEST1(17)))
+    strat->posInT = posInT17;
+  else if ((BTEST1(19)))
+    strat->posInT = posInT19;
+  else if (BTEST1(12) || BTEST1(14) || BTEST1(16) || BTEST1(18))
+    strat->posInT = posInT1;
+#ifdef HAVE_RINGS
+  if (rField_is_Ring(currRing))
+  {
+    strat->posInL = posInL11;
+    strat->posInT = posInT11;
+  }
+#endif
+  strat->posInLDependsOnLength = FALSE;
+  strat->posInLSba  = posInLSig;
+  //strat->posInL     = posInLSig;
+  strat->posInL     = posInLF5C;
+  //strat->posInT     = posInTSig;
+}
+
+void initSbaBuchMora (ideal F,ideal Q,kStrategy strat)
+{
+  strat->interpt = BTEST1(OPT_INTERRUPT);
+  strat->kHEdge=NULL;
+  if (currRing->OrdSgn==1) strat->kHEdgeFound=FALSE;
+  /*- creating temp data structures------------------- -*/
+  strat->cp = 0;
+  strat->c3 = 0;
+  strat->tail = pInit();
+  /*- set s -*/
+  strat->sl = -1;
+  /*- set ps -*/
+  strat->syzl = -1;
+  /*- set L -*/
+  strat->Lmax = ((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
+  strat->Ll = -1;
+  strat->L = initL(((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc);
+  /*- 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 (currRing->OrdSgn==-1)
+  {
+    if (strat->kHEdge!=NULL) pSetComp(strat->kHEdge, strat->ak);
+    if (strat->kNoether!=NULL) pSetComp(strat->kNoetherTail(), strat->ak);
+  }
+  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;
+    }
+    initSSpecialSba(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=*/initSLSba(F, Q,strat); /*sets also S, ecartS, fromQ */
+    // /*Shdl=*/initS(F, Q,strat); /*sets also S, ecartS, fromQ */
+  }
+  strat->fromT = FALSE;
+  strat->noTailReduction = !TEST_OPT_REDTAIL;
+  if (!TEST_OPT_SB_1)
+  {
+    updateS(TRUE,strat);
+  }
+  if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
+  strat->fromQ=NULL;
+}
+
+void exitSba (kStrategy strat)
+{
+  /*- release temp data -*/
+  cleanT(strat);
+  omFreeSize(strat->T,(strat->tmax)*sizeof(TObject));
+  omFreeSize(strat->R,(strat->tmax)*sizeof(TObject*));
+  omFreeSize(strat->sevT, (strat->tmax)*sizeof(unsigned long));
+  omFreeSize(strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
+  omFreeSize(strat->fromS,IDELEMS(strat->Shdl)*sizeof(int));
+  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
+  omFreeSize((ADDRESS)strat->sevSig,IDELEMS(strat->Shdl)*sizeof(unsigned long));
+  omFreeSize((ADDRESS)strat->syz,(strat->syzmax)*sizeof(poly));
+  omFreeSize((ADDRESS)strat->sevSyz,(strat->syzmax)*sizeof(unsigned long));
+  if (strat->incremental)
+  {
+    omFreeSize(strat->syzIdx,(strat->syzidxmax)*sizeof(int));
+  }
+  omFreeSize(strat->S_2_R,IDELEMS(strat->Shdl)*sizeof(int));
+  /*- set L: should be empty -*/
+  omFreeSize(strat->L,(strat->Lmax)*sizeof(LObject));
+  /*- set B: should be empty -*/
+  omFreeSize(strat->B,(strat->Bmax)*sizeof(LObject));
+  /*- set sig: no need for the signatures anymore -*/
+  omFreeSize(strat->sig,IDELEMS(strat->Shdl)*sizeof(poly));
+  pLmDelete(&strat->tail);
+  strat->syzComp=0;
+}
+
 /*2
 * in the case of a standardbase of a module over a qring:
@@ -6453 +8089 @@
 
   kStratChangeTailRing(strat, NULL, NULL, e);
+}
+
+ring sbaRing (kStrategy strat, const ring r, BOOLEAN complete, int sgn)
+{
+  int n = rBlocks(r); // Including trailing zero!
+  // if incremental => use (C,monomial order from r)
+  if (strat->incremental)
+  {
+    if (r->order[0] == ringorder_C || r->order[0] == ringorder_c)
+    {
+      return r;
+    }
+      ring res = rCopy0(r, FALSE, TRUE);
+      for (int i=1; i<n-1; i++)
+      {
+        res->order[i] = res->order[i-1];
+        res->block0[i] = res->block0[i-1];
+        res->block1[i] = res->block1[i-1];
+        res->wvhdl[i] = res->wvhdl[i-1];
+      }
+
+    // new 1st block
+    res->order[0]   = ringorder_C; // Prefix
+    res->block0[0]  = 1;
+    res->block1[0]  = res->N;
+    //res->wvhdl[j]   = NULL;
+    // res->order [j] = 0; // The End!
+    rComplete(res, 1);
+#ifdef HAVE_PLURAL
+    if (rIsPluralRing(r))
+    {
+      if ( nc_rComplete(r, res, false) ) // no qideal!
+      {
+#ifndef NDEBUG
+        WarnS("error in nc_rComplete");
+#endif
+        // cleanup?
+
+        //      rDelete(res);
+        //      return r;
+
+        // just go on..
+      }
+    }
+#endif
+  strat->tailRing = res;
+  return (res);
+  }
+  // not incremental => use Schreyer order
+  // this is done by a trick when initializing the signatures
+  // in initSLSba():
+  // Instead of using the signature 1e_i for F->m[i], we start
+  // with the signature LM(F->m[i])e_i for F->m[i]. Doing this we get a 
+  // Schreyer order w.r.t. the underlying monomial order.
+  // => we do not need to change the underlying polynomial ring at all!
+
+
+  /*
+  else
+  {
+    ring res = rCopy0(r, FALSE, FALSE);
+    // Create 2 more blocks for prefix/suffix:
+    res->order=(int *)omAlloc0((n+2)*sizeof(int)); // 0  ..  n+1
+    res->block0=(int *)omAlloc0((n+2)*sizeof(int));
+    res->block1=(int *)omAlloc0((n+2)*sizeof(int));
+    int ** wvhdl =(int **)omAlloc0((n+2)*sizeof(int**));
+
+    // Encapsulate all existing blocks between induced Schreyer ordering markers: prefix and suffix!
+    // Note that prefix and suffix have the same ringorder marker and only differ in block[] parameters!
+
+    // new 1st block
+    int j = 0;
+    res->order[j] = ringorder_IS; // Prefix
+    res->block0[j] = res->block1[j] = 0;
+    // wvhdl[j] = NULL;
+    j++;
+
+    for(int i = 0; (i < n) && (r->order[i] != 0); i++, j++) // i = [0 .. n-1] <- non-zero old blocks
+    {
+      res->order [j] = r->order [i];
+      res->block0[j] = r->block0[i];
+      res->block1[j] = r->block1[i];
+
+      if (r->wvhdl[i] != NULL)
+      {
+        wvhdl[j] = (int*) omMemDup(r->wvhdl[i]);
+      } // else wvhdl[j] = NULL;
+    }
+
+    // new last block
+    res->order [j] = ringorder_IS; // Suffix
+    res->block0[j] = res->block1[j] = sgn; // Sign of v[o]: 1 for C, -1 for c
+    // wvhdl[j] = NULL;
+    j++;
+
+    // res->order [j] = 0; // The End!
+    res->wvhdl = wvhdl;
+
+    // j == the last zero block now!
+    assume(j == (n+1));
+    assume(res->order[0]==ringorder_IS);
+    assume(res->order[j-1]==ringorder_IS);
+    assume(res->order[j]==0);
+
+    if (complete)
+    {
+      rComplete(res, 1);
+
+#ifdef HAVE_PLURAL
+      if (rIsPluralRing(r))
+      {
+        if ( nc_rComplete(r, res, false) ) // no qideal!
+        {
+        }
+      }
+      assume(rIsPluralRing(r) == rIsPluralRing(res));
+#endif
+
+
+#ifdef HAVE_PLURAL
+      ring old_ring = r;
+
+#endif
+
+      if (r->qideal!=NULL)
+      {
+        res->qideal= idrCopyR_NoSort(r->qideal, r, res);
+
+        assume(idRankFreeModule(res->qideal, res) == 0);
+
+#ifdef HAVE_PLURAL
+        if( rIsPluralRing(res) )
+          if( nc_SetupQuotient(res, r, true) )
+          {
+            //          WarnS("error in nc_SetupQuotient"); // cleanup?      rDelete(res);       return r;  // just go on...?
+          }
+
+#endif
+        assume(idRankFreeModule(res->qideal, res) == 0);
+      }
+
+#ifdef HAVE_PLURAL
+      assume((res->qideal==NULL) == (old_ring->qideal==NULL));
+      assume(rIsPluralRing(res) == rIsPluralRing(old_ring));
+      assume(rIsSCA(res) == rIsSCA(old_ring));
+      assume(ncRingType(res) == ncRingType(old_ring));
+#endif
+    }
+    strat->tailRing = res;
+    return res;
+  }
+  */
 }
 

kernel/kutil.h

@@ -67 +67 @@
 {
 public:
+  unsigned long sevSig;
+  poly sig;   // the signature of the element
   poly p;       // Lm(p) \in currRing Tail(p) \in tailRing
   poly t_p;     // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
@@ -77 +79 @@
     i_r;        // index of TObject in R set, or -1 if not in T
   BOOLEAN is_normalized; // true, if pNorm was called on p, false otherwise
+  // used in incremental sba() with F5C:
+  // we know some of the redundant elements in 
+  // strat->T beforehand, so we can just discard
+  // them and do not need to consider them in the
+  // interreduction process
+  BOOLEAN is_redundant;
+  // used in sba's sig-safe reduction:
+  // sometimes we already know that a reducer
+  // is sig-safe, so no need for a real
+  // sig-safeness check
+  BOOLEAN is_sigsafe;
+
 
 #ifdef HAVE_PLURAL  
@@ -167 +181 @@
 public:
   unsigned long sev;
+  unsigned long from; // from which polynomial it comes from
+            // this is important for signature-based
+            // algorithms
+  unsigned long checked; // this is the index of S up to which
+                      // the corresponding LObject was already checked in
+                      // critical pair creation => when entering the
+                      // reduction process it is enough to start a second
+                      // rewritten criterion check from checked+1 onwards
   poly  p1,p2; /*- the pair p comes from,
                  lm(pi) in currRing, tail(pi) in tailring -*/
@@ -252 +274 @@
   kStrategy next;
   int (*red)(LObject * L,kStrategy strat);
+  int (*red2)(LObject * L,kStrategy strat);
   void (*initEcart)(LObject * L);
   int (*posInT)(const TSet T,const int tl,LObject &h);
+  int (*posInLSba)(const LSet set, const int length,
+                LObject* L,const kStrategy strat);
   int (*posInL)(const LSet set, const int length,
                 LObject* L,const kStrategy strat);
@@ -262 +287 @@
   void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
   void (*chainCrit) (poly p,int ecart,kStrategy strat);
+  BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
+  BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
+  BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
   pFDegProc pOrigFDeg;
   pLDegProc pOrigLDeg;
@@ -272 +300 @@
   ideal M; /*set of minimal generators*/
   polyset S;
+  polyset syz;
+  polyset sig;
   intset ecartS;
+  intset fromS; // from which S[i] S[j] comes from
+                // this is important for signature-based
+                // algorithms
+  intset syzIdx;// index in the syz array at which the first
+                // syzygy of component i comes up
+                // important for signature-based algorithms
+  BOOLEAN incremental;
+  unsigned long currIdx;
+  int max_lower_index;
   intset lenS;
   wlen_set lenSw; /* for tgb.ccc */
   intset fromQ;
   unsigned long* sevS;
+  unsigned long* sevSyz;
+  unsigned long* sevSig;
   unsigned long* sevT;
   TSet T;
@@ -306 +347 @@
   int cv; // in shift bases: counting V criterion
   int sl,mu;
+  int syzl,syzmax,syzidxmax;
   int tl,tmax;
   int Ll,Lmax;
@@ -367 +409 @@
 void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
 void deleteInS (int i,kStrategy strat);
+void deleteInSSba (int i,kStrategy strat);
 void cleanT (kStrategy strat);
 static inline LSet initL (int nr=setmaxL)
@@ -373 +416 @@
 void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
 void enterSBba (LObject p,int atS,kStrategy strat, int atR = -1);
+void enterSSba (LObject p,int atS,kStrategy strat, int atR = -1);
 void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
 void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
@@ -381 +425 @@
 int posInT2 (const TSet set,const int length,LObject &p);
 int posInT11 (const TSet set,const int length,LObject &p);
+int posInTSig (const TSet set,const int length,LObject &p);
 int posInT110 (const TSet set,const int length,LObject &p);
 int posInT13 (const TSet set,const int length,LObject &p);
@@ -396 +441 @@
 
 void reorderS (int* suc,kStrategy strat);
+int posInLF5C (const LSet set, const int length,
+               LObject* L,const kStrategy strat);
+int posInLSig (const LSet set, const int length,
+               LObject* L,const kStrategy strat);
 int posInL0 (const LSet set, const int length,
              LObject* L,const kStrategy strat);
@@ -437 +486 @@
 int redLazy (LObject* h,kStrategy strat);
 int redHomog (LObject* h,kStrategy strat);
+int redSig (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);
 void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
 void entersets (LObject h);
@@ -452 +504 @@
 void initS (ideal F, ideal Q,kStrategy strat);
 void initSL (ideal F, ideal Q,kStrategy strat);
+void initSLSba (ideal F, ideal Q,kStrategy strat);
+/*************************************************
+ * when initializing a new bunch of principal 
+ * syzygies at the beginning of a new iteration
+ * step in a signature-based algorithm we 
+ * compute ONLY the leading elements of those
+ * syzygies, NOT the whole syzygy
+ * NOTE: this needs to be adjusted for a more
+ * general approach on signature-based algorithms
+ ***********************************************/
+void initSyzRules (kStrategy strat);
 void updateS(BOOLEAN toT,kStrategy strat);
+void enterSyz (LObject p,kStrategy strat);
 void enterT (LObject p,kStrategy strat, int atT = -1);
 void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
 void HEckeTest (poly pp,kStrategy strat);
 void initBuchMoraCrit(kStrategy strat);
+void initSbaCrit(kStrategy strat);
 void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
 void initBuchMoraPos(kStrategy strat);
+void initSbaPos(kStrategy strat);
 void initBuchMora (ideal F, ideal Q,kStrategy strat);
+void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
 void exitBuchMora (kStrategy strat);
+void exitSba (kStrategy strat);
 void updateResult(ideal r,ideal Q,kStrategy strat);
 void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
 void kFreeStrat(kStrategy strat);
 void enterOnePairNormal (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 chainCritNormal (poly p,int ecart,kStrategy strat);
+void chainCritSig (poly p,int ecart,kStrategy strat);
 BOOLEAN homogTest(polyset F, int Fmax);
 BOOLEAN newHEdge(kStrategy strat);
+BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
+BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
+KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
+BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
+BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
+BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
 // returns index of p in TSet, or -1 if not found
 int kFindInT(poly p, TSet T, int tlength);
@@ -541 +617 @@
 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
+ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
 poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
 ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
 void initBba(ideal F,kStrategy strat);
+void initSba(ideal F,kStrategy strat);
+void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg, 
+          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
+          intvec *w,intvec *hilb );
 
 /***************************************************************
@@ -569 +650 @@
                  kStrategy strat = NULL);
 
+// Reduces PR with PW
+// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
+// Changes: PR
+// Const:   PW
+// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
+// If strat != NULL, tailRing is changed if reduction would violate exp bound
+// of tailRing
+// Returns: 0 everything ok, no tailRing change
+//          1 tailRing has successfully changed (strat != NULL)
+//          2 no reduction performed, tailRing needs to be changed first
+//            (strat == NULL)
+//          3 no reduction performed, not sig-safe!!!
+//         -1 tailRing change could not be performed due to exceeding exp
+//            bound of currRing
+int ksReducePolySig(LObject* PR,
+                 TObject* PW,
+                 long idx,
+                 poly spNoether = NULL,
+                 number *coef = NULL,
+                 kStrategy strat = NULL);
+
 // Reduces PR at Current->next with PW
 // Assumes PR != NULL, Current contained in PR
@@ -638 +740 @@
 void kDebugPrint(kStrategy strat);
 
+// getting sb order for sba computations
+ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
 
 KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,