kstd1.h File Reference

#include "kernel/structs.h"
#include "polys/monomials/ring.h"
#include "coeffs/bigintmat.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
#define	KSTD_NF_CANCELUNIT   8
#define	KSTD_NF_NOLF   4096

Typedefs
typedef BOOLEAN(*	s_poly_proc_t) (kStrategy strat)

Functions
ideal	mora (ideal F, ideal Q, intvec *w, bigintmat *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)
ideal	idDivRem (ideal A, const ideal quot, ideal &factor, ideal *unit, 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.
ideal	kSba (ideal F, ideal Q, tHomog h, intvec **mw, int incremental=0, int arri=0, bigintmat *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)
	generic interface to GB/SB computations
ideal	kStd2 (ideal F, ideal Q, tHomog h, intvec **mw, bigintmat *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL)
	generic interface to GB/SB computations, large hilbert vectors
ideal	kStd_internal (ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL)
	pure GB/SB computations
ideal	kStdShift (ideal F, ideal Q, tHomog h, intvec **mw, bigintmat *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE)
ideal	kTryHilbstd (ideal F, ideal Q)
ideal	kTryHilbstd_par (ideal F, ideal Q, tHomog h, intvec **mw)
poly	kTryHC (ideal F, ideal Q)
ideal	rightgb (ideal F, const ideal Q)
void	initMora (ideal F, kStrategy strat)
ideal	kInterRed (ideal F, const ideal Q=NULL)
ideal	kInterRedOld (ideal F, const ideal Q=NULL)
ideal	kInterRedBba (ideal F, ideal Q, int &need_retry)
long	kModDeg (poly p, const ring r=currRing)
long	kHomModDeg (poly p, const ring r=currRing)
ideal	stdred (ideal F, ideal Q, tHomog h, intvec **w)
ideal	kMin_std2 (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, bigintmat *hilb, int syzComp=0, int reduced=0)
ideal	kMin_std (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, 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_CANCELUNIT

#define KSTD_NF_CANCELUNIT   8

Definition at line 24 of file kstd1.h.

KSTD_NF_ECART

#define KSTD_NF_ECART   2

Definition at line 20 of file kstd1.h.

KSTD_NF_LAZY

#define KSTD_NF_LAZY   1

Definition at line 18 of file kstd1.h.

KSTD_NF_NOLF

#define KSTD_NF_NOLF   4096

Definition at line 26 of file kstd1.h.

KSTD_NF_NONORM

#define KSTD_NF_NONORM   4

Definition at line 22 of file kstd1.h.

Typedef Documentation

s_poly_proc_t

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)

Definition at line 15 of file kstd1.h.

Function Documentation

idDivRem()

ideal idDivRem	(	ideal	A,
		const ideal	quot,
		ideal &	factor,
		ideal *	unit,
		int	lazyReduce = 0 )

Definition at line 347 of file kLiftstd.cc.

{
  /* special cases */
  if (idIs0(A) || idIs0(quot))
  {
    factor=idInit(1,IDELEMS(quot));
    setUnit(A->rank,unit);
    return idCopy(A);
  }
  /* ideal or module? */
  ring orig_ring=currRing;
  int k=id_RankFreeModule(quot,orig_ring);
  int lsmod=0;
  if (k==0) { lsmod=1;k=1;}  /*ideal*/
  /* NF(A 0 E,quot E 0)
   * A,quot: 1..k, 0,E: k+1..k+IDELEMS(quot),
   * E,0: k+IDELEMS(quot)..k+IDELEMS(quot)+IDELEMS(A) */
  /* new ring */
  ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
  rSetSyzComp(1,syz_ring);
  rChangeCurrRing(syz_ring);
  /* move ideals to new ring */
  ideal s_quot;
  ideal s_A;
  if (orig_ring != syz_ring)
  {
    s_quot=idrCopyR_NoSort(quot,orig_ring,syz_ring);
    s_A=idrCopyR_NoSort(A,orig_ring,syz_ring);
  }
  else
  {
    s_quot=id_Copy(quot,syz_ring);
    s_A=id_Copy(A,syz_ring);
  }
  /* quot[i] -> quot[i]+e(k+i+1) */
  for(int i=0;i<IDELEMS(s_quot);i++)
  {
    p_Shift(&s_quot->m[i],lsmod,syz_ring);
    poly p=p_One(syz_ring);
    p_SetComp(p,k+i+2,syz_ring);
    p_Setm(p,syz_ring);
    s_quot->m[i]=p_Add_q(s_quot->m[i],p,syz_ring);
  }
  s_quot->rank=k+IDELEMS(quot)+1;
  /* A[i] -> A[i]*e(1) */
  if (lsmod==1)
  {
    for(int i=0;i<IDELEMS(s_A);i++)
    {
      p_Shift(&s_A->m[i],1,syz_ring);
    }
  }
  if (unit!=NULL)
  {
    int u_k=k+IDELEMS(quot)+2;
    for(int i=0;i<IDELEMS(s_A);i++)
    {
      poly p=p_One(syz_ring);
      p_SetComp(p,u_k+i,syz_ring);
      p_Setm(p,syz_ring);
      s_A->m[i]=p_Add_q(s_A->m[i],p,syz_ring);
    }
    s_A->rank=k+IDELEMS(quot)+IDELEMS(A)+1;
  }
  /* normalform */
  #if 0
  PrintS("to reduce:\n");
  {
    void ipPrint_MA0(matrix m, const char *name);
    matrix m = id_Module2Matrix(id_Copy(s_A,currRing),currRing);
    ipPrint_MA0(m, "A");
    id_Delete((ideal *) &m,currRing);
  }
  PrintS("with:\n");
  {
    void ipPrint_MA0(matrix m, const char *name);
    matrix m = id_Module2Matrix(id_Copy(s_quot,currRing),currRing);
    ipPrint_MA0(m, "B");
    id_Delete((ideal *) &m,currRing);
  }
  #endif
  ideal rest=kNF(s_quot,syz_ring->qideal,s_A,0,lazyReduce);
  #if 0
  PrintS("result NF:\n");
  {
    void ipPrint_MA0(matrix m, const char *name);
    matrix m = id_Module2Matrix(id_Copy(rest,currRing),currRing);
    ipPrint_MA0(m, "A");
    id_Delete((ideal *) &m,currRing);
  }
  #endif
  /* clean s_quot,s_A */
  id_Delete(&s_quot,syz_ring);
  id_Delete(&s_A,syz_ring);
  /* interpret rest: remainder */
  ideal result=idInit(IDELEMS(rest),A->rank);
  for(int i=0;i<IDELEMS(rest);i++)
  {
    poly p=rest->m[i];
    poly d=NULL;
    while(p!=NULL)
    {
      poly q=p; pIter(p);
      pNext(q)=NULL;
      if (p_GetComp(q,syz_ring)<=k)
      {
        result->m[i]=p_Add_q(result->m[i],q,syz_ring);
      }
      else
      {
        d=p_Add_q(d,q,syz_ring);
      }
    }
    rest->m[i]=d;
    p_Shift(&result->m[i],-lsmod,syz_ring);
  }
  #if 0
  PrintS("rest:\n");
  {
    void ipPrint_MA0(matrix m, const char *name);
    matrix m = id_Module2Matrix(id_Copy(result,currRing),currRing);
    ipPrint_MA0(m, "_");
    id_Delete((ideal *) &m,currRing);
  }
  #endif
  #if 0
  PrintS("factor+unit:\n");
  {
    void ipPrint_MA0(matrix m, const char *name);
    matrix m = id_Module2Matrix(id_Copy(rest,currRing),currRing);
    ipPrint_MA0(m, "_");
    id_Delete((ideal *) &m,currRing);
  }
  #endif
  /* interpret rest: factors */
  factor=idInit(IDELEMS(rest),IDELEMS(quot));
  if (unit==NULL)
  {
    for(int i=0;i<IDELEMS(rest);i++)
    {
      poly p=rest->m[i];
      p_Shift(&p,-k-lsmod,syz_ring);
      factor->m[i]=p;
      factor->m[i]=p_Neg(factor->m[i],syz_ring);
      rest->m[i]=NULL;
    }
  }
  else
  {
    *unit=idInit(IDELEMS(A),IDELEMS(A));
    /* comp k+1..u_k-1 -> rest, u_k.. -> unit*/
    int u_k=k+IDELEMS(quot)+2;
    for(int i=0;i<IDELEMS(rest);i++)
    {
      poly p=rest->m[i];
      rest->m[i]=NULL;
      poly d=NULL;
      while(p!=NULL)
      {
        poly q=p; pIter(p);
        pNext(q)=NULL;
        if(p_GetComp(q,syz_ring)<u_k)
        {
          p_Shift(&q,-k-1,syz_ring);
          factor->m[i]=p_Add_q(factor->m[i],q,syz_ring);
        }
        else
        {
          d=p_Add_q(d,q,syz_ring);
        }
      }
      (*unit)->m[i]=d;
      /*fix sign:*/
      factor->m[i]=p_Neg(factor->m[i],syz_ring);
      p_Shift(&(*unit)->m[i],-(IDELEMS(quot)+k+1),syz_ring);
    }
  }
  id_Delete(&rest,syz_ring);
  if (orig_ring != syz_ring)
  {
    rChangeCurrRing(orig_ring);
    result=idrMoveR_NoSort(result, syz_ring, orig_ring);
    factor=idrMoveR(factor, syz_ring, orig_ring);
    if (unit!=NULL)
    {
      *unit=idrMoveR(*unit, syz_ring, orig_ring);
    }
    rDelete(syz_ring);
  }
  return result;
}

initMora()

void initMora	(	ideal	F,
		kStrategy	strat )

Definition at line 1820 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;
  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 )
  {
    strat->kNoether = pCopy((currRing->ppNoether));
    if (TEST_OPT_PROT)
    {
      Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
      mflush();
    }
  }
  if (strat->kNoether!=NULL)
  {
    HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
  }
  else
  {
    HCord = INT_MAX-3;/*- 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 3444 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,
		const ring	r = currRing )

Definition at line 2421 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,
		const ideal	Q = NULL )

Definition at line 3803 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=0;
  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 | KSTD_NF_NONORM);
    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 | KSTD_NF_NONORM);
      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;
}

kInterRedBba()

ideal kInterRedBba	(	ideal	F,
		ideal	Q,
		int &	need_retry )

Definition at line 3552 of file kstd1.cc.

{
  need_retry=0;
  int   red_result = 1;
  int   olddeg,reduc;
  // BOOLEAN withT = FALSE;
  // BOOLEAN toReset=FALSE;
  kStrategy strat=new skStrategy;
  tHomog h;
 
  if (rField_has_simple_inverse(currRing))
    strat->LazyPass=20;
  else
    strat->LazyPass=2;
  strat->LazyDegree = 1;
  strat->ak = id_RankFreeModule(F,currRing);
  strat->syzComp = strat->ak;
  strat->kModW=kModW=NULL;
  strat->kHomW=kHomW=NULL;
  if (strat->ak == 0)
  {
    h = (tHomog)idHomIdeal(F,Q);
  }
  else if (!TEST_OPT_DEGBOUND)
  {
    h = (tHomog)idHomIdeal(F,Q);
  }
  else
    h = isNotHomog;
  if (h==isHomog)
  {
    strat->LazyPass*=2;
  }
  strat->homog=h;
#ifdef KDEBUG
  idTest(F);
#endif
 
  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
  if(rField_is_Ring(currRing))
    initBuchMoraPosRing(strat);
  else
    initBuchMoraPos(strat);
  initBba(strat);
  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
  strat->posInL=posInL0; /* ord according pComp */
 
  /*Shdl=*/initBuchMora(F, Q, strat);
  reduc = olddeg = 0;
 
#ifndef NO_BUCKETS
  if (!TEST_OPT_NOT_BUCKETS)
    strat->use_buckets = 1;
#endif
 
  // redtailBBa against T for inhomogeneous input
  //if (!TEST_OPT_OLDSTD)
  //  withT = ! strat->homog;
 
  // strat->posInT = posInT_pLength;
  kTest_TS(strat);
 
#ifdef HAVE_TAIL_RING
  kStratInitChangeTailRing(strat);
#endif
 
  /* compute------------------------------------------------------- */
  while (strat->Ll >= 0)
  {
    #ifdef KDEBUG
      if (TEST_OPT_DEBUG) messageSets(strat);
    #endif
    if (strat->Ll== 0) strat->interpt=TRUE;
    /* picks the last element from the lazyset L */
    strat->P = strat->L[strat->Ll];
    strat->Ll--;
 
    if (strat->P.p1 == NULL)
    {
      // for input polys, prepare reduction
      strat->P.PrepareRed(strat->use_buckets);
    }
 
    if (strat->P.p == NULL && strat->P.t_p == NULL)
    {
      red_result = 0;
    }
    else
    {
      if (TEST_OPT_PROT)
        message(strat->P.pFDeg(),
                &olddeg,&reduc,strat, red_result);
 
      /* reduction of the element chosen from L */
      red_result = strat->red(&strat->P,strat);
    }
 
    // reduction to non-zero new poly
    if (red_result == 1)
    {
      /* statistic */
      if (TEST_OPT_PROT) PrintS("s");
 
      // get the polynomial (canonicalize bucket, make sure P.p is set)
      strat->P.GetP(strat->lmBin);
 
      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
 
      // reduce the tail and normalize poly
      // in the ring case we cannot expect LC(f) = 1,
      // therefore we call pCleardenom instead of pNorm
      if (TEST_OPT_INTSTRATEGY)
      {
        strat->P.pCleardenom();
      }
      else
      {
        strat->P.pNorm();
      }
 
#ifdef KDEBUG
      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
#endif
 
      // enter into S, L, and T
      if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
      {
        enterT(&strat->P, strat);
        // posInS only depends on the leading term
        strat->enterS(&strat->P, pos, strat, strat->tl);
 
        if (pos<strat->sl)
        {
          need_retry++;
          // move all "larger" elements fromS to L
          // remove them from T
          int ii=pos+1;
          for(;ii<=strat->sl;ii++)
          {
            LObject h;
            h.Clear();
            h.tailRing=strat->tailRing;
            h.p=strat->S[ii]; strat->S[ii]=NULL;
            strat->initEcart(&h);
            h.sev=strat->sevS[ii];
            int jj=strat->tl;
            while (jj>=0)
            {
              if (strat->T[jj].p==h.p)
              {
                strat->T[jj].p=NULL;
                if (jj<strat->tl)
                {
                  memmove(&(strat->T[jj]),&(strat->T[jj+1]),
                          (strat->tl-jj)*sizeof(strat->T[jj]));
                  memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
                          (strat->tl-jj)*sizeof(strat->sevT[jj]));
                }
                strat->tl--;
                break;
              }
              jj--;
            }
            int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
            enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
            #ifdef KDEBUG
            if (TEST_OPT_DEBUG)
            {
              Print("move S[%d] -> L[%d]: ",ii,pos);
              p_wrp(h.p,currRing, strat->tailRing);
              PrintLn();
            }
            #endif
          }
          if (strat->fromQ!=NULL)
          {
            for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
          }
          strat->sl=pos;
        }
      }
      else
      {
        // clean P
      }
      kDeleteLcm(&strat->P);
    }
 
#ifdef KDEBUG
    if (TEST_OPT_DEBUG)
    {
      messageSets(strat);
    }
    strat->P.Clear();
#endif
    //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
  }
