kstd1.cc File Reference

#include "kernel/mod2.h"
#include "misc/options.h"
#include "misc/intvec.h"
#include "polys/weight.h"
#include "kernel/polys.h"
#include "kernel/GBEngine/kutil.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/khstd.h"
#include "kernel/combinatorics/stairc.h"
#include "kernel/ideals.h"
#include "polys/nc/nc.h"
#include "polys/nc/sca.h"
#include "kernel/GBEngine/nc.h"
#include "kernel/GBEngine/kInline.h"
#include "polys/shiftop.h"

Go to the source code of this file.

Macros
#define	MORA_USE_BUCKETS
#define	PRE_INTEGER_CHECK   0

Functions
static BOOLEAN	kMoraUseBucket (kStrategy strat)
static void	kOptimizeLDeg (pLDegProc ldeg, kStrategy strat)
static int	doRed (LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
int	redEcart (LObject *h, kStrategy strat)
int	redRiloc (LObject *h, kStrategy strat)
int	redRiloc_Z (LObject *h, kStrategy strat)
int	redFirst (LObject *h, kStrategy strat)
static poly	redMoraNF (poly h, kStrategy strat, int flag)
static poly	redMoraNFRing (poly h, kStrategy strat, int flag)
static void	reorderL (kStrategy strat)
static void	reorderT (kStrategy strat)
static void	missingAxis (int *last, kStrategy strat)
static BOOLEAN	hasPurePower (const poly p, int last, int *length, kStrategy strat)
static BOOLEAN	hasPurePower (LObject *L, int last, int *length, kStrategy strat)
int	posInL10 (const LSet set, const int length, LObject *p, const kStrategy strat)
static void	updateL (BOOLEAN searchPP, kStrategy strat)
static void	updateLHC (kStrategy strat)
static void	updateT (kStrategy strat)
static void	firstUpdate (kStrategy strat)
void	enterSMora (LObject *p, int atS, kStrategy strat, int atR)
void	enterSMoraNF (LObject *p, int atS, kStrategy strat, int atR)
void	initBba (kStrategy strat)
void	initSba (ideal F, kStrategy strat)
void	initMora (ideal F, kStrategy strat)
void	kDebugPrint (kStrategy strat)
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)
long	kModDeg (poly p, const ring r)
long	kHomModDeg (poly p, const ring r)
ideal	kStd_internal (ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
	pure GB/SB computations
ideal	kStd2 (ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
	generic interface to GB/SB computations, large hilbert vectors
ideal	kStd (ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
	generic interface to GB/SB computations
ideal	kSba (ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw)
ideal	kStdShift (ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
ideal	kMin_std2 (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, bigintmat *hilb, int syzComp, int reduced)
ideal	kMin_std (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
poly	kNF (ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
poly	kNFBound (ideal F, ideal Q, poly p, int bound, int syzComp, int lazyReduce)
ideal	kNF (ideal F, ideal Q, ideal p, int syzComp, int lazyReduce)
ideal	kNFBound (ideal F, ideal Q, ideal p, int bound, int syzComp, int lazyReduce)
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	kInterRedOld (ideal F, const ideal Q)
ideal	kInterRedBba (ideal F, ideal Q, int &need_retry)
ideal	kInterRed (ideal F, const ideal Q)

Variables
VAR BITSET	kOptions
VAR BITSET	validOpts
VAR intvec *	kModW
VAR intvec *	kHomW

Macro Definition Documentation

MORA_USE_BUCKETS

#define MORA_USE_BUCKETS

Definition at line 12 of file kstd1.cc.

PRE_INTEGER_CHECK

#define PRE_INTEGER_CHECK   0

Definition at line 14 of file kstd1.cc.

Function Documentation

doRed()

int doRed ( LObject * h, TObject * with, BOOLEAN intoT, kStrategy strat, bool redMoraNF )

static

Definition at line 118 of file kstd1.cc.

{
  int ret;
#if KDEBUG > 0
  kTest_L(h);
  kTest_T(with);
#endif
  // Hmmm ... why do we do this -- polys from T should already be normalized
  if (!TEST_OPT_INTSTRATEGY)
    with->pNorm();
#ifdef KDEBUG
  if (TEST_OPT_DEBUG)
  {
    PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
  }
#endif
  if (intoT)
  {
    // need to do it exactly like this: otherwise
    // we might get errors
    LObject L= *h;
    L.Copy();
    h->GetP();
    h->length=h->pLength=pLength(h->p);
    ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, NULL, strat);
    if (ret)
    {
      if (ret < 0) return ret;
      if (h->tailRing != strat->tailRing)
        h->ShallowCopyDelete(strat->tailRing,
                             pGetShallowCopyDeleteProc(h->tailRing,
                                                       strat->tailRing));
    }
    if(redMoraNF && (rField_is_Ring(currRing)))
      enterT_strong(h,strat);
    else
      enterT(h,strat);
    *h = L;
  }
  else
    ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, NULL, strat);
#ifdef KDEBUG
  if (TEST_OPT_DEBUG)
  {
    PrintS("to ");h->wrp();PrintLn();
  }
#endif
  return ret;
}

enterSMora()

void enterSMora	(	LObject *	p,
		int	atS,
		kStrategy	strat,
		int	atR )

Definition at line 1629 of file kstd1.cc.

{
  enterSBba(p, atS, strat, atR);
  #ifdef KDEBUG
  if (TEST_OPT_DEBUG)
  {
    Print("new s%d:",atS);
    p_wrp(p->p,currRing,strat->tailRing);
    PrintLn();
  }
  #endif
  HEckeTest(p->p,strat);
  if (strat->kAllAxis)
  {
    if (newHEdge(strat))
    {
      firstUpdate(strat);
      if (TEST_OPT_FINDET)
        return;
 
      /*- cuts elements in L above noether and reorders L -*/
      updateLHC(strat);
      /*- reorders L with respect to posInL -*/
      reorderL(strat);
    }
  }
  else if ((strat->kNoether==NULL)
  && (TEST_OPT_FASTHC))
  {
    if (strat->posInLOldFlag)
    {
      missingAxis(&strat->lastAxis,strat);
      if (strat->lastAxis)
      {
        strat->posInLOld = strat->posInL;
        strat->posInLOldFlag = FALSE;
        strat->posInL = posInL10;
        strat->posInLDependsOnLength = TRUE;
        updateL(FALSE,strat);
        reorderL(strat);
      }
    }
    else if (strat->lastAxis)
      updateL(TRUE,strat);
  }
}

enterSMoraNF()

void enterSMoraNF	(	LObject *	p,
		int	atS,
		kStrategy	strat,
		int	atR )

Definition at line 1682 of file kstd1.cc.

{
  enterSBba(p, atS, strat, atR);
  if ((!strat->kAllAxis) || (strat->kNoether!=NULL)) HEckeTest(p->p,strat);
  if (strat->kAllAxis)
    newHEdge(strat);
}

firstUpdate()

void firstUpdate ( kStrategy strat )

static

Definition at line 1566 of file kstd1.cc.

{
  if (strat->update)
  {
    kTest_TS(strat);
    strat->update = (strat->tl == -1);
    if (TEST_OPT_WEIGHTM)
    {
      pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
      if (strat->tailRing != currRing)
      {
        strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
        strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
      }
      int i;
      for (i=strat->Ll; i>=0; i--)
      {
        strat->L[i].SetpFDeg();
      }
      for (i=strat->tl; i>=0; i--)
      {
        strat->T[i].SetpFDeg();
      }
      if (ecartWeights)
      {
        omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
        ecartWeights=NULL;
      }
    }
    if (TEST_OPT_FASTHC)
    {
      strat->posInL = strat->posInLOld;
      strat->lastAxis = 0;
    }
    if (TEST_OPT_FINDET)
      return;
 
    strat->use_buckets = kMoraUseBucket(strat);
    updateT(strat);
 
    if ( (!rField_is_Ring(currRing)) || (rHasGlobalOrdering(currRing)))
    {
      strat->posInT = posInT2;
      reorderT(strat);
    }
  }
  kTest_TS(strat);
}

hasPurePower() [1/2]

BOOLEAN hasPurePower ( const poly p, int last, int * length, kStrategy strat )

static

Definition at line 1312 of file kstd1.cc.

{
  poly h;
  int i;
 
  if (pNext(p) == strat->tail)
    return FALSE;
  pp_Test(p, currRing, strat->tailRing);
  if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
  {
    i = p_IsPurePower(p, currRing);
    if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
    if (i == last)
    {
      *length = 0;
      return TRUE;
    }
    *length = 1;
    h = pNext(p);
    while (h != NULL)
    {
      i = p_IsPurePower(h, strat->tailRing);
      if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
      if (i==last) return TRUE;
      (*length)++;
      pIter(h);
    }
  }
  return FALSE;
}

hasPurePower() [2/2]

BOOLEAN hasPurePower ( LObject * L, int last, int * length, kStrategy strat )

static

Definition at line 1343 of file kstd1.cc.

{
  if (L->bucket != NULL)
  {
    poly p = L->GetP();
    return hasPurePower(p, last, length, strat);
  }
  else
  {
    return hasPurePower(L->p, last, length, strat);
  }
}

initBba()

void initBba

(

kStrategy

strat

)

Definition at line 1690 of file kstd1.cc.

{
 /* setting global variables ------------------- */
  strat->enterS = enterSBba;
  strat->red = redHoney;
  if (strat->honey)
    strat->red = redHoney;
  else if (currRing->pLexOrder && !strat->homog)
    strat->red = redLazy;
  else
  {
    strat->LazyPass *=4;
    strat->red = redHomog;
  }
  if (rField_is_Ring(currRing))
  {
    if (rField_is_Z(currRing))
      strat->red = redRing_Z;
    else
      strat->red = redRing;
  }
  if (TEST_OPT_IDLIFT
  && (!rIsNCRing(currRing))
  && (!rField_is_Ring(currRing)))
    strat->red=redLiftstd;
  if (currRing->pLexOrder && strat->honey)
    strat->initEcart = initEcartNormal;
  else
    strat->initEcart = initEcartBBA;
  if (strat->honey)
    strat->initEcartPair = initEcartPairMora;
  else
    strat->initEcartPair = initEcartPairBba;
//  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
//  {
//    //interred  machen   Aenderung
//    strat->pOrigFDeg=pFDeg;
//    strat->pOrigLDeg=pLDeg;
//    //h=ggetid("ecart");
//    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
//    //{
//    //  ecartWeights=iv2array(IDINTVEC(h));
//    //}
//    //else
//    {
//      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
//      /*uses automatic computation of the ecartWeights to set them*/
//      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
//    }
//    pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
//    if (TEST_OPT_PROT)
//    {
//      for(i=1; i<=(currRing->N); i++)
//        Print(" %d",ecartWeights[i]);
//      PrintLn();
//      mflush();
//    }
//  }
}

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);
}

initSba()

void initSba	(	ideal	F,
		kStrategy	strat )

Definition at line 1750 of file kstd1.cc.

{
  int i;
  //idhdl h;
 /* setting global variables ------------------- */
  strat->enterS = enterSSba;
  strat->red2 = redHoney;
  if (strat->honey)
    strat->red2 = redHoney;
  else if (currRing->pLexOrder && !strat->homog)
    strat->red2 = redLazy;
  else
  {
    strat->LazyPass *=4;
    strat->red2 = redHomog;
  }
  if (rField_is_Ring(currRing))
  {
    if(rHasLocalOrMixedOrdering(currRing))
      {strat->red2 = redRiloc;}
    else
      {strat->red2 = redRing;}
  }
  if (currRing->pLexOrder && strat->honey)
    strat->initEcart = initEcartNormal;
  else
    strat->initEcart = initEcartBBA;
  if (strat->honey)
    strat->initEcartPair = initEcartPairMora;
  else
    strat->initEcartPair = initEcartPairBba;
  //strat->kIdeal = NULL;
  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
  //else              strat->kIdeal->rtyp=MODUL_CMD;
  //strat->kIdeal->data=(void *)strat->Shdl;
  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
  {
    //interred  machen   Aenderung
    strat->pOrigFDeg  = currRing->pFDeg;
    strat->pOrigLDeg  = currRing->pLDeg;
    //h=ggetid("ecart");
    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
    //{
    //  ecartWeights=iv2array(IDINTVEC(h));
    //}
    //else
    {
      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
      /*uses automatic computation of the ecartWeights to set them*/
      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights, currRing);
    }
    pRestoreDegProcs(currRing, totaldegreeWecart, maxdegreeWecart);
    if (TEST_OPT_PROT)
    {
      for(i=1; i<=(currRing->N); i++)
        Print(" %d",ecartWeights[i]);
      PrintLn();
      mflush();
    }
  }
  // for sig-safe reductions in signature-based
  // standard basis computations
  if(rField_is_Ring(currRing))
    strat->red = redSigRing;
  else
    strat->red        = redSig;
  //strat->sbaOrder  = 1;
  strat->currIdx      = 1;
}

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;
}

