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

1799 {
1800  int i,j;
1801 
1802  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1803  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1804  strat->enterS = enterSMora;
1805  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1806  strat->posInLOld = strat->posInL;
1807  strat->posInLOldFlag = TRUE;
1808  strat->initEcart = initEcartNormal;
1809  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1810  if ( strat->kHEdgeFound )
1811  strat->kNoether = pCopy((currRing->ppNoether));
1812  else if (strat->kHEdgeFound || strat->homog)
1813  strat->red = redFirst; /*take the first possible in T*/
1814  else
1815  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1816  if (strat->kHEdgeFound)
1817  {
1818  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1819  strat->posInT = posInT2;
1820  }
1821  else
1822  {
1823  strat->HCord = 32000;/*- very large -*/
1824  }
1825 
1826  if (rField_is_Ring(currRing)) {
1827  if (rField_is_Z(currRing))
1828  strat->red = redRiloc_Z;
1829  else
1830  strat->red = redRiloc;
1831  }
1832 
1833  /*reads the ecartWeights used for Graebes method from the
1834  *intvec ecart and set ecartWeights
1835  */
1836  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1837  {
1838  //interred machen Aenderung
1839  strat->pOrigFDeg=currRing->pFDeg;
1840  strat->pOrigLDeg=currRing->pLDeg;
1841  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1842  /*uses automatic computation of the ecartWeights to set them*/
1844 
1846  if (TEST_OPT_PROT)
1847  {
1848  for(i=1; i<=(currRing->N); i++)
1849  Print(" %d",ecartWeights[i]);
1850  PrintLn();
1851  mflush();
1852  }
1853  }
1854  kOptimizeLDeg(currRing->pLDeg, strat);
1855 }
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
int i
Definition: cfEzgcd.cc:132
char posInLOldFlag
Definition: kutil.h:386
poly kNoether
Definition: kutil.h:331
BOOLEAN * NotUsedAxis
Definition: kutil.h:335
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:285
pFDegProc pOrigFDeg
Definition: kutil.h:297
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:289
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:288
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:287
void(* initEcart)(TObject *L)
Definition: kutil.h:281
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:282
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:279
char kHEdgeFound
Definition: kutil.h:380
int HCord
Definition: kutil.h:358
char homog
Definition: kutil.h:376
pLDegProc pOrigLDeg
Definition: kutil.h:298
#define Print
Definition: emacs.cc:80
int j
Definition: facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:786
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:385
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1606
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:566
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4962
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:121
#define TEST_OPT_PROT
Definition: options.h:103
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:486
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:511
#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 3380 of file kstd1.cc.

3381 {
3382  const ring save = currRing;
3383  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3384  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3385  if( currRing != save ) rChangeCurrRing(save);
3386  return ret;
3387 }
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:3169
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2417 of file kstd1.cc.

2418 {
2419  int i;
2420  long j=0;
2421 
2422  for (i=r->N;i>0;i--)
2423  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2424  if (kModW == NULL) return j;
2425  i = __p_GetComp(p,r);
2426  if (i==0) return j;
2427  return j+(*kModW)[i-1];
2428 }
VAR intvec * kModW
Definition: kstd1.cc:2405
#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 3745 of file kstd1.cc.

3746 {
3747 #ifdef HAVE_PLURAL
3748  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3749 #endif
3752  )
3753  return kInterRedOld(F,Q);
3754 
3755  //return kInterRedOld(F,Q);
3756 
3757  BITSET save1;
3758  SI_SAVE_OPT1(save1);
3759  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3761  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3762  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3763  //extern char * showOption() ;
3764  //Print("%s\n",showOption());
3765 
3766  int need_retry;
3767  int counter=3;
3768  ideal res, res1;
3769  int elems;
3770  ideal null=NULL;
3771  if ((Q==NULL) || (!TEST_OPT_REDSB))
3772  {
3773  elems=idElem(F);
3774  res=kInterRedBba(F,Q,need_retry);
3775  }
3776  else
3777  {
3778  ideal FF=idSimpleAdd(F,Q);
3779  res=kInterRedBba(FF,NULL,need_retry);
3780  idDelete(&FF);
3781  null=idInit(1,1);
3782  if (need_retry)
3783  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3784  else
3785  res1=kNF(null,Q,res);
3786  idDelete(&res);
3787  res=res1;
3788  need_retry=1;
3789  }
3790  if (idElem(res)<=1) need_retry=0;
3791  while (need_retry && (counter>0))
3792  {
3793  #ifdef KDEBUG
3794  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3795  #endif
3796  res1=kInterRedBba(res,Q,need_retry);
3797  int new_elems=idElem(res1);
3798  counter -= (new_elems >= elems);
3799  elems = new_elems;
3800  idDelete(&res);
3801  if (idElem(res1)<=1) need_retry=0;
3802  if ((Q!=NULL) && (TEST_OPT_REDSB))
3803  {
3804  if (need_retry)
3805  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3806  else
3807  res=kNF(null,Q,res1);
3808  idDelete(&res1);
3809  }
3810  else
3811  res = res1;
3812  if (idElem(res)<=1) need_retry=0;
3813  }
3814  if (null!=NULL) idDelete(&null);
3815  SI_RESTORE_OPT1(save1);
3816  idSkipZeroes(res);
3817  return res;
3818 }
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:3393
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3485
#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:82
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:104
#define TEST_OPT_DEBUG
Definition: options.h:108
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:517
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:762
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 3393 of file kstd1.cc.

