My Project  debian-1:4.1.1-p2+ds-4build4
Macros | Functions | Variables
kstd1.cc File Reference
#include "kernel/mod2.h"
#include "omalloc/omalloc.h"
#include "misc/options.h"
#include "misc/intvec.h"
#include "polys/weight.h"
#include "kernel/polys.h"
#include "kernel/GBEngine/kutil.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/khstd.h"
#include "kernel/combinatorics/stairc.h"
#include "kernel/ideals.h"
#include "polys/nc/nc.h"
#include "polys/nc/sca.h"
#include "kernel/GBEngine/nc.h"
#include "kernel/GBEngine/kInline.h"

Go to the source code of this file.

Macros

#define MORA_USE_BUCKETS
 
#define PRE_INTEGER_CHECK   0
 

Functions

static BOOLEAN kMoraUseBucket (kStrategy strat)
 
static void kOptimizeLDeg (pLDegProc ldeg, kStrategy strat)
 
static int doRed (LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
 
int redEcart (LObject *h, kStrategy strat)
 
int redRiloc (LObject *h, kStrategy strat)
 
int redFirst (LObject *h, kStrategy strat)
 
static poly redMoraNF (poly h, kStrategy strat, int flag)
 
static poly redMoraNFRing (poly h, kStrategy strat, int flag)
 
void reorderL (kStrategy strat)
 
void reorderT (kStrategy strat)
 
void missingAxis (int *last, kStrategy strat)
 
BOOLEAN hasPurePower (const poly p, int last, int *length, kStrategy strat)
 
BOOLEAN hasPurePower (LObject *L, int last, int *length, kStrategy strat)
 
int posInL10 (const LSet set, const int length, LObject *p, const kStrategy strat)
 
void updateL (kStrategy strat)
 
void updateLHC (kStrategy strat)
 
void updateT (kStrategy strat)
 
void firstUpdate (kStrategy strat)
 
void enterSMora (LObject &p, int atS, kStrategy strat, int atR=-1)
 
void enterSMoraNF (LObject &p, int atS, kStrategy strat, int atR=-1)
 
void initBba (kStrategy strat)
 
void initSba (ideal F, kStrategy strat)
 
void initMora (ideal F, kStrategy strat)
 
void kDebugPrint (kStrategy strat)
 
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)
 
long kModDeg (poly p, ring r)
 
long kHomModDeg (poly p, ring r)
 
