My Project
Macros | Typedefs | Functions | Variables
kstd1.h File Reference
#include "kernel/structs.h"
#include "polys/monomials/ring.h"

Go to the source code of this file.

Macros

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

Typedefs

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)
 

Functions

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

Variables

EXTERN_VAR int LazyPass
 
EXTERN_VAR int LazyDegree
 
EXTERN_VAR int Kstd1_mu
 
EXTERN_VAR int Kstd1_deg
 
EXTERN_VAR BITSET kOptions
 
EXTERN_VAR BITSET validOpts
 
EXTERN_VAR intveckModW
 
EXTERN_VAR intveckHomW
 

Macro Definition Documentation

◆ KSTD_NF_ECART

#define KSTD_NF_ECART   2

Definition at line 19 of file kstd1.h.

◆ KSTD_NF_LAZY

#define KSTD_NF_LAZY   1

Definition at line 17 of file kstd1.h.

◆ KSTD_NF_NONORM

#define KSTD_NF_NONORM   4

Definition at line 21 of file kstd1.h.

Typedef Documentation

◆ s_poly_proc_t

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)

Definition at line 14 of file kstd1.h.

Function Documentation

◆ initMora()

void initMora ( ideal  F,
kStrategy  strat 
)

Definition at line 1787 of file kstd1.cc.

1788 {
1789  int i,j;
1790 
1791  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1792  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1793  strat->enterS = enterSMora;
1794  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1795  strat->posInLOld = strat->posInL;
1796  strat->posInLOldFlag = TRUE;
1797  strat->initEcart = initEcartNormal;
1798  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1799  if ( strat->kHEdgeFound )
1800  strat->kNoether = pCopy((currRing->ppNoether));
1801  else if (strat->kHEdgeFound || strat->homog)
1802  strat->red = redFirst; /*take the first possible in T*/
1803  else
1804  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1805  if (strat->kHEdgeFound)
1806  {
1807  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1808  strat->posInT = posInT2;
1809  }
1810  else
1811  {
1812  strat->HCord = 32000;/*- very large -*/
1813  }
1814 
1815  if (rField_is_Ring(currRing)) {
1816  if (rField_is_Z(currRing))
1817  strat->red = redRiloc_Z;
1818  else
1819  strat->red = redRiloc;
1820  }
1821 
1822  /*reads the ecartWeights used for Graebes method from the
1823  *intvec ecart and set ecartWeights
1824  */
1825  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1826  {
1827  //interred machen Aenderung
1828  strat->pOrigFDeg=currRing->pFDeg;
1829  strat->pOrigLDeg=currRing->pLDeg;
1830  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1831  /*uses automatic computation of the ecartWeights to set them*/
1833 
1835  if (TEST_OPT_PROT)
1836  {
1837  for(i=1; i<=(currRing->N); i++)
1838  Print(" %d",ecartWeights[i]);
1839  PrintLn();
1840  mflush();
1841  }
1842  }
1843  kOptimizeLDeg(currRing->pLDeg, strat);
1844 }
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
int i
Definition: cfEzgcd.cc:132
char posInLOldFlag
Definition: kutil.h:382
poly kNoether
Definition: kutil.h:327
BOOLEAN * NotUsedAxis
Definition: kutil.h:331
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:281
pFDegProc pOrigFDeg
Definition: kutil.h:293
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:285
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:284
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:283
void(* initEcart)(TObject *L)
Definition: kutil.h:277
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:278
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:275
char kHEdgeFound
Definition: kutil.h:376
int HCord
Definition: kutil.h:354
char homog
Definition: kutil.h:372
pLDegProc pOrigLDeg
Definition: kutil.h:294
#define Print
Definition: emacs.cc:80
int j
Definition: facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:784
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:100
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:383
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1595
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:564
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5370
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1347
void initEcartNormal(TObject *h)
Definition: kutil.cc:1325
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define NULL
Definition: omList.c:12
#define TEST_OPT_WEIGHTM
Definition: options.h:120
#define TEST_OPT_PROT
Definition: options.h:102
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3707
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
void PrintLn()
Definition: reporter.cc:310
#define mflush()
Definition: reporter.h:58
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:489
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:514
#define IDELEMS(i)
Definition: simpleideals.h:23
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition: weight.cc:247
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition: weight.cc:182
EXTERN_VAR short * ecartWeights
Definition: weight.h:12

◆ 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 3369 of file kstd1.cc.

3370 {
3371  const ring save = currRing;
3372  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3373  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3374  if( currRing != save ) rChangeCurrRing(save);
3375  return ret;
3376 }
int p
Definition: cfModGcd.cc:4080
STATIC_VAR jList * Q
Definition: janet.cc:30
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3158
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2406 of file kstd1.cc.

2407 {
2408  int i;
2409  long j=0;
2410 
2411  for (i=r->N;i>0;i--)
2412  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2413  if (kModW == NULL) return j;
2414  i = __p_GetComp(p,r);
2415  if (i==0) return j;
2416  return j+(*kModW)[i-1];
2417 }
VAR intvec * kModW
Definition: kstd1.cc:2394
#define __p_GetComp(p, r)
Definition: monomials.h:63
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:469

◆ kInterRed()

ideal kInterRed ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3734 of file kstd1.cc.

3735 {
3736 #ifdef HAVE_PLURAL
3737  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3738 #endif
3741  )
3742  return kInterRedOld(F,Q);
3743 
3744  //return kInterRedOld(F,Q);
3745 
3746  BITSET save1;
3747  SI_SAVE_OPT1(save1);
3748  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3750  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3751  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3752  //extern char * showOption() ;
3753  //Print("%s\n",showOption());
3754 
3755  int need_retry;
3756  int counter=3;
3757  ideal res, res1;
3758  int elems;
3759  ideal null=NULL;
3760  if ((Q==NULL) || (!TEST_OPT_REDSB))
3761  {
3762  elems=idElem(F);
3763  res=kInterRedBba(F,Q,need_retry);
3764  }
3765  else
3766  {
3767  ideal FF=idSimpleAdd(F,Q);
3768  res=kInterRedBba(FF,NULL,need_retry);
3769  idDelete(&FF);
3770  null=idInit(1,1);
3771  if (need_retry)
3772  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3773  else
3774  res1=kNF(null,Q,res);
3775  idDelete(&res);
3776  res=res1;
3777  need_retry=1;
3778  }
3779  if (idElem(res)<=1) need_retry=0;
3780  while (need_retry && (counter>0))
3781  {
3782  #ifdef KDEBUG
3783  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3784  #endif
3785  res1=kInterRedBba(res,Q,need_retry);
3786  int new_elems=idElem(res1);
3787  counter -= (new_elems >= elems);
3788  elems = new_elems;
3789  idDelete(&res);
3790  if (idElem(res1)<=1) need_retry=0;
3791  if ((Q!=NULL) && (TEST_OPT_REDSB))
3792  {
3793  if (need_retry)
3794  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3795  else
3796  res=kNF(null,Q,res1);
3797  idDelete(&res1);
3798  }
3799  else
3800  res = res1;
3801  if (idElem(res)<=1) need_retry=0;
3802  }
3803  if (null!=NULL) idDelete(&null);
3804  SI_RESTORE_OPT1(save1);
3805  idSkipZeroes(res);
3806  return res;
3807 }
CanonicalForm res
Definition: facAbsFact.cc:60
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
ideal kInterRedOld(ideal F, ideal Q)
Definition: kstd1.cc:3382
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3474
#define KSTD_NF_LAZY
Definition: kstd1.h:17
VAR unsigned si_opt_1
Definition: options.c:5
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define OPT_REDTHROUGH
Definition: options.h:81
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:103
#define TEST_OPT_DEBUG
Definition: options.h:107
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:520
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:765
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
int idElem(const ideal F)
count non-zero elements
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define BITSET
Definition: structs.h:20

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3382 of file kstd1.cc.

