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

1818 {
1819  int i,j;
1820 
1821  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1822  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1823  strat->enterS = enterSMora;
1824  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1825  strat->posInLOld = strat->posInL;
1826  strat->posInLOldFlag = TRUE;
1827  strat->initEcart = initEcartNormal;
1828  strat->kAllAxis = (currRing->ppNoether) != NULL; //!!
1829  if ( currRing->ppNoether != NULL )
1830  {
1831  strat->kNoether = pCopy((currRing->ppNoether));
1832  strat->red = redFirst; /*take the first possible in T*/
1833  if (TEST_OPT_PROT)
1834  {
1835  Print("H(%ld)",p_FDeg(currRing->ppNoether,currRing)+1);
1836  mflush();
1837  }
1838  }
1839  else if (strat->homog)
1840  strat->red = redFirst; /*take the first possible in T*/
1841  else
1842  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1843  if (currRing->ppNoether != NULL)
1844  {
1845  HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1846  }
1847  else
1848  {
1849  HCord = 32000;/*- very large -*/
1850  }
1851 
1852  if (rField_is_Ring(currRing))
1853  {
1854  if (rField_is_Z(currRing))
1855  strat->red = redRiloc_Z;
1856  else
1857  strat->red = redRiloc;
1858  }
1859 
1860  /*reads the ecartWeights used for Graebes method from the
1861  *intvec ecart and set ecartWeights
1862  */
1863  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1864  {
1865  //interred machen Aenderung
1866  strat->pOrigFDeg=currRing->pFDeg;
1867  strat->pOrigLDeg=currRing->pLDeg;
1868  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1869  /*uses automatic computation of the ecartWeights to set them*/
1871 
1873  if (TEST_OPT_PROT)
1874  {
1875  for(i=1; i<=(currRing->N); i++)
1876  Print(" %d",ecartWeights[i]);
1877  PrintLn();
1878  mflush();
1879  }
1880  }
1881  kOptimizeLDeg(currRing->pLDeg, strat);
1882 }
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:1628
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:1326
void initEcartNormal(TObject *h)
Definition: kutil.cc:1304
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define NULL
Definition: omList.c:12
#define TEST_OPT_WEIGHTM
Definition: options.h:122
#define TEST_OPT_PROT
Definition: options.h:104
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3633
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:378
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:509
#define rField_is_Ring(R)
Definition: ring.h:485
#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 3396 of file kstd1.cc.

3397 {
3398  const ring save = currRing;
3399  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3400  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3401  if( currRing != save ) rChangeCurrRing(save);
3402  return ret;
3403 }
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:3182
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2434 of file kstd1.cc.

2435 {
2436  int i;
2437  long j=0;
2438 
2439  for (i=r->N;i>0;i--)
2440  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2441  if (kModW == NULL) return j;
2442  i = __p_GetComp(p,r);
2443  if (i==0) return j;
2444  return j+(*kModW)[i-1];
2445 }
VAR intvec * kModW
Definition: kstd1.cc:2422
#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:467

◆ kInterRed()

ideal kInterRed ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3761 of file kstd1.cc.