ideal kStd (ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
 
ideal kSba (ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, intvec *hilb, int syzComp, int newIdeal, intvec *vw)
 
ideal kStdShift (ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, int uptodeg, int lV)
 
ideal kMin_std (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
 
poly kNF (ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
 
poly kNFBound (ideal F, ideal Q, poly p, int bound, int syzComp, int lazyReduce)
 
ideal kNF (ideal F, ideal Q, ideal p, int syzComp, int lazyReduce)
 
ideal kNFBound (ideal F, ideal Q, ideal p, int bound, int syzComp, int lazyReduce)
 
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 kInterRedOld (ideal F, ideal Q)
 
ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
 
ideal kInterRed (ideal F, ideal Q)
 

Variables

BITSET kOptions
 
BITSET validOpts
 
intveckModW
 
intveckHomW
 

Macro Definition Documentation

◆ MORA_USE_BUCKETS

#define MORA_USE_BUCKETS

Definition at line 12 of file kstd1.cc.

◆ PRE_INTEGER_CHECK

#define PRE_INTEGER_CHECK   0

Definition at line 14 of file kstd1.cc.

Function Documentation

◆ doRed()

static int doRed ( LObject h,
TObject with,
BOOLEAN  intoT,
kStrategy  strat,
bool  redMoraNF 
)
static

Definition at line 118 of file kstd1.cc.

119 {
120  int ret;
121 #if KDEBUG > 0
122  kTest_L(h);
123  kTest_T(with);
124 #endif
125  // Hmmm ... why do we do this -- polys from T should already be normalized
127  with->pNorm();
128 #ifdef KDEBUG
129  if (TEST_OPT_DEBUG)
130  {
131  PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
132  }
133 #endif
134  if (intoT)
135  {
136  // need to do it exacly like this: otherwise
137  // we might get errors
138  LObject L= *h;
139  L.Copy();
140  h->GetP();
141  h->length=h->pLength=pLength(h->p);
142  ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, strat);
143  if (ret)
144  {
145  if (ret < 0) return ret;
146  if (h->tailRing != strat->tailRing)
147  h->ShallowCopyDelete(strat->tailRing,
148  pGetShallowCopyDeleteProc(h->tailRing,
149  strat->tailRing));
150  }
152  enterT_strong(*h,strat);
153  else
154  enterT(*h,strat);
155  *h = L;
156  }
157  else
158  ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, strat);
159 #ifdef KDEBUG
160  if (TEST_OPT_DEBUG)
161  {
162  PrintS("to ");h->wrp();PrintLn();
163  }
164 #endif
165  return ret;
166 }
KINLINE poly kNoetherTail()
Definition: kInline.h:63
ring tailRing
Definition: kutil.h:336
static Poly * h
Definition: janet.cc:972
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:41
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:664
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9275
BOOLEAN kTest_L(LObject *L, ring strat_tailRing, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition: kutil.cc:859
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9356
BOOLEAN kTest_T(TObject *T, ring strat_tailRing, int i, char TN)
Definition: kutil.cc:758
class sLObject LObject
Definition: kutil.h:54
#define NULL
Definition: omList.c:10
#define TEST_OPT_INTSTRATEGY
Definition: options.h:109
#define TEST_OPT_DEBUG
Definition: options.h:107
pShallowCopyDeleteProc pGetShallowCopyDeleteProc(ring, ring)
static unsigned pLength(poly a)
Definition: p_polys.h:192
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:477

◆ enterSMora()

void enterSMora ( LObject p,
int  atS,
kStrategy  strat,
int  atR = -1 
)

Definition at line 1274 of file kstd1.cc.

1275 {
1276  enterSBba(p, atS, strat, atR);
1277  #ifdef KDEBUG
1278  if (TEST_OPT_DEBUG)
1279  {
1280  Print("new s%d:",atS);
1281  p_wrp(p.p,currRing,strat->tailRing);
1282  PrintLn();
1283  }
1284  #endif
1285  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1286  if (strat->kHEdgeFound)
1287  {
1288  if (newHEdge(strat))
1289  {
1290  firstUpdate(strat);
1291  if (TEST_OPT_FINDET)
1292  return;
1293 
1294  /*- cuts elements in L above noether and reorders L -*/
1295  updateLHC(strat);
1296  /*- reorders L with respect to posInL -*/
1297  reorderL(strat);
1298  }
1299  }
1300  else if (strat->kNoether!=NULL)
1301  strat->kHEdgeFound = TRUE;
1302  else if (TEST_OPT_FASTHC)
1303  {
1304  if (strat->posInLOldFlag)
1305  {
1306  missingAxis(&strat->lastAxis,strat);
1307  if (strat->lastAxis)
1308  {
1309  strat->posInLOld = strat->posInL;
1310  strat->posInLOldFlag = FALSE;
1311  strat->posInL = posInL10;
1312  strat->posInLDependsOnLength = TRUE;
1313  updateL(strat);
1314  reorderL(strat);
1315  }
1316  }
1317  else if (strat->lastAxis)
1318  updateL(strat);
1319  }
1320 }
#define TRUE
Definition: auxiliary.h:98
#define FALSE
Definition: auxiliary.h:94
int p
Definition: cfModGcd.cc:4019
char posInLOldFlag
Definition: kutil.h:376
poly kNoether
Definition: kutil.h:321
int lastAxis
Definition: kutil.h:349
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:275
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:279
char kHEdgeFound
Definition: kutil.h:370
char posInLDependsOnLength
Definition: kutil.h:383
#define Print
Definition: emacs.cc:80
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1207
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1114
void missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:927
void reorderL(kStrategy strat)
Definition: kstd1.cc:869
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1010
void updateL(kStrategy strat)
Definition: kstd1.cc:1043
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:467
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9034
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10521
#define TEST_OPT_FINDET
Definition: options.h:110
#define TEST_OPT_FASTHC
Definition: options.h:108
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:235

◆ enterSMoraNF()

void enterSMoraNF ( LObject p,
int  atS,
kStrategy  strat,
int  atR = -1 
)

Definition at line 1328 of file kstd1.cc.

1329 {
1330  enterSBba(p, atS, strat, atR);
1331  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1332  if (strat->kHEdgeFound)
1333  newHEdge(strat);
1334  else if (strat->kNoether!=NULL)
1335  strat->kHEdgeFound = TRUE;
1336 }

◆ firstUpdate()

void firstUpdate ( kStrategy  strat)

Definition at line 1207 of file kstd1.cc.

1208 {
1209  if (strat->update)
1210  {
1211  kTest_TS(strat);
1212  strat->update = (strat->tl == -1);
1213  if (TEST_OPT_WEIGHTM)
1214  {
1215  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1216  if (strat->tailRing != currRing)
1217  {
1218  strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1219  strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1220  }
1221  int i;
1222  for (i=strat->Ll; i>=0; i--)
1223  {
1224  strat->L[i].SetpFDeg();
1225  }
1226  for (i=strat->tl; i>=0; i--)
1227  {
1228  strat->T[i].SetpFDeg();
1229  }
1230  if (ecartWeights)
1231  {
1232  omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1234  }
1235  }
1236  if (TEST_OPT_FASTHC)
1237  {
1238  strat->posInL = strat->posInLOld;
1239  strat->lastAxis = 0;
1240  }
1241  if (TEST_OPT_FINDET)
1242  return;
1243 
1245  {
1246  strat->red = redFirst;
1247  strat->use_buckets = kMoraUseBucket(strat);
1248  }
1249  updateT(strat);
1250 
1252  {
1253  strat->posInT = posInT2;
1254  reorderT(strat);
1255  }
1256  }
1257  kTest_TS(strat);
1258 }
void * ADDRESS
Definition: auxiliary.h:133
int i
Definition: cfEzgcd.cc:125
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:289
int Ll
Definition: kutil.h:344
TSet T
Definition: kutil.h:317
int tl
Definition: kutil.h:343
pFDegProc pOrigFDeg
Definition: kutil.h:287
char use_buckets
Definition: kutil.h:377
LSet L
Definition: kutil.h:318
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:272
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:269
pLDegProc pOrigLDeg
Definition: kutil.h:288
char update
Definition: kutil.h:375
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:290
void reorderT(kStrategy strat)
Definition: kstd1.cc:889
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:530
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3463
void updateT(kStrategy strat)
Definition: kstd1.cc:1181
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:982
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5196
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define TEST_OPT_WEIGHTM
Definition: options.h:119
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3586
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:583
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:751
short * ecartWeights
Definition: weight0.c:28

◆ hasPurePower() [1/2]

BOOLEAN hasPurePower ( const poly  p,
int  last,
int *  length,
kStrategy  strat 
)

Definition at line 960 of file kstd1.cc.

961 {
962  poly h;
963  int i;
964 
965  if (pNext(p) == strat->tail)
966  return FALSE;
967  pp_Test(p, currRing, strat->tailRing);
968  if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
969  {
971  if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
972  if (i == last)
973  {
974  *length = 0;
975  return TRUE;
976  }
977  *length = 1;
978  h = pNext(p);
979  while (h != NULL)
980  {
981  i = p_IsPurePower(h, strat->tailRing);
982  if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
983  if (i==last) return TRUE;
984  (*length)++;
985  pIter(h);
986  }
987  }
988  return FALSE;
989 }
int ak
Definition: kutil.h:346
poly tail
Definition: kutil.h:327
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition: coeffs.h:516
static poly last
Definition: hdegree.cc:1077
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
#define pIter(p)
Definition: monomials.h:44
#define pNext(p)
Definition: monomials.h:43
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:51
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1218
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:313
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:165

◆ hasPurePower() [2/2]

BOOLEAN hasPurePower ( LObject L,
int  last,
int *  length,
kStrategy  strat 
)

Definition at line 991 of file kstd1.cc.

992 {
993  if (L->bucket != NULL)
994  {
995  poly p = L->CanonicalizeP();
996  BOOLEAN ret = hasPurePower(p, last, length, strat);
997  pNext(p) = NULL;
998  return ret;
999  }
1000  else
1001  {
1002  return hasPurePower(L->p, last, length, strat);
1003  }
1004 }
int BOOLEAN
Definition: auxiliary.h:85
BOOLEAN hasPurePower(const poly p, int last, int *length, kStrategy strat)
Definition: kstd1.cc:960

◆ initBba()

void initBba ( kStrategy  strat)

Definition at line 1338 of file kstd1.cc.

1339 {
1340  /* setting global variables ------------------- */
1341  strat->enterS = enterSBba;
1342  strat->red = redHoney;
1343  if (strat->honey)
1344  strat->red = redHoney;
1345  else if (currRing->pLexOrder && !strat->homog)
1346  strat->red = redLazy;
1347  else
1348  {
1349  strat->LazyPass *=4;
1350  strat->red = redHomog;
1351  }
1352  if (rField_is_Ring(currRing))
1353  {
1354  strat->red = redRing;
1355  }
1356  if (currRing->pLexOrder && strat->honey)
1357  strat->initEcart = initEcartNormal;
1358  else
1359  strat->initEcart = initEcartBBA;
1360  if (strat->honey)
1362  else
1364 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1365 // {
1366 // //interred machen Aenderung
1367 // strat->pOrigFDeg=pFDeg;
1368 // strat->pOrigLDeg=pLDeg;
1369 // //h=ggetid("ecart");
1370 // //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1371 // //{
1372 // // ecartWeights=iv2array(IDINTVEC(h));
1373 // //}
1374 // //else
1375 // {
1376 // ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1377 // /*uses automatic computation of the ecartWeights to set them*/
1378 // kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1379 // }
1380 // pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1381 // if (TEST_OPT_PROT)
1382 // {
1383 // for(i=1; i<=(currRing->N); i++)
1384 // Print(" %d",ecartWeights[i]);
1385 // PrintLn();
1386 // mflush();
1387 // }
1388 // }
1389 }
char honey
Definition: kutil.h:371
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:278
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:277
void(* initEcart)(TObject *L)
Definition: kutil.h:271
int LazyPass
Definition: kutil.h:346
char homog
Definition: kutil.h:366
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1402
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:548
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1254
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:438
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1261
void initEcartNormal(TObject *h)
Definition: kutil.cc:1239
void initEcartBBA(TObject *h)
Definition: kutil.cc:1247
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1254

◆ initMora()

void initMora ( ideal  F,
kStrategy  strat 
)

Definition at line 1461 of file kstd1.cc.

1462 {
1463  int i,j;
1464 
1465  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1466  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1467  strat->enterS = enterSMora;
1468  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1469  strat->posInLOld = strat->posInL;
1470  strat->posInLOldFlag = TRUE;
1471  strat->initEcart = initEcartNormal;
1472  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1473  if ( strat->kHEdgeFound )
1474  strat->kNoether = pCopy((currRing->ppNoether));
1475  else if (strat->kHEdgeFound || strat->homog)
1476  strat->red = redFirst; /*take the first possible in T*/
1477  else
1478  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1479  if (strat->kHEdgeFound)
1480  {
1481  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1482  strat->posInT = posInT2;
1483  }
1484  else
1485  {
1486  strat->HCord = 32000;/*- very large -*/
1487  }
1488 
1489  if (rField_is_Ring(currRing))
1490  strat->red = redRiloc;
1491 
1492  /*reads the ecartWeights used for Graebes method from the
1493  *intvec ecart and set ecartWeights
1494  */
1495  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1496  {
1497  //interred machen Aenderung
1498  strat->pOrigFDeg=currRing->pFDeg;
1499  strat->pOrigLDeg=currRing->pLDeg;
1500  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1501  /*uses automatic computation of the ecartWeights to set them*/
1503 
1505  if (TEST_OPT_PROT)
1506  {
1507  for(i=1; i<=(currRing->N); i++)
1508  Print(" %d",ecartWeights[i]);
1509  PrintLn();
1510  mflush();
1511  }
1512  }
1513  kOptimizeLDeg(currRing->pLDeg, strat);
1514 }
BOOLEAN * NotUsedAxis
Definition: kutil.h:325
int HCord
Definition: kutil.h:348
int j
Definition: facHensel.cc:105
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:168
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:99
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:344
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1274
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define TEST_OPT_PROT
Definition: options.h:102
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3574
#define pCopy(p)
return a copy of the poly
Definition: polys.h:172
#define mflush()
Definition: reporter.h:57
#define IDELEMS(i)
Definition: simpleideals.h:24
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:223
long maxdegreeWecart(poly p, int *l, ring r)
Definition: weight.cc:253
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition: weight.cc:188

◆ initSba()

void initSba ( ideal  F,
kStrategy  strat 
)

Definition at line 1391 of file kstd1.cc.

1392 {
1393  int i;
1394  //idhdl h;
1395  /* setting global variables ------------------- */
1396  strat->enterS = enterSSba;
1397  strat->red2 = redHoney;
1398  if (strat->honey)
1399  strat->red2 = redHoney;
1400  else if (currRing->pLexOrder && !strat->homog)
1401  strat->red2 = redLazy;
1402  else
1403  {
1404  strat->LazyPass *=4;
1405  strat->red2 = redHomog;
1406  }
1407  if (rField_is_Ring(currRing))
1408  {
1410  {strat->red2 = redRiloc;}
1411  else
1412  {strat->red2 = redRing;}
1413  }
1414  if (currRing->pLexOrder && strat->honey)
1415  strat->initEcart = initEcartNormal;
1416  else
1417  strat->initEcart = initEcartBBA;
1418  if (strat->honey)
1420  else
1422  //strat->kIdeal = NULL;
1423  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1424  //else strat->kIdeal->rtyp=MODUL_CMD;
1425  //strat->kIdeal->data=(void *)strat->Shdl;
1426  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1427  {
1428  //interred machen Aenderung
1429  strat->pOrigFDeg = currRing->pFDeg;
1430  strat->pOrigLDeg = currRing->pLDeg;
1431  //h=ggetid("ecart");
1432  //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1433  //{
1434  // ecartWeights=iv2array(IDINTVEC(h));
1435  //}
1436  //else
1437  {
1438  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1439  /*uses automatic computation of the ecartWeights to set them*/
1441  }
1443  if (TEST_OPT_PROT)
1444  {
1445  for(i=1; i<=(currRing->N); i++)
1446  Print(" %d",ecartWeights[i]);
1447  PrintLn();
1448  mflush();
1449  }
1450  }
1451  // for sig-safe reductions in signature-based
1452  // standard basis computations
1454  strat->red = redSigRing;
1455  else
1456  strat->red = redSig;
1457  //strat->sbaOrder = 1;
1458  strat->currIdx = 1;
1459 }
int currIdx
Definition: kutil.h:308
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:270
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:881
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:711
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9137
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:752

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

3007 {
3008  const ring save = currRing;
3009  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3010  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3011  if( currRing != save ) rChangeCurrRing(save);
3012  return ret;
3013 }
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2813
void rChangeCurrRing(ring r)
Definition: polys.cc:15
#define Q
Definition: sirandom.c:25

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 11583 of file kutil.cc.

11584 {
11585  PrintS("red: ");
11586  if (strat->red==redFirst) PrintS("redFirst\n");
11587  else if (strat->red==redHoney) PrintS("redHoney\n");
11588  else if (strat->red==redEcart) PrintS("redEcart\n");
11589  else if (strat->red==redHomog) PrintS("redHomog\n");
11590  else Print("%p\n",(void*)strat->red);
11591  PrintS("posInT: ");
11592  if (strat->posInT==posInT0) PrintS("posInT0\n");
11593  else if (strat->posInT==posInT1) PrintS("posInT1\n");
11594  else if (strat->posInT==posInT11) PrintS("posInT11\n");
11595  else if (strat->posInT==posInT110) PrintS("posInT110\n");
11596  else if (strat->posInT==posInT13) PrintS("posInT13\n");
11597  else if (strat->posInT==posInT15) PrintS("posInT15\n");
11598  else if (strat->posInT==posInT17) PrintS("posInT17\n");
11599  else if (strat->posInT==posInT17_c) PrintS("posInT17_c\n");
11600  else if (strat->posInT==posInT19) PrintS("posInT19\n");
11601  else if (strat->posInT==posInT2) PrintS("posInT2\n");
11602  #ifdef HAVE_RINGS
11603  else if (strat->posInT==posInT11Ring) PrintS("posInT11Ring\n");
11604  else if (strat->posInT==posInT110Ring) PrintS("posInT110Ring\n");
11605  else if (strat->posInT==posInT15Ring) PrintS("posInT15Ring\n");
11606  else if (strat->posInT==posInT17Ring) PrintS("posInT17Ring\n");
11607  else if (strat->posInT==posInT17_cRing) PrintS("posInT17_cRing\n");
11608  #endif
11609 #ifdef HAVE_MORE_POS_IN_T
11610  else if (strat->posInT==posInT_EcartFDegpLength) PrintS("posInT_EcartFDegpLength\n");
11611  else if (strat->posInT==posInT_FDegpLength) PrintS("posInT_FDegpLength\n");
11612  else if (strat->posInT==posInT_pLength) PrintS("posInT_pLength\n");
11613 #endif
11614  else if (strat->posInT==posInT_EcartpLength) PrintS("posInT_EcartpLength\n");
11615  else if (strat->posInT==posInTrg0) PrintS("posInTrg0\n");
11616  else Print("%p\n",(void*)strat->posInT);
11617  PrintS("posInL: ");
11618  if (strat->posInL==posInL0) PrintS("posInL0\n");
11619  else if (strat->posInL==posInL10) PrintS("posInL10\n");
11620  else if (strat->posInL==posInL11) PrintS("posInL11\n");
11621  else if (strat->posInL==posInL110) PrintS("posInL110\n");
11622  else if (strat->posInL==posInL13) PrintS("posInL13\n");
11623  else if (strat->posInL==posInL15) PrintS("posInL15\n");
11624  else if (strat->posInL==posInL17) PrintS("posInL17\n");
11625  else if (strat->posInL==posInL17_c) PrintS("posInL17_c\n");
11626  #ifdef HAVE_RINGS
11627  else if (strat->posInL==posInL0) PrintS("posInL0Ring\n");
11628  else if (strat->posInL==posInL11Ring) PrintS("posInL11Ring\n");
11629  else if (strat->posInL==posInL11Ringls) PrintS("posInL11Ringls\n");
11630  else if (strat->posInL==posInL110Ring) PrintS("posInL110Ring\n");
11631  else if (strat->posInL==posInL15Ring) PrintS("posInL15Ring\n");
11632  else if (strat->posInL==posInL17Ring) PrintS("posInL17Ring\n");
11633  else if (strat->posInL==posInL17_cRing) PrintS("posInL17_cRing\n");
11634  #endif
11635  else if (strat->posInL==posInLSpecial) PrintS("posInLSpecial\n");
11636  else if (strat->posInL==posInLrg0) PrintS("posInLrg0\n");
11637  else Print("%p\n",(void*)strat->posInL);
11638  PrintS("enterS: ");
11639  if (strat->enterS==enterSBba) PrintS("enterSBba\n");
11640  else if (strat->enterS==enterSMora) PrintS("enterSMora\n");
11641  else if (strat->enterS==enterSMoraNF) PrintS("enterSMoraNF\n");
11642  else Print("%p\n",(void*)strat->enterS);
11643  PrintS("initEcart: ");
11644  if (strat->initEcart==initEcartBBA) PrintS("initEcartBBA\n");
11645  else if (strat->initEcart==initEcartNormal) PrintS("initEcartNormal\n");
11646  else Print("%p\n",(void*)strat->initEcart);
11647  PrintS("initEcartPair: ");
11648  if (strat->initEcartPair==initEcartPairBba) PrintS("initEcartPairBba\n");
11649  else if (strat->initEcartPair==initEcartPairMora) PrintS("initEcartPairMora\n");
11650  else Print("%p\n",(void*)strat->initEcartPair);
11651  Print("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11652  strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11653  Print("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11654  strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11655  PrintS("chainCrit: ");
11656  if (strat->chainCrit==chainCritNormal) PrintS("chainCritNormal\n");
11657  else if (strat->chainCrit==chainCritOpt_1) PrintS("chainCritOpt_1\n");
11658  else Print("%p\n",(void*)strat->chainCrit);
11659  Print("posInLDependsOnLength=%d\n",
11660  strat->posInLDependsOnLength);
11661  PrintS(showOption());PrintLn();
11662  PrintS("LDeg: ");
11663  if (currRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11664  else if (currRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11665  else if (currRing->pLDeg==pLDegb) PrintS("pLDegb");
11666  else if (currRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11667  else if (currRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11668  else if (currRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11669  else if (currRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11670  else if (currRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11671  else if (currRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11672  else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11673  else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11674  else if (currRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11675  else Print("? (%lx)", (long)currRing->pLDeg);
11676  PrintS(" / ");
11677  if (strat->tailRing->pLDeg==pLDeg0) PrintS("pLDeg0");
11678  else if (strat->tailRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
11679  else if (strat->tailRing->pLDeg==pLDegb) PrintS("pLDegb");
11680  else if (strat->tailRing->pLDeg==pLDeg1) PrintS("pLDeg1");
11681  else if (strat->tailRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
11682  else if (strat->tailRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
11683  else if (strat->tailRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
11684  else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
11685  else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
11686  else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
11687  else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
11688  else if (strat->tailRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
11689  else Print("? (%lx)", (long)strat->tailRing->pLDeg);
11690  PrintLn();
11691  PrintS("currRing->pFDeg: ");
11692  if (currRing->pFDeg==p_Totaldegree) PrintS("p_Totaldegree");
11693  else if (currRing->pFDeg==p_WFirstTotalDegree) PrintS("pWFirstTotalDegree");
11694  else if (currRing->pFDeg==p_Deg) PrintS("p_Deg");
11695  else if (currRing->pFDeg==kHomModDeg) PrintS("kHomModDeg");
11696  else if (currRing->pFDeg==totaldegreeWecart) PrintS("totaldegreeWecart");
11697  else if (currRing->pFDeg==p_WTotaldegree) PrintS("p_WTotaldegree");
11698  else Print("? (%lx)", (long)currRing->pFDeg);
11699  PrintLn();
11700  Print(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11701  if(TEST_OPT_DEGBOUND)
11702  Print(" degBound: %d\n", Kstd1_deg);
11703 
11704  if( ecartWeights != NULL )
11705  {
11706  PrintS("ecartWeights: ");
11707  for (int i = rVar(currRing); i > 0; i--)
11708  Print("%hd ", ecartWeights[i]);
11709  PrintLn();
11711  }
11712 
11713 #ifndef SING_NDEBUG
11715 #endif
11716 }
int syzComp
Definition: kutil.h:347
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:282
char noTailReduction
Definition: kutil.h:372
char sugarCrit
Definition: kutil.h:371
char Gebauer
Definition: kutil.h:372
int LazyDegree
Definition: kutil.h:346
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2083
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6764
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6878
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6521
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5631
int posInTrg0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5303
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:530
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6265
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:168
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5226
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5168
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5421
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1328
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5497
int posInT0(const TSet, const int length, LObject &)
Definition: kutil.cc:5157
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6609
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6562
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11549
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5468
int Kstd1_deg
Definition: kutil.cc:236
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5965
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3337
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5262
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6644
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5738
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11458
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5536
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5922
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6335
char * showOption()
Definition: misc_ip.cc:727
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6720
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5379
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6679
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5865
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5590
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5692
int posInLrg0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6437
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1274
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5799
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6814
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11512
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3124
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6223
#define assume(x)
Definition: mod2.h:390
#define TEST_OPT_DEGBOUND
Definition: options.h:112
long pLDegb(poly p, int *l, const ring r)
Definition: p_polys.cc:803
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:967
long p_WFirstTotalDegree(poly p, const ring r)
Definition: p_polys.cc:588
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1030
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1060
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:933
long pLDeg1(poly p, int *l, const ring r)
Definition: p_polys.cc:833
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:902
long p_WTotaldegree(poly p, const ring r)
Definition: p_polys.cc:605
long pLDeg1c(poly p, int *l, const ring r)
Definition: p_polys.cc:869
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:997
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:762
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:731
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:579
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1453
void rDebugPrint(const ring r)
Definition: ring.cc:3998
static int rGetCurrSyzLimit(const ring r)
Definition: ring.h:714
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition: ring.h:711

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r 
)

Definition at line 2083 of file kstd1.cc.

2084 {
2085  int i;
2086  long j=0;
2087 
2088  for (i=r->N;i>0;i--)
2089  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2090  if (kModW == NULL) return j;
2091  i = __p_GetComp(p,r);
2092  if (i==0) return j;
2093  return j+(*kModW)[i-1];
2094 }
intvec * kModW
Definition: kstd1.cc:2071
#define __p_GetComp(p, r)
Definition: monomials.h:70
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 
)

Definition at line 3387 of file kstd1.cc.

3388 {
3389 #ifdef HAVE_PLURAL
3390  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3391 #endif
3394  )
3395  return kInterRedOld(F,Q);
3396 
3397  //return kInterRedOld(F,Q);
3398 
3399  BITSET save1;
3400  SI_SAVE_OPT1(save1);
3401  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3403  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3404  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3405  //extern char * showOption() ;
3406  //Print("%s\n",showOption());
3407 
3408  int need_retry;
3409  int counter=3;
3410  ideal res, res1;
3411  int elems;
3412  ideal null=NULL;
3413  if ((Q==NULL) || (!TEST_OPT_REDSB))
3414  {
3415  elems=idElem(F);
3416  res=kInterRedBba(F,Q,need_retry);
3417  }
3418  else
3419  {
3420  ideal FF=idSimpleAdd(F,Q);
3421  res=kInterRedBba(FF,NULL,need_retry);
3422  idDelete(&FF);
3423  null=idInit(1,1);
3424  if (need_retry)
3425  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3426  else
3427  res1=kNF(null,Q,res);
3428  idDelete(&res);
3429  res=res1;
3430  need_retry=1;
3431  }
3432  if (idElem(res)<=1) need_retry=0;
3433  while (need_retry && (counter>0))
3434  {
3435  #ifdef KDEBUG
3436  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3437  #endif
3438  res1=kInterRedBba(res,Q,need_retry);
3439  int new_elems=idElem(res1);
3440  counter -= (new_elems >= elems);
3441  elems = new_elems;
3442  idDelete(&res);
3443  if (idElem(res1)<=1) need_retry=0;
3444  if ((Q!=NULL) && (TEST_OPT_REDSB))
3445  {
3446  if (need_retry)
3447  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3448  else
3449  res=kNF(null,Q,res1);
3450  idDelete(&res1);
3451  }
3452  else
3453  res = res1;
3454  if (idElem(res)<=1) need_retry=0;
3455  }
3456  if (null!=NULL) idDelete(&null);
3457  SI_RESTORE_OPT1(save1);
3458  idSkipZeroes(res);
3459  return res;
3460 }
CanonicalForm res
Definition: facAbsFact.cc:64
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
ideal kInterRedOld(ideal F, ideal Q)
Definition: kstd1.cc:3019
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3111
#define KSTD_NF_LAZY
Definition: kstd1.h:17
unsigned si_opt_1
Definition: options.c:5
#define SI_SAVE_OPT1(A)
Definition: options.h:22
#define SI_RESTORE_OPT1(A)
Definition: options.h:25
#define OPT_REDTHROUGH
Definition: options.h:81
#define Sy_bit(x)
Definition: options.h:32
#define TEST_OPT_REDSB
Definition: options.h:103
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:404
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:507
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
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:18

◆ kInterRedBba()

ideal kInterRedBba ( ideal  F,
ideal  Q,
int &  need_retry 
)

Definition at line 3111 of file kstd1.cc.

3112 {
3113  need_retry=0;
3114  int red_result = 1;
3115  int olddeg,reduc;
3116  BOOLEAN withT = FALSE;
3117  // BOOLEAN toReset=FALSE;
3118  kStrategy strat=new skStrategy;
3119  tHomog h;
3120  intvec * w=NULL;
3121 
3123  strat->LazyPass=20;
3124  else
3125  strat->LazyPass=2;
3126  strat->LazyDegree = 1;
3127  strat->ak = id_RankFreeModule(F,currRing);
3128  strat->syzComp = strat->ak;
3129  strat->kModW=kModW=NULL;
3130  strat->kHomW=kHomW=NULL;
3131  if (strat->ak == 0)
3132  {
3133  h = (tHomog)idHomIdeal(F,Q);
3134  w=NULL;
3135  }
3136  else if (!TEST_OPT_DEGBOUND)
3137  {
3138  h = (tHomog)idHomModule(F,Q,&w);
3139  }
3140  else
3141  h = isNotHomog;
3142  if (h==isHomog)
3143  {
3144  if (strat->ak > 0 && (w!=NULL) && (w!=NULL))
3145  {
3146  strat->kModW = kModW = w;
3147  strat->pOrigFDeg = currRing->pFDeg;
3148  strat->pOrigLDeg = currRing->pLDeg;
3150  // toReset = TRUE;
3151  }
3152  strat->LazyPass*=2;
3153  }
3154  strat->homog=h;
3155 #ifdef KDEBUG
3156  idTest(F);
3157 #endif
3158 
3159  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3161  initBuchMoraPosRing(strat);
3162  else
3163  initBuchMoraPos(strat);
3164  initBba(strat);
3165  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3166  strat->posInL=posInL0; /* ord according pComp */
3167 
3168  /*Shdl=*/initBuchMora(F, Q, strat);
3169  reduc = olddeg = 0;
3170 
3171 #ifndef NO_BUCKETS
3172  if (!TEST_OPT_NOT_BUCKETS)
3173  strat->use_buckets = 1;
3174 #endif
3175 
3176  // redtailBBa against T for inhomogenous input
3177  if (!TEST_OPT_OLDSTD)
3178  withT = ! strat->homog;
3179 
3180  // strat->posInT = posInT_pLength;
3181  kTest_TS(strat);
3182 
3183 #ifdef HAVE_TAIL_RING
3184  kStratInitChangeTailRing(strat);
3185 #endif
3186 
3187  /* compute------------------------------------------------------- */
3188  while (strat->Ll >= 0)
3189  {
3190  #ifdef KDEBUG
3191  if (TEST_OPT_DEBUG) messageSets(strat);
3192  #endif
3193  if (strat->Ll== 0) strat->interpt=TRUE;
3194  /* picks the last element from the lazyset L */
3195  strat->P = strat->L[strat->Ll];
3196  strat->Ll--;
3197 
3198  if (strat->P.p1 == NULL)
3199  {
3200  // for input polys, prepare reduction
3201  strat->P.PrepareRed(strat->use_buckets);
3202  }
3203 
3204  if (strat->P.p == NULL && strat->P.t_p == NULL)
3205  {
3206  red_result = 0;
3207  }
3208  else
3209  {
3210  if (TEST_OPT_PROT)
3211  message(strat->P.pFDeg(),
3212  &olddeg,&reduc,strat, red_result);
3213 
3214  /* reduction of the element chosen from L */
3215  red_result = strat->red(&strat->P,strat);
3216  }
3217 
3218  // reduction to non-zero new poly
3219  if (red_result == 1)
3220  {
3221  /* statistic */
3222  if (TEST_OPT_PROT) PrintS("s");
3223 
3224  // get the polynomial (canonicalize bucket, make sure P.p is set)
3225  strat->P.GetP(strat->lmBin);
3226 
3227  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3228 
3229  // reduce the tail and normalize poly
3230  // in the ring case we cannot expect LC(f) = 1,
3231  // therefore we call pCleardenom instead of pNorm
3233  {
3234  strat->P.pCleardenom();
3235  if (0)
3236  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3237  {
3238  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3239  strat->P.pCleardenom();
3240  }
3241  }
3242  else
3243  {
3244  strat->P.pNorm();
3245  if (0)
3246  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3247  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3248  }
3249 
3250 #ifdef KDEBUG
3251  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3252 #endif
3253 
3254  // enter into S, L, and T
3255  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3256  {
3257  enterT(strat->P, strat);
3258  // posInS only depends on the leading term
3259  strat->enterS(strat->P, pos, strat, strat->tl);
3260 
3261  if (pos<strat->sl)
3262  {
3263  need_retry++;
3264  // move all "larger" elements fromS to L
3265  // remove them from T
3266  int ii=pos+1;
3267  for(;ii<=strat->sl;ii++)
3268  {
3269  LObject h;
3270  memset(&h,0,sizeof(h));
3271  h.tailRing=strat->tailRing;
3272  h.p=strat->S[ii]; strat->S[ii]=NULL;
3273  strat->initEcart(&h);
3274  h.sev=strat->sevS[ii];
3275  int jj=strat->tl;
3276  while (jj>=0)
3277  {
3278  if (strat->T[jj].p==h.p)
3279  {
3280  strat->T[jj].p=NULL;
3281  if (jj<strat->tl)
3282  {
3283  memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3284  (strat->tl-jj)*sizeof(strat->T[jj]));
3285  memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3286  (strat->tl-jj)*sizeof(strat->sevT[jj]));
3287  }
3288  strat->tl--;
3289  break;
3290  }
3291  jj--;
3292  }
3293  int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3294  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3295  #ifdef KDEBUG
3296  if (TEST_OPT_DEBUG)
3297  {
3298  Print("move S[%d] -> L[%d]: ",ii,pos);
3299  p_wrp(h.p,currRing, strat->tailRing);
3300  PrintLn();
3301  }
3302  #endif
3303  }
3304  if (strat->fromQ!=NULL)
3305  {
3306  for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3307  }
3308  strat->sl=pos;
3309  }
3310  }
3311  else
3312  {
3313  // clean P
3314  }
3315  if (strat->P.lcm!=NULL)
3316 #ifdef HAVE_RINGS
3317  pLmDelete(strat->P.lcm);
3318 #else
3319  pLmFree(strat->P.lcm);
3320 #endif
3321  }
3322 
3323 #ifdef KDEBUG
3324  if (TEST_OPT_DEBUG)
3325  {
3326  messageSets(strat);
3327  }
3328  memset(&(strat->P), 0, sizeof(strat->P));
3329 #endif
3330  //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3331  }
3332 #ifdef KDEBUG
3333  //if (TEST_OPT_DEBUG) messageSets(strat);
3334 #endif
3335  /* complete reduction of the standard basis--------- */
3336 
3337  if((need_retry<=0) && (TEST_OPT_REDSB))
3338  {
3339  completeReduce(strat);
3340  if (strat->completeReduce_retry)
3341  {
3342  // completeReduce needed larger exponents, retry
3343  // hopefully: kStratChangeTailRing already provided a larger tailRing
3344  // (otherwise: it will fail again)
3345  strat->completeReduce_retry=FALSE;
3346  completeReduce(strat);
3347  if (strat->completeReduce_retry)
3348  {
3349 #ifdef HAVE_TAIL_RING
3350  if(currRing->bitmask>strat->tailRing->bitmask)
3351  {
3352  // retry without T
3353  strat->completeReduce_retry=FALSE;
3354  cleanT(strat);strat->tailRing=currRing;
3355  int i;
3356  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3357  completeReduce(strat);
3358  }
3359  if (strat->completeReduce_retry)
3360 #endif
3361  Werror("exponent bound is %ld",currRing->bitmask);
3362  }
3363  }
3364  }
3365  else if (TEST_OPT_PROT) PrintLn();
3366 
3367 
3368  /* release temp data-------------------------------- */
3369  exitBuchMora(strat);
3370 // if (TEST_OPT_WEIGHTM)
3371 // {
3372 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3373 // if (ecartWeights)
3374 // {
3375 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3376 // ecartWeights=NULL;
3377 // }
3378 // }
3379  //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3380  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3381  ideal res=strat->Shdl;
3382  strat->Shdl=NULL;
3383  delete strat;
3384  if (w!=NULL) delete w;
3385  return res;
3386 }
Definition: intvec.h:21
intvec * kModW
Definition: kutil.h:328
int * S_2_R
Definition: kutil.h:335
omBin lmBin
Definition: kutil.h:337
polyset S
Definition: kutil.h:297
unsigned long * sevT
Definition: kutil.h:316
intvec * kHomW
Definition: kutil.h:329
ideal Shdl
Definition: kutil.h:294
intset fromQ
Definition: kutil.h:312
char interpt
Definition: kutil.h:365
char completeReduce_retry
Definition: kutil.h:397
LObject P
Definition: kutil.h:293
int Lmax
Definition: kutil.h:344
int sl
Definition: kutil.h:341
unsigned long * sevS
Definition: kutil.h:313
const CanonicalForm & w
Definition: facAbsFact.cc:55
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
#define idTest(id)
Definition: ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:91
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1095
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2073
intvec * kHomW
Definition: kstd1.cc:2071
void initBba(kStrategy strat)
Definition: kstd1.cc:1338
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7729
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9878
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1215
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9705
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:9954
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4935
void cleanT(kStrategy strat)
Definition: kutil.cc:537
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10187
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11136
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9554
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10399
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9791
void messageSets(kStrategy strat)
Definition: kutil.cc:7800
#define TEST_OPT_IDLIFT
Definition: options.h:127
#define TEST_OPT_OLDSTD
Definition: options.h:121
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:104
#define pGetComp(p)
Component.
Definition: polys.h:37
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
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
void Werror(const char *fmt,...)
Definition: reporter.cc:189
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:540
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
tHomog
Definition: structs.h:38
@ isHomog
Definition: structs.h:40
@ isNotHomog
Definition: structs.h:39

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
ideal  Q 
)

Definition at line 3019 of file kstd1.cc.

3020 {
3021  int j;
3022  kStrategy strat = new skStrategy;
3023 
3024  ideal tempF = F;
3025  ideal tempQ = Q;
3026 
3027 #ifdef HAVE_PLURAL
3028  if(rIsSCA(currRing))
3029  {
3030  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3031  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3032  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3033 
3034  // this should be done on the upper level!!! :
3035  // tempQ = SCAQuotient(currRing);
3036 
3037  if(Q == currRing->qideal)
3038  tempQ = SCAQuotient(currRing);
3039  }
3040 #endif
3041 
3042 // if (TEST_OPT_PROT)
3043 // {
3044 // writeTime("start InterRed:");
3045 // mflush();
3046 // }
3047  //strat->syzComp = 0;
3048  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3049  strat->kNoether=pCopy((currRing->ppNoether));
3050  strat->ak = id_RankFreeModule(tempF,currRing);
3051  initBuchMoraCrit(strat);
3052  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3053  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3054  strat->enterS = enterSBba;
3055  strat->posInT = posInT17;
3056  strat->initEcart = initEcartNormal;
3057  strat->sl = -1;
3058  strat->tl = -1;
3059  strat->tmax = setmaxT;
3060  strat->T = initT();
3061  strat->R = initR();
3062  strat->sevT = initsevT();
3064  initS(tempF, tempQ, strat);
3065  if (TEST_OPT_REDSB)
3066  strat->noTailReduction=FALSE;
3067  updateS(TRUE,strat);
3069  completeReduce(strat);
3070  //else if (TEST_OPT_PROT) PrintLn();
3071  cleanT(strat);
3072  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3073  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3074  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3075  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3076  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3077  omfree(strat->sevT);
3078  omfree(strat->S_2_R);
3079  omfree(strat->R);
3080 
3081  if (strat->fromQ)
3082  {
3083  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3084  {
3085  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3086  }
3087  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3088  }
3089 // if (TEST_OPT_PROT)
3090 // {
3091 // writeTime("end Interred:");
3092 // mflush();
3093 // }
3094  ideal shdl=strat->Shdl;
3095  idSkipZeroes(shdl);
3096  if (strat->fromQ)
3097  {
3098  strat->fromQ=NULL;
3099  ideal res=kInterRed(shdl,NULL);
3100  idDelete(&shdl);
3101  shdl=res;
3102  }
3103  delete(strat);
3104 #ifdef HAVE_PLURAL
3105  if( tempF != F )
3106  id_Delete( &tempF, currRing);
3107 #endif
3108  return shdl;
3109 }
intset ecartS
Definition: kutil.h:300
TObject ** R
Definition: kutil.h:333
poly kHEdge
Definition: kutil.h:320
int tmax
Definition: kutil.h:343
KINLINE unsigned long * initsevT()
Definition: kInline.h:97
KINLINE TSet initT()
Definition: kInline.h:81
KINLINE TObject ** initR()
Definition: kInline.h:92
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3387
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7848
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8807
#define setmaxT
Definition: kutil.h:33
class sTObject TObject
Definition: kutil.h:53
static bool rIsSCA(const ring r)
Definition: nc.h:198
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 pDelete(p_ptr)
Definition: polys.h:173
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

◆ kMin_std()

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

Definition at line 2664 of file kstd1.cc.

2666 {
2667  if(idIs0(F))
2668  {
2669  M=idInit(1,F->rank);
2670  return idInit(1,F->rank);
2671  }
2673  {
2674  ideal sb;
2675  sb = kStd(F, Q, h, w, hilb);
2676  idSkipZeroes(sb);
2677  if(IDELEMS(sb) <= IDELEMS(F))
2678  {
2679  M = idCopy(sb);
2680  idSkipZeroes(M);
2681  return(sb);
2682  }
2683  else
2684  {
2685  M = idCopy(F);
2686  idSkipZeroes(M);
2687  return(sb);
2688  }
2689  }
2690  ideal r=NULL;
2691  int Kstd1_OldDeg = Kstd1_deg,i;
2692  intvec* temp_w=NULL;
2693  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2694  BOOLEAN delete_w=(w==NULL);
2695  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
2696  kStrategy strat=new skStrategy;
2697 
2698  if(!TEST_OPT_RETURN_SB)
2699  strat->syzComp = syzComp;
2701  strat->LazyPass=20;
2702  else
2703  strat->LazyPass=2;
2704  strat->LazyDegree = 1;
2705  strat->minim=(reduced % 2)+1;
2706  strat->ak = id_RankFreeModule(F,currRing);
2707  if (delete_w)
2708  {
2709  temp_w=new intvec((strat->ak)+1);
2710  w = &temp_w;
2711  }
2712  if (h==testHomog)
2713  {
2714  if (strat->ak == 0)
2715  {
2716  h = (tHomog)idHomIdeal(F,Q);
2717  w=NULL;
2718  }
2719  else
2720  {
2721  h = (tHomog)idHomModule(F,Q,w);
2722  }
2723  }
2724  if (h==isHomog)
2725  {
2726  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2727  {
2728  kModW = *w;
2729  strat->kModW = *w;
2730  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
2731  strat->pOrigFDeg = currRing->pFDeg;
2732  strat->pOrigLDeg = currRing->pLDeg;
2734 
2735  toReset = TRUE;
2736  if (reduced>1)
2737  {
2738  Kstd1_OldDeg=Kstd1_deg;
2739  Kstd1_deg = -1;
2740  for (i=IDELEMS(F)-1;i>=0;i--)
2741  {
2742  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
2743  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
2744  }
2745  }
2746  }
2747  currRing->pLexOrder = TRUE;
2748  strat->LazyPass*=2;
2749  }
2750  strat->homog=h;
2752  {
2753  if (w!=NULL)
2754  r=mora(F,Q,*w,hilb,strat);
2755  else
2756  r=mora(F,Q,NULL,hilb,strat);
2757  }
2758  else
2759  {
2760  if (w!=NULL)
2761  r=bba(F,Q,*w,hilb,strat);
2762  else
2763  r=bba(F,Q,NULL,hilb,strat);
2764  }
2765 #ifdef KDEBUG
2766  {
2767  int i;
2768  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
2769  }
2770 #endif
2771  idSkipZeroes(r);
2772  if (toReset)
2773  {
2774  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2775  kModW = NULL;
2776  }
2777  currRing->pLexOrder = b;
2778  HCord=strat->HCord;
2779  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
2780  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
2781  {
2782  M=idInit(1,F->rank);
2783  M->m[0]=pOne();
2784  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
2785  if (strat->M!=NULL) idDelete(&strat->M);
2786  }
2787  else if (strat->M==NULL)
2788  {
2789  M=idInit(1,F->rank);
2790  WarnS("no minimal generating set computed");
2791  }
2792  else
2793  {
2794  idSkipZeroes(strat->M);
2795  M=strat->M;
2796  }
2797  delete(strat);
2798  if (reduced>2)
2799  {
2800  Kstd1_deg=Kstd1_OldDeg;
2801  if (!oldDegBound)
2803  }
2804  else
2805  {
2806  if (IDELEMS(M)>IDELEMS(r)) {
2807  idDelete(&M);
2808  M=idCopy(r); }
2809  }
2810  return r;
2811 }
CanonicalForm b
Definition: cfModGcd.cc:4044
int minim
Definition: kutil.h:351
ideal M
Definition: kutil.h:296
#define WarnS
Definition: emacs.cc:78
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
ideal idCopy(ideal A)
Definition: ideals.h:60
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd1.cc:1518
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:2096
int Kstd1_deg
Definition: kstd1.h:47
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:1919
int HCord
Definition: kutil.cc:235
#define TEST_OPT_RETURN_SB
Definition: options.h:111
#define OPT_DEGBOUND
Definition: options.h:89
#define pTest(p)
Definition: polys.h:401
#define pIsConstant(p)
like above, except that Comp might be != 0
Definition: polys.h:225
#define pOne()
Definition: polys.h:301
#define M
Definition: sirandom.c:24
@ testHomog
Definition: structs.h:41

◆ kModDeg()

long kModDeg ( poly  p,
ring  r 
)

Definition at line 2073 of file kstd1.cc.

2074 {
2075  long o=p_WDegree(p, r);
2076  long i=__p_GetComp(p, r);
2077  if (i==0) return o;
2078  //assume((i>0) && (i<=kModW->length()));
2079  if (i<=kModW->length())
2080  return o+(*kModW)[i-1];
2081  return o;
2082 }
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:706

◆ kMoraUseBucket()

static BOOLEAN kMoraUseBucket ( kStrategy  strat)
static

Definition at line 3463 of file kstd1.cc.

3464 {
3465 #ifdef MORA_USE_BUCKETS
3467  return FALSE;
3468  if (strat->red == redFirst)
3469  {
3470 #ifdef NO_LDEG
3471  if (strat->syzComp==0)
3472  return TRUE;
3473 #else
3474  if ((strat->homog || strat->honey) && (strat->syzComp==0))
3475  return TRUE;
3476 #endif
3477  }
3478  else
3479  {
3480  #ifdef HAVE_RINGS
3481  assume(strat->red == redEcart || strat->red == redRiloc);
3482  #else
3483  assume(strat->red == redEcart);
3484  #endif
3485  if (strat->honey && (strat->syzComp==0))
3486  return TRUE;
3487  }
3488 #endif
3489  return FALSE;
3490 }

◆ kNF() [1/2]

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

Definition at line 2901 of file kstd1.cc.

2902 {
2903  ideal res;
2904  if (TEST_OPT_PROT)
2905  {
2906  Print("(S:%d)",IDELEMS(p));mflush();
2907  }
2908  if (idIs0(p))
2909  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
2910 
2911  ideal pp = p;
2912 #ifdef HAVE_PLURAL
2913  if(rIsSCA(currRing))
2914  {
2915  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2916  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2917  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
2918 
2919  if(Q == currRing->qideal)
2920  Q = SCAQuotient(currRing);
2921  }
2922 #endif
2923 
2924  if ((idIs0(F))&&(Q==NULL))
2925  {
2926 #ifdef HAVE_PLURAL
2927  if(p != pp)
2928  return pp;
2929 #endif
2930  return idCopy(p); /*F+Q=0*/
2931  }
2932 
2933  kStrategy strat=new skStrategy;
2934  strat->syzComp = syzComp;
2936  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
2937  {
2938  strat->ak = si_max(strat->ak,(int)F->rank);
2939  }
2940 
2942  res=kNF1(F,Q,pp,strat,lazyReduce);
2943  else
2944  res=kNF2(F,Q,pp,strat,lazyReduce);
2945  delete(strat);
2946 
2947 #ifdef HAVE_PLURAL
2948  if(pp != p)
2949  id_Delete(&pp, currRing);
2950 #endif
2951 
2952  return res;
2953 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:1774
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3245

◆ kNF() [2/2]

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

Definition at line 2813 of file kstd1.cc.

2814 {
2815  if (p==NULL)
2816  return NULL;
2817 
2818  poly pp = p;
2819 
2820 #ifdef HAVE_PLURAL
2821  if(rIsSCA(currRing))
2822  {
2823  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2824  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2825  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
2826 
2827  if(Q == currRing->qideal)
2828  Q = SCAQuotient(currRing);
2829  }
2830 #endif
2831 
2832  if ((idIs0(F))&&(Q==NULL))
2833  {
2834 #ifdef HAVE_PLURAL
2835  if(p != pp)
2836  return pp;
2837 #endif
2838  return pCopy(p); /*F+Q=0*/
2839  }
2840 
2841  kStrategy strat=new skStrategy;
2842  strat->syzComp = syzComp;
2843  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
2844  poly res;
2845 
2847  res=kNF1(F,Q,pp,strat,lazyReduce);
2848  else
2849  res=kNF2(F,Q,pp,strat,lazyReduce);
2850  delete(strat);
2851 
2852 #ifdef HAVE_PLURAL
2853  if(pp != p)
2854  p_Delete(&pp, currRing);
2855 #endif
2856  return res;
2857 }
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:857
#define pMaxComp(p)
Definition: polys.h:285

◆ kNF1() [1/2]

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

Definition at line 1918 of file kstd1.cc.

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

◆ kNF1() [2/2]

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

Definition at line 1774 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 2955 of file kstd1.cc.

2956 {
2957  ideal res;
2958  if (TEST_OPT_PROT)
2959  {
2960  Print("(S:%d)",IDELEMS(p));mflush();
2961  }
2962  if (idIs0(p))
2963  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
2964 
2965  ideal pp = p;
2966 #ifdef HAVE_PLURAL
2967  if(rIsSCA(currRing))
2968  {
2969  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2970  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2971  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
2972 
2973  if(Q == currRing->qideal)
2974  Q = SCAQuotient(currRing);
2975  }
2976 #endif
2977 
2978  if ((idIs0(F))&&(Q==NULL))
2979  {
2980 #ifdef HAVE_PLURAL
2981  if(p != pp)
2982  return pp;
2983 #endif
2984  return idCopy(p); /*F+Q=0*/
2985  }
2986 
2987  kStrategy strat=new skStrategy;
2988  strat->syzComp = syzComp;
2990  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
2991  {
2992  strat->ak = si_max(strat->ak,(int)F->rank);
2993  }
2994 
2995  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
2996  delete(strat);
2997 
2998 #ifdef HAVE_PLURAL
2999  if(pp != p)
3000  id_Delete(&pp, currRing);
3001 #endif
3002 
3003  return res;
3004 }
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:3314

◆ kNFBound() [2/2]

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

Definition at line 2859 of file kstd1.cc.

2860 {
2861  if (p==NULL)
2862  return NULL;
2863 
2864  poly pp = p;
2865 
2866 #ifdef HAVE_PLURAL
2867  if(rIsSCA(currRing))
2868  {
2869  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2870  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2871  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
2872 
2873  if(Q == currRing->qideal)
2874  Q = SCAQuotient(currRing);
2875  }
2876 #endif
2877 
2878  if ((idIs0(F))&&(Q==NULL))
2879  {
2880 #ifdef HAVE_PLURAL
2881  if(p != pp)
2882  return pp;
2883 #endif
2884  return pCopy(p); /*F+Q=0*/
2885  }
2886 
2887  kStrategy strat=new skStrategy;
2888  strat->syzComp = syzComp;
2889  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
2890  poly res;
2891  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
2892  delete(strat);
2893 
2894 #ifdef HAVE_PLURAL
2895  if(pp != p)
2896  p_Delete(&pp, currRing);
2897 #endif
2898  return res;
2899 }

◆ kOptimizeLDeg()

static void kOptimizeLDeg ( pLDegProc  ldeg,
kStrategy  strat 
)
static

Definition at line 99 of file kstd1.cc.

100 {
101 // if (strat->ak == 0 && !rIsSyzIndexRing(currRing))
102  strat->length_pLength = TRUE;
103 // else
104 // strat->length_pLength = FALSE;
105 
106  if ((ldeg == pLDeg0c /*&& !rIsSyzIndexRing(currRing)*/) ||
107  (ldeg == pLDeg0 && strat->ak == 0))
108  {
109  strat->LDegLast = TRUE;
110  }
111  else
112  {
113  strat->LDegLast = FALSE;
114  }
115 }
char LDegLast
Definition: kutil.h:379
char length_pLength
Definition: kutil.h:381

◆ kSba()

ideal kSba ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  w,
int  sbaOrder,
int  arri,
intvec hilb,
int  syzComp,
int  newIdeal,
intvec vw 
)

Definition at line 2274 of file kstd1.cc.

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

◆ kStd()

ideal kStd ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  w,
intvec hilb,
int  syzComp,
int  newIdeal,
intvec vw,
s_poly_proc_t  sp 
)

Definition at line 2096 of file kstd1.cc.

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

◆ kStdShift()

ideal kStdShift ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  w,
intvec hilb,
int  syzComp,
int  newIdeal,
intvec vw,
int  uptodeg,
int  lV 
)

Definition at line 2564 of file kstd1.cc.

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

◆ missingAxis()

void missingAxis ( int *  last,
kStrategy  strat 
)

Definition at line 927 of file kstd1.cc.

928 {
929  int i = 0;
930  int k = 0;
931 
932  *last = 0;
934  {
935  loop
936  {
937  i++;
938  if (i > (currRing->N)) break;
939  if (strat->NotUsedAxis[i])
940  {
941  *last = i;
942  k++;
943  }
944  if (k>1)
945  {
946  *last = 0;
947  break;
948  }
949  }
950  }
951 }
int k
Definition: cfEzgcd.cc:92
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:753
#define loop
Definition: structs.h:78

◆ mora()

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

Definition at line 1518 of file kstd1.cc.

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

◆ posInL10()

int posInL10 ( const LSet  set,
const int  length,
LObject p,
const kStrategy  strat 
)

Definition at line 1010 of file kstd1.cc.

1011 {
1012  int j,dp,dL;
1013 
1014  if (length<0) return 0;
1015  if (hasPurePower(p,strat->lastAxis,&dp,strat))
1016  {
1017  int op= p->GetpFDeg() +p->ecart;
1018  for (j=length; j>=0; j--)
1019  {
1020  if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1021  return j+1;
1022  if (dp < dL)
1023  return j+1;
1024  if ((dp == dL)
1025  && (set[j].GetpFDeg()+set[j].ecart >= op))
1026  return j+1;
1027  }
1028  }
1029  j=length;
1030  loop
1031  {
1032  if (j<0) break;
1033  if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1034  j--;
1035  }
1036  return strat->posInLOld(set,j,p,strat);
1037 }

◆ redEcart()

int redEcart ( LObject h,
kStrategy  strat 
)

Definition at line 168 of file kstd1.cc.

169 {
170  int i,at,ei,li,ii;
171  int j = 0;
172  int pass = 0;
173  long d,reddeg;
174 
175  d = h->GetpFDeg()+ h->ecart;
176  reddeg = strat->LazyDegree+d;
177  h->SetShortExpVector();
178  loop
179  {
180  j = kFindDivisibleByInT(strat, h);
181  if (j < 0)
182  {
183  if (strat->honey) h->SetLength(strat->length_pLength);
184  return 1;
185  }
186 
187  ei = strat->T[j].ecart;
188  ii = j;
189 
190  if (ei > h->ecart && ii < strat->tl)
191  {
192  li = strat->T[j].length;
193  // the polynomial to reduce with (up to the moment) is;
194  // pi with ecart ei and length li
195  // look for one with smaller ecart
196  i = j;
197  loop
198  {
199  /*- takes the first possible with respect to ecart -*/
200  i++;
201 #if 1
202  if (i > strat->tl) break;
203  if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
204  strat->T[i].length < li))
205  &&
206  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing))
207 #else
208  j = kFindDivisibleByInT(strat, h, i);
209  if (j < 0) break;
210  i = j;
211  if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
212  strat->T[i].length < li))
213 #endif
214  {
215  // the polynomial to reduce with is now
216  ii = i;
217  ei = strat->T[i].ecart;
218  if (ei <= h->ecart) break;
219  li = strat->T[i].length;
220  }
221  }
222  }
223 
224  // end of search: have to reduce with pi
225  if (ei > h->ecart)
226  {
227  // It is not possible to reduce h with smaller ecart;
228  // if possible h goes to the lazy-set L,i.e
229  // if its position in L would be not the last one
230  strat->fromT = TRUE;
231  if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
232  {
233  h->SetLmCurrRing();
234  if (strat->honey && strat->posInLDependsOnLength)
235  h->SetLength(strat->length_pLength);
236  assume(h->FDeg == h->pFDeg());
237  at = strat->posInL(strat->L,strat->Ll,h,strat);
238  if (at <= strat->Ll)
239  {
240  /*- h will not become the next element to reduce -*/
241  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
242 #ifdef KDEBUG
243  if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
244 #endif
245  h->Clear();
246  strat->fromT = FALSE;
247  return -1;
248  }
249  }
250  }
251 
252  // now we finally can reduce
253  doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
254  strat->fromT=FALSE;
255 
256  // are we done ???
257  if (h->IsNull())
258  {
260  if (h->lcm!=NULL) pLmFree(h->lcm);
261  h->Clear();
262  return 0;
263  }
264 
265  // NO!
266  h->SetShortExpVector();
267  h->SetpFDeg();
268  if (strat->honey)
269  {
270  if (ei <= h->ecart)
271  h->ecart = d-h->GetpFDeg();
272  else
273  h->ecart = d-h->GetpFDeg()+ei-h->ecart;
274  }
275  else
276  // this has the side effect of setting h->length
277  h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
278 #if 0
279  if (strat->syzComp!=0)
280  {
281  if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
282  {
283  assume(h->MinComp() > strat->syzComp);
284  if (strat->honey) h->SetLength();
285 #ifdef KDEBUG
286  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
287 #endif
288  return -2;
289  }
290  }
291 #endif
292  /*- try to reduce the s-polynomial -*/
293  pass++;
294  d = h->GetpFDeg()+h->ecart;
295  /*
296  *test whether the polynomial should go to the lazyset L
297  *-if the degree jumps
298  *-if the number of pre-defined reductions jumps
299  */
300  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
301  && ((d >= reddeg) || (pass > strat->LazyPass)))
302  {
303  h->SetLmCurrRing();
304  if (strat->honey && strat->posInLDependsOnLength)
305  h->SetLength(strat->length_pLength);
306  assume(h->FDeg == h->pFDeg());
307  at = strat->posInL(strat->L,strat->Ll,h,strat);
308  if (at <= strat->Ll)
309  {
310  int dummy=strat->sl;
311  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
312  {
313  if (strat->honey && !strat->posInLDependsOnLength)
314  h->SetLength(strat->length_pLength);
315  return 1;
316  }
317  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
318 #ifdef KDEBUG
319  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
320 #endif
321  h->Clear();
322  return -1;
323  }
324  }
325  else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
326  {
327  Print(".%ld",d);mflush();
328  reddeg = d+1;
329  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
330  {
331  strat->overflow=TRUE;
332  //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
333  h->GetP();
334  at = strat->posInL(strat->L,strat->Ll,h,strat);
335  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
336  h->Clear();
337  return -1;
338  }
339  }
340  }
341 }
char fromT
Definition: kutil.h:373
char overflow
Definition: kutil.h:398
static int doRed(LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
Definition: kstd1.cc:118
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition: kstd2.cc:196
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:86
#define TEST_OPT_REDTHROUGH
Definition: options.h:120
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1849

◆ redFirst()

int redFirst ( LObject h,
kStrategy  strat 
)

Definition at line 530 of file kstd1.cc.

531 {
532  if (h->IsNull()) return 0;
533 
534  int at;
535  long reddeg,d;
536  int pass = 0;
537  int j = 0;
538 
539  if (! strat->homog)
540  {
541  d = h->GetpFDeg() + h->ecart;
542  reddeg = strat->LazyDegree+d;
543  }
544  h->SetShortExpVector();
545  loop
546  {
547  j = kFindDivisibleByInT(strat, h);
548  if (j < 0)
549  {
550  h->SetDegStuffReturnLDeg(strat->LDegLast);
551  return 1;
552  }
553 
555  strat->T[j].pNorm();
556 #ifdef KDEBUG
557  if (TEST_OPT_DEBUG)
558  {
559  PrintS("reduce ");
560  h->wrp();
561  PrintS(" with ");
562  strat->T[j].wrp();
563  }
564 #endif
565  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
566 #ifdef KDEBUG
567  if (TEST_OPT_DEBUG)
568  {
569  PrintS(" to ");
570  wrp(h->p);
571  PrintLn();
572  }
573 #endif
574  if (h->IsNull())
575  {
577  if (h->lcm!=NULL) pLmFree(h->lcm);
578  h->Clear();
579  return 0;
580  }
581  h->SetShortExpVector();
582 
583 #if 0
584  if ((strat->syzComp!=0) && !strat->honey)
585  {
586  if ((strat->syzComp>0) &&
587  (h->Comp() > strat->syzComp))
588  {
589  assume(h->MinComp() > strat->syzComp);
590 #ifdef KDEBUG
591  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
592 #endif
593  if (strat->homog)
594  h->SetDegStuffReturnLDeg(strat->LDegLast);
595  return -2;
596  }
597  }
598 #endif
599  if (!strat->homog)
600  {
601  if (!TEST_OPT_OLDSTD && strat->honey)
602  {
603  h->SetpFDeg();
604  if (strat->T[j].ecart <= h->ecart)
605  h->ecart = d - h->GetpFDeg();
606  else
607  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
608 
609  d = h->GetpFDeg() + h->ecart;
610  }
611  else
612  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
613  /*- try to reduce the s-polynomial -*/
614  pass++;
615  /*
616  *test whether the polynomial should go to the lazyset L
617  *-if the degree jumps
618  *-if the number of pre-defined reductions jumps
619  */
620  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
621  && ((d >= reddeg) || (pass > strat->LazyPass)))
622  {
623  h->SetLmCurrRing();
624  if (strat->posInLDependsOnLength)
625  h->SetLength(strat->length_pLength);
626  at = strat->posInL(strat->L,strat->Ll,h,strat);
627  if (at <= strat->Ll)
628  {
629  int dummy=strat->sl;
630  if (kFindDivisibleByInS(strat,&dummy, h) < 0)
631  return 1;
632  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
633 #ifdef KDEBUG
634  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
635 #endif
636  h->Clear();
637  return -1;
638  }
639  }
640  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
641  {
642  reddeg = d+1;
643  Print(".%ld",d);mflush();
644  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
645  {
646  strat->overflow=TRUE;
647  //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
648  h->GetP();
649  at = strat->posInL(strat->L,strat->Ll,h,strat);
650  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
651  h->Clear();
652  return -1;
653  }
654  }
655  }
656  }
657 }
void wrp(poly p)
Definition: polys.h:296

◆ redMoraNF()

static poly redMoraNF ( poly  h,
kStrategy  strat,
int  flag 
)
static

Definition at line 664 of file kstd1.cc.

665 {
666  LObject H;
667  H.p = h;
668  int j = 0;
669  int z = 10;
670  int o = H.SetpFDeg();
671  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
672  if ((flag & 2) == 0) cancelunit(&H,TRUE);
673  H.sev = pGetShortExpVector(H.p);
674  unsigned long not_sev = ~ H.sev;
675  loop
676  {
677  if (j > strat->tl)
678  {
679  return H.p;
680  }
681  if (TEST_V_DEG_STOP)
682  {
683  if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
684  if (H.p==NULL) return NULL;
685  }
686  if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
687  )
688  {
689  /*- remember the found T-poly -*/
690  // poly pi = strat->T[j].p;
691  int ei = strat->T[j].ecart;
692  int li = strat->T[j].length;
693  int ii = j;
694  /*
695  * the polynomial to reduce with (up to the moment) is;
696  * pi with ecart ei and length li
697  */
698  loop
699  {
700  /*- look for a better one with respect to ecart -*/
701  /*- stop, if the ecart is small enough (<=ecart(H)) -*/
702  j++;
703  if (j > strat->tl) break;
704  if (ei <= H.ecart) break;
705  if (((strat->T[j].ecart < ei)
706  || ((strat->T[j].ecart == ei)
707  && (strat->T[j].length < li)))
708  && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
709  )
710  {
711  /*
712  * the polynomial to reduce with is now;
713  */
714  // pi = strat->T[j].p;
715  ei = strat->T[j].ecart;
716  li = strat->T[j].length;
717  ii = j;
718  }
719  }
720  /*
721  * end of search: have to reduce with pi
722  */
723  z++;
724  if (z>10)
725  {
726  pNormalize(H.p);
727  z=0;
728  }
729  if ((ei > H.ecart) && (!strat->kHEdgeFound))
730  {
731  /*
732  * It is not possible to reduce h with smaller ecart;
733  * we have to reduce with bad ecart: H has to enter in T
734  */
735  doRed(&H,&(strat->T[ii]),TRUE,strat,TRUE);
736  if (H.p == NULL)
737  return NULL;
738  }
739  else
740  {
741  /*
742  * we reduce with good ecart, h need not to be put to T
743  */
744  doRed(&H,&(strat->T[ii]),FALSE,strat,TRUE);
745  if (H.p == NULL)
746  return NULL;
747  }
748  /*- try to reduce the s-polynomial -*/
749  o = H.SetpFDeg();
750  if ((flag &2 ) == 0) cancelunit(&H,TRUE);
751  H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
752  j = 0;
753  H.sev = pGetShortExpVector(H.p);
754  not_sev = ~ H.sev;
755  }
756  else
757  {
758  j++;
759  }
760  }
761 }
CanonicalForm H
Definition: facAbsFact.cc:64
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition: polys.h:146
#define pNormalize(p)
Definition: polys.h:303

◆ redMoraNFRing()

static poly redMoraNFRing ( poly  h,
kStrategy  strat,
int  flag 
)
static

Definition at line 764 of file kstd1.cc.

765 {
766  LObject H;
767  H.p = h;
768  int j = 0;
769  int z = 10;
770  int o = H.SetpFDeg();
771  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
772  if ((flag & 2) == 0) cancelunit(&H,TRUE);
773  H.sev = pGetShortExpVector(H.p);
774  unsigned long not_sev = ~ H.sev;
775  loop
776  {
777  if (j > strat->tl)
778  {
779  return H.p;
780  }
781  if (TEST_V_DEG_STOP)
782  {
783  if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
784  if (H.p==NULL) return NULL;
785  }
786  if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
787  && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
788  )
789  {
790  /*- remember the found T-poly -*/
791  // poly pi = strat->T[j].p;
792  int ei = strat->T[j].ecart;
793  int li = strat->T[j].length;
794  int ii = j;
795  /*
796  * the polynomial to reduce with (up to the moment) is;
797  * pi with ecart ei and length li
798  */
799  loop
800  {
801  /*- look for a better one with respect to ecart -*/
802  /*- stop, if the ecart is small enough (<=ecart(H)) -*/
803  j++;
804  if (j > strat->tl) break;
805  if (ei <= H.ecart) break;
806  if (((strat->T[j].ecart < ei)
807  || ((strat->T[j].ecart == ei)
808  && (strat->T[j].length < li)))
809  && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
810  && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
811  )
812  {
813  /*
814  * the polynomial to reduce with is now;
815  */
816  // pi = strat->T[j].p;
817  ei = strat->T[j].ecart;
818  li = strat->T[j].length;
819  ii = j;
820  }
821  }
822  /*
823  * end of search: have to reduce with pi
824  */
825  z++;
826  if (z>10)
827  {
828  pNormalize(H.p);
829  z=0;
830  }
831  if ((ei > H.ecart) && (!strat->kHEdgeFound))
832  {
833  /*
834  * It is not possible to reduce h with smaller ecart;
835  * we have to reduce with bad ecart: H has to enter in T
836  */
837  doRed(&H,&(strat->T[ii]),TRUE,strat,TRUE);
838  if (H.p == NULL)
839  return NULL;
840  }
841  else
842  {
843  /*
844  * we reduce with good ecart, h need not to be put to T
845  */
846  doRed(&H,&(strat->T[ii]),FALSE,strat,TRUE);
847  if (H.p == NULL)
848  return NULL;
849  }
850  /*- try to reduce the s-polynomial -*/
851  o = H.SetpFDeg();
852  if ((flag &2 ) == 0) cancelunit(&H,TRUE);
853  H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
854  j = 0;
855  H.sev = pGetShortExpVector(H.p);
856  not_sev = ~ H.sev;
857  }
858  else
859  {
860  j++;
861  }
862  }
863 }
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition: coeffs.h:784

◆ redRiloc()

int redRiloc ( LObject h,
kStrategy  strat 
)

Definition at line 344 of file kstd1.cc.

345 {
346  int i,at,ei,li,ii;
347  int j = 0;
348  int pass = 0;
349  long d,reddeg;
350 
351  d = h->GetpFDeg()+ h->ecart;
352  reddeg = strat->LazyDegree+d;
353  h->SetShortExpVector();
354  loop
355  {
356  j = kFindDivisibleByInT(strat, h);
357  if (j < 0)
358  {
359  // over ZZ: cleanup coefficients by complete reduction with monomials
360  postReduceByMon(h, strat);
361  if(h->p == NULL)
362  {
363  if (h->lcm!=NULL) pLmDelete(h->lcm);
364  h->Clear();
365  return 0;
366  }
367  if (strat->honey) h->SetLength(strat->length_pLength);
368  if(strat->tl >= 0)
369  h->i_r1 = strat->tl;
370  else
371  h->i_r1 = -1;
372  if (h->GetLmTailRing() == NULL)
373  {
374  if (h->lcm!=NULL) pLmDelete(h->lcm);
375  h->Clear();
376  return 0;
377  }
378  return 1;
379  }
380 
381  ei = strat->T[j].ecart;
382  ii = j;
383  if (ei > h->ecart && ii < strat->tl)
384  {
385  li = strat->T[j].length;
386  // the polynomial to reduce with (up to the moment) is;
387  // pi with ecart ei and length li
388  // look for one with smaller ecart
389  i = j;
390  loop
391  {
392  /*- takes the first possible with respect to ecart -*/
393  i++;
394 #if 1
395  if (i > strat->tl) break;
396  if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
397  strat->T[i].length < li))
398  &&
399  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
400  &&
401  n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
402 #else
403  j = kFindDivisibleByInT(strat, h, i);
404  if (j < 0) break;
405  i = j;
406  if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
407  strat->T[i].length < li))
408 #endif
409  {
410  // the polynomial to reduce with is now
411  ii = i;
412  ei = strat->T[i].ecart;
413  if (ei <= h->ecart) break;
414  li = strat->T[i].length;
415  }
416  }
417  }
418 
419  // end of search: have to reduce with pi
420  if (ei > h->ecart)
421  {
422  // It is not possible to reduce h with smaller ecart;
423  // if possible h goes to the lazy-set L,i.e
424  // if its position in L would be not the last one
425  strat->fromT = TRUE;
426  if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
427  {
428  h->SetLmCurrRing();
429  if (strat->honey && strat->posInLDependsOnLength)
430  h->SetLength(strat->length_pLength);
431  assume(h->FDeg == h->pFDeg());
432  at = strat->posInL(strat->L,strat->Ll,h,strat);
433  if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
434  {
435  /*- h will not become the next element to reduce -*/
436  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
437  #ifdef KDEBUG
438  if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
439  #endif
440  h->Clear();
441  strat->fromT = FALSE;
442  return -1;
443  }
444  }
445  doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
446  }
447  else
448  {
449  // now we finally can reduce
450  doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
451  }
452  strat->fromT=FALSE;
453  // are we done ???
454  if (h->IsNull())
455  {
456  if (h->lcm!=NULL) pLmDelete(h->lcm);
457  h->Clear();
458  return 0;
459  }
460 
461  // NO!
462  h->SetShortExpVector();
463  h->SetpFDeg();
464  if (strat->honey)
465  {
466  if (ei <= h->ecart)
467  h->ecart = d-h->GetpFDeg();
468  else
469  h->ecart = d-h->GetpFDeg()+ei-h->ecart;
470  }
471  else
472  // this has the side effect of setting h->length
473  h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
474  /*- try to reduce the s-polynomial -*/
475  pass++;
476  d = h->GetpFDeg()+h->ecart;
477  /*
478  *test whether the polynomial should go to the lazyset L
479  *-if the degree jumps
480  *-if the number of pre-defined reductions jumps
481  */
482  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
483  && ((d >= reddeg) || (pass > strat->LazyPass)))
484  {
485  h->SetLmCurrRing();
486  if (strat->honey && strat->posInLDependsOnLength)
487  h->SetLength(strat->length_pLength);
488  assume(h->FDeg == h->pFDeg());
489  at = strat->posInL(strat->L,strat->Ll,h,strat);
490  if (at <= strat->Ll)
491  {
492  int dummy=strat->sl;
493  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
494  {
495  if (strat->honey && !strat->posInLDependsOnLength)
496  h->SetLength(strat->length_pLength);
497  return 1;
498  }
499  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
500 #ifdef KDEBUG
501  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
502 #endif
503  h->Clear();
504  return -1;
505  }
506  }
507  else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
508  {
509  Print(".%ld",d);mflush();
510  reddeg = d+1;
511  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
512  {
513  strat->overflow=TRUE;
514  //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
515  h->GetP();
516  at = strat->posInL(strat->L,strat->Ll,h,strat);
517  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
518  h->Clear();
519  return -1;
520  }
521  }
522  }
523 }
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:10814
#define nEqual(n1, n2)
Definition: numbers.h:21
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105