#ifdef KDEBUG
  //if (TEST_OPT_DEBUG) messageSets(strat);
#endif
  /* complete reduction of the standard basis--------- */
 
  if((need_retry<=0) && (TEST_OPT_REDSB))
  {
    completeReduce(strat);
    if (strat->completeReduce_retry)
    {
      // completeReduce needed larger exponents, retry
      // hopefully: kStratChangeTailRing already provided a larger tailRing
      //    (otherwise: it will fail again)
      strat->completeReduce_retry=FALSE;
      completeReduce(strat);
      if (strat->completeReduce_retry)
      {
#ifdef HAVE_TAIL_RING
        if(currRing->bitmask>strat->tailRing->bitmask)
        {
          // retry without T
          strat->completeReduce_retry=FALSE;
          cleanT(strat);strat->tailRing=currRing;
          int i;
          for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
          completeReduce(strat);
        }
        if (strat->completeReduce_retry)
#endif
          Werror("exponent bound is %ld",currRing->bitmask);
      }
    }
  }
  else if (TEST_OPT_PROT) PrintLn();
 
 
  /* release temp data-------------------------------- */
  exitBuchMora(strat);
//  if (TEST_OPT_WEIGHTM)
//  {
//    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
//    if (ecartWeights)
//    {
//      omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
//      ecartWeights=NULL;
//    }
//  }
  //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
  ideal res=strat->Shdl;
  strat->Shdl=NULL;
  delete strat;
  return res;
}