3762 {
3763 #ifdef HAVE_PLURAL
3764  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3765 #endif
3768  )
3769  return kInterRedOld(F,Q);
3770 
3771  //return kInterRedOld(F,Q);
3772 
3773  BITSET save1;
3774  SI_SAVE_OPT1(save1);
3775  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3777  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3778  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3779  //extern char * showOption() ;
3780  //Print("%s\n",showOption());
3781 
3782  int need_retry;
3783  int counter=3;
3784  ideal res, res1;
3785  int elems;
3786  ideal null=NULL;
3787  if ((Q==NULL) || (!TEST_OPT_REDSB))
3788  {
3789  elems=idElem(F);
3790  res=kInterRedBba(F,Q,need_retry);
3791  }
3792  else
3793  {
3794  ideal FF=idSimpleAdd(F,Q);
3795  res=kInterRedBba(FF,NULL,need_retry);
3796  idDelete(&FF);
3797  null=idInit(1,1);
3798  if (need_retry)
3799  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3800  else
3801  res1=kNF(null,Q,res);
3802  idDelete(&res);
3803  res=res1;
3804  need_retry=1;
3805  }
3806  if (idElem(res)<=1) need_retry=0;
3807  while (need_retry && (counter>0))
3808  {
3809  #ifdef KDEBUG
3810  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3811  #endif
3812  res1=kInterRedBba(res,Q,need_retry);
3813  int new_elems=idElem(res1);
3814  counter -= (new_elems >= elems);
3815  elems = new_elems;
3816  idDelete(&res);
3817  if (idElem(res1)<=1) need_retry=0;
3818  if ((Q!=NULL) && (TEST_OPT_REDSB))
3819  {
3820  if (need_retry)
3821  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3822  else
3823  res=kNF(null,Q,res1);
3824  idDelete(&res1);
3825  }
3826  else
3827  res = res1;
3828  if (idElem(res)<=1) need_retry=0;
3829  }
3830  if (null!=NULL) idDelete(&null);
3831  SI_RESTORE_OPT1(save1);
3832  idSkipZeroes(res);
3833  return res;
3834 }
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:3409
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3501
#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:83
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:105
#define TEST_OPT_DEBUG
Definition: options.h:109
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:515
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:760
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static int idElem(const ideal F)
number of non-zero polys in F
Definition: simpleideals.h:67
#define BITSET
Definition: structs.h:16

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3409 of file kstd1.cc.

3410 {
3411  int j;
3412  kStrategy strat = new skStrategy;
3413 
3414  ideal tempF = F;
3415  ideal tempQ = Q;
3416 
3417 #ifdef HAVE_PLURAL
3418  if(rIsSCA(currRing))
3419  {
3420  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3421  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3422  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3423 
3424  // this should be done on the upper level!!! :
3425  // tempQ = SCAQuotient(currRing);
3426 
3427  if(Q == currRing->qideal)
3428  tempQ = SCAQuotient(currRing);
3429  }
3430 #endif
3431 
3432 // if (TEST_OPT_PROT)
3433 // {
3434 // writeTime("start InterRed:");
3435 // mflush();
3436 // }
3437  //strat->syzComp = 0;
3438  strat->kAllAxis = (currRing->ppNoether) != NULL;
3439  strat->kNoether=pCopy((currRing->ppNoether));
3440  strat->ak = id_RankFreeModule(tempF,currRing);
3441  initBuchMoraCrit(strat);
3442  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3443  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3444  strat->enterS = enterSBba;
3445  strat->posInT = posInT17;
3446  strat->initEcart = initEcartNormal;
3447  strat->sl = -1;
3448  strat->tl = -1;
3449  strat->tmax = setmaxT;
3450  strat->T = initT();
3451  strat->R = initR();
3452  strat->sevT = initsevT();
3454  initS(tempF, tempQ, strat);
3455  if (TEST_OPT_REDSB)
3456  strat->noTailReduction=FALSE;
3457  updateS(TRUE,strat);
3459  completeReduce(strat);
3460  //else if (TEST_OPT_PROT) PrintLn();
3461  cleanT(strat);
3462  if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3463  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3464  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3465  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3466  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3467  omfree(strat->sevT);
3468  omfree(strat->S_2_R);
3469  omfree(strat->R);
3470 
3471  if (strat->fromQ)
3472  {
3473  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3474  {
3475  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3476  }
3477  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3478  }
3479 // if (TEST_OPT_PROT)
3480 // {
3481 // writeTime("end Interred:");
3482 // mflush();
3483 // }
3484  ideal shdl=strat->Shdl;
3485  idSkipZeroes(shdl);
3486  if (strat->fromQ)
3487  {
3488  strat->fromQ=NULL;
3489  ideal res=kInterRed(shdl,NULL);
3490  idDelete(&shdl);
3491  shdl=res;
3492  }
3493  delete(strat);
3494 #ifdef HAVE_PLURAL
3495  if( tempF != F )
3496  id_Delete( &tempF, currRing);
3497 #endif
3498  return shdl;
3499 }
#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:3761
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5306
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7635
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8594
void cleanT(kStrategy strat)
Definition: kutil.cc:565
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9476
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10340
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:8829
#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:111
#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 3034 of file kstd1.cc.