◆ reorderL()

void reorderL ( kStrategy  strat)

Definition at line 869 of file kstd1.cc.

870 {
871  int i,j,at;
872  LObject p;
873 
874  for (i=1; i<=strat->Ll; i++)
875  {
876  at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
877  if (at != i)
878  {
879  p = strat->L[i];
880  for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
881  strat->L[at] = p;
882  }
883  }
884 }

◆ reorderT()

void reorderT ( kStrategy  strat)

Definition at line 889 of file kstd1.cc.

890 {
891  int i,j,at;
892  TObject p;
893  unsigned long sev;
894 
895 
896  for (i=1; i<=strat->tl; i++)
897  {
898  if (strat->T[i-1].length > strat->T[i].length)
899  {
900  p = strat->T[i];
901  sev = strat->sevT[i];
902  at = i-1;
903  loop
904  {
905  at--;
906  if (at < 0) break;
907  if (strat->T[i].length > strat->T[at].length) break;
908  }
909  for (j = i-1; j>at; j--)
910  {
911  strat->T[j+1]=strat->T[j];
912  strat->sevT[j+1]=strat->sevT[j];
913  strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
914  }
915  strat->T[at+1]=p;
916  strat->sevT[at+1] = sev;
917  strat->R[p.i_r] = &(strat->T[at+1]);
918  }
919  }
920 }