kDebugPrint()

void kDebugPrint

(

kStrategy

strat

)

Definition at line 11478 of file kutil.cc.

{
  printf("red: ");
    if (strat->red==redFirst) printf("redFirst\n");
    else if (strat->red==redHoney) printf("redHoney\n");
    else if (strat->red==redEcart) printf("redEcart\n");
    else if (strat->red==redHomog) printf("redHomog\n");
    else if (strat->red==redLazy) printf("redLazy\n");
    else if (strat->red==redLiftstd) printf("redLiftstd\n");
    else  printf("%p\n",(void*)strat->red);
  printf("posInT: ");
    if (strat->posInT==posInT0) printf("posInT0\n");
    else if (strat->posInT==posInT1) printf("posInT1\n");
    else if (strat->posInT==posInT11) printf("posInT11\n");
    else if (strat->posInT==posInT110) printf("posInT110\n");
    else if (strat->posInT==posInT13) printf("posInT13\n");
    else if (strat->posInT==posInT15) printf("posInT15\n");
    else if (strat->posInT==posInT17) printf("posInT17\n");
    else if (strat->posInT==posInT17_c) printf("posInT17_c\n");
    else if (strat->posInT==posInT19) printf("posInT19\n");
    else if (strat->posInT==posInT2) printf("posInT2\n");
    else if (strat->posInT==posInT11Ring) printf("posInT11Ring\n");
    else if (strat->posInT==posInT110Ring) printf("posInT110Ring\n");
    else if (strat->posInT==posInT15Ring) printf("posInT15Ring\n");
    else if (strat->posInT==posInT17Ring) printf("posInT17Ring\n");
    else if (strat->posInT==posInT17_cRing) printf("posInT17_cRing\n");
#ifdef HAVE_MORE_POS_IN_T
    else if (strat->posInT==posInT_EcartFDegpLength) printf("posInT_EcartFDegpLength\n");
    else if (strat->posInT==posInT_FDegpLength) printf("posInT_FDegpLength\n");
    else if (strat->posInT==posInT_pLength) printf("posInT_pLength\n");
#endif
    else if (strat->posInT==posInT_EcartpLength) printf("posInT_EcartpLength\n");
    else  printf("%p\n",(void*)strat->posInT);
  printf("posInL: ");
    if (strat->posInL==posInL0) printf("posInL0\n");
    else if (strat->posInL==posInL10) printf("posInL10\n");
    else if (strat->posInL==posInL11) printf("posInL11\n");
    else if (strat->posInL==posInL110) printf("posInL110\n");
    else if (strat->posInL==posInL13) printf("posInL13\n");
    else if (strat->posInL==posInL15) printf("posInL15\n");
    else if (strat->posInL==posInL17) printf("posInL17\n");
    else if (strat->posInL==posInL17_c) printf("posInL17_c\n");
    else if (strat->posInL==posInL0) printf("posInL0Ring\n");
    else if (strat->posInL==posInL11Ring) printf("posInL11Ring\n");
    else if (strat->posInL==posInL11Ringls) printf("posInL11Ringls\n");
    else if (strat->posInL==posInL110Ring) printf("posInL110Ring\n");
    else if (strat->posInL==posInL15Ring) printf("posInL15Ring\n");
    else if (strat->posInL==posInL17Ring) printf("posInL17Ring\n");
    else if (strat->posInL==posInL17_cRing) printf("posInL17_cRing\n");
    else if (strat->posInL==posInLSpecial) printf("posInLSpecial\n");
    else  printf("%p\n",(void*)strat->posInL);
  printf("enterS: ");
    if (strat->enterS==enterSBba) printf("enterSBba\n");
    else if (strat->enterS==enterSMora) printf("enterSMora\n");
    else if (strat->enterS==enterSMoraNF) printf("enterSMoraNF\n");
    else  printf("%p\n",(void*)strat->enterS);
  printf("initEcart: ");
    if (strat->initEcart==initEcartBBA) printf("initEcartBBA\n");
    else if (strat->initEcart==initEcartNormal) printf("initEcartNormal\n");
    else  printf("%p\n",(void*)strat->initEcart);
  printf("initEcartPair: ");
    if (strat->initEcartPair==initEcartPairBba) printf("initEcartPairBba\n");
    else if (strat->initEcartPair==initEcartPairMora) printf("initEcartPairMora\n");
    else  printf("%p\n",(void*)strat->initEcartPair);
  printf("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
    strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
  printf("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
    strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
  printf("chainCrit: ");
    if (strat->chainCrit==chainCritNormal) printf("chainCritNormal\n");
    else if (strat->chainCrit==chainCritOpt_1) printf("chainCritOpt_1\n");
    else  printf("%p\n",(void*)strat->chainCrit);
  printf("posInLDependsOnLength=%d\n",
         strat->posInLDependsOnLength);
  printf("%s\n",showOption());
  printf("LDeg: ");
    if (currRing->pLDeg==pLDeg0) printf("pLDeg0");
    else if (currRing->pLDeg==pLDeg0c) printf("pLDeg0c");
    else if (currRing->pLDeg==pLDegb) printf("pLDegb");
    else if (currRing->pLDeg==pLDeg1) printf("pLDeg1");
    else if (currRing->pLDeg==pLDeg1c) printf("pLDeg1c");
    else if (currRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
    else if (currRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
    else if (currRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
    else if (currRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
    else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
    else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
    else if (currRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
    else printf("? (%lx)", (long)currRing->pLDeg);
    printf(" / ");
    if (strat->tailRing->pLDeg==pLDeg0) printf("pLDeg0");
    else if (strat->tailRing->pLDeg==pLDeg0c) printf("pLDeg0c");
    else if (strat->tailRing->pLDeg==pLDegb) printf("pLDegb");
    else if (strat->tailRing->pLDeg==pLDeg1) printf("pLDeg1");
    else if (strat->tailRing->pLDeg==pLDeg1c) printf("pLDeg1c");
    else if (strat->tailRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
    else if (strat->tailRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
    else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
    else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
    else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
    else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
    else if (strat->tailRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
    else printf("? (%lx)", (long)strat->tailRing->pLDeg);
    printf("\n");
  printf("currRing->pFDeg: ");
    if (currRing->pFDeg==p_Totaldegree) printf("p_Totaldegree");
    else if (currRing->pFDeg==p_WFirstTotalDegree) printf("pWFirstTotalDegree");
    else if (currRing->pFDeg==p_Deg) printf("p_Deg");
    else if (currRing->pFDeg==kHomModDeg) printf("kHomModDeg");
    else if (currRing->pFDeg==kModDeg) printf("kModDeg");
    else if (currRing->pFDeg==totaldegreeWecart) printf("totaldegreeWecart");
    else if (currRing->pFDeg==p_WTotaldegree) printf("p_WTotaldegree");
    else printf("? (%lx)", (long)currRing->pFDeg);
    printf("\n");
    printf(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
    if(TEST_OPT_DEGBOUND)
      printf(" degBound: %d\n", Kstd1_deg);
 
    if( ecartWeights != NULL )
    {
       printf("ecartWeights: ");
       for (int i = rVar(currRing); i > 0; i--)
         printf("%hd ", ecartWeights[i]);
       printf("\n");
       assume( TEST_OPT_WEIGHTM );
    }
 
#ifndef SING_NDEBUG
    rDebugPrint(currRing);
#endif
}

kHomModDeg()

long kHomModDeg	(	poly	p,
		const ring	r )

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 )

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 )

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,
		int	reduced )

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,
		int	reduced )

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 )

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;
}

kMoraUseBucket()

BOOLEAN kMoraUseBucket ( kStrategy strat )

static

Definition at line 3879 of file kstd1.cc.

{
#ifdef MORA_USE_BUCKETS
  if (TEST_OPT_NOT_BUCKETS)
    return FALSE;
  if ((strat->red == redFirst)
  ||((strat->red == redEcart)&&(strat->kNoether!=NULL)))
  {
#ifdef NO_LDEG
    if (strat->syzComp==0)
      return TRUE;
#else
    if ((strat->homog || strat->honey) && (strat->syzComp==0))
      return TRUE;
#endif
  }
  else
  {
    assume(strat->red == redEcart || strat->red == redRiloc || strat->red == redRiloc_Z);
    if (strat->honey && (strat->syzComp==0))
      return TRUE;
  }
#endif
  return FALSE;
}

kNF() [1/2]

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

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,
		int	lazyReduce )

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,
		int	lazyReduce )

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,
		int	lazyReduce )

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;
}

kOptimizeLDeg()

void kOptimizeLDeg ( pLDegProc ldeg, kStrategy strat )

static

Definition at line 100 of file kstd1.cc.

{
//  if (strat->ak == 0 && !rIsSyzIndexRing(currRing))
    strat->length_pLength = TRUE;
//  else
//    strat->length_pLength = FALSE;
 
  if ((ldeg == pLDeg0c /*&& !rIsSyzIndexRing(currRing)*/) ||
      (ldeg == pLDeg0 && strat->ak == 0))
  {
    strat->LDegLast = TRUE;
  }
  else
  {
    strat->LDegLast = FALSE;
  }
}

kSba()

ideal kSba	(	ideal	F,
		ideal	Q,
		tHomog	h,
		intvec **	w,
		int	sbaOrder,
		int	arri,
		bigintmat *	hilb,
		int	syzComp,
		int	newIdeal,
		intvec *	vw )

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 **	w,
		intvec *	hilb,
		int	syzComp,
		int	newIdeal,
		intvec *	vw,
		s_poly_proc_t	sp )

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 **	w,
		bigintmat *	hilb,
		int	syzComp,
		int	newIdeal,
		intvec *	vw,
		s_poly_proc_t	sp )

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,
		int	syzComp,
		int	newIdeal,
		intvec *	vw,
		s_poly_proc_t	sp )

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 **	w,
		bigintmat *	hilb,
		int	syzComp,
		int	newIdeal,
		intvec *	vw,
		BOOLEAN	rightGB )

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;
}