3036 {
3037  if(idIs0(F))
3038  {
3039  M=idInit(1,F->rank);
3040  return idInit(1,F->rank);
3041  }
3043  {
3044  ideal sb;
3045  sb = kStd(F, Q, h, w, hilb);
3046  idSkipZeroes(sb);
3047  if(IDELEMS(sb) <= IDELEMS(F))
3048  {
3049  M = idCopy(sb);
3050  idSkipZeroes(M);
3051  return(sb);
3052  }
3053  else
3054  {
3055  M = idCopy(F);
3056  idSkipZeroes(M);
3057  return(sb);
3058  }
3059  }
3060  ideal r=NULL;
3061  int Kstd1_OldDeg = Kstd1_deg,i;
3062  intvec* temp_w=NULL;
3063  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3064  BOOLEAN delete_w=(w==NULL);
3065  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3066  kStrategy strat=new skStrategy;
3067 
3068  if(!TEST_OPT_RETURN_SB)
3069  strat->syzComp = syzComp;
3071  strat->LazyPass=20;
3072  else
3073  strat->LazyPass=2;
3074  strat->LazyDegree = 1;
3075  strat->minim=(reduced % 2)+1;
3076  strat->ak = id_RankFreeModule(F,currRing);
3077  if (delete_w)
3078  {
3079  temp_w=new intvec((strat->ak)+1);
3080  w = &temp_w;
3081  }
3082  if (h==testHomog)
3083  {
3084  if (strat->ak == 0)
3085  {
3086  h = (tHomog)idHomIdeal(F,Q);
3087  w=NULL;
3088  }
3089  else
3090  {
3091  h = (tHomog)idHomModule(F,Q,w);
3092  }
3093  }
3094  if (h==isHomog)
3095  {
3096  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3097  {
3098  kModW = *w;
3099  strat->kModW = *w;
3100  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3101  strat->pOrigFDeg = currRing->pFDeg;
3102  strat->pOrigLDeg = currRing->pLDeg;
3104 
3105  toReset = TRUE;
3106  if (reduced>1)
3107  {
3108  Kstd1_OldDeg=Kstd1_deg;
3109  Kstd1_deg = -1;
3110  for (i=IDELEMS(F)-1;i>=0;i--)
3111  {
3112  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3113  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3114  }
3115  }
3116  }
3117  currRing->pLexOrder = TRUE;
3118  strat->LazyPass*=2;
3119  }
3120  strat->homog=h;
3122  {
3123  if (w!=NULL)
3124  r=mora(F,Q,*w,hilb,strat);
3125  else
3126  r=mora(F,Q,NULL,hilb,strat);
3127  }
3128  else
3129  {
3130  if (w!=NULL)
3131  r=bba(F,Q,*w,hilb,strat);
3132  else
3133  r=bba(F,Q,NULL,hilb,strat);
3134  }
3135 #ifdef KDEBUG
3136  {
3137  int i;
3138  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3139  }
3140 #endif
3141  idSkipZeroes(r);
3142  if (toReset)
3143  {
3144  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3145  kModW = NULL;
3146  }
3147  currRing->pLexOrder = b;
3148  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3149  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3150  {
3151  M=idInit(1,F->rank);
3152  M->m[0]=pOne();
3153  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3154  if (strat->M!=NULL) idDelete(&strat->M);
3155  }
3156  else if (strat->M==NULL)
3157  {
3158  M=idInit(1,F->rank);
3159  WarnS("no minimal generating set computed");
3160  }
3161  else
3162  {
3163  idSkipZeroes(strat->M);
3164  M=strat->M;
3165  }
3166  delete(strat);
3167  if (reduced>2)
3168  {
3169  Kstd1_deg=Kstd1_OldDeg;
3170  if (!oldDegBound)
3172  }
3173  else
3174  {
3175  if (IDELEMS(M)>IDELEMS(r)) {
3176  idDelete(&M);
3177  M=idCopy(r); }
3178  }
3179  return r;
3180 }
CanonicalForm b
Definition: cfModGcd.cc:4103
Definition: intvec.h:23
intvec * kModW
Definition: kutil.h:335
unsigned 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:1886
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2424
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:2447
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2642
#define assume(x)
Definition: mod2.h:389
#define TEST_OPT_DEGBOUND
Definition: options.h:114
#define TEST_OPT_RETURN_SB
Definition: options.h:113
#define OPT_DEGBOUND
Definition: options.h:91
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3645
#define pTest(p)
Definition: polys.h:414
#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:548
#define M
Definition: sirandom.c:25
tHomog
Definition: structs.h:35
@ isHomog
Definition: structs.h:37
@ testHomog
Definition: structs.h:38

