kstd1.h File Reference

#include "kernel/structs.h"
#include "polys/monomials/ring.h"

Go to the source code of this file.

Macros
#define	KSTD_NF_LAZY   1
#define	KSTD_NF_ECART   2
#define	KSTD_NF_NONORM   4

Typedefs
typedef BOOLEAN(*	s_poly_proc_t) (kStrategy strat)

Functions
ideal	mora (ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
poly	kNF1 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
ideal	kNF1 (ideal F, ideal Q, ideal q, kStrategy strat, int lazyReduce)
poly	kNF (ideal F, ideal Q, poly p, int syzComp=0, int lazyReduce=0)
ideal	kNF (ideal F, ideal Q, ideal p, int syzComp=0, int lazyReduce=0)
poly	kNFBound (ideal F, ideal Q, poly p, int bound, int syzComp=0, int lazyReduce=0)
ideal	kNFBound (ideal F, ideal Q, ideal p, int bound, int syzComp=0, int lazyReduce=0)
poly	k_NF (ideal F, ideal Q, poly p, int syzComp, int lazyReduce, const ring _currRing)
	NOTE: this is just a wrapper which sets currRing for the actual kNF call. More...
ideal	kSba (ideal F, ideal Q, tHomog h, intvec **mw, int incremental=0, int arri=0, intvec *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL)
ideal	kStd (ideal F, ideal Q, tHomog h, intvec **mw, intvec *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL)
ideal	kStdShift (ideal F, ideal Q, tHomog h, intvec **mw, intvec *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE)
ideal	rightgb (ideal F, ideal Q)
void	initMora (ideal F, kStrategy strat)
ideal	kInterRed (ideal F, ideal Q=NULL)
ideal	kInterRedOld (ideal F, ideal Q=NULL)
long	kModDeg (poly p, ring r=currRing)
long	kHomModDeg (poly p, ring r=currRing)
ideal	stdred (ideal F, ideal Q, tHomog h, intvec **w)
ideal	kMin_std (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb=NULL, int syzComp=0, int reduced=0)
BOOLEAN	kVerify (ideal F, ideal Q)

Variables
EXTERN_VAR int	Kstd1_mu
EXTERN_VAR int	Kstd1_deg
EXTERN_VAR BITSET	kOptions
EXTERN_VAR BITSET	validOpts
EXTERN_VAR intvec *	kModW
EXTERN_VAR intvec *	kHomW

Macro Definition Documentation

KSTD_NF_ECART

#define KSTD_NF_ECART   2

Definition at line 19 of file kstd1.h.

KSTD_NF_LAZY

#define KSTD_NF_LAZY   1

Definition at line 17 of file kstd1.h.

KSTD_NF_NONORM

#define KSTD_NF_NONORM   4

Definition at line 21 of file kstd1.h.

Typedef Documentation

s_poly_proc_t

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)

Definition at line 14 of file kstd1.h.

Function Documentation

initMora()

void initMora	(	ideal	F,
		kStrategy	strat
	)

!

Definition at line 1804 of file kstd1.cc.

{
  int i,j;
 
  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
  strat->enterS = enterSMora;
  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
  strat->posInLOld = strat->posInL;
  strat->posInLOldFlag = TRUE;
  strat->initEcart = initEcartNormal;
  strat->kAllAxis = (currRing->ppNoether) != NULL; //!!
  if ( currRing->ppNoether != NULL )
  {
    strat->kNoether = pCopy((currRing->ppNoether));
    strat->red = redFirst;  /*take the first possible in T*/
    if (TEST_OPT_PROT)
    {
      Print("H(%ld)",p_FDeg(currRing->ppNoether,currRing)+1);
      mflush();
    }
  }
  else if (strat->homog)
    strat->red = redFirst;  /*take the first possible in T*/
  else
    strat->red = redEcart;/*take the first possible in under ecart-restriction*/
  if (currRing->ppNoether != NULL)
  {
    HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
  }
  else
  {
    HCord = 32000;/*- very large -*/
  }
 
  if (rField_is_Ring(currRing)) {
    if (rField_is_Z(currRing))
      strat->red = redRiloc_Z;
    else
      strat->red = redRiloc;
  }
 
  /*reads the ecartWeights used for Graebes method from the
   *intvec ecart and set ecartWeights
   */
  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
  {
    //interred  machen   Aenderung
    strat->pOrigFDeg=currRing->pFDeg;
    strat->pOrigLDeg=currRing->pLDeg;
    ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
    /*uses automatic computation of the ecartWeights to set them*/
    kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights,currRing);
 
    pSetDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
    if (TEST_OPT_PROT)
    {
      for(i=1; i<=(currRing->N); i++)
        Print(" %d",ecartWeights[i]);
      PrintLn();
      mflush();
    }
  }
  kOptimizeLDeg(currRing->pLDeg, strat);
}

k_NF()

poly k_NF	(	ideal	F,
		ideal	Q,
		poly	p,
		int	syzComp,
		int	lazyReduce,
		const ring	_currRing
	)

NOTE: this is just a wrapper which sets currRing for the actual kNF call.

Definition at line 3378 of file kstd1.cc.

{
  const ring save = currRing;
  if( currRing != _currRing ) rChangeCurrRing(_currRing);
  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
  if( currRing != save )     rChangeCurrRing(save);
  return ret;
}

kHomModDeg()

long kHomModDeg	(	poly	p,
		ring	r = currRing
	)

Definition at line 2420 of file kstd1.cc.

{
  int i;
  long j=0;
 
  for (i=r->N;i>0;i--)
    j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
  if (kModW == NULL) return j;
  i = __p_GetComp(p,r);
  if (i==0) return j;
  return j+(*kModW)[i-1];
}

kInterRed()

ideal kInterRed	(	ideal	F,
		ideal	Q = NULL
	)

Definition at line 3743 of file kstd1.cc.