3394 {
3395  int j;
3396  kStrategy strat = new skStrategy;
3397 
3398  ideal tempF = F;
3399  ideal tempQ = Q;
3400 
3401 #ifdef HAVE_PLURAL
3402  if(rIsSCA(currRing))
3403  {
3404  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3405  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3406  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3407 
3408  // this should be done on the upper level!!! :
3409  // tempQ = SCAQuotient(currRing);
3410 
3411  if(Q == currRing->qideal)
3412  tempQ = SCAQuotient(currRing);
3413  }
3414 #endif
3415 
3416 // if (TEST_OPT_PROT)
3417 // {
3418 // writeTime("start InterRed:");
3419 // mflush();
3420 // }
3421  //strat->syzComp = 0;
3422  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3423  strat->kNoether=pCopy((currRing->ppNoether));
3424  strat->ak = id_RankFreeModule(tempF,currRing);
3425  initBuchMoraCrit(strat);
3426  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3427  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3428  strat->enterS = enterSBba;
3429  strat->posInT = posInT17;
3430  strat->initEcart = initEcartNormal;
3431  strat->sl = -1;
3432  strat->tl = -1;
3433  strat->tmax = setmaxT;
3434  strat->T = initT();
3435  strat->R = initR();
3436  strat->sevT = initsevT();
3438  initS(tempF, tempQ, strat);
3439  if (TEST_OPT_REDSB)
3440  strat->noTailReduction=FALSE;
3441  updateS(TRUE,strat);
3443  completeReduce(strat);
3444  //else if (TEST_OPT_PROT) PrintLn();
3445  cleanT(strat);
3446  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3447  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3448  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3449  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3450  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3451  omfree(strat->sevT);
3452  omfree(strat->S_2_R);
3453  omfree(strat->R);
3454 
3455  if (strat->fromQ)
3456  {
3457  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3458  {
3459  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3460  }
3461  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3462  }
3463 // if (TEST_OPT_PROT)
3464 // {
3465 // writeTime("end Interred:");
3466 // mflush();
3467 // }
3468  ideal shdl=strat->Shdl;
3469  idSkipZeroes(shdl);
3470  if (strat->fromQ)
3471  {
3472  strat->fromQ=NULL;
3473  ideal res=kInterRed(shdl,NULL);
3474  idDelete(&shdl);
3475  shdl=res;
3476  }
3477  delete(strat);
3478 #ifdef HAVE_PLURAL
3479  if( tempF != F )
3480  id_Delete( &tempF, currRing);
3481 #endif
3482  return shdl;
3483 }
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
int * S_2_R
Definition: kutil.h:345
char noTailReduction
Definition: kutil.h:382
TSet T
Definition: kutil.h:327
intset ecartS
Definition: kutil.h:310
char honey
Definition: kutil.h:381
int ak
Definition: kutil.h:356
TObject ** R
Definition: kutil.h:343
poly kHEdge
Definition: kutil.h:330
int tl
Definition: kutil.h:353
unsigned long * sevT
Definition: kutil.h:326
ideal Shdl
Definition: kutil.h:304
int tmax
Definition: kutil.h:353
intset fromQ
Definition: kutil.h:322
int sl
Definition: kutil.h:351
unsigned long * sevS
Definition: kutil.h:323
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:3745
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5394
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7829
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8788
void cleanT(kStrategy strat)
Definition: kutil.cc:545
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9670
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10532
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9023
#define setmaxT
Definition: kutil.h:33
class sTObject TObject
Definition: kutil.h:57
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:110
#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 3020 of file kstd1.cc.