◆ kModDeg()

long kModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2424 of file kstd1.cc.

2425 {
2426  long o=p_WDegree(p, r);
2427  long i=__p_GetComp(p, r);
2428  if (i==0) return o;
2429  //assume((i>0) && (i<=kModW->length()));
2430  if (i<=kModW->length())
2431  return o+(*kModW)[i-1];
2432  return o;
2433 }
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:714

◆ kNF() [1/2]

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

Definition at line 3280 of file kstd1.cc.

3281 {
3282  ideal res;
3283  if (TEST_OPT_PROT)
3284  {
3285  Print("(S:%d)",IDELEMS(p));mflush();
3286  }
3287  if (idIs0(p))
3288  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3289 
3290  ideal pp = p;
3291 #ifdef HAVE_PLURAL
3292  if(rIsSCA(currRing))
3293  {
3294  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3295  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3296  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3297 
3298  if(Q == currRing->qideal)
3299  Q = SCAQuotient(currRing);
3300  }
3301 #endif
3302 
3303  if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3304 
3305  if ((idIs0(F))&&(Q==NULL))
3306  {
3307 #ifdef HAVE_PLURAL
3308  if(p != pp)
3309  return pp;
3310 #endif
3311  return idCopy(p); /*F+Q=0*/
3312  }
3313 
3314  kStrategy strat=new skStrategy;
3315  strat->syzComp = syzComp;
3317  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3318  {
3319  strat->ak = si_max(strat->ak,(int)F->rank);
3320  }
3321 
3323  {
3324 #ifdef HAVE_SHIFTBBA
3325  if (currRing->isLPring)
3326  {
3327  WerrorS("No local ordering possible for shift algebra");
3328  return(NULL);
3329  }
3330 #endif
3331  res=kNF1(F,Q,pp,strat,lazyReduce);
3332  }
3333  else
3334  res=kNF2(F,Q,pp,strat,lazyReduce);
3335  delete(strat);
3336 
3337 #ifdef HAVE_PLURAL
3338  if(pp != p)
3339  id_Delete(&pp, currRing);
3340 #endif
3341 
3342  return res;
3343 }
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:2124
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3967

◆ kNF() [2/2]

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

Definition at line 3182 of file kstd1.cc.

3183 {
3184  if (p==NULL)
3185  return NULL;
3186 
3187  poly pp = p;
3188 
3189 #ifdef HAVE_PLURAL
3190  if(rIsSCA(currRing))
3191  {
3192  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3193  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3194  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3195 
3196  if(Q == currRing->qideal)
3197  Q = SCAQuotient(currRing);
3198  }
3199 #endif
3200  if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3201 
3202  if ((idIs0(F))&&(Q==NULL))
3203  {
3204 #ifdef HAVE_PLURAL
3205  if(p != pp)
3206  return pp;
3207 #endif
3208  return pCopy(p); /*F+Q=0*/
3209  }
3210 
3211  kStrategy strat=new skStrategy;
3212  strat->syzComp = syzComp;
3213  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3214  poly res;
3215 
3217  {
3218 #ifdef HAVE_SHIFTBBA
3219  if (currRing->isLPring)
3220  {
3221  WerrorS("No local ordering possible for shift algebra");
3222  return(NULL);
3223  }
3224 #endif
3225  res=kNF1(F,Q,pp,strat,lazyReduce);
3226  }
3227  else
3228  res=kNF2(F,Q,pp,strat,lazyReduce);
3229  delete(strat);
3230 
3231 #ifdef HAVE_PLURAL
3232  if(pp != p)
3233  p_Delete(&pp, currRing);
3234 #endif
3235  return res;
3236 }
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:899
#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 2269 of file kstd1.cc.