{
#ifdef HAVE_PLURAL
  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
#endif
  if ((rHasLocalOrMixedOrdering(currRing))|| (rField_is_numeric(currRing))
  ||(rField_is_Ring(currRing))
  )
    return kInterRedOld(F,Q);
 
    //return kInterRedOld(F,Q);
 
  BITSET save1;
  SI_SAVE_OPT1(save1);
  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
  si_opt_1|=Sy_bit(OPT_REDTHROUGH);
  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
  //si_opt_1&= ~Sy_bit(OPT_REDSB);
  //extern char * showOption() ;
  //Print("%s\n",showOption());
 
  int need_retry;
  int counter=3;
  ideal res, res1;
  int elems;
  ideal null=NULL;
  if ((Q==NULL) || (!TEST_OPT_REDSB))
  {
    elems=idElem(F);
    res=kInterRedBba(F,Q,need_retry);
  }
  else
  {
    ideal FF=idSimpleAdd(F,Q);
    res=kInterRedBba(FF,NULL,need_retry);
    idDelete(&FF);
    null=idInit(1,1);
    if (need_retry)
      res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
    else
      res1=kNF(null,Q,res);
    idDelete(&res);
    res=res1;
    need_retry=1;
  }
  if (idElem(res)<=1) need_retry=0;
  while (need_retry && (counter>0))
  {
    #ifdef KDEBUG
    if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
    #endif
    res1=kInterRedBba(res,Q,need_retry);
    int new_elems=idElem(res1);
    counter -= (new_elems >= elems);
    elems = new_elems;
    idDelete(&res);
    if (idElem(res1)<=1) need_retry=0;
    if ((Q!=NULL) && (TEST_OPT_REDSB))
    {
      if (need_retry)
        res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
      else
        res=kNF(null,Q,res1);
      idDelete(&res1);
    }
    else
      res = res1;
    if (idElem(res)<=1) need_retry=0;
  }
  if (null!=NULL) idDelete(&null);
  SI_RESTORE_OPT1(save1);
  idSkipZeroes(res);
  return res;
}

kInterRedOld()

ideal kInterRedOld	(	ideal	F,
		ideal	Q = NULL
	)

Definition at line 3391 of file kstd1.cc.

{
  int j;
  kStrategy strat = new skStrategy;
 
  ideal tempF = F;
  ideal tempQ = Q;
 
#ifdef HAVE_PLURAL
  if(rIsSCA(currRing))
  {
    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
    tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
 
    // this should be done on the upper level!!! :
    //    tempQ = SCAQuotient(currRing);
 
    if(Q == currRing->qideal)
      tempQ = SCAQuotient(currRing);
  }
#endif
 
//  if (TEST_OPT_PROT)
//  {
//    writeTime("start InterRed:");
//    mflush();
//  }
  //strat->syzComp     = 0;
  strat->kAllAxis = (currRing->ppNoether) != NULL;
  strat->kNoether=pCopy((currRing->ppNoether));
  strat->ak = id_RankFreeModule(tempF,currRing);
  initBuchMoraCrit(strat);
  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
  strat->enterS      = enterSBba;
  strat->posInT      = posInT17;
  strat->initEcart   = initEcartNormal;
  strat->sl   = -1;
  strat->tl          = -1;
  strat->tmax        = setmaxT;
  strat->T           = initT();
  strat->R           = initR();
  strat->sevT        = initsevT();
  if (rHasLocalOrMixedOrdering(currRing))   strat->honey = TRUE;
  initS(tempF, tempQ, strat);
  if (TEST_OPT_REDSB)
    strat->noTailReduction=FALSE;
  updateS(TRUE,strat);
  if (TEST_OPT_REDSB && TEST_OPT_INTSTRATEGY)
    completeReduce(strat);
  //else if (TEST_OPT_PROT) PrintLn();
  cleanT(strat);
  if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
  omfree(strat->sevT);
  omfree(strat->S_2_R);
  omfree(strat->R);
 
  if (strat->fromQ)
  {
    for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
    {
      if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
    }
    omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
  }
//  if (TEST_OPT_PROT)
//  {
//    writeTime("end Interred:");
//    mflush();
//  }
  ideal shdl=strat->Shdl;
  idSkipZeroes(shdl);
  if (strat->fromQ)
  {
    strat->fromQ=NULL;
    ideal res=kInterRed(shdl,NULL);
    idDelete(&shdl);
    shdl=res;
  }
  delete(strat);
#ifdef HAVE_PLURAL
  if( tempF != F )
    id_Delete( &tempF, currRing);
#endif
  return shdl;
}

kMin_std()

ideal kMin_std	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	w,
		ideal &	M,
		intvec *	hilb = NULL,
		int	syzComp = 0,
		int	reduced = 0
	)

Definition at line 3019 of file kstd1.cc.

{
  if(idIs0(F))
  {
    M=idInit(1,F->rank);
    return idInit(1,F->rank);
  }
  if(rField_is_Ring(currRing))
  {
    ideal sb;
    sb = kStd(F, Q, h, w, hilb);
    idSkipZeroes(sb);
    if(IDELEMS(sb) <= IDELEMS(F))
    {
        M = idCopy(sb);
        idSkipZeroes(M);
        return(sb);
    }
    else
    {
        M = idCopy(F);
        idSkipZeroes(M);
        return(sb);
    }
  }
  ideal r=NULL;
  int Kstd1_OldDeg = Kstd1_deg,i;
  intvec* temp_w=NULL;
  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
  BOOLEAN delete_w=(w==NULL);
  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
  kStrategy strat=new skStrategy;
 
  if(!TEST_OPT_RETURN_SB)
     strat->syzComp = syzComp;
  if (rField_has_simple_inverse(currRing))
    strat->LazyPass=20;
  else
    strat->LazyPass=2;
  strat->LazyDegree = 1;
  strat->minim=(reduced % 2)+1;
  strat->ak = id_RankFreeModule(F,currRing);
  if (delete_w)
  {
    temp_w=new intvec((strat->ak)+1);
    w = &temp_w;
  }
  if (h==testHomog)
  {
    if (strat->ak == 0)
    {
      h = (tHomog)idHomIdeal(F,Q);
      w=NULL;
    }
    else
    {
      h = (tHomog)idHomModule(F,Q,w);
    }
  }
  if (h==isHomog)
  {
    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
    {
      kModW = *w;
      strat->kModW = *w;
      assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
      strat->pOrigFDeg = currRing->pFDeg;
      strat->pOrigLDeg = currRing->pLDeg;
      pSetDegProcs(currRing,kModDeg);
 
      toReset = TRUE;
      if (reduced>1)
      {
        Kstd1_OldDeg=Kstd1_deg;
        Kstd1_deg = -1;
        for (i=IDELEMS(F)-1;i>=0;i--)
        {
          if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
            Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
        }
      }
    }
    currRing->pLexOrder = TRUE;
    strat->LazyPass*=2;
  }
  strat->homog=h;
  if (rHasLocalOrMixedOrdering(currRing))
  {
    if (w!=NULL)
      r=mora(F,Q,*w,hilb,strat);
    else
      r=mora(F,Q,NULL,hilb,strat);
  }
  else
  {
    if (w!=NULL)
      r=bba(F,Q,*w,hilb,strat);
    else
      r=bba(F,Q,NULL,hilb,strat);
  }
#ifdef KDEBUG
  {
    int i;
    for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
  }
#endif
  idSkipZeroes(r);
  if (toReset)
  {
    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
    kModW = NULL;
  }
  currRing->pLexOrder = b;
  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
  {
    M=idInit(1,F->rank);
    M->m[0]=pOne();
    //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
    if (strat->M!=NULL) idDelete(&strat->M);
  }
  else if (strat->M==NULL)
  {
    M=idInit(1,F->rank);
    WarnS("no minimal generating set computed");
  }
  else
  {
    idSkipZeroes(strat->M);
    M=strat->M;
  }
  delete(strat);
  if (reduced>2)
  {
    Kstd1_deg=Kstd1_OldDeg;
    if (!oldDegBound)
      si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
  }
  else
  {
    if (IDELEMS(M)>IDELEMS(r)) {
       idDelete(&M);
       M=idCopy(r); }
  }
  return r;
}

