Changeset 9e806f in git


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

Signature-based algorithms in spielwiese
Files:
12 added
13 edited

Legend:

Unmodified
Added
Removed
  • Singular/grammar.cc

    rcffd3e r9e806f  
    396396     PARAMETER = 381,
    397397     SYSVAR = 382,
    398      UMINUS = 383
     398     UMINUS = 383,
     399     SBA_CMD = 384
    399400   };
    400401#endif
  • Singular/grammar.h

    rcffd3e r9e806f  
    164164     PARAMETER = 381,
    165165     SYSVAR = 382,
    166      UMINUS = 383
     166     UMINUS = 383,
     167     SBA_CMD = 384
    167168   };
    168169#endif
  • Singular/grammar.y

    rcffd3e r9e806f  
    262262%token <i> REGULARITY_CMD
    263263%token <i> RES_CMD
     264%token <i> SBA_CMD
    264265%token <i> SIMPLIFY_CMD
    265266%token <i> SORTVEC_CMD
  • Singular/iparith.cc

    rcffd3e r9e806f  
    47834783  //res->data=(char *)t_rep_gb(currRing, u_id);
    47844784
     4785  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
     4786  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
     4787  return FALSE;
     4788}
     4789static BOOLEAN jjSBA(leftv res, leftv v)
     4790{
     4791  ideal result;
     4792  ideal v_id=(ideal)v->Data();
     4793  intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD);
     4794  tHomog hom=testHomog;
     4795  if (w!=NULL)
     4796  {
     4797    if (!idTestHomModule(v_id,currQuotient,w))
     4798    {
     4799      WarnS("wrong weights");
     4800      w=NULL;
     4801    }
     4802    else
     4803    {
     4804      hom=isHomog;
     4805      w=ivCopy(w);
     4806    }
     4807  }
     4808  result=kSba(v_id,currQuotient,hom,&w,1,0);
     4809  idSkipZeroes(result);
     4810  res->data = (char *)result;
     4811  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
     4812  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
     4813  return FALSE;
     4814}
     4815static BOOLEAN jjSBA_1(leftv res, leftv v, leftv u)
     4816{
     4817  ideal result;
     4818  ideal v_id=(ideal)v->Data();
     4819  intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD);
     4820  tHomog hom=testHomog;
     4821  if (w!=NULL)
     4822  {
     4823    if (!idTestHomModule(v_id,currQuotient,w))
     4824    {
     4825      WarnS("wrong weights");
     4826      w=NULL;
     4827    }
     4828    else
     4829    {
     4830      hom=isHomog;
     4831      w=ivCopy(w);
     4832    }
     4833  }
     4834  result=kSba(v_id,currQuotient,hom,&w,(int)(long)u->Data(),0);
     4835  idSkipZeroes(result);
     4836  res->data = (char *)result;
     4837  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
     4838  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
     4839  return FALSE;
     4840}
     4841static BOOLEAN jjSBA_2(leftv res, leftv v, leftv u, leftv t)
     4842{
     4843  ideal result;
     4844  ideal v_id=(ideal)v->Data();
     4845  intvec *w=(intvec *)atGet(v,"isHomog",INTVEC_CMD);
     4846  tHomog hom=testHomog;
     4847  if (w!=NULL)
     4848  {
     4849    if (!idTestHomModule(v_id,currQuotient,w))
     4850    {
     4851      WarnS("wrong weights");
     4852      w=NULL;
     4853    }
     4854    else
     4855    {
     4856      hom=isHomog;
     4857      w=ivCopy(w);
     4858    }
     4859  }
     4860  result=kSba(v_id,currQuotient,hom,&w,(int)(long)u->Data(),(int)(long)t->Data());
     4861  idSkipZeroes(result);
     4862  res->data = (char *)result;
    47854863  if(!TEST_OPT_DEGBOUND) setFlag(res,FLAG_STD);
    47864864  if (w!=NULL) atSet(res,omStrDup("isHomog"),w,INTVEC_CMD);
  • Singular/table.h

    rcffd3e r9e806f  
    238238,{D(jjROWS_BIM),   ROWS_CMD,        INT_CMD,        BIGINTMAT_CMD , ALLOW_PLURAL |ALLOW_RING}
    239239,{D(jjCOUNT_IV),   ROWS_CMD,        INT_CMD,        INTVEC_CMD    , ALLOW_PLURAL |ALLOW_RING}
     240,{D(jjSBA),        SBA_CMD,         IDEAL_CMD,      IDEAL_CMD     , ALLOW_PLURAL |ALLOW_RING}
     241,{D(jjSBA),        SBA_CMD,         MODUL_CMD,      MODUL_CMD     , ALLOW_PLURAL |ALLOW_RING}
    240242,{D(jjSLIM_GB),    SLIM_GB_CMD,     IDEAL_CMD,      IDEAL_CMD     , ALLOW_PLURAL }
    241243,{D(jjSLIM_GB),    SLIM_GB_CMD,     MODUL_CMD,      MODUL_CMD     , ALLOW_PLURAL }
     
    662664,{D(jjRES),       SRES_CMD,       RESOLUTION_CMD, IDEAL_CMD,  INT_CMD, NO_PLURAL |ALLOW_RING}
    663665,{D(jjRES),       SRES_CMD,       RESOLUTION_CMD, MODUL_CMD,  INT_CMD, NO_PLURAL |ALLOW_RING}
     666,{D(jjSBA_1),     SBA_CMD,        IDEAL_CMD,      IDEAL_CMD,  INT_CMD, ALLOW_PLURAL |ALLOW_RING}
     667,{D(jjSBA_1),     SBA_CMD,        MODUL_CMD,      MODUL_CMD,  INT_CMD, ALLOW_PLURAL |ALLOW_RING}
    664668,{D(jjSTD_1),     STD_CMD,        IDEAL_CMD,      IDEAL_CMD,  POLY_CMD, ALLOW_PLURAL |ALLOW_RING}
    665669,{D(jjSTD_1),     STD_CMD,        MODUL_CMD,      MODUL_CMD,  VECTOR_CMD, ALLOW_PLURAL |ALLOW_RING}
     
    760764,{D(jjRES3),           SRES_CMD,   NONE,       MODUL_CMD,  INT_CMD,    ANY_TYPE, NO_PLURAL |ALLOW_RING}
    761765#endif
     766,{D(jjSBA_2),          SBA_CMD,    IDEAL_CMD,  IDEAL_CMD,  INT_CMD, INT_CMD, ALLOW_PLURAL |ALLOW_RING}
     767,{D(jjSBA_2),          SBA_CMD,    MODUL_CMD,  MODUL_CMD,  INT_CMD, INT_CMD, ALLOW_PLURAL |ALLOW_RING}
    762768,{D(jjSTATUS3),        STATUS_CMD, INT_CMD,    LINK_CMD,   STRING_CMD, STRING_CMD, ALLOW_PLURAL |ALLOW_RING}
    763769,{D(jjSTD_HILB_W),     STD_CMD,    IDEAL_CMD,  IDEAL_CMD,  INTVEC_CMD, INTVEC_CMD, NO_PLURAL |NO_RING}
     
    828834,{D(loSimplex),   SIMPLEX_CMD,     LIST_CMD,            6      , NO_PLURAL |NO_RING}
    829835,{D(nuUResSolve), URSOLVE_CMD,     LIST_CMD,            4      , NO_PLURAL |NO_RING}
     836,{D(jjCALL1ARG),  SBA_CMD,         IDEAL_CMD,           1      , ALLOW_PLURAL |ALLOW_RING}
     837,{D(jjCALL2ARG),  SBA_CMD,         IDEAL_CMD,           2      , ALLOW_PLURAL |ALLOW_RING}
     838,{D(jjCALL3ARG),  SBA_CMD,         IDEAL_CMD,           3      , NO_PLURAL |ALLOW_RING}
    830839,{D(jjCALL1ARG),  STD_CMD,         IDEAL_CMD,           1      , ALLOW_PLURAL |ALLOW_RING}
    831840,{D(jjCALL2ARG),  STD_CMD,         IDEAL_CMD,           2      , ALLOW_PLURAL |ALLOW_RING}
     
    10271036  { "ringlist",    0, RINGLIST_CMD ,      CMD_1},
    10281037  { "rvar",        0, IS_RINGVAR ,        CMD_1},
     1038  { "sba",         0, SBA_CMD ,           CMD_M},
    10291039  { "setring",     0, SETRING_CMD ,       SETRING_CMD},
    10301040  { "simplex",     0, SIMPLEX_CMD,        CMD_M},
  • kernel/kInline.h

    rcffd3e r9e806f  
    11731173}
    11741174
     1175// dummy function for function pointer strat->rewCrit being usable in all
     1176// possible choices for criteria
     1177KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, kStrategy strat, int start=0)
     1178{
     1179  return FALSE;
     1180}
     1181
    11751182#endif // defined(KINLINE) || defined(KUTIL_CC)
    11761183#endif // KINLINE_H
  • kernel/kspoly.cc

    rcffd3e r9e806f  
    155155#endif
    156156 
     157#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
     158  if (TEST_OPT_DEBUG)
     159  {
     160    Print(" to: "); PR->wrp(); Print("\n");
     161  }
     162#endif
     163  return ret;
     164}
     165
     166/***************************************************************
     167 *
     168 * Reduces PR with PW
     169 * Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
     170 *
     171 ***************************************************************/
     172int ksReducePolySig(LObject* PR,
     173                 TObject* PW,
     174                 long idx,
     175                 poly spNoether,
     176                 number *coef,
     177                 kStrategy strat)
     178{
     179#ifdef KDEBUG
     180  red_count++;
     181#ifdef TEST_OPT_DEBUG_RED
     182  if (TEST_OPT_DEBUG)
     183  {
     184    Print("Red %d:", red_count); PR->wrp(); Print(" with:");
     185    PW->wrp();
     186  }
     187#endif
     188#endif
     189  int ret = 0;
     190  ring tailRing = PR->tailRing;
     191  kTest_L(PR);
     192  kTest_T(PW);
     193
     194  // signature-based stuff:
     195  // checking for sig-safeness first
     196  // NOTE: This has to be done in the current ring
     197  //
     198  /**********************************************
     199   *
     200   * TODO:
     201   * --------------------------------------------
     202   * if strat->incremental
     203   * Since we are subdividing lower index and
     204   * current index reductions it is enough to
     205   * look at the polynomial part of the signature
     206   * for a check. This should speed-up checking
     207   * a lot!
     208   * if !strat->incremental
     209   * We are not subdividing lower and current index
     210   * due to the fact that we are using the induced
     211   * Schreyer order
     212   *
     213   * nevertheless, this different behaviour is
     214   * taken care of by is_sigsafe
     215   * => one reduction procedure can be used for
     216   * both, the incremental and the non-incremental
     217   * attempt!
     218   * --------------------------------------------
     219   *
     220   *********************************************/
     221  //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
     222  if (!PW->is_sigsafe)
     223  {
     224    poly f1 = p_Copy(PR->GetLmCurrRing(),currRing);
     225    poly f2 = PW->GetLmCurrRing();
     226    poly sigMult = pCopy(PW->sig);   // copy signature of reducer
     227    p_ExpVectorSub(f1, f2, currRing); // Calculate the Monomial we must multiply to p2
     228//#if 1
     229#ifdef DEBUGF5
     230    printf("IN KSREDUCEPOLYSIG: \n");
     231    pWrite(pHead(f1));
     232    pWrite(pHead(f2));
     233    pWrite(sigMult);
     234    printf("--------------\n");
     235#endif
     236    sigMult = pp_Mult_qq(f1,sigMult,currRing);
     237//#if 1
     238#ifdef DEBUGF5
     239    printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
     240    pWrite(pHead(f1));
     241    pWrite(pHead(f2));
     242    pWrite(sigMult);
     243    pWrite(PR->sig);
     244    printf("--------------\n");
     245#endif
     246    int sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
     247    // now we can delete the copied polynomial data used for checking for
     248    // sig-safeness of the reduction step
     249//#if 1
     250#ifdef DEBUGF5
     251    printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
     252
     253#endif
     254    pDelete(&f1);
     255    pDelete(&sigMult);
     256    // go on with the computations only if the signature of p2 is greater than the
     257    // signature of fm*p1
     258    if(sigSafe != 1)
     259    {
     260      PR->is_redundant = TRUE;
     261      return 3;
     262    }
     263    PW->is_sigsafe  = TRUE;
     264  }
     265  PR->is_redundant = FALSE;
     266  poly p1 = PR->GetLmTailRing();   // p2 | p1
     267  poly p2 = PW->GetLmTailRing();   // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
     268  poly t2 = pNext(p2), lm = p1;    // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
     269  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
     270  p_CheckPolyRing(p1, tailRing);
     271  p_CheckPolyRing(p2, tailRing);
     272
     273  pAssume1(p2 != NULL && p1 != NULL &&
     274      p_DivisibleBy(p2,  p1, tailRing));
     275
     276  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
     277      (p_GetComp(p2, tailRing) == 0 &&
     278       p_MaxComp(pNext(p2),tailRing) == 0));
     279
     280#ifdef HAVE_PLURAL
     281  if (rIsPluralRing(currRing))
     282  {
     283    // for the time being: we know currRing==strat->tailRing
     284    // no exp-bound checking needed
     285    // (only needed if exp-bound(tailring)<exp-b(currRing))
     286    if (PR->bucket!=NULL)  nc_kBucketPolyRed(PR->bucket, p2,coef);
     287    else
     288    {
     289      poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
     290      assume(_p != NULL);
     291      nc_PolyPolyRed(_p, p2, coef, currRing);
     292      if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
     293      PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
     294    }
     295    return 0;
     296  }
     297#endif
     298
     299  if (t2==NULL)           // Divisor is just one term, therefore it will
     300  {                       // just cancel the leading term
     301    PR->LmDeleteAndIter();
     302    if (coef != NULL) *coef = n_Init(1, tailRing);
     303    return 0;
     304  }
     305
     306  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
     307
     308  if (tailRing != currRing)
     309  {
     310    // check that reduction does not violate exp bound
     311    while (PW->max != NULL && !p_LmExpVectorAddIsOk(lm, PW->max, tailRing))
     312    {
     313      // undo changes of lm
     314      p_ExpVectorAdd(lm, p2, tailRing);
     315      if (strat == NULL) return 2;
     316      if (! kStratChangeTailRing(strat, PR, PW)) return -1;
     317      tailRing = strat->tailRing;
     318      p1 = PR->GetLmTailRing();
     319      p2 = PW->GetLmTailRing();
     320      t2 = pNext(p2);
     321      lm = p1;
     322      p_ExpVectorSub(lm, p2, tailRing);
     323      ret = 1;
     324    }
     325  }
     326
     327  // take care of coef buisness
     328  if (! n_IsOne(pGetCoeff(p2), tailRing))
     329  {
     330    number bn = pGetCoeff(lm);
     331    number an = pGetCoeff(p2);
     332    int ct = ksCheckCoeff(&an, &bn, tailRing->cf);    // Calculate special LC
     333    p_SetCoeff(lm, bn, tailRing);
     334    if ((ct == 0) || (ct == 2))
     335      PR->Tail_Mult_nn(an);
     336    if (coef != NULL) *coef = an;
     337    else n_Delete(&an, tailRing);
     338  }
     339  else
     340  {
     341    if (coef != NULL) *coef = n_Init(1, tailRing);
     342  }
     343
     344
     345  // and finally,
     346  PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
     347  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
     348  PR->LmDeleteAndIter();
     349
     350  // the following is commented out: shrinking
     351#ifdef HAVE_SHIFTBBA_NONEXISTENT
     352  if ( (currRing->isLPring) && (!strat->homog) )
     353  {
     354    // assume? h->p in currRing
     355    PR->GetP();
     356    poly qq = p_Shrink(PR->p, currRing->isLPring, currRing);
     357    PR->Clear(); // does the right things
     358    PR->p = qq;
     359    PR->t_p = NULL;
     360    PR->SetShortExpVector();
     361  }
     362#endif
     363
    157364#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
    158365  if (TEST_OPT_DEBUG)
  • kernel/kstd1.cc

    rcffd3e r9e806f  
    10981098}
    10991099
     1100
     1101void initSba(ideal F,kStrategy strat)
     1102{
     1103  int i;
     1104  //idhdl h;
     1105 /* setting global variables ------------------- */
     1106  strat->enterS = enterSSba;
     1107    strat->red2 = redHoney;
     1108  if (strat->honey)
     1109    strat->red2 = redHoney;
     1110  else if (currRing->pLexOrder && !strat->homog)
     1111    strat->red2 = redLazy;
     1112  else
     1113  {
     1114    strat->LazyPass *=4;
     1115    strat->red2 = redHomog;
     1116  }
     1117#ifdef HAVE_RINGS  //TODO Oliver
     1118  if (rField_is_Ring(currRing))
     1119  {
     1120    strat->red2 = redRing;
     1121  }
     1122#endif
     1123  if (currRing->pLexOrder && strat->honey)
     1124    strat->initEcart = initEcartNormal;
     1125  else
     1126    strat->initEcart = initEcartBBA;
     1127  if (strat->honey)
     1128    strat->initEcartPair = initEcartPairMora;
     1129  else
     1130    strat->initEcartPair = initEcartPairBba;
     1131  //strat->kIdeal = NULL;
     1132  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
     1133  //else              strat->kIdeal->rtyp=MODUL_CMD;
     1134  //strat->kIdeal->data=(void *)strat->Shdl;
     1135  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
     1136  {
     1137    //interred  machen   Aenderung
     1138    strat->pOrigFDeg  = currRing->pFDeg;
     1139    strat->pOrigLDeg  = currRing->pLDeg;
     1140    //h=ggetid("ecart");
     1141    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
     1142    //{
     1143    //  ecartWeights=iv2array(IDINTVEC(h));
     1144    //}
     1145    //else
     1146    {
     1147      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
     1148      /*uses automatic computation of the ecartWeights to set them*/
     1149      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights, currRing);
     1150    }
     1151    pRestoreDegProcs(currRing, totaldegreeWecart, maxdegreeWecart);
     1152    if (TEST_OPT_PROT)
     1153    {
     1154      for(i=1; i<=(currRing->N); i++)
     1155        Print(" %d",ecartWeights[i]);
     1156      PrintLn();
     1157      mflush();
     1158    }
     1159  }
     1160  // for sig-safe reductions in signature-based
     1161  // standard basis computations
     1162  strat->red          = redSig;
     1163  //strat->incremental  = TRUE;
     1164  strat->currIdx      = 1;
     1165}
     1166
    11001167void initMora(ideal F,kStrategy strat)
    11011168{
     
    17951862      else
    17961863        r=bba(F,Q,NULL,hilb,strat);
     1864    }
     1865  }
     1866#ifdef KDEBUG
     1867  idTest(r);
     1868#endif
     1869  if (toReset)
     1870  {
     1871    kModW = NULL;
     1872    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
     1873  }
     1874  currRing->pLexOrder = b;
     1875//Print("%d reductions canceled \n",strat->cel);
     1876  HCord=strat->HCord;
     1877  delete(strat);
     1878  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
     1879  return r;
     1880}
     1881
     1882ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int incremental, int arri, intvec *hilb,int syzComp,
     1883          int newIdeal, intvec *vw)
     1884{
     1885  if(idIs0(F))
     1886    return idInit(1,F->rank);
     1887
     1888  ideal r;
     1889  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
     1890  BOOLEAN delete_w=(w==NULL);
     1891  kStrategy strat=new skStrategy;
     1892  if (incremental!=0)
     1893  {
     1894    strat->incremental = TRUE;
     1895  }
     1896  else
     1897  {
     1898    strat->incremental = FALSE;
     1899  }
     1900  if (arri!=0)
     1901  {
     1902    strat->rewCrit1 = arriRewDummy;
     1903    strat->rewCrit2 = arriRewCriterion;
     1904  }
     1905  else
     1906  {
     1907    strat->rewCrit1 = faugereRewCriterion;
     1908    strat->rewCrit2 = faugereRewCriterion;
     1909  }
     1910
     1911  if(!TEST_OPT_RETURN_SB)
     1912    strat->syzComp = syzComp;
     1913  if (TEST_OPT_SB_1)
     1914    strat->newIdeal = newIdeal;
     1915  if (rField_has_simple_inverse(currRing))
     1916    strat->LazyPass=20;
     1917  else
     1918    strat->LazyPass=2;
     1919  strat->LazyDegree = 1;
     1920  strat->enterOnePair=enterOnePairNormal;
     1921  strat->chainCrit=chainCritNormal;
     1922  strat->ak = id_RankFreeModule(F,currRing);
     1923  strat->kModW=kModW=NULL;
     1924  strat->kHomW=kHomW=NULL;
     1925  if (vw != NULL)
     1926  {
     1927    currRing->pLexOrder=FALSE;
     1928    strat->kHomW=kHomW=vw;
     1929    strat->pOrigFDeg = currRing->pFDeg;
     1930    strat->pOrigLDeg = currRing->pLDeg;
     1931    pSetDegProcs(currRing,kHomModDeg);
     1932    toReset = TRUE;
     1933  }
     1934  if (h==testHomog)
     1935  {
     1936    if (strat->ak == 0)
     1937    {
     1938      h = (tHomog)idHomIdeal(F,Q);
     1939      w=NULL;
     1940    }
     1941    else if (!TEST_OPT_DEGBOUND)
     1942    {
     1943      h = (tHomog)idHomModule(F,Q,w);
     1944    }
     1945  }
     1946  currRing->pLexOrder=b;
     1947  if (h==isHomog)
     1948  {
     1949    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
     1950    {
     1951      strat->kModW = kModW = *w;
     1952      if (vw == NULL)
     1953      {
     1954        strat->pOrigFDeg = currRing->pFDeg;
     1955        strat->pOrigLDeg = currRing->pLDeg;
     1956        pSetDegProcs(currRing,kModDeg);
     1957        toReset = TRUE;
     1958      }
     1959    }
     1960    currRing->pLexOrder = TRUE;
     1961    if (hilb==NULL) strat->LazyPass*=2;
     1962  }
     1963  strat->homog=h;
     1964#ifdef KDEBUG
     1965  idTest(F);
     1966  idTest(Q);
     1967
     1968#if MYTEST
     1969  if (TEST_OPT_DEBUG)
     1970  {
     1971    PrintS("// kSTD: currRing: ");
     1972    rWrite(currRing);
     1973  }
     1974#endif
     1975
     1976#endif
     1977#ifdef HAVE_PLURAL
     1978  if (rIsPluralRing(currRing))
     1979  {
     1980    const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
     1981    strat->no_prod_crit   = ! bIsSCA;
     1982    if (w!=NULL)
     1983      r = nc_GB(F, Q, *w, hilb, strat, currRing);
     1984    else
     1985      r = nc_GB(F, Q, NULL, hilb, strat, currRing);
     1986  }
     1987  else
     1988#endif
     1989#ifdef HAVE_RINGS
     1990  if (rField_is_Ring(currRing))
     1991    r=bba(F,Q,NULL,hilb,strat);
     1992  else
     1993#endif
     1994  {
     1995    if (currRing->OrdSgn==-1)
     1996    {
     1997      if (w!=NULL)
     1998        r=mora(F,Q,*w,hilb,strat);
     1999      else
     2000        r=mora(F,Q,NULL,hilb,strat);
     2001    }
     2002    else
     2003    {
     2004      if (w!=NULL)
     2005        r=sba(F,Q,*w,hilb,strat);
     2006      else
     2007                          r=sba(F,Q,NULL,hilb,strat);
    17972008    }
    17982009  }
  • kernel/kstd1.h

    rcffd3e r9e806f  
    2929/// NOTE: this is just a wrapper which sets currRing for the actual kNF call
    3030poly kNF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing);
     31ideal kSba(ideal F,ideal Q, tHomog h, intvec ** mw, int incremental=0, int arri=0, intvec *hilb=NULL,
     32          int syzComp=0,int newIdeal=0, intvec *vw=NULL);
    3133
    3234ideal kStd(ideal F, ideal Q, tHomog h, intvec ** mw,intvec *hilb=NULL,
  • kernel/kstd2.cc

    rcffd3e r9e806f  
    3434#define PLURAL_INTERNAL_DECLARATIONS 1
    3535#endif
     36
     37#define DEBUGF50  0
     38#define DEBUGF51  0
     39
     40#ifdef DEBUGF5
     41#undef DEBUGF5
     42//#define DEBUGF5 1
     43#endif
     44
     45#define F5C       1
     46#if F5C
     47  #define F5CTAILRED 0
     48#endif
     49
    3650#include <kernel/kutil.h>
    3751#include <misc/options.h>
     
    4357#include <kernel/khstd.h>
    4458#include <polys/kbuckets.h>
     59#include <polys/prCopy.h>
    4560//#include "cntrlc.h"
    4661#include <polys/weight.h>
     
    478493        h->Clear();
    479494        return -1;
     495      }
     496    }
     497  }
     498}
     499
     500/*2
     501*  reduction procedure for signature-based standard
     502*  basis algorithms:
     503*  all reductions have to be sig-safe!
     504*
     505*  2 is returned if and only if the pair is rejected by the rewritten criterion
     506*  at exactly this point of the computations. This is the last possible point
     507*  such a check can be done => checks with the biggest set of available
     508*  signatures
     509*/
     510int redSig (LObject* h,kStrategy strat)
     511{
     512  if (strat->tl<0) return 1;
     513  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
     514  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
     515  assume(h->FDeg == h->pFDeg());
     516//#if 1
     517#ifdef DEBUGF5
     518  Print("------- IN REDSIG -------\n");
     519  Print("p: ");
     520  pWrite(pHead(h->p));
     521  Print("p1: ");
     522  pWrite(pHead(h->p1));
     523  Print("p2: ");
     524  pWrite(pHead(h->p2));
     525  Print("---------------------------\n");
     526#endif
     527  poly h_p;
     528  int i,j,at,pass, ii;
     529  int start=0;
     530  int sigSafe;
     531  unsigned long not_sev;
     532  long reddeg,d;
     533
     534  pass = j = 0;
     535  d = reddeg = h->GetpFDeg();
     536  h->SetShortExpVector();
     537  int li;
     538  h_p = h->GetLmTailRing();
     539  not_sev = ~ h->sev;
     540  loop
     541  {
     542    j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h, start);
     543    if (j < 0)
     544    {
     545      return 1;
     546    }
     547
     548    li = strat->T[j].pLength;
     549    ii = j;
     550    /*
     551     * the polynomial to reduce with (up to the moment) is;
     552     * pi with length li
     553     */
     554    i = j;
     555#if 1
     556    if (TEST_OPT_LENGTH)
     557    loop
     558    {
     559      /*- search the shortest possible with respect to length -*/
     560      i++;
     561      if (i > strat->tl)
     562        break;
     563      if (li<=1)
     564        break;
     565      if ((strat->T[i].pLength < li)
     566         &&
     567          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
     568                               h_p, not_sev, strat->tailRing))
     569      {
     570        /*
     571         * the polynomial to reduce with is now;
     572         */
     573        li = strat->T[i].pLength;
     574        ii = i;
     575      }
     576    }
     577    start = ii+1;
     578#endif
     579
     580    /*
     581     * end of search: have to reduce with pi
     582     */
     583#ifdef KDEBUG
     584    if (TEST_OPT_DEBUG)
     585    {
     586      PrintS("red:");
     587      h->wrp();
     588      PrintS(" with ");
     589      strat->T[ii].wrp();
     590    }
     591#endif
     592    assume(strat->fromT == FALSE);
     593//#if 1
     594#ifdef DEBUGF5
     595    Print("BEFORE REDUCTION WITH %d:\n",ii);
     596    Print("--------------------------------\n");
     597    pWrite(h->sig);
     598    pWrite(strat->T[ii].sig);
     599    pWrite(h->GetLmCurrRing());
     600    pWrite(pHead(h->p1));
     601    pWrite(pHead(h->p2));
     602    pWrite(pHead(strat->T[ii].p));
     603    Print("--------------------------------\n");
     604    printf("INDEX OF REDUCER T: %d\n",ii);
     605#endif
     606    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
     607    // if reduction has taken place, i.e. the reduction was sig-safe
     608    // otherwise start is already at the next position and the loop
     609    // searching reducers in T goes on from index start
     610//#if 1
     611#ifdef DEBUGF5
     612    Print("SigSAFE: %d\n",sigSafe);
     613#endif
     614    if (sigSafe != 3)
     615    {
     616      // start the next search for reducers in T from the beginning
     617      start = 0;
     618#ifdef KDEBUG
     619      if (TEST_OPT_DEBUG)
     620      {
     621        PrintS("\nto ");
     622        h->wrp();
     623        PrintLn();
     624      }
     625#endif
     626
     627      h_p = h->GetLmTailRing();
     628      if (h_p == NULL)
     629      {
     630        if (h->lcm!=NULL) pLmFree(h->lcm);
     631#ifdef KDEBUG
     632        h->lcm=NULL;
     633#endif
     634        return 0;
     635      }
     636      h->SetShortExpVector();
     637      not_sev = ~ h->sev;
     638      /*
     639      * try to reduce the s-polynomial h
     640      *test first whether h should go to the lazyset L
     641      *-if the degree jumps
     642      *-if the number of pre-defined reductions jumps
     643      */
     644      pass++;
     645      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
     646      {
     647        h->SetLmCurrRing();
     648        at = strat->posInL(strat->L,strat->Ll,h,strat);
     649        if (at <= strat->Ll)
     650        {
     651          int dummy=strat->sl;
     652          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
     653          {
     654            return 1;
     655          }
     656          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
     657#ifdef KDEBUG
     658          if (TEST_OPT_DEBUG)
     659            Print(" lazy: -> L%d\n",at);
     660#endif
     661          h->Clear();
     662          return -1;
     663        }
    480664      }
    481665    }
     
    12941478  idTest(strat->Shdl);
    12951479
     1480  return (strat->Shdl);
     1481}
     1482ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
     1483{
     1484  // ring order stuff:
     1485  // in sba we have (until now) two possibilities:
     1486  // 1. an incremental computation w.r.t. (C,monomial order)
     1487  // 2. a (possibly non-incremental) computation w.r.t. the
     1488  //    induced Schreyer order.
     1489  // The corresponding orders are computed in sbaRing(), depending
     1490  // on the flag strat->incremental
     1491  ideal F = F0;
     1492  ring sRing, currRingOld;
     1493  currRingOld  = currRing;
     1494  if (strat->incremental)
     1495  {
     1496    sRing = sbaRing(strat);
     1497    if (sRing!=currRingOld)
     1498    {
     1499      rChangeCurrRing (sRing);
     1500      F = idrMoveR (F0, currRingOld, currRing);
     1501    }
     1502  }
     1503#if 0
     1504  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
     1505  rWrite (currRing);
     1506  printf("\n");
     1507#endif
     1508#ifdef KDEBUG
     1509  bba_count++;
     1510  int loop_count = 0;
     1511#endif /* KDEBUG */
     1512  om_Opts.MinTrack = 5;
     1513  int   srmax,lrmax, red_result = 1;
     1514  int   olddeg,reduc;
     1515  int hilbeledeg=1,hilbcount=0,minimcnt=0;
     1516  long zeroreductions = 0;
     1517  LObject L;
     1518  BOOLEAN withT     = FALSE;
     1519  BOOLEAN newrules  = FALSE;
     1520  strat->max_lower_index = 0;
     1521
     1522  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
     1523  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
     1524  initSbaPos(strat);
     1525  //initBuchMoraPos(strat);
     1526  initHilbCrit(F,Q,&hilb,strat);
     1527  initSba(F,strat);
     1528  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
     1529  /*Shdl=*/initSbaBuchMora(F, Q,strat);
     1530  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
     1531  srmax = strat->sl;
     1532  reduc = olddeg = lrmax = 0;
     1533
     1534#ifndef NO_BUCKETS
     1535  if (!TEST_OPT_NOT_BUCKETS)
     1536    strat->use_buckets = 1;
     1537#endif
     1538
     1539  // redtailBBa against T for inhomogenous input
     1540  if (!TEST_OPT_OLDSTD)
     1541    withT = ! strat->homog;
     1542
     1543  // strat->posInT = posInT_pLength;
     1544  kTest_TS(strat);
     1545
     1546#ifdef KDEBUG
     1547#if MYTEST
     1548  if (TEST_OPT_DEBUG)
     1549  {
     1550    PrintS("bba start GB: currRing: ");
     1551    // rWrite(currRing);PrintLn();
     1552    rDebugPrint(currRing);
     1553    PrintLn();
     1554  }
     1555#endif /* MYTEST */
     1556#endif /* KDEBUG */
     1557
     1558#ifdef HAVE_TAIL_RING
     1559  if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
     1560    kStratInitChangeTailRing(strat);
     1561#endif
     1562  if (BVERBOSE(23))
     1563  {
     1564    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
     1565    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
     1566    kDebugPrint(strat);
     1567  }
     1568
     1569
     1570#ifdef KDEBUG
     1571  //kDebugPrint(strat);
     1572#endif
     1573  /* compute------------------------------------------------------- */
     1574  arriAgain:
     1575  while (strat->Ll >= 0)
     1576  {
     1577    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
     1578    #ifdef KDEBUG
     1579      loop_count++;
     1580      if (TEST_OPT_DEBUG) messageSets(strat);
     1581    #endif
     1582    if (strat->Ll== 0) strat->interpt=TRUE;
     1583    if (TEST_OPT_DEGBOUND
     1584        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
     1585            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
     1586    {
     1587      /*
     1588       *stops computation if
     1589       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
     1590       *a predefined number Kstd1_deg
     1591       */
     1592      while ((strat->Ll >= 0)
     1593        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
     1594        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
     1595            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
     1596        )
     1597        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
     1598      if (strat->Ll<0) break;
     1599      else strat->noClearS=TRUE;
     1600    }
     1601    if (strat->incremental && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
     1602    {
     1603      strat->currIdx  = pGetComp(strat->L[strat->Ll].sig);
     1604#if F5C
     1605      // 1. interreduction of the current standard basis
     1606      // 2. generation of new principal syzygy rules for syzCriterion
     1607      f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
     1608            lrmax, reduc, Q, w, hilb );
     1609#endif
     1610      // initialize new syzygy rules for the next iteration step 
     1611      initSyzRules(strat);
     1612    }
     1613    /*********************************************************************
     1614     * interrreduction step is done, we can go on with the next iteration
     1615     * step of the signature-based algorithm
     1616     ********************************************************************/
     1617    /* picks the last element from the lazyset L */
     1618    strat->P = strat->L[strat->Ll];
     1619    strat->Ll--;
     1620//#if 1
     1621#ifdef DEBUGF5
     1622    Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
     1623    Print("-------------------------------------------------\n");
     1624    pWrite(strat->P.sig);
     1625    pWrite(pHead(strat->P.p));
     1626    pWrite(pHead(strat->P.p1));
     1627    pWrite(pHead(strat->P.p2));
     1628    Print("-------------------------------------------------\n");
     1629#endif
     1630    if (pNext(strat->P.p) == strat->tail)
     1631    {
     1632      // deletes the short spoly
     1633#ifdef HAVE_RINGS
     1634      if (rField_is_Ring(currRing))
     1635        pLmDelete(strat->P.p);
     1636      else
     1637#endif
     1638        pLmFree(strat->P.p);
     1639
     1640      // TODO: needs some masking
     1641      // TODO: masking needs to vanish once the signature
     1642      //       sutff is completely implemented
     1643      strat->P.p = NULL;
     1644      poly m1 = NULL, m2 = NULL;
     1645
     1646      // check that spoly creation is ok
     1647      while (strat->tailRing != currRing &&
     1648             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
     1649      {
     1650        assume(m1 == NULL && m2 == NULL);
     1651        // if not, change to a ring where exponents are at least
     1652        // large enough
     1653        if (!kStratChangeTailRing(strat))
     1654        {
     1655          WerrorS("OVERFLOW...");
     1656          break;
     1657        }
     1658      }
     1659      // create the real one
     1660      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
     1661                    strat->tailRing, m1, m2, strat->R);
     1662
     1663    }
     1664    else if (strat->P.p1 == NULL)
     1665    {
     1666      if (strat->minim > 0)
     1667        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
     1668      // for input polys, prepare reduction
     1669      strat->P.PrepareRed(strat->use_buckets);
     1670    }
     1671
     1672    if (strat->P.p == NULL && strat->P.t_p == NULL)
     1673    {
     1674      red_result = 0;
     1675    }
     1676    else
     1677    {
     1678      if (TEST_OPT_PROT)
     1679        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
     1680                &olddeg,&reduc,strat, red_result);
     1681
     1682//#if 1
     1683#ifdef DEBUGF5
     1684      Print("Poly before red: ");
     1685      pWrite(strat->P.p);
     1686#endif
     1687      /* reduction of the element choosen from L */
     1688      if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat, strat->P.checked+1))
     1689        red_result = strat->red(&strat->P,strat);
     1690      else
     1691      {
     1692        if (strat->P.lcm!=NULL)
     1693          pLmFree(strat->P.lcm);
     1694        red_result = 2;
     1695      }
     1696      if (errorreported)  break;
     1697    }
     1698
     1699    if (strat->overflow)
     1700    {
     1701        if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
     1702    }
     1703    if (strat->incremental)
     1704    {
     1705      for (int jj = 0; jj<strat->tl+1; jj++)
     1706      {
     1707        if (pGetComp(strat->T[jj].sig) == strat->currIdx)
     1708        {
     1709          strat->T[jj].is_sigsafe = FALSE;
     1710        }
     1711      }
     1712    }
     1713    else
     1714    {
     1715      for (int jj = 0; jj<strat->tl+1; jj++)
     1716      {
     1717        strat->T[jj].is_sigsafe = FALSE;
     1718      }
     1719    }
     1720
     1721    // reduction to non-zero new poly
     1722    if (red_result == 1)
     1723    {
     1724      // get the polynomial (canonicalize bucket, make sure P.p is set)
     1725      strat->P.GetP(strat->lmBin);
     1726     
     1727      // sig-safe computations may lead to wrong FDeg computation, thus we need
     1728      // to recompute it to make sure everything is alright
     1729      (strat->P).FDeg = (strat->P).pFDeg();
     1730      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
     1731      // but now, for entering S, T, we reset it
     1732      // in the inhomogeneous case: FDeg == pFDeg
     1733      if (strat->homog) strat->initEcart(&(strat->P));
     1734
     1735      /* statistic */
     1736      if (TEST_OPT_PROT) PrintS("s");
     1737
     1738      //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
     1739      // in F5E we know that the last reduced element is already the
     1740      // the one with highest signature
     1741      int pos = strat->sl+1;
     1742
     1743#ifdef KDEBUG
     1744#if MYTEST
     1745      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
     1746#endif /* MYTEST */
     1747#endif /* KDEBUG */
     1748
     1749      // reduce the tail and normalize poly
     1750      // in the ring case we cannot expect LC(f) = 1,
     1751      // therefore we call pContent instead of pNorm
     1752      /*
     1753      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
     1754      {
     1755        strat->P.pCleardenom();
     1756        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     1757        {
     1758          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     1759          strat->P.pCleardenom();
     1760        }
     1761      }
     1762      else
     1763      {
     1764        strat->P.pNorm();
     1765        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     1766          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     1767      }
     1768      */
     1769#ifdef KDEBUG
     1770      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
     1771#if MYTEST
     1772//#if 1
     1773      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
     1774#endif /* MYTEST */
     1775#endif /* KDEBUG */
     1776
     1777      // min_std stuff
     1778      if ((strat->P.p1==NULL) && (strat->minim>0))
     1779      {
     1780        if (strat->minim==1)
     1781        {
     1782          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
     1783          p_Delete(&strat->P.p2, currRing, strat->tailRing);
     1784        }
     1785        else
     1786        {
     1787          strat->M->m[minimcnt]=strat->P.p2;
     1788          strat->P.p2=NULL;
     1789        }
     1790        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
     1791          pNext(strat->M->m[minimcnt])
     1792            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
     1793                                           strat->tailRing, currRing,
     1794                                           currRing->PolyBin);
     1795        minimcnt++;
     1796      }
     1797
     1798      // enter into S, L, and T
     1799      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
     1800      if(!strat->incremental)
     1801      {
     1802        BOOLEAN overwrite = TRUE;
     1803        for (int tk=0; tk<strat->sl+1; tk++)
     1804        {
     1805          if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
     1806          {
     1807            //printf("TK %d / %d\n",tk,strat->sl);
     1808            overwrite = FALSE;
     1809            break;
     1810          }
     1811        }
     1812        //printf("OVERWRITE %d\n",overwrite);
     1813        if (overwrite)
     1814        {
     1815          int cmp = pGetComp(strat->P.sig);
     1816          int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
     1817          pGetExpV (strat->P.p,vv);
     1818          pSetExpV (strat->P.sig, vv);
     1819          pSetComp (strat->P.sig,cmp);
     1820
     1821          strat->P.sevSig = pGetShortExpVector (strat->P.sig);
     1822          for(int ps=0;ps<strat->sl+1;ps++)
     1823          {
     1824            int i = strat->syzl;
     1825
     1826            strat->newt = TRUE;
     1827            if (strat->syzl == strat->syzmax)
     1828            {
     1829              pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
     1830              strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
     1831                  (strat->syzmax)*sizeof(unsigned long),
     1832                  ((strat->syzmax)+setmaxTinc)
     1833                  *sizeof(unsigned long));
     1834              strat->syzmax += setmaxTinc;
     1835            }
     1836            strat->syz[i] = pCopy(strat->P.sig);
     1837            // add LM(F->m[i]) to the signature to get a Schreyer order
     1838            // without changing the underlying polynomial ring at all
     1839            p_ExpVectorAdd (strat->syz[i],strat->S[ps],currRing); 
     1840            // since p_Add_q() destroys all input
     1841            // data we need to recreate help
     1842            // each time
     1843            // ----------------------------------------------------------
     1844            // in the Schreyer order we always know that the multiplied
     1845            // module monomial strat->P.sig gives the leading monomial of
     1846            // the corresponding principal syzygy
     1847            // => we do not need to compute the "real" syzygy completely
     1848            poly help = pCopy(strat->sig[ps]);
     1849            p_ExpVectorAdd (help,strat->P.p,currRing); 
     1850            strat->syz[i] = p_Add_q(strat->syz[i],help,currRing);
     1851            //printf("%d. SYZ  ",i+1);
     1852            //pWrite(strat->syz[i]);
     1853            strat->sevSyz[i] = p_GetShortExpVector(strat->syz[i],currRing);
     1854            strat->syzl++;
     1855          }
     1856        }
     1857      }
     1858        enterT(strat->P, strat);
     1859        strat->T[strat->tl].is_sigsafe = FALSE;
     1860#ifdef HAVE_RINGS
     1861      if (rField_is_Ring(currRing))
     1862        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
     1863      else
     1864#endif
     1865        enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
     1866      // posInS only depends on the leading term
     1867      strat->enterS(strat->P, pos, strat, strat->tl);
     1868//#if 1
     1869#if DEBUGF50
     1870    printf("---------------------------\n");
     1871    Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
     1872    Print("LEAD POLY:  "); pWrite(pHead(strat->S[strat->sl]));
     1873    Print("SIGNATURE:  "); pWrite(strat->sig[strat->sl]);
     1874#endif
     1875      /*
     1876      if (newrules)
     1877      {
     1878        newrules  = FALSE;
     1879      }
     1880      */
     1881#if 0
     1882      int pl=pLength(strat->P.p);
     1883      if (pl==1)
     1884      {
     1885        //if (TEST_OPT_PROT)
     1886        //PrintS("<1>");
     1887      }
     1888      else if (pl==2)
     1889      {
     1890        //if (TEST_OPT_PROT)
     1891        //PrintS("<2>");
     1892      }
     1893#endif
     1894      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
     1895//      Print("[%d]",hilbeledeg);
     1896      if (strat->P.lcm!=NULL)
     1897#ifdef HAVE_RINGS
     1898        pLmDelete(strat->P.lcm);
     1899#else
     1900        pLmFree(strat->P.lcm);
     1901#endif
     1902      if (strat->sl>srmax) srmax = strat->sl;
     1903    }
     1904    else
     1905    {
     1906      // adds signature of the zero reduction to
     1907      // strat->syz. This is the leading term of
     1908      // syzygy and can be used in syzCriterion()
     1909      // the signature is added if and only if the
     1910      // pair was not detected by the rewritten criterion in strat->red = redSig
     1911      if (red_result!=2) {
     1912        zeroreductions++;
     1913        enterSyz(strat->P,strat);
     1914//#if 1
     1915#ifdef DEBUGF5
     1916        Print("ADDING STUFF TO SYZ :  ");
     1917        pWrite(strat->P.p);
     1918        pWrite(strat->P.sig);
     1919#endif
     1920      }
     1921      if (strat->P.p1 == NULL && strat->minim > 0)
     1922      {
     1923        p_Delete(&strat->P.p2, currRing, strat->tailRing);
     1924      }
     1925    }
     1926
     1927#ifdef KDEBUG
     1928    memset(&(strat->P), 0, sizeof(strat->P));
     1929#endif /* KDEBUG */
     1930    kTest_TS(strat);
     1931  }
     1932#ifdef KDEBUG
     1933#if MYTEST
     1934  PrintS("bba finish GB: currRing: "); rWrite(currRing);
     1935#endif /* MYTEST */
     1936  if (TEST_OPT_DEBUG) messageSets(strat);
     1937#endif /* KDEBUG */
     1938
     1939  if (TEST_OPT_SB_1)
     1940  {
     1941    int k=1;
     1942    int j;
     1943    while(k<=strat->sl)
     1944    {
     1945      j=0;
     1946      loop
     1947      {
     1948        if (j>=k) break;
     1949        clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
     1950        j++;
     1951      }
     1952      k++;
     1953    }
     1954  }
     1955
     1956  /* complete reduction of the standard basis--------- */
     1957  if (TEST_OPT_REDSB)
     1958  {
     1959    completeReduce(strat);
     1960#ifdef HAVE_TAIL_RING
     1961    if (strat->completeReduce_retry)
     1962    {
     1963      // completeReduce needed larger exponents, retry
     1964      // to reduce with S (instead of T)
     1965      // and in currRing (instead of strat->tailRing)
     1966      cleanT(strat);strat->tailRing=currRing;
     1967      int i;
     1968      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
     1969      completeReduce(strat);
     1970    }
     1971#endif
     1972  }
     1973  else if (TEST_OPT_PROT) PrintLn();
     1974
     1975  exitSba(strat);
     1976//  if (TEST_OPT_WEIGHTM)
     1977//  {
     1978//    pRestoreDegProcs(pFDegOld, pLDegOld);
     1979//    if (ecartWeights)
     1980//    {
     1981//      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
     1982//      ecartWeights=NULL;
     1983//    }
     1984//  }
     1985  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
     1986  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
     1987
     1988#ifdef KDEBUG
     1989#if MYTEST
     1990  PrintS("bba_end: currRing: "); rWrite(currRing);
     1991#endif /* MYTEST */
     1992#endif /* KDEBUG */
     1993  // using F5C it is possible that there is some data stored in the last
     1994  // entries of strat->Shdl which are dirty, i.e. not correct, but also not NULL
     1995  // => we need to delete them before return the ideal
     1996#if F5C
     1997  for(int i=strat->sl+1;i<IDELEMS(strat->Shdl);i++)
     1998  {
     1999    //pDelete (&strat->Shdl->m[i]);
     2000    strat->Shdl->m[i] = NULL;
     2001  }
     2002#endif
     2003  if (strat->incremental && sRing!=currRingOld)
     2004  {
     2005    rChangeCurrRing (currRingOld);
     2006    F0          = idrMoveR (F, sRing, currRing);
     2007    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
     2008    rDelete (sRing);
     2009  }
     2010  idTest(strat->Shdl);
     2011
     2012#ifdef DEBUGF5
     2013  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
     2014  int oo = 0;
     2015  while (oo<IDELEMS(strat->Shdl))
     2016  {
     2017    printf(" %d.   ",oo+1);
     2018    pWrite(pHead(strat->Shdl->m[oo]));
     2019    oo++;
     2020  }
     2021#endif
     2022  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
     2023  zeroreductions  = 0;
    12962024  return (strat->Shdl);
    12972025}
     
    14472175  return res;
    14482176}
     2177
     2178#if F5C
     2179/*********************************************************************
     2180* interrreduction step of the signature-based algorithm:
     2181* 1. all strat->S are interpreted as new critical pairs
     2182* 2. those pairs need to be completely reduced by the usual (non sig-
     2183*    safe) reduction process (including tail reductions)
     2184* 3. strat->S and strat->T are completely new computed in these steps
     2185********************************************************************/
     2186void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
     2187          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
     2188          intvec *w,intvec *hilb )
     2189{
     2190  int Ll_old, red_result = 1;
     2191  BOOLEAN withT = FALSE;
     2192  int pos  = 0;
     2193  hilbeledeg=1;
     2194  hilbcount=0;
     2195  minimcnt=0;
     2196  srmax = 0; // strat->sl is 0 at this point
     2197  reduc = olddeg = lrmax = 0;
     2198  // we cannot use strat->T anymore
     2199  //cleanT(strat);
     2200  //strat->tl = -1;
     2201  Ll_old    = strat->Ll;
     2202  while (strat->tl >= 0)
     2203  {
     2204    if(!strat->T[strat->tl].is_redundant)
     2205    {
     2206      LObject h;
     2207      h.p = strat->T[strat->tl].p;
     2208      h.tailRing = strat->T[strat->tl].tailRing;
     2209      h.t_p = strat->T[strat->tl].t_p;
     2210      if (h.p!=NULL)
     2211      {
     2212        if (currRing->OrdSgn==-1)
     2213        {
     2214          cancelunit(&h); 
     2215          deleteHC(&h, strat);
     2216        }
     2217        if (h.p!=NULL)
     2218        {
     2219          if (TEST_OPT_INTSTRATEGY)
     2220          {
     2221            //pContent(h.p);
     2222            h.pCleardenom(); // also does a pContent
     2223          }
     2224          else
     2225          {
     2226            h.pNorm();
     2227          }
     2228          strat->initEcart(&h);
     2229          pos = strat->Ll+1;
     2230          h.sev = pGetShortExpVector(h.p);
     2231          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
     2232        }
     2233      }
     2234    }
     2235    strat->tl--;
     2236  }
     2237  strat->sl = -1;
     2238#if 0
     2239//#ifdef HAVE_TAIL_RING
     2240  if(!rField_is_Ring())  // create strong gcd poly computes with tailring and S[i] ->to be fixed
     2241    kStratInitChangeTailRing(strat);
     2242#endif
     2243  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
     2244  //strat->sl = -1;
     2245  /* picks the last element from the lazyset L */
     2246  while (strat->Ll>Ll_old)
     2247  {
     2248    strat->P = strat->L[strat->Ll];
     2249    strat->Ll--;
     2250//#if 1
     2251#ifdef DEBUGF5
     2252    Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
     2253    Print("-------------------------------------------------\n");
     2254    pWrite(pHead(strat->P.p));
     2255    pWrite(pHead(strat->P.p1));
     2256    pWrite(pHead(strat->P.p2));
     2257    printf("%d\n",strat->tl);
     2258    Print("-------------------------------------------------\n");
     2259#endif
     2260    if (pNext(strat->P.p) == strat->tail)
     2261    {
     2262      // deletes the short spoly
     2263#ifdef HAVE_RINGS
     2264      if (rField_is_Ring(currRing))
     2265        pLmDelete(strat->P.p);
     2266      else
     2267#endif
     2268        pLmFree(strat->P.p);
     2269
     2270      // TODO: needs some masking
     2271      // TODO: masking needs to vanish once the signature
     2272      //       sutff is completely implemented
     2273      strat->P.p = NULL;
     2274      poly m1 = NULL, m2 = NULL;
     2275
     2276      // check that spoly creation is ok
     2277      while (strat->tailRing != currRing &&
     2278          !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
     2279      {
     2280        assume(m1 == NULL && m2 == NULL);
     2281        // if not, change to a ring where exponents are at least
     2282        // large enough
     2283        if (!kStratChangeTailRing(strat))
     2284        {
     2285          WerrorS("OVERFLOW...");
     2286          break;
     2287        }
     2288      }
     2289      // create the real one
     2290      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
     2291          strat->tailRing, m1, m2, strat->R);
     2292    }
     2293    else if (strat->P.p1 == NULL)
     2294    {
     2295      if (strat->minim > 0)
     2296        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
     2297      // for input polys, prepare reduction
     2298      strat->P.PrepareRed(strat->use_buckets);
     2299    }
     2300
     2301    if (strat->P.p == NULL && strat->P.t_p == NULL)
     2302    {
     2303      red_result = 0;
     2304    }
     2305    else
     2306    {
     2307      if (TEST_OPT_PROT)
     2308        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
     2309            &olddeg,&reduc,strat, red_result);
     2310
     2311#ifdef DEBUGF5
     2312      Print("Poly before red: ");
     2313      pWrite(strat->P.p);
     2314#endif
     2315      /* complete reduction of the element choosen from L */
     2316      red_result = strat->red2(&strat->P,strat);
     2317      if (errorreported)  break;
     2318    }
     2319
     2320    if (strat->overflow)
     2321    {
     2322      if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
     2323    }
     2324
     2325    // reduction to non-zero new poly
     2326    if (red_result == 1)
     2327    {
     2328      // get the polynomial (canonicalize bucket, make sure P.p is set)
     2329      strat->P.GetP(strat->lmBin);
     2330      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
     2331      // but now, for entering S, T, we reset it
     2332      // in the inhomogeneous case: FDeg == pFDeg
     2333      if (strat->homog) strat->initEcart(&(strat->P));
     2334
     2335      /* statistic */
     2336      if (TEST_OPT_PROT) PrintS("s");
     2337
     2338      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
     2339
     2340#ifdef KDEBUG
     2341#if MYTEST
     2342      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
     2343#endif /* MYTEST */
     2344#endif /* KDEBUG */
     2345
     2346      // reduce the tail and normalize poly
     2347      // in the ring case we cannot expect LC(f) = 1,
     2348      // therefore we call pContent instead of pNorm
     2349#if F5CTAILRED
     2350      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
     2351      {
     2352        strat->P.pCleardenom();
     2353        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     2354        {
     2355          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     2356          strat->P.pCleardenom();
     2357        }
     2358      }
     2359      else
     2360      {
     2361        strat->P.pNorm();
     2362        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     2363          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     2364      }
     2365#endif
     2366#ifdef KDEBUG
     2367      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
     2368#if MYTEST
     2369//#if 1
     2370      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
     2371#endif /* MYTEST */
     2372#endif /* KDEBUG */
     2373
     2374      // min_std stuff
     2375      if ((strat->P.p1==NULL) && (strat->minim>0))
     2376      {
     2377        if (strat->minim==1)
     2378        {
     2379          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
     2380          p_Delete(&strat->P.p2, currRing, strat->tailRing);
     2381        }
     2382        else
     2383        {
     2384          strat->M->m[minimcnt]=strat->P.p2;
     2385          strat->P.p2=NULL;
     2386        }
     2387        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
     2388          pNext(strat->M->m[minimcnt])
     2389            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
     2390                strat->tailRing, currRing,
     2391                currRing->PolyBin);
     2392        minimcnt++;
     2393      }
     2394
     2395      // enter into S, L, and T
     2396      // here we need to recompute new signatures, but those are trivial ones
     2397      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
     2398      enterT(strat->P, strat);
     2399      // posInS only depends on the leading term
     2400      strat->enterS(strat->P, pos, strat, strat->tl);
     2401//#if 1
     2402#ifdef DEBUGF5
     2403      Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
     2404      pWrite(pHead(strat->S[strat->sl]));
     2405      pWrite(strat->sig[strat->sl]);
     2406#endif
     2407      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
     2408      //      Print("[%d]",hilbeledeg);
     2409      if (strat->P.lcm!=NULL)
     2410#ifdef HAVE_RINGS
     2411        pLmDelete(strat->P.lcm);
     2412#else
     2413      pLmFree(strat->P.lcm);
     2414#endif
     2415      if (strat->sl>srmax) srmax = strat->sl;
     2416    }
     2417    else
     2418    {
     2419      // adds signature of the zero reduction to
     2420      // strat->syz. This is the leading term of
     2421      // syzygy and can be used in syzCriterion()
     2422      // the signature is added if and only if the
     2423      // pair was not detected by the rewritten criterion in strat->red = redSig
     2424      if (strat->P.p1 == NULL && strat->minim > 0)
     2425      {
     2426        p_Delete(&strat->P.p2, currRing, strat->tailRing);
     2427      }
     2428    }
     2429
     2430#ifdef KDEBUG
     2431    memset(&(strat->P), 0, sizeof(strat->P));
     2432#endif /* KDEBUG */
     2433  }
     2434  int cc = 0;
     2435  while (cc<strat->tl+1)
     2436  {
     2437    strat->T[cc].sig        = pOne();
     2438    p_SetComp(strat->T[cc].sig,cc+1,currRing);
     2439    strat->T[cc].sevSig     = pGetShortExpVector(strat->T[cc].sig);
     2440    strat->sig[cc]          = strat->T[cc].sig;
     2441    strat->sevSig[cc]       = strat->T[cc].sevSig;
     2442    strat->T[cc].is_sigsafe = TRUE; 
     2443    cc++;
     2444  }
     2445  strat->max_lower_index = strat->tl;
     2446  // set current signature index of upcoming iteration step
     2447  // NOTE:  this needs to be set here, as otherwise initSyzRules cannot compute
     2448  //        the corresponding syzygy rules correctly
     2449  strat->currIdx = cc+1;
     2450  for (int cd=strat->Ll; cd>=0; cd--)
     2451  {
     2452    p_SetComp(strat->L[cd].sig,cc+1,currRing);
     2453    cc++;
     2454  }
     2455//#if 1
     2456#if DEBUGF5
     2457  Print("------------------- STRAT S ---------------------\n");
     2458  cc = 0;
     2459  while (cc<strat->tl+1)
     2460  {
     2461    pWrite(pHead(strat->S[cc]));
     2462    pWrite(strat->sig[cc]);
     2463    printf("- - - - - -\n");
     2464    cc++;
     2465  }
     2466  Print("-------------------------------------------------\n");
     2467  Print("------------------- STRAT T ---------------------\n");
     2468  cc = 0;
     2469  while (cc<strat->tl+1)
     2470  {
     2471    pWrite(pHead(strat->T[cc].p));
     2472    pWrite(strat->T[cc].sig);
     2473    printf("- - - - - -\n");
     2474    cc++;
     2475  }
     2476  Print("-------------------------------------------------\n");
     2477  Print("------------------- STRAT L ---------------------\n");
     2478  cc = 0;
     2479  while (cc<strat->Ll+1)
     2480  {
     2481    pWrite(pHead(strat->L[cc].p));
     2482    pWrite(pHead(strat->L[cc].p1));
     2483    pWrite(pHead(strat->L[cc].p2));
     2484    pWrite(strat->L[cc].sig);
     2485    printf("- - - - - -\n");
     2486    cc++;
     2487  }
     2488  Print("-------------------------------------------------\n");
     2489  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
     2490#endif
     2491
     2492}
     2493#endif
    14492494
    14502495/* shiftgb stuff */
  • kernel/kutil.cc

    rcffd3e r9e806f  
    2929#undef KDEBUG
    3030#define KDEBUG 2
     31#endif
     32
     33#ifdef DEBUGF5
     34#undef DEBUGF5
     35//#define DEBUGF5 1
    3136#endif
    3237
     
    7277#endif
    7378
     79#ifdef DEBUGF5
     80#undef DEBUGF5
     81#define DEBUGF5 2
     82#endif
     83
    7484denominator_list DENOMINATOR_LIST=NULL;
    7585
     
    916926    strat->sevS[j] = strat->sevS[j+1];
    917927    strat->S_2_R[j] = strat->S_2_R[j+1];
     928  }
     929#endif
     930  if (strat->lenS!=NULL)
     931  {
     932#ifdef ENTER_USE_MEMMOVE
     933    memmove(&(strat->lenS[i]),&(strat->lenS[i+1]),(strat->sl - i)*sizeof(int));
     934#else
     935    for (j=i; j<strat->sl; j++) strat->lenS[j] = strat->lenS[j+1];
     936#endif
     937  }
     938  if (strat->lenSw!=NULL)
     939  {
     940#ifdef ENTER_USE_MEMMOVE
     941    memmove(&(strat->lenSw[i]),&(strat->lenSw[i+1]),(strat->sl - i)*sizeof(wlen_type));
     942#else
     943    for (j=i; j<strat->sl; j++) strat->lenSw[j] = strat->lenSw[j+1];
     944#endif
     945  }
     946  if (strat->fromQ!=NULL)
     947  {
     948#ifdef ENTER_USE_MEMMOVE
     949    memmove(&(strat->fromQ[i]),&(strat->fromQ[i+1]),(strat->sl - i)*sizeof(int));
     950#else
     951    for (j=i; j<strat->sl; j++)
     952    {
     953      strat->fromQ[j] = strat->fromQ[j+1];
     954    }
     955#endif
     956  }
     957  strat->S[strat->sl] = NULL;
     958  strat->sl--;
     959}
     960
     961
     962/*2
     963*cancels the i-th polynomial in the standardbase s
     964*/
     965void deleteInSSba (int i,kStrategy strat)
     966{
     967#ifdef ENTER_USE_MEMMOVE
     968  memmove(&(strat->S[i]), &(strat->S[i+1]), (strat->sl - i)*sizeof(poly));
     969  memmove(&(strat->sig[i]), &(strat->sig[i+1]), (strat->sl - i)*sizeof(poly));
     970  memmove(&(strat->ecartS[i]),&(strat->ecartS[i+1]),(strat->sl - i)*sizeof(int));
     971  memmove(&(strat->sevS[i]),&(strat->sevS[i+1]),(strat->sl - i)*sizeof(unsigned long));
     972  memmove(&(strat->sevSig[i]),&(strat->sevSig[i+1]),(strat->sl - i)*sizeof(unsigned long));
     973  memmove(&(strat->S_2_R[i]),&(strat->S_2_R[i+1]),(strat->sl - i)*sizeof(int));
     974  memmove(&(strat->fromS[i]),&(strat->fromS[i+1]),(strat->sl - i)*sizeof(int));
     975#else
     976  int j;
     977  for (j=i; j<strat->sl; j++)
     978  {
     979    strat->S[j] = strat->S[j+1];
     980    strat->sig[j] = strat->sig[j+1];
     981    strat->ecartS[j] = strat->ecartS[j+1];
     982    strat->sevS[j] = strat->sevS[j+1];
     983    strat->sevSig[j] = strat->sevSig[j+1];
     984    strat->S_2_R[j] = strat->S_2_R[j+1];
     985    strat->fromS[j] = strat->fromS[j+1];
    918986  }
    919987#endif
     
    16681736
    16691737/*2
     1738* put the pair (s[i],p)  into the set B, ecart=ecart(p)
     1739* NOTE: here we need to add the signature-based criteria
     1740*/
     1741
     1742void enterOnePairSig (int i, poly p, poly pSig, int from, int ecart, int isFromQ, kStrategy strat, int atR = -1)
     1743{
     1744  assume(i<=strat->sl);
     1745  if (strat->interred_flag) return;
     1746
     1747  int      l;
     1748  poly m1 = NULL,m2 = NULL; // we need the multipliers for the s-polynomial to compute
     1749              // the corresponding signatures for criteria checks
     1750  LObject  Lp;
     1751  poly last;
     1752  poly pSigMult = p_Copy(pSig,currRing);
     1753  poly sSigMult = p_Copy(strat->sig[i],currRing);
     1754  unsigned long pSigMultNegSev,sSigMultNegSev;
     1755  Lp.i_r = -1;
     1756
     1757#ifdef KDEBUG
     1758  Lp.ecart=0; Lp.length=0;
     1759#endif
     1760  /*- computes the lcm(s[i],p) -*/
     1761  Lp.lcm = pInit();
     1762  k_GetLeadTerms(p,strat->S[i],currRing,m1,m2,currRing);
     1763#ifndef HAVE_RATGRING
     1764  pLcm(p,strat->S[i],Lp.lcm);
     1765#elif defined(HAVE_RATGRING)
     1766  //  if (rIsRatGRing(currRing))
     1767  pLcmRat(p,strat->S[i],Lp.lcm, currRing->real_var_start); // int rat_shift
     1768#endif
     1769  pSetm(Lp.lcm);
     1770
     1771  // set coeffs of multipliers m1 and m2
     1772  pSetCoeff0(m1, nInit(1));
     1773  pSetCoeff0(m2, nInit(1));
     1774//#if 1
     1775#ifdef DEBUGF5
     1776  Print("P1  ");
     1777  pWrite(pHead(p));
     1778  Print("FROM: %d\n", from);
     1779  Print("P2  ");
     1780  pWrite(pHead(strat->S[i]));
     1781  Print("FROM: %d\n", strat->fromS[i]);
     1782  Print("M1  ");
     1783  pWrite(m1);
     1784  Print("M2  ");
     1785  pWrite(m2);
     1786#endif
     1787  // get multiplied signatures for testing
     1788  pSigMult = currRing->p_Procs->pp_Mult_mm(pSigMult,m1,currRing,last);
     1789  pSigMultNegSev = ~p_GetShortExpVector(pSigMult,currRing);
     1790  sSigMult = currRing->p_Procs->pp_Mult_mm(sSigMult,m2,currRing,last);
     1791  sSigMultNegSev = ~p_GetShortExpVector(sSigMult,currRing);
     1792 
     1793  pDelete (&m1);
     1794  pDelete (&m2);
     1795
     1796//#if 1
     1797#ifdef DEBUGF5
     1798  Print("----------------\n");
     1799  pWrite(pSigMult);
     1800  pWrite(sSigMult);
     1801  Print("----------------\n");
     1802#endif
     1803  // testing by syzCrit = F5 Criterion
     1804  // testing by rewCrit1 = Rewritten Criterion
     1805  if  ( strat->syzCrit(pSigMult,pSigMultNegSev,strat) ||
     1806        strat->syzCrit(sSigMult,sSigMultNegSev,strat)
     1807        || strat->rewCrit1(sSigMult,sSigMultNegSev,strat,i+1)
     1808      )
     1809  {
     1810    pDelete(&pSigMult);
     1811    pDelete(&sSigMult);
     1812    strat->cp++;
     1813    pLmFree(Lp.lcm);
     1814    Lp.lcm=NULL;
     1815    return;
     1816  }
     1817  // in any case Lp is checked up to the next strat->P which is added
     1818  // to S right after this critical pair creation.
     1819  // NOTE: this even holds if the 2nd generator gives the bigger signature
     1820  //       moreover, this improves rewCriterion,
     1821  //       i.e. strat->checked > strat->from if and only if the 2nd generator
     1822  //       gives the bigger signature.
     1823  Lp.checked = strat->sl+1;
     1824  int sigCmp = p_LmCmp(pSigMult,sSigMult,currRing);
     1825//#if 1
     1826#if DEBUGF5
     1827  printf("IN PAIR GENERATION - COMPARING SIGS: %d\n",sigCmp);
     1828  pWrite(pSigMult);
     1829  pWrite(sSigMult);
     1830#endif
     1831  if(sigCmp==0)
     1832  {
     1833    // printf("!!!!   EQUAL SIGS   !!!!\n");
     1834    // pSig = sSig, delete element due to Rewritten Criterion
     1835    strat->cp++;
     1836    pDelete(&pSigMult);
     1837    pDelete(&sSigMult);
     1838    pLmFree(Lp.lcm);
     1839    Lp.lcm=NULL;
     1840    return;
     1841  }
     1842  // at this point it is clear that the pair will be added to L, since it has
     1843  // passed all tests up to now
     1844
     1845  // store from which element this pair comes from for further tests
     1846  Lp.from = strat->sl+1;   
     1847  if(sigCmp==currRing->OrdSgn)
     1848  {
     1849    // pSig > sSig
     1850    pDelete (&sSigMult);
     1851    Lp.sig    = pSigMult;
     1852    Lp.sevSig = ~pSigMultNegSev;
     1853  }
     1854  else
     1855  {
     1856    // pSig < sSig
     1857    pDelete (&pSigMult);
     1858    Lp.sig    = sSigMult;
     1859    Lp.sevSig = ~sSigMultNegSev;
     1860  }
     1861#if DEBUGF5
     1862  printf("SIGNATURE OF PAIR:  ");
     1863  pWrite(Lp.sig);
     1864#endif
     1865  /*
     1866  *the pair (S[i],p) enters B if the spoly != 0
     1867  */
     1868  /*-  compute the short s-polynomial -*/
     1869  if (strat->fromT && !TEST_OPT_INTSTRATEGY)
     1870    pNorm(p);
     1871
     1872  if ((strat->S[i]==NULL) || (p==NULL))
     1873    return;
     1874
     1875  if ((strat->fromQ!=NULL) && (isFromQ!=0) && (strat->fromQ[i]!=0))
     1876    Lp.p=NULL;
     1877  else
     1878  {
     1879    #ifdef HAVE_PLURAL
     1880    if ( rIsPluralRing(currRing) )
     1881    {
     1882      if(pHasNotCF(p, strat->S[i]))
     1883      {
     1884         if(ncRingType(currRing) == nc_lie)
     1885         {
     1886             // generalized prod-crit for lie-type
     1887             strat->cp++;
     1888             Lp.p = nc_p_Bracket_qq(pCopy(p),strat->S[i], currRing);
     1889         }
     1890         else
     1891        if( ALLOW_PROD_CRIT(strat) )
     1892        {
     1893            // product criterion for homogeneous case in SCA
     1894            strat->cp++;
     1895            Lp.p = NULL;
     1896        }
     1897        else
     1898        {
     1899          Lp.p = // nc_CreateSpoly(strat->S[i],p,currRing);
     1900                nc_CreateShortSpoly(strat->S[i], p, currRing);
     1901
     1902          assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
     1903          pNext(Lp.p) = strat->tail; // !!!
     1904        }
     1905      }
     1906      else
     1907      {
     1908        Lp.p = // nc_CreateSpoly(strat->S[i],p,currRing);
     1909              nc_CreateShortSpoly(strat->S[i], p, currRing);
     1910
     1911        assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
     1912        pNext(Lp.p) = strat->tail; // !!!
     1913
     1914      }
     1915
     1916
     1917#if MYTEST
     1918      if (TEST_OPT_DEBUG)
     1919      {
     1920        PrintS("enterOnePairNormal::\n strat->S[i]: "); pWrite(strat->S[i]);
     1921        PrintS("p: "); pWrite(p);
     1922        PrintS("SPoly: "); pWrite(Lp.p);
     1923      }
     1924#endif
     1925
     1926    }
     1927    else
     1928    #endif
     1929    {
     1930      assume(!rIsPluralRing(currRing));
     1931      Lp.p = ksCreateShortSpoly(strat->S[i], p, strat->tailRing);
     1932#if MYTEST
     1933      if (TEST_OPT_DEBUG)
     1934      {
     1935        PrintS("enterOnePairNormal::\n strat->S[i]: "); pWrite(strat->S[i]);
     1936        PrintS("p: "); pWrite(p);
     1937        PrintS("commutative SPoly: "); pWrite(Lp.p);
     1938      }
     1939#endif
     1940
     1941      }
     1942  }
     1943  if (Lp.p == NULL)
     1944  {
     1945    /*- the case that the s-poly is 0 -*/
     1946    if (strat->pairtest==NULL) initPairtest(strat);
     1947    strat->pairtest[i] = TRUE;/*- hint for spoly(S^[i],p)=0 -*/
     1948    strat->pairtest[strat->sl+1] = TRUE;
     1949    /*hint for spoly(S[i],p) == 0 for some i,0 <= i <= sl*/
     1950    /*
     1951    *suppose we have (s,r),(r,p),(s,p) and spoly(s,p) == 0 and (r,p) is
     1952    *still in B (i.e. lcm(r,p) == lcm(s,p) or the leading term of s does not
     1953    *devide lcm(r,p)). In the last case (s,r) can be canceled if the leading
     1954    *term of p devides the lcm(s,r)
     1955    *(this canceling should be done here because
     1956    *the case lcm(s,p) == lcm(s,r) is not covered in chainCrit)
     1957    *the first case is handeled in chainCrit
     1958    */
     1959    if (Lp.lcm!=NULL) pLmFree(Lp.lcm);
     1960  }
     1961  else
     1962  {
     1963    /*- the pair (S[i],p) enters B -*/
     1964    Lp.p1 = strat->S[i];
     1965    Lp.p2 = p;
     1966
     1967    if (
     1968        (!rIsPluralRing(currRing))
     1969//      ||  (rIsPluralRing(currRing) && (ncRingType(currRing) != nc_lie))
     1970       )
     1971    {
     1972      assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
     1973      pNext(Lp.p) = strat->tail; // !!!
     1974    }
     1975
     1976    if (atR >= 0)
     1977    {
     1978      Lp.i_r1 = strat->S_2_R[i];
     1979      Lp.i_r2 = atR;
     1980    }
     1981    else
     1982    {
     1983      Lp.i_r1 = -1;
     1984      Lp.i_r2 = -1;
     1985    }
     1986    strat->initEcartPair(&Lp,strat->S[i],p,strat->ecartS[i],ecart);
     1987
     1988    if (TEST_OPT_INTSTRATEGY)
     1989    {
     1990      if (!rIsPluralRing(currRing))
     1991        nDelete(&(Lp.p->coef));
     1992    }
     1993
     1994    l = strat->posInLSba(strat->B,strat->Bl,&Lp,strat);
     1995    enterL(&strat->B,&strat->Bl,&strat->Bmax,Lp,l);
     1996  }
     1997}
     1998
     1999/*2
    16702000* put the pair (s[i],p) into the set L, ecart=ecart(p)
    16712001* in the case that s forms a SB of (s)
     
    17712101  {
    17722102    j = strat->posInL(strat->L,j,&(strat->B[i]),strat);
     2103    enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
     2104  }
     2105  strat->Bl = -1;
     2106}
     2107
     2108/*2
     2109* merge set B into L
     2110*/
     2111void kMergeBintoLSba(kStrategy strat)
     2112{
     2113  int j=strat->Ll+strat->Bl+1;
     2114  if (j>strat->Lmax)
     2115  {
     2116    j=((j+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
     2117    strat->L = (LSet)omReallocSize(strat->L,strat->Lmax*sizeof(LObject),
     2118                                 j*sizeof(LObject));
     2119    strat->Lmax=j;
     2120  }
     2121  j = strat->Ll;
     2122  int i;
     2123  for (i=strat->Bl; i>=0; i--)
     2124  {
     2125    j = strat->posInLSba(strat->L,j,&(strat->B[i]),strat);
    17732126    enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
    17742127  }
     
    19882341      j--;
    19892342    }
     2343  }
     2344}
     2345/*2
     2346*the pairset B of pairs of type (s[i],p) is complete now. It will be updated
     2347*using the chain-criterion in B and L and enters B to L
     2348*/
     2349void chainCritSig (poly p,int ecart,kStrategy strat)
     2350{
     2351  int i,j,l;
     2352  kMergeBintoLSba(strat);
     2353  j = strat->Ll;
     2354  loop  /*cannot be changed into a for !!! */
     2355  {
     2356    if (j <= 0)
     2357    {
     2358      /*now L[0] cannot be canceled any more and the tail can be removed*/
     2359      if (strat->L[0].p2 == strat->tail) strat->L[0].p2 = p;
     2360      break;
     2361    }
     2362    if (strat->L[j].p2 == p)
     2363    {
     2364      i = j-1;
     2365      loop
     2366      {
     2367        if (i < 0)  break;
     2368        if ((strat->L[i].p2 == p) && pLmEqual(strat->L[j].lcm,strat->L[i].lcm))
     2369        {
     2370          /*L[i] could be canceled but we search for a better one to cancel*/
     2371          strat->c3++;
     2372          if (isInPairsetL(i-1,strat->L[j].p1,strat->L[i].p1,&l,strat)
     2373              && (pNext(strat->L[l].p) == strat->tail)
     2374              && (!pLmEqual(strat->L[i].p,strat->L[l].p))
     2375              && pDivisibleBy(p,strat->L[l].lcm))
     2376          {
     2377            /*
     2378             *"NOT equal(...)" because in case of "equal" the element L[l]
     2379             *is "older" and has to be from theoretical point of view behind
     2380             *L[i], but we do not want to reorder L
     2381             */
     2382            strat->L[i].p2 = strat->tail;
     2383            /*
     2384             *L[l] will be canceled, we cannot cancel L[i] later on,
     2385             *so we mark it with "tail"
     2386             */
     2387            deleteInL(strat->L,&strat->Ll,l,strat);
     2388            i--;
     2389          }
     2390          else
     2391          {
     2392            deleteInL(strat->L,&strat->Ll,i,strat);
     2393          }
     2394          j--;
     2395        }
     2396        i--;
     2397      }
     2398    }
     2399    else if (strat->L[j].p2 == strat->tail)
     2400    {
     2401      /*now L[j] cannot be canceled any more and the tail can be removed*/
     2402      strat->L[j].p2 = p;
     2403    }
     2404    j--;
    19902405  }
    19912406}
     
    23422757}
    23432758
     2759/*2
     2760*(s[0],h),...,(s[k],h) will be put to the pairset L
     2761*using signatures <= only for signature-based standard basis algorithms
     2762*/
     2763void initenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1)
     2764{
     2765
     2766  if ((strat->syzComp==0)
     2767  || (pGetComp(h)<=strat->syzComp))
     2768  {
     2769    int j;
     2770    BOOLEAN new_pair=FALSE;
     2771
     2772    if (pGetComp(h)==0)
     2773    {
     2774      /* for Q!=NULL: build pairs (f,q),(f1,f2), but not (q1,q2)*/
     2775      if ((isFromQ)&&(strat->fromQ!=NULL))
     2776      {
     2777        for (j=0; j<=k; j++)
     2778        {
     2779          if (!strat->fromQ[j])
     2780          {
     2781            new_pair=TRUE;
     2782            enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
     2783          //Print("j:%d, Ll:%d\n",j,strat->Ll);
     2784          }
     2785        }
     2786      }
     2787      else
     2788      {
     2789        new_pair=TRUE;
     2790        for (j=0; j<=k; j++)
     2791        {
     2792          enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
     2793          //Print("j:%d, Ll:%d\n",j,strat->Ll);
     2794        }
     2795      }
     2796    }
     2797    else
     2798    {
     2799      for (j=0; j<=k; j++)
     2800      {
     2801        if ((pGetComp(h)==pGetComp(strat->S[j]))
     2802        || (pGetComp(strat->S[j])==0))
     2803        {
     2804          new_pair=TRUE;
     2805          enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
     2806        //Print("j:%d, Ll:%d\n",j,strat->Ll);
     2807        }
     2808      }
     2809    }
     2810
     2811    if (new_pair)
     2812    {
     2813#ifdef HAVE_RATGRING
     2814      if (currRing->real_var_start>0)
     2815        chainCritPart(h,ecart,strat);
     2816      else
     2817#endif
     2818      strat->chainCrit(h,ecart,strat);
     2819    }
     2820  }
     2821}
     2822
    23442823#ifdef HAVE_RINGS
    23452824/*2
     
    31003579  }
    31013580 // PrintS("end enterpairs\n");
     3581}
     3582
     3583/*2
     3584*(s[0],h),...,(s[k],h) will be put to the pairset L(via initenterpairs)
     3585*superfluous elements in S will be deleted
     3586*this is a special variant of signature-based algorithms including the
     3587*signatures for criteria checks
     3588*/
     3589void enterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR)
     3590{
     3591int j=pos;
     3592
     3593#ifdef HAVE_RINGS
     3594assume (!rField_is_Ring(currRing));
     3595#endif
     3596
     3597initenterpairsSig(h,hSig,hFrom,k,ecart,0,strat, atR);
     3598if ( (!strat->fromT)
     3599&& ((strat->syzComp==0)
     3600  ||(pGetComp(h)<=strat->syzComp)))
     3601{
     3602  //Print("start clearS k=%d, pos=%d, sl=%d\n",k,pos,strat->sl);
     3603  unsigned long h_sev = pGetShortExpVector(h);
     3604  loop
     3605  {
     3606    if (j > k) break;
     3607    clearS(h,h_sev, &j,&k,strat);
     3608    j++;
     3609  }
     3610  //Print("end clearS sl=%d\n",strat->sl);
     3611}
     3612// PrintS("end enterpairs\n");
    31023613}
    31033614
     
    39534464* e is the ecart of p
    39544465* set[length] is the smallest element in set with respect
     4466* to the signature order
     4467*/
     4468int posInLSig (const LSet set, const int length,
     4469            LObject* p,const kStrategy strat)
     4470{
     4471if (length<0) return 0;
     4472if (pLmCmp(set[length].sig,p->sig)== currRing->OrdSgn)
     4473  return length+1;
     4474
     4475int i;
     4476int an = 0;
     4477int en= length;
     4478loop
     4479{
     4480  if (an >= en-1)
     4481  {
     4482    if (pLmCmp(set[an].sig,p->sig) == currRing->OrdSgn) return en;
     4483    return an;
     4484  }
     4485  i=(an+en) / 2;
     4486  if (pLmCmp(set[i].sig,p->sig) == currRing->OrdSgn) an=i;
     4487  else                                      en=i;
     4488  /*aend. fuer lazy == in !=- machen */
     4489}
     4490}
     4491
     4492/*2
     4493*
     4494* is only used in F5C, must ensure that the interreduction process does add new
     4495* critical pairs to strat->L only behind all other critical pairs which are
     4496* still in strat->L!
     4497*/
     4498int posInLF5C (const LSet set, const int length,
     4499            LObject* p,const kStrategy strat)
     4500{
     4501  return strat->Ll+1;
     4502}
     4503
     4504/*2
     4505* looks up the position of polynomial p in set
     4506* e is the ecart of p
     4507* set[length] is the smallest element in set with respect
    39554508* to the ordering-procedure totaldegree,pComp
    39564509*/
     
    43594912}
    43604913
     4914/*
     4915 * SYZYGY CRITERION for signature-based standard basis algorithms
     4916 */
     4917BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
     4918{
     4919//#if 1
     4920#ifdef DEBUGF5
     4921  Print("syzygy criterion checks:  ");
     4922  pWrite(sig);
     4923#endif
     4924  for (int k=0; k<strat->syzl; k++)
     4925  {
     4926//#if 1
     4927#ifdef DEBUGF5
     4928    Print("checking with: %d --  ",k);
     4929    pWrite(pHead(strat->syz[k]));
     4930#endif
     4931    if (p_LmShortDivisibleBy(strat->syz[k], strat->sevSyz[k], sig, not_sevSig, currRing))
     4932    {
     4933//#if 1
     4934#ifdef DEBUGF5
     4935      printf("DELETE!\n");
     4936#endif
     4937      return TRUE;
     4938    }
     4939  }
     4940  return FALSE;
     4941}
     4942
     4943/*
     4944 * SYZYGY CRITERION for signature-based standard basis algorithms
     4945 */
     4946BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat)
     4947{
     4948//#if 1
     4949#ifdef DEBUGF5
     4950  Print("syzygy criterion checks:  ");
     4951  pWrite(sig);
     4952#endif
     4953  int comp = p_GetComp(sig, currRing);
     4954  int min, max;
     4955  if (comp<=1)
     4956    return FALSE;
     4957  else
     4958  {
     4959    min = strat->syzIdx[comp-2];
     4960    //printf("SYZIDX %d/%d\n",strat->syzIdx[comp-2],comp-2);
     4961    //printf("SYZIDX %d/%d\n",strat->syzIdx[comp-1],comp-1);
     4962    //printf("SYZIDX %d/%d\n",strat->syzIdx[comp],comp);
     4963    if (comp == strat->currIdx)
     4964    {
     4965      max = strat->syzl;
     4966    }
     4967    else
     4968    {
     4969      max = strat->syzIdx[comp-1];
     4970    }
     4971    for (int k=min; k<max; k++)
     4972    {
     4973#ifdef DEBUGF5
     4974      printf("COMP %d/%d - MIN %d - MAX %d - SYZL %ld\n",comp,strat->currIdx,min,max,strat->syzl);
     4975      Print("checking with: %d --  ",k);
     4976      pWrite(pHead(strat->syz[k]));
     4977#endif
     4978      if (p_LmShortDivisibleBy(strat->syz[k], strat->sevSyz[k], sig, not_sevSig, currRing))
     4979        return TRUE;
     4980    }
     4981    return FALSE;
     4982  }
     4983}
     4984
     4985/*
     4986 * REWRITTEN CRITERION for signature-based standard basis algorithms
     4987 */
     4988BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start=0)
     4989{
     4990  //printf("Faugere Rewritten Criterion\n");
     4991//#if 1
     4992#ifdef DEBUGF5
     4993  printf("rewritten criterion checks:  ");
     4994  pWrite(sig);
     4995#endif
     4996  //for(int k = start; k<strat->sl+1; k++)
     4997  for(int k = strat->sl; k>start; k--)
     4998  {
     4999//#if 1
     5000#ifdef DEBUGF5
     5001    Print("checking with:  ");
     5002    pWrite(strat->sig[k]);
     5003    pWrite(pHead(strat->S[k]));
     5004#endif
     5005    if (p_LmShortDivisibleBy(strat->sig[k], strat->sevSig[k], sig, not_sevSig, currRing))
     5006    //if (p_LmEqual(strat->sig[k], sig, currRing))
     5007    {
     5008//#if 1
     5009#ifdef DEBUGF5
     5010      printf("DELETE!\n");
     5011#endif
     5012      return TRUE;
     5013    }
     5014  }
     5015#ifdef DEBUGF5
     5016  Print("ALL ELEMENTS OF S\n----------------------------------------\n");
     5017  for(int kk = 0; kk<strat->sl+1; kk++)
     5018  {
     5019    pWrite(pHead(strat->S[kk]));
     5020  }
     5021  Print("------------------------------\n");
     5022#endif
     5023  return FALSE;
     5024}
     5025
     5026/*
     5027 * REWRITTEN CRITERION for signature-based standard basis algorithms
     5028 ***************************************************************************
     5029 * TODO:This should become the version of Arri/Perry resp. Bjarke/Stillman *
     5030 ***************************************************************************
     5031 */
     5032
     5033// real implementation of arri's rewritten criterion, only called once in
     5034// kstd2.cc, right before starting reduction
     5035// IDEA:  Arri says that it is enough to consider 1 polynomial for each unique
     5036//        signature appearing during the computations. Thus we first of all go
     5037//        through strat->L and delete all other pairs of the same signature,
     5038//        keeping only the one with least possible leading monomial. After this
     5039//        we check if we really need to compute this critical pair at all: There
     5040//        can be elements already in strat->S whose signatures divide the
     5041//        signature of the critical pair in question and whose multiplied
     5042//        leading monomials are smaller than the leading monomial of the
     5043//        critical pair. In this situation we can discard the critical pair
     5044//        completely.
     5045BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start=0)
     5046{
     5047  //printf("Arri Rewritten Criterion\n");
     5048  while (strat->Ll > 0 && pLmEqual(strat->L[strat->Ll].sig,strat->P.sig))
     5049  {
     5050    // deletes the short spoly
     5051#ifdef HAVE_RINGS
     5052    if (rField_is_Ring(currRing))
     5053      pLmDelete(strat->L[strat->Ll].p);
     5054    else
     5055#endif
     5056      pLmFree(strat->L[strat->Ll].p);
     5057
     5058    // TODO: needs some masking
     5059    // TODO: masking needs to vanish once the signature
     5060    //       sutff is completely implemented
     5061    strat->L[strat->Ll].p = NULL;
     5062    poly m1 = NULL, m2 = NULL;
     5063
     5064    // check that spoly creation is ok
     5065    while (strat->tailRing != currRing &&
     5066          !kCheckSpolyCreation(&(strat->L[strat->Ll]), strat, m1, m2))
     5067    {
     5068      assume(m1 == NULL && m2 == NULL);
     5069      // if not, change to a ring where exponents are at least
     5070      // large enough
     5071      if (!kStratChangeTailRing(strat))
     5072      {
     5073        WerrorS("OVERFLOW...");
     5074        break;
     5075      }
     5076    }
     5077    // create the real one
     5078    ksCreateSpoly(&(strat->L[strat->Ll]), NULL, strat->use_buckets,
     5079                  strat->tailRing, m1, m2, strat->R);
     5080    if (strat->P.GetLmCurrRing() == NULL)
     5081    {
     5082      deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
     5083    }
     5084    if (strat->L[strat->Ll].GetLmCurrRing() == NULL)
     5085    {
     5086      strat->P.Delete();
     5087      strat->P = strat->L[strat->Ll];
     5088      strat->Ll--;
     5089    }
     5090
     5091    if (strat->P.GetLmCurrRing() != NULL && strat->L[strat->Ll].GetLmCurrRing() != NULL)
     5092    {
     5093      if (pLmCmp(strat->P.GetLmCurrRing(),strat->L[strat->Ll].GetLmCurrRing()) == -1)
     5094      {
     5095        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
     5096      }
     5097      else
     5098      {
     5099        strat->P.Delete();
     5100        strat->P = strat->L[strat->Ll];
     5101        strat->Ll--;
     5102      }
     5103    }
     5104  }
     5105  for (int ii=strat->sl; ii>-1; ii--)
     5106  {
     5107    if (p_LmShortDivisibleBy(strat->sig[ii], strat->sevSig[ii], strat->P.sig, ~strat->P.sevSig, currRing))
     5108    {
     5109      if (!(pLmCmp(ppMult_mm(strat->P.sig,pHead(strat->S[ii])),ppMult_mm(strat->sig[ii],strat->P.GetLmCurrRing())) == 1))
     5110      {
     5111        strat->P.Delete();
     5112        return TRUE;
     5113      }
     5114    }
     5115  }
     5116  return FALSE;
     5117}
     5118
    43615119/***************************************************************
    43625120 *
     
    50195777}
    50205778
     5779void initSLSba (ideal F, ideal Q,kStrategy strat)
     5780{
     5781  int   i,j,pos, ctr=0, ps=0;
     5782  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
     5783  else i=setmaxT;
     5784  strat->ecartS =   initec(i);
     5785  strat->fromS  =   initec(i);
     5786  strat->sevS   =   initsevS(i);
     5787  strat->sevSig =   initsevS(i);
     5788  strat->S_2_R  =   initS_2_R(i);
     5789  strat->fromQ  =   NULL;
     5790  strat->Shdl   =   idInit(i,F->rank);
     5791  strat->S      =   strat->Shdl->m;
     5792  strat->sig    =   (poly *)omAlloc0(i*sizeof(poly));
     5793  if (!strat->incremental)
     5794  {
     5795    strat->syz    = (poly *)omAlloc0(i*sizeof(poly));
     5796    strat->sevSyz = initsevS(i);
     5797    strat->syzmax = i;
     5798    strat->syzl   = 0;
     5799  }
     5800  /*- put polys into S -*/
     5801  if (Q!=NULL)
     5802  {
     5803    strat->fromQ=initec(i);
     5804    memset(strat->fromQ,0,i*sizeof(int));
     5805    for (i=0; i<IDELEMS(Q); i++)
     5806    {
     5807      if (Q->m[i]!=NULL)
     5808      {
     5809        LObject h;
     5810        h.p = pCopy(Q->m[i]);
     5811        if (currRing->OrdSgn==-1)
     5812        {
     5813          deleteHC(&h,strat);
     5814        }
     5815        if (TEST_OPT_INTSTRATEGY)
     5816        {
     5817          //pContent(h.p);
     5818          h.pCleardenom(); // also does a pContent
     5819        }
     5820        else
     5821        {
     5822          h.pNorm();
     5823        }
     5824        if (h.p!=NULL)
     5825        {
     5826          strat->initEcart(&h);
     5827          if (strat->sl==-1)
     5828            pos =0;
     5829          else
     5830          {
     5831            pos = posInS(strat,strat->sl,h.p,h.ecart);
     5832          }
     5833          h.sev = pGetShortExpVector(h.p);
     5834          strat->enterS(h,pos,strat,-1);
     5835          strat->fromQ[pos]=1;
     5836        }
     5837      }
     5838    }
     5839  }
     5840  for (i=0; i<IDELEMS(F); i++)
     5841  {
     5842    if (F->m[i]!=NULL)
     5843    {
     5844      LObject h;
     5845      h.p = pCopy(F->m[i]);
     5846      h.sig = pOne();
     5847      //h.sig = pInit();
     5848      //p_SetCoeff(h.sig,nInit(1),currRing);
     5849      p_SetComp(h.sig,i+1,currRing);
     5850      // if we are working with the Schreyer order we generate it
     5851      // by multiplying the initial signatures with the leading monomial
     5852      // of the corresponding initial polynomials generating the ideal
     5853      // => we can keep the underlying monomial order and get a Schreyer
     5854      //    order without any bigger overhead
     5855      if (!strat->incremental)
     5856      {
     5857        p_ExpVectorAdd (h.sig,F->m[i],currRing); 
     5858      }
     5859      h.sevSig = pGetShortExpVector(h.sig);
     5860#ifdef DEBUGF5
     5861      pWrite(h.p);
     5862      pWrite(h.sig);
     5863#endif
     5864      if (h.p!=NULL)
     5865      {
     5866        if (currRing->OrdSgn==-1)
     5867        {
     5868          cancelunit(&h);  /*- tries to cancel a unit -*/
     5869          deleteHC(&h, strat);
     5870        }
     5871        if (h.p!=NULL)
     5872        {
     5873          if (TEST_OPT_INTSTRATEGY)
     5874          {
     5875            //pContent(h.p);
     5876            h.pCleardenom(); // also does a pContent
     5877          }
     5878          else
     5879          {
     5880            h.pNorm();
     5881          }
     5882          strat->initEcart(&h);
     5883          if (strat->Ll==-1)
     5884            pos =0;
     5885          else
     5886            pos = strat->posInLSba(strat->L,strat->Ll,&h,strat);
     5887          h.sev = pGetShortExpVector(h.p);
     5888          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
     5889        }
     5890      }
     5891      /*
     5892      if (!strat->incremental)
     5893      {
     5894        for(j=0;j<i;j++)
     5895        {
     5896          strat->syz[ctr] = pCopy(F->m[j]);
     5897          p_SetCompP(strat->syz[ctr],i+1,currRing);
     5898          // add LM(F->m[i]) to the signature to get a Schreyer order
     5899          // without changing the underlying polynomial ring at all
     5900          p_ExpVectorAdd (strat->syz[ctr],F->m[i],currRing); 
     5901          // since p_Add_q() destroys all input
     5902          // data we need to recreate help
     5903          // each time
     5904          poly help = pCopy(F->m[i]);
     5905          p_SetCompP(help,j+1,currRing);
     5906          pWrite(strat->syz[ctr]);
     5907          pWrite(help);
     5908          printf("%d\n",pLmCmp(strat->syz[ctr],help));
     5909          strat->syz[ctr] = p_Add_q(strat->syz[ctr],help,currRing);
     5910          printf("%d. SYZ  ",ctr);
     5911          pWrite(strat->syz[ctr]);
     5912          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
     5913          ctr++;
     5914        }
     5915        strat->syzl = ps;
     5916      }
     5917      */
     5918    }
     5919  }
     5920  /*- test, if a unit is in F -*/
     5921
     5922  if ((strat->Ll>=0)
     5923#ifdef HAVE_RINGS
     5924       && n_IsUnit(pGetCoeff(strat->L[strat->Ll].p), currRing->cf)
     5925#endif
     5926       && pIsConstant(strat->L[strat->Ll].p))
     5927  {
     5928    while (strat->Ll>0) deleteInL(strat->L,&strat->Ll,strat->Ll-1,strat);
     5929  }
     5930}
     5931
     5932void initSyzRules (kStrategy strat)
     5933{
     5934  if( strat->S[0] )
     5935  {
     5936    if( strat->S[1] )
     5937    {
     5938      omFreeSize(strat->syzIdx,(strat->syzidxmax)*sizeof(int));
     5939      omFreeSize(strat->sevSyz,(strat->syzmax)*sizeof(unsigned long));
     5940      omFreeSize(strat->syz,(strat->syzmax)*sizeof(poly));
     5941    }
     5942    int i, j, k, diff, comp, comp_old, ps=0, ctr=0;
     5943    /************************************************************
     5944     * computing the length of the syzygy array needed
     5945     ***********************************************************/
     5946    for(i=1; i<=strat->sl; i++)
     5947    {
     5948      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
     5949      {
     5950        ps += i;
     5951      }
     5952    }
     5953    ps += strat->sl+1;
     5954    //comp              = pGetComp (strat->P.sig);
     5955    comp              = strat->currIdx;
     5956    strat->syzIdx     = initec(comp);
     5957    strat->sevSyz     = initsevS(ps);
     5958    strat->syz        = (poly *)omAlloc(ps*sizeof(poly));
     5959    strat->syzl       = strat->syzmax = ps;
     5960    strat->syzidxmax  = comp;
     5961#ifdef DEBUGF5 || DEBUGF51
     5962    printf("------------- GENERATING SYZ RULES NEW ---------------\n");
     5963#endif
     5964    i = 1;
     5965    j = 0;
     5966    /************************************************************
     5967     * generating the leading terms of the principal syzygies
     5968     ***********************************************************/
     5969    while (i <= strat->sl)
     5970    {
     5971      /**********************************************************
     5972       * principal syzygies start with component index 2
     5973       * the array syzIdx starts with index 0
     5974       * => the rules for a signature with component comp start
     5975       *    at strat->syz[strat->syzIdx[comp-2]] !
     5976       *********************************************************/
     5977      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
     5978      {
     5979        comp      = pGetComp(strat->sig[i]);
     5980        comp_old  = pGetComp(strat->sig[i-1]);
     5981        diff      = comp - comp_old - 1;
     5982        // diff should be zero, but sometimes also the initial generating
     5983        // elements of the input ideal reduce to zero. then there is an
     5984        // index-gap between the signatures. for these inbetween signatures we
     5985        // can safely set syzIdx[j] = 0 as no such element will be ever computed
     5986        // in the following.
     5987        // doing this, we keep the relation "j = comp - 2" alive, which makes
     5988        // jumps way easier when checking criteria
     5989        while (diff>0)
     5990        {
     5991          strat->syzIdx[j]  = 0;
     5992          diff--;
     5993          j++;
     5994        }
     5995        strat->syzIdx[j]  = ctr;
     5996        j++;
     5997        for (k = 0; k<i; k++)
     5998        {
     5999          poly p          = pOne();
     6000          pLcm(strat->S[k],strat->S[i],p);
     6001          strat->syz[ctr] = p;
     6002          p_SetCompP (strat->syz[ctr], comp, currRing);
     6003          poly q          = p_Copy(p, currRing);
     6004          q               = p_Neg (q, currRing);
     6005          p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
     6006          strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
     6007#ifdef DEBUGF5 || DEBUGF51
     6008          pWrite(strat->syz[ctr]);
     6009#endif
     6010          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
     6011          ctr++;
     6012        }
     6013      }
     6014      i++;
     6015    }
     6016    /**************************************************************
     6017    * add syzygies for upcoming first element of new iteration step
     6018    **************************************************************/
     6019    comp      = strat->currIdx;
     6020    comp_old  = pGetComp(strat->sig[i-1]);
     6021    diff      = comp - comp_old - 1;
     6022    // diff should be zero, but sometimes also the initial generating
     6023    // elements of the input ideal reduce to zero. then there is an
     6024    // index-gap between the signatures. for these inbetween signatures we
     6025    // can safely set syzIdx[j] = 0 as no such element will be ever computed
     6026    // in the following.
     6027    // doing this, we keep the relation "j = comp - 2" alive, which makes
     6028    // jumps way easier when checking criteria
     6029    while (diff>0)
     6030    {
     6031      strat->syzIdx[j]  = 0;
     6032      diff--;
     6033      j++;
     6034    }
     6035    strat->syzIdx[j]  = ctr;
     6036    for (k = 0; k<strat->sl+1; k++)
     6037    {
     6038      strat->syz[ctr] = p_Copy (pHead(strat->S[k]), currRing);
     6039      p_SetCompP (strat->syz[ctr], comp, currRing);
     6040      poly q          = p_Copy (pHead(strat->L[strat->Ll].p), currRing);
     6041      q               = p_Neg (q, currRing);
     6042      p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
     6043      strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
     6044//#if 1
     6045#if DEBUGF5 || DEBUGF51
     6046      printf("..");
     6047      pWrite(strat->syz[ctr]);
     6048#endif
     6049      strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
     6050      ctr++;
     6051    }
     6052//#if 1
     6053#ifdef DEBUGF5
     6054    Print("Principal syzygies:\n");
     6055    Print("--------------------------------\n");
     6056    for(i=0;i<=ps-1;i++)
     6057    {
     6058      pWrite(strat->syz[i]);
     6059    }
     6060    Print("--------------------------------\n");
     6061#endif
     6062
     6063  }
     6064}
     6065
     6066
    50216067
    50226068/*2
     
    50376083  strat->S=strat->Shdl->m;
    50386084
     6085  /*- put polys into S -*/
     6086  if (Q!=NULL)
     6087  {
     6088    strat->fromQ=initec(i);
     6089    memset(strat->fromQ,0,i*sizeof(int));
     6090    for (i=0; i<IDELEMS(Q); i++)
     6091    {
     6092      if (Q->m[i]!=NULL)
     6093      {
     6094        LObject h;
     6095        h.p = pCopy(Q->m[i]);
     6096        //if (TEST_OPT_INTSTRATEGY)
     6097        //{
     6098        //  //pContent(h.p);
     6099        //  h.pCleardenom(); // also does a pContent
     6100        //}
     6101        //else
     6102        //{
     6103        //  h.pNorm();
     6104        //}
     6105        if (currRing->OrdSgn==-1)
     6106        {
     6107          deleteHC(&h,strat);
     6108        }
     6109        if (h.p!=NULL)
     6110        {
     6111          strat->initEcart(&h);
     6112          if (strat->sl==-1)
     6113            pos =0;
     6114          else
     6115          {
     6116            pos = posInS(strat,strat->sl,h.p,h.ecart);
     6117          }
     6118          h.sev = pGetShortExpVector(h.p);
     6119          strat->enterS(h,pos,strat, strat->tl+1);
     6120          enterT(h, strat);
     6121          strat->fromQ[pos]=1;
     6122        }
     6123      }
     6124    }
     6125  }
     6126  /*- put polys into S -*/
     6127  for (i=0; i<IDELEMS(F); i++)
     6128  {
     6129    if (F->m[i]!=NULL)
     6130    {
     6131      LObject h;
     6132      h.p = pCopy(F->m[i]);
     6133      if (currRing->OrdSgn==-1)
     6134      {
     6135        deleteHC(&h,strat);
     6136      }
     6137      else
     6138      {
     6139        h.p=redtailBba(h.p,strat->sl,strat);
     6140      }
     6141      if (h.p!=NULL)
     6142      {
     6143        strat->initEcart(&h);
     6144        if (strat->sl==-1)
     6145          pos =0;
     6146        else
     6147          pos = posInS(strat,strat->sl,h.p,h.ecart);
     6148        h.sev = pGetShortExpVector(h.p);
     6149        strat->enterS(h,pos,strat, strat->tl+1);
     6150        enterT(h,strat);
     6151      }
     6152    }
     6153  }
     6154  for (i=0; i<IDELEMS(P); i++)
     6155  {
     6156    if (P->m[i]!=NULL)
     6157    {
     6158      LObject h;
     6159      h.p=pCopy(P->m[i]);
     6160      if (TEST_OPT_INTSTRATEGY)
     6161      {
     6162        h.pCleardenom();
     6163      }
     6164      else
     6165      {
     6166        h.pNorm();
     6167      }
     6168      if(strat->sl>=0)
     6169      {
     6170        if (currRing->OrdSgn==1)
     6171        {
     6172          h.p=redBba(h.p,strat->sl,strat);
     6173          if (h.p!=NULL)
     6174          {
     6175            h.p=redtailBba(h.p,strat->sl,strat);
     6176          }
     6177        }
     6178        else
     6179        {
     6180          h.p=redMora(h.p,strat->sl,strat);
     6181        }
     6182        if(h.p!=NULL)
     6183        {
     6184          strat->initEcart(&h);
     6185          if (TEST_OPT_INTSTRATEGY)
     6186          {
     6187            h.pCleardenom();
     6188          }
     6189          else
     6190          {
     6191            h.is_normalized = 0;
     6192            h.pNorm();
     6193          }
     6194          h.sev = pGetShortExpVector(h.p);
     6195          h.SetpFDeg();
     6196          pos = posInS(strat,strat->sl,h.p,h.ecart);
     6197          enterpairsSpecial(h.p,strat->sl,h.ecart,pos,strat,strat->tl+1);
     6198          strat->enterS(h,pos,strat, strat->tl+1);
     6199          enterT(h,strat);
     6200        }
     6201      }
     6202      else
     6203      {
     6204        h.sev = pGetShortExpVector(h.p);
     6205        strat->initEcart(&h);
     6206        strat->enterS(h,0,strat, strat->tl+1);
     6207        enterT(h,strat);
     6208      }
     6209    }
     6210  }
     6211}
     6212/*2
     6213*construct the set s from F and {P}
     6214*/
     6215
     6216void initSSpecialSba (ideal F, ideal Q, ideal P,kStrategy strat)
     6217{
     6218  int   i,pos;
     6219
     6220  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
     6221  else i=setmaxT;
     6222  i=((i+IDELEMS(F)+IDELEMS(P)+15)/16)*16;
     6223  strat->fromS=initec(i);
     6224  strat->sevS=initsevS(i);
     6225  strat->sevSig=initsevS(i);
     6226  strat->S_2_R=initS_2_R(i);
     6227  strat->fromQ=NULL;
     6228  strat->Shdl=idInit(i,F->rank);
     6229  strat->S=strat->Shdl->m;
     6230  strat->sig=(poly *)omAlloc0(i*sizeof(poly));
    50396231  /*- put polys into S -*/
    50406232  if (Q!=NULL)
     
    56656857
    56666858/*2
     6859* -puts p to the standardbasis s at position at
     6860* -saves the result in S
     6861*/
     6862void enterSSba (LObject p,int atS,kStrategy strat, int atR)
     6863{
     6864  int i;
     6865  strat->news = TRUE;
     6866  /*- puts p to the standardbasis s at position at -*/
     6867  if (strat->sl == IDELEMS(strat->Shdl)-1)
     6868  {
     6869    strat->sevS = (unsigned long*) omRealloc0Size(strat->sevS,
     6870                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
     6871                                    (IDELEMS(strat->Shdl)+setmaxTinc)
     6872                                                  *sizeof(unsigned long));
     6873    strat->sevSig = (unsigned long*) omRealloc0Size(strat->sevSig,
     6874                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
     6875                                    (IDELEMS(strat->Shdl)+setmaxTinc)
     6876                                                  *sizeof(unsigned long));
     6877    strat->ecartS = (intset)omReallocSize(strat->ecartS,
     6878                                          IDELEMS(strat->Shdl)*sizeof(int),
     6879                                          (IDELEMS(strat->Shdl)+setmaxTinc)
     6880                                                  *sizeof(int));
     6881    strat->fromS = (intset)omReallocSize(strat->fromS,
     6882                                          IDELEMS(strat->Shdl)*sizeof(int),
     6883                                          (IDELEMS(strat->Shdl)+setmaxTinc)
     6884                                                  *sizeof(int));
     6885    strat->S_2_R = (int*) omRealloc0Size(strat->S_2_R,
     6886                                         IDELEMS(strat->Shdl)*sizeof(int),
     6887                                         (IDELEMS(strat->Shdl)+setmaxTinc)
     6888                                                  *sizeof(int));
     6889    if (strat->lenS!=NULL)
     6890      strat->lenS=(int*)omRealloc0Size(strat->lenS,
     6891                                       IDELEMS(strat->Shdl)*sizeof(int),
     6892                                       (IDELEMS(strat->Shdl)+setmaxTinc)
     6893                                                 *sizeof(int));
     6894    if (strat->lenSw!=NULL)
     6895      strat->lenSw=(wlen_type*)omRealloc0Size(strat->lenSw,
     6896                                       IDELEMS(strat->Shdl)*sizeof(wlen_type),
     6897                                       (IDELEMS(strat->Shdl)+setmaxTinc)
     6898                                                 *sizeof(wlen_type));
     6899    if (strat->fromQ!=NULL)
     6900    {
     6901      strat->fromQ = (intset)omReallocSize(strat->fromQ,
     6902                                    IDELEMS(strat->Shdl)*sizeof(int),
     6903                                    (IDELEMS(strat->Shdl)+setmaxTinc)*sizeof(int));
     6904    }
     6905    pEnlargeSet(&strat->S,IDELEMS(strat->Shdl),setmaxTinc);
     6906    pEnlargeSet(&strat->sig,IDELEMS(strat->Shdl),setmaxTinc);
     6907    IDELEMS(strat->Shdl)+=setmaxTinc;
     6908    strat->Shdl->m=strat->S;
     6909  }
     6910  // in a signature-based algorithm the following situation will never
     6911  // appear due to the fact that the critical pairs are already sorted
     6912  // by increasing signature.
     6913  if (atS <= strat->sl)
     6914  {
     6915#ifdef ENTER_USE_MEMMOVE
     6916// #if 0
     6917    memmove(&(strat->S[atS+1]), &(strat->S[atS]),
     6918            (strat->sl - atS + 1)*sizeof(poly));
     6919    memmove(&(strat->ecartS[atS+1]), &(strat->ecartS[atS]),
     6920            (strat->sl - atS + 1)*sizeof(int));
     6921    memmove(&(strat->fromS[atS+1]), &(strat->fromS[atS]),
     6922            (strat->sl - atS + 1)*sizeof(int));
     6923    memmove(&(strat->sevS[atS+1]), &(strat->sevS[atS]),
     6924            (strat->sl - atS + 1)*sizeof(unsigned long));
     6925    memmove(&(strat->S_2_R[atS+1]), &(strat->S_2_R[atS]),
     6926            (strat->sl - atS + 1)*sizeof(int));
     6927    if (strat->lenS!=NULL)
     6928    memmove(&(strat->lenS[atS+1]), &(strat->lenS[atS]),
     6929            (strat->sl - atS + 1)*sizeof(int));
     6930    if (strat->lenSw!=NULL)
     6931    memmove(&(strat->lenSw[atS+1]), &(strat->lenSw[atS]),
     6932            (strat->sl - atS + 1)*sizeof(wlen_type));
     6933#else
     6934    for (i=strat->sl+1; i>=atS+1; i--)
     6935    {
     6936      strat->S[i] = strat->S[i-1];
     6937      strat->ecartS[i] = strat->ecartS[i-1];
     6938      strat->fromS[i] = strat->fromS[i-1];
     6939      strat->sevS[i] = strat->sevS[i-1];
     6940      strat->S_2_R[i] = strat->S_2_R[i-1];
     6941    }
     6942    if (strat->lenS!=NULL)
     6943    for (i=strat->sl+1; i>=atS+1; i--)
     6944      strat->lenS[i] = strat->lenS[i-1];
     6945    if (strat->lenSw!=NULL)
     6946    for (i=strat->sl+1; i>=atS+1; i--)
     6947      strat->lenSw[i] = strat->lenSw[i-1];
     6948#endif
     6949  }
     6950  if (strat->fromQ!=NULL)
     6951  {
     6952#ifdef ENTER_USE_MEMMOVE
     6953    memmove(&(strat->fromQ[atS+1]), &(strat->fromQ[atS]),
     6954                  (strat->sl - atS + 1)*sizeof(int));
     6955#else
     6956    for (i=strat->sl+1; i>=atS+1; i--)
     6957    {
     6958      strat->fromQ[i] = strat->fromQ[i-1];
     6959    }
     6960#endif
     6961    strat->fromQ[atS]=0;
     6962  }
     6963
     6964  /*- save result -*/
     6965  strat->S[atS] = p.p;
     6966  strat->sig[atS] = p.sig; // TODO: get ths correct signature in here!
     6967  if (strat->honey) strat->ecartS[atS] = p.ecart;
     6968  if (p.sev == 0)
     6969    p.sev = pGetShortExpVector(p.p);
     6970  else
     6971    assume(p.sev == pGetShortExpVector(p.p));
     6972  strat->sevS[atS] = p.sev;
     6973  // during the interreduction process of a signature-based algorithm we do not
     6974  // compute the signature at this point, but when the whole interreduction
     6975  // process finishes, i.e. f5c terminates!
     6976  if (p.sig != NULL)
     6977  {
     6978    if (p.sevSig == 0)
     6979      p.sevSig = pGetShortExpVector(p.sig);
     6980    else
     6981      assume(p.sevSig == pGetShortExpVector(p.sig));
     6982    strat->sevSig[atS] = p.sevSig; // TODO: get the correct signature in here!
     6983  }
     6984  strat->ecartS[atS] = p.ecart;
     6985  strat->fromS[atS] = p.from;
     6986  strat->S_2_R[atS] = atR;
     6987  strat->sl++;
     6988#ifdef DEBUGF5
     6989  int k;
     6990  Print("--- LIST S: %d ---\n",strat->sl);
     6991  for(k=0;k<=strat->sl;k++)
     6992  {
     6993    pWrite(strat->sig[k]);
     6994  }
     6995  Print("--- LIST S END ---\n");
     6996#endif
     6997}
     6998
     6999/*2
    56677000* puts p to the set T at position atT
    56687001*/
     
    57357068  kTest_T(&(strat->T[atT]));
    57367069}
     7070
     7071/*2
     7072* puts signature p.sig to the set syz
     7073*/
     7074void enterSyz(LObject p, kStrategy strat)
     7075{
     7076  int i = strat->syzl;
     7077
     7078  strat->newt = TRUE;
     7079  if (strat->syzl == strat->syzmax)
     7080  {
     7081    pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
     7082    strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
     7083                                    (strat->syzmax)*sizeof(unsigned long),
     7084                                    ((strat->syzmax)+setmaxTinc)
     7085                                                  *sizeof(unsigned long));
     7086    strat->syzmax += setmaxTinc;
     7087  }
     7088  strat->syz[i] = p.sig;
     7089  strat->sevSyz[i] = p.sevSig;
     7090  strat->syzl++;
     7091#ifdef DEBUGF5
     7092  Print("last element in strat->syz: %d--%d  ",i+1,strat->syzmax);
     7093  pWrite(strat->syz[i]);
     7094#endif
     7095  // recheck pairs in strat->L with new rule and delete correspondingly
     7096  int cc = strat->Ll;
     7097  while (cc>-1)
     7098  {
     7099    if (p_LmShortDivisibleBy( strat->syz[strat->syzl-1], strat->sevSyz[strat->syzl-1],
     7100                              strat->L[cc].sig, ~strat->L[cc].sevSig, currRing))
     7101    {
     7102      deleteInL(strat->L,&strat->Ll,cc,strat);
     7103    }
     7104    cc--;
     7105  }
     7106
     7107}
     7108
    57377109
    57387110void initHilbCrit(ideal/*F*/, ideal /*Q*/, intvec **hilb,kStrategy strat)
     
    57717143  * - in local rings, - in lex order case, -in ring over extensions */
    57727144  strat->noTailReduction = !TEST_OPT_REDTAIL;
     7145
     7146#ifdef HAVE_PLURAL
     7147  // and r is plural_ring
     7148  //  hence this holds for r a rational_plural_ring
     7149  if( rIsPluralRing(currRing) || (rIsSCA(currRing) && !strat->z2homog) )
     7150  {    //or it has non-quasi-comm type... later
     7151    strat->sugarCrit = FALSE;
     7152    strat->Gebauer = FALSE;
     7153    strat->honey = FALSE;
     7154  }
     7155#endif
     7156
     7157#ifdef HAVE_RINGS
     7158  // Coefficient ring?
     7159  if (rField_is_Ring(currRing))
     7160  {
     7161    strat->sugarCrit = FALSE;
     7162    strat->Gebauer = FALSE ;
     7163    strat->honey = FALSE;
     7164  }
     7165#endif
     7166  #ifdef KDEBUG
     7167  if (TEST_OPT_DEBUG)
     7168  {
     7169    if (strat->homog) PrintS("ideal/module is homogeneous\n");
     7170    else              PrintS("ideal/module is not homogeneous\n");
     7171  }
     7172  #endif
     7173}
     7174
     7175void initSbaCrit(kStrategy strat)
     7176{
     7177  //strat->enterOnePair=enterOnePairNormal;
     7178  strat->enterOnePair = enterOnePairNormal;
     7179  //strat->chainCrit=chainCritNormal;
     7180  strat->chainCrit    = chainCritSig;
     7181  /******************************************
     7182   * rewCrit1 and rewCrit2 are already set in
     7183   * kSba() in kstd1.cc
     7184   *****************************************/
     7185  //strat->rewCrit1     = faugereRewCriterion;
     7186  if (strat->incremental)
     7187  {
     7188    strat->syzCrit  = syzCriterionInc;
     7189  }
     7190  else
     7191  {
     7192    strat->syzCrit  = syzCriterion;
     7193  }
     7194#ifdef HAVE_RINGS
     7195  if (rField_is_Ring(currRing))
     7196  {
     7197    strat->enterOnePair=enterOnePairRing;
     7198    strat->chainCrit=chainCritRing;
     7199  }
     7200#endif
     7201#ifdef HAVE_RATGRING
     7202  if (rIsRatGRing(currRing))
     7203  {
     7204     strat->chainCrit=chainCritPart;
     7205     /* enterOnePairNormal get rational part in it */
     7206  }
     7207#endif
     7208
     7209  strat->sugarCrit =        TEST_OPT_SUGARCRIT;
     7210  strat->Gebauer =          strat->homog || strat->sugarCrit;
     7211  strat->honey =            !strat->homog || strat->sugarCrit || TEST_OPT_WEIGHTM;
     7212  if (TEST_OPT_NOT_SUGAR) strat->honey = FALSE;
     7213  strat->pairtest = NULL;
     7214  /* alway use tailreduction, except:
     7215  * - in local rings, - in lex order case, -in ring over extensions */
     7216  strat->noTailReduction = !TEST_OPT_REDTAIL;
     7217  //strat->noTailReduction = NULL;
    57737218
    57747219#ifdef HAVE_PLURAL
     
    59877432}
    59887433
     7434void initSbaPos (kStrategy strat)
     7435{
     7436  if (currRing->OrdSgn==1)
     7437  {
     7438    if (strat->honey)
     7439    {
     7440      strat->posInL = posInL15;
     7441      // ok -- here is the deal: from my experiments for Singular-2-0
     7442      // I conclude that that posInT_EcartpLength is the best of
     7443      // posInT15, posInT_EcartFDegpLength, posInT_FDegLength, posInT_pLength
     7444      // see the table at the end of this file
     7445      if (TEST_OPT_OLDSTD)
     7446        strat->posInT = posInT15;
     7447      else
     7448        strat->posInT = posInT_EcartpLength;
     7449    }
     7450    else if (currRing->pLexOrder && !TEST_OPT_INTSTRATEGY)
     7451    {
     7452      strat->posInL = posInL11;
     7453      strat->posInT = posInT11;
     7454    }
     7455    else if (TEST_OPT_INTSTRATEGY)
     7456    {
     7457      strat->posInL = posInL11;
     7458      strat->posInT = posInT11;
     7459    }
     7460    else
     7461    {
     7462      strat->posInL = posInL0;
     7463      strat->posInT = posInT0;
     7464    }
     7465    //if (strat->minim>0) strat->posInL =posInLSpecial;
     7466    if (strat->homog)
     7467    {
     7468       strat->posInL = posInL110;
     7469       strat->posInT = posInT110;
     7470    }
     7471  }
     7472  else
     7473  {
     7474    if (strat->homog)
     7475    {
     7476      strat->posInL = posInL11;
     7477      strat->posInT = posInT11;
     7478    }
     7479    else
     7480    {
     7481      if ((currRing->order[0]==ringorder_c)
     7482      ||(currRing->order[0]==ringorder_C))
     7483      {
     7484        strat->posInL = posInL17_c;
     7485        strat->posInT = posInT17_c;
     7486      }
     7487      else
     7488      {
     7489        strat->posInL = posInL17;
     7490        strat->posInT = posInT17;
     7491      }
     7492    }
     7493  }
     7494  if (strat->minim>0) strat->posInL =posInLSpecial;
     7495  // for further tests only
     7496  if ((BTEST1(11)) || (BTEST1(12)))
     7497    strat->posInL = posInL11;
     7498  else if ((BTEST1(13)) || (BTEST1(14)))
     7499    strat->posInL = posInL13;
     7500  else if ((BTEST1(15)) || (BTEST1(16)))
     7501    strat->posInL = posInL15;
     7502  else if ((BTEST1(17)) || (BTEST1(18)))
     7503    strat->posInL = posInL17;
     7504  if (BTEST1(11))
     7505    strat->posInT = posInT11;
     7506  else if (BTEST1(13))
     7507    strat->posInT = posInT13;
     7508  else if (BTEST1(15))
     7509    strat->posInT = posInT15;
     7510  else if ((BTEST1(17)))
     7511    strat->posInT = posInT17;
     7512  else if ((BTEST1(19)))
     7513    strat->posInT = posInT19;
     7514  else if (BTEST1(12) || BTEST1(14) || BTEST1(16) || BTEST1(18))
     7515    strat->posInT = posInT1;
     7516#ifdef HAVE_RINGS
     7517  if (rField_is_Ring(currRing))
     7518  {
     7519    strat->posInL = posInL11;
     7520    strat->posInT = posInT11;
     7521  }
     7522#endif
     7523  strat->posInLDependsOnLength = FALSE;
     7524  strat->posInLSba  = posInLSig;
     7525  //strat->posInL     = posInLSig;
     7526  strat->posInL     = posInLF5C;
     7527  //strat->posInT     = posInTSig;
     7528}
     7529
     7530void initSbaBuchMora (ideal F,ideal Q,kStrategy strat)
     7531{
     7532  strat->interpt = BTEST1(OPT_INTERRUPT);
     7533  strat->kHEdge=NULL;
     7534  if (currRing->OrdSgn==1) strat->kHEdgeFound=FALSE;
     7535  /*- creating temp data structures------------------- -*/
     7536  strat->cp = 0;
     7537  strat->c3 = 0;
     7538  strat->tail = pInit();
     7539  /*- set s -*/
     7540  strat->sl = -1;
     7541  /*- set ps -*/
     7542  strat->syzl = -1;
     7543  /*- set L -*/
     7544  strat->Lmax = ((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
     7545  strat->Ll = -1;
     7546  strat->L = initL(((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc);
     7547  /*- set B -*/
     7548  strat->Bmax = setmaxL;
     7549  strat->Bl = -1;
     7550  strat->B = initL();
     7551  /*- set T -*/
     7552  strat->tl = -1;
     7553  strat->tmax = setmaxT;
     7554  strat->T = initT();
     7555  strat->R = initR();
     7556  strat->sevT = initsevT();
     7557  /*- init local data struct.---------------------------------------- -*/
     7558  strat->P.ecart=0;
     7559  strat->P.length=0;
     7560  if (currRing->OrdSgn==-1)
     7561  {
     7562    if (strat->kHEdge!=NULL) pSetComp(strat->kHEdge, strat->ak);
     7563    if (strat->kNoether!=NULL) pSetComp(strat->kNoetherTail(), strat->ak);
     7564  }
     7565  if(TEST_OPT_SB_1)
     7566  {
     7567    int i;
     7568    ideal P=idInit(IDELEMS(F)-strat->newIdeal,F->rank);
     7569    for (i=strat->newIdeal;i<IDELEMS(F);i++)
     7570    {
     7571      P->m[i-strat->newIdeal] = F->m[i];
     7572      F->m[i] = NULL;
     7573    }
     7574    initSSpecialSba(F,Q,P,strat);
     7575    for (i=strat->newIdeal;i<IDELEMS(F);i++)
     7576    {
     7577      F->m[i] = P->m[i-strat->newIdeal];
     7578      P->m[i-strat->newIdeal] = NULL;
     7579    }
     7580    idDelete(&P);
     7581  }
     7582  else
     7583  {
     7584    /*Shdl=*/initSLSba(F, Q,strat); /*sets also S, ecartS, fromQ */
     7585    // /*Shdl=*/initS(F, Q,strat); /*sets also S, ecartS, fromQ */
     7586  }
     7587  strat->fromT = FALSE;
     7588  strat->noTailReduction = !TEST_OPT_REDTAIL;
     7589  if (!TEST_OPT_SB_1)
     7590  {
     7591    updateS(TRUE,strat);
     7592  }
     7593  if (strat->fromQ!=NULL) omFreeSize(strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
     7594  strat->fromQ=NULL;
     7595}
     7596
     7597void exitSba (kStrategy strat)
     7598{
     7599  /*- release temp data -*/
     7600  cleanT(strat);
     7601  omFreeSize(strat->T,(strat->tmax)*sizeof(TObject));
     7602  omFreeSize(strat->R,(strat->tmax)*sizeof(TObject*));
     7603  omFreeSize(strat->sevT, (strat->tmax)*sizeof(unsigned long));
     7604  omFreeSize(strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
     7605  omFreeSize(strat->fromS,IDELEMS(strat->Shdl)*sizeof(int));
     7606  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
     7607  omFreeSize((ADDRESS)strat->sevSig,IDELEMS(strat->Shdl)*sizeof(unsigned long));
     7608  omFreeSize((ADDRESS)strat->syz,(strat->syzmax)*sizeof(poly));
     7609  omFreeSize((ADDRESS)strat->sevSyz,(strat->syzmax)*sizeof(unsigned long));
     7610  if (strat->incremental)
     7611  {
     7612    omFreeSize(strat->syzIdx,(strat->syzidxmax)*sizeof(int));
     7613  }
     7614  omFreeSize(strat->S_2_R,IDELEMS(strat->Shdl)*sizeof(int));
     7615  /*- set L: should be empty -*/
     7616  omFreeSize(strat->L,(strat->Lmax)*sizeof(LObject));
     7617  /*- set B: should be empty -*/
     7618  omFreeSize(strat->B,(strat->Bmax)*sizeof(LObject));
     7619  /*- set sig: no need for the signatures anymore -*/
     7620  omFreeSize(strat->sig,IDELEMS(strat->Shdl)*sizeof(poly));
     7621  pLmDelete(&strat->tail);
     7622  strat->syzComp=0;
     7623}
     7624
    59897625/*2
    59907626* in the case of a standardbase of a module over a qring:
     
    64538089
    64548090  kStratChangeTailRing(strat, NULL, NULL, e);
     8091}
     8092
     8093ring sbaRing (kStrategy strat, const ring r, BOOLEAN complete, int sgn)
     8094{
     8095  int n = rBlocks(r); // Including trailing zero!
     8096  // if incremental => use (C,monomial order from r)
     8097  if (strat->incremental)
     8098  {
     8099    if (r->order[0] == ringorder_C || r->order[0] == ringorder_c)
     8100    {
     8101      return r;
     8102    }
     8103      ring res = rCopy0(r, FALSE, TRUE);
     8104      for (int i=1; i<n-1; i++)
     8105      {
     8106        res->order[i] = res->order[i-1];
     8107        res->block0[i] = res->block0[i-1];
     8108        res->block1[i] = res->block1[i-1];
     8109        res->wvhdl[i] = res->wvhdl[i-1];
     8110      }
     8111
     8112    // new 1st block
     8113    res->order[0]   = ringorder_C; // Prefix
     8114    res->block0[0]  = 1;
     8115    res->block1[0]  = res->N;
     8116    //res->wvhdl[j]   = NULL;
     8117    // res->order [j] = 0; // The End!
     8118    rComplete(res, 1);
     8119#ifdef HAVE_PLURAL
     8120    if (rIsPluralRing(r))
     8121    {
     8122      if ( nc_rComplete(r, res, false) ) // no qideal!
     8123      {
     8124#ifndef NDEBUG
     8125        WarnS("error in nc_rComplete");
     8126#endif
     8127        // cleanup?
     8128
     8129        //      rDelete(res);
     8130        //      return r;
     8131
     8132        // just go on..
     8133      }
     8134    }
     8135#endif
     8136  strat->tailRing = res;
     8137  return (res);
     8138  }
     8139  // not incremental => use Schreyer order
     8140  // this is done by a trick when initializing the signatures
     8141  // in initSLSba():
     8142  // Instead of using the signature 1e_i for F->m[i], we start
     8143  // with the signature LM(F->m[i])e_i for F->m[i]. Doing this we get a
     8144  // Schreyer order w.r.t. the underlying monomial order.
     8145  // => we do not need to change the underlying polynomial ring at all!
     8146
     8147
     8148  /*
     8149  else
     8150  {
     8151    ring res = rCopy0(r, FALSE, FALSE);
     8152    // Create 2 more blocks for prefix/suffix:
     8153    res->order=(int *)omAlloc0((n+2)*sizeof(int)); // 0  ..  n+1
     8154    res->block0=(int *)omAlloc0((n+2)*sizeof(int));
     8155    res->block1=(int *)omAlloc0((n+2)*sizeof(int));
     8156    int ** wvhdl =(int **)omAlloc0((n+2)*sizeof(int**));
     8157
     8158    // Encapsulate all existing blocks between induced Schreyer ordering markers: prefix and suffix!
     8159    // Note that prefix and suffix have the same ringorder marker and only differ in block[] parameters!
     8160
     8161    // new 1st block
     8162    int j = 0;
     8163    res->order[j] = ringorder_IS; // Prefix
     8164    res->block0[j] = res->block1[j] = 0;
     8165    // wvhdl[j] = NULL;
     8166    j++;
     8167
     8168    for(int i = 0; (i < n) && (r->order[i] != 0); i++, j++) // i = [0 .. n-1] <- non-zero old blocks
     8169    {
     8170      res->order [j] = r->order [i];
     8171      res->block0[j] = r->block0[i];
     8172      res->block1[j] = r->block1[i];
     8173
     8174      if (r->wvhdl[i] != NULL)
     8175      {
     8176        wvhdl[j] = (int*) omMemDup(r->wvhdl[i]);
     8177      } // else wvhdl[j] = NULL;
     8178    }
     8179
     8180    // new last block
     8181    res->order [j] = ringorder_IS; // Suffix
     8182    res->block0[j] = res->block1[j] = sgn; // Sign of v[o]: 1 for C, -1 for c
     8183    // wvhdl[j] = NULL;
     8184    j++;
     8185
     8186    // res->order [j] = 0; // The End!
     8187    res->wvhdl = wvhdl;
     8188
     8189    // j == the last zero block now!
     8190    assume(j == (n+1));
     8191    assume(res->order[0]==ringorder_IS);
     8192    assume(res->order[j-1]==ringorder_IS);
     8193    assume(res->order[j]==0);
     8194
     8195    if (complete)
     8196    {
     8197      rComplete(res, 1);
     8198
     8199#ifdef HAVE_PLURAL
     8200      if (rIsPluralRing(r))
     8201      {
     8202        if ( nc_rComplete(r, res, false) ) // no qideal!
     8203        {
     8204        }
     8205      }
     8206      assume(rIsPluralRing(r) == rIsPluralRing(res));
     8207#endif
     8208
     8209
     8210#ifdef HAVE_PLURAL
     8211      ring old_ring = r;
     8212
     8213#endif
     8214
     8215      if (r->qideal!=NULL)
     8216      {
     8217        res->qideal= idrCopyR_NoSort(r->qideal, r, res);
     8218
     8219        assume(idRankFreeModule(res->qideal, res) == 0);
     8220
     8221#ifdef HAVE_PLURAL
     8222        if( rIsPluralRing(res) )
     8223          if( nc_SetupQuotient(res, r, true) )
     8224          {
     8225            //          WarnS("error in nc_SetupQuotient"); // cleanup?      rDelete(res);       return r;  // just go on...?
     8226          }
     8227
     8228#endif
     8229        assume(idRankFreeModule(res->qideal, res) == 0);
     8230      }
     8231
     8232#ifdef HAVE_PLURAL
     8233      assume((res->qideal==NULL) == (old_ring->qideal==NULL));
     8234      assume(rIsPluralRing(res) == rIsPluralRing(old_ring));
     8235      assume(rIsSCA(res) == rIsSCA(old_ring));
     8236      assume(ncRingType(res) == ncRingType(old_ring));
     8237#endif
     8238    }
     8239    strat->tailRing = res;
     8240    return res;
     8241  }
     8242  */
    64558243}
    64568244
  • kernel/kutil.h

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