missingAxis()

void missingAxis ( int * last, kStrategy strat )

static

Definition at line 1279 of file kstd1.cc.

{
  int   i = 0;
  int   k = 0;
 
  *last = 0;
  if (!rHasMixedOrdering(currRing))
  {
    loop
    {
      i++;
      if (i > (currRing->N)) break;
      if (strat->NotUsedAxis[i])
      {
        *last = i;
        k++;
      }
      if (k>1)
      {
        *last = 0;
        break;
      }
    }
  }
}

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);
}

posInL10()

int posInL10	(	const LSet	set,
		const int	length,
		LObject *	p,
		const kStrategy	strat )

Definition at line 1360 of file kstd1.cc.

{
  int j,dp,dL;
 
  if (length<0) return 0;
  if (hasPurePower(p,strat->lastAxis,&dp,strat))
  {
    int op= p->GetpFDeg() +p->ecart;
    for (j=length; j>=0; j--)
    {
      if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
        return j+1;
      if (dp < dL)
        return j+1;
      if ((dp == dL)
          && (set[j].GetpFDeg()+set[j].ecart >= op))
        return j+1;
    }
  }
  j=length;
  loop
  {
    if (j<0) break;
    if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
    j--;
  }
  return strat->posInLOld(set,j,p,strat);
}