kModDeg()

long kModDeg	(	poly	p,
		ring	r = currRing
	)

Definition at line 2410 of file kstd1.cc.

{
  long o=p_WDegree(p, r);
  long i=__p_GetComp(p, r);
  if (i==0) return o;
  //assume((i>0) && (i<=kModW->length()));
  if (i<=kModW->length())
    return o+(*kModW)[i-1];
  return o;
}

kNF() [1/2]

ideal kNF	(	ideal	F,
		ideal	Q,
		ideal	p,
		int	syzComp = 0,
		int	lazyReduce = 0
	)

Definition at line 3264 of file kstd1.cc.

{
  ideal res;
  if (TEST_OPT_PROT)
  {
    Print("(S:%d)",IDELEMS(p));mflush();
  }
  if (idIs0(p))
    return idInit(IDELEMS(p),si_max(p->rank,F->rank));
 
  ideal pp = p;
#ifdef HAVE_PLURAL
  if(rIsSCA(currRing))
  {
    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
    pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
 
    if(Q == currRing->qideal)
      Q = SCAQuotient(currRing);
  }
#endif
 
  if ((idIs0(F))&&(Q==NULL))
  {
#ifdef HAVE_PLURAL
    if(p != pp)
      return pp;
#endif
    return idCopy(p); /*F+Q=0*/
  }
 
  kStrategy strat=new skStrategy;
  strat->syzComp = syzComp;
  strat->ak = si_max(id_RankFreeModule(F,currRing),id_RankFreeModule(p,currRing));
  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
  {
    strat->ak = si_max(strat->ak,(int)F->rank);
  }
 
  if (rHasLocalOrMixedOrdering(currRing))
  {
#ifdef HAVE_SHIFTBBA
    if (currRing->isLPring)
    {
      WerrorS("No local ordering possible for shift algebra");
      return(NULL);
    }
#endif
    res=kNF1(F,Q,pp,strat,lazyReduce);
  }
  else
    res=kNF2(F,Q,pp,strat,lazyReduce);
  delete(strat);
 
#ifdef HAVE_PLURAL
  if(pp != p)
    id_Delete(&pp, currRing);
#endif
 
  return res;
}

kNF() [2/2]

poly kNF	(	ideal	F,
		ideal	Q,
		poly	p,
		int	syzComp = 0,
		int	lazyReduce = 0
	)

Definition at line 3167 of file kstd1.cc.

{
  if (p==NULL)
     return NULL;
 
  poly pp = p;
 
#ifdef HAVE_PLURAL
  if(rIsSCA(currRing))
  {
    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
    pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
 
    if(Q == currRing->qideal)
      Q = SCAQuotient(currRing);
  }
#endif
 
  if ((idIs0(F))&&(Q==NULL))
  {
#ifdef HAVE_PLURAL
    if(p != pp)
      return pp;
#endif
    return pCopy(p); /*F+Q=0*/
  }
 
  kStrategy strat=new skStrategy;
  strat->syzComp = syzComp;
  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
  poly res;
 
  if (rHasLocalOrMixedOrdering(currRing))
  {
#ifdef HAVE_SHIFTBBA
    if (currRing->isLPring)
    {
      WerrorS("No local ordering possible for shift algebra");
      return(NULL);
    }
#endif
    res=kNF1(F,Q,pp,strat,lazyReduce);
  }
  else
    res=kNF2(F,Q,pp,strat,lazyReduce);
  delete(strat);
 
#ifdef HAVE_PLURAL
  if(pp != p)
    p_Delete(&pp, currRing);
#endif
  return res;
}

kNF1() [1/2]

ideal kNF1	(	ideal	F,
		ideal	Q,
		ideal	q,
		kStrategy	strat,
		int	lazyReduce
	)

Definition at line 2255 of file kstd1.cc.