2270 {
2271  assume(!idIs0(q));
2272  assume(!(idIs0(F)&&(Q==NULL)));
2273 
2274 // lazy_reduce flags: can be combined by |
2275 //#define KSTD_NF_LAZY 1
2276  // do only a reduction of the leading term
2277 //#define KSTD_NF_ECART 2
2278  // only local: reduce even with bad ecart
2279  poly p;
2280  int i;
2281  int j;
2282  int o;
2283  LObject h;
2284  ideal res;
2285  BITSET save1;
2286  SI_SAVE_OPT1(save1);
2287 
2288  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2289  //if ((idIs0(F))&&(Q==NULL))
2290  // return idCopy(q); /*F=0*/
2291  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2292  /*- creating temp data structures------------------- -*/
2293  //strat->kAllAxis = (currRing->ppNoether) != NULL;
2294  strat->kNoether=pCopy((currRing->ppNoether));
2297  && (0<Kstd1_deg)
2298  && ((strat->kNoether==NULL)
2300  {
2301  pLmDelete(&strat->kNoether);
2302  strat->kNoether=pOne();
2303  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2304  pSetm(strat->kNoether);
2305  //strat->kAllAxis=TRUE;
2306  }
2307  initBuchMoraCrit(strat);
2309  initBuchMoraPosRing(strat);
2310  else
2311  initBuchMoraPos(strat);
2312  initMora(F,strat);
2313  strat->enterS = enterSMoraNF;
2314  /*- set T -*/
2315  strat->tl = -1;
2316  strat->tmax = setmaxT;
2317  strat->T = initT();
2318  strat->R = initR();
2319  strat->sevT = initsevT();
2320  /*- set S -*/
2321  strat->sl = -1;
2322  /*- init local data struct.-------------------------- -*/
2323  /*Shdl=*/initS(F,Q,strat);
2324  if ((strat->ak!=0)
2325  && (strat->kNoether!=NULL))
2326  {
2327  if (strat->ak!=1)
2328  {
2329  pSetComp(strat->kNoether,1);
2330  pSetmComp(strat->kNoether);
2331  poly p=pHead(strat->kNoether);
2332  pSetComp(p,strat->ak);
2333  pSetmComp(p);
2334  p=pAdd(strat->kNoether,p);
2335  strat->kNoether=pNext(p);
2337  }
2338  }
2339  if (((lazyReduce & KSTD_NF_LAZY)==0)
2340  && (!rField_is_Ring(currRing)))
2341  {
2342  for (i=strat->sl; i>=0; i--)
2343  pNorm(strat->S[i]);
2344  }
2345  /*- compute------------------------------------------- -*/
2346  res=idInit(IDELEMS(q),strat->ak);
2347  for (i=0; i<IDELEMS(q); i++)
2348  {
2349  if (q->m[i]!=NULL)
2350  {
2351  p = pCopy(q->m[i]);
2352  deleteHC(&p,&o,&j,strat);
2353  if (p!=NULL)
2354  {
2355  /*- puts the elements of S also to T -*/
2356  for (j=0; j<=strat->sl; j++)
2357  {
2358  h.p = strat->S[j];
2359  h.ecart = strat->ecartS[j];
2360  h.pLength = h.length = pLength(h.p);
2361  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2362  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2363  h.sev = strat->sevS[j];
2364  h.SetpFDeg();
2366  enterT_strong(h,strat);
2367  else
2368  enterT(h,strat);
2369  }
2370  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2372  {
2373  p = redMoraNFRing(p,strat, lazyReduce);
2374  }
2375  else
2376  p = redMoraNF(p,strat, lazyReduce);
2377  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2378  {
2379  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2380  p = redtail(p,strat->sl,strat);
2381  }
2382  cleanT(strat);
2383  }
2384  res->m[i]=p;
2385  }
2386  //else
2387  // res->m[i]=NULL;
2388  }
2389  /*- release temp data------------------------------- -*/
2390  assume(strat->L==NULL); /*strat->L unused */
2391  assume(strat->B==NULL); /*strat->B unused */
2392  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2393  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2394  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2395  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2396  omFree(strat->sevT);
2397  omFree(strat->S_2_R);
2398  omFree(strat->R);
2399  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2400  {
2402  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2403  strat->fromQ=NULL;
2404  }
2405  if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2406 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2407 // {
2408 // pFDeg=strat->pOrigFDeg;
2409 // pLDeg=strat->pOrigLDeg;
2410 // if (ecartWeights)
2411 // {
2412 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2413 // ecartWeights=NULL;
2414 // }
2415 // }
2416  idDelete(&strat->Shdl);
2417  SI_RESTORE_OPT1(save1);
2418  if (TEST_OPT_PROT) PrintLn();
2419  return res;
2420 }
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:1817
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1681
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1083
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:978
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:6883
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9178
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9627
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9278
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:294
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9713
#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:92
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:116
static int pLength(poly a)
Definition: p_polys.h:188
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:721
#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:362
#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 2124 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 3345 of file kstd1.cc.

3346 {
3347  ideal res;
3348  if (TEST_OPT_PROT)
3349  {
3350  Print("(S:%d)",IDELEMS(p));mflush();
3351  }
3352  if (idIs0(p))
3353  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3354 
3355  ideal pp = p;
3356 #ifdef HAVE_PLURAL
3357  if(rIsSCA(currRing))
3358  {
3359  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3360  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3361  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3362 
3363  if(Q == currRing->qideal)
3364  Q = SCAQuotient(currRing);
3365  }
3366 #endif
3367 
3368  if ((idIs0(F))&&(Q==NULL))
3369  {
3370 #ifdef HAVE_PLURAL
3371  if(p != pp)
3372  return pp;
3373 #endif
3374  return idCopy(p); /*F+Q=0*/
3375  }
3376 
3377  kStrategy strat=new skStrategy;
3378  strat->syzComp = syzComp;
3380  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3381  {
3382  strat->ak = si_max(strat->ak,(int)F->rank);
3383  }
3384 
3385  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3386  delete(strat);
3387 
3388 #ifdef HAVE_PLURAL
3389  if(pp != p)
3390  id_Delete(&pp, currRing);
3391 #endif
3392 
3393  return res;
3394 }
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:4049

◆ kNFBound() [2/2]

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

Definition at line 3238 of file kstd1.cc.

3239 {
3240  if (p==NULL)
3241  return NULL;
3242 
3243  poly pp = p;
3244 
3245 #ifdef HAVE_PLURAL
3246  if(rIsSCA(currRing))
3247  {
3248  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3249  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3250  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3251 
3252  if(Q == currRing->qideal)
3253  Q = SCAQuotient(currRing);
3254  }
3255 #endif
3256 
3257  if ((idIs0(F))&&(Q==NULL))
3258  {
3259 #ifdef HAVE_PLURAL
3260  if(p != pp)
3261  return pp;
3262 #endif
3263  return pCopy(p); /*F+Q=0*/
3264  }
3265 
3266  kStrategy strat=new skStrategy;
3267  strat->syzComp = syzComp;
3268  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3269  poly res;
3270  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3271  delete(strat);
3272 
3273 #ifdef HAVE_PLURAL
3274  if(pp != p)
3275  p_Delete(&pp, currRing);
3276 #endif
3277  return res;
3278 }

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

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

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

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

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

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

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4972 of file kstd2.cc.

4973 {
4975  assume(idIsInV(F));
4976  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4977  idSkipZeroes(RS); // is this even necessary?
4978  assume(idIsInV(RS));
4979  return(RS);
4980 }

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