3383 {
3384  int j;
3385  kStrategy strat = new skStrategy;
3386 
3387  ideal tempF = F;
3388  ideal tempQ = Q;
3389 
3390 #ifdef HAVE_PLURAL
3391  if(rIsSCA(currRing))
3392  {
3393  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3394  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3395  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3396 
3397  // this should be done on the upper level!!! :
3398  // tempQ = SCAQuotient(currRing);
3399 
3400  if(Q == currRing->qideal)
3401  tempQ = SCAQuotient(currRing);
3402  }
3403 #endif
3404 
3405 // if (TEST_OPT_PROT)
3406 // {
3407 // writeTime("start InterRed:");
3408 // mflush();
3409 // }
3410  //strat->syzComp = 0;
3411  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3412  strat->kNoether=pCopy((currRing->ppNoether));
3413  strat->ak = id_RankFreeModule(tempF,currRing);
3414  initBuchMoraCrit(strat);
3415  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3416  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3417  strat->enterS = enterSBba;
3418  strat->posInT = posInT17;
3419  strat->initEcart = initEcartNormal;
3420  strat->sl = -1;
3421  strat->tl = -1;
3422  strat->tmax = setmaxT;
3423  strat->T = initT();
3424  strat->R = initR();
3425  strat->sevT = initsevT();
3427  initS(tempF, tempQ, strat);
3428  if (TEST_OPT_REDSB)
3429  strat->noTailReduction=FALSE;
3430  updateS(TRUE,strat);
3432  completeReduce(strat);
3433  //else if (TEST_OPT_PROT) PrintLn();
3434  cleanT(strat);
3435  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3436  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3437  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3438  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3439  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3440  omfree(strat->sevT);
3441  omfree(strat->S_2_R);
3442  omfree(strat->R);
3443 
3444  if (strat->fromQ)
3445  {
3446  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3447  {
3448  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3449  }
3450  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3451  }
3452 // if (TEST_OPT_PROT)
3453 // {
3454 // writeTime("end Interred:");
3455 // mflush();
3456 // }
3457  ideal shdl=strat->Shdl;
3458  idSkipZeroes(shdl);
3459  if (strat->fromQ)
3460  {
3461  strat->fromQ=NULL;
3462  ideal res=kInterRed(shdl,NULL);
3463  idDelete(&shdl);
3464  shdl=res;
3465  }
3466  delete(strat);
3467 #ifdef HAVE_PLURAL
3468  if( tempF != F )
3469  id_Delete( &tempF, currRing);
3470 #endif
3471  return shdl;
3472 }
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
int * S_2_R
Definition: kutil.h:341
char noTailReduction
Definition: kutil.h:378
TSet T
Definition: kutil.h:323
intset ecartS
Definition: kutil.h:306
char honey
Definition: kutil.h:377
int ak
Definition: kutil.h:352
TObject ** R
Definition: kutil.h:339
poly kHEdge
Definition: kutil.h:326
int tl
Definition: kutil.h:349
unsigned long * sevT
Definition: kutil.h:322
ideal Shdl
Definition: kutil.h:300
int tmax
Definition: kutil.h:349
intset fromQ
Definition: kutil.h:318
int sl
Definition: kutil.h:347
unsigned long * sevS
Definition: kutil.h:319
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
KINLINE TSet initT()
Definition: kInline.h:84
KINLINE TObject ** initR()
Definition: kInline.h:95
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3734
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5805
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8156
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:9115
void cleanT(kStrategy strat)
Definition: kutil.cc:545
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9997
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10859
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9350
#define setmaxT
Definition: kutil.h:33
class sTObject TObject
Definition: kutil.h:53
static bool rIsSCA(const ring r)
Definition: nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1520
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define TEST_OPT_INTSTRATEGY
Definition: options.h:109
#define pDelete(p_ptr)
Definition: polys.h:186
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition: polys.h:70
ideal SCAQuotient(const ring r)
Definition: sca.h:10
static short scaLastAltVar(ring r)
Definition: sca.h:25
static short scaFirstAltVar(ring r)
Definition: sca.h:18
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s

◆ kMin_std()

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

Definition at line 3009 of file kstd1.cc.

3011 {
3012  if(idIs0(F))
3013  {
3014  M=idInit(1,F->rank);
3015  return idInit(1,F->rank);
3016  }
3018  {
3019  ideal sb;
3020  sb = kStd(F, Q, h, w, hilb);
3021  idSkipZeroes(sb);
3022  if(IDELEMS(sb) <= IDELEMS(F))
3023  {
3024  M = idCopy(sb);
3025  idSkipZeroes(M);
3026  return(sb);
3027  }
3028  else
3029  {
3030  M = idCopy(F);
3031  idSkipZeroes(M);
3032  return(sb);
3033  }
3034  }
3035  ideal r=NULL;
3036  int Kstd1_OldDeg = Kstd1_deg,i;
3037  intvec* temp_w=NULL;
3038  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3039  BOOLEAN delete_w=(w==NULL);
3040  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3041  kStrategy strat=new skStrategy;
3042 
3043  if(!TEST_OPT_RETURN_SB)
3044  strat->syzComp = syzComp;
3046  strat->LazyPass=20;
3047  else
3048  strat->LazyPass=2;
3049  strat->LazyDegree = 1;
3050  strat->minim=(reduced % 2)+1;
3051  strat->ak = id_RankFreeModule(F,currRing);
3052  if (delete_w)
3053  {
3054  temp_w=new intvec((strat->ak)+1);
3055  w = &temp_w;
3056  }
3057  if (h==testHomog)
3058  {
3059  if (strat->ak == 0)
3060  {
3061  h = (tHomog)idHomIdeal(F,Q);
3062  w=NULL;
3063  }
3064  else
3065  {
3066  h = (tHomog)idHomModule(F,Q,w);
3067  }
3068  }
3069  if (h==isHomog)
3070  {
3071  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3072  {
3073  kModW = *w;
3074  strat->kModW = *w;
3075  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3076  strat->pOrigFDeg = currRing->pFDeg;
3077  strat->pOrigLDeg = currRing->pLDeg;
3079 
3080  toReset = TRUE;
3081  if (reduced>1)
3082  {
3083  Kstd1_OldDeg=Kstd1_deg;
3084  Kstd1_deg = -1;
3085  for (i=IDELEMS(F)-1;i>=0;i--)
3086  {
3087  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3088  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3089  }
3090  }
3091  }
3092  currRing->pLexOrder = TRUE;
3093  strat->LazyPass*=2;
3094  }
3095  strat->homog=h;
3097  {
3098  if (w!=NULL)
3099  r=mora(F,Q,*w,hilb,strat);
3100  else
3101  r=mora(F,Q,NULL,hilb,strat);
3102  }
3103  else
3104  {
3105  if (w!=NULL)
3106  r=bba(F,Q,*w,hilb,strat);
3107  else
3108  r=bba(F,Q,NULL,hilb,strat);
3109  }
3110 #ifdef KDEBUG
3111  {
3112  int i;
3113  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3114  }
3115 #endif
3116  idSkipZeroes(r);
3117  if (toReset)
3118  {
3119  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3120  kModW = NULL;
3121  }
3122  currRing->pLexOrder = b;
3123  HCord=strat->HCord;
3124  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3125  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3126  {
3127  M=idInit(1,F->rank);
3128  M->m[0]=pOne();
3129  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3130  if (strat->M!=NULL) idDelete(&strat->M);
3131  }
3132  else if (strat->M==NULL)
3133  {
3134  M=idInit(1,F->rank);
3135  WarnS("no minimal generating set computed");
3136  }
3137  else
3138  {
3139  idSkipZeroes(strat->M);
3140  M=strat->M;
3141  }
3142  delete(strat);
3143  if (reduced>2)
3144  {
3145  Kstd1_deg=Kstd1_OldDeg;
3146  if (!oldDegBound)
3148  }
3149  else
3150  {
3151  if (IDELEMS(M)>IDELEMS(r)) {
3152  idDelete(&M);
3153  M=idCopy(r); }
3154  }
3155  return r;
3156 }
CanonicalForm b
Definition: cfModGcd.cc:4105
Definition: intvec.h:23
intvec * kModW
Definition: kutil.h:334
int syzComp
Definition: kutil.h:353
int minim
Definition: kutil.h:357
ideal M
Definition: kutil.h:302
int LazyPass
Definition: kutil.h:352
int LazyDegree
Definition: kutil.h:352
#define WarnS
Definition: emacs.cc:78
const CanonicalForm & w
Definition: facAbsFact.cc:51
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:91
ideal idCopy(ideal A)
Definition: ideals.h:60
STATIC_VAR Poly * h
Definition: janet.cc:971
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd1.cc:1848
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2396
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2419
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2383
VAR int HCord
Definition: kutil.cc:246
#define assume(x)
Definition: mod2.h:387
#define TEST_OPT_DEGBOUND
Definition: options.h:112
#define TEST_OPT_RETURN_SB
Definition: options.h:111
#define OPT_DEGBOUND
Definition: options.h:89
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3719
#define pTest(p)
Definition: polys.h:415
#define pIsConstant(p)
like above, except that Comp must be 0
Definition: polys.h:238
#define pOne()
Definition: polys.h:315
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:553
#define M
Definition: sirandom.c:25
tHomog
Definition: structs.h:40
@ isHomog
Definition: structs.h:42
@ testHomog
Definition: structs.h:43

