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

1805 {
1806  int i,j;
1807 
1808  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1809  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1810  strat->enterS = enterSMora;
1811  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1812  strat->posInLOld = strat->posInL;
1813  strat->posInLOldFlag = TRUE;
1814  strat->initEcart = initEcartNormal;
1815  strat->kAllAxis = (currRing->ppNoether) != NULL; //!!
1816  if ( currRing->ppNoether != NULL )
1817  {
1818  strat->kNoether = pCopy((currRing->ppNoether));
1819  strat->red = redFirst; /*take the first possible in T*/
1820  if (TEST_OPT_PROT)
1821  {
1822  Print("H(%ld)",p_FDeg(currRing->ppNoether,currRing)+1);
1823  mflush();
1824  }
1825  }
1826  else if (strat->homog)
1827  strat->red = redFirst; /*take the first possible in T*/
1828  else
1829  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1830  if (currRing->ppNoether != NULL)
1831  {
1832  HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1833  }
1834  else
1835  {
1836  HCord = 32000;/*- very large -*/
1837  }
1838 
1839  if (rField_is_Ring(currRing)) {
1840  if (rField_is_Z(currRing))
1841  strat->red = redRiloc_Z;
1842  else
1843  strat->red = redRiloc;
1844  }
1845 
1846  /*reads the ecartWeights used for Graebes method from the
1847  *intvec ecart and set ecartWeights
1848  */
1849  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1850  {
1851  //interred machen Aenderung
1852  strat->pOrigFDeg=currRing->pFDeg;
1853  strat->pOrigLDeg=currRing->pLDeg;
1854  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1855  /*uses automatic computation of the ecartWeights to set them*/
1857 
1859  if (TEST_OPT_PROT)
1860  {
1861  for(i=1; i<=(currRing->N); i++)
1862  Print(" %d",ecartWeights[i]);
1863  PrintLn();
1864  mflush();
1865  }
1866  }
1867  kOptimizeLDeg(currRing->pLDeg, strat);
1868 }
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
int i
Definition: cfEzgcd.cc:132
char posInLOldFlag
Definition: kutil.h:382
poly kNoether
Definition: kutil.h:329
BOOLEAN * NotUsedAxis
Definition: kutil.h:332
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:284
pFDegProc pOrigFDeg
Definition: kutil.h:296
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:288
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:287
char kAllAxis
Definition: kutil.h:376
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:286
void(* initEcart)(TObject *L)
Definition: kutil.h:280
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:278
char homog
Definition: kutil.h:372
pLDegProc pOrigLDeg
Definition: kutil.h:297
#define Print
Definition: emacs.cc:80
int j
Definition: facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:797
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:387
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1615
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:568
VAR int HCord
Definition: kutil.cc:246
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1373
void initEcartNormal(TObject *h)
Definition: kutil.cc:1351
#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:3711
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:380
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_Z(const ring r)
Definition: ring.h:510
#define rField_is_Ring(R)
Definition: ring.h:486
#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 3378 of file kstd1.cc.

3379 {
3380  const ring save = currRing;
3381  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3382  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3383  if( currRing != save ) rChangeCurrRing(save);
3384  return ret;
3385 }
int p
Definition: cfModGcd.cc:4078
STATIC_VAR jList * Q
Definition: janet.cc:30
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3167
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2420 of file kstd1.cc.

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

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

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

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

◆ kModDeg()

long kModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2410 of file kstd1.cc.

2411 {
2412  long o=p_WDegree(p, r);
2413  long i=__p_GetComp(p, r);
2414  if (i==0) return o;
2415  //assume((i>0) && (i<=kModW->length()));
2416  if (i<=kModW->length())
2417  return o+(*kModW)[i-1];
2418  return o;
2419 }
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:710

◆ kNF() [1/2]

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

Definition at line 3264 of file kstd1.cc.

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

◆ kNF() [2/2]

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

Definition at line 3167 of file kstd1.cc.

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

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

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

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

◆ kNFBound() [2/2]

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

Definition at line 3222 of file kstd1.cc.

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

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

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

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

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

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

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 53 of file kstd1.h.