My Project  debian-1:4.1.2-p1+ds-2
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 freegb (ideal F, ideal Q)
 
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)
 

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

◆ freegb()

ideal freegb ( ideal  F,
ideal  Q 
)

Definition at line 4461 of file kstd2.cc.

4462 {
4464  assume(idIsInV(F));
4465  ideal RS = kStdShift(F, Q, testHomog, NULL);
4466  idSkipZeroes(RS); // is this even necessary?
4467  assume(idIsInV(RS));
4468  return(RS);
4469 }
STATIC_VAR jList * Q
Definition: janet.cc:30
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2569
#define assume(x)
Definition: mod2.h:390
#define NULL
Definition: omList.c:12
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:408
#define idIsInV(I)
Definition: shiftop.h:49
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
@ testHomog
Definition: structs.h:43

◆ initMora()

void initMora ( ideal  F,
kStrategy  strat 
)

Definition at line 1460 of file kstd1.cc.

1461 {
1462  int i,j;
1463 
1464  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1465  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1466  strat->enterS = enterSMora;
1467  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1468  strat->posInLOld = strat->posInL;
1469  strat->posInLOldFlag = TRUE;
1470  strat->initEcart = initEcartNormal;
1471  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1472  if ( strat->kHEdgeFound )
1473  strat->kNoether = pCopy((currRing->ppNoether));
1474  else if (strat->kHEdgeFound || strat->homog)
1475  strat->red = redFirst; /*take the first possible in T*/
1476  else
1477  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1478  if (strat->kHEdgeFound)
1479  {
1480  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1481  strat->posInT = posInT2;
1482  }
1483  else
1484  {
1485  strat->HCord = 32000;/*- very large -*/
1486  }
1487 
1488  if (rField_is_Ring(currRing))
1489  strat->red = redRiloc;
1490 
1491  /*reads the ecartWeights used for Graebes method from the
1492  *intvec ecart and set ecartWeights
1493  */
1494  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1495  {
1496  //interred machen Aenderung
1497  strat->pOrigFDeg=currRing->pFDeg;
1498  strat->pOrigLDeg=currRing->pLDeg;
1499  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1500  /*uses automatic computation of the ecartWeights to set them*/
1502 
1504  if (TEST_OPT_PROT)
1505  {
1506  for(i=1; i<=(currRing->N); i++)
1507  Print(" %d",ecartWeights[i]);
1508  PrintLn();
1509  mflush();
1510  }
1511  }
1512  kOptimizeLDeg(currRing->pLDeg, strat);
1513 }
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
int i
Definition: cfEzgcd.cc:125
char posInLOldFlag
Definition: kutil.h:381
poly kNoether
Definition: kutil.h:326
BOOLEAN * NotUsedAxis
Definition: kutil.h:330
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:280
pFDegProc pOrigFDeg
Definition: kutil.h:292
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:284
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:283
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:282
void(* initEcart)(TObject *L)
Definition: kutil.h:276
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:277
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:274
char kHEdgeFound
Definition: kutil.h:375
int HCord
Definition: kutil.h:353
char homog
Definition: kutil.h:371
pLDegProc pOrigLDeg
Definition: kutil.h:293
#define Print
Definition: emacs.cc:80
int j
Definition: facHensel.cc:105
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:528
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:166
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:97
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:342
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1270
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5296
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1306
void initEcartNormal(TObject *h)
Definition: kutil.cc:1284
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define TEST_OPT_WEIGHTM
Definition: options.h:118
#define TEST_OPT_PROT
Definition: options.h:101
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3597
#define pCopy(p)
return a copy of the poly
Definition: polys.h:181
void PrintLn()
Definition: reporter.cc:310
#define mflush()
Definition: reporter.h:57
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:479
#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 3035 of file kstd1.cc.

3036 {
3037  const ring save = currRing;
3038  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3039  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3040  if( currRing != save ) rChangeCurrRing(save);
3041  return ret;
3042 }
int p
Definition: cfModGcd.cc:4019
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2824
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2075 of file kstd1.cc.

2076 {
2077  int i;
2078  long j=0;
2079 
2080  for (i=r->N;i>0;i--)
2081  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2082  if (kModW == NULL) return j;
2083  i = __p_GetComp(p,r);
2084  if (i==0) return j;
2085  return j+(*kModW)[i-1];
2086 }
VAR intvec * kModW
Definition: kstd1.cc:2063
#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:468

◆ kInterRed()

ideal kInterRed ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3400 of file kstd1.cc.

3401 {
3402 #ifdef HAVE_PLURAL
3403  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3404 #endif
3407  )
3408  return kInterRedOld(F,Q);
3409 
3410  //return kInterRedOld(F,Q);
3411 
3412  BITSET save1;
3413  SI_SAVE_OPT1(save1);
3414  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3416  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3417  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3418  //extern char * showOption() ;
3419  //Print("%s\n",showOption());
3420 
3421  int need_retry;
3422  int counter=3;
3423  ideal res, res1;
3424  int elems;
3425  ideal null=NULL;
3426  if ((Q==NULL) || (!TEST_OPT_REDSB))
3427  {
3428  elems=idElem(F);
3429  res=kInterRedBba(F,Q,need_retry);
3430  }
3431  else
3432  {
3433  ideal FF=idSimpleAdd(F,Q);
3434  res=kInterRedBba(FF,NULL,need_retry);
3435  idDelete(&FF);
3436  null=idInit(1,1);
3437  if (need_retry)
3438  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3439  else
3440  res1=kNF(null,Q,res);
3441  idDelete(&res);
3442  res=res1;
3443  need_retry=1;
3444  }
3445  if (idElem(res)<=1) need_retry=0;
3446  while (need_retry && (counter>0))
3447  {
3448  #ifdef KDEBUG
3449  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3450  #endif
3451  res1=kInterRedBba(res,Q,need_retry);
3452  int new_elems=idElem(res1);
3453  counter -= (new_elems >= elems);
3454  elems = new_elems;
3455  idDelete(&res);
3456  if (idElem(res1)<=1) need_retry=0;
3457  if ((Q!=NULL) && (TEST_OPT_REDSB))
3458  {
3459  if (need_retry)
3460  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3461  else
3462  res=kNF(null,Q,res1);
3463  idDelete(&res1);
3464  }
3465  else
3466  res = res1;
3467  if (idElem(res)<=1) need_retry=0;
3468  }
3469  if (null!=NULL) idDelete(&null);
3470  SI_RESTORE_OPT1(save1);
3471  idSkipZeroes(res);
3472  return res;
3473 }
CanonicalForm res
Definition: facAbsFact.cc:64
#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:3048
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3140
#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:80
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:102
#define TEST_OPT_DEBUG
Definition: options.h:106
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:397
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:510
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:755
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
int idElem(const ideal F)
count non-zero elements
#define BITSET
Definition: structs.h:20

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3048 of file kstd1.cc.