redEcart()

int redEcart	(	LObject *	h,
		kStrategy	strat )

Definition at line 168 of file kstd1.cc.

{
  int i,at,ei,li,ii;
  int j = 0;
  int pass = 0;
  long d,reddeg;
 
  d = h->GetpFDeg()+ h->ecart;
  reddeg = strat->LazyDegree+d;
  h->SetShortExpVector();
  loop
  {
    j = kFindDivisibleByInT(strat, h);
    if (j < 0)
    {
      if (strat->honey) h->SetLength(strat->length_pLength);
      return 1;
    }
 
    ei = strat->T[j].ecart;
    ii = j;
 
    if (ei > h->ecart)
    {
      unsigned long not_sev=~h->sev;
      poly h_t= h->GetLmTailRing();
      li = strat->T[j].length;
      if (li<=0) li=strat->T[j].GetpLength();
      // the polynomial to reduce with (up to the moment) is;
      // pi with ecart ei and length li
      // look for one with smaller ecart
      i = j;
      loop
      {
        /*- takes the first possible with respect to ecart -*/
        i++;
        if (i > strat->tl) break;
#if 1
        if (strat->T[i].length<=0) strat->T[i].GetpLength();
        if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
                                        strat->T[i].length < li))
            &&
            p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h_t, not_sev, strat->tailRing))
#else
          j = kFindDivisibleByInT(strat, h, i);
        if (j < 0) break;
        i = j;
        if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
                                        strat->T[i].length < li))
#endif
        {
          // the polynomial to reduce with is now
          ii = i;
          ei = strat->T[i].ecart;
          if (ei <= h->ecart) break;
          li = strat->T[i].length;
        }
      }
    }
 
    // end of search: have to reduce with pi
    if ((ei > h->ecart)&&(strat->kNoether==NULL))
    {
      // It is not possible to reduce h with smaller ecart;
      // if possible h goes to the lazy-set L,i.e
      // if its position in L would be not the last one
      strat->fromT = TRUE;
      if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
      {
        h->SetLmCurrRing();
        if (strat->honey && strat->posInLDependsOnLength)
          h->SetLength(strat->length_pLength);
        assume(h->FDeg == h->pFDeg());
        at = strat->posInL(strat->L,strat->Ll,h,strat);
        if (at <= strat->Ll)
        {
          /*- h will not become the next element to reduce -*/
          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
          if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
#endif
          h->Clear();
          strat->fromT = FALSE;
          return -1;
        }
      }
    }
 
    // now we finally can reduce
    doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
    strat->fromT=FALSE;
 
    // are we done ???
    if (h->IsNull())
    {
      assume(!rField_is_Ring(currRing));
      kDeleteLcm(h);
      h->Clear();
      return 0;
    }
    if (TEST_OPT_IDLIFT)
    {
      if (h->p!=NULL)
      {
        if(p_GetComp(h->p,currRing)>strat->syzComp)
        {
          h->Delete();
          return 0;
        }
      }
      else // if (h->t_p!=NULL)
      {
        if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
        {
          h->Delete();
          return 0;
        }
      }
    }
    #if 0
    else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
    {
      if (h->p!=NULL)
      {
        if(p_GetComp(h->p,currRing)>strat->syzComp)
        {
          return 1;
        }
      }
      else // if (h->t_p!=NULL)
      {
        if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
        {
          return 1;
        }
      }
    }
    #endif
 
    // done ? NO!
    h->SetShortExpVector();
    h->SetpFDeg();
    if (strat->honey)
    {
      if (ei <= h->ecart)
        h->ecart = d-h->GetpFDeg();
      else
        h->ecart = d-h->GetpFDeg()+ei-h->ecart;
    }
    else
      // this has the side effect of setting h->length
      h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
#if 0
    if (strat->syzComp!=0)
    {
      if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
      {
        assume(h->MinComp() > strat->syzComp);
        if (strat->honey) h->SetLength();
#ifdef KDEBUG
        if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
#endif
        return -2;
      }
    }