◆ updateL()

void updateL ( kStrategy  strat)

Definition at line 1043 of file kstd1.cc.

1044 {
1045  LObject p;
1046  int dL;
1047  int j=strat->Ll;
1048  loop
1049  {
1050  if (j<0) break;
1051  if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1052  {
1053  p=strat->L[strat->Ll];
1054  strat->L[strat->Ll]=strat->L[j];
1055  strat->L[j]=p;
1056  break;
1057  }
1058  j--;
1059  }
1060  if (j<0)
1061  {
1062  j=strat->Ll;
1063  loop
1064  {
1065  if (j<0) break;
1066  if (pNext(strat->L[j].p) == strat->tail)
1067  {
1068  if (rField_is_Ring(currRing))
1069  pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1070  else
1071  pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1072  strat->L[j].p = NULL;
1073  poly m1 = NULL, m2 = NULL;
1074  // check that spoly creation is ok
1075  while (strat->tailRing != currRing &&
1076  !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1077  {
1078  assume(m1 == NULL && m2 == NULL);
1079  // if not, change to a ring where exponents are at least
1080  // large enough
1081  kStratChangeTailRing(strat);
1082  }
1083  /* create the real one */
1084  ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1085  strat->tailRing, m1, m2, strat->R);
1086 
1087  strat->L[j].SetLmCurrRing();
1088  if (!strat->honey)
1089  strat->initEcart(&strat->L[j]);
1090  else
1091  strat->L[j].SetLength(strat->length_pLength);
1092 
1093  BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1094 
1095  if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
1096 
1097  if (pp)
1098  {
1099  p=strat->L[strat->Ll];
1100  strat->L[strat->Ll]=strat->L[j];
1101  strat->L[j]=p;
1102  break;
1103  }
1104  }
1105  j--;
1106  }
1107  }
1108 }