{
  assume(!idIs0(q));
  assume(!(idIs0(F)&&(Q==NULL)));
 
// lazy_reduce flags: can be combined by |
//#define KSTD_NF_LAZY   1
  // do only a reduction of the leading term
//#define KSTD_NF_ECART  2
  // only local: recude even with bad ecart
  poly   p;
  int   i;
  int   j;
  int   o;
  LObject   h;
  ideal res;
  BITSET save1;
  SI_SAVE_OPT1(save1);
 
  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
  //if ((idIs0(F))&&(Q==NULL))
  //  return idCopy(q); /*F=0*/
  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
  /*- creating temp data structures------------------- -*/
  //strat->kAllAxis = (currRing->ppNoether) != NULL;
  strat->kNoether=pCopy((currRing->ppNoether));
  si_opt_1|=Sy_bit(OPT_REDTAIL);
  if (TEST_OPT_STAIRCASEBOUND
  && (0<Kstd1_deg)
  && ((strat->kNoether==NULL)
    ||(TEST_OPT_DEGBOUND && (pWTotaldegree(strat->kNoether)<Kstd1_deg))))
  {
    pLmDelete(&strat->kNoether);
    strat->kNoether=pOne();
    pSetExp(strat->kNoether,1, Kstd1_deg+1);
    pSetm(strat->kNoether);
    //strat->kAllAxis=TRUE;
  }
  initBuchMoraCrit(strat);
  if(rField_is_Ring(currRing))
    initBuchMoraPosRing(strat);
  else
    initBuchMoraPos(strat);
  initMora(F,strat);
  strat->enterS = enterSMoraNF;
  /*- set T -*/
  strat->tl = -1;
  strat->tmax = setmaxT;
  strat->T = initT();
  strat->R = initR();
  strat->sevT = initsevT();
  /*- set S -*/
  strat->sl = -1;
  /*- init local data struct.-------------------------- -*/
  /*Shdl=*/initS(F,Q,strat);
  if ((strat->ak!=0)
  && (strat->kNoether!=NULL))
  {
    if (strat->ak!=1)
    {
      pSetComp(strat->kNoether,1);
      pSetmComp(strat->kNoether);
      poly p=pHead(strat->kNoether);
      pSetComp(p,strat->ak);
      pSetmComp(p);
      p=pAdd(strat->kNoether,p);
      strat->kNoether=pNext(p);
      p_LmDelete(p,currRing);
    }
  }
  if (((lazyReduce & KSTD_NF_LAZY)==0)
  && (!rField_is_Ring(currRing)))
  {
    for (i=strat->sl; i>=0; i--)
      pNorm(strat->S[i]);
  }
  /*- compute------------------------------------------- -*/
  res=idInit(IDELEMS(q),strat->ak);
  for (i=0; i<IDELEMS(q); i++)
  {
    if (q->m[i]!=NULL)
    {
      p = pCopy(q->m[i]);
      deleteHC(&p,&o,&j,strat);
      if (p!=NULL)
      {
        /*- puts the elements of S also to T -*/
        for (j=0; j<=strat->sl; j++)
        {
          h.p = strat->S[j];
          h.ecart = strat->ecartS[j];
          h.pLength = h.length = pLength(h.p);
          if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
          else assume(strat->sevS[j] == pGetShortExpVector(h.p));
          h.sev = strat->sevS[j];
          h.SetpFDeg();
          if(rField_is_Ring(currRing) && rHasLocalOrMixedOrdering(currRing))
            enterT_strong(h,strat);
          else
            enterT(h,strat);
        }
        if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
        if(rField_is_Ring(currRing))
        {
          p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
        }
        else
          p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
        if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
        {
          if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
          p = redtail(p,strat->sl,strat);
        }
        cleanT(strat);
      }
      res->m[i]=p;
    }
    //else
    //  res->m[i]=NULL;
  }
  /*- release temp data------------------------------- -*/
  assume(strat->L==NULL); /*strat->L unsed */
  assume(strat->B==NULL); /*strat->B unused */
  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
  omFree(strat->sevT);
  omFree(strat->S_2_R);
  omFree(strat->R);
  if ((Q!=NULL)&&(strat->fromQ!=NULL))
  {
    i=((IDELEMS(F)+IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
    omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
    strat->fromQ=NULL;
  }
  if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
//  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
//  {
//    pFDeg=strat->pOrigFDeg;
//    pLDeg=strat->pOrigLDeg;
//    if (ecartWeights)
//    {
//      omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
//      ecartWeights=NULL;
//    }
//  }
  idDelete(&strat->Shdl);
  SI_RESTORE_OPT1(save1);
  if (TEST_OPT_PROT) PrintLn();
  return res;
}

kNF1() [2/2]

poly kNF1	(	ideal	F,
		ideal	Q,
		poly	q,
		kStrategy	strat,
		int	lazyReduce
	)

Definition at line 2110 of file kstd1.cc.

{
  assume(q!=NULL);
  assume(!(idIs0(F)&&(Q==NULL)));
 
// lazy_reduce flags: can be combined by |
//#define KSTD_NF_LAZY   1
  // do only a reduction of the leading term
//#define KSTD_NF_ECART  2
  // only local: recude even with bad ecart
  poly   p;
  int   i;
  int   j;
  int   o;
  LObject   h;
  BITSET save1;
  SI_SAVE_OPT1(save1);
 
  //if ((idIs0(F))&&(Q==NULL))
  //  return pCopy(q); /*F=0*/
  //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
  /*- creating temp data structures------------------- -*/
  //strat->kAllAxis = (currRing->ppNoether) != NULL;
  strat->kNoether    = pCopy((currRing->ppNoether));
  si_opt_1|=Sy_bit(OPT_REDTAIL);
  if (!rField_is_Ring(currRing))
    si_opt_1&=~Sy_bit(OPT_INTSTRATEGY);
  if (TEST_OPT_STAIRCASEBOUND
  && (! TEST_V_DEG_STOP)
  && (0<Kstd1_deg)
  && ((strat->kNoether==NULL)
    ||(TEST_OPT_DEGBOUND && (pWTotaldegree(strat->kNoether)<Kstd1_deg))))
  {
    pLmDelete(&strat->kNoether);
    strat->kNoether=pOne();
    pSetExp(strat->kNoether,1, Kstd1_deg+1);
    pSetm(strat->kNoether);
    // strat->kAllAxis=TRUE;
  }
  initBuchMoraCrit(strat);
  if(rField_is_Ring(currRing))
    initBuchMoraPosRing(strat);
  else
    initBuchMoraPos(strat);
  initMora(F,strat);
  strat->enterS = enterSMoraNF;
  /*- set T -*/
  strat->tl = -1;
  strat->tmax = setmaxT;
  strat->T = initT();
  strat->R = initR();
  strat->sevT = initsevT();
  /*- set S -*/
  strat->sl = -1;
  /*- init local data struct.-------------------------- -*/
  /*Shdl=*/initS(F,Q,strat);
  if ((strat->ak!=0)
  && (strat->kAllAxis))
  {
    if (strat->ak!=1)
    {
      pSetComp(strat->kNoether,1);
      pSetmComp(strat->kNoether);
      poly p=pHead(strat->kNoether);
      pSetComp(p,strat->ak);
      pSetmComp(p);
      p=pAdd(strat->kNoether,p);
      strat->kNoether=pNext(p);
      p_LmDelete(p,currRing);
    }
  }
  if (((lazyReduce & KSTD_NF_LAZY)==0)
  && (!rField_is_Ring(currRing)))
  {
    for (i=strat->sl; i>=0; i--)
      pNorm(strat->S[i]);
  }
  /*- puts the elements of S also to T -*/
  for (i=0; i<=strat->sl; i++)
  {
    h.p = strat->S[i];
    h.ecart = strat->ecartS[i];
    if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
    else assume(strat->sevS[i] == pGetShortExpVector(h.p));
    h.length = pLength(h.p);
    h.sev = strat->sevS[i];
    h.SetpFDeg();
    enterT(h,strat);
  }
#ifdef KDEBUG
//  kDebugPrint(strat);
#endif
  /*- compute------------------------------------------- -*/
  p = pCopy(q);
  deleteHC(&p,&o,&j,strat);
  kTest(strat);
  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
  if (BVERBOSE(23)) kDebugPrint(strat);
  if(rField_is_Ring(currRing))
  {
    if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
  }
  else
  {
    if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
  }
  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
  {
    if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
    p = redtail(p,strat->sl,strat);
  }
  /*- release temp data------------------------------- -*/
  cleanT(strat);
  assume(strat->L==NULL); /*strat->L unsed */
  assume(strat->B==NULL); /*strat->B unused */
  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
  omFree(strat->sevT);
  omFree(strat->S_2_R);
  omFree(strat->R);
 
  if ((Q!=NULL)&&(strat->fromQ!=NULL))
  {
    i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
    omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
    strat->fromQ=NULL;
  }
  if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
//  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
//  {
//    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
//    if (ecartWeights)
//    {
//      omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
//      ecartWeights=NULL;
//    }
//  }
  idDelete(&strat->Shdl);
  SI_RESTORE_OPT1(save1);
  if (TEST_OPT_PROT) PrintLn();
  return p;
}

kNFBound() [1/2]

ideal kNFBound	(	ideal	F,
		ideal	Q,
		ideal	p,
		int	bound,
		int	syzComp = 0,
		int	lazyReduce = 0
	)

Definition at line 3327 of file kstd1.cc.

{
  ideal res;
  if (TEST_OPT_PROT)
  {
    Print("(S:%d)",IDELEMS(p));mflush();
  }
  if (idIs0(p))
    return idInit(IDELEMS(p),si_max(p->rank,F->rank));
 
  ideal pp = p;
#ifdef HAVE_PLURAL
  if(rIsSCA(currRing))
  {
    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
    pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
 
    if(Q == currRing->qideal)
      Q = SCAQuotient(currRing);
  }
#endif
 
  if ((idIs0(F))&&(Q==NULL))
  {
#ifdef HAVE_PLURAL
    if(p != pp)
      return pp;
#endif
    return idCopy(p); /*F+Q=0*/
  }
 
  kStrategy strat=new skStrategy;
  strat->syzComp = syzComp;
  strat->ak = si_max(id_RankFreeModule(F,currRing),id_RankFreeModule(p,currRing));
  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
  {
    strat->ak = si_max(strat->ak,(int)F->rank);
  }
 
  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
  delete(strat);
 
#ifdef HAVE_PLURAL
  if(pp != p)
    id_Delete(&pp, currRing);
#endif
 
  return res;
}

kNFBound() [2/2]

poly kNFBound	(	ideal	F,
		ideal	Q,
		poly	p,
		int	bound,
		int	syzComp = 0,
		int	lazyReduce = 0
	)

Definition at line 3222 of file kstd1.cc.

{
  if (p==NULL)
     return NULL;
 
  poly pp = p;
 
#ifdef HAVE_PLURAL
  if(rIsSCA(currRing))
  {
    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
    pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
 
    if(Q == currRing->qideal)
      Q = SCAQuotient(currRing);
  }
#endif
 
  if ((idIs0(F))&&(Q==NULL))
  {
#ifdef HAVE_PLURAL
    if(p != pp)
      return pp;
#endif
    return pCopy(p); /*F+Q=0*/
  }
 
  kStrategy strat=new skStrategy;
  strat->syzComp = syzComp;
  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
  poly res;
  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
  delete(strat);
 
#ifdef HAVE_PLURAL
  if(pp != p)
    p_Delete(&pp, currRing);
#endif
  return res;
}

kSba()

ideal kSba	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	mw,
		int	incremental = 0,
		int	arri = 0,
		intvec *	hilb = NULL,
		int	syzComp = 0,
		int	newIdeal = 0,
		intvec *	vw = NULL
	)

Definition at line 2617 of file kstd1.cc.

{
  if(idIs0(F))
    return idInit(1,F->rank);
  if(!rField_is_Ring(currRing))
  {
    ideal r;
    BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
    BOOLEAN delete_w=(w==NULL);
    kStrategy strat=new skStrategy;
    strat->sbaOrder = sbaOrder;
    if (arri!=0)
    {
      strat->rewCrit1 = arriRewDummy;
      strat->rewCrit2 = arriRewCriterion;
      strat->rewCrit3 = arriRewCriterionPre;
    }
    else
    {
      strat->rewCrit1 = faugereRewCriterion;
      strat->rewCrit2 = faugereRewCriterion;
      strat->rewCrit3 = faugereRewCriterion;
    }
 
    if(!TEST_OPT_RETURN_SB)
      strat->syzComp = syzComp;
    if (TEST_OPT_SB_1)
      //if(!rField_is_Ring(currRing)) // always true here
        strat->newIdeal = newIdeal;
    if (rField_has_simple_inverse(currRing))
      strat->LazyPass=20;
    else
      strat->LazyPass=2;
    strat->LazyDegree = 1;
    strat->enterOnePair=enterOnePairNormal;
    strat->chainCrit=chainCritNormal;
    if (TEST_OPT_SB_1) strat->chainCrit=chainCritOpt_1;
    strat->ak = id_RankFreeModule(F,currRing);
    strat->kModW=kModW=NULL;
    strat->kHomW=kHomW=NULL;
    if (vw != NULL)
    {
      currRing->pLexOrder=FALSE;
      strat->kHomW=kHomW=vw;
      strat->pOrigFDeg = currRing->pFDeg;
      strat->pOrigLDeg = currRing->pLDeg;
      pSetDegProcs(currRing,kHomModDeg);
      toReset = TRUE;
    }
    if (h==testHomog)
    {
      if (strat->ak == 0)
      {
        h = (tHomog)idHomIdeal(F,Q);
        w=NULL;
      }
      else if (!TEST_OPT_DEGBOUND)
      {
        if (w!=NULL)
          h = (tHomog)idHomModule(F,Q,w);
        else
          h = (tHomog)idHomIdeal(F,Q);
      }
    }
    currRing->pLexOrder=b;
    if (h==isHomog)
    {
      if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
      {
        strat->kModW = kModW = *w;
        if (vw == NULL)
        {
          strat->pOrigFDeg = currRing->pFDeg;
          strat->pOrigLDeg = currRing->pLDeg;
          pSetDegProcs(currRing,kModDeg);
          toReset = TRUE;
        }
      }
      currRing->pLexOrder = TRUE;
      if (hilb==NULL) strat->LazyPass*=2;
    }
    strat->homog=h;
  #ifdef KDEBUG
    idTest(F);
    if(Q != NULL)
      idTest(Q);
  #endif
  #ifdef HAVE_PLURAL
    if (rIsPluralRing(currRing))
    {
      const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
      strat->no_prod_crit   = ! bIsSCA;
      if (w!=NULL)
        r = nc_GB(F, Q, *w, hilb, strat, currRing);
      else
        r = nc_GB(F, Q, NULL, hilb, strat, currRing);
    }
    else
  #endif
    {
      if (rHasLocalOrMixedOrdering(currRing))
      {
        if (w!=NULL)
          r=mora(F,Q,*w,hilb,strat);
        else
          r=mora(F,Q,NULL,hilb,strat);
      }
      else
      {
        strat->sigdrop = FALSE;
        if (w!=NULL)
          r=sba(F,Q,*w,hilb,strat);
        else
          r=sba(F,Q,NULL,hilb,strat);
      }
    }
  #ifdef KDEBUG
    idTest(r);
  #endif
    if (toReset)
    {
      kModW = NULL;
      pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
    }
    currRing->pLexOrder = b;
  //Print("%d reductions canceled \n",strat->cel);
    //delete(strat);
    if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
    return r;
  }
  else
  {
    //--------------------------RING CASE-------------------------
    assume(sbaOrder == 1);
    assume(arri == 0);
    ideal r;
    r = idCopy(F);
    int sbaEnterS = -1;
    bool sigdrop = TRUE;
    //This is how we set the SBA algorithm;
    int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
    while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
                  && (blockred <= blockedreductions))
    {
      loops++;
      if(loops == 1)
        sigdrop = FALSE;
      BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
      BOOLEAN delete_w=(w==NULL);
      kStrategy strat=new skStrategy;
      strat->sbaEnterS = sbaEnterS;
      strat->sigdrop = sigdrop;
      #if 0
      strat->blockred = blockred;
      #else
      strat->blockred = 0;
      #endif
      strat->blockredmax = blockedreductions;
      //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
      //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
      strat->sbaOrder = sbaOrder;
      if (arri!=0)
      {
        strat->rewCrit1 = arriRewDummy;
        strat->rewCrit2 = arriRewCriterion;
        strat->rewCrit3 = arriRewCriterionPre;
      }
      else
      {
        strat->rewCrit1 = faugereRewCriterion;
        strat->rewCrit2 = faugereRewCriterion;
        strat->rewCrit3 = faugereRewCriterion;
      }
 
      if(!TEST_OPT_RETURN_SB)
        strat->syzComp = syzComp;
      if (TEST_OPT_SB_1)
        if(!rField_is_Ring(currRing))
          strat->newIdeal = newIdeal;
      if (rField_has_simple_inverse(currRing))
        strat->LazyPass=20;
      else
        strat->LazyPass=2;
      strat->LazyDegree = 1;
      strat->enterOnePair=enterOnePairNormal;
      strat->chainCrit=chainCritNormal;
      if (TEST_OPT_SB_1) strat->chainCrit=chainCritOpt_1;
      strat->ak = id_RankFreeModule(F,currRing);
      strat->kModW=kModW=NULL;
      strat->kHomW=kHomW=NULL;
      if (vw != NULL)
      {
        currRing->pLexOrder=FALSE;
        strat->kHomW=kHomW=vw;
        strat->pOrigFDeg = currRing->pFDeg;
        strat->pOrigLDeg = currRing->pLDeg;
        pSetDegProcs(currRing,kHomModDeg);
        toReset = TRUE;
      }
      if (h==testHomog)
      {
        if (strat->ak == 0)
        {
          h = (tHomog)idHomIdeal(F,Q);
          w=NULL;
        }
        else if (!TEST_OPT_DEGBOUND)
        {
          if (w!=NULL)
            h = (tHomog)idHomModule(F,Q,w);
          else
            h = (tHomog)idHomIdeal(F,Q);
        }
      }
      currRing->pLexOrder=b;
      if (h==isHomog)
      {
        if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
        {
          strat->kModW = kModW = *w;
          if (vw == NULL)
          {
            strat->pOrigFDeg = currRing->pFDeg;
            strat->pOrigLDeg = currRing->pLDeg;
            pSetDegProcs(currRing,kModDeg);
            toReset = TRUE;
          }
        }
        currRing->pLexOrder = TRUE;
        if (hilb==NULL) strat->LazyPass*=2;
      }
      strat->homog=h;
    #ifdef KDEBUG
      idTest(F);
      if(Q != NULL)
        idTest(Q);
    #endif
    #ifdef HAVE_PLURAL
      if (rIsPluralRing(currRing))
      {
        const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
        strat->no_prod_crit   = ! bIsSCA;
        if (w!=NULL)
          r = nc_GB(F, Q, *w, hilb, strat, currRing);
        else
          r = nc_GB(F, Q, NULL, hilb, strat, currRing);
      }
      else
    #endif
      {
        if (rHasLocalOrMixedOrdering(currRing))
        {
          if (w!=NULL)
            r=mora(F,Q,*w,hilb,strat);
          else
            r=mora(F,Q,NULL,hilb,strat);
        }
        else
        {
          if (w!=NULL)
            r=sba(r,Q,*w,hilb,strat);
          else
          {
            r=sba(r,Q,NULL,hilb,strat);
          }
        }
      }
    #ifdef KDEBUG
      idTest(r);
    #endif
      if (toReset)
      {
        kModW = NULL;
        pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
      }
      currRing->pLexOrder = b;
    //Print("%d reductions canceled \n",strat->cel);
      sigdrop = strat->sigdrop;
      sbaEnterS = strat->sbaEnterS;
      blockred = strat->blockred;
      delete(strat);
      if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
    }
    // Go to std
    if(sigdrop || blockred > blockedreductions)
    {
      r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
    }
    return r;
  }
}