3022 {
3023  if(idIs0(F))
3024  {
3025  M=idInit(1,F->rank);
3026  return idInit(1,F->rank);
3027  }
3029  {
3030  ideal sb;
3031  sb = kStd(F, Q, h, w, hilb);
3032  idSkipZeroes(sb);
3033  if(IDELEMS(sb) <= IDELEMS(F))
3034  {
3035  M = idCopy(sb);
3036  idSkipZeroes(M);
3037  return(sb);
3038  }
3039  else
3040  {
3041  M = idCopy(F);
3042  idSkipZeroes(M);
3043  return(sb);
3044  }
3045  }
3046  ideal r=NULL;
3047  int Kstd1_OldDeg = Kstd1_deg,i;
3048  intvec* temp_w=NULL;
3049  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3050  BOOLEAN delete_w=(w==NULL);
3051  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3052  kStrategy strat=new skStrategy;
3053 
3054  if(!TEST_OPT_RETURN_SB)
3055  strat->syzComp = syzComp;
3057  strat->LazyPass=20;
3058  else
3059  strat->LazyPass=2;
3060  strat->LazyDegree = 1;
3061  strat->minim=(reduced % 2)+1;
3062  strat->ak = id_RankFreeModule(F,currRing);
3063  if (delete_w)
3064  {
3065  temp_w=new intvec((strat->ak)+1);
3066  w = &temp_w;
3067  }
3068  if (h==testHomog)
3069  {
3070  if (strat->ak == 0)
3071  {
3072  h = (tHomog)idHomIdeal(F,Q);
3073  w=NULL;
3074  }
3075  else
3076  {
3077  h = (tHomog)idHomModule(F,Q,w);
3078  }
3079  }
3080  if (h==isHomog)
3081  {
3082  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3083  {
3084  kModW = *w;
3085  strat->kModW = *w;
3086  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3087  strat->pOrigFDeg = currRing->pFDeg;
3088  strat->pOrigLDeg = currRing->pLDeg;
3090 
3091  toReset = TRUE;
3092  if (reduced>1)
3093  {
3094  Kstd1_OldDeg=Kstd1_deg;
3095  Kstd1_deg = -1;
3096  for (i=IDELEMS(F)-1;i>=0;i--)
3097  {
3098  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3099  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3100  }
3101  }
3102  }
3103  currRing->pLexOrder = TRUE;
3104  strat->LazyPass*=2;
3105  }
3106  strat->homog=h;
3108  {
3109  if (w!=NULL)
3110  r=mora(F,Q,*w,hilb,strat);
3111  else
3112  r=mora(F,Q,NULL,hilb,strat);
3113  }
3114  else
3115  {
3116  if (w!=NULL)
3117  r=bba(F,Q,*w,hilb,strat);
3118  else
3119  r=bba(F,Q,NULL,hilb,strat);
3120  }
3121 #ifdef KDEBUG
3122  {
3123  int i;
3124  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3125  }
3126 #endif
3127  idSkipZeroes(r);
3128  if (toReset)
3129  {
3130  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3131  kModW = NULL;
3132  }
3133  currRing->pLexOrder = b;
3134  HCord=strat->HCord;
3135  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3136  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3137  {
3138  M=idInit(1,F->rank);
3139  M->m[0]=pOne();
3140  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3141  if (strat->M!=NULL) idDelete(&strat->M);
3142  }
3143  else if (strat->M==NULL)
3144  {
3145  M=idInit(1,F->rank);
3146  WarnS("no minimal generating set computed");
3147  }
3148  else
3149  {
3150  idSkipZeroes(strat->M);
3151  M=strat->M;
3152  }
3153  delete(strat);
3154  if (reduced>2)
3155  {
3156  Kstd1_deg=Kstd1_OldDeg;
3157  if (!oldDegBound)
3159  }
3160  else
3161  {
3162  if (IDELEMS(M)>IDELEMS(r)) {
3163  idDelete(&M);
3164  M=idCopy(r); }
3165  }
3166  return r;
3167 }
CanonicalForm b
Definition: cfModGcd.cc:4105
Definition: intvec.h:23
intvec * kModW
Definition: kutil.h:338
int syzComp
Definition: kutil.h:357
int minim
Definition: kutil.h:361
ideal M
Definition: kutil.h:306
int LazyPass
Definition: kutil.h:356
int LazyDegree
Definition: kutil.h:356
#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:1859
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2407
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:2430
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2374
VAR int HCord
Definition: kutil.cc:246
#define assume(x)
Definition: mod2.h:387
#define TEST_OPT_DEGBOUND
Definition: options.h:113
#define TEST_OPT_RETURN_SB
Definition: options.h:112
#define OPT_DEGBOUND
Definition: options.h:90
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:550
#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 2407 of file kstd1.cc.