#endif
    /*- try to reduce the s-polynomial -*/
    pass++;
    d = h->GetpFDeg()+h->ecart;
    /*
     *test whether the polynomial should go to the lazyset L
     *-if the degree jumps
     *-if the number of pre-defined reductions jumps
     */
    if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
        && ((d >= reddeg) || (pass > strat->LazyPass)))
    {
      h->SetLmCurrRing();
      if (strat->honey && strat->posInLDependsOnLength)
        h->SetLength(strat->length_pLength);
      assume(h->FDeg == h->pFDeg());
      at = strat->posInL(strat->L,strat->Ll,h,strat);
      if (at <= strat->Ll)
      {
        int dummy=strat->sl;
        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
        {
          if (strat->honey && !strat->posInLDependsOnLength)
            h->SetLength(strat->length_pLength);
          return 1;
        }
        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
        if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
#endif
        h->Clear();
        return -1;
      }
    }
    else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
    {
      Print(".%ld",d);mflush();
      reddeg = d+1;
      if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
      {
        strat->overflow=TRUE;
        //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
        h->GetP();
        at = strat->posInL(strat->L,strat->Ll,h,strat);
        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
        h->Clear();
        return -1;
      }
    }
  }
}

redFirst()

int redFirst	(	LObject *	h,
		kStrategy	strat )

Definition at line 794 of file kstd1.cc.

{
  if (strat->tl<0) return 1;
  if (h->IsNull()) return 0;
 
  int at;
  long reddeg,d;
  int pass = 0;
  int cnt = RED_CANONICALIZE;
  int j = 0;
 
  reddeg = d = h->GetpFDeg();
  if (! strat->homog)
  {
    d += h->ecart;
    reddeg = strat->LazyDegree+d;
  }
  h->SetShortExpVector();
  loop
  {
    j = kFindDivisibleByInT(strat, h);
    if (j < 0)
    {
      h->SetDegStuffReturnLDeg(strat->LDegLast);
      return 1;
    }
 
    if (!TEST_OPT_INTSTRATEGY)
      strat->T[j].pNorm();
#ifdef KDEBUG
    if (TEST_OPT_DEBUG)
    {
      PrintS("reduce ");
      h->wrp();
      PrintS(" with ");
      strat->T[j].wrp();
    }
#endif
    ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
#ifdef KDEBUG
    if (TEST_OPT_DEBUG)
    {
      PrintS(" to ");
      wrp(h->p);
      PrintLn();
    }
#endif
    if (h->IsNull())
    {
      assume(!rField_is_Ring(currRing));
      kDeleteLcm(h);
      h->Clear();
      return 0;
    }
    if (TEST_OPT_IDLIFT)
    {
      if (h->p!=NULL)
      {
        if(p_GetComp(h->p,currRing)>strat->syzComp)
        {
          h->Delete();
          return 0;
        }
      }
      else // if (h->t_p!=NULL)
      {
        if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
        {
          h->Delete();
          return 0;
        }
      }
    }
    #if 0
    else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
    {
      if (h->p!=NULL)
      {
        if(p_GetComp(h->p,currRing)>strat->syzComp)
        {
          return 1;
        }
      }
      else // if (h->t_p!=NULL)
      {
        if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
        {
          return 1;
        }
      }
    }
    #endif
    h->SetShortExpVector();
 
#if 0
    if ((strat->syzComp!=0) && !strat->honey)
    {
      if ((strat->syzComp>0) &&
          (h->Comp() > strat->syzComp))
      {
        assume(h->MinComp() > strat->syzComp);
#ifdef KDEBUG
        if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
#endif
        if (strat->homog)
          h->SetDegStuffReturnLDeg(strat->LDegLast);
        return -2;
      }
    }
#endif
    if (!strat->homog)
    {
      if (!TEST_OPT_OLDSTD && strat->honey)
      {
        h->SetpFDeg();
        if (strat->T[j].ecart <= h->ecart)
          h->ecart = d - h->GetpFDeg();
        else
          h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
 
        d = h->GetpFDeg() + h->ecart;
      }
      else
        d = h->SetDegStuffReturnLDeg(strat->LDegLast);
      /*- try to reduce the s-polynomial -*/
      cnt--;
      pass++;
      /*
       *test whether the polynomial should go to the lazyset L
       *-if the degree jumps
       *-if the number of pre-defined reductions jumps
       */
      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
          && ((d >= reddeg) || (pass > strat->LazyPass)))
      {
        h->SetLmCurrRing();
        if (strat->posInLDependsOnLength)
          h->SetLength(strat->length_pLength);
        at = strat->posInL(strat->L,strat->Ll,h,strat);
        if (at <= strat->Ll)
        {
          int dummy=strat->sl;
          if (kFindDivisibleByInS(strat,&dummy, h) < 0)
            return 1;
          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
          if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
#endif
          h->Clear();
          return -1;
        }
      }
      if (UNLIKELY(cnt==0))
      {
        h->CanonicalizeP();
        cnt=RED_CANONICALIZE;
        //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
      }
      if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
      {
        reddeg = d+1;
        Print(".%ld",d);mflush();
        if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
        {
          strat->overflow=TRUE;
          //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
          h->GetP();
          at = strat->posInL(strat->L,strat->Ll,h,strat);
          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
          h->Clear();
          return -1;
        }
      }
    }
  }
}

redMoraNF()

poly redMoraNF ( poly h, kStrategy strat, int flag )

static

Definition at line 976 of file kstd1.cc.

{
  LObject H;
  H.p = h;
  int j = 0;
  int z = 10;
  int o = H.SetpFDeg();
  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
  if ((flag & (KSTD_NF_ECART|KSTD_NF_CANCELUNIT)) == KSTD_NF_CANCELUNIT) cancelunit(&H,TRUE);
  H.sev = pGetShortExpVector(H.p);
  loop
  {
    if (j > strat->tl)
    {
      return H.p;
    }
    if (TEST_V_DEG_STOP)
    {
      if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
      if (H.p==NULL) return NULL;
    }
    unsigned long not_sev = ~ H.sev;
    if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
        )
    {
      /*- remember the found T-poly -*/
      // poly pi = strat->T[j].p;
      int ei = strat->T[j].ecart;
      int li = strat->T[j].length;
      int ii = j;
      /*
      * the polynomial to reduce with (up to the moment) is;
      * pi with ecart ei and length li
      */
      loop
      {
        /*- look for a better one with respect to ecart -*/
        /*- stop, if the ecart is small enough (<=ecart(H)) -*/
        j++;
        if (j > strat->tl) break;
        if (ei <= H.ecart) break;
        if (((strat->T[j].ecart < ei)
          || ((strat->T[j].ecart == ei)
        && (strat->T[j].length < li)))
        && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
        )
        {
          /*
          * the polynomial to reduce with is now;
          */
          // pi = strat->T[j].p;
          ei = strat->T[j].ecart;
          li = strat->T[j].length;
          ii = j;
        }
      }
      /*
      * end of search: have to reduce with pi
      */
      z++;
      if (z>10)
      {
        pNormalize(H.p);
        z=0;
      }
      if ((ei > H.ecart) && (strat->kNoether==NULL))
      {
        /*
        * It is not possible to reduce h with smaller ecart;
        * we have to reduce with bad ecart: H has to enter in T
        */
        LObject L= H;
        L.Copy();
        H.GetP();
        H.length=H.pLength=pLength(H.p);
        ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
                            (flag & KSTD_NF_NONORM)==0);
        enterT(&H,strat);
        H = L;
      }
      else
      {
        /*
        * we reduce with good ecart, h need not to be put to T
        */
        ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
                            (flag & KSTD_NF_NONORM)==0);
      }
      if (H.p == NULL)
        return NULL;
      /*- try to reduce the s-polynomial -*/
      o = H.SetpFDeg();
      if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
      H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
      j = 0;
      H.sev = pGetShortExpVector(H.p);
    }
    else
    {
      j++;
    }
  }
}