kStd()

ideal kStd	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	mw,
		intvec *	hilb = NULL,
		int	syzComp = 0,
		int	newIdeal = 0,
		intvec *	vw = NULL,
		s_poly_proc_t	sp = NULL
	)

Definition at line 2433 of file kstd1.cc.

{
  if(idIs0(F))
    return idInit(1,F->rank);
 
#ifdef HAVE_SHIFTBBA
  if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
#endif
 
  ideal r;
  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
  BOOLEAN delete_w=(w==NULL);
  kStrategy strat=new skStrategy;
 
  strat->s_poly=sp;
  if(!TEST_OPT_RETURN_SB)
    strat->syzComp = syzComp;
  if (TEST_OPT_SB_1
    &&(!rField_is_Ring(currRing))
    )
    strat->newIdeal = newIdeal;
  if (rField_has_simple_inverse(currRing))
    strat->LazyPass=20;
  else
    strat->LazyPass=2;
  strat->LazyDegree = 1;
  strat->ak = id_RankFreeModule(F,currRing);
  strat->kModW=kModW=NULL;
  strat->kHomW=kHomW=NULL;
  if (vw != NULL)
  {
    currRing->pLexOrder=FALSE;
    strat->kHomW=kHomW=vw;
    strat->pOrigFDeg = currRing->pFDeg;
    strat->pOrigLDeg = currRing->pLDeg;
    pSetDegProcs(currRing,kHomModDeg);
    toReset = TRUE;
  }
  if (h==testHomog)
  {
    if (strat->ak == 0)
    {
      h = (tHomog)idHomIdeal(F,Q);
      w=NULL;
    }
    else if (!TEST_OPT_DEGBOUND)
    {
      if (w!=NULL)
        h = (tHomog)idHomModule(F,Q,w);
      else
        h = (tHomog)idHomIdeal(F,Q);
    }
  }
  currRing->pLexOrder=b;
  if (h==isHomog)
  {
    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
    {
      strat->kModW = kModW = *w;
      if (vw == NULL)
      {
        strat->pOrigFDeg = currRing->pFDeg;
        strat->pOrigLDeg = currRing->pLDeg;
        pSetDegProcs(currRing,kModDeg);
        toReset = TRUE;
      }
    }
    currRing->pLexOrder = TRUE;
    if (hilb==NULL) strat->LazyPass*=2;
  }
  strat->homog=h;
#ifdef KDEBUG
  idTest(F);
  if (Q!=NULL) idTest(Q);
#endif
#ifdef HAVE_PLURAL
  if (rIsPluralRing(currRing))
  {
    const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
    strat->no_prod_crit   = ! bIsSCA;
    if (w!=NULL)
      r = nc_GB(F, Q, *w, hilb, strat, currRing);
    else
      r = nc_GB(F, Q, NULL, hilb, strat, currRing);
  }
  else
#endif
  {
    #if PRE_INTEGER_CHECK
    //the preinteger check strategy is not for modules
    if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
    {
      ideal FCopy = idCopy(F);
      poly pFmon = preIntegerCheck(FCopy, Q);
      if(pFmon != NULL)
      {
        idInsertPoly(FCopy, pFmon);
        strat->kModW=kModW=NULL;
        if (h==testHomog)
        {
            if (strat->ak == 0)
            {
              h = (tHomog)idHomIdeal(FCopy,Q);
              w=NULL;
            }
            else if (!TEST_OPT_DEGBOUND)
            {
              if (w!=NULL)
                h = (tHomog)idHomModule(FCopy,Q,w);
              else
                h = (tHomog)idHomIdeal(FCopy,Q);
            }
        }
        currRing->pLexOrder=b;
        if (h==isHomog)
        {
          if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
          {
            strat->kModW = kModW = *w;
            if (vw == NULL)
            {
              strat->pOrigFDeg = currRing->pFDeg;
              strat->pOrigLDeg = currRing->pLDeg;
              pSetDegProcs(currRing,kModDeg);
              toReset = TRUE;
            }
          }
          currRing->pLexOrder = TRUE;
          if (hilb==NULL) strat->LazyPass*=2;
        }
        strat->homog=h;
      }
      omTestMemory(1);
      if(w == NULL)
      {
        if(rHasLocalOrMixedOrdering(currRing))
            r=mora(FCopy,Q,NULL,hilb,strat);
        else
            r=bba(FCopy,Q,NULL,hilb,strat);
      }
      else
      {
        if(rHasLocalOrMixedOrdering(currRing))
            r=mora(FCopy,Q,*w,hilb,strat);
        else
            r=bba(FCopy,Q,*w,hilb,strat);
      }
      idDelete(&FCopy);
    }
    else
    #endif
    {
      if(w==NULL)
      {
        if(rHasLocalOrMixedOrdering(currRing))
          r=mora(F,Q,NULL,hilb,strat);
        else
          r=bba(F,Q,NULL,hilb,strat);
      }
      else
      {
        if(rHasLocalOrMixedOrdering(currRing))
          r=mora(F,Q,*w,hilb,strat);
        else
          r=bba(F,Q,*w,hilb,strat);
      }
    }
  }
#ifdef KDEBUG
  idTest(r);
#endif
  if (toReset)
  {
    kModW = NULL;
    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
  }
  currRing->pLexOrder = b;
//Print("%d reductions canceled \n",strat->cel);
  delete(strat);
  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
  return r;
}

