Changeset 83be980 in git


Ignore:
Timestamp:
Jul 2, 2012, 7:26:50 AM (11 years ago)
Author:
Christian Eder
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'ad2543eab51733612ba7d118afc77edca719600e')
Children:
1bc7d4ac8a4fd3280459ab78ca65bd4e60dd2c93
Parents:
cffd3e2f630fbc7b0e35afee97d6fa948cfd0b3e
git-author:
Christian Eder <ederc@mathematik.uni-kl.de>2012-07-02 07:26:50+02:00
git-committer:
Christian Eder <ederc@mathematik.uni-kl.de>2012-07-05 16:12:50+02:00
Message:
adds signature-based algorithm files from master, does not build right now:
fixes kstd1.cc for compilation
Location:
kernel
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • kernel/kstd1.cc

    rcffd3e r83be980  
    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                if (arri == 2)
     2008                {
     2009                        r=ssg(F,Q,NULL,hilb,strat);
     2010                }
     2011                if (arri == 3)
     2012                {
     2013                        r=ssgnoninc(F,Q,NULL,hilb,strat);
     2014                }
     2015                if (arri == 4)
     2016                {
     2017                        r=ssgincschreyer(F,Q,NULL,hilb,strat);
     2018                }
     2019                else
     2020                {
     2021                        r=sba(F,Q,NULL,hilb,strat);
     2022                }
    17972023    }
    17982024  }
  • kernel/kstd1.h

    rcffd3e r83be980  
    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 r83be980  
    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>
     
    478492        h->Clear();
    479493        return -1;
     494      }
     495    }
     496  }
     497}
     498
     499/*2
     500*  reduction procedure for signature-based standard
     501*  basis algorithms:
     502*  all reductions have to be sig-safe!
     503*
     504*  2 is returned if and only if the pair is rejected by the rewritten criterion
     505*  at exactly this point of the computations. This is the last possible point
     506*  such a check can be done => checks with the biggest set of available
     507*  signatures
     508*/
     509int redSig (LObject* h,kStrategy strat)
     510{
     511  if (strat->tl<0) return 1;
     512  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
     513  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
     514  assume(h->FDeg == h->pFDeg());
     515//#if 1
     516#ifdef DEBUGF5
     517  Print("------- IN REDSIG -------\n");
     518  Print("p: ");
     519  pWrite(pHead(h->p));
     520  Print("p1: ");
     521  pWrite(pHead(h->p1));
     522  Print("p2: ");
     523  pWrite(pHead(h->p2));
     524  Print("---------------------------\n");
     525#endif
     526  poly h_p;
     527  int i,j,at,pass, ii;
     528  int start=0;
     529  int sigSafe;
     530  unsigned long not_sev;
     531  long reddeg,d;
     532
     533  pass = j = 0;
     534  d = reddeg = h->GetpFDeg();
     535  h->SetShortExpVector();
     536  int li;
     537  h_p = h->GetLmTailRing();
     538  not_sev = ~ h->sev;
     539  loop
     540  {
     541    j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h, start);
     542    if (j < 0)
     543    {
     544      return 1;
     545    }
     546
     547    li = strat->T[j].pLength;
     548    ii = j;
     549    /*
     550     * the polynomial to reduce with (up to the moment) is;
     551     * pi with length li
     552     */
     553    i = j;
     554#if 1
     555    if (TEST_OPT_LENGTH)
     556    loop
     557    {
     558      /*- search the shortest possible with respect to length -*/
     559      i++;
     560      if (i > strat->tl)
     561        break;
     562      if (li<=1)
     563        break;
     564      if ((strat->T[i].pLength < li)
     565         &&
     566          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
     567                               h_p, not_sev, strat->tailRing))
     568      {
     569        /*
     570         * the polynomial to reduce with is now;
     571         */
     572        li = strat->T[i].pLength;
     573        ii = i;
     574      }
     575    }
     576    start = ii+1;
     577#endif
     578
     579    /*
     580     * end of search: have to reduce with pi
     581     */
     582#ifdef KDEBUG
     583    if (TEST_OPT_DEBUG)
     584    {
     585      PrintS("red:");
     586      h->wrp();
     587      PrintS(" with ");
     588      strat->T[ii].wrp();
     589    }
     590#endif
     591    assume(strat->fromT == FALSE);
     592//#if 1
     593#ifdef DEBUGF5
     594    Print("BEFORE REDUCTION WITH %d:\n",ii);
     595    Print("--------------------------------\n");
     596    pWrite(h->sig);
     597    pWrite(strat->T[ii].sig);
     598    pWrite(h->GetLmCurrRing());
     599    pWrite(pHead(h->p1));
     600    pWrite(pHead(h->p2));
     601    pWrite(pHead(strat->T[ii].p));
     602    Print("--------------------------------\n");
     603    printf("INDEX OF REDUCER T: %d\n",ii);
     604#endif
     605    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
     606    // if reduction has taken place, i.e. the reduction was sig-safe
     607    // otherwise start is already at the next position and the loop
     608    // searching reducers in T goes on from index start
     609//#if 1
     610#ifdef DEBUGF5
     611    Print("SigSAFE: %d\n",sigSafe);
     612#endif
     613    if (sigSafe != 3)
     614    {
     615      // start the next search for reducers in T from the beginning
     616      start = 0;
     617#ifdef KDEBUG
     618      if (TEST_OPT_DEBUG)
     619      {
     620        PrintS("\nto ");
     621        h->wrp();
     622        PrintLn();
     623      }
     624#endif
     625
     626      h_p = h->GetLmTailRing();
     627      if (h_p == NULL)
     628      {
     629        if (h->lcm!=NULL) pLmFree(h->lcm);
     630#ifdef KDEBUG
     631        h->lcm=NULL;
     632#endif
     633        return 0;
     634      }
     635      h->SetShortExpVector();
     636      not_sev = ~ h->sev;
     637      /*
     638      * try to reduce the s-polynomial h
     639      *test first whether h should go to the lazyset L
     640      *-if the degree jumps
     641      *-if the number of pre-defined reductions jumps
     642      */
     643      pass++;
     644      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
     645      {
     646        h->SetLmCurrRing();
     647        at = strat->posInL(strat->L,strat->Ll,h,strat);
     648        if (at <= strat->Ll)
     649        {
     650          int dummy=strat->sl;
     651          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
     652          {
     653            return 1;
     654          }
     655          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
     656#ifdef KDEBUG
     657          if (TEST_OPT_DEBUG)
     658            Print(" lazy: -> L%d\n",at);
     659#endif
     660          h->Clear();
     661          return -1;
     662        }
    480663      }
    481664    }
     
    12941477  idTest(strat->Shdl);
    12951478
     1479  return (strat->Shdl);
     1480}
     1481ideal ssgincschreyer (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
     1482{
     1483        int
     1484                time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
     1485                time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
     1486                time_add_b2 = 0;
     1487
     1488        time_from_last_call();
     1489        int current_input_idx = 0;
     1490        while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
     1491        {
     1492                ++current_input_idx;
     1493        }
     1494        ideal I0 = idInit(1);
     1495        if (current_input_idx >= IDELEMS(F))
     1496        {
     1497                return I0;
     1498        }
     1499        I0->m[0] = pCopy(F->m[current_input_idx]);
     1500        int zero_reductions = 0;
     1501        LabeledPoly::GvwLess gvw_less;
     1502  poly pEins = pOne();
     1503        for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
     1504        {
     1505                if (!F->m[current_input_idx]) continue;
     1506                idDelDiv(I0);
     1507                idSkipZeroes(I0);
     1508#ifndef SSG_NO_INTERRED
     1509                std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
     1510               
     1511                ideal I0_tail_reduced = idInit(IDELEMS(I0));
     1512                //tail reducton
     1513                for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
     1514                {
     1515                        poly p_old = NULL;
     1516                        std::swap(p_old,I0->m[n0]);
     1517                        poly p_new = kNF(I0, Q, p_old);
     1518                        pDelete(&p_old);
     1519                        I0_tail_reduced->m[n0] = p_new;
     1520                }
     1521                std::swap(I0_tail_reduced->m[0], I0->m[0]);
     1522                idDelete(&I0);
     1523                I0 = I0_tail_reduced;
     1524#endif
     1525                time_interred += time_from_last_call();
     1526                LPolysByGvw R;
     1527                LPolysMuledBySig B;
     1528    //LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
     1529    LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx],
     1530    current_input_idx);
     1531                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     1532                {
     1533                        R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
     1534                }
     1535                const LPolysByGvw::iterator first_zero_sig = R.begin();
     1536    /*
     1537                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     1538                {
     1539      for (int m0 = n0-1; m0>=0; --m0)
     1540      {
     1541                          R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0], n0, I0->m[m0], m0));
     1542      }
     1543                }
     1544    */
     1545                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     1546                {
     1547      //R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
     1548                        R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0],current_input_idx+1,F->m[current_input_idx]));
     1549                }
     1550                                /*
     1551        printf("\nR-init = \n");
     1552                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     1553                                {
     1554                                        printf("p = ");pWrite((*ir)->p_);
     1555                                        printf("s = ");pWrite((*ir)->s_monom_);
     1556                                }
     1557        */
     1558    LabeledPolyMuled bnew;
     1559    bnew.Init();
     1560    bnew.FillBy(pEins, *p);
     1561    LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
     1562    /*
     1563    const LPolysByGvw::iterator p_insert_pos =
     1564      R.insert(known_gvw_greater_p, p);
     1565    */
     1566    bool rejected = false;
     1567                SigMuledMinimumFinder b_min_finder(B);
     1568    /*
     1569    for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
     1570    {
     1571      if ((*ir2)->sig_divides(bnew))
     1572      {
     1573        rejected = true;
     1574        break;
     1575      }
     1576    }
     1577    */
     1578    if (!rejected)
     1579    {
     1580      B.push_back(bnew);
     1581      b_min_finder.UpdateBy(B.size() - 1);
     1582      bnew.Init();
     1583      //time_add_b1_insertion += time_from_last_call();
     1584    }
     1585    bnew.Release();
     1586                time_prepare += time_from_last_call();
     1587    // first test in B
     1588                        if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
     1589                        {
     1590                                break;
     1591                        }else{
     1592                                p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
     1593                                B.erase_and_move_from_back(b_min_finder.minimum_idx_);
     1594                        }
     1595                while(1)
     1596                {
     1597                        bool reduced_to_zero = false;
     1598                        LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
     1599#if 1
     1600      /*
     1601                        if (n ==  IDELEMS(F) - 1)
     1602                        {
     1603      */
     1604        /*
     1605        printf("\nR = \n");
     1606                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     1607                                {
     1608                                        printf("p = ");pWrite((*ir)->p_);
     1609                                        printf("s = ");pWrite((*ir)->s_monom_);
     1610                                }
     1611                                printf("B = \n");
     1612                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     1613                                {
     1614                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
     1615          //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
     1616                                }
     1617        */
     1618                        /*
     1619      }
     1620      */
     1621#endif
     1622                        while(1)
     1623                        {
     1624        //printf("p to reduce = ");pWrite (p->p_);
     1625                                bool was_reduced = false;
     1626                                LPolysByGvw::iterator ir = --R.end();
     1627                                while(1)
     1628                                {
     1629                                        was_reduced = p->can_reduce_by(*ir);
     1630                                        if (was_reduced)
     1631                                        {
     1632                                                time_reduction_search += time_from_last_call();
     1633                                                p->reduce_by(*ir);
     1634                                                time_reduction += time_from_last_call();
     1635                                                break;
     1636                                        }
     1637                                        if (ir == known_gvw_greater_p) break;
     1638                                        --ir;
     1639                                }
     1640                                if (!was_reduced && ir != R.begin())
     1641                                {
     1642                                        --ir;
     1643                                        while(1)
     1644                                        {
     1645                                                if (!gvw_less(p, *ir))
     1646                                                {
     1647                                                        ++ir;
     1648                                                        break;
     1649                                                }
     1650                                                was_reduced = p->can_reduce_by(*ir);
     1651                                                if (was_reduced)
     1652                                                {
     1653                                                        time_reduction_search += time_from_last_call();
     1654                                                        p->reduce_by(*ir);
     1655                                                        time_reduction += time_from_last_call();
     1656                                                        break;
     1657                                                }
     1658                                                if (ir == R.begin()) break;
     1659                                                --ir;
     1660                                        }
     1661                                        known_gvw_greater_p = ir;
     1662                                }
     1663                                if (!was_reduced) break;
     1664                                reduced_to_zero = p->p_ == NULL;
     1665                                if (reduced_to_zero)
     1666                                {
     1667                                        ++zero_reductions;
     1668                                        known_gvw_greater_p = R.begin();
     1669                                        break;
     1670                                }
     1671                        }
     1672                        time_reduction_search += time_from_last_call();
     1673                        const LPolysByGvw::iterator p_insert_pos =
     1674                                R.insert(known_gvw_greater_p, p);
     1675                        time_add_r += time_from_last_call();
     1676                        SigMuledMinimumFinder b_min_finder(B);
     1677                        for(int i=0;i<B.size();)
     1678                        {
     1679                                LabeledPolyMuled& b = B[i];
     1680                                if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
     1681                                {
     1682                                        b.Release();
     1683                                        B.erase_and_move_from_back(i);
     1684                                }else
     1685                                {
     1686                                        b_min_finder.UpdateBy(i);
     1687                                        ++i;
     1688                                }
     1689                        }
     1690                        time_filter_b += time_from_last_call();
     1691                        if (!reduced_to_zero)
     1692                        {
     1693                                LabeledPolyMuled bnew;
     1694                                bnew.Init();
     1695                                for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
     1696                                {
     1697                                        bnew.FillBy((*ir)->p_, *p);
     1698                                        bool rejected = false;
     1699                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
     1700                                        {
     1701                                                if ((*ir2)->sig_divides(bnew))
     1702                                                {
     1703                                                        rejected = true;
     1704                                                        break;
     1705                                                }
     1706                                        }
     1707                                        time_add_b1_testings += time_from_last_call();
     1708                                        if (!rejected)
     1709                                        {
     1710                                                B.push_back(bnew);
     1711                                                b_min_finder.UpdateBy(B.size() - 1);
     1712                                                bnew.Init();
     1713                                                time_add_b1_insertion += time_from_last_call();
     1714                                        }
     1715                                }
     1716                                for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
     1717                                {
     1718                                        if (!gvw_less(*ir, p)) break;
     1719                                        if ((*ir)->p_ == NULL) continue;
     1720                                        bool rejected = false;
     1721                                        bnew.FillBy(p->p_, *(*ir));
     1722                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
     1723                                        {
     1724                                                if ((*ir2)->sig_divides(bnew))
     1725                                                {
     1726                                                        rejected = true;
     1727                                                        break;
     1728                                                }
     1729                                        }
     1730                                        if (!rejected)
     1731                                        {
     1732                                                B.push_back(bnew);
     1733                                                b_min_finder.UpdateBy(B.size() - 1);
     1734                                                bnew.Init();
     1735                                        }
     1736                                }
     1737                                bnew.Release();
     1738                                time_add_b2 += time_from_last_call();
     1739                        }
     1740      /*
     1741                                printf("B = \n");
     1742                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     1743                                {
     1744                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
     1745          //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
     1746                                }
     1747        */
     1748                        if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
     1749                        {
     1750                                break;
     1751                        }else{
     1752                                p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
     1753                                B.erase_and_move_from_back(b_min_finder.minimum_idx_);
     1754                        }
     1755                }
     1756                idDelete(&I0);
     1757                I0 = idInit(R.size());
     1758                int i0_idx = 0;
     1759                for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
     1760                {
     1761                        std::swap(I0->m[i0_idx], (*ir)->p_);
     1762                        delete (*ir);
     1763                       
     1764                }
     1765                R.clear();
     1766        }
     1767
     1768        printf("time time_interred = %d\n", time_interred);
     1769        printf("time time_prepare = %d\n", time_prepare);
     1770        printf("time time_reduction_search = %d\n", time_reduction_search);
     1771        printf("time time_reduction = %d\n", time_reduction);
     1772        printf("time time_add_r = %d\n", time_add_r);
     1773        printf("time time_filter_b = %d\n", time_filter_b);
     1774        printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
     1775        printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
     1776        printf("time time_add_b2 = %d\n", time_add_b2);
     1777
     1778        printf("ZERO REDUCTIONS: %d\n", zero_reductions);
     1779
     1780        return I0;
     1781}
     1782ideal ssgnoninc (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
     1783{
     1784  int
     1785    time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
     1786                  time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
     1787                  time_add_b2 = 0;
     1788
     1789  time_from_last_call();
     1790  int current_input_idx = 0;
     1791  while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
     1792  {
     1793    ++current_input_idx;
     1794  }
     1795  ideal I0 = idInit(1);
     1796  if (current_input_idx >= IDELEMS(F))
     1797  {
     1798    return I0;
     1799  }
     1800  I0->m[0] = pCopy(F->m[current_input_idx]);
     1801  int zero_reductions = 0;
     1802  LabeledPoly::GvwLess gvw_less;
     1803  poly pEins = pOne();
     1804  // made these global for non-incremental computation
     1805  // -------------------------------------------------
     1806  LPolysByGvw R;
     1807  LPolysMuledBySig B;
     1808  SigMuledMinimumFinder b_min_finder(B);
     1809  LabeledPoly* p;
     1810  LPolysByGvw::iterator first_zero_sig_temp = R.begin();
     1811  bool set_first_zero_sig                   = true;
     1812  // -------------------------------------------------
     1813  for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
     1814  {
     1815    if (!F->m[current_input_idx]) continue;
     1816    idDelDiv(I0);
     1817    idSkipZeroes(I0);
     1818#ifndef SSG_NO_INTERRED
     1819    std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
     1820
     1821    ideal I0_tail_reduced = idInit(IDELEMS(I0));
     1822    //tail reducton
     1823    for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
     1824    {
     1825      poly p_old = NULL;
     1826      std::swap(p_old,I0->m[n0]);
     1827      poly p_new = kNF(I0, Q, p_old);
     1828      pDelete(&p_old);
     1829      I0_tail_reduced->m[n0] = p_new;
     1830    }
     1831    std::swap(I0_tail_reduced->m[0], I0->m[0]);
     1832    idDelete(&I0);
     1833    I0 = I0_tail_reduced;
     1834#endif
     1835    time_interred += time_from_last_call();
     1836    //LPolysByGvw R;
     1837    //LPolysMuledBySig B;
     1838    //LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
     1839    p = LabeledPoly::CreateOneSig(F->m[current_input_idx],
     1840        current_input_idx);
     1841    for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     1842    {
     1843      R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
     1844    }
     1845    //const LPolysByGvw::iterator first_zero_sig = R.begin();
     1846    if (set_first_zero_sig)
     1847    {
     1848      first_zero_sig_temp = R.begin();
     1849      set_first_zero_sig  = false;
     1850    }
     1851    /*
     1852       for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     1853       {
     1854       for (int m0 = n0-1; m0>=0; --m0)
     1855       {
     1856       R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0], n0, I0->m[m0], m0));
     1857       }
     1858       }
     1859       */
     1860    for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     1861    {
     1862      //R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
     1863      R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0],current_input_idx+1,F->m[current_input_idx]));
     1864    }
     1865    /*
     1866       printf("\nR-init = \n");
     1867       for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     1868       {
     1869       printf("p = ");pWrite((*ir)->p_);
     1870       printf("s = ");pWrite((*ir)->s_monom_);
     1871       }
     1872       */
     1873    LabeledPolyMuled bnew;
     1874    bnew.Init();
     1875    bnew.FillBy(pEins, *p);
     1876    LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig_temp;
     1877    /*
     1878       const LPolysByGvw::iterator p_insert_pos =
     1879       R.insert(known_gvw_greater_p, p);
     1880       */
     1881    bool rejected = false;
     1882    //SigMuledMinimumFinder b_min_finder(B);
     1883    //SigMuledMinimumFinder b_min_finder(B);
     1884    /*
     1885       for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
     1886       {
     1887       if ((*ir2)->sig_divides(bnew))
     1888       {
     1889       rejected = true;
     1890       break;
     1891       }
     1892       }
     1893       */
     1894    if (!rejected)
     1895    {
     1896      B.push_back(bnew);
     1897      b_min_finder.UpdateBy(B.size() - 1);
     1898      bnew.Init();
     1899      //time_add_b1_insertion += time_from_last_call();
     1900    }
     1901    bnew.Release();
     1902  }
     1903  const LPolysByGvw::iterator first_zero_sig = first_zero_sig_temp;
     1904  //SigMuledMinimumFinder b_min_finder(B);
     1905  /*
     1906  printf("B = \n");
     1907  for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     1908  {
     1909    printf("smuled = ");pWrite((*ib).smuled_monom_);
     1910    //printf("s = ");pWrite((ib)->not_muled_.s_monom_);
     1911  }
     1912  */
     1913  time_prepare += time_from_last_call();
     1914  // first test in B
     1915  if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
     1916  {
     1917    return I0;
     1918    //break;
     1919  }else{
     1920    p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
     1921    B.erase_and_move_from_back(b_min_finder.minimum_idx_);
     1922  }
     1923  while(1)
     1924  {
     1925    bool reduced_to_zero = false;
     1926    LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
     1927#if 1
     1928    /*
     1929       if (n ==  IDELEMS(F) - 1)
     1930       {
     1931       */
     1932    /*
     1933       printf("\nR = \n");
     1934       for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     1935       {
     1936       printf("p = ");pWrite((*ir)->p_);
     1937       printf("s = ");pWrite((*ir)->s_monom_);
     1938       }
     1939       printf("B = \n");
     1940       for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     1941       {
     1942       printf("smuled = ");pWrite((*ib).smuled_monom_);
     1943    //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
     1944    }
     1945    */
     1946    /*
     1947       }
     1948       */
     1949#endif
     1950    while(1)
     1951    {
     1952      //printf("p to reduce = ");pWrite (p->p_);
     1953      bool was_reduced = false;
     1954      LPolysByGvw::iterator ir = --R.end();
     1955      while(1)
     1956      {
     1957        was_reduced = p->can_reduce_by(*ir);
     1958        if (was_reduced)
     1959        {
     1960          time_reduction_search += time_from_last_call();
     1961          p->reduce_by(*ir);
     1962          time_reduction += time_from_last_call();
     1963          break;
     1964        }
     1965        if (ir == known_gvw_greater_p) break;
     1966        --ir;
     1967      }
     1968      if (!was_reduced && ir != R.begin())
     1969      {
     1970        --ir;
     1971        while(1)
     1972        {
     1973          if (!gvw_less(p, *ir))
     1974          {
     1975            ++ir;
     1976            break;
     1977          }
     1978          was_reduced = p->can_reduce_by(*ir);
     1979          if (was_reduced)
     1980          {
     1981            time_reduction_search += time_from_last_call();
     1982            p->reduce_by(*ir);
     1983            time_reduction += time_from_last_call();
     1984            break;
     1985          }
     1986          if (ir == R.begin()) break;
     1987          --ir;
     1988        }
     1989        known_gvw_greater_p = ir;
     1990      }
     1991      if (!was_reduced) break;
     1992      reduced_to_zero = p->p_ == NULL;
     1993      if (reduced_to_zero)
     1994      {
     1995        ++zero_reductions;
     1996        known_gvw_greater_p = R.begin();
     1997        break;
     1998      }
     1999    }
     2000    time_reduction_search += time_from_last_call();
     2001    const LPolysByGvw::iterator p_insert_pos =
     2002      R.insert(known_gvw_greater_p, p);
     2003    time_add_r += time_from_last_call();
     2004    SigMuledMinimumFinder b_min_finder(B);
     2005    for(int i=0;i<B.size();)
     2006    {
     2007      LabeledPolyMuled& b = B[i];
     2008      if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
     2009      {
     2010        b.Release();
     2011        B.erase_and_move_from_back(i);
     2012      }else
     2013      {
     2014        b_min_finder.UpdateBy(i);
     2015        ++i;
     2016      }
     2017    }
     2018    time_filter_b += time_from_last_call();
     2019    if (!reduced_to_zero)
     2020    {
     2021      LabeledPolyMuled bnew;
     2022      bnew.Init();
     2023       /*
     2024        printf("\nR = \n");
     2025       for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     2026       {
     2027       printf("p = ");pWrite((*ir)->p_);
     2028       printf("s = ");pWrite((*ir)->s_monom_);
     2029       }
     2030       */
     2031      for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
     2032      {
     2033        //printf ("pNew = "); pWrite(p->p_);
     2034        bnew.FillBy((*ir)->p_, *p);
     2035        bool rejected = false;
     2036        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
     2037        {
     2038          if ((*ir2)->sig_divides(bnew))
     2039          {
     2040            rejected = true;
     2041            break;
     2042          }
     2043        }
     2044        time_add_b1_testings += time_from_last_call();
     2045        if (!rejected)
     2046        {
     2047          B.push_back(bnew);
     2048          b_min_finder.UpdateBy(B.size() - 1);
     2049          bnew.Init();
     2050          time_add_b1_insertion += time_from_last_call();
     2051        }
     2052      }
     2053      for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
     2054      {
     2055        if (!gvw_less(*ir, p)) break;
     2056        if ((*ir)->p_ == NULL) continue;
     2057        bool rejected = false;
     2058        bnew.FillBy(p->p_, *(*ir));
     2059        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
     2060        {
     2061          if ((*ir2)->sig_divides(bnew))
     2062          {
     2063            rejected = true;
     2064            break;
     2065          }
     2066        }
     2067        if (!rejected)
     2068        {
     2069          B.push_back(bnew);
     2070          b_min_finder.UpdateBy(B.size() - 1);
     2071          bnew.Init();
     2072        }
     2073      }
     2074      bnew.Release();
     2075      time_add_b2 += time_from_last_call();
     2076    }
     2077    /*
     2078       printf("B = \n");
     2079       for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     2080       {
     2081       printf("smuled = ");pWrite((*ib).smuled_monom_);
     2082    //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
     2083    }
     2084    */
     2085    if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
     2086    {
     2087      break;
     2088    }else{
     2089      p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
     2090      B.erase_and_move_from_back(b_min_finder.minimum_idx_);
     2091    }
     2092  }
     2093  idDelete(&I0);
     2094  I0 = idInit(R.size());
     2095  int i0_idx = 0;
     2096  for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
     2097  {
     2098    std::swap(I0->m[i0_idx], (*ir)->p_);
     2099    delete (*ir);
     2100
     2101  }
     2102  R.clear();
     2103
     2104  printf("time time_interred = %d\n", time_interred);
     2105  printf("time time_prepare = %d\n", time_prepare);
     2106  printf("time time_reduction_search = %d\n", time_reduction_search);
     2107  printf("time time_reduction = %d\n", time_reduction);
     2108  printf("time time_add_r = %d\n", time_add_r);
     2109  printf("time time_filter_b = %d\n", time_filter_b);
     2110  printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
     2111  printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
     2112  printf("time time_add_b2 = %d\n", time_add_b2);
     2113
     2114  printf("ZERO REDUCTIONS: %d\n", zero_reductions);
     2115
     2116  return I0;
     2117}
     2118ideal ssg (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
     2119{
     2120        int
     2121                time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
     2122                time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
     2123                time_add_b2 = 0;
     2124
     2125        time_from_last_call();
     2126        int current_input_idx = 0;
     2127        while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
     2128        {
     2129                ++current_input_idx;
     2130        }
     2131        ideal I0 = idInit(1);
     2132        if (current_input_idx >= IDELEMS(F))
     2133        {
     2134                return I0;
     2135        }
     2136        I0->m[0] = pCopy(F->m[current_input_idx]);
     2137        int zero_reductions = 0;
     2138        LabeledPoly::GvwLess gvw_less;
     2139        for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
     2140        {
     2141                if (!F->m[current_input_idx]) continue;
     2142                idDelDiv(I0);
     2143                idSkipZeroes(I0);
     2144#ifndef SSG_NO_INTERRED
     2145                std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
     2146               
     2147                ideal I0_tail_reduced = idInit(IDELEMS(I0));
     2148                //tail reducton
     2149                for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
     2150                {
     2151                        poly p_old = NULL;
     2152                        std::swap(p_old,I0->m[n0]);
     2153                        poly p_new = kNF(I0, Q, p_old);
     2154                        pDelete(&p_old);
     2155                        I0_tail_reduced->m[n0] = p_new;
     2156                }
     2157                std::swap(I0_tail_reduced->m[0], I0->m[0]);
     2158                idDelete(&I0);
     2159                I0 = I0_tail_reduced;
     2160#endif
     2161                time_interred += time_from_last_call();
     2162                LPolysByGvw R;
     2163                LPolysMuledBySig B;
     2164                LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
     2165                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     2166                {
     2167                        R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
     2168                }
     2169                const LPolysByGvw::iterator first_zero_sig = R.begin();
     2170                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
     2171                {
     2172                        R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
     2173                }
     2174    /*
     2175                                printf("\nR-init = \n");
     2176                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     2177                                {
     2178                                        printf("p = ");pWrite((*ir)->p_);
     2179                                        printf("s = ");pWrite((*ir)->s_monom_);
     2180                                }
     2181    */
     2182                time_prepare += time_from_last_call();
     2183                while(1)
     2184                {
     2185                        bool reduced_to_zero = false;
     2186                        LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
     2187#if 1
     2188      /*
     2189                        if (n ==  IDELEMS(F) - 1)
     2190                        {
     2191      */
     2192                                /*
     2193        printf("\nR = \n");
     2194                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
     2195                                {
     2196                                        printf("p = ");pWrite((*ir)->p_);
     2197                                        printf("s = ");pWrite((*ir)->s_monom_);
     2198                                }
     2199                                printf("B = \n");
     2200                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     2201                                {
     2202                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
     2203          //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
     2204                                }
     2205        */
     2206                        /*
     2207      }
     2208      */
     2209#endif
     2210                        while(1)
     2211                        {
     2212                                bool was_reduced = false;
     2213                                LPolysByGvw::iterator ir = --R.end();
     2214        //printf("p to reduce = ");pWrite (p->p_);
     2215                                while(1)
     2216                                {
     2217                                        was_reduced = p->can_reduce_by(*ir);
     2218                                        if (was_reduced)
     2219                                        {
     2220                                                time_reduction_search += time_from_last_call();
     2221                                                p->reduce_by(*ir);
     2222                                                time_reduction += time_from_last_call();
     2223                                                break;
     2224                                        }
     2225                                        if (ir == known_gvw_greater_p) break;
     2226                                        --ir;
     2227                                }
     2228                                if (!was_reduced && ir != R.begin())
     2229                                {
     2230                                        --ir;
     2231                                        while(1)
     2232                                        {
     2233                                                if (!gvw_less(p, *ir))
     2234                                                {
     2235                                                        ++ir;
     2236                                                        break;
     2237                                                }
     2238                                                was_reduced = p->can_reduce_by(*ir);
     2239                                                if (was_reduced)
     2240                                                {
     2241                                                        time_reduction_search += time_from_last_call();
     2242                                                        p->reduce_by(*ir);
     2243                                                        time_reduction += time_from_last_call();
     2244                                                        break;
     2245                                                }
     2246                                                if (ir == R.begin()) break;
     2247                                                --ir;
     2248                                        }
     2249                                        known_gvw_greater_p = ir;
     2250                                }
     2251                                if (!was_reduced) break;
     2252                                reduced_to_zero = p->p_ == NULL;
     2253                                if (reduced_to_zero)
     2254                                {
     2255                                        ++zero_reductions;
     2256                                        known_gvw_greater_p = R.begin();
     2257                                        break;
     2258                                }
     2259                        }
     2260                        time_reduction_search += time_from_last_call();
     2261                        const LPolysByGvw::iterator p_insert_pos =
     2262                                R.insert(known_gvw_greater_p, p);
     2263                        time_add_r += time_from_last_call();
     2264                        SigMuledMinimumFinder b_min_finder(B);
     2265                        for(int i=0;i<B.size();)
     2266                        {
     2267                                LabeledPolyMuled& b = B[i];
     2268                                if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
     2269                                {
     2270                                        b.Release();
     2271                                        B.erase_and_move_from_back(i);
     2272                                }else
     2273                                {
     2274                                        b_min_finder.UpdateBy(i);
     2275                                        ++i;
     2276                                }
     2277                        }
     2278                        time_filter_b += time_from_last_call();
     2279                        if (!reduced_to_zero)
     2280                        {
     2281                                LabeledPolyMuled bnew;
     2282                                bnew.Init();
     2283                                for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
     2284                                {
     2285                                        bnew.FillBy((*ir)->p_, *p);
     2286                                        bool rejected = false;
     2287                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
     2288                                        {
     2289                                                if ((*ir2)->sig_divides(bnew))
     2290                                                {
     2291                                                        rejected = true;
     2292                                                        break;
     2293                                                }
     2294                                        }
     2295                                        time_add_b1_testings += time_from_last_call();
     2296                                        if (!rejected)
     2297                                        {
     2298                                                B.push_back(bnew);
     2299                                                b_min_finder.UpdateBy(B.size() - 1);
     2300                                                bnew.Init();
     2301                                                time_add_b1_insertion += time_from_last_call();
     2302                                        }
     2303                                }
     2304                                for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
     2305                                {
     2306                                        if (!gvw_less(*ir, p)) break;
     2307                                        if ((*ir)->p_ == NULL) continue;
     2308                                        bool rejected = false;
     2309                                        bnew.FillBy(p->p_, *(*ir));
     2310                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
     2311                                        {
     2312                                                if ((*ir2)->sig_divides(bnew))
     2313                                                {
     2314                                                        rejected = true;
     2315                                                        break;
     2316                                                }
     2317                                        }
     2318                                        if (!rejected)
     2319                                        {
     2320                                                B.push_back(bnew);
     2321                                                b_min_finder.UpdateBy(B.size() - 1);
     2322                                                bnew.Init();
     2323                                        }
     2324                                }
     2325                                bnew.Release();
     2326                                time_add_b2 += time_from_last_call();
     2327                        }
     2328                                /*
     2329        printf("B = \n");
     2330                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
     2331                                {
     2332                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
     2333          //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
     2334                                }
     2335        */
     2336                        if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
     2337                        {
     2338                                break;
     2339                        }else{
     2340                                p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
     2341                                B.erase_and_move_from_back(b_min_finder.minimum_idx_);
     2342                        }
     2343     
     2344                }
     2345                idDelete(&I0);
     2346                I0 = idInit(R.size());
     2347                int i0_idx = 0;
     2348                for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
     2349                {
     2350                        std::swap(I0->m[i0_idx], (*ir)->p_);
     2351                        delete (*ir);
     2352                       
     2353                }
     2354                R.clear();
     2355        }
     2356
     2357        printf("time time_interred = %d\n", time_interred);
     2358        printf("time time_prepare = %d\n", time_prepare);
     2359        printf("time time_reduction_search = %d\n", time_reduction_search);
     2360        printf("time time_reduction = %d\n", time_reduction);
     2361        printf("time time_add_r = %d\n", time_add_r);
     2362        printf("time time_filter_b = %d\n", time_filter_b);
     2363        printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
     2364        printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
     2365        printf("time time_add_b2 = %d\n", time_add_b2);
     2366
     2367        printf("ZERO REDUCTIONS: %d\n", zero_reductions);
     2368
     2369        return I0;
     2370}
     2371ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
     2372{
     2373  // ring order stuff:
     2374  // in sba we have (until now) two possibilities:
     2375  // 1. an incremental computation w.r.t. (C,monomial order)
     2376  // 2. a (possibly non-incremental) computation w.r.t. the
     2377  //    induced Schreyer order.
     2378  // The corresponding orders are computed in sbaRing(), depending
     2379  // on the flag strat->incremental
     2380  ideal F = F0;
     2381  ring sRing, currRingOld;
     2382  currRingOld  = currRing;
     2383  if (strat->incremental)
     2384  {
     2385    sRing = sbaRing(strat);
     2386    if (sRing!=currRingOld)
     2387    {
     2388      rChangeCurrRing (sRing);
     2389      F = idrMoveR (F0, currRingOld);
     2390    }
     2391  }
     2392#if 0
     2393  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
     2394  rWrite (currRing);
     2395  printf("\n");
     2396#endif
     2397#ifdef KDEBUG
     2398  bba_count++;
     2399  int loop_count = 0;
     2400#endif /* KDEBUG */
     2401  om_Opts.MinTrack = 5;
     2402  int   srmax,lrmax, red_result = 1;
     2403  int   olddeg,reduc;
     2404  int hilbeledeg=1,hilbcount=0,minimcnt=0;
     2405  LObject L;
     2406  BOOLEAN withT     = FALSE;
     2407  BOOLEAN newrules  = FALSE;
     2408  strat->max_lower_index = 0;
     2409
     2410  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
     2411  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
     2412  initSbaPos(strat);
     2413  //initBuchMoraPos(strat);
     2414  initHilbCrit(F,Q,&hilb,strat);
     2415  initSba(F,strat);
     2416  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
     2417  /*Shdl=*/initSbaBuchMora(F, Q,strat);
     2418  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
     2419  srmax = strat->sl;
     2420  reduc = olddeg = lrmax = 0;
     2421
     2422#ifndef NO_BUCKETS
     2423  if (!TEST_OPT_NOT_BUCKETS)
     2424    strat->use_buckets = 1;
     2425#endif
     2426
     2427  // redtailBBa against T for inhomogenous input
     2428  if (!TEST_OPT_OLDSTD)
     2429    withT = ! strat->homog;
     2430
     2431  // strat->posInT = posInT_pLength;
     2432  kTest_TS(strat);
     2433
     2434#ifdef KDEBUG
     2435#if MYTEST
     2436  if (TEST_OPT_DEBUG)
     2437  {
     2438    PrintS("bba start GB: currRing: ");
     2439    // rWrite(currRing);PrintLn();
     2440    rDebugPrint(currRing);
     2441    PrintLn();
     2442  }
     2443#endif /* MYTEST */
     2444#endif /* KDEBUG */
     2445
     2446#ifdef HAVE_TAIL_RING
     2447  if(!idIs0(F) &&(!rField_is_Ring()))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
     2448    kStratInitChangeTailRing(strat);
     2449#endif
     2450  if (BVERBOSE(23))
     2451  {
     2452    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
     2453    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
     2454    kDebugPrint(strat);
     2455  }
     2456
     2457
     2458#ifdef KDEBUG
     2459  //kDebugPrint(strat);
     2460#endif
     2461  /* compute------------------------------------------------------- */
     2462  arriAgain:
     2463  while (strat->Ll >= 0)
     2464  {
     2465    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
     2466    #ifdef KDEBUG
     2467      loop_count++;
     2468      if (TEST_OPT_DEBUG) messageSets(strat);
     2469    #endif
     2470    if (strat->Ll== 0) strat->interpt=TRUE;
     2471    if (TEST_OPT_DEGBOUND
     2472        && ((strat->honey && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
     2473            || ((!strat->honey) && (pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
     2474    {
     2475      /*
     2476       *stops computation if
     2477       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
     2478       *a predefined number Kstd1_deg
     2479       */
     2480      while ((strat->Ll >= 0)
     2481        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
     2482        && ((strat->honey && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
     2483            || ((!strat->honey) && (pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
     2484        )
     2485        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
     2486      if (strat->Ll<0) break;
     2487      else strat->noClearS=TRUE;
     2488    }
     2489    if (strat->incremental && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
     2490    {
     2491      strat->currIdx  = pGetComp(strat->L[strat->Ll].sig);
     2492#if F5C
     2493      // 1. interreduction of the current standard basis
     2494      // 2. generation of new principal syzygy rules for syzCriterion
     2495      f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
     2496            lrmax, reduc, Q, w, hilb );
     2497#endif
     2498      // initialize new syzygy rules for the next iteration step 
     2499      initSyzRules(strat);
     2500    }
     2501    /*********************************************************************
     2502     * interrreduction step is done, we can go on with the next iteration
     2503     * step of the signature-based algorithm
     2504     ********************************************************************/
     2505    /* picks the last element from the lazyset L */
     2506    strat->P = strat->L[strat->Ll];
     2507    strat->Ll--;
     2508//#if 1
     2509#ifdef DEBUGF5
     2510    Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
     2511    Print("-------------------------------------------------\n");
     2512    pWrite(strat->P.sig);
     2513    pWrite(pHead(strat->P.p));
     2514    pWrite(pHead(strat->P.p1));
     2515    pWrite(pHead(strat->P.p2));
     2516    Print("-------------------------------------------------\n");
     2517#endif
     2518    if (pNext(strat->P.p) == strat->tail)
     2519    {
     2520      // deletes the short spoly
     2521#ifdef HAVE_RINGS
     2522      if (rField_is_Ring(currRing))
     2523        pLmDelete(strat->P.p);
     2524      else
     2525#endif
     2526        pLmFree(strat->P.p);
     2527
     2528      // TODO: needs some masking
     2529      // TODO: masking needs to vanish once the signature
     2530      //       sutff is completely implemented
     2531      strat->P.p = NULL;
     2532      poly m1 = NULL, m2 = NULL;
     2533
     2534      // check that spoly creation is ok
     2535      while (strat->tailRing != currRing &&
     2536             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
     2537      {
     2538        assume(m1 == NULL && m2 == NULL);
     2539        // if not, change to a ring where exponents are at least
     2540        // large enough
     2541        if (!kStratChangeTailRing(strat))
     2542        {
     2543          WerrorS("OVERFLOW...");
     2544          break;
     2545        }
     2546      }
     2547      // create the real one
     2548      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
     2549                    strat->tailRing, m1, m2, strat->R);
     2550
     2551    }
     2552    else if (strat->P.p1 == NULL)
     2553    {
     2554      if (strat->minim > 0)
     2555        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
     2556      // for input polys, prepare reduction
     2557      strat->P.PrepareRed(strat->use_buckets);
     2558    }
     2559
     2560    if (strat->P.p == NULL && strat->P.t_p == NULL)
     2561    {
     2562      red_result = 0;
     2563    }
     2564    else
     2565    {
     2566      if (TEST_OPT_PROT)
     2567        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
     2568                &olddeg,&reduc,strat, red_result);
     2569
     2570//#if 1
     2571#ifdef DEBUGF5
     2572      Print("Poly before red: ");
     2573      pWrite(strat->P.p);
     2574#endif
     2575      /* reduction of the element choosen from L */
     2576      if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat, strat->P.checked+1))
     2577        red_result = strat->red(&strat->P,strat);
     2578      else
     2579      {
     2580        if (strat->P.lcm!=NULL)
     2581          pLmFree(strat->P.lcm);
     2582        red_result = 2;
     2583      }
     2584      if (errorreported)  break;
     2585    }
     2586
     2587    if (strat->overflow)
     2588    {
     2589        if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
     2590    }
     2591    if (strat->incremental)
     2592    {
     2593      for (int jj = 0; jj<strat->tl+1; jj++)
     2594      {
     2595        if (pGetComp(strat->T[jj].sig) == strat->currIdx)
     2596        {
     2597          strat->T[jj].is_sigsafe = FALSE;
     2598        }
     2599      }
     2600    }
     2601    else
     2602    {
     2603      for (int jj = 0; jj<strat->tl+1; jj++)
     2604      {
     2605        strat->T[jj].is_sigsafe = FALSE;
     2606      }
     2607    }
     2608
     2609    // reduction to non-zero new poly
     2610    if (red_result == 1)
     2611    {
     2612      // get the polynomial (canonicalize bucket, make sure P.p is set)
     2613      strat->P.GetP(strat->lmBin);
     2614     
     2615      // sig-safe computations may lead to wrong FDeg computation, thus we need
     2616      // to recompute it to make sure everything is alright
     2617      (strat->P).FDeg = (strat->P).pFDeg();
     2618      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
     2619      // but now, for entering S, T, we reset it
     2620      // in the inhomogeneous case: FDeg == pFDeg
     2621      if (strat->homog) strat->initEcart(&(strat->P));
     2622
     2623      /* statistic */
     2624      if (TEST_OPT_PROT) PrintS("s");
     2625
     2626      //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
     2627      // in F5E we know that the last reduced element is already the
     2628      // the one with highest signature
     2629      int pos = strat->sl+1;
     2630
     2631#ifdef KDEBUG
     2632#if MYTEST
     2633      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
     2634#endif /* MYTEST */
     2635#endif /* KDEBUG */
     2636
     2637      // reduce the tail and normalize poly
     2638      // in the ring case we cannot expect LC(f) = 1,
     2639      // therefore we call pContent instead of pNorm
     2640      /*
     2641      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
     2642      {
     2643        strat->P.pCleardenom();
     2644        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     2645        {
     2646          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     2647          strat->P.pCleardenom();
     2648        }
     2649      }
     2650      else
     2651      {
     2652        strat->P.pNorm();
     2653        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     2654          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     2655      }
     2656      */
     2657#ifdef KDEBUG
     2658      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
     2659#if MYTEST
     2660//#if 1
     2661      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
     2662#endif /* MYTEST */
     2663#endif /* KDEBUG */
     2664
     2665      // min_std stuff
     2666      if ((strat->P.p1==NULL) && (strat->minim>0))
     2667      {
     2668        if (strat->minim==1)
     2669        {
     2670          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
     2671          p_Delete(&strat->P.p2, currRing, strat->tailRing);
     2672        }
     2673        else
     2674        {
     2675          strat->M->m[minimcnt]=strat->P.p2;
     2676          strat->P.p2=NULL;
     2677        }
     2678        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
     2679          pNext(strat->M->m[minimcnt])
     2680            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
     2681                                           strat->tailRing, currRing,
     2682                                           currRing->PolyBin);
     2683        minimcnt++;
     2684      }
     2685
     2686      // enter into S, L, and T
     2687      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
     2688      if(!strat->incremental)
     2689      {
     2690        BOOLEAN overwrite = TRUE;
     2691        for (int tk=0; tk<strat->sl+1; tk++)
     2692        {
     2693          if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
     2694          {
     2695            //printf("TK %d / %d\n",tk,strat->sl);
     2696            overwrite = FALSE;
     2697            break;
     2698          }
     2699        }
     2700        //printf("OVERWRITE %d\n",overwrite);
     2701        if (overwrite)
     2702        {
     2703          int cmp = pGetComp(strat->P.sig);
     2704          int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
     2705          pGetExpV (strat->P.p,vv);
     2706          pSetExpV (strat->P.sig, vv);
     2707          pSetComp (strat->P.sig,cmp);
     2708
     2709          strat->P.sevSig = pGetShortExpVector (strat->P.sig);
     2710          for(int ps=0;ps<strat->sl+1;ps++)
     2711          {
     2712            int i = strat->syzl;
     2713
     2714            strat->newt = TRUE;
     2715            if (strat->syzl == strat->syzmax)
     2716            {
     2717              pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
     2718              strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
     2719                  (strat->syzmax)*sizeof(unsigned long),
     2720                  ((strat->syzmax)+setmaxTinc)
     2721                  *sizeof(unsigned long));
     2722              strat->syzmax += setmaxTinc;
     2723            }
     2724            strat->syz[i] = pCopy(strat->P.sig);
     2725            // add LM(F->m[i]) to the signature to get a Schreyer order
     2726            // without changing the underlying polynomial ring at all
     2727            p_ExpVectorAdd (strat->syz[i],strat->S[ps],currRing); 
     2728            // since p_Add_q() destroys all input
     2729            // data we need to recreate help
     2730            // each time
     2731            // ----------------------------------------------------------
     2732            // in the Schreyer order we always know that the multiplied
     2733            // module monomial strat->P.sig gives the leading monomial of
     2734            // the corresponding principal syzygy
     2735            // => we do not need to compute the "real" syzygy completely
     2736            poly help = pCopy(strat->sig[ps]);
     2737            p_ExpVectorAdd (help,strat->P.p,currRing); 
     2738            strat->syz[i] = p_Add_q(strat->syz[i],help,currRing);
     2739            //printf("%d. SYZ  ",i+1);
     2740            //pWrite(strat->syz[i]);
     2741            strat->sevSyz[i] = p_GetShortExpVector(strat->syz[i],currRing);
     2742            strat->syzl++;
     2743          }
     2744        }
     2745      }
     2746        enterT(strat->P, strat);
     2747        strat->T[strat->tl].is_sigsafe = FALSE;
     2748#ifdef HAVE_RINGS
     2749      if (rField_is_Ring(currRing))
     2750        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
     2751      else
     2752#endif
     2753        enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
     2754      // posInS only depends on the leading term
     2755      strat->enterS(strat->P, pos, strat, strat->tl);
     2756//#if 1
     2757#if DEBUGF50
     2758    printf("---------------------------\n");
     2759    Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
     2760    Print("LEAD POLY:  "); pWrite(pHead(strat->S[strat->sl]));
     2761    Print("SIGNATURE:  "); pWrite(strat->sig[strat->sl]);
     2762#endif
     2763      /*
     2764      if (newrules)
     2765      {
     2766        newrules  = FALSE;
     2767      }
     2768      */
     2769#if 0
     2770      int pl=pLength(strat->P.p);
     2771      if (pl==1)
     2772      {
     2773        //if (TEST_OPT_PROT)
     2774        //PrintS("<1>");
     2775      }
     2776      else if (pl==2)
     2777      {
     2778        //if (TEST_OPT_PROT)
     2779        //PrintS("<2>");
     2780      }
     2781#endif
     2782      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
     2783//      Print("[%d]",hilbeledeg);
     2784      if (strat->P.lcm!=NULL)
     2785#ifdef HAVE_RINGS
     2786        pLmDelete(strat->P.lcm);
     2787#else
     2788        pLmFree(strat->P.lcm);
     2789#endif
     2790      if (strat->sl>srmax) srmax = strat->sl;
     2791    }
     2792    else
     2793    {
     2794      // adds signature of the zero reduction to
     2795      // strat->syz. This is the leading term of
     2796      // syzygy and can be used in syzCriterion()
     2797      // the signature is added if and only if the
     2798      // pair was not detected by the rewritten criterion in strat->red = redSig
     2799      if (red_result!=2) {
     2800        zeroreductions++;
     2801        enterSyz(strat->P,strat);
     2802//#if 1
     2803#ifdef DEBUGF5
     2804        Print("ADDING STUFF TO SYZ :  ");
     2805        pWrite(strat->P.p);
     2806        pWrite(strat->P.sig);
     2807#endif
     2808      }
     2809      if (strat->P.p1 == NULL && strat->minim > 0)
     2810      {
     2811        p_Delete(&strat->P.p2, currRing, strat->tailRing);
     2812      }
     2813    }
     2814
     2815#ifdef KDEBUG
     2816    memset(&(strat->P), 0, sizeof(strat->P));
     2817#endif /* KDEBUG */
     2818    kTest_TS(strat);
     2819  }
     2820#ifdef KDEBUG
     2821#if MYTEST
     2822  PrintS("bba finish GB: currRing: "); rWrite(currRing);
     2823#endif /* MYTEST */
     2824  if (TEST_OPT_DEBUG) messageSets(strat);
     2825#endif /* KDEBUG */
     2826
     2827  if (TEST_OPT_SB_1)
     2828  {
     2829    int k=1;
     2830    int j;
     2831    while(k<=strat->sl)
     2832    {
     2833      j=0;
     2834      loop
     2835      {
     2836        if (j>=k) break;
     2837        clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
     2838        j++;
     2839      }
     2840      k++;
     2841    }
     2842  }
     2843
     2844  /* complete reduction of the standard basis--------- */
     2845  if (TEST_OPT_REDSB)
     2846  {
     2847    completeReduce(strat);
     2848#ifdef HAVE_TAIL_RING
     2849    if (strat->completeReduce_retry)
     2850    {
     2851      // completeReduce needed larger exponents, retry
     2852      // to reduce with S (instead of T)
     2853      // and in currRing (instead of strat->tailRing)
     2854      cleanT(strat);strat->tailRing=currRing;
     2855      int i;
     2856      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
     2857      completeReduce(strat);
     2858    }
     2859#endif
     2860  }
     2861  else if (TEST_OPT_PROT) PrintLn();
     2862
     2863  exitSba(strat);
     2864  if (TEST_OPT_WEIGHTM)
     2865  {
     2866    pRestoreDegProcs(pFDegOld, pLDegOld);
     2867    if (ecartWeights)
     2868    {
     2869      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
     2870      ecartWeights=NULL;
     2871    }
     2872  }
     2873  if (TEST_OPT_PROT) messageStat(srmax,lrmax,hilbcount,strat);
     2874  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
     2875
     2876#ifdef KDEBUG
     2877#if MYTEST
     2878  PrintS("bba_end: currRing: "); rWrite(currRing);
     2879#endif /* MYTEST */
     2880#endif /* KDEBUG */
     2881  // using F5C it is possible that there is some data stored in the last
     2882  // entries of strat->Shdl which are dirty, i.e. not correct, but also not NULL
     2883  // => we need to delete them before return the ideal
     2884#if F5C
     2885  for(int i=strat->sl+1;i<IDELEMS(strat->Shdl);i++)
     2886  {
     2887    //pDelete (&strat->Shdl->m[i]);
     2888    strat->Shdl->m[i] = NULL;
     2889  }
     2890#endif
     2891  if (strat->incremental && sRing!=currRingOld)
     2892  {
     2893    rChangeCurrRing (currRingOld);
     2894    F0          = idrMoveR (F, sRing);
     2895    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing);
     2896    rDelete (sRing);
     2897  }
     2898  idTest(strat->Shdl);
     2899
     2900#ifdef DEBUGF5
     2901  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
     2902  int oo = 0;
     2903  while (oo<IDELEMS(strat->Shdl))
     2904  {
     2905    printf(" %d.   ",oo+1);
     2906    pWrite(pHead(strat->Shdl->m[oo]));
     2907    oo++;
     2908  }
     2909#endif
     2910  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
     2911  zeroreductions  = 0;
    12962912  return (strat->Shdl);
    12972913}
     
    14473063  return res;
    14483064}
     3065
     3066#if F5C
     3067/*********************************************************************
     3068* interrreduction step of the signature-based algorithm:
     3069* 1. all strat->S are interpreted as new critical pairs
     3070* 2. those pairs need to be completely reduced by the usual (non sig-
     3071*    safe) reduction process (including tail reductions)
     3072* 3. strat->S and strat->T are completely new computed in these steps
     3073********************************************************************/
     3074void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
     3075          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
     3076          intvec *w,intvec *hilb )
     3077{
     3078  int Ll_old, red_result = 1;
     3079  BOOLEAN withT = FALSE;
     3080  int pos  = 0;
     3081  hilbeledeg=1;
     3082  hilbcount=0;
     3083  minimcnt=0;
     3084  srmax = 0; // strat->sl is 0 at this point
     3085  reduc = olddeg = lrmax = 0;
     3086  // we cannot use strat->T anymore
     3087  //cleanT(strat);
     3088  //strat->tl = -1;
     3089  Ll_old    = strat->Ll;
     3090  while (strat->tl >= 0)
     3091  {
     3092    if(!strat->T[strat->tl].is_redundant)
     3093    {
     3094      LObject h;
     3095      h.p = strat->T[strat->tl].p;
     3096      h.tailRing = strat->T[strat->tl].tailRing;
     3097      h.t_p = strat->T[strat->tl].t_p;
     3098      if (h.p!=NULL)
     3099      {
     3100        if (pOrdSgn==-1)
     3101        {
     3102          cancelunit(&h); 
     3103          deleteHC(&h, strat);
     3104        }
     3105        if (h.p!=NULL)
     3106        {
     3107          if (TEST_OPT_INTSTRATEGY)
     3108          {
     3109            //pContent(h.p);
     3110            h.pCleardenom(); // also does a pContent
     3111          }
     3112          else
     3113          {
     3114            h.pNorm();
     3115          }
     3116          strat->initEcart(&h);
     3117          pos = strat->Ll+1;
     3118          h.sev = pGetShortExpVector(h.p);
     3119          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
     3120        }
     3121      }
     3122    }
     3123    strat->tl--;
     3124  }
     3125  strat->sl = -1;
     3126#if 0
     3127//#ifdef HAVE_TAIL_RING
     3128  if(!rField_is_Ring())  // create strong gcd poly computes with tailring and S[i] ->to be fixed
     3129    kStratInitChangeTailRing(strat);
     3130#endif
     3131  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
     3132  //strat->sl = -1;
     3133  /* picks the last element from the lazyset L */
     3134  while (strat->Ll>Ll_old)
     3135  {
     3136    strat->P = strat->L[strat->Ll];
     3137    strat->Ll--;
     3138//#if 1
     3139#ifdef DEBUGF5
     3140    Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
     3141    Print("-------------------------------------------------\n");
     3142    pWrite(pHead(strat->P.p));
     3143    pWrite(pHead(strat->P.p1));
     3144    pWrite(pHead(strat->P.p2));
     3145    printf("%d\n",strat->tl);
     3146    Print("-------------------------------------------------\n");
     3147#endif
     3148    if (pNext(strat->P.p) == strat->tail)
     3149    {
     3150      // deletes the short spoly
     3151#ifdef HAVE_RINGS
     3152      if (rField_is_Ring(currRing))
     3153        pLmDelete(strat->P.p);
     3154      else
     3155#endif
     3156        pLmFree(strat->P.p);
     3157
     3158      // TODO: needs some masking
     3159      // TODO: masking needs to vanish once the signature
     3160      //       sutff is completely implemented
     3161      strat->P.p = NULL;
     3162      poly m1 = NULL, m2 = NULL;
     3163
     3164      // check that spoly creation is ok
     3165      while (strat->tailRing != currRing &&
     3166          !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
     3167      {
     3168        assume(m1 == NULL && m2 == NULL);
     3169        // if not, change to a ring where exponents are at least
     3170        // large enough
     3171        if (!kStratChangeTailRing(strat))
     3172        {
     3173          WerrorS("OVERFLOW...");
     3174          break;
     3175        }
     3176      }
     3177      // create the real one
     3178      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
     3179          strat->tailRing, m1, m2, strat->R);
     3180    }
     3181    else if (strat->P.p1 == NULL)
     3182    {
     3183      if (strat->minim > 0)
     3184        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
     3185      // for input polys, prepare reduction
     3186      strat->P.PrepareRed(strat->use_buckets);
     3187    }
     3188
     3189    if (strat->P.p == NULL && strat->P.t_p == NULL)
     3190    {
     3191      red_result = 0;
     3192    }
     3193    else
     3194    {
     3195      if (TEST_OPT_PROT)
     3196        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
     3197            &olddeg,&reduc,strat, red_result);
     3198
     3199#ifdef DEBUGF5
     3200      Print("Poly before red: ");
     3201      pWrite(strat->P.p);
     3202#endif
     3203      /* complete reduction of the element choosen from L */
     3204      red_result = strat->red2(&strat->P,strat);
     3205      if (errorreported)  break;
     3206    }
     3207
     3208    if (strat->overflow)
     3209    {
     3210      if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
     3211    }
     3212
     3213    // reduction to non-zero new poly
     3214    if (red_result == 1)
     3215    {
     3216      // get the polynomial (canonicalize bucket, make sure P.p is set)
     3217      strat->P.GetP(strat->lmBin);
     3218      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
     3219      // but now, for entering S, T, we reset it
     3220      // in the inhomogeneous case: FDeg == pFDeg
     3221      if (strat->homog) strat->initEcart(&(strat->P));
     3222
     3223      /* statistic */
     3224      if (TEST_OPT_PROT) PrintS("s");
     3225
     3226      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
     3227
     3228#ifdef KDEBUG
     3229#if MYTEST
     3230      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
     3231#endif /* MYTEST */
     3232#endif /* KDEBUG */
     3233
     3234      // reduce the tail and normalize poly
     3235      // in the ring case we cannot expect LC(f) = 1,
     3236      // therefore we call pContent instead of pNorm
     3237#if F5CTAILRED
     3238      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
     3239      {
     3240        strat->P.pCleardenom();
     3241        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     3242        {
     3243          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     3244          strat->P.pCleardenom();
     3245        }
     3246      }
     3247      else
     3248      {
     3249        strat->P.pNorm();
     3250        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
     3251          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
     3252      }
     3253#endif
     3254#ifdef KDEBUG
     3255      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
     3256#if MYTEST
     3257//#if 1
     3258      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
     3259#endif /* MYTEST */
     3260#endif /* KDEBUG */
     3261
     3262      // min_std stuff
     3263      if ((strat->P.p1==NULL) && (strat->minim>0))
     3264      {
     3265        if (strat->minim==1)
     3266        {
     3267          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
     3268          p_Delete(&strat->P.p2, currRing, strat->tailRing);
     3269        }
     3270        else
     3271        {
     3272          strat->M->m[minimcnt]=strat->P.p2;
     3273          strat->P.p2=NULL;
     3274        }
     3275        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
     3276          pNext(strat->M->m[minimcnt])
     3277            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
     3278                strat->tailRing, currRing,
     3279                currRing->PolyBin);
     3280        minimcnt++;
     3281      }
     3282
     3283      // enter into S, L, and T
     3284      // here we need to recompute new signatures, but those are trivial ones
     3285      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
     3286      enterT(strat->P, strat);
     3287      // posInS only depends on the leading term
     3288      strat->enterS(strat->P, pos, strat, strat->tl);
     3289//#if 1
     3290#ifdef DEBUGF5
     3291      Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
     3292      pWrite(pHead(strat->S[strat->sl]));
     3293      pWrite(strat->sig[strat->sl]);
     3294#endif
     3295      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
     3296      //      Print("[%d]",hilbeledeg);
     3297      if (strat->P.lcm!=NULL)
     3298#ifdef HAVE_RINGS
     3299        pLmDelete(strat->P.lcm);
     3300#else
     3301      pLmFree(strat->P.lcm);
     3302#endif
     3303      if (strat->sl>srmax) srmax = strat->sl;
     3304    }
     3305    else
     3306    {
     3307      // adds signature of the zero reduction to
     3308      // strat->syz. This is the leading term of
     3309      // syzygy and can be used in syzCriterion()
     3310      // the signature is added if and only if the
     3311      // pair was not detected by the rewritten criterion in strat->red = redSig
     3312      if (strat->P.p1 == NULL && strat->minim > 0)
     3313      {
     3314        p_Delete(&strat->P.p2, currRing, strat->tailRing);
     3315      }
     3316    }
     3317
     3318#ifdef KDEBUG
     3319    memset(&(strat->P), 0, sizeof(strat->P));
     3320#endif /* KDEBUG */
     3321  }
     3322  int cc = 0;
     3323  while (cc<strat->tl+1)
     3324  {
     3325    strat->T[cc].sig        = pOne();
     3326    p_SetComp(strat->T[cc].sig,cc+1,currRing);
     3327    strat->T[cc].sevSig     = pGetShortExpVector(strat->T[cc].sig);
     3328    strat->sig[cc]          = strat->T[cc].sig;
     3329    strat->sevSig[cc]       = strat->T[cc].sevSig;
     3330    strat->T[cc].is_sigsafe = TRUE; 
     3331    cc++;
     3332  }
     3333  strat->max_lower_index = strat->tl;
     3334  // set current signature index of upcoming iteration step
     3335  // NOTE:  this needs to be set here, as otherwise initSyzRules cannot compute
     3336  //        the corresponding syzygy rules correctly
     3337  strat->currIdx = cc+1;
     3338  for (int cd=strat->Ll; cd>=0; cd--)
     3339  {
     3340    p_SetComp(strat->L[cd].sig,cc+1,currRing);
     3341    cc++;
     3342  }
     3343//#if 1
     3344#if DEBUGF5
     3345  Print("------------------- STRAT S ---------------------\n");
     3346  cc = 0;
     3347  while (cc<strat->tl+1)
     3348  {
     3349    pWrite(pHead(strat->S[cc]));
     3350    pWrite(strat->sig[cc]);
     3351    printf("- - - - - -\n");
     3352    cc++;
     3353  }
     3354  Print("-------------------------------------------------\n");
     3355  Print("------------------- STRAT T ---------------------\n");
     3356  cc = 0;
     3357  while (cc<strat->tl+1)
     3358  {
     3359    pWrite(pHead(strat->T[cc].p));
     3360    pWrite(strat->T[cc].sig);
     3361    printf("- - - - - -\n");
     3362    cc++;
     3363  }
     3364  Print("-------------------------------------------------\n");
     3365  Print("------------------- STRAT L ---------------------\n");
     3366  cc = 0;
     3367  while (cc<strat->Ll+1)
     3368  {
     3369    pWrite(pHead(strat->L[cc].p));
     3370    pWrite(pHead(strat->L[cc].p1));
     3371    pWrite(pHead(strat->L[cc].p2));
     3372    pWrite(strat->L[cc].sig);
     3373    printf("- - - - - -\n");
     3374    cc++;
     3375  }
     3376  Print("-------------------------------------------------\n");
     3377  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
     3378#endif
     3379
     3380}
     3381#endif
    14493382
    14503383/* shiftgb stuff */
  • kernel/kutil.cc

    rcffd3e r83be980  
    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,j,compare;
     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==pOrdSgn)
     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]);
     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)== pOrdSgn)
     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) == pOrdSgn) return en;
     4483    return an;
     4484  }
     4485  i=(an+en) / 2;
     4486  if (pLmCmp(set[i].sig,p->sig) == pOrdSgn) 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*/
     
    50185571  }
    50195572}
     5573
     5574void initSLSba (ideal F, ideal Q,kStrategy strat)
     5575{
     5576  int   i,j,pos, ctr=0, ps=0;
     5577  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
     5578  else i=setmaxT;
     5579  strat->ecartS =   initec(i);
     5580  strat->fromS  =   initec(i);
     5581  strat->sevS   =   initsevS(i);
     5582  strat->sevSig =   initsevS(i);
     5583  strat->S_2_R  =   initS_2_R(i);
     5584  strat->fromQ  =   NULL;
     5585  strat->Shdl   =   idInit(i,F->rank);
     5586  strat->S      =   strat->Shdl->m;
     5587  strat->sig    =   (poly *)omAlloc0(i*sizeof(poly));
     5588  if (!strat->incremental)
     5589  {
     5590    strat->syz    = (poly *)omAlloc0(i*sizeof(poly));
     5591    strat->sevSyz = initsevS(i);
     5592    strat->syzmax = i;
     5593    strat->syzl   = 0;
     5594  }
     5595  /*- put polys into S -*/
     5596  if (Q!=NULL)
     5597  {
     5598    strat->fromQ=initec(i);
     5599    memset(strat->fromQ,0,i*sizeof(int));
     5600    for (i=0; i<IDELEMS(Q); i++)
     5601    {
     5602      if (Q->m[i]!=NULL)
     5603      {
     5604        LObject h;
     5605        h.p = pCopy(Q->m[i]);
     5606        if (pOrdSgn==-1)
     5607        {
     5608          deleteHC(&h,strat);
     5609        }
     5610        if (TEST_OPT_INTSTRATEGY)
     5611        {
     5612          //pContent(h.p);
     5613          h.pCleardenom(); // also does a pContent
     5614        }
     5615        else
     5616        {
     5617          h.pNorm();
     5618        }
     5619        if (h.p!=NULL)
     5620        {
     5621          strat->initEcart(&h);
     5622          if (strat->sl==-1)
     5623            pos =0;
     5624          else
     5625          {
     5626            pos = posInS(strat,strat->sl,h.p,h.ecart);
     5627          }
     5628          h.sev = pGetShortExpVector(h.p);
     5629          strat->enterS(h,pos,strat,-1);
     5630          strat->fromQ[pos]=1;
     5631        }
     5632      }
     5633    }
     5634  }
     5635  for (i=0; i<IDELEMS(F); i++)
     5636  {
     5637    if (F->m[i]!=NULL)
     5638    {
     5639      LObject h;
     5640      h.p = pCopy(F->m[i]);
     5641      h.sig = pOne();
     5642      //h.sig = pInit();
     5643      //p_SetCoeff(h.sig,nInit(1),currRing);
     5644      p_SetComp(h.sig,i+1,currRing);
     5645      // if we are working with the Schreyer order we generate it
     5646      // by multiplying the initial signatures with the leading monomial
     5647      // of the corresponding initial polynomials generating the ideal
     5648      // => we can keep the underlying monomial order and get a Schreyer
     5649      //    order without any bigger overhead
     5650      if (!strat->incremental)
     5651      {
     5652        p_ExpVectorAdd (h.sig,F->m[i],currRing); 
     5653      }
     5654      h.sevSig = pGetShortExpVector(h.sig);
     5655#ifdef DEBUGF5
     5656      pWrite(h.p);
     5657      pWrite(h.sig);
     5658#endif
     5659      if (h.p!=NULL)
     5660      {
     5661        if (pOrdSgn==-1)
     5662        {
     5663          cancelunit(&h);  /*- tries to cancel a unit -*/
     5664          deleteHC(&h, strat);
     5665        }
     5666        if (h.p!=NULL)
     5667        {
     5668          if (TEST_OPT_INTSTRATEGY)
     5669          {
     5670            //pContent(h.p);
     5671            h.pCleardenom(); // also does a pContent
     5672          }
     5673          else
     5674          {
     5675            h.pNorm();
     5676          }
     5677          strat->initEcart(&h);
     5678          if (strat->Ll==-1)
     5679            pos =0;
     5680          else
     5681            pos = strat->posInLSba(strat->L,strat->Ll,&h,strat);
     5682          h.sev = pGetShortExpVector(h.p);
     5683          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
     5684        }
     5685      }
     5686      /*
     5687      if (!strat->incremental)
     5688      {
     5689        for(j=0;j<i;j++)
     5690        {
     5691          strat->syz[ctr] = pCopy(F->m[j]);
     5692          p_SetCompP(strat->syz[ctr],i+1,currRing);
     5693          // add LM(F->m[i]) to the signature to get a Schreyer order
     5694          // without changing the underlying polynomial ring at all
     5695          p_ExpVectorAdd (strat->syz[ctr],F->m[i],currRing); 
     5696          // since p_Add_q() destroys all input
     5697          // data we need to recreate help
     5698          // each time
     5699          poly help = pCopy(F->m[i]);
     5700          p_SetCompP(help,j+1,currRing);
     5701          pWrite(strat->syz[ctr]);
     5702          pWrite(help);
     5703          printf("%d\n",pLmCmp(strat->syz[ctr],help));
     5704          strat->syz[ctr] = p_Add_q(strat->syz[ctr],help,currRing);
     5705          printf("%d. SYZ  ",ctr);
     5706          pWrite(strat->syz[ctr]);
     5707          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
     5708          ctr++;
     5709        }
     5710        strat->syzl = ps;
     5711      }
     5712      */
     5713    }
     5714  }
     5715  /*- test, if a unit is in F -*/
     5716
     5717  if ((strat->Ll>=0)
     5718#ifdef HAVE_RINGS
     5719       && nIsUnit(pGetCoeff(strat->L[strat->Ll].p))
     5720#endif
     5721       && pIsConstant(strat->L[strat->Ll].p))
     5722  {
     5723    while (strat->Ll>0) deleteInL(strat->L,&strat->Ll,strat->Ll-1,strat);
     5724  }
     5725}
     5726
     5727void initSyzRules (kStrategy strat)
     5728{
     5729  if( strat->S[0] )
     5730  {
     5731    if( strat->S[1] )
     5732    {
     5733      omFreeSize(strat->syzIdx,(strat->syzidxmax)*sizeof(int));
     5734      omFreeSize(strat->sevSyz,(strat->syzmax)*sizeof(unsigned long));
     5735      omFreeSize(strat->syz,(strat->syzmax)*sizeof(poly));
     5736    }
     5737    int i, j, k, diff, comp, comp_old, ps=0, ctr=0;
     5738    /************************************************************
     5739     * computing the length of the syzygy array needed
     5740     ***********************************************************/
     5741    for(i=1; i<=strat->sl; i++)
     5742    {
     5743      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
     5744      {
     5745        ps += i;
     5746      }
     5747    }
     5748    ps += strat->sl+1;
     5749    //comp              = pGetComp (strat->P.sig);
     5750    comp              = strat->currIdx;
     5751    strat->syzIdx     = initec(comp);
     5752    strat->sevSyz     = initsevS(ps);
     5753    strat->syz        = (poly *)omAlloc(ps*sizeof(poly));
     5754    strat->syzl       = strat->syzmax = ps;
     5755    strat->syzidxmax  = comp;
     5756#ifdef DEBUGF5 || DEBUGF51
     5757    printf("------------- GENERATING SYZ RULES NEW ---------------\n");
     5758#endif
     5759    i = 1;
     5760    j = 0;
     5761    /************************************************************
     5762     * generating the leading terms of the principal syzygies
     5763     ***********************************************************/
     5764    while (i <= strat->sl)
     5765    {
     5766      /**********************************************************
     5767       * principal syzygies start with component index 2
     5768       * the array syzIdx starts with index 0
     5769       * => the rules for a signature with component comp start
     5770       *    at strat->syz[strat->syzIdx[comp-2]] !
     5771       *********************************************************/
     5772      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
     5773      {
     5774        comp      = pGetComp(strat->sig[i]);
     5775        comp_old  = pGetComp(strat->sig[i-1]);
     5776        diff      = comp - comp_old - 1;
     5777        // diff should be zero, but sometimes also the initial generating
     5778        // elements of the input ideal reduce to zero. then there is an
     5779        // index-gap between the signatures. for these inbetween signatures we
     5780        // can safely set syzIdx[j] = 0 as no such element will be ever computed
     5781        // in the following.
     5782        // doing this, we keep the relation "j = comp - 2" alive, which makes
     5783        // jumps way easier when checking criteria
     5784        while (diff>0)
     5785        {
     5786          strat->syzIdx[j]  = 0;
     5787          diff--;
     5788          j++;
     5789        }
     5790        strat->syzIdx[j]  = ctr;
     5791        j++;
     5792        for (k = 0; k<i; k++)
     5793        {
     5794          poly p          = pOne();
     5795          pLcm(strat->S[k],strat->S[i],p);
     5796          strat->syz[ctr] = p;
     5797          p_SetCompP (strat->syz[ctr], comp, currRing);
     5798          poly q          = p_Copy(p, currRing);
     5799          q               = p_Neg (q, currRing);
     5800          p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
     5801          strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
     5802#ifdef DEBUGF5 || DEBUGF51
     5803          pWrite(strat->syz[ctr]);
     5804#endif
     5805          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
     5806          ctr++;
     5807        }
     5808      }
     5809      i++;
     5810    }
     5811    /**************************************************************
     5812    * add syzygies for upcoming first element of new iteration step
     5813    **************************************************************/
     5814    comp      = strat->currIdx;
     5815    comp_old  = pGetComp(strat->sig[i-1]);
     5816    diff      = comp - comp_old - 1;
     5817    // diff should be zero, but sometimes also the initial generating
     5818    // elements of the input ideal reduce to zero. then there is an
     5819    // index-gap between the signatures. for these inbetween signatures we
     5820    // can safely set syzIdx[j] = 0 as no such element will be ever computed
     5821    // in the following.
     5822    // doing this, we keep the relation "j = comp - 2" alive, which makes
     5823    // jumps way easier when checking criteria
     5824    while (diff>0)
     5825    {
     5826      strat->syzIdx[j]  = 0;
     5827      diff--;
     5828      j++;
     5829    }
     5830    strat->syzIdx[j]  = ctr;
     5831    for (k = 0; k<strat->sl+1; k++)
     5832    {
     5833      strat->syz[ctr] = p_Copy (pHead(strat->S[k]), currRing);
     5834      p_SetCompP (strat->syz[ctr], comp, currRing);
     5835      poly q          = p_Copy (pHead(strat->L[strat->Ll].p), currRing);
     5836      q               = p_Neg (q, currRing);
     5837      p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
     5838      strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
     5839//#if 1
     5840#if DEBUGF5 || DEBUGF51
     5841      printf("..");
     5842      pWrite(strat->syz[ctr]);
     5843#endif
     5844      strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
     5845      ctr++;
     5846    }
     5847//#if 1
     5848#ifdef DEBUGF5
     5849    Print("Principal syzygies:\n");
     5850    Print("--------------------------------\n");
     5851    for(i=0;i<=ps-1;i++)
     5852    {
     5853      pWrite(strat->syz[i]);
     5854    }
     5855    Print("--------------------------------\n");
     5856#endif
     5857
     5858  }
     5859}
     5860
    50205861
    50215862
     
    56656506
    56666507/*2
     6508* -puts p to the standardbasis s at position at
     6509* -saves the result in S
     6510*/
     6511void enterSSba (LObject p,int atS,kStrategy strat, int atR)
     6512{
     6513  int i;
     6514  strat->news = TRUE;
     6515  /*- puts p to the standardbasis s at position at -*/
     6516  if (strat->sl == IDELEMS(strat->Shdl)-1)
     6517  {
     6518    strat->sevS = (unsigned long*) omRealloc0Size(strat->sevS,
     6519                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
     6520                                    (IDELEMS(strat->Shdl)+setmaxTinc)
     6521                                                  *sizeof(unsigned long));
     6522    strat->sevSig = (unsigned long*) omRealloc0Size(strat->sevSig,
     6523                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
     6524                                    (IDELEMS(strat->Shdl)+setmaxTinc)
     6525                                                  *sizeof(unsigned long));
     6526    strat->ecartS = (intset)omReallocSize(strat->ecartS,
     6527                                          IDELEMS(strat->Shdl)*sizeof(int),
     6528                                          (IDELEMS(strat->Shdl)+setmaxTinc)
     6529                                                  *sizeof(int));
     6530    strat->fromS = (intset)omReallocSize(strat->fromS,
     6531                                          IDELEMS(strat->Shdl)*sizeof(int),
     6532                                          (IDELEMS(strat->Shdl)+setmaxTinc)
     6533                                                  *sizeof(int));
     6534    strat->S_2_R = (int*) omRealloc0Size(strat->S_2_R,
     6535                                         IDELEMS(strat->Shdl)*sizeof(int),
     6536                                         (IDELEMS(strat->Shdl)+setmaxTinc)
     6537                                                  *sizeof(int));
     6538    if (strat->lenS!=NULL)
     6539      strat->lenS=(int*)omRealloc0Size(strat->lenS,
     6540                                       IDELEMS(strat->Shdl)*sizeof(int),
     6541                                       (IDELEMS(strat->Shdl)+setmaxTinc)
     6542                                                 *sizeof(int));
     6543    if (strat->lenSw!=NULL)
     6544      strat->lenSw=(wlen_type*)omRealloc0Size(strat->lenSw,
     6545                                       IDELEMS(strat->Shdl)*sizeof(wlen_type),
     6546                                       (IDELEMS(strat->Shdl)+setmaxTinc)
     6547                                                 *sizeof(wlen_type));
     6548    if (strat->fromQ!=NULL)
     6549    {
     6550      strat->fromQ = (intset)omReallocSize(strat->fromQ,
     6551                                    IDELEMS(strat->Shdl)*sizeof(int),
     6552                                    (IDELEMS(strat->Shdl)+setmaxTinc)*sizeof(int));
     6553    }
     6554    pEnlargeSet(&strat->S,IDELEMS(strat->Shdl),setmaxTinc);
     6555    pEnlargeSet(&strat->sig,IDELEMS(strat->Shdl),setmaxTinc);
     6556    IDELEMS(strat->Shdl)+=setmaxTinc;
     6557    strat->Shdl->m=strat->S;
     6558  }
     6559  // in a signature-based algorithm the following situation will never
     6560  // appear due to the fact that the critical pairs are already sorted
     6561  // by increasing signature.
     6562  if (atS <= strat->sl)
     6563  {
     6564#ifdef ENTER_USE_MEMMOVE
     6565// #if 0
     6566    memmove(&(strat->S[atS+1]), &(strat->S[atS]),
     6567            (strat->sl - atS + 1)*sizeof(poly));
     6568    memmove(&(strat->ecartS[atS+1]), &(strat->ecartS[atS]),
     6569            (strat->sl - atS + 1)*sizeof(int));
     6570    memmove(&(strat->fromS[atS+1]), &(strat->fromS[atS]),
     6571            (strat->sl - atS + 1)*sizeof(int));
     6572    memmove(&(strat->sevS[atS+1]), &(strat->sevS[atS]),
     6573            (strat->sl - atS + 1)*sizeof(unsigned long));
     6574    memmove(&(strat->S_2_R[atS+1]), &(strat->S_2_R[atS]),
     6575            (strat->sl - atS + 1)*sizeof(int));
     6576    if (strat->lenS!=NULL)
     6577    memmove(&(strat->lenS[atS+1]), &(strat->lenS[atS]),
     6578            (strat->sl - atS + 1)*sizeof(int));
     6579    if (strat->lenSw!=NULL)
     6580    memmove(&(strat->lenSw[atS+1]), &(strat->lenSw[atS]),
     6581            (strat->sl - atS + 1)*sizeof(wlen_type));
     6582#else
     6583    for (i=strat->sl+1; i>=atS+1; i--)
     6584    {
     6585      strat->S[i] = strat->S[i-1];
     6586      strat->ecartS[i] = strat->ecartS[i-1];
     6587      strat->fromS[i] = strat->fromS[i-1];
     6588      strat->sevS[i] = strat->sevS[i-1];
     6589      strat->S_2_R[i] = strat->S_2_R[i-1];
     6590    }
     6591    if (strat->lenS!=NULL)
     6592    for (i=strat->sl+1; i>=atS+1; i--)
     6593      strat->lenS[i] = strat->lenS[i-1];
     6594    if (strat->lenSw!=NULL)
     6595    for (i=strat->sl+1; i>=atS+1; i--)
     6596      strat->lenSw[i] = strat->lenSw[i-1];
     6597#endif
     6598  }
     6599  if (strat->fromQ!=NULL)
     6600  {
     6601#ifdef ENTER_USE_MEMMOVE
     6602    memmove(&(strat->fromQ[atS+1]), &(strat->fromQ[atS]),
     6603                  (strat->sl - atS + 1)*sizeof(int));
     6604#else
     6605    for (i=strat->sl+1; i>=atS+1; i--)
     6606    {
     6607      strat->fromQ[i] = strat->fromQ[i-1];
     6608    }
     6609#endif
     6610    strat->fromQ[atS]=0;
     6611  }
     6612
     6613  /*- save result -*/
     6614  strat->S[atS] = p.p;
     6615  strat->sig[atS] = p.sig; // TODO: get ths correct signature in here!
     6616  if (strat->honey) strat->ecartS[atS] = p.ecart;
     6617  if (p.sev == 0)
     6618    p.sev = pGetShortExpVector(p.p);
     6619  else
     6620    assume(p.sev == pGetShortExpVector(p.p));
     6621  strat->sevS[atS] = p.sev;
     6622  // during the interreduction process of a signature-based algorithm we do not
     6623  // compute the signature at this point, but when the whole interreduction
     6624  // process finishes, i.e. f5c terminates!
     6625  if (p.sig != NULL)
     6626  {
     6627    if (p.sevSig == 0)
     6628      p.sevSig = pGetShortExpVector(p.sig);
     6629    else
     6630      assume(p.sevSig == pGetShortExpVector(p.sig));
     6631    strat->sevSig[atS] = p.sevSig; // TODO: get the correct signature in here!
     6632  }
     6633  strat->ecartS[atS] = p.ecart;
     6634  strat->fromS[atS] = p.from;
     6635  strat->S_2_R[atS] = atR;
     6636  strat->sl++;
     6637#ifdef DEBUGF5
     6638  int k;
     6639  Print("--- LIST S: %d ---\n",strat->sl);
     6640  for(k=0;k<=strat->sl;k++)
     6641  {
     6642    pWrite(strat->sig[k]);
     6643  }
     6644  Print("--- LIST S END ---\n");
     6645#endif
     6646}
     6647
     6648/*2
    56676649* puts p to the set T at position atT
    56686650*/
     
    57356717  kTest_T(&(strat->T[atT]));
    57366718}
     6719
     6720/*2
     6721* puts signature p.sig to the set syz
     6722*/
     6723void enterSyz(LObject p, kStrategy strat)
     6724{
     6725  int i = strat->syzl;
     6726
     6727  strat->newt = TRUE;
     6728  if (strat->syzl == strat->syzmax)
     6729  {
     6730    pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
     6731    strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
     6732                                    (strat->syzmax)*sizeof(unsigned long),
     6733                                    ((strat->syzmax)+setmaxTinc)
     6734                                                  *sizeof(unsigned long));
     6735    strat->syzmax += setmaxTinc;
     6736  }
     6737  strat->syz[i] = p.sig;
     6738  strat->sevSyz[i] = p.sevSig;
     6739  strat->syzl++;
     6740#ifdef DEBUGF5
     6741  Print("last element in strat->syz: %d--%d  ",i+1,strat->syzmax);
     6742  pWrite(strat->syz[i]);
     6743#endif
     6744  // recheck pairs in strat->L with new rule and delete correspondingly
     6745  int cc = strat->Ll;
     6746  while (cc>-1)
     6747  {
     6748    if (p_LmShortDivisibleBy( strat->syz[strat->syzl-1], strat->sevSyz[strat->syzl-1],
     6749                              strat->L[cc].sig, ~strat->L[cc].sevSig, currRing))
     6750    {
     6751      deleteInL(strat->L,&strat->Ll,cc,strat);
     6752    }
     6753    cc--;
     6754  }
     6755
     6756}
     6757
    57376758
    57386759void initHilbCrit(ideal/*F*/, ideal /*Q*/, intvec **hilb,kStrategy strat)
     
    57716792  * - in local rings, - in lex order case, -in ring over extensions */
    57726793  strat->noTailReduction = !TEST_OPT_REDTAIL;
     6794
     6795#ifdef HAVE_PLURAL
     6796  // and r is plural_ring
     6797  //  hence this holds for r a rational_plural_ring
     6798  if( rIsPluralRing(currRing) || (rIsSCA(currRing) && !strat->z2homog) )
     6799  {    //or it has non-quasi-comm type... later
     6800    strat->sugarCrit = FALSE;
     6801    strat->Gebauer = FALSE;
     6802    strat->honey = FALSE;
     6803  }
     6804#endif
     6805
     6806#ifdef HAVE_RINGS
     6807  // Coefficient ring?
     6808  if (rField_is_Ring(currRing))
     6809  {
     6810    strat->sugarCrit = FALSE;
     6811    strat->Gebauer = FALSE ;
     6812    strat->honey = FALSE;
     6813  }
     6814#endif
     6815  #ifdef KDEBUG
     6816  if (TEST_OPT_DEBUG)
     6817  {
     6818    if (strat->homog) PrintS("ideal/module is homogeneous\n");
     6819    else              PrintS("ideal/module is not homogeneous\n");
     6820  }
     6821  #endif
     6822}
     6823
     6824void initSbaCrit(kStrategy strat)
     6825{
     6826  //strat->enterOnePair=enterOnePairNormal;
     6827  strat->enterOnePair = enterOnePairNormal;
     6828  //strat->chainCrit=chainCritNormal;
     6829  strat->chainCrit    = chainCritSig;
     6830  /******************************************
     6831   * rewCrit1 and rewCrit2 are already set in
     6832   * kSba() in kstd1.cc
     6833   *****************************************/
     6834  //strat->rewCrit1     = faugereRewCriterion;
     6835  if (strat->incremental)
     6836  {
     6837    strat->syzCrit  = syzCriterionInc;
     6838  }
     6839  else
     6840  {
     6841    strat->syzCrit  = syzCriterion;
     6842  }
     6843#ifdef HAVE_RINGS
     6844  if (rField_is_Ring(currRing))
     6845  {
     6846    strat->enterOnePair=enterOnePairRing;
     6847    strat->chainCrit=chainCritRing;
     6848  }
     6849#endif
     6850#ifdef HAVE_RATGRING
     6851  if (rIsRatGRing(currRing))
     6852  {
     6853     strat->chainCrit=chainCritPart;
     6854     /* enterOnePairNormal get rational part in it */
     6855  }
     6856#endif
     6857
     6858  strat->sugarCrit =        TEST_OPT_SUGARCRIT;
     6859  strat->Gebauer =          strat->homog || strat->sugarCrit;
     6860  strat->honey =            !strat->homog || strat->sugarCrit || TEST_OPT_WEIGHTM;
     6861  if (TEST_OPT_NOT_SUGAR) strat->honey = FALSE;
     6862  strat->pairtest = NULL;
     6863  /* alway use tailreduction, except:
     6864  * - in local rings, - in lex order case, -in ring over extensions */
     6865  strat->noTailReduction = !TEST_OPT_REDTAIL;
     6866  //strat->noTailReduction = NULL;
    57736867
    57746868#ifdef HAVE_PLURAL
  • kernel/kutil.h

    rcffd3e r83be980  
    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);
     620ideal ssg (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
     621ideal ssgincschreyer (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
     622ideal ssgnoninc (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    543623poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
    544624ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
    545625void initBba(ideal F,kStrategy strat);
     626void initSba(ideal F,kStrategy strat);
     627void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
     628          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
     629          intvec *w,intvec *hilb );
    546630
    547631/***************************************************************
     
    569653                 kStrategy strat = NULL);
    570654
     655// Reduces PR with PW
     656// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
     657// Changes: PR
     658// Const:   PW
     659// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
     660// If strat != NULL, tailRing is changed if reduction would violate exp bound
     661// of tailRing
     662// Returns: 0 everything ok, no tailRing change
     663//          1 tailRing has successfully changed (strat != NULL)
     664//          2 no reduction performed, tailRing needs to be changed first
     665//            (strat == NULL)
     666//          3 no reduction performed, not sig-safe!!!
     667//         -1 tailRing change could not be performed due to exceeding exp
     668//            bound of currRing
     669int ksReducePolySig(LObject* PR,
     670                 TObject* PW,
     671                 long idx,
     672                 poly spNoether = NULL,
     673                 number *coef = NULL,
     674                 kStrategy strat = NULL);
     675
    571676// Reduces PR at Current->next with PW
    572677// Assumes PR != NULL, Current contained in PR
     
    638743void kDebugPrint(kStrategy strat);
    639744
     745// getting sb order for sba computations
     746ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
    640747
    641748KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
Note: See TracChangeset for help on using the changeset viewer.