kInterRedOld()

ideal kInterRedOld	(	ideal	F,
		const ideal	Q = NULL )

Definition at line 3457 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 = 0;
  if (id_IsModule(tempF,currRing)) 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]);
    }
    omFree((ADDRESS)strat->fromQ);
    strat->fromQ=NULL;
  }
//  if (TEST_OPT_PROT)
//  {
//    writeTime("end Interred:");
//    mflush();
//  }
  ideal shdl=strat->Shdl;
  idSkipZeroes(shdl);
  if (strat->fromQ)
  {
    omfree(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,
		int	syzComp = 0,
		int	reduced = 0 )

Definition at line 3222 of file kstd1.cc.

{
  bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
  ideal res=kMin_std2(F,Q,h,w,M,hh,syzComp,reduced);
  if (hh!=NULL) delete hh;
  return res;
}

kMin_std2()

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

Definition at line 3070 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 = kStd2(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 = 0;
  if (id_IsModule(F,currRing)) 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;
  ideal SB=NULL;
  if (rHasLocalOrMixedOrdering(currRing))
  {
    r=idMinBase(F,&SB); // SB and M via minbase
    strat->M=r;
    r=SB;
  }
  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;
    strat->M=NULL;
  }
  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,
		const ring	r = currRing )

Definition at line 2411 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 3328 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(Q)) Q=NULL;
 
  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 3230 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(Q)) Q=NULL;
 
  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 2260 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: reduce 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);
        }
        else
          p = redMoraNF(p,strat, lazyReduce);
        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 unused */
  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);
  omfree((ADDRESS)strat->fromQ);
  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 2119 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: reduce 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)) /*never true for ring-cf*/
  {
    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|KSTD_NF_CANCELUNIT));
  }
  else
  {
    if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & (KSTD_NF_ECART|KSTD_NF_CANCELUNIT));
  }
  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 unused */
  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);
 
  omfree((ADDRESS)strat->fromQ);
  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 3393 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 3286 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,
		bigintmat *	hilb = NULL,
		int	syzComp = 0,
		int	newIdeal = 0,
		intvec *	vw = NULL )