kStdShift()

ideal kStdShift	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	mw,
		intvec *	hilb = NULL,
		int	syzComp = 0,
		int	newIdeal = 0,
		intvec *	vw = NULL,
		BOOLEAN	rightGB = FALSE
	)

Definition at line 2911 of file kstd1.cc.

{
  assume(rIsLPRing(currRing));
  assume(idIsInV(F));
  ideal r;
  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
  BOOLEAN delete_w=(w==NULL);
  kStrategy strat=new skStrategy;
  intvec* temp_w=NULL;
 
  strat->rightGB = rightGB;
 
  if(!TEST_OPT_RETURN_SB)
    strat->syzComp = syzComp;
  if (TEST_OPT_SB_1)
    if(!rField_is_Ring(currRing))
      strat->newIdeal = newIdeal;
  if (rField_has_simple_inverse(currRing))
    strat->LazyPass=20;
  else
    strat->LazyPass=2;
  strat->LazyDegree = 1;
  strat->ak = id_RankFreeModule(F,currRing);
  strat->kModW=kModW=NULL;
  strat->kHomW=kHomW=NULL;
  if (vw != NULL)
  {
    currRing->pLexOrder=FALSE;
    strat->kHomW=kHomW=vw;
    strat->pOrigFDeg = currRing->pFDeg;
    strat->pOrigLDeg = currRing->pLDeg;
    pSetDegProcs(currRing,kHomModDeg);
    toReset = TRUE;
  }
  if (h==testHomog)
  {
    if (strat->ak == 0)
    {
      h = (tHomog)idHomIdeal(F,Q);
      w=NULL;
    }
    else if (!TEST_OPT_DEGBOUND)
    {
      if (w!=NULL)
        h = (tHomog)idHomModule(F,Q,w);
      else
        h = (tHomog)idHomIdeal(F,Q);
    }
  }
  currRing->pLexOrder=b;
  if (h==isHomog)
  {
    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
    {
      strat->kModW = kModW = *w;
      if (vw == NULL)
      {
        strat->pOrigFDeg = currRing->pFDeg;
        strat->pOrigLDeg = currRing->pLDeg;
        pSetDegProcs(currRing,kModDeg);
        toReset = TRUE;
      }
    }
    currRing->pLexOrder = TRUE;
    if (hilb==NULL) strat->LazyPass*=2;
  }
  strat->homog=h;
#ifdef KDEBUG
  idTest(F);
#endif
  if (rHasLocalOrMixedOrdering(currRing))
  {
    /* error: no local ord yet with shifts */
    WerrorS("No local ordering possible for shift algebra");
    return(NULL);
  }
  else
  {
    /* global ordering */
    if (w!=NULL)
      r=bbaShift(F,Q,*w,hilb,strat);
    else
      r=bbaShift(F,Q,NULL,hilb,strat);
  }
#ifdef KDEBUG
  idTest(r);
#endif
  if (toReset)
  {
    kModW = NULL;
    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
  }
  currRing->pLexOrder = b;
//Print("%d reductions canceled \n",strat->cel);
  delete(strat);
  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
  assume(idIsInV(r));
  return r;
}