redMoraNFRing()

poly redMoraNFRing ( poly h, kStrategy strat, int flag )

static

Definition at line 1080 of file kstd1.cc.

{
    LObject H;
    H.p = h;
    int j0, j = 0;
    int docoeffred  = 0;
    poly T0p    = strat->T[0].p;
    int T0ecart = strat->T[0].ecart;
    int o = H.SetpFDeg();
    H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
    if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
    H.sev = pGetShortExpVector(H.p);
    unsigned long not_sev = ~ H.sev;
    if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2)
    {
        docoeffred  = 1; // euclidean ring required: n_QuotRem
        if (currRing->cf->cfQuotRem==ndQuotRem)
        {
          docoeffred = 0;
        }
    }
    loop
    {
        /* cut down the lead coefficients, only possible if the degree of
         * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
         * we ask for the length of T[0] to be <= 2 */
        if (docoeffred)
        {
            j0 = kTestDivisibleByT0_Z(strat, &H);
            if ((j0 == 0)
            && (n_DivBy(pGetCoeff(H.p), pGetCoeff(T0p), currRing->cf) == FALSE)
            && (T0ecart <= H.ecart))
            {
                /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
                 * => we try to cut down the lead coefficient at least */
                /* first copy T[j0] in order to multiply it with a coefficient later on */
                number mult, rest;
                TObject tj  = strat->T[0];
                tj.Copy();
                /* compute division with remainder of lc(h) and lc(T[j]) */
                mult = n_QuotRem(pGetCoeff(H.p), pGetCoeff(T0p),
                        &rest, currRing->cf);
                /* set corresponding new lead coefficient already. we do not
                 * remove the lead term in ksReducePolyLC, but only apply
                 * a lead coefficient reduction */
                tj.Mult_nn(mult);
                ksReducePolyLC(&H, &tj, NULL, &rest, strat);
                tj.Delete();
                tj.Clear();
            }
        }
        if (j > strat->tl)
        {
            return H.p;
        }
        if (TEST_V_DEG_STOP)
        {
            if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
            if (H.p==NULL) return NULL;
        }
        if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
                && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
           )
        {
            /*- remember the found T-poly -*/
            // poly pi = strat->T[j].p;
            int ei = strat->T[j].ecart;
            int li = strat->T[j].length;
            int ii = j;
            /*
             * the polynomial to reduce with (up to the moment) is;
             * pi with ecart ei and length li
             */
            loop
            {
                /*- look for a better one with respect to ecart -*/
                /*- stop, if the ecart is small enough (<=ecart(H)) -*/
                j++;
                if (j > strat->tl) break;
                if (ei <= H.ecart) break;
                if (((strat->T[j].ecart < ei)
                            || ((strat->T[j].ecart == ei)
                                && (strat->T[j].length < li)))
                        && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
                        && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
                   )
                {
                    /*
                     * the polynomial to reduce with is now;
                     */
                    // pi = strat->T[j].p;
                    ei = strat->T[j].ecart;
                    li = strat->T[j].length;
                    ii = j;
                }
            }
            /*
             * end of search: have to reduce with pi
             */
            if ((ei > H.ecart) && (strat->kNoether==NULL))
            {
                /*
                 * It is not possible to reduce h with smaller ecart;
                 * we have to reduce with bad ecart: H has to enter in T
                 */
              LObject L= H;
              L.Copy();
              H.GetP();
              H.length=H.pLength=pLength(H.p);
              ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
                            (flag & KSTD_NF_NONORM)==0);
              enterT_strong(&H,strat);
              H = L;
            }
            else
            {
                /*
                 * we reduce with good ecart, h need not to be put to T
                 */
                ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
                            (flag & KSTD_NF_NONORM)==0);
            }
            if (H.p == NULL)
              return NULL;
            /*- try to reduce the s-polynomial -*/
            o = H.SetpFDeg();
            if ((flag &2 ) == 0) cancelunit(&H,TRUE);
            H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
            j = 0;
            H.sev = pGetShortExpVector(H.p);
            not_sev = ~ H.sev;
        }
        else
        {
            j++;
        }
    }
}

redRiloc()

int redRiloc	(	LObject *	h,
		kStrategy	strat )

Definition at line 385 of file kstd1.cc.

{
  int i,at,ei,li,ii;
  int j = 0;
  int pass = 0;
  long d,reddeg;
 
  d = h->GetpFDeg()+ h->ecart;
  reddeg = strat->LazyDegree+d;
  h->SetShortExpVector();
  loop
  {
    j = kFindDivisibleByInT(strat, h);
    if (j < 0)
    {
      // over ZZ: cleanup coefficients by complete reduction with monomials
      postReduceByMon(h, strat);
      if(h->p == NULL)
      {
        kDeleteLcm(h);
        h->Clear();
        return 0;
      }
      if (strat->honey) h->SetLength(strat->length_pLength);
      if(strat->tl >= 0)
          h->i_r1 = strat->tl;
      else
          h->i_r1 = -1;
      if (h->GetLmTailRing() == NULL)
      {
        kDeleteLcm(h);
        h->Clear();
        return 0;
      }
      return 1;
    }
 
    ei = strat->T[j].ecart;
    ii = j;
    if (ei > h->ecart && ii < strat->tl)
    {
      li = strat->T[j].length;
      // the polynomial to reduce with (up to the moment) is;
      // pi with ecart ei and length li
      // look for one with smaller ecart
      i = j;
      loop
      {
        /*- takes the first possible with respect to ecart -*/
        i++;
#if 1
        if (i > strat->tl) break;
        if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
                                        strat->T[i].length < li))
            &&
            p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
            &&
            n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
#else
          j = kFindDivisibleByInT(strat, h, i);
        if (j < 0) break;
        i = j;
        if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
                                        strat->T[i].length < li))