◆ kModDeg()

long kModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2396 of file kstd1.cc.

2397 {
2398  long o=p_WDegree(p, r);
2399  long i=__p_GetComp(p, r);
2400  if (i==0) return o;
2401  //assume((i>0) && (i<=kModW->length()));
2402  if (i<=kModW->length())
2403  return o+(*kModW)[i-1];
2404  return o;
2405 }
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:709

◆ kNF() [1/2]

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

Definition at line 3255 of file kstd1.cc.

3256 {
3257  ideal res;
3258  if (TEST_OPT_PROT)
3259  {
3260  Print("(S:%d)",IDELEMS(p));mflush();
3261  }
3262  if (idIs0(p))
3263  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3264 
3265  ideal pp = p;
3266 #ifdef HAVE_PLURAL
3267  if(rIsSCA(currRing))
3268  {
3269  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3270  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3271  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3272 
3273  if(Q == currRing->qideal)
3274  Q = SCAQuotient(currRing);
3275  }
3276 #endif
3277 
3278  if ((idIs0(F))&&(Q==NULL))
3279  {
3280 #ifdef HAVE_PLURAL
3281  if(p != pp)
3282  return pp;
3283 #endif
3284  return idCopy(p); /*F+Q=0*/
3285  }
3286 
3287  kStrategy strat=new skStrategy;
3288  strat->syzComp = syzComp;
3290  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3291  {
3292  strat->ak = si_max(strat->ak,(int)F->rank);
3293  }
3294 
3296  {
3297 #ifdef HAVE_SHIFTBBA
3298  if (currRing->isLPring)
3299  {
3300  WerrorS("No local ordering possible for shift algebra");
3301  return(NULL);
3302  }
3303 #endif
3304  res=kNF1(F,Q,pp,strat,lazyReduce);
3305  }
3306  else
3307  res=kNF2(F,Q,pp,strat,lazyReduce);
3308  delete(strat);
3309 
3310 #ifdef HAVE_PLURAL
3311  if(pp != p)
3312  id_Delete(&pp, currRing);
3313 #endif
3314 
3315  return res;
3316 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
void WerrorS(const char *s)
Definition: feFopen.cc:24
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:2097
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3712

◆ kNF() [2/2]

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

Definition at line 3158 of file kstd1.cc.

3159 {
3160  if (p==NULL)
3161  return NULL;
3162 
3163  poly pp = p;
3164 
3165 #ifdef HAVE_PLURAL
3166  if(rIsSCA(currRing))
3167  {
3168  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3169  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3170  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3171 
3172  if(Q == currRing->qideal)
3173  Q = SCAQuotient(currRing);
3174  }
3175 #endif
3176 
3177  if ((idIs0(F))&&(Q==NULL))
3178  {
3179 #ifdef HAVE_PLURAL
3180  if(p != pp)
3181  return pp;
3182 #endif
3183  return pCopy(p); /*F+Q=0*/
3184  }
3185 
3186  kStrategy strat=new skStrategy;
3187  strat->syzComp = syzComp;
3188  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3189  poly res;
3190 
3192  {
3193 #ifdef HAVE_SHIFTBBA
3194  if (currRing->isLPring)
3195  {
3196  WerrorS("No local ordering possible for shift algebra");
3197  return(NULL);
3198  }
3199 #endif
3200  res=kNF1(F,Q,pp,strat,lazyReduce);
3201  }
3202  else
3203  res=kNF2(F,Q,pp,strat,lazyReduce);
3204  delete(strat);
3205 
3206 #ifdef HAVE_PLURAL
3207  if(pp != p)
3208  p_Delete(&pp, currRing);
3209 #endif
3210  return res;
3211 }
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1465
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
#define pMaxComp(p)
Definition: polys.h:299

◆ kNF1() [1/2]

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

Definition at line 2241 of file kstd1.cc.

2242 {
2243  assume(!idIs0(q));
2244  assume(!(idIs0(F)&&(Q==NULL)));
2245 
2246 // lazy_reduce flags: can be combined by |
2247 //#define KSTD_NF_LAZY 1
2248  // do only a reduction of the leading term
2249 //#define KSTD_NF_ECART 2
2250  // only local: recude even with bad ecart
2251  poly p;
2252  int i;
2253  int j;
2254  int o;
2255  LObject h;
2256  ideal res;
2257  BITSET save1;
2258  SI_SAVE_OPT1(save1);
2259 
2260  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2261  //if ((idIs0(F))&&(Q==NULL))
2262  // return idCopy(q); /*F=0*/
2263  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2264  /*- creating temp data structures------------------- -*/
2265  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2266  strat->kNoether=pCopy((currRing->ppNoether));
2269  && (0<Kstd1_deg)
2270  && ((!strat->kHEdgeFound)
2272  {
2273  pLmDelete(&strat->kNoether);
2274  strat->kNoether=pOne();
2275  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2276  pSetm(strat->kNoether);
2277  strat->kHEdgeFound=TRUE;
2278  }
2279  initBuchMoraCrit(strat);
2281  initBuchMoraPosRing(strat);
2282  else
2283  initBuchMoraPos(strat);
2284  initMora(F,strat);
2285  strat->enterS = enterSMoraNF;
2286  /*- set T -*/
2287  strat->tl = -1;
2288  strat->tmax = setmaxT;
2289  strat->T = initT();
2290  strat->R = initR();
2291  strat->sevT = initsevT();
2292  /*- set S -*/
2293  strat->sl = -1;
2294  /*- init local data struct.-------------------------- -*/
2295  /*Shdl=*/initS(F,Q,strat);
2296  if ((strat->ak!=0)
2297  && (strat->kHEdgeFound))
2298  {
2299  if (strat->ak!=1)
2300  {
2301  pSetComp(strat->kNoether,1);
2302  pSetmComp(strat->kNoether);
2303  poly p=pHead(strat->kNoether);
2304  pSetComp(p,strat->ak);
2305  pSetmComp(p);
2306  p=pAdd(strat->kNoether,p);
2307  strat->kNoether=pNext(p);
2309  }
2310  }
2311  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
2312  {
2313  for (i=strat->sl; i>=0; i--)
2314  pNorm(strat->S[i]);
2315  }
2316  /*- compute------------------------------------------- -*/
2317  res=idInit(IDELEMS(q),strat->ak);
2318  for (i=0; i<IDELEMS(q); i++)
2319  {
2320  if (q->m[i]!=NULL)
2321  {
2322  p = pCopy(q->m[i]);
2323  deleteHC(&p,&o,&j,strat);
2324  if (p!=NULL)
2325  {
2326  /*- puts the elements of S also to T -*/
2327  for (j=0; j<=strat->sl; j++)
2328  {
2329  h.p = strat->S[j];
2330  h.ecart = strat->ecartS[j];
2331  h.pLength = h.length = pLength(h.p);
2332  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2333  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2334  h.sev = strat->sevS[j];
2335  h.SetpFDeg();
2337  enterT_strong(h,strat);
2338  else
2339  enterT(h,strat);
2340  }
2341  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2343  {
2344  p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2345  }
2346  else
2347  p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2348  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2349  {
2350  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2351  p = redtail(p,strat->sl,strat);
2352  }
2353  cleanT(strat);
2354  }
2355  res->m[i]=p;
2356  }
2357  //else
2358  // res->m[i]=NULL;
2359  }
2360  /*- release temp data------------------------------- -*/
2361  assume(strat->L==NULL); /*strat->L unsed */
2362  assume(strat->B==NULL); /*strat->B unused */
2363  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2364  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2365  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2366  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2367  omFree(strat->sevT);
2368  omFree(strat->S_2_R);
2369  omFree(strat->R);
2370  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2371  {
2373  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2374  strat->fromQ=NULL;
2375  }
2376  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2377  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2378 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2379 // {
2380 // pFDeg=strat->pOrigFDeg;
2381 // pLDeg=strat->pOrigLDeg;
2382 // if (ecartWeights)
2383 // {
2384 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2385 // ecartWeights=NULL;
2386 // }
2387 // }
2388  idDelete(&strat->Shdl);
2389  SI_RESTORE_OPT1(save1);
2390  if (TEST_OPT_PROT) PrintLn();
2391  return res;
2392 }
polyset S
Definition: kutil.h:303
LSet B
Definition: kutil.h:325
LSet L
Definition: kutil.h:324
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1787
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1649
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1056
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:956
#define KSTD_NF_ECART
Definition: kstd1.h:19
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7480
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9699
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:10149
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9799
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:254
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:10235
#define setmaxTinc
Definition: kutil.h:34
class sLObject LObject
Definition: kutil.h:54
#define pNext(p)
Definition: monomials.h:36
#define omFree(addr)
Definition: omAllocDecl.h:261
#define OPT_REDTAIL
Definition: options.h:90
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:114
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:711
static unsigned pLength(poly a)
Definition: p_polys.h:191
#define pAdd(p, q)
Definition: polys.h:203
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pSetm(p)
Definition: polys.h:271
#define pSetComp(p, v)
Definition: polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
#define pSetmComp(p)
TODO:
Definition: polys.h:273
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:363
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pWTotaldegree(p)
Definition: polys.h:283
void PrintS(const char *s)
Definition: reporter.cc:284

◆ kNF1() [2/2]

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

Definition at line 2097 of file kstd1.cc.

2098 {
2099  assume(q!=NULL);
2100  assume(!(idIs0(F)&&(Q==NULL)));
2101 
2102 // lazy_reduce flags: can be combined by |
2103 //#define KSTD_NF_LAZY 1
2104  // do only a reduction of the leading term
2105 //#define KSTD_NF_ECART 2
2106  // only local: recude even with bad ecart
2107  poly p;
2108  int i;
2109  int j;
2110  int o;
2111  LObject h;
2112  BITSET save1;
2113  SI_SAVE_OPT1(save1);
2114 
2115  //if ((idIs0(F))&&(Q==NULL))
2116  // return pCopy(q); /*F=0*/
2117  //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
2118  /*- creating temp data structures------------------- -*/
2119  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2120  strat->kNoether = pCopy((currRing->ppNoether));
2124  && (! TEST_V_DEG_STOP)
2125  && (0<Kstd1_deg)
2126  && ((!strat->kHEdgeFound)
2128  {
2129  pLmDelete(&strat->kNoether);
2130  strat->kNoether=pOne();
2131  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2132  pSetm(strat->kNoether);
2133  strat->kHEdgeFound=TRUE;
2134  }
2135  initBuchMoraCrit(strat);
2137  initBuchMoraPosRing(strat);
2138  else
2139  initBuchMoraPos(strat);
2140  initMora(F,strat);
2141  strat->enterS = enterSMoraNF;
2142  /*- set T -*/
2143  strat->tl = -1;
2144  strat->tmax = setmaxT;
2145  strat->T = initT();
2146  strat->R = initR();
2147  strat->sevT = initsevT();
2148  /*- set S -*/
2149  strat->sl = -1;
2150  /*- init local data struct.-------------------------- -*/
2151  /*Shdl=*/initS(F,Q,strat);
2152  if ((strat->ak!=0)
2153  && (strat->kHEdgeFound))
2154  {
2155  if (strat->ak!=1)
2156  {
2157  pSetComp(strat->kNoether,1);
2158  pSetmComp(strat->kNoether);
2159  poly p=pHead(strat->kNoether);
2160  pSetComp(p,strat->ak);
2161  pSetmComp(p);
2162  p=pAdd(strat->kNoether,p);
2163  strat->kNoether=pNext(p);
2165  }
2166  }
2167  if ((lazyReduce & KSTD_NF_LAZY)==0)
2168  {
2169  for (i=strat->sl; i>=0; i--)
2170  pNorm(strat->S[i]);
2171  }
2172  /*- puts the elements of S also to T -*/
2173  for (i=0; i<=strat->sl; i++)
2174  {
2175  h.p = strat->S[i];
2176  h.ecart = strat->ecartS[i];
2177  if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
2178  else assume(strat->sevS[i] == pGetShortExpVector(h.p));
2179  h.length = pLength(h.p);
2180  h.sev = strat->sevS[i];
2181  h.SetpFDeg();
2182  enterT(h,strat);
2183  }
2184 #ifdef KDEBUG
2185 // kDebugPrint(strat);
2186 #endif
2187  /*- compute------------------------------------------- -*/
2188  p = pCopy(q);
2189  deleteHC(&p,&o,&j,strat);
2190  kTest(strat);
2191  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2192  if (BVERBOSE(23)) kDebugPrint(strat);
2194  {
2195  if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2196  }
2197  else
2198  {
2199  if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2200  }
2201  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2202  {
2203  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2204  p = redtail(p,strat->sl,strat);
2205  }
2206  /*- release temp data------------------------------- -*/
2207  cleanT(strat);
2208  assume(strat->L==NULL); /*strat->L unsed */
2209  assume(strat->B==NULL); /*strat->B unused */
2210  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2211  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2212  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2213  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2214  omFree(strat->sevT);
2215  omFree(strat->S_2_R);
2216  omFree(strat->R);
2217 
2218  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2219  {
2220  i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
2221  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2222  strat->fromQ=NULL;
2223  }
2224  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2225  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2226 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2227 // {
2228 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2229 // if (ecartWeights)
2230 // {
2231 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2232 // ecartWeights=NULL;
2233 // }
2234 // }
2235  idDelete(&strat->Shdl);
2236  SI_RESTORE_OPT1(save1);
2237  if (TEST_OPT_PROT) PrintLn();
2238  return p;
2239 }
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:12080
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1010
#define OPT_INTSTRATEGY
Definition: options.h:91
#define BVERBOSE(a)
Definition: options.h:34
#define TEST_V_DEG_STOP
Definition: options.h:136

◆ kNFBound() [1/2]

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

Definition at line 3318 of file kstd1.cc.

3319 {
3320  ideal res;
3321  if (TEST_OPT_PROT)
3322  {
3323  Print("(S:%d)",IDELEMS(p));mflush();
3324  }
3325  if (idIs0(p))
3326  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3327 
3328  ideal pp = p;
3329 #ifdef HAVE_PLURAL
3330  if(rIsSCA(currRing))
3331  {
3332  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3333  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3334  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3335 
3336  if(Q == currRing->qideal)
3337  Q = SCAQuotient(currRing);
3338  }
3339 #endif
3340 
3341  if ((idIs0(F))&&(Q==NULL))
3342  {
3343 #ifdef HAVE_PLURAL
3344  if(p != pp)
3345  return pp;
3346 #endif
3347  return idCopy(p); /*F+Q=0*/
3348  }
3349 
3350  kStrategy strat=new skStrategy;
3351  strat->syzComp = syzComp;
3353  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3354  {
3355  strat->ak = si_max(strat->ak,(int)F->rank);
3356  }
3357 
3358  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3359  delete(strat);
3360 
3361 #ifdef HAVE_PLURAL
3362  if(pp != p)
3363  id_Delete(&pp, currRing);
3364 #endif
3365 
3366  return res;
3367 }
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3790

◆ kNFBound() [2/2]

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

Definition at line 3213 of file kstd1.cc.

3214 {
3215  if (p==NULL)
3216  return NULL;
3217 
3218  poly pp = p;
3219 
3220 #ifdef HAVE_PLURAL
3221  if(rIsSCA(currRing))
3222  {
3223  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3224  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3225  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3226 
3227  if(Q == currRing->qideal)
3228  Q = SCAQuotient(currRing);
3229  }
3230 #endif
3231 
3232  if ((idIs0(F))&&(Q==NULL))
3233  {
3234 #ifdef HAVE_PLURAL
3235  if(p != pp)
3236  return pp;
3237 #endif
3238  return pCopy(p); /*F+Q=0*/
3239  }
3240 
3241  kStrategy strat=new skStrategy;
3242  strat->syzComp = syzComp;
3243  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3244  poly res;
3245  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3246  delete(strat);
3247 
3248 #ifdef HAVE_PLURAL
3249  if(pp != p)
3250  p_Delete(&pp, currRing);
3251 #endif
3252  return res;
3253 }

◆ kSba()

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

Definition at line 2604 of file kstd1.cc.

2606 {
2607  if(idIs0(F))
2608  return idInit(1,F->rank);
2609  if(!rField_is_Ring(currRing))
2610  {
2611  ideal r;
2612  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2613  BOOLEAN delete_w=(w==NULL);
2614  kStrategy strat=new skStrategy;
2615  strat->sbaOrder = sbaOrder;
2616  if (arri!=0)
2617  {
2618  strat->rewCrit1 = arriRewDummy;
2619  strat->rewCrit2 = arriRewCriterion;
2620  strat->rewCrit3 = arriRewCriterionPre;
2621  }
2622  else
2623  {
2624  strat->rewCrit1 = faugereRewCriterion;
2625  strat->rewCrit2 = faugereRewCriterion;
2626  strat->rewCrit3 = faugereRewCriterion;
2627  }
2628 
2629  if(!TEST_OPT_RETURN_SB)
2630  strat->syzComp = syzComp;
2631  if (TEST_OPT_SB_1)
2632  //if(!rField_is_Ring(currRing)) // always true here
2633  strat->newIdeal = newIdeal;
2635  strat->LazyPass=20;
2636  else
2637  strat->LazyPass=2;
2638  strat->LazyDegree = 1;
2640  strat->chainCrit=chainCritNormal;
2642  strat->ak = id_RankFreeModule(F,currRing);
2643  strat->kModW=kModW=NULL;
2644  strat->kHomW=kHomW=NULL;
2645  if (vw != NULL)
2646  {
2647  currRing->pLexOrder=FALSE;
2648  strat->kHomW=kHomW=vw;
2649  strat->pOrigFDeg = currRing->pFDeg;
2650  strat->pOrigLDeg = currRing->pLDeg;
2652  toReset = TRUE;
2653  }
2654  if (h==testHomog)
2655  {
2656  if (strat->ak == 0)
2657  {
2658  h = (tHomog)idHomIdeal(F,Q);
2659  w=NULL;
2660  }
2661  else if (!TEST_OPT_DEGBOUND)
2662  {
2663  if (w!=NULL)
2664  h = (tHomog)idHomModule(F,Q,w);
2665  else
2666  h = (tHomog)idHomIdeal(F,Q);
2667  }
2668  }
2669  currRing->pLexOrder=b;
2670  if (h==isHomog)
2671  {
2672  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2673  {
2674  strat->kModW = kModW = *w;
2675  if (vw == NULL)
2676  {
2677  strat->pOrigFDeg = currRing->pFDeg;
2678  strat->pOrigLDeg = currRing->pLDeg;
2680  toReset = TRUE;
2681  }
2682  }
2683  currRing->pLexOrder = TRUE;
2684  if (hilb==NULL) strat->LazyPass*=2;
2685  }
2686  strat->homog=h;
2687  #ifdef KDEBUG
2688  idTest(F);
2689  if(Q != NULL)
2690  idTest(Q);
2691  #endif
2692  #ifdef HAVE_PLURAL
2693  if (rIsPluralRing(currRing))
2694  {
2695  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2696  strat->no_prod_crit = ! bIsSCA;
2697  if (w!=NULL)
2698  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2699  else
2700  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2701  }
2702  else
2703  #endif
2704  {
2706  {
2707  if (w!=NULL)
2708  r=mora(F,Q,*w,hilb,strat);
2709  else
2710  r=mora(F,Q,NULL,hilb,strat);
2711  }
2712  else
2713  {
2714  strat->sigdrop = FALSE;
2715  if (w!=NULL)
2716  r=sba(F,Q,*w,hilb,strat);
2717  else
2718  r=sba(F,Q,NULL,hilb,strat);
2719  }
2720  }
2721  #ifdef KDEBUG
2722  idTest(r);
2723  #endif
2724  if (toReset)
2725  {
2726  kModW = NULL;
2727  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2728  }
2729  currRing->pLexOrder = b;
2730  //Print("%d reductions canceled \n",strat->cel);
2731  HCord=strat->HCord;
2732  //delete(strat);
2733  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2734  return r;
2735  }
2736  else
2737  {
2738  //--------------------------RING CASE-------------------------
2739  assume(sbaOrder == 1);
2740  assume(arri == 0);
2741  ideal r;
2742  r = idCopy(F);
2743  int sbaEnterS = -1;
2744  bool sigdrop = TRUE;
2745  //This is how we set the SBA algorithm;
2746  int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2747  while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2748  && (blockred <= blockedreductions))
2749  {
2750  loops++;
2751  if(loops == 1)
2752  sigdrop = FALSE;
2753  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2754  BOOLEAN delete_w=(w==NULL);
2755  kStrategy strat=new skStrategy;
2756  strat->sbaEnterS = sbaEnterS;
2757  strat->sigdrop = sigdrop;
2758  #if 0
2759  strat->blockred = blockred;
2760  #else
2761  strat->blockred = 0;
2762  #endif
2763  strat->blockredmax = blockedreductions;
2764  //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2765  //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2766  strat->sbaOrder = sbaOrder;
2767  if (arri!=0)
2768  {
2769  strat->rewCrit1 = arriRewDummy;
2770  strat->rewCrit2 = arriRewCriterion;
2771  strat->rewCrit3 = arriRewCriterionPre;
2772  }
2773  else
2774  {
2775  strat->rewCrit1 = faugereRewCriterion;
2776  strat->rewCrit2 = faugereRewCriterion;
2777  strat->rewCrit3 = faugereRewCriterion;
2778  }
2779 
2780  if(!TEST_OPT_RETURN_SB)
2781  strat->syzComp = syzComp;
2782  if (TEST_OPT_SB_1)
2783  if(!rField_is_Ring(currRing))
2784  strat->newIdeal = newIdeal;
2786  strat->LazyPass=20;
2787  else
2788  strat->LazyPass=2;
2789  strat->LazyDegree = 1;
2791  strat->chainCrit=chainCritNormal;
2793  strat->ak = id_RankFreeModule(F,currRing);
2794  strat->kModW=kModW=NULL;
2795  strat->kHomW=kHomW=NULL;
2796  if (vw != NULL)
2797  {
2798  currRing->pLexOrder=FALSE;
2799  strat->kHomW=kHomW=vw;
2800  strat->pOrigFDeg = currRing->pFDeg;
2801  strat->pOrigLDeg = currRing->pLDeg;
2803  toReset = TRUE;
2804  }
2805  if (h==testHomog)
2806  {
2807  if (strat->ak == 0)
2808  {
2809  h = (tHomog)idHomIdeal(F,Q);
2810  w=NULL;
2811  }
2812  else if (!TEST_OPT_DEGBOUND)
2813  {
2814  if (w!=NULL)
2815  h = (tHomog)idHomModule(F,Q,w);
2816  else
2817  h = (tHomog)idHomIdeal(F,Q);
2818  }
2819  }
2820  currRing->pLexOrder=b;
2821  if (h==isHomog)
2822  {
2823  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2824  {
2825  strat->kModW = kModW = *w;
2826  if (vw == NULL)
2827  {
2828  strat->pOrigFDeg = currRing->pFDeg;
2829  strat->pOrigLDeg = currRing->pLDeg;
2831  toReset = TRUE;
2832  }
2833  }
2834  currRing->pLexOrder = TRUE;
2835  if (hilb==NULL) strat->LazyPass*=2;
2836  }
2837  strat->homog=h;
2838  #ifdef KDEBUG
2839  idTest(F);
2840  if(Q != NULL)
2841  idTest(Q);
2842  #endif
2843  #ifdef HAVE_PLURAL
2844  if (rIsPluralRing(currRing))
2845  {
2846  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2847  strat->no_prod_crit = ! bIsSCA;
2848  if (w!=NULL)
2849  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2850  else
2851  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2852  }
2853  else
2854  #endif
2855  {
2857  {
2858  if (w!=NULL)
2859  r=mora(F,Q,*w,hilb,strat);
2860  else
2861  r=mora(F,Q,NULL,hilb,strat);
2862  }
2863  else
2864  {
2865  if (w!=NULL)
2866  r=sba(r,Q,*w,hilb,strat);
2867  else
2868  {
2869  r=sba(r,Q,NULL,hilb,strat);
2870  }
2871  }
2872  }
2873  #ifdef KDEBUG
2874  idTest(r);
2875  #endif
2876  if (toReset)
2877  {
2878  kModW = NULL;
2879  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2880  }
2881  currRing->pLexOrder = b;
2882  //Print("%d reductions canceled \n",strat->cel);
2883  HCord=strat->HCord;
2884  sigdrop = strat->sigdrop;
2885  sbaEnterS = strat->sbaEnterS;
2886  blockred = strat->blockred;
2887  delete(strat);
2888  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2889  }
2890  // Go to std
2891  if(sigdrop || blockred > blockedreductions)
2892  {
2893  r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2894  }
2895  return r;
2896  }
2897 }
bool sigdrop
Definition: kutil.h:359
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:288
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:290
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:292
intvec * kHomW
Definition: kutil.h:335
int blockred
Definition: kutil.h:364
unsigned sbaOrder
Definition: kutil.h:313
int blockredmax
Definition: kutil.h:365
int newIdeal
Definition: kutil.h:356
char z2homog
Definition: kutil.h:374
char no_prod_crit
Definition: kutil.h:394
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:287
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:291
int sbaEnterS
Definition: kutil.h:362
#define idTest(id)
Definition: ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition: kInline.h:1225
static ideal nc_GB(const ideal F, const ideal Q, const intvec *w, const intvec *hilb, kStrategy strat, const ring r)
Definition: nc.h:27
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2406
VAR intvec * kHomW
Definition: kstd1.cc:2394
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2745
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition: kutil.cc:7287
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:7262
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:1975
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition: kutil.cc:7203
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3476
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3240
if(yy_init)
Definition: libparse.cc:1420
#define TEST_OPT_SB_1
Definition: options.h:118

◆ kStd()

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

Definition at line 2419 of file kstd1.cc.

2421 {
2422  if(idIs0(F))
2423  return idInit(1,F->rank);
2424 
2425 #ifdef HAVE_SHIFTBBA
2426  if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2427 #endif
2428 
2429  ideal r;
2430  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2431  BOOLEAN delete_w=(w==NULL);
2432  kStrategy strat=new skStrategy;
2433 
2434  strat->s_poly=sp;
2435  if(!TEST_OPT_RETURN_SB)
2436  strat->syzComp = syzComp;
2437  if (TEST_OPT_SB_1
2438  &&(!rField_is_Ring(currRing))
2439  )
2440  strat->newIdeal = newIdeal;
2442  strat->LazyPass=20;
2443  else
2444  strat->LazyPass=2;
2445  strat->LazyDegree = 1;
2446  strat->ak = id_RankFreeModule(F,currRing);
2447  strat->kModW=kModW=NULL;
2448  strat->kHomW=kHomW=NULL;
2449  if (vw != NULL)
2450  {
2451  currRing->pLexOrder=FALSE;
2452  strat->kHomW=kHomW=vw;
2453  strat->pOrigFDeg = currRing->pFDeg;
2454  strat->pOrigLDeg = currRing->pLDeg;
2456  toReset = TRUE;
2457  }
2458  if (h==testHomog)
2459  {
2460  if (strat->ak == 0)
2461  {
2462  h = (tHomog)idHomIdeal(F,Q);
2463  w=NULL;
2464  }
2465  else if (!TEST_OPT_DEGBOUND)
2466  {
2467  if (w!=NULL)
2468  h = (tHomog)idHomModule(F,Q,w);
2469  else
2470  h = (tHomog)idHomIdeal(F,Q);
2471  }
2472  }
2473  currRing->pLexOrder=b;
2474  if (h==isHomog)
2475  {
2476  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2477  {
2478  strat->kModW = kModW = *w;
2479  if (vw == NULL)
2480  {
2481  strat->pOrigFDeg = currRing->pFDeg;
2482  strat->pOrigLDeg = currRing->pLDeg;
2484  toReset = TRUE;
2485  }
2486  }
2487  currRing->pLexOrder = TRUE;
2488  if (hilb==NULL) strat->LazyPass*=2;
2489  }
2490  strat->homog=h;
2491 #ifdef KDEBUG
2492  idTest(F);
2493  if (Q!=NULL) idTest(Q);
2494 #endif
2495 #ifdef HAVE_PLURAL
2496  if (rIsPluralRing(currRing))
2497  {
2498  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2499  strat->no_prod_crit = ! bIsSCA;
2500  if (w!=NULL)
2501  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2502  else
2503  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2504  }
2505  else
2506 #endif
2507  {
2508  #if PRE_INTEGER_CHECK
2509  //the preinteger check strategy is not for modules
2510  if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2511  {
2512  ideal FCopy = idCopy(F);
2513  poly pFmon = preIntegerCheck(FCopy, Q);
2514  if(pFmon != NULL)
2515  {
2516  idInsertPoly(FCopy, pFmon);
2517  strat->kModW=kModW=NULL;
2518  if (h==testHomog)
2519  {
2520  if (strat->ak == 0)
2521  {
2522  h = (tHomog)idHomIdeal(FCopy,Q);
2523  w=NULL;
2524  }
2525  else if (!TEST_OPT_DEGBOUND)
2526  {
2527  if (w!=NULL)
2528  h = (tHomog)idHomModule(FCopy,Q,w);
2529  else
2530  h = (tHomog)idHomIdeal(FCopy,Q);
2531  }
2532  }
2533  currRing->pLexOrder=b;
2534  if (h==isHomog)
2535  {
2536  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2537  {
2538  strat->kModW = kModW = *w;
2539  if (vw == NULL)
2540  {
2541  strat->pOrigFDeg = currRing->pFDeg;
2542  strat->pOrigLDeg = currRing->pLDeg;
2544  toReset = TRUE;
2545  }
2546  }
2547  currRing->pLexOrder = TRUE;
2548  if (hilb==NULL) strat->LazyPass*=2;
2549  }
2550  strat->homog=h;
2551  }
2552  omTestMemory(1);
2553  if(w == NULL)
2554  {
2556  r=mora(FCopy,Q,NULL,hilb,strat);
2557  else
2558  r=bba(FCopy,Q,NULL,hilb,strat);
2559  }
2560  else
2561  {
2563  r=mora(FCopy,Q,*w,hilb,strat);
2564  else
2565  r=bba(FCopy,Q,*w,hilb,strat);
2566  }
2567  idDelete(&FCopy);
2568  }
2569  else
2570  #endif
2571  {
2572  if(w==NULL)
2573  {
2575  r=mora(F,Q,NULL,hilb,strat);
2576  else
2577  r=bba(F,Q,NULL,hilb,strat);
2578  }
2579  else
2580  {
2582  r=mora(F,Q,*w,hilb,strat);
2583  else
2584  r=bba(F,Q,*w,hilb,strat);
2585  }
2586  }
2587  }
2588 #ifdef KDEBUG
2589  idTest(r);
2590 #endif
2591  if (toReset)
2592  {
2593  kModW = NULL;
2594  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2595  }
2596  currRing->pLexOrder = b;
2597 //Print("%d reductions canceled \n",strat->cel);
2598  HCord=strat->HCord;
2599  delete(strat);
2600  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2601  return r;
2602 }
s_poly_proc_t s_poly
Definition: kutil.h:297
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:840
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2900
poly preIntegerCheck(const ideal Forig, const ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition: kutil.cc:11107
omError_t omTestMemory(int check_level)
Definition: omDebug.c:94
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411

◆ kStdShift()

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

Definition at line 2900 of file kstd1.cc.

2902 {
2904  assume(idIsInV(F));
2905  ideal r;
2906  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2907  BOOLEAN delete_w=(w==NULL);
2908  kStrategy strat=new skStrategy;
2909  intvec* temp_w=NULL;
2910 
2911  strat->rightGB = rightGB;
2912 
2913  if(!TEST_OPT_RETURN_SB)
2914  strat->syzComp = syzComp;
2915  if (TEST_OPT_SB_1)
2916  if(!rField_is_Ring(currRing))
2917  strat->newIdeal = newIdeal;
2919  strat->LazyPass=20;
2920  else
2921  strat->LazyPass=2;
2922  strat->LazyDegree = 1;
2923  strat->ak = id_RankFreeModule(F,currRing);
2924  strat->kModW=kModW=NULL;
2925  strat->kHomW=kHomW=NULL;
2926  if (vw != NULL)
2927  {
2928  currRing->pLexOrder=FALSE;
2929  strat->kHomW=kHomW=vw;
2930  strat->pOrigFDeg = currRing->pFDeg;
2931  strat->pOrigLDeg = currRing->pLDeg;
2933  toReset = TRUE;
2934  }
2935  if (h==testHomog)
2936  {
2937  if (strat->ak == 0)
2938  {
2939  h = (tHomog)idHomIdeal(F,Q);
2940  w=NULL;
2941  }
2942  else if (!TEST_OPT_DEGBOUND)
2943  {
2944  if (w!=NULL)
2945  h = (tHomog)idHomModule(F,Q,w);
2946  else
2947  h = (tHomog)idHomIdeal(F,Q);
2948  }
2949  }
2950  currRing->pLexOrder=b;
2951  if (h==isHomog)
2952  {
2953  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2954  {
2955  strat->kModW = kModW = *w;
2956  if (vw == NULL)
2957  {
2958  strat->pOrigFDeg = currRing->pFDeg;
2959  strat->pOrigLDeg = currRing->pLDeg;
2961  toReset = TRUE;
2962  }
2963  }
2964  currRing->pLexOrder = TRUE;
2965  if (hilb==NULL) strat->LazyPass*=2;
2966  }
2967  strat->homog=h;
2968 #ifdef KDEBUG
2969  idTest(F);
2970 #endif
2972  {
2973  /* error: no local ord yet with shifts */
2974  WerrorS("No local ordering possible for shift algebra");
2975  return(NULL);
2976  }
2977  else
2978  {
2979  /* global ordering */
2980  if (w!=NULL)
2981  r=bbaShift(F,Q,*w,hilb,strat);
2982  else
2983  r=bbaShift(F,Q,NULL,hilb,strat);
2984  }
2985 #ifdef KDEBUG
2986  idTest(r);
2987 #endif
2988  if (toReset)
2989  {
2990  kModW = NULL;
2991  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2992  }
2993  currRing->pLexOrder = b;
2994 //Print("%d reductions canceled \n",strat->cel);
2995  HCord=strat->HCord;
2996  delete(strat);
2997  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2998  assume(idIsInV(r));
2999  return r;
3000 }
char rightGB
Definition: kutil.h:369
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4340
#define idIsInV(I)
Definition: shiftop.h:49

◆ kVerify()

BOOLEAN kVerify ( ideal  F,
ideal  Q 
)

◆ mora()

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

Definition at line 1848 of file kstd1.cc.

1849 {
1850  int olddeg = 0;
1851  int reduc = 0;
1852  int red_result = 1;
1853  int hilbeledeg=1,hilbcount=0;
1854  BITSET save1;
1855  SI_SAVE_OPT1(save1);
1857  {
1858  si_opt_1 &= ~Sy_bit(OPT_REDSB);
1860  }
1861 
1862  strat->update = TRUE;
1863  /*- setting global variables ------------------- -*/
1864  initBuchMoraCrit(strat);
1865  initHilbCrit(F,Q,&hilb,strat);
1866  initMora(F,strat);
1868  initBuchMoraPosRing(strat);
1869  else
1870  initBuchMoraPos(strat);
1871  /*Shdl=*/initBuchMora(F,Q,strat);
1872  if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1873  /*updateS in initBuchMora has Hecketest
1874  * and could have put strat->kHEdgdeFound FALSE*/
1875  if ((currRing->ppNoether)!=NULL)
1876  {
1877  strat->kHEdgeFound = TRUE;
1878  }
1879  if (strat->kHEdgeFound && strat->update)
1880  {
1881  firstUpdate(strat);
1882  updateLHC(strat);
1883  reorderL(strat);
1884  }
1885  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1886  {
1887  strat->posInLOld = strat->posInL;
1888  strat->posInLOldFlag = FALSE;
1889  strat->posInL = posInL10;
1890  updateL(strat);
1891  reorderL(strat);
1892  }
1893  kTest_TS(strat);
1894  strat->use_buckets = kMoraUseBucket(strat);
1895 
1896 #ifdef HAVE_TAIL_RING
1897  if (strat->homog && strat->red == redFirst)
1898  if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1899  kStratInitChangeTailRing(strat);
1900 #endif
1901 
1902  if (BVERBOSE(23))
1903  {
1904  kDebugPrint(strat);
1905  }
1906 //deleteInL(strat->L,&strat->Ll,1,strat);
1907 //deleteInL(strat->L,&strat->Ll,0,strat);
1908 
1909  /*- compute-------------------------------------------*/
1910  while (strat->Ll >= 0)
1911  {
1912  #ifdef KDEBUG
1913  if (TEST_OPT_DEBUG) messageSets(strat);
1914  #endif
1915  if (siCntrlc)
1916  {
1917  while (strat->Ll >= 0)
1918  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1919  strat->noClearS=TRUE;
1920  }
1921  if (TEST_OPT_DEGBOUND
1922  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1923  {
1924  /*
1925  * stops computation if
1926  * - 24 (degBound)
1927  * && upper degree is bigger than Kstd1_deg
1928  */
1929  while ((strat->Ll >= 0)
1930  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1931  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1932  )
1933  {
1934  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1935  //if (TEST_OPT_PROT)
1936  //{
1937  // PrintS("D"); mflush();
1938  //}
1939  }
1940  if (strat->Ll<0) break;
1941  else strat->noClearS=TRUE;
1942  }
1943  strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1944  if (strat->Ll==0) strat->interpt=TRUE;
1945  strat->Ll--;
1946  // create the real Spoly
1947  if (pNext(strat->P.p) == strat->tail)
1948  {
1949  /*- deletes the short spoly and computes -*/
1950  if (rField_is_Ring(currRing))
1951  pLmDelete(strat->P.p);
1952  else
1953  pLmFree(strat->P.p);
1954  strat->P.p = NULL;
1955  poly m1 = NULL, m2 = NULL;
1956  // check that spoly creation is ok
1957  while (strat->tailRing != currRing &&
1958  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1959  {
1960  assume(m1 == NULL && m2 == NULL);
1961  // if not, change to a ring where exponents are large enough
1962  kStratChangeTailRing(strat);
1963  }
1964  /* create the real one */
1965  ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1966  strat->tailRing, m1, m2, strat->R);
1967  if (!strat->use_buckets)
1968  strat->P.SetLength(strat->length_pLength);
1969  }
1970  else if (strat->P.p1 == NULL)
1971  {
1972  // for input polys, prepare reduction (buckets !)
1973  strat->P.SetLength(strat->length_pLength);
1974  strat->P.PrepareRed(strat->use_buckets);
1975  }
1976 
1977  // the s-poly
1978  if (!strat->P.IsNull())
1979  {
1980  // might be NULL from noether !!!
1981  if (TEST_OPT_PROT)
1982  message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1983  // reduce
1984  red_result = strat->red(&strat->P,strat);
1985  }
1986 
1987  // the reduced s-poly
1988  if (! strat->P.IsNull())
1989  {
1990  strat->P.GetP();
1991  // statistics
1992  if (TEST_OPT_PROT) PrintS("s");
1993  // normalization
1995  strat->P.pCleardenom();
1996  else
1997  strat->P.pNorm();
1998  // tailreduction
1999  strat->P.p = redtail(&(strat->P),strat->sl,strat);
2000  if (strat->P.p==NULL)
2001  {
2002  WerrorS("expoent overflow - wrong ordering");
2003  return(idInit(1,1));
2004  }
2005  // set ecart -- might have changed because of tail reductions
2006  if ((!strat->noTailReduction) && (!strat->honey))
2007  strat->initEcart(&strat->P);
2008  // cancel unit
2009  cancelunit(&strat->P);
2010  // for char 0, clear denominators
2011  if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2013  strat->P.pCleardenom();
2014 
2015  enterT(strat->P,strat);
2016  // build new pairs
2017  if (rField_is_Ring(currRing))
2018  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2019  else
2020  enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2021  // put in S
2022  strat->enterS(strat->P,
2023  posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2024  strat, strat->tl);
2025  // apply hilbert criterion
2026  if (hilb!=NULL)
2027  {
2028  if (strat->homog==isHomog)
2029  khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2030  else
2031  khCheckLocInhom(Q,w,hilb,hilbcount,strat);
2032  }
2033 
2034  // clear strat->P
2035  kDeleteLcm(&strat->P);
2036 
2037 #ifdef KDEBUG
2038  // make sure kTest_TS does not complain about strat->P
2039  strat->P.Clear();
2040 #endif
2041  }
2042  if (strat->kHEdgeFound)
2043  {
2044  if ((TEST_OPT_FINDET)
2045  || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL,strat->tailRing) < Kstd1_mu)))
2046  {
2047  // obachman: is this still used ???
2048  /*
2049  * stops computation if strat->kHEdgeFound and
2050  * - 27 (finiteDeterminacyTest)
2051  * or
2052  * - 23
2053  * (multBound)
2054  * && multiplicity of the ideal is smaller then a predefined number mu
2055  */
2056  while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2057  }
2058  }
2059  kTest_TS(strat);
2060  }
2061  /*- complete reduction of the standard basis------------------------ -*/
2062  if (TEST_OPT_REDSB) completeReduce(strat);
2063  else if (TEST_OPT_PROT) PrintLn();
2064  /*- release temp data------------------------------- -*/
2065  exitBuchMora(strat);
2066  /*- polynomials used for HECKE: HC, noether -*/
2067  if (TEST_OPT_FINDET)
2068  {
2069  if (strat->kHEdge!=NULL)
2070  Kstd1_mu=currRing->pFDeg(strat->kHEdge,currRing);
2071  else
2072  Kstd1_mu=-1;
2073  }
2074  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2075  strat->update = TRUE; //???
2076  strat->lastAxis = 0; //???
2077  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2078  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2079  if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2080 // if (TEST_OPT_WEIGHTM)
2081 // {
2082 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2083 // if (ecartWeights)
2084 // {
2085 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2086 // ecartWeights=NULL;
2087 // }
2088 // }
2089  if(nCoeff_is_Z(currRing->cf))
2090  finalReduceByMon(strat);
2091  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2092  SI_RESTORE_OPT1(save1);
2093  idTest(strat->Shdl);
2094  return (strat->Shdl);
2095 }
KINLINE poly kNoetherTail()
Definition: kInline.h:66
ring tailRing
Definition: kutil.h:342
int Ll
Definition: kutil.h:350
int lastAxis
Definition: kutil.h:355
poly tail
Definition: kutil.h:333
char use_buckets
Definition: kutil.h:383
char interpt
Definition: kutil.h:371
LObject P
Definition: kutil.h:299
char noClearS
Definition: kutil.h:402
char length_pLength
Definition: kutil.h:387
char update
Definition: kutil.h:381
int scMult0Int(ideal S, ideal Q, const ring tailRing)
Definition: hdegree.cc:992
void khCheckLocInhom(ideal Q, intvec *w, intvec *hilb, int &count, kStrategy strat)
Definition: khstd.cc:133
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
Definition: khstd.cc:28
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:1167
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1528
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1435
void missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:1250
void reorderL(kStrategy strat)
Definition: kstd1.cc:1192
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1331
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3810
void updateL(kStrategy strat)
Definition: kstd1.cc:1364
EXTERN_VAR int Kstd1_mu
Definition: kstd1.h:49
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:8033
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10322
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1071
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4933
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9979
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11532
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10406
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5109
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:11045
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10647
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4902
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1244
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11632
void messageSets(kStrategy strat)
Definition: kutil.cc:8106
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:8074
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11439
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:343
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
VAR BOOLEAN siCntrlc
Definition: options.c:14
#define TEST_OPT_FINDET
Definition: options.h:110
#define OPT_REDSB
Definition: options.h:75
#define TEST_OPT_MULTBOUND
Definition: options.h:113
#define TEST_OPT_FASTHC
Definition: options.h:108
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:766

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4703 of file kstd2.cc.

4704 {
4706  assume(idIsInV(F));
4707  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4708  idSkipZeroes(RS); // is this even necessary?
4709  assume(idIsInV(RS));
4710  return(RS);
4711 }

◆ stdred()

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

Variable Documentation

◆ kHomW

Definition at line 70 of file kstd1.h.

◆ kModW

Definition at line 69 of file kstd1.h.

◆ kOptions

EXTERN_VAR BITSET kOptions

Definition at line 51 of file kstd1.h.

◆ Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 49 of file kstd1.h.

◆ Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 49 of file kstd1.h.

◆ LazyDegree

EXTERN_VAR int LazyDegree

Definition at line 49 of file kstd1.h.

◆ LazyPass

EXTERN_VAR int LazyPass

Definition at line 49 of file kstd1.h.

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 53 of file kstd1.h.