kVerify()

BOOLEAN kVerify	(	ideal	F,
		ideal	Q
	)

mora()

ideal mora	(	ideal	F,
		ideal	Q,
		intvec *	w,
		intvec *	hilb,
		kStrategy	strat
	)

Definition at line 1872 of file kstd1.cc.

{
  int olddeg = 0;
  int reduc = 0;
  int red_result = 1;
  int hilbeledeg=1,hilbcount=0;
  BITSET save1;
  SI_SAVE_OPT1(save1);
  if (rHasMixedOrdering(currRing))
  {
    si_opt_1 &= ~Sy_bit(OPT_REDSB);
    si_opt_1 &= ~Sy_bit(OPT_REDTAIL);
  }
 
  strat->update = TRUE;
  /*- setting global variables ------------------- -*/
  initBuchMoraCrit(strat);
  initHilbCrit(F,Q,&hilb,strat);
  initMora(F,strat);
  if(rField_is_Ring(currRing))
    initBuchMoraPosRing(strat);
  else
    initBuchMoraPos(strat);
  /*Shdl=*/initBuchMora(F,Q,strat);
  if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
  /*updateS in initBuchMora has Hecketest
  * and could have put strat->kHEdgdeFound FALSE*/
  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
  {
    strat->posInLOld = strat->posInL;
    strat->posInLOldFlag = FALSE;
    strat->posInL = posInL10;
    updateL(strat);
    reorderL(strat);
  }
  kTest_TS(strat);
  strat->use_buckets = kMoraUseBucket(strat);
 
#ifdef HAVE_TAIL_RING
  if (strat->homog && strat->red == redFirst)
    if(!idIs0(F) &&(!rField_is_Ring(currRing)))
      kStratInitChangeTailRing(strat);
#endif
 
  if (BVERBOSE(23))
  {
    kDebugPrint(strat);
  }
//deleteInL(strat->L,&strat->Ll,1,strat);
//deleteInL(strat->L,&strat->Ll,0,strat);
 
  /*- compute-------------------------------------------*/
  while (strat->Ll >= 0)
  {
    #ifdef KDEBUG
    if (TEST_OPT_DEBUG) messageSets(strat);
    #endif
    if (siCntrlc)
    {
      while (strat->Ll >= 0)
        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
      strat->noClearS=TRUE;
    }
    if (TEST_OPT_DEGBOUND
    && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
    {
      /*
      * stops computation if
      * - 24 (degBound)
      *   && upper degree is bigger than Kstd1_deg
      */
      while ((strat->Ll >= 0)
        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
        && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
      )
      {
        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
        //if (TEST_OPT_PROT)
        //{
        //   PrintS("D"); mflush();
        //}
      }
      if (strat->Ll<0) break;
      else strat->noClearS=TRUE;
    }
    strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
    if (strat->Ll==0) strat->interpt=TRUE;
    strat->Ll--;
    // create the real Spoly
    if (pNext(strat->P.p) == strat->tail)
    {
      /*- deletes the short spoly and computes -*/
      if (rField_is_Ring(currRing))
        pLmDelete(strat->P.p);
      else
        pLmFree(strat->P.p);
      strat->P.p = NULL;
      poly m1 = NULL, m2 = NULL;
      // check that spoly creation is ok
      while (strat->tailRing != currRing &&
             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
      {
        assume(m1 == NULL && m2 == NULL);
        // if not, change to a ring where exponents are large enough
        kStratChangeTailRing(strat);
      }
      /* create the real one */
      ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
                    strat->tailRing, m1, m2, strat->R);
      if (!strat->use_buckets)
        strat->P.SetLength(strat->length_pLength);
    }
    else if (strat->P.p1 == NULL)
    {
      // for input polys, prepare reduction (buckets !)
      strat->P.SetLength(strat->length_pLength);
      strat->P.PrepareRed(strat->use_buckets);
    }
 
    // the s-poly
    if (!strat->P.IsNull())
    {
      // might be NULL from noether !!!
      if (TEST_OPT_PROT)
        message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
      // reduce
      red_result = strat->red(&strat->P,strat);
    }
 
    // the reduced s-poly
    if (! strat->P.IsNull())
    {
      strat->P.GetP();
      // statistics
      if (TEST_OPT_PROT) PrintS("s");
      // normalization
      if (TEST_OPT_INTSTRATEGY)
        strat->P.pCleardenom();
      else
        strat->P.pNorm();
      // tailreduction
      strat->P.p = redtail(&(strat->P),strat->sl,strat);
      if (strat->P.p==NULL)
      {
        WerrorS("exponent overflow - wrong ordering");
        return(idInit(1,1));
      }
      // set ecart -- might have changed because of tail reductions
      if ((!strat->noTailReduction) && (!strat->honey))
        strat->initEcart(&strat->P);
      // cancel unit
      cancelunit(&strat->P);
      // for char 0, clear denominators
      if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
      && TEST_OPT_INTSTRATEGY)
        strat->P.pCleardenom();
 
      strat->P.SetShortExpVector();
      enterT(strat->P,strat);
      // build new pairs
      if (rField_is_Ring(currRing))
        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
      else
        enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
      // put in S
      strat->enterS(strat->P,
                    posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
                    strat, strat->tl);
      // apply hilbert criterion
      if (hilb!=NULL)
      {
        if (strat->homog==isHomog)
          khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
        else
          khCheckLocInhom(Q,w,hilb,hilbcount,strat);
      }
 
      // clear strat->P
      kDeleteLcm(&strat->P);
 
#ifdef KDEBUG
      // make sure kTest_TS does not complain about strat->P
      strat->P.Clear();
#endif
    }
    if (strat->kAllAxis)
    {
      if ((TEST_OPT_FINDET)
      || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL,strat->tailRing) < Kstd1_mu)))
      {
        // obachman: is this still used ???
        /*
        * stops computation if strat->kAllAxis and
        * - 27 (finiteDeterminacyTest)
        * or
        * - 23
        *   (multBound)
        *   && multiplicity of the ideal is smaller then a predefined number mu
        */
        while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
      }
    }
    kTest_TS(strat);
  }
  /*- complete reduction of the standard basis------------------------ -*/
  if (TEST_OPT_REDSB) completeReduce(strat);
  else if (TEST_OPT_PROT) PrintLn();
  /*- release temp data------------------------------- -*/
  exitBuchMora(strat);
  /*- polynomials used for HECKE: HC, noether -*/
  if (TEST_OPT_FINDET)
  {
    if (strat->kNoether!=NULL)
      Kstd1_mu=currRing->pFDeg(strat->kNoether,currRing);
    else
      Kstd1_mu=-1;
  }
  if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
  if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG))  messageStat(hilbcount,strat);
//  if (TEST_OPT_WEIGHTM)
//  {
//    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
//    if (ecartWeights)
//    {
//      omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
//      ecartWeights=NULL;
//    }
//  }
  if(nCoeff_is_Z(currRing->cf))
    finalReduceByMon(strat);
  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
  SI_RESTORE_OPT1(save1);
  idTest(strat->Shdl);
  return (strat->Shdl);
}

rightgb()

ideal rightgb	(	ideal	F,
		ideal	Q
	)

Definition at line 4715 of file kstd2.cc.

{
  assume(rIsLPRing(currRing));
  assume(idIsInV(F));
  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
  idSkipZeroes(RS); // is this even necessary?
  assume(idIsInV(RS));
  return(RS);
}

stdred()

ideal stdred	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	w
	)

Variable Documentation

kHomW

EXTERN_VAR intvec* kHomW

Definition at line 70 of file kstd1.h.

kModW

EXTERN_VAR intvec* kModW

Definition at line 69 of file kstd1.h.

kOptions

EXTERN_VAR BITSET kOptions

Definition at line 51 of file kstd1.h.

Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 49 of file kstd1.h.

Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 49 of file kstd1.h.

validOpts

EXTERN_VAR BITSET validOpts

Definition at line 53 of file kstd1.h.