#endif
        {
          // the polynomial to reduce with is now
          ii = i;
          ei = strat->T[i].ecart;
          if (ei <= h->ecart) break;
          li = strat->T[i].length;
        }
      }
    }
 
    // end of search: have to reduce with pi
    if (ei > h->ecart)
    {
      // It is not possible to reduce h with smaller ecart;
      // if possible h goes to the lazy-set L,i.e
      // if its position in L would be not the last one
      strat->fromT = TRUE;
      if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
      {
        h->SetLmCurrRing();
        if (strat->honey && strat->posInLDependsOnLength)
          h->SetLength(strat->length_pLength);
        assume(h->FDeg == h->pFDeg());
        at = strat->posInL(strat->L,strat->Ll,h,strat);
        if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
        {
          /*- h will not become the next element to reduce -*/
          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
          #ifdef KDEBUG
          if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
          #endif
          h->Clear();
          strat->fromT = FALSE;
          return -1;
        }
      }
      doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
    }
    else
    {
      // now we finally can reduce
      doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
    }
    strat->fromT=FALSE;
    // are we done ???
    if (h->IsNull())
    {
      kDeleteLcm(h);
      h->Clear();
      return 0;
    }
 
    // NO!
    h->SetShortExpVector();
    h->SetpFDeg();
    if (strat->honey)
    {
      if (ei <= h->ecart)
        h->ecart = d-h->GetpFDeg();
      else
        h->ecart = d-h->GetpFDeg()+ei-h->ecart;
    }
    else
      // this has the side effect of setting h->length
      h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
    /*- try to reduce the s-polynomial -*/
    pass++;
    d = h->GetpFDeg()+h->ecart;
    /*
     *test whether the polynomial should go to the lazyset L
     *-if the degree jumps
     *-if the number of pre-defined reductions jumps
     */
    if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
        && ((d >= reddeg) || (pass > strat->LazyPass)))
    {
      h->SetLmCurrRing();
      if (strat->honey && strat->posInLDependsOnLength)
        h->SetLength(strat->length_pLength);
      assume(h->FDeg == h->pFDeg());
      at = strat->posInL(strat->L,strat->Ll,h,strat);
      if (at <= strat->Ll)
      {
        int dummy=strat->sl;
        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
        {
          if (strat->honey && !strat->posInLDependsOnLength)
            h->SetLength(strat->length_pLength);
          return 1;
        }
        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
        if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
#endif
        h->Clear();
        return -1;
      }
    }
    else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
    {
      Print(".%ld",d);mflush();
      reddeg = d+1;
      if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
      {
        strat->overflow=TRUE;
        //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
        h->GetP();
        at = strat->posInL(strat->L,strat->Ll,h,strat);
        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
        h->Clear();
        return -1;
      }
    }
  }
}

redRiloc_Z()

int redRiloc_Z	(	LObject *	h,
		kStrategy	strat )

Definition at line 566 of file kstd1.cc.

{
    int i,at,ei,li,ii;
    int j = 0;
    int pass = 0;
    long d,reddeg;
    int docoeffred  = 0;
    poly T0p        = strat->T[0].p;
    int T0ecart     = strat->T[0].ecart;
 
 
    d = h->GetpFDeg()+ h->ecart;
    reddeg = strat->LazyDegree+d;
    h->SetShortExpVector();
    if ((strat->tl>=0)
    &&strat->T[0].GetpFDeg() == 0
    && strat->T[0].length <= 2)
    {
        docoeffred  = 1;
    }
    loop
    {
        /* cut down the lead coefficients, only possible if the degree of
         * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
         * we ask for the length of T[0] to be <= 2 */
        if (docoeffred)
        {
            j = kTestDivisibleByT0_Z(strat, h);
            if (j == 0 && n_DivBy(pGetCoeff(h->p), pGetCoeff(T0p), currRing->cf) == FALSE
                    && T0ecart <= h->ecart)
            {
                /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
                 * => we try to cut down the lead coefficient at least */
                /* first copy T[j] in order to multiply it with a coefficient later on */
                number mult, rest;
                TObject tj  = strat->T[0];
                tj.Copy();
                /* compute division with remainder of lc(h) and lc(T[j]) */
                mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(T0p),
                        &rest, currRing->cf);
                /* set corresponding new lead coefficient already. we do not
                 * remove the lead term in ksReducePolyLC, but only apply
                 * a lead coefficient reduction */
                tj.Mult_nn(mult);
                ksReducePolyLC(h, &tj, NULL, &rest, strat);
                tj.Delete();
                tj.Clear();
                if (n_IsZero(pGetCoeff(h->GetP()),currRing->cf))
                {
                  h->LmDeleteAndIter();
                }
            }
        }
        j = kFindDivisibleByInT(strat, h);
        if (j < 0)
        {
            // over ZZ: cleanup coefficients by complete reduction with monomials
            postReduceByMon(h, strat);
            if(h->p == NULL)
            {
                kDeleteLcm(h);
                h->Clear();
                return 0;
            }
            if (strat->honey) h->SetLength(strat->length_pLength);
            if(strat->tl >= 0)
                h->i_r1 = strat->tl;
            else
                h->i_r1 = -1;
            if (h->GetLmTailRing() == NULL)
            {
                kDeleteLcm(h);
                h->Clear();
                return 0;
            }
            return 1;
        }
 
        ei = strat->T[j].ecart;
        ii = j;
#if 1
        if (ei > h->ecart && ii < strat->tl)
        {
            li = strat->T[j].length;
            // the polynomial to reduce with (up to the moment) is;
            // pi with ecart ei and length li
            // look for one with smaller ecart
            i = j;
            loop
            {
                /*- takes the first possible with respect to ecart -*/
                i++;
#if 1
                if (i > strat->tl) break;
                if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
                                strat->T[i].length < li))
                        &&
                        p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
                        &&
                        n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
#else
                    j = kFindDivisibleByInT(strat, h, i);
                if (j < 0) break;
                i = j;
                if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
                            strat->T[i].length < li))
#endif
                {
                    // the polynomial to reduce with is now
                    ii = i;
                    ei = strat->T[i].ecart;
                    if (ei <= h->ecart) break;
                    li = strat->T[i].length;
                }
            }
        }
#endif
 
        // end of search: have to reduce with pi
        if (ei > h->ecart)
        {
            // It is not possible to reduce h with smaller ecart;
            // if possible h goes to the lazy-set L,i.e
            // if its position in L would be not the last one
            strat->fromT = TRUE;
            if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
            {
                h->SetLmCurrRing();
                if (strat->honey && strat->posInLDependsOnLength)
                    h->SetLength(strat->length_pLength);
                assume(h->FDeg == h->pFDeg());
                at = strat->posInL(strat->L,strat->Ll,h,strat);
                if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
                {
                    /*- h will not become the next element to reduce -*/
                    enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
                    if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
#endif
                    h->Clear();
                    strat->fromT = FALSE;
                    return -1;
                }
            }
            doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
        }
        else
        {
            // now we finally can reduce
            doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
        }
        strat->fromT=FALSE;
        // are we done ???
        if (h->IsNull())
        {
            kDeleteLcm(h);
            h->Clear();
            return 0;
        }
 
        // NO!
        h->SetShortExpVector();
        h->SetpFDeg();
        if (strat->honey)
        {
            if (ei <= h->ecart)
                h->ecart = d-h->GetpFDeg();
            else
                h->ecart = d-h->GetpFDeg()+ei-h->ecart;
        }
        else
            // this has the side effect of setting h->length
            h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
        /*- try to reduce the s-polynomial -*/
        pass++;
        d = h->GetpFDeg()+h->ecart;
        /*
         *test whether the polynomial should go to the lazyset L
         *-if the degree jumps
         *-if the number of pre-defined reductions jumps
         */
        if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
                && ((d >= reddeg) || (pass > strat->LazyPass)))
        {
            h->SetLmCurrRing();
            if (strat->honey && strat->posInLDependsOnLength)
                h->SetLength(strat->length_pLength);
            assume(h->FDeg == h->pFDeg());
            at = strat->posInL(strat->L,strat->Ll,h,strat);
            if (at <= strat->Ll)
            {
                int dummy=strat->sl;
                if (kFindDivisibleByInS(strat, &dummy, h) < 0)
                {
                    if (strat->honey && !strat->posInLDependsOnLength)
                        h->SetLength(strat->length_pLength);
                    return 1;
                }
                enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
                if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
#endif
                h->Clear();
                return -1;
            }
        }
        else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
        {
            Print(".%ld",d);mflush();
            reddeg = d+1;
            if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
            {
                strat->overflow=TRUE;
                //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
                h->GetP();
                at = strat->posInL(strat->L,strat->Ll,h,strat);
                enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
                h->Clear();
                return -1;
            }
        }
    }
}