◆ updateLHC()

void updateLHC ( kStrategy  strat)

Definition at line 1114 of file kstd1.cc.

1115 {
1116 
1117  int i = 0;
1118  kTest_TS(strat);
1119  while (i <= strat->Ll)
1120  {
1121  if (pNext(strat->L[i].p) == strat->tail)
1122  {
1123  /*- deletes the int spoly and computes -*/
1124  if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
1125  {
1126  if (rField_is_Ring(currRing))
1127  pLmDelete(strat->L[i].p);
1128  else
1129  pLmFree(strat->L[i].p);
1130  strat->L[i].p = NULL;
1131  }
1132  else
1133  {
1134  if (rField_is_Ring(currRing))
1135  pLmDelete(strat->L[i].p);
1136  else
1137  pLmFree(strat->L[i].p);
1138  strat->L[i].p = NULL;
1139  poly m1 = NULL, m2 = NULL;
1140  // check that spoly creation is ok
1141  while (strat->tailRing != currRing &&
1142  !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
1143  {
1144  assume(m1 == NULL && m2 == NULL);
1145  // if not, change to a ring where exponents are at least
1146  // large enough
1147  kStratChangeTailRing(strat);
1148  }
1149  /* create the real one */
1150  ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
1151  strat->tailRing, m1, m2, strat->R);
1152  if (! strat->L[i].IsNull())
1153  {
1154  strat->L[i].SetLmCurrRing();
1155  strat->L[i].SetpFDeg();
1156  strat->L[i].ecart
1157  = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
1158  if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
1159  }
1160  }
1161  }
1162  else
1163  deleteHC(&(strat->L[i]), strat);
1164  if (strat->L[i].IsNull())
1165  deleteInL(strat->L,&strat->Ll,i,strat);
1166  else
1167  {
1168 #ifdef KDEBUG
1169  kTest_L(&(strat->L[i]), strat->tailRing, TRUE, i, strat->T, strat->tl);
1170 #endif
1171  i++;
1172  }
1173  }
1174  kTest_TS(strat);
1175 }