3049 {
3050  int j;
3051  kStrategy strat = new skStrategy;
3052 
3053  ideal tempF = F;
3054  ideal tempQ = Q;
3055 
3056 #ifdef HAVE_PLURAL
3057  if(rIsSCA(currRing))
3058  {
3059  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3060  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3061  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3062 
3063  // this should be done on the upper level!!! :
3064  // tempQ = SCAQuotient(currRing);
3065 
3066  if(Q == currRing->qideal)
3067  tempQ = SCAQuotient(currRing);
3068  }
3069 #endif
3070 
3071 // if (TEST_OPT_PROT)
3072 // {
3073 // writeTime("start InterRed:");
3074 // mflush();
3075 // }
3076  //strat->syzComp = 0;
3077  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3078  strat->kNoether=pCopy((currRing->ppNoether));
3079  strat->ak = id_RankFreeModule(tempF,currRing);
3080  initBuchMoraCrit(strat);
3081  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3082  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3083  strat->enterS = enterSBba;
3084  strat->posInT = posInT17;
3085  strat->initEcart = initEcartNormal;
3086  strat->sl = -1;
3087  strat->tl = -1;
3088  strat->tmax = setmaxT;
3089  strat->T = initT();
3090  strat->R = initR();
3091  strat->sevT = initsevT();
3093  initS(tempF, tempQ, strat);
3094  if (TEST_OPT_REDSB)
3095  strat->noTailReduction=FALSE;
3096  updateS(TRUE,strat);
3098  completeReduce(strat);
3099  //else if (TEST_OPT_PROT) PrintLn();
3100  cleanT(strat);
3101  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3102  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3103  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3104  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3105  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3106  omfree(strat->sevT);
3107  omfree(strat->S_2_R);
3108  omfree(strat->R);
3109 
3110  if (strat->fromQ)
3111  {
3112  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3113  {
3114  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3115  }
3116  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3117  }
3118 // if (TEST_OPT_PROT)
3119 // {
3120 // writeTime("end Interred:");
3121 // mflush();
3122 // }
3123  ideal shdl=strat->Shdl;
3124  idSkipZeroes(shdl);
3125  if (strat->fromQ)
3126  {
3127  strat->fromQ=NULL;
3128  ideal res=kInterRed(shdl,NULL);
3129  idDelete(&shdl);
3130  shdl=res;
3131  }
3132  delete(strat);
3133 #ifdef HAVE_PLURAL
3134  if( tempF != F )
3135  id_Delete( &tempF, currRing);
3136 #endif
3137  return shdl;
3138 }
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:135
int * S_2_R
Definition: kutil.h:340
char noTailReduction
Definition: kutil.h:377
TSet T
Definition: kutil.h:322
intset ecartS
Definition: kutil.h:305
char honey
Definition: kutil.h:376
int ak
Definition: kutil.h:351
TObject ** R
Definition: kutil.h:338
poly kHEdge
Definition: kutil.h:325
int tl
Definition: kutil.h:348
unsigned long * sevT
Definition: kutil.h:321
ideal Shdl
Definition: kutil.h:299
int tmax
Definition: kutil.h:348
intset fromQ
Definition: kutil.h:317
int sl
Definition: kutil.h:346
unsigned long * sevS
Definition: kutil.h:318
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:3400
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5731
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8077
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:9036
void cleanT(kStrategy strat)
Definition: kutil.cc:538
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9884
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10745
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9271
#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:108
#define pDelete(p_ptr)
Definition: polys.h:182
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 2675 of file kstd1.cc.

2677 {
2678  if(idIs0(F))
2679  {
2680  M=idInit(1,F->rank);
2681  return idInit(1,F->rank);
2682  }
2684  {
2685  ideal sb;
2686  sb = kStd(F, Q, h, w, hilb);
2687  idSkipZeroes(sb);
2688  if(IDELEMS(sb) <= IDELEMS(F))
2689  {
2690  M = idCopy(sb);
2691  idSkipZeroes(M);
2692  return(sb);
2693  }
2694  else
2695  {
2696  M = idCopy(F);
2697  idSkipZeroes(M);
2698  return(sb);
2699  }
2700  }
2701  ideal r=NULL;
2702  int Kstd1_OldDeg = Kstd1_deg,i;
2703  intvec* temp_w=NULL;
2704  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2705  BOOLEAN delete_w=(w==NULL);
2706  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
2707  kStrategy strat=new skStrategy;
2708 
2709  if(!TEST_OPT_RETURN_SB)
2710  strat->syzComp = syzComp;
2712  strat->LazyPass=20;
2713  else
2714  strat->LazyPass=2;
2715  strat->LazyDegree = 1;
2716  strat->minim=(reduced % 2)+1;
2717  strat->ak = id_RankFreeModule(F,currRing);
2718  if (delete_w)
2719  {
2720  temp_w=new intvec((strat->ak)+1);
2721  w = &temp_w;
2722  }
2723  if (h==testHomog)
2724  {
2725  if (strat->ak == 0)
2726  {
2727  h = (tHomog)idHomIdeal(F,Q);
2728  w=NULL;
2729  }
2730  else
2731  {
2732  h = (tHomog)idHomModule(F,Q,w);
2733  }
2734  }
2735  if (h==isHomog)
2736  {
2737  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2738  {
2739  kModW = *w;
2740  strat->kModW = *w;
2741  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
2742  strat->pOrigFDeg = currRing->pFDeg;
2743  strat->pOrigLDeg = currRing->pLDeg;
2745 
2746  toReset = TRUE;
2747  if (reduced>1)
2748  {
2749  Kstd1_OldDeg=Kstd1_deg;
2750  Kstd1_deg = -1;
2751  for (i=IDELEMS(F)-1;i>=0;i--)
2752  {
2753  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
2754  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
2755  }
2756  }
2757  }
2758  currRing->pLexOrder = TRUE;
2759  strat->LazyPass*=2;
2760  }
2761  strat->homog=h;
2763  {
2764  if (w!=NULL)
2765  r=mora(F,Q,*w,hilb,strat);
2766  else
2767  r=mora(F,Q,NULL,hilb,strat);
2768  }
2769  else
2770  {
2771  if (w!=NULL)
2772  r=bba(F,Q,*w,hilb,strat);
2773  else
2774  r=bba(F,Q,NULL,hilb,strat);
2775  }
2776 #ifdef KDEBUG
2777  {
2778  int i;
2779  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
2780  }
2781 #endif
2782  idSkipZeroes(r);
2783  if (toReset)
2784  {
2785  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2786  kModW = NULL;
2787  }
2788  currRing->pLexOrder = b;
2789  HCord=strat->HCord;
2790  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
2791  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
2792  {
2793  M=idInit(1,F->rank);
2794  M->m[0]=pOne();
2795  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
2796  if (strat->M!=NULL) idDelete(&strat->M);
2797  }
2798  else if (strat->M==NULL)
2799  {
2800  M=idInit(1,F->rank);
2801  WarnS("no minimal generating set computed");
2802  }
2803  else
2804  {
2805  idSkipZeroes(strat->M);
2806  M=strat->M;
2807  }
2808  delete(strat);
2809  if (reduced>2)
2810  {
2811  Kstd1_deg=Kstd1_OldDeg;
2812  if (!oldDegBound)
2814  }
2815  else
2816  {
2817  if (IDELEMS(M)>IDELEMS(r)) {
2818  idDelete(&M);
2819  M=idCopy(r); }
2820  }
2821  return r;
2822 }
CanonicalForm b
Definition: cfModGcd.cc:4044
Definition: intvec.h:23
intvec * kModW
Definition: kutil.h:333
int syzComp
Definition: kutil.h:352
int minim
Definition: kutil.h:356
ideal M
Definition: kutil.h:301
int LazyPass
Definition: kutil.h:351
int LazyDegree
Definition: kutil.h:351
#define WarnS
Definition: emacs.cc:78
const CanonicalForm & w
Definition: facAbsFact.cc:55
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:1517
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2065
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:2088
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:50
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2178
VAR int HCord
Definition: kutil.cc:236
#define TEST_OPT_DEGBOUND
Definition: options.h:111
#define TEST_OPT_RETURN_SB
Definition: options.h:110
#define OPT_DEGBOUND
Definition: options.h:88
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3609
#define pTest(p)
Definition: polys.h:411
#define pIsConstant(p)
like above, except that Comp must be 0
Definition: polys.h:234
#define pOne()
Definition: polys.h:311
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:543
#define M
Definition: sirandom.c:25
tHomog
Definition: structs.h:40
@ isHomog
Definition: structs.h:42