reorderL()

void reorderL ( kStrategy strat )

static

Definition at line 1222 of file kstd1.cc.

{
  int i,j,at;
 
  for (i=1; i<=strat->Ll; i++)
  {
    at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
    if (at != i)
    {
      LObject p = strat->L[i];
      for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
      strat->L[at] = p;
    }
  }
}

reorderT()

void reorderT ( kStrategy strat )

static

Definition at line 1241 of file kstd1.cc.

{
  int i,j,at;
  TObject p;
  unsigned long sev;
 
 
  for (i=1; i<=strat->tl; i++)
  {
    if (strat->T[i-1].length > strat->T[i].length)
    {
      p = strat->T[i];
      sev = strat->sevT[i];
      at = i-1;
      loop
      {
        at--;
        if (at < 0) break;
        if (strat->T[i].length > strat->T[at].length) break;
      }
      for (j = i-1; j>at; j--)
      {
        strat->T[j+1]=strat->T[j];
        strat->sevT[j+1]=strat->sevT[j];
        strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
      }
      strat->T[at+1]=p;
      strat->sevT[at+1] = sev;
      strat->R[p.i_r] = &(strat->T[at+1]);
    }
  }
}

updateL()

void updateL ( BOOLEAN searchPP, kStrategy strat )

static

Definition at line 1394 of file kstd1.cc.

{
  // only in mora
  assume(rHasLocalOrMixedOrdering(currRing));
  int dL;
  int j=strat->Ll;
  BOOLEAN lastPPfound=FALSE;
  if (searchPP && (strat->kNoether==NULL))
  {
    loop
    {
      if (j<0) break;
      if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
      {
        LObject p;
        p=strat->L[strat->Ll];
        strat->L[strat->Ll]=strat->L[j];
        strat->L[j]=p;
        lastPPfound=TRUE;
        break;
      }
      j--;
    }
  }
  j=strat->Ll;
  loop
  {
    if (j<0) break;
    if (pNext(strat->L[j].p) == strat->tail)
    {
      if (rField_is_Ring(currRing))
        pLmDelete(strat->L[j].p);    /*deletes the short spoly and computes*/
      else
        pLmFree(strat->L[j].p);    /*deletes the short spoly and computes*/
      strat->L[j].p = NULL;
      poly m1 = NULL, m2 = NULL;
      // check that spoly creation is ok
      while (strat->tailRing != currRing &&
             !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
      {
        assume(m1 == NULL && m2 == NULL);
        // if not, change to a ring where exponents are at least
        // large enough
        kStratChangeTailRing(strat);
      }
      /* create the real one */
      ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
                    strat->tailRing, m1, m2, strat->R);
 
      strat->L[j].SetLmCurrRing();
      if (!strat->honey)
        strat->initEcart(&strat->L[j]);
      else
        strat->L[j].SetLength(strat->length_pLength);
 
      BOOLEAN pp = FALSE;
      if (searchPP
      && (!lastPPfound)
      && (strat->kNoether==NULL))
        pp=hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
 
      strat->L[j].PrepareRed(strat->use_buckets);
 
      if (pp)
      {
        LObject p;
        p=strat->L[strat->Ll];
        strat->L[strat->Ll]=strat->L[j];
        strat->L[j]=p;
        break;
      }
    }
    j--;
  }
}

updateLHC()

void updateLHC ( kStrategy strat )

static

Definition at line 1474 of file kstd1.cc.

{
 
  int i = 0;
  kTest_TS(strat);
  while (i <= strat->Ll)
  {
    if (pNext(strat->L[i].p) == strat->tail)
    {
       /*- deletes the int spoly and computes -*/
      if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
      {
        if (rField_is_Ring(currRing))
          pLmDelete(strat->L[i].p);
        else
          pLmFree(strat->L[i].p);
        strat->L[i].p = NULL;
      }
      else
      {
        if (rField_is_Ring(currRing))
          pLmDelete(strat->L[i].p);
        else
          pLmFree(strat->L[i].p);
        strat->L[i].p = NULL;
        poly m1 = NULL, m2 = NULL;
        // check that spoly creation is ok
        while (strat->tailRing != currRing &&
               !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
        {
          assume(m1 == NULL && m2 == NULL);
          // if not, change to a ring where exponents are at least
          // large enough
          kStratChangeTailRing(strat);
        }
        /* create the real one */
        ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
                      strat->tailRing, m1, m2, strat->R);
        if (! strat->L[i].IsNull())
        {
          strat->L[i].SetLmCurrRing();
          strat->L[i].SetpFDeg();
          strat->L[i].ecart
            = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
          if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
        }
      }
    }
    deleteHC(&(strat->L[i]), strat);
    if (strat->L[i].IsNull())
      deleteInL(strat->L,&strat->Ll,i,strat);
    else
    {
#ifdef KDEBUG
      kTest_L(&(strat->L[i]), strat, TRUE, i, strat->T, strat->tl);
#endif
      i++;
    }
  }
  kTest_TS(strat);
}

updateT()

void updateT ( kStrategy strat )

static

Definition at line 1540 of file kstd1.cc.

{
  int i = 0;
  LObject p;
 
  while (i <= strat->tl)
  {
    p = strat->T[i];
    deleteHC(&p,strat, TRUE);
    /*- tries to cancel a unit: -*/
    cancelunit(&p);
    if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
      p.pCleardenom();
    if (p.p != strat->T[i].p)
    {
      strat->sevT[i] = pGetShortExpVector(p.p);
      p.SetpFDeg();
    }
    strat->T[i] = p;
    i++;
  }
}

Variable Documentation

kHomW

VAR intvec * kHomW

Definition at line 2409 of file kstd1.cc.

kModW

VAR intvec* kModW

Definition at line 2409 of file kstd1.cc.

kOptions

VAR BITSET kOptions

Initial value:

   =Sy_bit(OPT_PROT)           
|Sy_bit(OPT_REDSB)         
|Sy_bit(OPT_NOT_SUGAR)     
|Sy_bit(OPT_INTERRUPT)     
|Sy_bit(OPT_SUGARCRIT)     
|Sy_bit(OPT_REDTHROUGH)
|Sy_bit(OPT_OLDSTD)
|Sy_bit(OPT_FASTHC)        
|Sy_bit(OPT_INTSTRATEGY)   
|Sy_bit(OPT_INFREDTAIL)    
|Sy_bit(OPT_NOTREGULARITY) 
|Sy_bit(OPT_WEIGHTM)

Definition at line 45 of file kstd1.cc.

validOpts

VAR BITSET validOpts

Definition at line 60 of file kstd1.cc.