Definition at line 2669 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 = 0;
    if (id_IsModule(F,currRing)) 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 = 0;
      if (id_IsModule(F,currRing)) 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 = kStd2(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 )

generic interface to GB/SB computations

Definition at line 2660 of file kstd1.cc.

{
  bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
  ideal res=kStd2(F,Q,h,w,hh,syzComp,newIdeal,vw,sp);
  if (hh!=NULL) delete hh;
  return res;
}

kStd2()

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

generic interface to GB/SB computations, large hilbert vectors

rIsLPRing already tested above

Definition at line 2607 of file kstd1.cc.

{
  if(idIs0(F))
    return idInit(1,F->rank);
 
  if(idIs0(Q)) Q=NULL;
#ifdef HAVE_SHIFTBBA
  if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
#endif
 
  if ((hilb==NULL)
  && (vw==NULL)
  && (newIdeal==0)
  && (sp==NULL)
  && (IDELEMS(F)>1)
  && (!TEST_OPT_SB_1)
  && (currRing->ppNoether==NULL)
  && !rIsPluralRing(currRing)  /*!rIsLPRing already tested above*/
  && (!id_IsModule(F,currRing)))
  {
    /* test HC precomputation*/
    if( rField_is_Q(currRing)
    && (!rHasGlobalOrdering(currRing))
    && (rOrd_is_ds(currRing)||rOrd_is_Ds(currRing))
    && (!idIsSimpleGB(F,Q)))
    {
      currRing->ppNoether=kTryHC(F,Q);
      ideal res=kStd_internal(F,Q,h,w,hilb,syzComp,newIdeal,vw,sp);
      if (currRing->ppNoether!=NULL) pLmDelete(currRing->ppNoether);
      currRing->ppNoether=NULL;
      return res;
    }
    /* test hilbstd */
    if ( rHasGlobalOrdering(currRing)
    && (!TEST_OPT_RETURN_SB)
    && (!TEST_OPT_DEGBOUND)
    && (currRing->LexOrder
         || rHasBlockOrder(currRing))
    && (!idIsSimpleGB(F,Q))
    && ( rField_is_Q(currRing)|| rField_is_Zp(currRing)))
    {
      ideal result=kTryHilbstd(F,Q);
      //ideal result=kTryHilbstd_par(F,Q,h,w);
      if (result!=NULL)
      {
        return result;
      }
    }
  }
  return kStd_internal(F,Q,h,w,hilb,syzComp,newIdeal,vw,sp);
}