◆ kModDeg()

long kModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2065 of file kstd1.cc.

2066 {
2067  long o=p_WDegree(p, r);
2068  long i=__p_GetComp(p, r);
2069  if (i==0) return o;
2070  //assume((i>0) && (i<=kModW->length()));
2071  if (i<=kModW->length())
2072  return o+(*kModW)[i-1];
2073  return o;
2074 }
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:704

◆ kNF() [1/2]

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

Definition at line 2921 of file kstd1.cc.

2922 {
2923  ideal res;
2924  if (TEST_OPT_PROT)
2925  {
2926  Print("(S:%d)",IDELEMS(p));mflush();
2927  }
2928  if (idIs0(p))
2929  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
2930 
2931  ideal pp = p;
2932 #ifdef HAVE_PLURAL
2933  if(rIsSCA(currRing))
2934  {
2935  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2936  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2937  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
2938 
2939  if(Q == currRing->qideal)
2940  Q = SCAQuotient(currRing);
2941  }
2942 #endif
2943 
2944  if ((idIs0(F))&&(Q==NULL))
2945  {
2946 #ifdef HAVE_PLURAL
2947  if(p != pp)
2948  return pp;
2949 #endif
2950  return idCopy(p); /*F+Q=0*/
2951  }
2952 
2953  kStrategy strat=new skStrategy;
2954  strat->syzComp = syzComp;
2956  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
2957  {
2958  strat->ak = si_max(strat->ak,(int)F->rank);
2959  }
2960 
2962  {
2963 #ifdef HAVE_SHIFTBBA
2964  if (currRing->isLPring)
2965  {
2966  WerrorS("No local ordering possible for shift algebra");
2967  return(NULL);
2968  }
2969 #endif
2970  res=kNF1(F,Q,pp,strat,lazyReduce);
2971  }
2972  else
2973  res=kNF2(F,Q,pp,strat,lazyReduce);
2974  delete(strat);
2975 
2976 #ifdef HAVE_PLURAL
2977  if(pp != p)
2978  id_Delete(&pp, currRing);
2979 #endif
2980 
2981  return res;
2982 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:140
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
void WerrorS(const char *s)
Definition: feFopen.cc:24
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:1766
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3503

◆ kNF() [2/2]

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

Definition at line 2824 of file kstd1.cc.

2825 {
2826  if (p==NULL)
2827  return NULL;
2828 
2829  poly pp = p;
2830 
2831 #ifdef HAVE_PLURAL
2832  if(rIsSCA(currRing))
2833  {
2834  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2835  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2836  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
2837 
2838  if(Q == currRing->qideal)
2839  Q = SCAQuotient(currRing);
2840  }
2841 #endif
2842 
2843  if ((idIs0(F))&&(Q==NULL))
2844  {
2845 #ifdef HAVE_PLURAL
2846  if(p != pp)
2847  return pp;
2848 #endif
2849  return pCopy(p); /*F+Q=0*/
2850  }
2851 
2852  kStrategy strat=new skStrategy;
2853  strat->syzComp = syzComp;
2854  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
2855  poly res;
2856 
2858  {
2859 #ifdef HAVE_SHIFTBBA
2860  if (currRing->isLPring)
2861  {
2862  WerrorS("No local ordering possible for shift algebra");
2863  return(NULL);
2864  }
2865 #endif
2866  res=kNF1(F,Q,pp,strat,lazyReduce);
2867  }
2868  else
2869  res=kNF2(F,Q,pp,strat,lazyReduce);
2870  delete(strat);
2871 
2872 #ifdef HAVE_PLURAL
2873  if(pp != p)
2874  p_Delete(&pp, currRing);
2875 #endif
2876  return res;
2877 }
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:860
#define pMaxComp(p)
Definition: polys.h:295

◆ kNF1() [1/2]

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

Definition at line 1910 of file kstd1.cc.

1911 {
1912  assume(!idIs0(q));
1913  assume(!(idIs0(F)&&(Q==NULL)));
1914 
1915 // lazy_reduce flags: can be combined by |
1916 //#define KSTD_NF_LAZY 1
1917  // do only a reduction of the leading term
1918 //#define KSTD_NF_ECART 2
1919  // only local: recude even with bad ecart
1920  poly p;
1921  int i;
1922  int j;
1923  int o;
1924  LObject h;
1925  ideal res;
1926  BITSET save1;
1927  SI_SAVE_OPT1(save1);
1928 
1929  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
1930  //if ((idIs0(F))&&(Q==NULL))
1931  // return idCopy(q); /*F=0*/
1932  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
1933  /*- creating temp data structures------------------- -*/
1934  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1935  strat->kNoether=pCopy((currRing->ppNoether));
1938  && (0<Kstd1_deg)
1939  && ((!strat->kHEdgeFound)
1941  {
1942  pLmDelete(&strat->kNoether);
1943  strat->kNoether=pOne();
1944  pSetExp(strat->kNoether,1, Kstd1_deg+1);
1945  pSetm(strat->kNoether);
1946  strat->kHEdgeFound=TRUE;
1947  }
1948  initBuchMoraCrit(strat);
1950  initBuchMoraPosRing(strat);
1951  else
1952  initBuchMoraPos(strat);
1953  initMora(F,strat);
1954  strat->enterS = enterSMoraNF;
1955  /*- set T -*/
1956  strat->tl = -1;
1957  strat->tmax = setmaxT;
1958  strat->T = initT();
1959  strat->R = initR();
1960  strat->sevT = initsevT();
1961  /*- set S -*/
1962  strat->sl = -1;
1963  /*- init local data struct.-------------------------- -*/
1964  /*Shdl=*/initS(F,Q,strat);
1965  if ((strat->ak!=0)
1966  && (strat->kHEdgeFound))
1967  {
1968  if (strat->ak!=1)
1969  {
1970  pSetComp(strat->kNoether,1);
1971  pSetmComp(strat->kNoether);
1972  poly p=pHead(strat->kNoether);
1973  pSetComp(p,strat->ak);
1974  pSetmComp(p);
1975  p=pAdd(strat->kNoether,p);
1976  strat->kNoether=pNext(p);
1978  }
1979  }
1980  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
1981  {
1982  for (i=strat->sl; i>=0; i--)
1983  pNorm(strat->S[i]);
1984  }
1985  /*- compute------------------------------------------- -*/
1986  res=idInit(IDELEMS(q),strat->ak);
1987  for (i=0; i<IDELEMS(q); i++)
1988  {
1989  if (q->m[i]!=NULL)
1990  {
1991  p = pCopy(q->m[i]);
1992  deleteHC(&p,&o,&j,strat);
1993  if (p!=NULL)
1994  {
1995  /*- puts the elements of S also to T -*/
1996  for (j=0; j<=strat->sl; j++)
1997  {
1998  h.p = strat->S[j];
1999  h.ecart = strat->ecartS[j];
2000  h.pLength = h.length = pLength(h.p);
2001  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2002  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2003  h.sev = strat->sevS[j];
2004  h.SetpFDeg();
2006  enterT_strong(h,strat);
2007  else
2008  enterT(h,strat);
2009  }
2010  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2012  {
2013  p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2014  }
2015  else
2016  p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2017  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2018  {
2019  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2020  p = redtail(p,strat->sl,strat);
2021  }
2022  cleanT(strat);
2023  }
2024  res->m[i]=p;
2025  }
2026  //else
2027  // res->m[i]=NULL;
2028  }
2029  /*- release temp data------------------------------- -*/
2030  assume(strat->L==NULL); /*strat->L unsed */
2031  assume(strat->B==NULL); /*strat->B unused */
2032  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2033  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2034  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2035  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2036  omFree(strat->sevT);
2037  omFree(strat->S_2_R);
2038  omFree(strat->R);
2039  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2040  {
2042  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2043  strat->fromQ=NULL;
2044  }
2045  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2046  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2047 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2048 // {
2049 // pFDeg=strat->pOrigFDeg;
2050 // pLDeg=strat->pOrigLDeg;
2051 // if (ecartWeights)
2052 // {
2053 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2054 // ecartWeights=NULL;
2055 // }
2056 // }
2057  idDelete(&strat->Shdl);
2058  SI_RESTORE_OPT1(save1);
2059  if (TEST_OPT_PROT) PrintLn();
2060  return res;
2061 }
polyset S
Definition: kutil.h:302
LSet B
Definition: kutil.h:324
LSet L
Definition: kutil.h:323
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1460
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1324
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:762
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:662
#define KSTD_NF_ECART
Definition: kstd1.h:19
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7405
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9586
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:10035
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9686
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:244
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:10121
#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:89
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:113
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:710
static unsigned pLength(poly a)
Definition: p_polys.h:191
#define pAdd(p, q)
Definition: polys.h:199
#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:267
#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:269
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:359
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pWTotaldegree(p)
Definition: polys.h:279
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 1766 of file kstd1.cc.

1767 {
1768  assume(q!=NULL);
1769  assume(!(idIs0(F)&&(Q==NULL)));
1770 
1771 // lazy_reduce flags: can be combined by |
1772 //#define KSTD_NF_LAZY 1
1773  // do only a reduction of the leading term
1774 //#define KSTD_NF_ECART 2
1775  // only local: recude even with bad ecart
1776  poly p;
1777  int i;
1778  int j;
1779  int o;
1780  LObject h;
1781  BITSET save1;
1782  SI_SAVE_OPT1(save1);
1783 
1784  //if ((idIs0(F))&&(Q==NULL))
1785  // return pCopy(q); /*F=0*/
1786  //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
1787  /*- creating temp data structures------------------- -*/
1788  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1789  strat->kNoether = pCopy((currRing->ppNoether));
1793  && (! TEST_V_DEG_STOP)
1794  && (0<Kstd1_deg)
1795  && ((!strat->kHEdgeFound)
1797  {
1798  pLmDelete(&strat->kNoether);
1799  strat->kNoether=pOne();
1800  pSetExp(strat->kNoether,1, Kstd1_deg+1);
1801  pSetm(strat->kNoether);
1802  strat->kHEdgeFound=TRUE;
1803  }
1804  initBuchMoraCrit(strat);
1806  initBuchMoraPosRing(strat);
1807  else
1808  initBuchMoraPos(strat);
1809  initMora(F,strat);
1810  strat->enterS = enterSMoraNF;
1811  /*- set T -*/
1812  strat->tl = -1;
1813  strat->tmax = setmaxT;
1814  strat->T = initT();
1815  strat->R = initR();
1816  strat->sevT = initsevT();
1817  /*- set S -*/
1818  strat->sl = -1;
1819  /*- init local data struct.-------------------------- -*/
1820  /*Shdl=*/initS(F,Q,strat);
1821  if ((strat->ak!=0)
1822  && (strat->kHEdgeFound))
1823  {
1824  if (strat->ak!=1)
1825  {
1826  pSetComp(strat->kNoether,1);
1827  pSetmComp(strat->kNoether);
1828  poly p=pHead(strat->kNoether);
1829  pSetComp(p,strat->ak);
1830  pSetmComp(p);
1831  p=pAdd(strat->kNoether,p);
1832  strat->kNoether=pNext(p);
1834  }
1835  }
1836  if ((lazyReduce & KSTD_NF_LAZY)==0)
1837  {
1838  for (i=strat->sl; i>=0; i--)
1839  pNorm(strat->S[i]);
1840  }
1841  /*- puts the elements of S also to T -*/
1842  for (i=0; i<=strat->sl; i++)
1843  {
1844  h.p = strat->S[i];
1845  h.ecart = strat->ecartS[i];
1846  if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
1847  else assume(strat->sevS[i] == pGetShortExpVector(h.p));
1848  h.length = pLength(h.p);
1849  h.sev = strat->sevS[i];
1850  h.SetpFDeg();
1851  enterT(h,strat);
1852  }
1853 #ifdef KDEBUG
1854 // kDebugPrint(strat);
1855 #endif
1856  /*- compute------------------------------------------- -*/
1857  p = pCopy(q);
1858  deleteHC(&p,&o,&j,strat);
1859  kTest(strat);
1860  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
1861  if (BVERBOSE(23)) kDebugPrint(strat);
1863  {
1864  if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
1865  }
1866  else
1867  {
1868  if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
1869  }
1870  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
1871  {
1872  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
1873  p = redtail(p,strat->sl,strat);
1874  }
1875  /*- release temp data------------------------------- -*/
1876  cleanT(strat);
1877  assume(strat->L==NULL); /*strat->L unsed */
1878  assume(strat->B==NULL); /*strat->B unused */
1879  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
1880  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
1881  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
1882  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
1883  omFree(strat->sevT);
1884  omFree(strat->S_2_R);
1885  omFree(strat->R);
1886 
1887  if ((Q!=NULL)&&(strat->fromQ!=NULL))
1888  {
1889  i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
1890  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
1891  strat->fromQ=NULL;
1892  }
1893  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
1894  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
1895 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1896 // {
1897 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1898 // if (ecartWeights)
1899 // {
1900 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
1901 // ecartWeights=NULL;
1902 // }
1903 // }
1904  idDelete(&strat->Shdl);
1905  SI_RESTORE_OPT1(save1);
1906  if (TEST_OPT_PROT) PrintLn();
1907  return p;
1908 }
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11949
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:960
#define OPT_INTSTRATEGY
Definition: options.h:90
#define BVERBOSE(a)
Definition: options.h:34
#define TEST_V_DEG_STOP
Definition: options.h:134

◆ kNFBound() [1/2]

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

Definition at line 2984 of file kstd1.cc.

2985 {
2986  ideal res;
2987  if (TEST_OPT_PROT)
2988  {
2989  Print("(S:%d)",IDELEMS(p));mflush();
2990  }
2991  if (idIs0(p))
2992  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
2993 
2994  ideal pp = p;
2995 #ifdef HAVE_PLURAL
2996  if(rIsSCA(currRing))
2997  {
2998  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2999  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3000  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3001 
3002  if(Q == currRing->qideal)
3003  Q = SCAQuotient(currRing);
3004  }
3005 #endif
3006 
3007  if ((idIs0(F))&&(Q==NULL))
3008  {
3009 #ifdef HAVE_PLURAL
3010  if(p != pp)
3011  return pp;
3012 #endif
3013  return idCopy(p); /*F+Q=0*/
3014  }
3015 
3016  kStrategy strat=new skStrategy;
3017  strat->syzComp = syzComp;
3019  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3020  {
3021  strat->ak = si_max(strat->ak,(int)F->rank);
3022  }
3023 
3024  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3025  delete(strat);
3026 
3027 #ifdef HAVE_PLURAL
3028  if(pp != p)
3029  id_Delete(&pp, currRing);
3030 #endif
3031 
3032  return res;
3033 }
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:3596

◆ kNFBound() [2/2]

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

Definition at line 2879 of file kstd1.cc.

2880 {
2881  if (p==NULL)
2882  return NULL;
2883 
2884  poly pp = p;
2885 
2886 #ifdef HAVE_PLURAL
2887  if(rIsSCA(currRing))
2888  {
2889  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2890  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2891  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
2892 
2893  if(Q == currRing->qideal)
2894  Q = SCAQuotient(currRing);
2895  }
2896 #endif
2897 
2898  if ((idIs0(F))&&(Q==NULL))
2899  {
2900 #ifdef HAVE_PLURAL
2901  if(p != pp)
2902  return pp;
2903 #endif
2904  return pCopy(p); /*F+Q=0*/
2905  }
2906 
2907  kStrategy strat=new skStrategy;
2908  strat->syzComp = syzComp;
2909  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
2910  poly res;
2911  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
2912  delete(strat);
2913 
2914 #ifdef HAVE_PLURAL
2915  if(pp != p)
2916  p_Delete(&pp, currRing);
2917 #endif
2918  return res;
2919 }

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

2275 {
2276  if(idIs0(F))
2277  return idInit(1,F->rank);
2278  if(!rField_is_Ring(currRing))
2279  {
2280  ideal r;
2281  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2282  BOOLEAN delete_w=(w==NULL);
2283  kStrategy strat=new skStrategy;
2284  strat->sbaOrder = sbaOrder;
2285  if (arri!=0)
2286  {
2287  strat->rewCrit1 = arriRewDummy;
2288  strat->rewCrit2 = arriRewCriterion;
2289  strat->rewCrit3 = arriRewCriterionPre;
2290  }
2291  else
2292  {
2293  strat->rewCrit1 = faugereRewCriterion;
2294  strat->rewCrit2 = faugereRewCriterion;
2295  strat->rewCrit3 = faugereRewCriterion;
2296  }
2297 
2298  if(!TEST_OPT_RETURN_SB)
2299  strat->syzComp = syzComp;
2300  if (TEST_OPT_SB_1)
2301  //if(!rField_is_Ring(currRing)) // always true here
2302  strat->newIdeal = newIdeal;
2304  strat->LazyPass=20;
2305  else
2306  strat->LazyPass=2;
2307  strat->LazyDegree = 1;
2309  strat->chainCrit=chainCritNormal;
2311  strat->ak = id_RankFreeModule(F,currRing);
2312  strat->kModW=kModW=NULL;
2313  strat->kHomW=kHomW=NULL;
2314  if (vw != NULL)
2315  {
2316  currRing->pLexOrder=FALSE;
2317  strat->kHomW=kHomW=vw;
2318  strat->pOrigFDeg = currRing->pFDeg;
2319  strat->pOrigLDeg = currRing->pLDeg;
2321  toReset = TRUE;
2322  }
2323  if (h==testHomog)
2324  {
2325  if (strat->ak == 0)
2326  {
2327  h = (tHomog)idHomIdeal(F,Q);
2328  w=NULL;
2329  }
2330  else if (!TEST_OPT_DEGBOUND)
2331  {
2332  if (w!=NULL)
2333  h = (tHomog)idHomModule(F,Q,w);
2334  else
2335  h = (tHomog)idHomIdeal(F,Q);
2336  }
2337  }
2338  currRing->pLexOrder=b;
2339  if (h==isHomog)
2340  {
2341  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2342  {
2343  strat->kModW = kModW = *w;
2344  if (vw == NULL)
2345  {
2346  strat->pOrigFDeg = currRing->pFDeg;
2347  strat->pOrigLDeg = currRing->pLDeg;
2349  toReset = TRUE;
2350  }
2351  }
2352  currRing->pLexOrder = TRUE;
2353  if (hilb==NULL) strat->LazyPass*=2;
2354  }
2355  strat->homog=h;
2356  #ifdef KDEBUG
2357  idTest(F);
2358  if(Q != NULL)
2359  idTest(Q);
2360  #endif
2361  #ifdef HAVE_PLURAL
2362  if (rIsPluralRing(currRing))
2363  {
2364  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2365  strat->no_prod_crit = ! bIsSCA;
2366  if (w!=NULL)
2367  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2368  else
2369  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2370  }
2371  else
2372  #endif
2373  {
2375  {
2376  if (w!=NULL)
2377  r=mora(F,Q,*w,hilb,strat);
2378  else
2379  r=mora(F,Q,NULL,hilb,strat);
2380  }
2381  else
2382  {
2383  strat->sigdrop = FALSE;
2384  if (w!=NULL)
2385  r=sba(F,Q,*w,hilb,strat);
2386  else
2387  r=sba(F,Q,NULL,hilb,strat);
2388  }
2389  }
2390  #ifdef KDEBUG
2391  idTest(r);
2392  #endif
2393  if (toReset)
2394  {
2395  kModW = NULL;
2396  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2397  }
2398  currRing->pLexOrder = b;
2399  //Print("%d reductions canceled \n",strat->cel);
2400  HCord=strat->HCord;
2401  //delete(strat);
2402  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2403  return r;
2404  }
2405  else
2406  {
2407  //--------------------------RING CASE-------------------------
2408  assume(sbaOrder == 1);
2409  assume(arri == 0);
2410  ideal r;
2411  r = idCopy(F);
2412  int sbaEnterS = -1;
2413  bool sigdrop = TRUE;
2414  //This is how we set the SBA algorithm;
2415  int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2416  while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2417  && (blockred <= blockedreductions))
2418  {
2419  loops++;
2420  if(loops == 1)
2421  sigdrop = FALSE;
2422  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2423  BOOLEAN delete_w=(w==NULL);
2424  kStrategy strat=new skStrategy;
2425  strat->sbaEnterS = sbaEnterS;
2426  strat->sigdrop = sigdrop;
2427  #if 0
2428  strat->blockred = blockred;
2429  #else
2430  strat->blockred = 0;
2431  #endif
2432  strat->blockredmax = blockedreductions;
2433  //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2434  //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2435  strat->sbaOrder = sbaOrder;
2436  if (arri!=0)
2437  {
2438  strat->rewCrit1 = arriRewDummy;
2439  strat->rewCrit2 = arriRewCriterion;
2440  strat->rewCrit3 = arriRewCriterionPre;
2441  }
2442  else
2443  {
2444  strat->rewCrit1 = faugereRewCriterion;
2445  strat->rewCrit2 = faugereRewCriterion;
2446  strat->rewCrit3 = faugereRewCriterion;
2447  }
2448 
2449  if(!TEST_OPT_RETURN_SB)
2450  strat->syzComp = syzComp;
2451  if (TEST_OPT_SB_1)
2452  if(!rField_is_Ring(currRing))
2453  strat->newIdeal = newIdeal;
2455  strat->LazyPass=20;
2456  else
2457  strat->LazyPass=2;
2458  strat->LazyDegree = 1;
2460  strat->chainCrit=chainCritNormal;
2462  strat->ak = id_RankFreeModule(F,currRing);
2463  strat->kModW=kModW=NULL;
2464  strat->kHomW=kHomW=NULL;
2465  if (vw != NULL)
2466  {
2467  currRing->pLexOrder=FALSE;
2468  strat->kHomW=kHomW=vw;
2469  strat->pOrigFDeg = currRing->pFDeg;
2470  strat->pOrigLDeg = currRing->pLDeg;
2472  toReset = TRUE;
2473  }
2474  if (h==testHomog)
2475  {
2476  if (strat->ak == 0)
2477  {
2478  h = (tHomog)idHomIdeal(F,Q);
2479  w=NULL;
2480  }
2481  else if (!TEST_OPT_DEGBOUND)
2482  {
2483  if (w!=NULL)
2484  h = (tHomog)idHomModule(F,Q,w);
2485  else
2486  h = (tHomog)idHomIdeal(F,Q);
2487  }
2488  }
2489  currRing->pLexOrder=b;
2490  if (h==isHomog)
2491  {
2492  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2493  {
2494  strat->kModW = kModW = *w;
2495  if (vw == NULL)
2496  {
2497  strat->pOrigFDeg = currRing->pFDeg;
2498  strat->pOrigLDeg = currRing->pLDeg;
2500  toReset = TRUE;
2501  }
2502  }
2503  currRing->pLexOrder = TRUE;
2504  if (hilb==NULL) strat->LazyPass*=2;
2505  }
2506  strat->homog=h;
2507  #ifdef KDEBUG
2508  idTest(F);
2509  if(Q != NULL)
2510  idTest(Q);
2511  #endif
2512  #ifdef HAVE_PLURAL
2513  if (rIsPluralRing(currRing))
2514  {
2515  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2516  strat->no_prod_crit = ! bIsSCA;
2517  if (w!=NULL)
2518  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2519  else
2520  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2521  }
2522  else
2523  #endif
2524  {
2526  {
2527  if (w!=NULL)
2528  r=mora(F,Q,*w,hilb,strat);
2529  else
2530  r=mora(F,Q,NULL,hilb,strat);
2531  }
2532  else
2533  {
2534  if (w!=NULL)
2535  r=sba(r,Q,*w,hilb,strat);
2536  else
2537  {
2538  r=sba(r,Q,NULL,hilb,strat);
2539  }
2540  }
2541  }
2542  #ifdef KDEBUG
2543  idTest(r);
2544  #endif
2545  if (toReset)
2546  {
2547  kModW = NULL;
2548  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2549  }
2550  currRing->pLexOrder = b;
2551  //Print("%d reductions canceled \n",strat->cel);
2552  HCord=strat->HCord;
2553  sigdrop = strat->sigdrop;
2554  sbaEnterS = strat->sbaEnterS;
2555  blockred = strat->blockred;
2556  delete(strat);
2557  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2558  }
2559  // Go to std
2560  if(sigdrop || blockred > blockedreductions)
2561  {
2562  r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2563  }
2564  return r;
2565  }
2566 }
bool sigdrop
Definition: kutil.h:358
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:287
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:289
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:291
intvec * kHomW
Definition: kutil.h:334
int blockred
Definition: kutil.h:363
unsigned sbaOrder
Definition: kutil.h:312
int blockredmax
Definition: kutil.h:364
int newIdeal
Definition: kutil.h:355
char z2homog
Definition: kutil.h:373
char no_prod_crit
Definition: kutil.h:393
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:286
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:290
int sbaEnterS
Definition: kutil.h:361
#define idTest(id)
Definition: ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition: kInline.h:1203
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:2075
VAR intvec * kHomW
Definition: kstd1.cc:2063
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2536
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition: kutil.cc:7213
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:7188
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:1929
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition: kutil.cc:7129
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3405
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3192
if(yy_init)
Definition: libparse.cc:1420
#define TEST_OPT_SB_1
Definition: options.h:116

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

2090 {
2091  if(idIs0(F))
2092  return idInit(1,F->rank);
2093 
2094 #ifdef HAVE_SHIFTBBA
2095  if(rIsLPRing(currRing)) return freegb(F, Q);
2096 #endif
2097 
2098  ideal r;
2099  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2100  BOOLEAN delete_w=(w==NULL);
2101  kStrategy strat=new skStrategy;
2102 
2103  strat->s_poly=sp;
2104  if(!TEST_OPT_RETURN_SB)
2105  strat->syzComp = syzComp;
2106  if (TEST_OPT_SB_1
2107  &&(!rField_is_Ring(currRing))
2108  )
2109  strat->newIdeal = newIdeal;
2111  strat->LazyPass=20;
2112  else
2113  strat->LazyPass=2;
2114  strat->LazyDegree = 1;
2115  strat->ak = id_RankFreeModule(F,currRing);
2116  strat->kModW=kModW=NULL;
2117  strat->kHomW=kHomW=NULL;
2118  if (vw != NULL)
2119  {
2120  currRing->pLexOrder=FALSE;
2121  strat->kHomW=kHomW=vw;
2122  strat->pOrigFDeg = currRing->pFDeg;
2123  strat->pOrigLDeg = currRing->pLDeg;
2125  toReset = TRUE;
2126  }
2127  if (h==testHomog)
2128  {
2129  if (strat->ak == 0)
2130  {
2131  h = (tHomog)idHomIdeal(F,Q);
2132  w=NULL;
2133  }
2134  else if (!TEST_OPT_DEGBOUND)
2135  {
2136  if (w!=NULL)
2137  h = (tHomog)idHomModule(F,Q,w);
2138  else
2139  h = (tHomog)idHomIdeal(F,Q);
2140  }
2141  }
2142  currRing->pLexOrder=b;
2143  if (h==isHomog)
2144  {
2145  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2146  {
2147  strat->kModW = kModW = *w;
2148  if (vw == NULL)
2149  {
2150  strat->pOrigFDeg = currRing->pFDeg;
2151  strat->pOrigLDeg = currRing->pLDeg;
2153  toReset = TRUE;
2154  }
2155  }
2156  currRing->pLexOrder = TRUE;
2157  if (hilb==NULL) strat->LazyPass*=2;
2158  }
2159  strat->homog=h;
2160 #ifdef KDEBUG
2161  idTest(F);
2162  if (Q!=NULL) idTest(Q);
2163 #endif
2164 #ifdef HAVE_PLURAL
2165  if (rIsPluralRing(currRing))
2166  {
2167  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2168  strat->no_prod_crit = ! bIsSCA;
2169  if (w!=NULL)
2170  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2171  else
2172  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2173  }
2174  else
2175 #endif
2176  {
2177  #if PRE_INTEGER_CHECK
2178  //the preinteger check strategy is not for modules
2179  if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2180  {
2181  ideal FCopy = idCopy(F);
2182  poly pFmon = preIntegerCheck(FCopy, Q);
2183  if(pFmon != NULL)
2184  {
2185  idInsertPoly(FCopy, pFmon);
2186  strat->kModW=kModW=NULL;
2187  if (h==testHomog)
2188  {
2189  if (strat->ak == 0)
2190  {
2191  h = (tHomog)idHomIdeal(FCopy,Q);
2192  w=NULL;
2193  }
2194  else if (!TEST_OPT_DEGBOUND)
2195  {
2196  if (w!=NULL)
2197  h = (tHomog)idHomModule(FCopy,Q,w);
2198  else
2199  h = (tHomog)idHomIdeal(FCopy,Q);
2200  }
2201  }
2202  currRing->pLexOrder=b;
2203  if (h==isHomog)
2204  {
2205  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2206  {
2207  strat->kModW = kModW = *w;
2208  if (vw == NULL)
2209  {
2210  strat->pOrigFDeg = currRing->pFDeg;
2211  strat->pOrigLDeg = currRing->pLDeg;
2213  toReset = TRUE;
2214  }
2215  }
2216  currRing->pLexOrder = TRUE;
2217  if (hilb==NULL) strat->LazyPass*=2;
2218  }
2219  strat->homog=h;
2220  }
2221  omTestMemory(1);
2222  if(w == NULL)
2223  {
2225  r=mora(FCopy,Q,NULL,hilb,strat);
2226  else
2227  r=bba(FCopy,Q,NULL,hilb,strat);
2228  }
2229  else
2230  {
2232  r=mora(FCopy,Q,*w,hilb,strat);
2233  else
2234  r=bba(FCopy,Q,*w,hilb,strat);
2235  }
2236  idDelete(&FCopy);
2237  }
2238  else
2239  #endif
2240  {
2241  if(w==NULL)
2242  {
2244  r=mora(F,Q,NULL,hilb,strat);
2245  else
2246  r=bba(F,Q,NULL,hilb,strat);
2247  }
2248  else
2249  {
2251  r=mora(F,Q,*w,hilb,strat);
2252  else
2253  r=bba(F,Q,*w,hilb,strat);
2254  }
2255  }
2256  }
2257 #ifdef KDEBUG
2258  idTest(r);
2259 #endif
2260  if (toReset)
2261  {
2262  kModW = NULL;
2263  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2264  }
2265  currRing->pLexOrder = b;
2266 //Print("%d reductions canceled \n",strat->cel);
2267  HCord=strat->HCord;
2268  delete(strat);
2269  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2270  return r;
2271 }
s_poly_proc_t s_poly
Definition: kutil.h:296
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:838
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 freegb(ideal F, ideal Q)
Definition: kstd2.cc:4461
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:10994
omError_t omTestMemory(int check_level)
Definition: omDebug.c:94

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

2571 {
2572  ideal r;
2573  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2574  BOOLEAN delete_w=(w==NULL);
2575  kStrategy strat=new skStrategy;
2576  intvec* temp_w=NULL;
2577 
2578  strat->rightGB = rightGB;
2579 
2580  if(!TEST_OPT_RETURN_SB)
2581  strat->syzComp = syzComp;
2582  if (TEST_OPT_SB_1)
2583  if(!rField_is_Ring(currRing))
2584  strat->newIdeal = newIdeal;
2586  strat->LazyPass=20;
2587  else
2588  strat->LazyPass=2;
2589  strat->LazyDegree = 1;
2590  strat->ak = id_RankFreeModule(F,currRing);
2591  strat->kModW=kModW=NULL;
2592  strat->kHomW=kHomW=NULL;
2593  if (vw != NULL)
2594  {
2595  currRing->pLexOrder=FALSE;
2596  strat->kHomW=kHomW=vw;
2597  strat->pOrigFDeg = currRing->pFDeg;
2598  strat->pOrigLDeg = currRing->pLDeg;
2600  toReset = TRUE;
2601  }
2602  if (h==testHomog)
2603  {
2604  if (strat->ak == 0)
2605  {
2606  h = (tHomog)idHomIdeal(F,Q);
2607  w=NULL;
2608  }
2609  else if (!TEST_OPT_DEGBOUND)
2610  {
2611  if (w!=NULL)
2612  h = (tHomog)idHomModule(F,Q,w);
2613  else
2614  h = (tHomog)idHomIdeal(F,Q);
2615  }
2616  }
2617  currRing->pLexOrder=b;
2618  if (h==isHomog)
2619  {
2620  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2621  {
2622  strat->kModW = kModW = *w;
2623  if (vw == NULL)
2624  {
2625  strat->pOrigFDeg = currRing->pFDeg;
2626  strat->pOrigLDeg = currRing->pLDeg;
2628  toReset = TRUE;
2629  }
2630  }
2631  currRing->pLexOrder = TRUE;
2632  if (hilb==NULL) strat->LazyPass*=2;
2633  }
2634  strat->homog=h;
2635 #ifdef KDEBUG
2636  idTest(F);
2637 #endif
2639  {
2640  /* error: no local ord yet with shifts */
2641  WerrorS("No local ordering possible for shift algebra");
2642  return(NULL);
2643  }
2644  else
2645  {
2646  /* global ordering */
2647  if (w!=NULL)
2648  r=bbaShift(F,Q,*w,hilb,strat);
2649  else
2650  r=bbaShift(F,Q,NULL,hilb,strat);
2651  }
2652 #ifdef KDEBUG
2653  idTest(r);
2654 #endif
2655  if (toReset)
2656  {
2657  kModW = NULL;
2658  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2659  }
2660  currRing->pLexOrder = b;
2661 //Print("%d reductions canceled \n",strat->cel);
2662  HCord=strat->HCord;
2663  delete(strat);
2664  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2665  return r;
2666 }
char rightGB
Definition: kutil.h:368
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4163

◆ mora()

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

Definition at line 1517 of file kstd1.cc.

1518 {
1519  int olddeg = 0;
1520  int reduc = 0;
1521  int red_result = 1;
1522  int hilbeledeg=1,hilbcount=0;
1523  BITSET save1;
1524  SI_SAVE_OPT1(save1);
1526  {
1527  si_opt_1 &= ~Sy_bit(OPT_REDSB);
1529  }
1530 
1531  strat->update = TRUE;
1532  /*- setting global variables ------------------- -*/
1533  initBuchMoraCrit(strat);
1534  initHilbCrit(F,Q,&hilb,strat);
1535  initMora(F,strat);
1537  initBuchMoraPosRing(strat);
1538  else
1539  initBuchMoraPos(strat);
1540  /*Shdl=*/initBuchMora(F,Q,strat);
1541  if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1542  /*updateS in initBuchMora has Hecketest
1543  * and could have put strat->kHEdgdeFound FALSE*/
1544  if ((currRing->ppNoether)!=NULL)
1545  {
1546  strat->kHEdgeFound = TRUE;
1547  }
1548  if (strat->kHEdgeFound && strat->update)
1549  {
1550  firstUpdate(strat);
1551  updateLHC(strat);
1552  reorderL(strat);
1553  }
1554  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1555  {
1556  strat->posInLOld = strat->posInL;
1557  strat->posInLOldFlag = FALSE;
1558  strat->posInL = posInL10;
1559  updateL(strat);
1560  reorderL(strat);
1561  }
1562  kTest_TS(strat);
1563  strat->use_buckets = kMoraUseBucket(strat);
1564 
1565 #ifdef HAVE_TAIL_RING
1566  if (strat->homog && strat->red == redFirst)
1567  if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1568  kStratInitChangeTailRing(strat);
1569 #endif
1570 
1571  if (BVERBOSE(23))
1572  {
1573  kDebugPrint(strat);
1574  }
1575 //deleteInL(strat->L,&strat->Ll,1,strat);
1576 //deleteInL(strat->L,&strat->Ll,0,strat);
1577 
1578  /*- compute-------------------------------------------*/
1579  while (strat->Ll >= 0)
1580  {
1581  #ifdef KDEBUG
1582  if (TEST_OPT_DEBUG) messageSets(strat);
1583  #endif
1584  if (siCntrlc)
1585  {
1586  while (strat->Ll >= 0)
1587  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1588  strat->noClearS=TRUE;
1589  }
1590  if (TEST_OPT_DEGBOUND
1591  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1592  {
1593  /*
1594  * stops computation if
1595  * - 24 (degBound)
1596  * && upper degree is bigger than Kstd1_deg
1597  */
1598  while ((strat->Ll >= 0)
1599  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1600  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1601  )
1602  {
1603  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1604  //if (TEST_OPT_PROT)
1605  //{
1606  // PrintS("D"); mflush();
1607  //}
1608  }
1609  if (strat->Ll<0) break;
1610  else strat->noClearS=TRUE;
1611  }
1612  strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1613  if (strat->Ll==0) strat->interpt=TRUE;
1614  strat->Ll--;
1615  // create the real Spoly
1616  if (pNext(strat->P.p) == strat->tail)
1617  {
1618  /*- deletes the short spoly and computes -*/
1619  if (rField_is_Ring(currRing))
1620  pLmDelete(strat->P.p);
1621  else
1622  pLmFree(strat->P.p);
1623  strat->P.p = NULL;
1624  poly m1 = NULL, m2 = NULL;
1625  // check that spoly creation is ok
1626  while (strat->tailRing != currRing &&
1627  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1628  {
1629  assume(m1 == NULL && m2 == NULL);
1630  // if not, change to a ring where exponents are large enough
1631  kStratChangeTailRing(strat);
1632  }
1633  /* create the real one */
1634  ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1635  strat->tailRing, m1, m2, strat->R);
1636  if (!strat->use_buckets)
1637  strat->P.SetLength(strat->length_pLength);
1638  }
1639  else if (strat->P.p1 == NULL)
1640  {
1641  // for input polys, prepare reduction (buckets !)
1642  strat->P.SetLength(strat->length_pLength);
1643  strat->P.PrepareRed(strat->use_buckets);
1644  }
1645 
1646  // the s-poly
1647  if (!strat->P.IsNull())
1648  {
1649  // might be NULL from noether !!!
1650  if (TEST_OPT_PROT)
1651  message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1652  // reduce
1653  red_result = strat->red(&strat->P,strat);
1654  }
1655 
1656  // the reduced s-poly
1657  if (! strat->P.IsNull())
1658  {
1659  strat->P.GetP();
1660  // statistics
1661  if (TEST_OPT_PROT) PrintS("s");
1662  // normalization
1664  strat->P.pCleardenom();
1665  else
1666  strat->P.pNorm();
1667  // tailreduction
1668  strat->P.p = redtail(&(strat->P),strat->sl,strat);
1669  if (strat->P.p==NULL)
1670  {
1671  WerrorS("expoent overflow - wrong ordering");
1672  return(idInit(1,1));
1673  }
1674  // set ecart -- might have changed because of tail reductions
1675  if ((!strat->noTailReduction) && (!strat->honey))
1676  strat->initEcart(&strat->P);
1677  // cancel unit
1678  cancelunit(&strat->P);
1679  // for char 0, clear denominators
1680  if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
1682  strat->P.pCleardenom();
1683 
1684  enterT(strat->P,strat);
1685  // build new pairs
1686  if (rField_is_Ring(currRing))
1687  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1688  else
1689  enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1690  // put in S
1691  strat->enterS(strat->P,
1692  posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
1693  strat, strat->tl);
1694  // apply hilbert criterion
1695  if (hilb!=NULL)
1696  {
1697  if (strat->homog==isHomog)
1698  khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
1699  else
1700  khCheckLocInhom(Q,w,hilb,hilbcount,strat);
1701  }
1702 
1703  // clear strat->P
1704  kDeleteLcm(&strat->P);
1705 
1706 #ifdef KDEBUG
1707  // make sure kTest_TS does not complain about strat->P
1708  memset(&strat->P,0,sizeof(strat->P));
1709 #endif
1710  }
1711  if (strat->kHEdgeFound)
1712  {
1713  if ((TEST_OPT_FINDET)
1714  || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL,strat->tailRing) < Kstd1_mu)))
1715  {
1716  // obachman: is this still used ???
1717  /*
1718  * stops computation if strat->kHEdgeFound and
1719  * - 27 (finiteDeterminacyTest)
1720  * or
1721  * - 23
1722  * (multBound)
1723  * && multiplicity of the ideal is smaller then a predefined number mu
1724  */
1725  while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1726  }
1727  }
1728  kTest_TS(strat);
1729  }
1730  /*- complete reduction of the standard basis------------------------ -*/
1731  if (TEST_OPT_REDSB) completeReduce(strat);
1732  else if (TEST_OPT_PROT) PrintLn();
1733  /*- release temp data------------------------------- -*/
1734  exitBuchMora(strat);
1735  /*- polynomials used for HECKE: HC, noether -*/
1736  if (TEST_OPT_FINDET)
1737  {
1738  if (strat->kHEdge!=NULL)
1739  Kstd1_mu=currRing->pFDeg(strat->kHEdge,currRing);
1740  else
1741  Kstd1_mu=-1;
1742  }
1743  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
1744  strat->update = TRUE; //???
1745  strat->lastAxis = 0; //???
1746  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
1747  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
1748  if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
1749 // if (TEST_OPT_WEIGHTM)
1750 // {
1751 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1752 // if (ecartWeights)
1753 // {
1754 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
1755 // ecartWeights=NULL;
1756 // }
1757 // }
1758  if(nCoeff_is_Z(currRing->cf))
1759  finalReduceByMon(strat);
1760  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
1761  SI_RESTORE_OPT1(save1);
1762  idTest(strat->Shdl);
1763  return (strat->Shdl);
1764 }
KINLINE poly kNoetherTail()
Definition: kInline.h:66
ring tailRing
Definition: kutil.h:341
int Ll
Definition: kutil.h:349
int lastAxis
Definition: kutil.h:354
poly tail
Definition: kutil.h:332
char use_buckets
Definition: kutil.h:382
char interpt
Definition: kutil.h:370
LObject P
Definition: kutil.h:298
char noClearS
Definition: kutil.h:401
char length_pLength
Definition: kutil.h:386
char update
Definition: kutil.h:380
int scMult0Int(ideal S, ideal Q, const ring tailRing)
Definition: hdegree.cc:918
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:1159
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1203
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1110
void missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:925
void reorderL(kStrategy strat)
Definition: kstd1.cc:867
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1006
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3476
void updateL(kStrategy strat)
Definition: kstd1.cc:1039
EXTERN_VAR int Kstd1_mu
Definition: kstd1.h:50
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7954
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10208
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1033
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4859
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9866
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11403
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10292
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5035
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10931
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10533
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4831
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1203
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11502
void messageSets(kStrategy strat)
Definition: kutil.cc:8027
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7995
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11318
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:333
static void kDeleteLcm(LObject *P)
Definition: kutil.h:869
VAR BOOLEAN siCntrlc
Definition: options.c:14
#define TEST_OPT_FINDET
Definition: options.h:109
#define OPT_REDSB
Definition: options.h:74
#define TEST_OPT_MULTBOUND
Definition: options.h:112
#define TEST_OPT_FASTHC
Definition: options.h:107
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:756

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4471 of file kstd2.cc.

4472 {
4474  assume(idIsInV(F));
4475  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4476  idSkipZeroes(RS); // is this even necessary?
4477  assume(idIsInV(RS));
4478  return(RS);
4479 }

◆ 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 52 of file kstd1.h.

◆ Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 50 of file kstd1.h.

◆ Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 50 of file kstd1.h.

◆ LazyDegree

EXTERN_VAR int LazyDegree

Definition at line 50 of file kstd1.h.

◆ LazyPass

EXTERN_VAR int LazyPass

Definition at line 50 of file kstd1.h.

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 54 of file kstd1.h.