◆ updateT()

void updateT ( kStrategy  strat)

Definition at line 1181 of file kstd1.cc.

1182 {
1183  int i = 0;
1184  LObject p;
1185 
1186  while (i <= strat->tl)
1187  {
1188  p = strat->T[i];
1189  deleteHC(&p,strat, TRUE);
1190  /*- tries to cancel a unit: -*/
1191  cancelunit(&p);
1192  if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
1193  p.pCleardenom();
1194  if (p.p != strat->T[i].p)
1195  {
1196  strat->sevT[i] = pGetShortExpVector(p.p);
1197  p.SetpFDeg();
1198  }
1199  strat->T[i] = p;
1200  i++;
1201  }
1202 }

Variable Documentation

◆ kHomW

intvec * kHomW

Definition at line 2071 of file kstd1.cc.

◆ kModW

intvec* kModW

Definition at line 2071 of file kstd1.cc.

◆ kOptions

BITSET kOptions
Initial value:
#define OPT_SUGARCRIT
Definition: options.h:79
#define OPT_PROT
Definition: options.h:74
#define OPT_INFREDTAIL
Definition: options.h:93
#define OPT_WEIGHTM
Definition: options.h:96
#define OPT_NOT_SUGAR
Definition: options.h:77
#define OPT_NOTREGULARITY
Definition: options.h:95
#define OPT_INTERRUPT
Definition: options.h:78
#define OPT_FASTHC
Definition: options.h:84
#define OPT_OLDSTD
Definition: options.h:85

Definition at line 44 of file kstd1.cc.

◆ validOpts

BITSET validOpts

Definition at line 59 of file kstd1.cc.