2408 {
2409  long o=p_WDegree(p, r);
2410  long i=__p_GetComp(p, r);
2411  if (i==0) return o;
2412  //assume((i>0) && (i<=kModW->length()));
2413  if (i<=kModW->length())
2414  return o+(*kModW)[i-1];
2415  return o;
2416 }
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 3266 of file kstd1.cc.

3267 {
3268  ideal res;
3269  if (TEST_OPT_PROT)
3270  {
3271  Print("(S:%d)",IDELEMS(p));mflush();
3272  }
3273  if (idIs0(p))
3274  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3275 
3276  ideal pp = p;
3277 #ifdef HAVE_PLURAL
3278  if(rIsSCA(currRing))
3279  {
3280  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3281  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3282  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3283 
3284  if(Q == currRing->qideal)
3285  Q = SCAQuotient(currRing);
3286  }
3287 #endif
3288 
3289  if ((idIs0(F))&&(Q==NULL))
3290  {
3291 #ifdef HAVE_PLURAL
3292  if(p != pp)
3293  return pp;
3294 #endif
3295  return idCopy(p); /*F+Q=0*/
3296  }
3297 
3298  kStrategy strat=new skStrategy;
3299  strat->syzComp = syzComp;
3301  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3302  {
3303  strat->ak = si_max(strat->ak,(int)F->rank);
3304  }
3305 
3307  {
3308 #ifdef HAVE_SHIFTBBA
3309  if (currRing->isLPring)
3310  {
3311  WerrorS("No local ordering possible for shift algebra");
3312  return(NULL);
3313  }
3314 #endif
3315  res=kNF1(F,Q,pp,strat,lazyReduce);
3316  }
3317  else
3318  res=kNF2(F,Q,pp,strat,lazyReduce);
3319  delete(strat);
3320 
3321 #ifdef HAVE_PLURAL
3322  if(pp != p)
3323  id_Delete(&pp, currRing);
3324 #endif
3325 
3326  return res;
3327 }
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:2108
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3701

◆ kNF() [2/2]

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

Definition at line 3169 of file kstd1.cc.

3170 {
3171  if (p==NULL)
3172  return NULL;
3173 
3174  poly pp = p;
3175 
3176 #ifdef HAVE_PLURAL
3177  if(rIsSCA(currRing))
3178  {
3179  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3180  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3181  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3182 
3183  if(Q == currRing->qideal)
3184  Q = SCAQuotient(currRing);
3185  }
3186 #endif
3187 
3188  if ((idIs0(F))&&(Q==NULL))
3189  {
3190 #ifdef HAVE_PLURAL
3191  if(p != pp)
3192  return pp;
3193 #endif
3194  return pCopy(p); /*F+Q=0*/
3195  }
3196 
3197  kStrategy strat=new skStrategy;
3198  strat->syzComp = syzComp;
3199  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3200  poly res;
3201 
3203  {
3204 #ifdef HAVE_SHIFTBBA
3205  if (currRing->isLPring)
3206  {
3207  WerrorS("No local ordering possible for shift algebra");
3208  return(NULL);
3209  }
3210 #endif
3211  res=kNF1(F,Q,pp,strat,lazyReduce);
3212  }
3213  else
3214  res=kNF2(F,Q,pp,strat,lazyReduce);
3215  delete(strat);
3216 
3217 #ifdef HAVE_PLURAL
3218  if(pp != p)
3219  p_Delete(&pp, currRing);
3220 #endif
3221  return res;
3222 }
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 2252 of file kstd1.cc.