kStd_internal()

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

pure GB/SB computations

Definition at line 2434 of file kstd1.cc.

{
  assume(!idIs0(F));
  assume((Q==NULL)||(!idIs0(Q)));
 
  kStrategy strat=new skStrategy;
 
  ideal r;
  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
  BOOLEAN delete_w=(w==NULL);
 
  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 = 0;
  if (id_IsModule(F,currRing)) 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)
        {
          h = (tHomog)idHomIdeal(FCopy,Q);
          w=NULL;
        }
        currRing->pLexOrder=b;
        if (h==isHomog)
        {
          if ((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);
      }
    }
  }
  if(errorreported) return NULL;
#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,
		bigintmat *	hilb = NULL,
		int	syzComp = 0,
		int	newIdeal = 0,
		intvec *	vw = NULL,
		BOOLEAN	rightGB = FALSE )

Definition at line 2965 of file kstd1.cc.

{
  assume(rIsLPRing(currRing));
  assume(idIsInV(F));
  if (rHasLocalOrMixedOrdering(currRing))
  {
    /* error: no local ord yet with shifts */
    WerrorS("No local ordering possible for shift algebra");
    return(NULL);
  }
  ideal r;
  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
  BOOLEAN delete_w=(w==NULL);
  kStrategy strat=new skStrategy;
 
  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 = 0;
  if (id_IsModule(F,currRing)) 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
  /* 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;
}

kTryHC()

poly kTryHC	(	ideal	F,
		ideal	Q )

Definition at line 38 of file kstdhelper.cc.

{
  if (Q!=NULL)
    return NULL;
  int prim=kFindLuckyPrime(F,Q);
  if (TEST_OPT_PROT) Print("try HC in ring over ZZ/%d\n",prim);
  // create Zp_ring
  ring save_ring=currRing;
  ring Zp_ring=rCopy0(save_ring);
  nKillChar(Zp_ring->cf);
  Zp_ring->cf=nInitChar(n_Zp, (void*)(long)prim);
  rComplete(Zp_ring);
  // map data
  rChangeCurrRing(Zp_ring);
  nMapFunc nMap=n_SetMap(save_ring->cf,Zp_ring->cf);
  if (nMap==NULL) return NULL;
  ideal FF=id_PermIdeal(F,1,IDELEMS(F),NULL,save_ring,Zp_ring,nMap,NULL,0,0);
  ideal QQ=NULL;
  if (Q!=NULL) QQ=id_PermIdeal(Q,1,IDELEMS(Q),NULL,save_ring,Zp_ring,nMap,NULL,0,0);
  // call std
  kStrategy strat=new skStrategy;
  strat->LazyPass=20;
  strat->LazyDegree = 1;
  strat->kModW=kModW=NULL;
  strat->kHomW=kHomW=NULL;
  strat->homog = (tHomog)idHomIdeal(F,Q);
  ideal res=mora(FF,QQ,NULL,NULL,strat);
  // clean
  idDelete(&FF);
  poly HC=NULL;
  if (strat->kNoether!=NULL) scComputeHC(res,QQ,0,HC);
  delete strat;
  if (QQ!=NULL) idDelete(&QQ);
  idDelete(&res);
  // map back
  rChangeCurrRing(save_ring);
  if (HC!=NULL)
  {
    //p_IncrExp(HC,Zp_ring->N,Zp_ring);
    for (int i=rVar(Zp_ring)-1; i>0; i--)
    {
      int e;
      if ((e=pGetExp(HC, i)) > 0) pSetExp(HC,i,e-1);
    }
    p_Setm(HC,Zp_ring);
    if (TEST_OPT_PROT) Print("HC(%ld) found\n",pTotaldegree(HC));
    pSetCoeff0(HC,nInit(1));
  }
  else
  {
    if (TEST_OPT_PROT) PrintS("HC not found\n");
  }
  rDelete(Zp_ring);
  return HC;
}

kTryHilbstd()

ideal kTryHilbstd	(	ideal	F,
		ideal	Q )

Definition at line 326 of file kstdhelper.cc.

{
 if (rField_is_Ring(currRing)) return NULL;
 if(!TEST_V_PURE_GB)
 {
   tHomog h = (tHomog)id_HomIdealDP(F,Q,currRing);
   if (h==(tHomog)TRUE) return kTryHilbstd_homog(F,Q);
   if((!rField_is_Q(currRing))
   &&(!rField_is_Zp(currRing))
   ) return NULL;
   if (h==(tHomog)FALSE) return kTryHilbstd_nonhomog(F,Q);
 }
 return NULL;
}

kTryHilbstd_par()

ideal kTryHilbstd_par	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	mw )

Definition at line 341 of file kstdhelper.cc.

{
  int cpus = (long) feOptValue(FE_OPT_CPUS);
  if (cpus<1)
  {
    //WerrorS("no sub-processes allowed");
    return NULL;
  }
#if 0
  if(!TEST_V_PURE_GB)
  {
    int cp_std[2];
    int cp_hstd[2];
    int err1=pipe(cp_std);// [0] is read , [1] is write
    int err2=pipe(cp_hstd);
    if (err1||err2)
    {
      Werror("pipe failed with %d\n",errno);
      si_close(cp_std[0]);
      si_close(cp_std[1]);
      si_close(cp_hstd[0]);
      si_close(cp_hstd[1]);
      return NULL;
    }
    pid_t pid_std=fork();
    if (pid_std==0) /*child std*/
    {
      si_set_signal(SIGTERM,sig_term_hdl_child);
      si_close(cp_std[0]);
      si_close(cp_hstd[0]);
      si_close(cp_hstd[1]);
      ssiInfo d;
      memset(&d,0,sizeof(d));
      d.f_write=fdopen(cp_std[1],"w");
      d.fd_write=cp_std[1];
      d.r=currRing;
      si_opt_2|=Sy_bit(V_PURE_GB);
      ideal res=kStd_internal(F,Q,h,mw);
      ssiWriteIdeal(&d,IDEAL_CMD,res);
      fclose(d.f_write);
      _exit(0);
    }
    pid_t pid_hstd=fork();
    if (pid_hstd==0) /*child hstd*/
    {
      si_set_signal(SIGTERM,sig_term_hdl_child);
      si_close(cp_hstd[0]);
      si_close(cp_std[0]);
      si_close(cp_std[1]);
      ssiInfo d;
      memset(&d,0,sizeof(d));
      d.f_write=fdopen(cp_hstd[1],"w");
      d.fd_write=cp_hstd[1];
      d.r=currRing;
 
      si_opt_2|=Sy_bit(V_PURE_GB);
      ideal res=kTryHilbstd(F,Q);
      if (res!=NULL)
      {
        ssiWriteIdeal(&d,IDEAL_CMD,res);
      }
      fclose(d.f_write);
      _exit(0);
    }
    /*parent*/
    si_close(cp_std[1]);
    si_close(cp_hstd[1]);
  #ifdef HAVE_POLL
    pollfd pfd[2];
    pfd[0].fd=cp_std[0];
    pfd[0].events=POLLIN;
    pfd[1].fd=cp_hstd[0];
    pfd[1].events=POLLIN;
    int s=si_poll(pfd,2,-1); // wait infinite
    ideal res;
    ssiInfo d;
    memset(&d,0,sizeof(d));
    d.r=currRing;
    if (s==1) //std
    {
      d.f_read=s_open(cp_std[0]);
      d.fd_read=cp_std[0];
      res=ssiReadIdeal(&d);
      si_close(cp_hstd[0]);
      s_close(d.f_read);
      si_close(cp_std[0]);
      kill(pid_hstd,SIGTERM);
      si_waitpid(pid_std,NULL,0);
      si_waitpid(pid_hstd,NULL,0);
    }
    else if(s==2)
    {
      d.f_read=s_open(cp_hstd[0]);
      d.fd_read=cp_hstd[0];
      res=ssiReadIdeal(&d);
      si_close(cp_std[0]);
      s_close(d.f_read);
      si_close(cp_hstd[0]);
      kill(pid_std,SIGTERM);
      si_waitpid(pid_hstd,NULL,0);
      si_waitpid(pid_std,NULL,0);
    }
    return res;
  #endif
  }
#endif
  return NULL;
}

kVerify()

BOOLEAN kVerify	(	ideal	F,
		ideal	Q )

Definition at line 367 of file kverify.cc.

{
  #ifdef HAVE_VSPACE
  int cpus = (long) feOptValue(FE_OPT_CPUS);
  if (cpus>1)
    return kVerify2(F,currRing->qideal);
  else
  #endif
    return kVerify1(F,currRing->qideal);
}

mora()

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

Definition at line 1887 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(FALSE,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); 
 
  /*- 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);
      strat->P.PrepareRed(strat->use_buckets);
    }
    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) < 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;
  }
  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,
		const ideal	Q )

Definition at line 4935 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 95 of file kstd1.h.

kModW

EXTERN_VAR intvec* kModW

Definition at line 94 of file kstd1.h.

kOptions

EXTERN_VAR BITSET kOptions

Definition at line 72 of file kstd1.h.

Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 70 of file kstd1.h.

Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 70 of file kstd1.h.

validOpts

EXTERN_VAR BITSET validOpts

Definition at line 74 of file kstd1.h.