2253 {
2254  assume(!idIs0(q));
2255  assume(!(idIs0(F)&&(Q==NULL)));
2256 
2257 // lazy_reduce flags: can be combined by |
2258 //#define KSTD_NF_LAZY 1
2259  // do only a reduction of the leading term
2260 //#define KSTD_NF_ECART 2
2261  // only local: recude even with bad ecart
2262  poly p;
2263  int i;
2264  int j;
2265  int o;
2266  LObject h;
2267  ideal res;
2268  BITSET save1;
2269  SI_SAVE_OPT1(save1);
2270 
2271  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2272  //if ((idIs0(F))&&(Q==NULL))
2273  // return idCopy(q); /*F=0*/
2274  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2275  /*- creating temp data structures------------------- -*/
2276  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2277  strat->kNoether=pCopy((currRing->ppNoether));
2280  && (0<Kstd1_deg)
2281  && ((!strat->kHEdgeFound)
2283  {
2284  pLmDelete(&strat->kNoether);
2285  strat->kNoether=pOne();
2286  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2287  pSetm(strat->kNoether);
2288  strat->kHEdgeFound=TRUE;
2289  }
2290  initBuchMoraCrit(strat);
2292  initBuchMoraPosRing(strat);
2293  else
2294  initBuchMoraPos(strat);
2295  initMora(F,strat);
2296  strat->enterS = enterSMoraNF;
2297  /*- set T -*/
2298  strat->tl = -1;
2299  strat->tmax = setmaxT;
2300  strat->T = initT();
2301  strat->R = initR();
2302  strat->sevT = initsevT();
2303  /*- set S -*/
2304  strat->sl = -1;
2305  /*- init local data struct.-------------------------- -*/
2306  /*Shdl=*/initS(F,Q,strat);
2307  if ((strat->ak!=0)
2308  && (strat->kHEdgeFound))
2309  {
2310  if (strat->ak!=1)
2311  {
2312  pSetComp(strat->kNoether,1);
2313  pSetmComp(strat->kNoether);
2314  poly p=pHead(strat->kNoether);
2315  pSetComp(p,strat->ak);
2316  pSetmComp(p);
2317  p=pAdd(strat->kNoether,p);
2318  strat->kNoether=pNext(p);
2320  }
2321  }
2322  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
2323  {
2324  for (i=strat->sl; i>=0; i--)
2325  pNorm(strat->S[i]);
2326  }
2327  /*- compute------------------------------------------- -*/
2328  res=idInit(IDELEMS(q),strat->ak);
2329  for (i=0; i<IDELEMS(q); i++)
2330  {
2331  if (q->m[i]!=NULL)
2332  {
2333  p = pCopy(q->m[i]);
2334  deleteHC(&p,&o,&j,strat);
2335  if (p!=NULL)
2336  {
2337  /*- puts the elements of S also to T -*/
2338  for (j=0; j<=strat->sl; j++)
2339  {
2340  h.p = strat->S[j];
2341  h.ecart = strat->ecartS[j];
2342  h.pLength = h.length = pLength(h.p);
2343  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2344  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2345  h.sev = strat->sevS[j];
2346  h.SetpFDeg();
2348  enterT_strong(h,strat);
2349  else
2350  enterT(h,strat);
2351  }
2352  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2354  {
2355  p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2356  }
2357  else
2358  p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2359  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2360  {
2361  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2362  p = redtail(p,strat->sl,strat);
2363  }
2364  cleanT(strat);
2365  }
2366  res->m[i]=p;
2367  }
2368  //else
2369  // res->m[i]=NULL;
2370  }
2371  /*- release temp data------------------------------- -*/
2372  assume(strat->L==NULL); /*strat->L unsed */
2373  assume(strat->B==NULL); /*strat->B unused */
2374  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2375  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2376  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2377  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2378  omFree(strat->sevT);
2379  omFree(strat->S_2_R);
2380  omFree(strat->R);
2381  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2382  {
2384  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2385  strat->fromQ=NULL;
2386  }
2387  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2388  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2389 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2390 // {
2391 // pFDeg=strat->pOrigFDeg;
2392 // pLDeg=strat->pOrigLDeg;
2393 // if (ecartWeights)
2394 // {
2395 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2396 // ecartWeights=NULL;
2397 // }
2398 // }
2399  idDelete(&strat->Shdl);
2400  SI_RESTORE_OPT1(save1);
2401  if (TEST_OPT_PROT) PrintLn();
2402  return res;
2403 }
polyset S
Definition: kutil.h:307
LSet B
Definition: kutil.h:329
LSet L
Definition: kutil.h:328
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1798
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1660
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1067
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:967
#define KSTD_NF_ECART
Definition: kstd1.h:19
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7069
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9372
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9822
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9472
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:254
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9908
#define setmaxTinc
Definition: kutil.h:34
class sLObject LObject
Definition: kutil.h:58
#define pNext(p)
Definition: monomials.h:36
#define omFree(addr)
Definition: omAllocDecl.h:261
#define OPT_REDTAIL
Definition: options.h:91
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:115
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 2108 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 3329 of file kstd1.cc.

3330 {
3331  ideal res;
3332  if (TEST_OPT_PROT)
3333  {
3334  Print("(S:%d)",IDELEMS(p));mflush();
3335  }
3336  if (idIs0(p))
3337  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3338 
3339  ideal pp = p;
3340 #ifdef HAVE_PLURAL
3341  if(rIsSCA(currRing))
3342  {
3343  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3344  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3345  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3346 
3347  if(Q == currRing->qideal)
3348  Q = SCAQuotient(currRing);
3349  }
3350 #endif
3351 
3352  if ((idIs0(F))&&(Q==NULL))
3353  {
3354 #ifdef HAVE_PLURAL
3355  if(p != pp)
3356  return pp;
3357 #endif
3358  return idCopy(p); /*F+Q=0*/
3359  }
3360 
3361  kStrategy strat=new skStrategy;
3362  strat->syzComp = syzComp;
3364  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3365  {
3366  strat->ak = si_max(strat->ak,(int)F->rank);
3367  }
3368 
3369  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3370  delete(strat);
3371 
3372 #ifdef HAVE_PLURAL
3373  if(pp != p)
3374  id_Delete(&pp, currRing);
3375 #endif
3376 
3377  return res;
3378 }
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:3783

◆ kNFBound() [2/2]

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

Definition at line 3224 of file kstd1.cc.

3225 {
3226  if (p==NULL)
3227  return NULL;
3228 
3229  poly pp = p;
3230 
3231 #ifdef HAVE_PLURAL
3232  if(rIsSCA(currRing))
3233  {
3234  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3235  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3236  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3237 
3238  if(Q == currRing->qideal)
3239  Q = SCAQuotient(currRing);
3240  }
3241 #endif
3242 
3243  if ((idIs0(F))&&(Q==NULL))
3244  {
3245 #ifdef HAVE_PLURAL
3246  if(p != pp)
3247  return pp;
3248 #endif
3249  return pCopy(p); /*F+Q=0*/
3250  }
3251 
3252  kStrategy strat=new skStrategy;
3253  strat->syzComp = syzComp;
3254  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3255  poly res;
3256  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3257  delete(strat);
3258 
3259 #ifdef HAVE_PLURAL
3260  if(pp != p)
3261  p_Delete(&pp, currRing);
3262 #endif
3263  return res;
3264 }

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

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

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

2432 {
2433  if(idIs0(F))
2434  return idInit(1,F->rank);
2435 
2436 #ifdef HAVE_SHIFTBBA
2437  if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2438 #endif
2439 
2440  ideal r;
2441  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2442  BOOLEAN delete_w=(w==NULL);
2443  kStrategy strat=new skStrategy;
2444 
2445  strat->s_poly=sp;
2446  if(!TEST_OPT_RETURN_SB)
2447  strat->syzComp = syzComp;
2448  if (TEST_OPT_SB_1
2449  &&(!rField_is_Ring(currRing))
2450  )
2451  strat->newIdeal = newIdeal;
2453  strat->LazyPass=20;
2454  else
2455  strat->LazyPass=2;
2456  strat->LazyDegree = 1;
2457  strat->ak = id_RankFreeModule(F,currRing);
2458  strat->kModW=kModW=NULL;
2459  strat->kHomW=kHomW=NULL;
2460  if (vw != NULL)
2461  {
2462  currRing->pLexOrder=FALSE;
2463  strat->kHomW=kHomW=vw;
2464  strat->pOrigFDeg = currRing->pFDeg;
2465  strat->pOrigLDeg = currRing->pLDeg;
2467  toReset = TRUE;
2468  }
2469  if (h==testHomog)
2470  {
2471  if (strat->ak == 0)
2472  {
2473  h = (tHomog)idHomIdeal(F,Q);
2474  w=NULL;
2475  }
2476  else if (!TEST_OPT_DEGBOUND)
2477  {
2478  if (w!=NULL)
2479  h = (tHomog)idHomModule(F,Q,w);
2480  else
2481  h = (tHomog)idHomIdeal(F,Q);
2482  }
2483  }
2484  currRing->pLexOrder=b;
2485  if (h==isHomog)
2486  {
2487  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2488  {
2489  strat->kModW = kModW = *w;
2490  if (vw == NULL)
2491  {
2492  strat->pOrigFDeg = currRing->pFDeg;
2493  strat->pOrigLDeg = currRing->pLDeg;
2495  toReset = TRUE;
2496  }
2497  }
2498  currRing->pLexOrder = TRUE;
2499  if (hilb==NULL) strat->LazyPass*=2;
2500  }
2501  strat->homog=h;
2502 #ifdef KDEBUG
2503  idTest(F);
2504  if (Q!=NULL) idTest(Q);
2505 #endif
2506 #ifdef HAVE_PLURAL
2507  if (rIsPluralRing(currRing))
2508  {
2509  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2510  strat->no_prod_crit = ! bIsSCA;
2511  if (w!=NULL)
2512  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2513  else
2514  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2515  }
2516  else
2517 #endif
2518  {
2519  #if PRE_INTEGER_CHECK
2520  //the preinteger check strategy is not for modules
2521  if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2522  {
2523  ideal FCopy = idCopy(F);
2524  poly pFmon = preIntegerCheck(FCopy, Q);
2525  if(pFmon != NULL)
2526  {
2527  idInsertPoly(FCopy, pFmon);
2528  strat->kModW=kModW=NULL;
2529  if (h==testHomog)
2530  {
2531  if (strat->ak == 0)
2532  {
2533  h = (tHomog)idHomIdeal(FCopy,Q);
2534  w=NULL;
2535  }
2536  else if (!TEST_OPT_DEGBOUND)
2537  {
2538  if (w!=NULL)
2539  h = (tHomog)idHomModule(FCopy,Q,w);
2540  else
2541  h = (tHomog)idHomIdeal(FCopy,Q);
2542  }
2543  }
2544  currRing->pLexOrder=b;
2545  if (h==isHomog)
2546  {
2547  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2548  {
2549  strat->kModW = kModW = *w;
2550  if (vw == NULL)
2551  {
2552  strat->pOrigFDeg = currRing->pFDeg;
2553  strat->pOrigLDeg = currRing->pLDeg;
2555  toReset = TRUE;
2556  }
2557  }
2558  currRing->pLexOrder = TRUE;
2559  if (hilb==NULL) strat->LazyPass*=2;
2560  }
2561  strat->homog=h;
2562  }
2563  omTestMemory(1);
2564  if(w == NULL)
2565  {
2567  r=mora(FCopy,Q,NULL,hilb,strat);
2568  else
2569  r=bba(FCopy,Q,NULL,hilb,strat);
2570  }
2571  else
2572  {
2574  r=mora(FCopy,Q,*w,hilb,strat);
2575  else
2576  r=bba(FCopy,Q,*w,hilb,strat);
2577  }
2578  idDelete(&FCopy);
2579  }
2580  else
2581  #endif
2582  {
2583  if(w==NULL)
2584  {
2586  r=mora(F,Q,NULL,hilb,strat);
2587  else
2588  r=bba(F,Q,NULL,hilb,strat);
2589  }
2590  else
2591  {
2593  r=mora(F,Q,*w,hilb,strat);
2594  else
2595  r=bba(F,Q,*w,hilb,strat);
2596  }
2597  }
2598  }
2599 #ifdef KDEBUG
2600  idTest(r);
2601 #endif
2602  if (toReset)
2603  {
2604  kModW = NULL;
2605  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2606  }
2607  currRing->pLexOrder = b;
2608 //Print("%d reductions canceled \n",strat->cel);
2609  HCord=strat->HCord;
2610  delete(strat);
2611  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2612  return r;
2613 }
s_poly_proc_t s_poly
Definition: kutil.h:301
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:2911
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:10780
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 2911 of file kstd1.cc.

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

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

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4708 of file kstd2.cc.

4709 {
4711  assume(idIsInV(F));
4712  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4713  idSkipZeroes(RS); // is this even necessary?
4714  assume(idIsInV(RS));
4715  return(RS);
4716 }

◆ 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.