My Project
Macros | Functions | Variables
kstd1.cc File Reference
#include "kernel/mod2.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"
#include "polys/shiftop.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 redRiloc_Z (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, BOOLEAN rightGB)
 
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

VAR BITSET kOptions
 
VAR BITSET validOpts
 
VAR intveckModW
 
VAR 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 119 of file kstd1.cc.

120 {
121  int ret;
122 #if KDEBUG > 0
123  kTest_L(h);
124  kTest_T(with);
125 #endif
126  // Hmmm ... why do we do this -- polys from T should already be normalized
128  with->pNorm();
129 #ifdef KDEBUG
130  if (TEST_OPT_DEBUG)
131  {
132  PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
133  }
134 #endif
135  if (intoT)
136  {
137  // need to do it exacly like this: otherwise
138  // we might get errors
139  LObject L= *h;
140  L.Copy();
141  h->GetP();
142  h->length=h->pLength=pLength(h->p);
143  ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, NULL, strat);
144  if (ret)
145  {
146  if (ret < 0) return ret;
147  if (h->tailRing != strat->tailRing)
148  h->ShallowCopyDelete(strat->tailRing,
149  pGetShallowCopyDeleteProc(h->tailRing,
150  strat->tailRing));
151  }
153  enterT_strong(*h,strat);
154  else
155  enterT(*h,strat);
156  *h = L;
157  }
158  else
159  ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, NULL, strat);
160 #ifdef KDEBUG
161  if (TEST_OPT_DEBUG)
162  {
163  PrintS("to ");h->wrp();PrintLn();
164  }
165 #endif
166  return ret;
167 }
KINLINE poly kNoetherTail()
Definition: kInline.h:66
ring tailRing
Definition: kutil.h:342
STATIC_VAR Poly * h
Definition: janet.cc:971
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat)
Definition: kspoly.cc:185
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:956
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9699
BOOLEAN kTest_L(LObject *L, ring strat_tailRing, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition: kutil.cc:925
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9799
BOOLEAN kTest_T(TObject *T, ring strat_tailRing, int i, char TN)
Definition: kutil.cc:801
class sLObject LObject
Definition: kutil.h:54
#define NULL
Definition: omList.c:12
#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:191
VAR 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:489

◆ enterSMora()

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

Definition at line 1595 of file kstd1.cc.

1596 {
1597  enterSBba(p, atS, strat, atR);
1598  #ifdef KDEBUG
1599  if (TEST_OPT_DEBUG)
1600  {
1601  Print("new s%d:",atS);
1602  p_wrp(p.p,currRing,strat->tailRing);
1603  PrintLn();
1604  }
1605  #endif
1606  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1607  if (strat->kHEdgeFound)
1608  {
1609  if (newHEdge(strat))
1610  {
1611  firstUpdate(strat);
1612  if (TEST_OPT_FINDET)
1613  return;
1614 
1615  /*- cuts elements in L above noether and reorders L -*/
1616  updateLHC(strat);
1617  /*- reorders L with respect to posInL -*/
1618  reorderL(strat);
1619  }
1620  }
1621  else if (strat->kNoether!=NULL)
1622  strat->kHEdgeFound = TRUE;
1623  else if (TEST_OPT_FASTHC)
1624  {
1625  if (strat->posInLOldFlag)
1626  {
1627  missingAxis(&strat->lastAxis,strat);
1628  if (strat->lastAxis)
1629  {
1630  strat->posInLOld = strat->posInL;
1631  strat->posInLOldFlag = FALSE;
1632  strat->posInL = posInL10;
1633  strat->posInLDependsOnLength = TRUE;
1634  updateL(strat);
1635  reorderL(strat);
1636  }
1637  }
1638  else if (strat->lastAxis)
1639  updateL(strat);
1640  }
1641 }
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int p
Definition: cfModGcd.cc:4080
char posInLOldFlag
Definition: kutil.h:382
poly kNoether
Definition: kutil.h:327
int lastAxis
Definition: kutil.h:355
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:281
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:285
char kHEdgeFound
Definition: kutil.h:376
char posInLDependsOnLength
Definition: kutil.h:389
#define Print
Definition: emacs.cc:80
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1528
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1435
void missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:1250
void reorderL(kStrategy strat)
Definition: kstd1.cc:1192
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1331
void updateL(kStrategy strat)
Definition: kstd1.cc:1364
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:475
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9350
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10981
#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:373

◆ enterSMoraNF()

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

Definition at line 1649 of file kstd1.cc.

1650 {
1651  enterSBba(p, atS, strat, atR);
1652  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1653  if (strat->kHEdgeFound)
1654  newHEdge(strat);
1655  else if (strat->kNoether!=NULL)
1656  strat->kHEdgeFound = TRUE;
1657 }

◆ firstUpdate()

void firstUpdate ( kStrategy  strat)

Definition at line 1528 of file kstd1.cc.

1529 {
1530  if (strat->update)
1531  {
1532  kTest_TS(strat);
1533  strat->update = (strat->tl == -1);
1534  if (TEST_OPT_WEIGHTM)
1535  {
1536  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1537  if (strat->tailRing != currRing)
1538  {
1539  strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1540  strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1541  }
1542  int i;
1543  for (i=strat->Ll; i>=0; i--)
1544  {
1545  strat->L[i].SetpFDeg();
1546  }
1547  for (i=strat->tl; i>=0; i--)
1548  {
1549  strat->T[i].SetpFDeg();
1550  }
1551  if (ecartWeights)
1552  {
1553  omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1555  }
1556  }
1557  if (TEST_OPT_FASTHC)
1558  {
1559  strat->posInL = strat->posInLOld;
1560  strat->lastAxis = 0;
1561  }
1562  if (TEST_OPT_FINDET)
1563  return;
1564 
1566  {
1567  strat->red = redFirst;
1568  strat->use_buckets = kMoraUseBucket(strat);
1569  }
1570  updateT(strat);
1571 
1573  {
1574  strat->posInT = posInT2;
1575  reorderT(strat);
1576  }
1577  }
1578  kTest_TS(strat);
1579 }
void * ADDRESS
Definition: auxiliary.h:119
int i
Definition: cfEzgcd.cc:132
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:295
int Ll
Definition: kutil.h:350
TSet T
Definition: kutil.h:323
int tl
Definition: kutil.h:349
pFDegProc pOrigFDeg
Definition: kutil.h:293
char use_buckets
Definition: kutil.h:383
LSet L
Definition: kutil.h:324
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:278
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:275
pLDegProc pOrigLDeg
Definition: kutil.h:294
char update
Definition: kutil.h:381
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:296
void reorderT(kStrategy strat)
Definition: kstd1.cc:1212
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:784
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3810
void updateT(kStrategy strat)
Definition: kstd1.cc:1502
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1071
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5370
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define TEST_OPT_WEIGHTM
Definition: options.h:120
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3719
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:597
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:764
EXTERN_VAR short * ecartWeights
Definition: weight.h:12

◆ hasPurePower() [1/2]

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

Definition at line 1283 of file kstd1.cc.

1284 {
1285  poly h;
1286  int i;
1287 
1288  if (pNext(p) == strat->tail)
1289  return FALSE;
1290  pp_Test(p, currRing, strat->tailRing);
1291  if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
1292  {
1293  i = p_IsPurePower(p, currRing);
1294  if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
1295  if (i == last)
1296  {
1297  *length = 0;
1298  return TRUE;
1299  }
1300  *length = 1;
1301  h = pNext(p);
1302  while (h != NULL)
1303  {
1304  i = p_IsPurePower(h, strat->tailRing);
1305  if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
1306  if (i==last) return TRUE;
1307  (*length)++;
1308  pIter(h);
1309  }
1310  }
1311  return FALSE;
1312 }
int ak
Definition: kutil.h:352
poly tail
Definition: kutil.h:333
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_VAR poly last
Definition: hdegree.cc:1150
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1221
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:164

◆ hasPurePower() [2/2]

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

Definition at line 1314 of file kstd1.cc.

1315 {
1316  if (L->bucket != NULL)
1317  {
1318  poly p = L->GetP();
1319  return hasPurePower(p, last, length, strat);
1320  }
1321  else
1322  {
1323  return hasPurePower(L->p, last, length, strat);
1324  }
1325 }
BOOLEAN hasPurePower(const poly p, int last, int *length, kStrategy strat)
Definition: kstd1.cc:1283

◆ initBba()

void initBba ( kStrategy  strat)

Definition at line 1659 of file kstd1.cc.

1660 {
1661  /* setting global variables ------------------- */
1662  strat->enterS = enterSBba;
1663  strat->red = redHoney;
1664  if (strat->honey)
1665  strat->red = redHoney;
1666  else if (currRing->pLexOrder && !strat->homog)
1667  strat->red = redLazy;
1668  else
1669  {
1670  strat->LazyPass *=4;
1671  strat->red = redHomog;
1672  }
1673  if (rField_is_Ring(currRing))
1674  {
1675  if (rField_is_Z(currRing))
1676  strat->red = redRing_Z;
1677  else
1678  strat->red = redRing;
1679  }
1680  if (TEST_OPT_IDLIFT)
1681  strat->red=redLiftstd;
1682  if (currRing->pLexOrder && strat->honey)
1683  strat->initEcart = initEcartNormal;
1684  else
1685  strat->initEcart = initEcartBBA;
1686  if (strat->honey)
1688  else
1690 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1691 // {
1692 // //interred machen Aenderung
1693 // strat->pOrigFDeg=pFDeg;
1694 // strat->pOrigLDeg=pLDeg;
1695 // //h=ggetid("ecart");
1696 // //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1697 // //{
1698 // // ecartWeights=iv2array(IDINTVEC(h));
1699 // //}
1700 // //else
1701 // {
1702 // ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1703 // /*uses automatic computation of the ecartWeights to set them*/
1704 // kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1705 // }
1706 // pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1707 // if (TEST_OPT_PROT)
1708 // {
1709 // for(i=1; i<=(currRing->N); i++)
1710 // Print(" %d",ecartWeights[i]);
1711 // PrintLn();
1712 // mflush();
1713 // }
1714 // }
1715 }
char honey
Definition: kutil.h:377
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:284
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:283
void(* initEcart)(TObject *L)
Definition: kutil.h:277
int LazyPass
Definition: kutil.h:352
char homog
Definition: kutil.h:372
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:161
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:640
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1842
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:902
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1648
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:795
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1347
void initEcartNormal(TObject *h)
Definition: kutil.cc:1325
void initEcartBBA(TObject *h)
Definition: kutil.cc:1333
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1340
#define TEST_OPT_IDLIFT
Definition: options.h:128
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:514

◆ initMora()

void initMora ( ideal  F,
kStrategy  strat 
)

Definition at line 1787 of file kstd1.cc.

1788 {
1789  int i,j;
1790 
1791  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1792  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1793  strat->enterS = enterSMora;
1794  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1795  strat->posInLOld = strat->posInL;
1796  strat->posInLOldFlag = TRUE;
1797  strat->initEcart = initEcartNormal;
1798  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1799  if ( strat->kHEdgeFound )
1800  strat->kNoether = pCopy((currRing->ppNoether));
1801  else if (strat->kHEdgeFound || strat->homog)
1802  strat->red = redFirst; /*take the first possible in T*/
1803  else
1804  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1805  if (strat->kHEdgeFound)
1806  {
1807  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1808  strat->posInT = posInT2;
1809  }
1810  else
1811  {
1812  strat->HCord = 32000;/*- very large -*/
1813  }
1814 
1815  if (rField_is_Ring(currRing)) {
1816  if (rField_is_Z(currRing))
1817  strat->red = redRiloc_Z;
1818  else
1819  strat->red = redRiloc;
1820  }
1821 
1822  /*reads the ecartWeights used for Graebes method from the
1823  *intvec ecart and set ecartWeights
1824  */
1825  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1826  {
1827  //interred machen Aenderung
1828  strat->pOrigFDeg=currRing->pFDeg;
1829  strat->pOrigLDeg=currRing->pLDeg;
1830  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1831  /*uses automatic computation of the ecartWeights to set them*/
1833 
1835  if (TEST_OPT_PROT)
1836  {
1837  for(i=1; i<=(currRing->N); i++)
1838  Print(" %d",ecartWeights[i]);
1839  PrintLn();
1840  mflush();
1841  }
1842  }
1843  kOptimizeLDeg(currRing->pLDeg, strat);
1844 }
int BOOLEAN
Definition: auxiliary.h:87
BOOLEAN * NotUsedAxis
Definition: kutil.h:331
int HCord
Definition: kutil.h:354
int j
Definition: facHensel.cc:110
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:100
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:383
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1595
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:564
#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:3707
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define mflush()
Definition: reporter.h:58
#define IDELEMS(i)
Definition: simpleideals.h:23
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition: weight.cc:247
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition: weight.cc:182

◆ initSba()

void initSba ( ideal  F,
kStrategy  strat 
)

Definition at line 1717 of file kstd1.cc.

1718 {
1719  int i;
1720  //idhdl h;
1721  /* setting global variables ------------------- */
1722  strat->enterS = enterSSba;
1723  strat->red2 = redHoney;
1724  if (strat->honey)
1725  strat->red2 = redHoney;
1726  else if (currRing->pLexOrder && !strat->homog)
1727  strat->red2 = redLazy;
1728  else
1729  {
1730  strat->LazyPass *=4;
1731  strat->red2 = redHomog;
1732  }
1733  if (rField_is_Ring(currRing))
1734  {
1736  {strat->red2 = redRiloc;}
1737  else
1738  {strat->red2 = redRing;}
1739  }
1740  if (currRing->pLexOrder && strat->honey)
1741  strat->initEcart = initEcartNormal;
1742  else
1743  strat->initEcart = initEcartBBA;
1744  if (strat->honey)
1746  else
1748  //strat->kIdeal = NULL;
1749  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1750  //else strat->kIdeal->rtyp=MODUL_CMD;
1751  //strat->kIdeal->data=(void *)strat->Shdl;
1752  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1753  {
1754  //interred machen Aenderung
1755  strat->pOrigFDeg = currRing->pFDeg;
1756  strat->pOrigLDeg = currRing->pLDeg;
1757  //h=ggetid("ecart");
1758  //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1759  //{
1760  // ecartWeights=iv2array(IDINTVEC(h));
1761  //}
1762  //else
1763  {
1764  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1765  /*uses automatic computation of the ecartWeights to set them*/
1767  }
1769  if (TEST_OPT_PROT)
1770  {
1771  for(i=1; i<=(currRing->N); i++)
1772  Print(" %d",ecartWeights[i]);
1773  PrintLn();
1774  mflush();
1775  }
1776  }
1777  // for sig-safe reductions in signature-based
1778  // standard basis computations
1780  strat->red = redSigRing;
1781  else
1782  strat->red = redSig;
1783  //strat->sbaOrder = 1;
1784  strat->currIdx = 1;
1785 }
int currIdx
Definition: kutil.h:314
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:276
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1278
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1111
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9473
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:765

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

3370 {
3371  const ring save = currRing;
3372  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3373  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3374  if( currRing != save ) rChangeCurrRing(save);
3375  return ret;
3376 }
STATIC_VAR jList * Q
Definition: janet.cc:30
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3158
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kDebugPrint()

void kDebugPrint ( kStrategy  strat)

Definition at line 12080 of file kutil.cc.

12081 {
12082  PrintS("red: ");
12083  if (strat->red==redFirst) PrintS("redFirst\n");
12084  else if (strat->red==redHoney) PrintS("redHoney\n");
12085  else if (strat->red==redEcart) PrintS("redEcart\n");
12086  else if (strat->red==redHomog) PrintS("redHomog\n");
12087  else if (strat->red==redLazy) PrintS("redLazy\n");
12088  else if (strat->red==redLiftstd) PrintS("redLiftstd\n");
12089  else Print("%p\n",(void*)strat->red);
12090  PrintS("posInT: ");
12091  if (strat->posInT==posInT0) PrintS("posInT0\n");
12092  else if (strat->posInT==posInT1) PrintS("posInT1\n");
12093  else if (strat->posInT==posInT11) PrintS("posInT11\n");
12094  else if (strat->posInT==posInT110) PrintS("posInT110\n");
12095  else if (strat->posInT==posInT13) PrintS("posInT13\n");
12096  else if (strat->posInT==posInT15) PrintS("posInT15\n");
12097  else if (strat->posInT==posInT17) PrintS("posInT17\n");
12098  else if (strat->posInT==posInT17_c) PrintS("posInT17_c\n");
12099  else if (strat->posInT==posInT19) PrintS("posInT19\n");
12100  else if (strat->posInT==posInT2) PrintS("posInT2\n");
12101  #ifdef HAVE_RINGS
12102  else if (strat->posInT==posInT11Ring) PrintS("posInT11Ring\n");
12103  else if (strat->posInT==posInT110Ring) PrintS("posInT110Ring\n");
12104  else if (strat->posInT==posInT15Ring) PrintS("posInT15Ring\n");
12105  else if (strat->posInT==posInT17Ring) PrintS("posInT17Ring\n");
12106  else if (strat->posInT==posInT17_cRing) PrintS("posInT17_cRing\n");
12107  #endif
12108 #ifdef HAVE_MORE_POS_IN_T
12109  else if (strat->posInT==posInT_EcartFDegpLength) PrintS("posInT_EcartFDegpLength\n");
12110  else if (strat->posInT==posInT_FDegpLength) PrintS("posInT_FDegpLength\n");
12111  else if (strat->posInT==posInT_pLength) PrintS("posInT_pLength\n");
12112 #endif
12113  else if (strat->posInT==posInT_EcartpLength) PrintS("posInT_EcartpLength\n");
12114  else if (strat->posInT==posInTrg0) PrintS("posInTrg0\n");
12115  else Print("%p\n",(void*)strat->posInT);
12116  PrintS("posInL: ");
12117  if (strat->posInL==posInL0) PrintS("posInL0\n");
12118  else if (strat->posInL==posInL10) PrintS("posInL10\n");
12119  else if (strat->posInL==posInL11) PrintS("posInL11\n");
12120  else if (strat->posInL==posInL110) PrintS("posInL110\n");
12121  else if (strat->posInL==posInL13) PrintS("posInL13\n");
12122  else if (strat->posInL==posInL15) PrintS("posInL15\n");
12123  else if (strat->posInL==posInL17) PrintS("posInL17\n");
12124  else if (strat->posInL==posInL17_c) PrintS("posInL17_c\n");
12125  #ifdef HAVE_RINGS
12126  else if (strat->posInL==posInL0) PrintS("posInL0Ring\n");
12127  else if (strat->posInL==posInL11Ring) PrintS("posInL11Ring\n");
12128  else if (strat->posInL==posInL11Ringls) PrintS("posInL11Ringls\n");
12129  else if (strat->posInL==posInL110Ring) PrintS("posInL110Ring\n");
12130  else if (strat->posInL==posInL15Ring) PrintS("posInL15Ring\n");
12131  else if (strat->posInL==posInL17Ring) PrintS("posInL17Ring\n");
12132  else if (strat->posInL==posInL17_cRing) PrintS("posInL17_cRing\n");
12133  #endif
12134  else if (strat->posInL==posInLSpecial) PrintS("posInLSpecial\n");
12135  else if (strat->posInL==posInLrg0) PrintS("posInLrg0\n");
12136  else Print("%p\n",(void*)strat->posInL);
12137  PrintS("enterS: ");
12138  if (strat->enterS==enterSBba) PrintS("enterSBba\n");
12139  else if (strat->enterS==enterSMora) PrintS("enterSMora\n");
12140  else if (strat->enterS==enterSMoraNF) PrintS("enterSMoraNF\n");
12141  else Print("%p\n",(void*)strat->enterS);
12142  PrintS("initEcart: ");
12143  if (strat->initEcart==initEcartBBA) PrintS("initEcartBBA\n");
12144  else if (strat->initEcart==initEcartNormal) PrintS("initEcartNormal\n");
12145  else Print("%p\n",(void*)strat->initEcart);
12146  PrintS("initEcartPair: ");
12147  if (strat->initEcartPair==initEcartPairBba) PrintS("initEcartPairBba\n");
12148  else if (strat->initEcartPair==initEcartPairMora) PrintS("initEcartPairMora\n");
12149  else Print("%p\n",(void*)strat->initEcartPair);
12150  Print("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
12151  strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
12152  Print("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
12153  strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
12154  PrintS("chainCrit: ");
12155  if (strat->chainCrit==chainCritNormal) PrintS("chainCritNormal\n");
12156  else if (strat->chainCrit==chainCritOpt_1) PrintS("chainCritOpt_1\n");
12157  else Print("%p\n",(void*)strat->chainCrit);
12158  Print("posInLDependsOnLength=%d\n",
12159  strat->posInLDependsOnLength);
12160  PrintS(showOption());PrintLn();
12161  PrintS("LDeg: ");
12162  if (currRing->pLDeg==pLDeg0) PrintS("pLDeg0");
12163  else if (currRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
12164  else if (currRing->pLDeg==pLDegb) PrintS("pLDegb");
12165  else if (currRing->pLDeg==pLDeg1) PrintS("pLDeg1");
12166  else if (currRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
12167  else if (currRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
12168  else if (currRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
12169  else if (currRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
12170  else if (currRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
12171  else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
12172  else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
12173  else if (currRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
12174  else Print("? (%lx)", (long)currRing->pLDeg);
12175  PrintS(" / ");
12176  if (strat->tailRing->pLDeg==pLDeg0) PrintS("pLDeg0");
12177  else if (strat->tailRing->pLDeg==pLDeg0c) PrintS("pLDeg0c");
12178  else if (strat->tailRing->pLDeg==pLDegb) PrintS("pLDegb");
12179  else if (strat->tailRing->pLDeg==pLDeg1) PrintS("pLDeg1");
12180  else if (strat->tailRing->pLDeg==pLDeg1c) PrintS("pLDeg1c");
12181  else if (strat->tailRing->pLDeg==pLDeg1_Deg) PrintS("pLDeg1_Deg");
12182  else if (strat->tailRing->pLDeg==pLDeg1c_Deg) PrintS("pLDeg1c_Deg");
12183  else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) PrintS("pLDeg1_Totaldegree");
12184  else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) PrintS("pLDeg1c_Totaldegree");
12185  else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) PrintS("pLDeg1_WFirstTotalDegree");
12186  else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) PrintS("pLDeg1c_WFirstTotalDegree");
12187  else if (strat->tailRing->pLDeg==maxdegreeWecart) PrintS("maxdegreeWecart");
12188  else Print("? (%lx)", (long)strat->tailRing->pLDeg);
12189  PrintLn();
12190  PrintS("currRing->pFDeg: ");
12191  if (currRing->pFDeg==p_Totaldegree) PrintS("p_Totaldegree");
12192  else if (currRing->pFDeg==p_WFirstTotalDegree) PrintS("pWFirstTotalDegree");
12193  else if (currRing->pFDeg==p_Deg) PrintS("p_Deg");
12194  else if (currRing->pFDeg==kHomModDeg) PrintS("kHomModDeg");
12195  else if (currRing->pFDeg==totaldegreeWecart) PrintS("totaldegreeWecart");
12196  else if (currRing->pFDeg==p_WTotaldegree) PrintS("p_WTotaldegree");
12197  else Print("? (%lx)", (long)currRing->pFDeg);
12198  PrintLn();
12199  Print(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
12200  if(TEST_OPT_DEGBOUND)
12201  Print(" degBound: %d\n", Kstd1_deg);
12202 
12203  if( ecartWeights != NULL )
12204  {
12205  PrintS("ecartWeights: ");
12206  for (int i = rVar(currRing); i > 0; i--)
12207  Print("%hd ", ecartWeights[i]);
12208  PrintLn();
12210  }
12211 
12212 #ifndef SING_NDEBUG
12214 #endif
12215 }
int syzComp
Definition: kutil.h:353
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:288
char noTailReduction
Definition: kutil.h:378
char sugarCrit
Definition: kutil.h:377
char Gebauer
Definition: kutil.h:378
int LazyDegree
Definition: kutil.h:352
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2406
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6938
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:7052
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6695
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5805
int posInTrg0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5477
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:784
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6439
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5400
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5342
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5595
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1649
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5671
int posInT0(const TSet, const int length, LObject &)
Definition: kutil.cc:5331
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6783
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6736
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:12046
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5642
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6139
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3476
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5436
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6818
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5912
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11955
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5710
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6096
VAR int Kstd1_deg
Definition: kutil.cc:247
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6509
char * showOption()
Definition: misc_ip.cc:721
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6894
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5553
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6853
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:6039
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5764
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5866
int posInLrg0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6611
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1595
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5973
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6988
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:12009
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3240
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6397
#define assume(x)
Definition: mod2.h:387
#define TEST_OPT_DEGBOUND
Definition: options.h:112
long pLDegb(poly p, int *l, const ring r)
Definition: p_polys.cc:806
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:970
long p_WFirstTotalDegree(poly p, const ring r)
Definition: p_polys.cc:591
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1033
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1063
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:936
long pLDeg1(poly p, int *l, const ring r)
Definition: p_polys.cc:836
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition: p_polys.cc:905
long p_WTotaldegree(poly p, const ring r)
Definition: p_polys.cc:608
long pLDeg1c(poly p, int *l, const ring r)
Definition: p_polys.cc:872
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition: p_polys.cc:1000
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:765
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:734
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:582
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1467
void rDebugPrint(const ring r)
Definition: ring.cc:4075
static int rGetCurrSyzLimit(const ring r)
Definition: ring.h:728
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition: ring.h:725

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r 
)

Definition at line 2406 of file kstd1.cc.

2407 {
2408  int i;
2409  long j=0;
2410 
2411  for (i=r->N;i>0;i--)
2412  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2413  if (kModW == NULL) return j;
2414  i = __p_GetComp(p,r);
2415  if (i==0) return j;
2416  return j+(*kModW)[i-1];
2417 }
VAR intvec * kModW
Definition: kstd1.cc:2394
#define __p_GetComp(p, r)
Definition: monomials.h:63
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:469

◆ kInterRed()

ideal kInterRed ( ideal  F,
ideal  Q 
)

Definition at line 3734 of file kstd1.cc.

3735 {
3736 #ifdef HAVE_PLURAL
3737  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3738 #endif
3741  )
3742  return kInterRedOld(F,Q);
3743 
3744  //return kInterRedOld(F,Q);
3745 
3746  BITSET save1;
3747  SI_SAVE_OPT1(save1);
3748  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3750  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3751  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3752  //extern char * showOption() ;
3753  //Print("%s\n",showOption());
3754 
3755  int need_retry;
3756  int counter=3;
3757  ideal res, res1;
3758  int elems;
3759  ideal null=NULL;
3760  if ((Q==NULL) || (!TEST_OPT_REDSB))
3761  {
3762  elems=idElem(F);
3763  res=kInterRedBba(F,Q,need_retry);
3764  }
3765  else
3766  {
3767  ideal FF=idSimpleAdd(F,Q);
3768  res=kInterRedBba(FF,NULL,need_retry);
3769  idDelete(&FF);
3770  null=idInit(1,1);
3771  if (need_retry)
3772  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3773  else
3774  res1=kNF(null,Q,res);
3775  idDelete(&res);
3776  res=res1;
3777  need_retry=1;
3778  }
3779  if (idElem(res)<=1) need_retry=0;
3780  while (need_retry && (counter>0))
3781  {
3782  #ifdef KDEBUG
3783  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3784  #endif
3785  res1=kInterRedBba(res,Q,need_retry);
3786  int new_elems=idElem(res1);
3787  counter -= (new_elems >= elems);
3788  elems = new_elems;
3789  idDelete(&res);
3790  if (idElem(res1)<=1) need_retry=0;
3791  if ((Q!=NULL) && (TEST_OPT_REDSB))
3792  {
3793  if (need_retry)
3794  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3795  else
3796  res=kNF(null,Q,res1);
3797  idDelete(&res1);
3798  }
3799  else
3800  res = res1;
3801  if (idElem(res)<=1) need_retry=0;
3802  }
3803  if (null!=NULL) idDelete(&null);
3804  SI_RESTORE_OPT1(save1);
3805  idSkipZeroes(res);
3806  return res;
3807 }
CanonicalForm res
Definition: facAbsFact.cc:60
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
ideal kInterRedOld(ideal F, ideal Q)
Definition: kstd1.cc:3382
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3474
#define KSTD_NF_LAZY
Definition: kstd1.h:17
VAR unsigned si_opt_1
Definition: options.c:5
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define OPT_REDTHROUGH
Definition: options.h:81
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:103
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:520
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
int idElem(const ideal F)
count non-zero elements
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define BITSET
Definition: structs.h:20

◆ kInterRedBba()

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

Definition at line 3474 of file kstd1.cc.

3475 {
3476  need_retry=0;
3477  int red_result = 1;
3478  int olddeg,reduc;
3479  BOOLEAN withT = FALSE;
3480  // BOOLEAN toReset=FALSE;
3481  kStrategy strat=new skStrategy;
3482  tHomog h;
3483 
3485  strat->LazyPass=20;
3486  else
3487  strat->LazyPass=2;
3488  strat->LazyDegree = 1;
3489  strat->ak = id_RankFreeModule(F,currRing);
3490  strat->syzComp = strat->ak;
3491  strat->kModW=kModW=NULL;
3492  strat->kHomW=kHomW=NULL;
3493  if (strat->ak == 0)
3494  {
3495  h = (tHomog)idHomIdeal(F,Q);
3496  }
3497  else if (!TEST_OPT_DEGBOUND)
3498  {
3499  h = (tHomog)idHomIdeal(F,Q);
3500  }
3501  else
3502  h = isNotHomog;
3503  if (h==isHomog)
3504  {
3505  strat->LazyPass*=2;
3506  }
3507  strat->homog=h;
3508 #ifdef KDEBUG
3509  idTest(F);
3510 #endif
3511 
3512  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3514  initBuchMoraPosRing(strat);
3515  else
3516  initBuchMoraPos(strat);
3517  initBba(strat);
3518  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3519  strat->posInL=posInL0; /* ord according pComp */
3520 
3521  /*Shdl=*/initBuchMora(F, Q, strat);
3522  reduc = olddeg = 0;
3523 
3524 #ifndef NO_BUCKETS
3525  if (!TEST_OPT_NOT_BUCKETS)
3526  strat->use_buckets = 1;
3527 #endif
3528 
3529  // redtailBBa against T for inhomogenous input
3530  if (!TEST_OPT_OLDSTD)
3531  withT = ! strat->homog;
3532 
3533  // strat->posInT = posInT_pLength;
3534  kTest_TS(strat);
3535 
3536 #ifdef HAVE_TAIL_RING
3537  kStratInitChangeTailRing(strat);
3538 #endif
3539 
3540  /* compute------------------------------------------------------- */
3541  while (strat->Ll >= 0)
3542  {
3543  #ifdef KDEBUG
3544  if (TEST_OPT_DEBUG) messageSets(strat);
3545  #endif
3546  if (strat->Ll== 0) strat->interpt=TRUE;
3547  /* picks the last element from the lazyset L */
3548  strat->P = strat->L[strat->Ll];
3549  strat->Ll--;
3550 
3551  if (strat->P.p1 == NULL)
3552  {
3553  // for input polys, prepare reduction
3554  strat->P.PrepareRed(strat->use_buckets);
3555  }
3556 
3557  if (strat->P.p == NULL && strat->P.t_p == NULL)
3558  {
3559  red_result = 0;
3560  }
3561  else
3562  {
3563  if (TEST_OPT_PROT)
3564  message(strat->P.pFDeg(),
3565  &olddeg,&reduc,strat, red_result);
3566 
3567  /* reduction of the element chosen from L */
3568  red_result = strat->red(&strat->P,strat);
3569  }
3570 
3571  // reduction to non-zero new poly
3572  if (red_result == 1)
3573  {
3574  /* statistic */
3575  if (TEST_OPT_PROT) PrintS("s");
3576 
3577  // get the polynomial (canonicalize bucket, make sure P.p is set)
3578  strat->P.GetP(strat->lmBin);
3579 
3580  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3581 
3582  // reduce the tail and normalize poly
3583  // in the ring case we cannot expect LC(f) = 1,
3584  // therefore we call pCleardenom instead of pNorm
3586  {
3587  strat->P.pCleardenom();
3588  if (0)
3589  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3590  {
3591  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3592  strat->P.pCleardenom();
3593  }
3594  }
3595  else
3596  {
3597  strat->P.pNorm();
3598  if (0)
3599  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3600  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3601  }
3602 
3603 #ifdef KDEBUG
3604  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3605 #endif
3606 
3607  // enter into S, L, and T
3608  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3609  {
3610  enterT(strat->P, strat);
3611  // posInS only depends on the leading term
3612  strat->enterS(strat->P, pos, strat, strat->tl);
3613 
3614  if (pos<strat->sl)
3615  {
3616  need_retry++;
3617  // move all "larger" elements fromS to L
3618  // remove them from T
3619  int ii=pos+1;
3620  for(;ii<=strat->sl;ii++)
3621  {
3622  LObject h;
3623  h.Clear();
3624  h.tailRing=strat->tailRing;
3625  h.p=strat->S[ii]; strat->S[ii]=NULL;
3626  strat->initEcart(&h);
3627  h.sev=strat->sevS[ii];
3628  int jj=strat->tl;
3629  while (jj>=0)
3630  {
3631  if (strat->T[jj].p==h.p)
3632  {
3633  strat->T[jj].p=NULL;
3634  if (jj<strat->tl)
3635  {
3636  memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3637  (strat->tl-jj)*sizeof(strat->T[jj]));
3638  memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3639  (strat->tl-jj)*sizeof(strat->sevT[jj]));
3640  }
3641  strat->tl--;
3642  break;
3643  }
3644  jj--;
3645  }
3646  int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3647  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3648  #ifdef KDEBUG
3649  if (TEST_OPT_DEBUG)
3650  {
3651  Print("move S[%d] -> L[%d]: ",ii,pos);
3652  p_wrp(h.p,currRing, strat->tailRing);
3653  PrintLn();
3654  }
3655  #endif
3656  }
3657  if (strat->fromQ!=NULL)
3658  {
3659  for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3660  }
3661  strat->sl=pos;
3662  }
3663  }
3664  else
3665  {
3666  // clean P
3667  }
3668  kDeleteLcm(&strat->P);
3669  }
3670 
3671 #ifdef KDEBUG
3672  if (TEST_OPT_DEBUG)
3673  {
3674  messageSets(strat);
3675  }
3676  strat->P.Clear();
3677 #endif
3678  //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3679  }
3680 #ifdef KDEBUG
3681  //if (TEST_OPT_DEBUG) messageSets(strat);
3682 #endif
3683  /* complete reduction of the standard basis--------- */
3684 
3685  if((need_retry<=0) && (TEST_OPT_REDSB))
3686  {
3687  completeReduce(strat);
3688  if (strat->completeReduce_retry)
3689  {
3690  // completeReduce needed larger exponents, retry
3691  // hopefully: kStratChangeTailRing already provided a larger tailRing
3692  // (otherwise: it will fail again)
3693  strat->completeReduce_retry=FALSE;
3694  completeReduce(strat);
3695  if (strat->completeReduce_retry)
3696  {
3697 #ifdef HAVE_TAIL_RING
3698  if(currRing->bitmask>strat->tailRing->bitmask)
3699  {
3700  // retry without T
3701  strat->completeReduce_retry=FALSE;
3702  cleanT(strat);strat->tailRing=currRing;
3703  int i;
3704  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3705  completeReduce(strat);
3706  }
3707  if (strat->completeReduce_retry)
3708 #endif
3709  Werror("exponent bound is %ld",currRing->bitmask);
3710  }
3711  }
3712  }
3713  else if (TEST_OPT_PROT) PrintLn();
3714 
3715 
3716  /* release temp data-------------------------------- */
3717  exitBuchMora(strat);
3718 // if (TEST_OPT_WEIGHTM)
3719 // {
3720 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3721 // if (ecartWeights)
3722 // {
3723 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3724 // ecartWeights=NULL;
3725 // }
3726 // }
3727  //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3728  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3729  ideal res=strat->Shdl;
3730  strat->Shdl=NULL;
3731  delete strat;
3732  return res;
3733 }
intvec * kModW
Definition: kutil.h:334
int * S_2_R
Definition: kutil.h:341
omBin lmBin
Definition: kutil.h:343
polyset S
Definition: kutil.h:303
unsigned long * sevT
Definition: kutil.h:322
intvec * kHomW
Definition: kutil.h:335
ideal Shdl
Definition: kutil.h:300
intset fromQ
Definition: kutil.h:318
char interpt
Definition: kutil.h:371
char completeReduce_retry
Definition: kutil.h:403
LObject P
Definition: kutil.h:299
int Lmax
Definition: kutil.h:350
int sl
Definition: kutil.h:347
unsigned long * sevS
Definition: kutil.h:319
#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:1180
void initBba(kStrategy strat)
Definition: kstd1.cc:1659
VAR intvec * kHomW
Definition: kstd1.cc:2394
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:8033
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10322
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1301
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:10149
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10406
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5109
void cleanT(kStrategy strat)
Definition: kutil.cc:545
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10647
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11632
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9997
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10859
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:10235
void messageSets(kStrategy strat)
Definition: kutil.cc:8106
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
#define TEST_OPT_OLDSTD
Definition: options.h:122
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:104
#define pGetComp(p)
Component.
Definition: polys.h:37
void Werror(const char *fmt,...)
Definition: reporter.cc:189
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:553
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
tHomog
Definition: structs.h:40
@ isHomog
Definition: structs.h:42
@ isNotHomog
Definition: structs.h:41

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
ideal  Q 
)

Definition at line 3382 of file kstd1.cc.

3383 {
3384  int j;
3385  kStrategy strat = new skStrategy;
3386 
3387  ideal tempF = F;
3388  ideal tempQ = Q;
3389 
3390 #ifdef HAVE_PLURAL
3391  if(rIsSCA(currRing))
3392  {
3393  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3394  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3395  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3396 
3397  // this should be done on the upper level!!! :
3398  // tempQ = SCAQuotient(currRing);
3399 
3400  if(Q == currRing->qideal)
3401  tempQ = SCAQuotient(currRing);
3402  }
3403 #endif
3404 
3405 // if (TEST_OPT_PROT)
3406 // {
3407 // writeTime("start InterRed:");
3408 // mflush();
3409 // }
3410  //strat->syzComp = 0;
3411  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3412  strat->kNoether=pCopy((currRing->ppNoether));
3413  strat->ak = id_RankFreeModule(tempF,currRing);
3414  initBuchMoraCrit(strat);
3415  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3416  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3417  strat->enterS = enterSBba;
3418  strat->posInT = posInT17;
3419  strat->initEcart = initEcartNormal;
3420  strat->sl = -1;
3421  strat->tl = -1;
3422  strat->tmax = setmaxT;
3423  strat->T = initT();
3424  strat->R = initR();
3425  strat->sevT = initsevT();
3427  initS(tempF, tempQ, strat);
3428  if (TEST_OPT_REDSB)
3429  strat->noTailReduction=FALSE;
3430  updateS(TRUE,strat);
3432  completeReduce(strat);
3433  //else if (TEST_OPT_PROT) PrintLn();
3434  cleanT(strat);
3435  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3436  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3437  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3438  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3439  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3440  omfree(strat->sevT);
3441  omfree(strat->S_2_R);
3442  omfree(strat->R);
3443 
3444  if (strat->fromQ)
3445  {
3446  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3447  {
3448  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3449  }
3450  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3451  }
3452 // if (TEST_OPT_PROT)
3453 // {
3454 // writeTime("end Interred:");
3455 // mflush();
3456 // }
3457  ideal shdl=strat->Shdl;
3458  idSkipZeroes(shdl);
3459  if (strat->fromQ)
3460  {
3461  strat->fromQ=NULL;
3462  ideal res=kInterRed(shdl,NULL);
3463  idDelete(&shdl);
3464  shdl=res;
3465  }
3466  delete(strat);
3467 #ifdef HAVE_PLURAL
3468  if( tempF != F )
3469  id_Delete( &tempF, currRing);
3470 #endif
3471  return shdl;
3472 }
intset ecartS
Definition: kutil.h:306
TObject ** R
Definition: kutil.h:339
poly kHEdge
Definition: kutil.h:326
int tmax
Definition: kutil.h:349
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
KINLINE TSet initT()
Definition: kInline.h:84
KINLINE TObject ** initR()
Definition: kInline.h:95
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3734
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8156
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:9115
#define setmaxT
Definition: kutil.h:33
class sTObject TObject
Definition: kutil.h:53
static bool rIsSCA(const ring r)
Definition: nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1520
#define omfree(addr)
Definition: omAllocDecl.h:237
#define pDelete(p_ptr)
Definition: polys.h:186
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition: polys.h:70
ideal SCAQuotient(const ring r)
Definition: sca.h:10
static short scaLastAltVar(ring r)
Definition: sca.h:25
static short scaFirstAltVar(ring r)
Definition: sca.h:18
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix

◆ kMin_std()

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

Definition at line 3009 of file kstd1.cc.

3011 {
3012  if(idIs0(F))
3013  {
3014  M=idInit(1,F->rank);
3015  return idInit(1,F->rank);
3016  }
3018  {
3019  ideal sb;
3020  sb = kStd(F, Q, h, w, hilb);
3021  idSkipZeroes(sb);
3022  if(IDELEMS(sb) <= IDELEMS(F))
3023  {
3024  M = idCopy(sb);
3025  idSkipZeroes(M);
3026  return(sb);
3027  }
3028  else
3029  {
3030  M = idCopy(F);
3031  idSkipZeroes(M);
3032  return(sb);
3033  }
3034  }
3035  ideal r=NULL;
3036  int Kstd1_OldDeg = Kstd1_deg,i;
3037  intvec* temp_w=NULL;
3038  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3039  BOOLEAN delete_w=(w==NULL);
3040  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3041  kStrategy strat=new skStrategy;
3042 
3043  if(!TEST_OPT_RETURN_SB)
3044  strat->syzComp = syzComp;
3046  strat->LazyPass=20;
3047  else
3048  strat->LazyPass=2;
3049  strat->LazyDegree = 1;
3050  strat->minim=(reduced % 2)+1;
3051  strat->ak = id_RankFreeModule(F,currRing);
3052  if (delete_w)
3053  {
3054  temp_w=new intvec((strat->ak)+1);
3055  w = &temp_w;
3056  }
3057  if (h==testHomog)
3058  {
3059  if (strat->ak == 0)
3060  {
3061  h = (tHomog)idHomIdeal(F,Q);
3062  w=NULL;
3063  }
3064  else
3065  {
3066  h = (tHomog)idHomModule(F,Q,w);
3067  }
3068  }
3069  if (h==isHomog)
3070  {
3071  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3072  {
3073  kModW = *w;
3074  strat->kModW = *w;
3075  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3076  strat->pOrigFDeg = currRing->pFDeg;
3077  strat->pOrigLDeg = currRing->pLDeg;
3079 
3080  toReset = TRUE;
3081  if (reduced>1)
3082  {
3083  Kstd1_OldDeg=Kstd1_deg;
3084  Kstd1_deg = -1;
3085  for (i=IDELEMS(F)-1;i>=0;i--)
3086  {
3087  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3088  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3089  }
3090  }
3091  }
3092  currRing->pLexOrder = TRUE;
3093  strat->LazyPass*=2;
3094  }
3095  strat->homog=h;
3097  {
3098  if (w!=NULL)
3099  r=mora(F,Q,*w,hilb,strat);
3100  else
3101  r=mora(F,Q,NULL,hilb,strat);
3102  }
3103  else
3104  {
3105  if (w!=NULL)
3106  r=bba(F,Q,*w,hilb,strat);
3107  else
3108  r=bba(F,Q,NULL,hilb,strat);
3109  }
3110 #ifdef KDEBUG
3111  {
3112  int i;
3113  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3114  }
3115 #endif
3116  idSkipZeroes(r);
3117  if (toReset)
3118  {
3119  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3120  kModW = NULL;
3121  }
3122  currRing->pLexOrder = b;
3123  HCord=strat->HCord;
3124  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3125  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3126  {
3127  M=idInit(1,F->rank);
3128  M->m[0]=pOne();
3129  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3130  if (strat->M!=NULL) idDelete(&strat->M);
3131  }
3132  else if (strat->M==NULL)
3133  {
3134  M=idInit(1,F->rank);
3135  WarnS("no minimal generating set computed");
3136  }
3137  else
3138  {
3139  idSkipZeroes(strat->M);
3140  M=strat->M;
3141  }
3142  delete(strat);
3143  if (reduced>2)
3144  {
3145  Kstd1_deg=Kstd1_OldDeg;
3146  if (!oldDegBound)
3148  }
3149  else
3150  {
3151  if (IDELEMS(M)>IDELEMS(r)) {
3152  idDelete(&M);
3153  M=idCopy(r); }
3154  }
3155  return r;
3156 }
CanonicalForm b
Definition: cfModGcd.cc:4105
Definition: intvec.h:23
int minim
Definition: kutil.h:357
ideal M
Definition: kutil.h:302
#define WarnS
Definition: emacs.cc:78
const CanonicalForm & w
Definition: facAbsFact.cc:51
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
ideal idCopy(ideal A)
Definition: ideals.h:60
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd1.cc:1848
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2396
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:2419
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2383
VAR int HCord
Definition: kutil.cc:246
#define TEST_OPT_RETURN_SB
Definition: options.h:111
#define OPT_DEGBOUND
Definition: options.h:89
#define pTest(p)
Definition: polys.h:415
#define pIsConstant(p)
like above, except that Comp must be 0
Definition: polys.h:238
#define pOne()
Definition: polys.h:315
#define M
Definition: sirandom.c:25
@ testHomog
Definition: structs.h:43

◆ kModDeg()

long kModDeg ( poly  p,
ring  r 
)

Definition at line 2396 of file kstd1.cc.

2397 {
2398  long o=p_WDegree(p, r);
2399  long i=__p_GetComp(p, r);
2400  if (i==0) return o;
2401  //assume((i>0) && (i<=kModW->length()));
2402  if (i<=kModW->length())
2403  return o+(*kModW)[i-1];
2404  return o;
2405 }
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:709

◆ kMoraUseBucket()

static BOOLEAN kMoraUseBucket ( kStrategy  strat)
static

Definition at line 3810 of file kstd1.cc.

3811 {
3812 #ifdef MORA_USE_BUCKETS
3814  return FALSE;
3815  if (strat->red == redFirst)
3816  {
3817 #ifdef NO_LDEG
3818  if (strat->syzComp==0)
3819  return TRUE;
3820 #else
3821  if ((strat->homog || strat->honey) && (strat->syzComp==0))
3822  return TRUE;
3823 #endif
3824  }
3825  else
3826  {
3827  #ifdef HAVE_RINGS
3828  assume(strat->red == redEcart || strat->red == redRiloc);
3829  #else
3830  assume(strat->red == redEcart);
3831  #endif
3832  if (strat->honey && (strat->syzComp==0))
3833  return TRUE;
3834  }
3835 #endif
3836  return FALSE;
3837 }

◆ kNF() [1/2]

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

Definition at line 3255 of file kstd1.cc.

3256 {
3257  ideal res;
3258  if (TEST_OPT_PROT)
3259  {
3260  Print("(S:%d)",IDELEMS(p));mflush();
3261  }
3262  if (idIs0(p))
3263  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3264 
3265  ideal pp = p;
3266 #ifdef HAVE_PLURAL
3267  if(rIsSCA(currRing))
3268  {
3269  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3270  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3271  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3272 
3273  if(Q == currRing->qideal)
3274  Q = SCAQuotient(currRing);
3275  }
3276 #endif
3277 
3278  if ((idIs0(F))&&(Q==NULL))
3279  {
3280 #ifdef HAVE_PLURAL
3281  if(p != pp)
3282  return pp;
3283 #endif
3284  return idCopy(p); /*F+Q=0*/
3285  }
3286 
3287  kStrategy strat=new skStrategy;
3288  strat->syzComp = syzComp;
3290  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3291  {
3292  strat->ak = si_max(strat->ak,(int)F->rank);
3293  }
3294 
3296  {
3297 #ifdef HAVE_SHIFTBBA
3298  if (currRing->isLPring)
3299  {
3300  WerrorS("No local ordering possible for shift algebra");
3301  return(NULL);
3302  }
3303 #endif
3304  res=kNF1(F,Q,pp,strat,lazyReduce);
3305  }
3306  else
3307  res=kNF2(F,Q,pp,strat,lazyReduce);
3308  delete(strat);
3309 
3310 #ifdef HAVE_PLURAL
3311  if(pp != p)
3312  id_Delete(&pp, currRing);
3313 #endif
3314 
3315  return res;
3316 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
void WerrorS(const char *s)
Definition: feFopen.cc:24
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:2097
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3712

◆ kNF() [2/2]

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

Definition at line 3158 of file kstd1.cc.

3159 {
3160  if (p==NULL)
3161  return NULL;
3162 
3163  poly pp = p;
3164 
3165 #ifdef HAVE_PLURAL
3166  if(rIsSCA(currRing))
3167  {
3168  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3169  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3170  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3171 
3172  if(Q == currRing->qideal)
3173  Q = SCAQuotient(currRing);
3174  }
3175 #endif
3176 
3177  if ((idIs0(F))&&(Q==NULL))
3178  {
3179 #ifdef HAVE_PLURAL
3180  if(p != pp)
3181  return pp;
3182 #endif
3183  return pCopy(p); /*F+Q=0*/
3184  }
3185 
3186  kStrategy strat=new skStrategy;
3187  strat->syzComp = syzComp;
3188  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3189  poly res;
3190 
3192  {
3193 #ifdef HAVE_SHIFTBBA
3194  if (currRing->isLPring)
3195  {
3196  WerrorS("No local ordering possible for shift algebra");
3197  return(NULL);
3198  }
3199 #endif
3200  res=kNF1(F,Q,pp,strat,lazyReduce);
3201  }
3202  else
3203  res=kNF2(F,Q,pp,strat,lazyReduce);
3204  delete(strat);
3205 
3206 #ifdef HAVE_PLURAL
3207  if(pp != p)
3208  p_Delete(&pp, currRing);
3209 #endif
3210  return res;
3211 }
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1465
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
#define pMaxComp(p)
Definition: polys.h:299

◆ kNF1() [1/2]

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

Definition at line 2241 of file kstd1.cc.

2242 {
2243  assume(!idIs0(q));
2244  assume(!(idIs0(F)&&(Q==NULL)));
2245 
2246 // lazy_reduce flags: can be combined by |
2247 //#define KSTD_NF_LAZY 1
2248  // do only a reduction of the leading term
2249 //#define KSTD_NF_ECART 2
2250  // only local: recude even with bad ecart
2251  poly p;
2252  int i;
2253  int j;
2254  int o;
2255  LObject h;
2256  ideal res;
2257  BITSET save1;
2258  SI_SAVE_OPT1(save1);
2259 
2260  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2261  //if ((idIs0(F))&&(Q==NULL))
2262  // return idCopy(q); /*F=0*/
2263  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2264  /*- creating temp data structures------------------- -*/
2265  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2266  strat->kNoether=pCopy((currRing->ppNoether));
2269  && (0<Kstd1_deg)
2270  && ((!strat->kHEdgeFound)
2272  {
2273  pLmDelete(&strat->kNoether);
2274  strat->kNoether=pOne();
2275  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2276  pSetm(strat->kNoether);
2277  strat->kHEdgeFound=TRUE;
2278  }
2279  initBuchMoraCrit(strat);
2281  initBuchMoraPosRing(strat);
2282  else
2283  initBuchMoraPos(strat);
2284  initMora(F,strat);
2285  strat->enterS = enterSMoraNF;
2286  /*- set T -*/
2287  strat->tl = -1;
2288  strat->tmax = setmaxT;
2289  strat->T = initT();
2290  strat->R = initR();
2291  strat->sevT = initsevT();
2292  /*- set S -*/
2293  strat->sl = -1;
2294  /*- init local data struct.-------------------------- -*/
2295  /*Shdl=*/initS(F,Q,strat);
2296  if ((strat->ak!=0)
2297  && (strat->kHEdgeFound))
2298  {
2299  if (strat->ak!=1)
2300  {
2301  pSetComp(strat->kNoether,1);
2302  pSetmComp(strat->kNoether);
2303  poly p=pHead(strat->kNoether);
2304  pSetComp(p,strat->ak);
2305  pSetmComp(p);
2306  p=pAdd(strat->kNoether,p);
2307  strat->kNoether=pNext(p);
2309  }
2310  }
2311  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
2312  {
2313  for (i=strat->sl; i>=0; i--)
2314  pNorm(strat->S[i]);
2315  }
2316  /*- compute------------------------------------------- -*/
2317  res=idInit(IDELEMS(q),strat->ak);
2318  for (i=0; i<IDELEMS(q); i++)
2319  {
2320  if (q->m[i]!=NULL)
2321  {
2322  p = pCopy(q->m[i]);
2323  deleteHC(&p,&o,&j,strat);
2324  if (p!=NULL)
2325  {
2326  /*- puts the elements of S also to T -*/
2327  for (j=0; j<=strat->sl; j++)
2328  {
2329  h.p = strat->S[j];
2330  h.ecart = strat->ecartS[j];
2331  h.pLength = h.length = pLength(h.p);
2332  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2333  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2334  h.sev = strat->sevS[j];
2335  h.SetpFDeg();
2337  enterT_strong(h,strat);
2338  else
2339  enterT(h,strat);
2340  }
2341  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2343  {
2344  p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2345  }
2346  else
2347  p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2348  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2349  {
2350  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2351  p = redtail(p,strat->sl,strat);
2352  }
2353  cleanT(strat);
2354  }
2355  res->m[i]=p;
2356  }
2357  //else
2358  // res->m[i]=NULL;
2359  }
2360  /*- release temp data------------------------------- -*/
2361  assume(strat->L==NULL); /*strat->L unsed */
2362  assume(strat->B==NULL); /*strat->B unused */
2363  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2364  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2365  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2366  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2367  omFree(strat->sevT);
2368  omFree(strat->S_2_R);
2369  omFree(strat->R);
2370  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2371  {
2373  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2374  strat->fromQ=NULL;
2375  }
2376  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2377  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2378 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2379 // {
2380 // pFDeg=strat->pOrigFDeg;
2381 // pLDeg=strat->pOrigLDeg;
2382 // if (ecartWeights)
2383 // {
2384 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2385 // ecartWeights=NULL;
2386 // }
2387 // }
2388  idDelete(&strat->Shdl);
2389  SI_RESTORE_OPT1(save1);
2390  if (TEST_OPT_PROT) PrintLn();
2391  return res;
2392 }
LSet B
Definition: kutil.h:325
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1787
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1649
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1056
#define KSTD_NF_ECART
Definition: kstd1.h:19
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7480
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:254
#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:203
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pSetm(p)
Definition: polys.h:271
#define pSetComp(p, v)
Definition: polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
#define pSetmComp(p)
TODO:
Definition: polys.h:273
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:363
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pWTotaldegree(p)
Definition: polys.h:283

◆ kNF1() [2/2]

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

Definition at line 2097 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 3318 of file kstd1.cc.

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

◆ kNFBound() [2/2]

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

Definition at line 3213 of file kstd1.cc.

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

◆ kOptimizeLDeg()

static void kOptimizeLDeg ( pLDegProc  ldeg,
kStrategy  strat 
)
static

Definition at line 100 of file kstd1.cc.

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

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

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

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

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

◆ kStdShift()

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

Definition at line 2900 of file kstd1.cc.

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

◆ missingAxis()

void missingAxis ( int *  last,
kStrategy  strat 
)

Definition at line 1250 of file kstd1.cc.

1251 {
1252  int i = 0;
1253  int k = 0;
1254 
1255  *last = 0;
1257  {
1258  loop
1259  {
1260  i++;
1261  if (i > (currRing->N)) break;
1262  if (strat->NotUsedAxis[i])
1263  {
1264  *last = i;
1265  k++;
1266  }
1267  if (k>1)
1268  {
1269  *last = 0;
1270  break;
1271  }
1272  }
1273  }
1274 }
int k
Definition: cfEzgcd.cc:99
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:766
#define loop
Definition: structs.h:80

◆ mora()

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

Definition at line 1848 of file kstd1.cc.

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

1332 {
1333  int j,dp,dL;
1334 
1335  if (length<0) return 0;
1336  if (hasPurePower(p,strat->lastAxis,&dp,strat))
1337  {
1338  int op= p->GetpFDeg() +p->ecart;
1339  for (j=length; j>=0; j--)
1340  {
1341  if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1342  return j+1;
1343  if (dp < dL)
1344  return j+1;
1345  if ((dp == dL)
1346  && (set[j].GetpFDeg()+set[j].ecart >= op))
1347  return j+1;
1348  }
1349  }
1350  j=length;
1351  loop
1352  {
1353  if (j<0) break;
1354  if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1355  j--;
1356  }
1357  return strat->posInLOld(set,j,p,strat);
1358 }

◆ redEcart()

int redEcart ( LObject h,
kStrategy  strat 
)

Definition at line 169 of file kstd1.cc.

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

◆ redFirst()

int redFirst ( LObject h,
kStrategy  strat 
)

Definition at line 784 of file kstd1.cc.

785 {
786  if (h->IsNull()) return 0;
787 
788  int at;
789  long reddeg,d;
790  int pass = 0;
791  int j = 0;
792 
793  if (! strat->homog)
794  {
795  d = h->GetpFDeg() + h->ecart;
796  reddeg = strat->LazyDegree+d;
797  }
798  h->SetShortExpVector();
799  loop
800  {
801  j = kFindDivisibleByInT(strat, h);
802  if (j < 0)
803  {
804  h->SetDegStuffReturnLDeg(strat->LDegLast);
805  return 1;
806  }
807 
809  strat->T[j].pNorm();
810 #ifdef KDEBUG
811  if (TEST_OPT_DEBUG)
812  {
813  PrintS("reduce ");
814  h->wrp();
815  PrintS(" with ");
816  strat->T[j].wrp();
817  }
818 #endif
819  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
820 #ifdef KDEBUG
821  if (TEST_OPT_DEBUG)
822  {
823  PrintS(" to ");
824  wrp(h->p);
825  PrintLn();
826  }
827 #endif
828  if (h->IsNull())
829  {
831  kDeleteLcm(h);
832  h->Clear();
833  return 0;
834  }
835  if (TEST_OPT_IDLIFT)
836  {
837  if (h->p!=NULL)
838  {
839  if(p_GetComp(h->p,currRing)>strat->syzComp)
840  {
841  h->Delete();
842  return 0;
843  }
844  }
845  else if (h->t_p!=NULL)
846  {
847  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
848  {
849  h->Delete();
850  return 0;
851  }
852  }
853  }
854  #if 0
855  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
856  {
857  if (h->p!=NULL)
858  {
859  if(p_GetComp(h->p,currRing)>strat->syzComp)
860  {
861  return 1;
862  }
863  }
864  else if (h->t_p!=NULL)
865  {
866  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
867  {
868  return 1;
869  }
870  }
871  }
872  #endif
873  h->SetShortExpVector();
874 
875 #if 0
876  if ((strat->syzComp!=0) && !strat->honey)
877  {
878  if ((strat->syzComp>0) &&
879  (h->Comp() > strat->syzComp))
880  {
881  assume(h->MinComp() > strat->syzComp);
882 #ifdef KDEBUG
883  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
884 #endif
885  if (strat->homog)
886  h->SetDegStuffReturnLDeg(strat->LDegLast);
887  return -2;
888  }
889  }
890 #endif
891  if (!strat->homog)
892  {
893  if (!TEST_OPT_OLDSTD && strat->honey)
894  {
895  h->SetpFDeg();
896  if (strat->T[j].ecart <= h->ecart)
897  h->ecart = d - h->GetpFDeg();
898  else
899  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
900 
901  d = h->GetpFDeg() + h->ecart;
902  }
903  else
904  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
905  /*- try to reduce the s-polynomial -*/
906  pass++;
907  /*
908  *test whether the polynomial should go to the lazyset L
909  *-if the degree jumps
910  *-if the number of pre-defined reductions jumps
911  */
912  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
913  && ((d >= reddeg) || (pass > strat->LazyPass)))
914  {
915  h->SetLmCurrRing();
916  if (strat->posInLDependsOnLength)
917  h->SetLength(strat->length_pLength);
918  at = strat->posInL(strat->L,strat->Ll,h,strat);
919  if (at <= strat->Ll)
920  {
921  int dummy=strat->sl;
922  if (kFindDivisibleByInS(strat,&dummy, h) < 0)
923  return 1;
924  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
925 #ifdef KDEBUG
926  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
927 #endif
928  h->Clear();
929  return -1;
930  }
931  }
932  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
933  {
934  reddeg = d+1;
935  Print(".%ld",d);mflush();
936  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
937  {
938  strat->overflow=TRUE;
939  //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
940  h->GetP();
941  at = strat->posInL(strat->L,strat->Ll,h,strat);
942  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
943  h->Clear();
944  return -1;
945  }
946  }
947  }
948  }
949 }
void wrp(poly p)
Definition: polys.h:310

◆ redMoraNF()

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

Definition at line 956 of file kstd1.cc.

957 {
958  LObject H;
959  H.p = h;
960  int j = 0;
961  int z = 10;
962  int o = H.SetpFDeg();
963  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
964  if ((flag & 2) == 0) cancelunit(&H,TRUE);
965  H.sev = pGetShortExpVector(H.p);
966  unsigned long not_sev = ~ H.sev;
967  loop
968  {
969  if (j > strat->tl)
970  {
971  return H.p;
972  }
973  if (TEST_V_DEG_STOP)
974  {
975  if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
976  if (H.p==NULL) return NULL;
977  }
978  if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
979  )
980  {
981  /*- remember the found T-poly -*/
982  // poly pi = strat->T[j].p;
983  int ei = strat->T[j].ecart;
984  int li = strat->T[j].length;
985  int ii = j;
986  /*
987  * the polynomial to reduce with (up to the moment) is;
988  * pi with ecart ei and length li
989  */
990  loop
991  {
992  /*- look for a better one with respect to ecart -*/
993  /*- stop, if the ecart is small enough (<=ecart(H)) -*/
994  j++;
995  if (j > strat->tl) break;
996  if (ei <= H.ecart) break;
997  if (((strat->T[j].ecart < ei)
998  || ((strat->T[j].ecart == ei)
999  && (strat->T[j].length < li)))
1000  && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1001  )
1002  {
1003  /*
1004  * the polynomial to reduce with is now;
1005  */
1006  // pi = strat->T[j].p;
1007  ei = strat->T[j].ecart;
1008  li = strat->T[j].length;
1009  ii = j;
1010  }
1011  }
1012  /*
1013  * end of search: have to reduce with pi
1014  */
1015  z++;
1016  if (z>10)
1017  {
1018  pNormalize(H.p);
1019  z=0;
1020  }
1021  if ((ei > H.ecart) && (!strat->kHEdgeFound))
1022  {
1023  /*
1024  * It is not possible to reduce h with smaller ecart;
1025  * we have to reduce with bad ecart: H has to enter in T
1026  */
1027  doRed(&H,&(strat->T[ii]),TRUE,strat,TRUE);
1028  if (H.p == NULL)
1029  return NULL;
1030  }
1031  else
1032  {
1033  /*
1034  * we reduce with good ecart, h need not to be put to T
1035  */
1036  doRed(&H,&(strat->T[ii]),FALSE,strat,TRUE);
1037  if (H.p == NULL)
1038  return NULL;
1039  }
1040  /*- try to reduce the s-polynomial -*/
1041  o = H.SetpFDeg();
1042  if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1043  H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1044  j = 0;
1045  H.sev = pGetShortExpVector(H.p);
1046  not_sev = ~ H.sev;
1047  }
1048  else
1049  {
1050  j++;
1051  }
1052  }
1053 }
CanonicalForm H
Definition: facAbsFact.cc:60
#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:317

◆ redMoraNFRing()

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

Definition at line 1056 of file kstd1.cc.

1057 {
1058  LObject H;
1059  H.p = h;
1060  int j0, j = 0;
1061  int z = 10;
1062  int docoeffred = 0;
1063  poly T0p = strat->T[0].p;
1064  int T0ecart = strat->T[0].ecart;
1065  int o = H.SetpFDeg();
1066  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
1067  if ((flag & 2) == 0) cancelunit(&H,TRUE);
1068  H.sev = pGetShortExpVector(H.p);
1069  unsigned long not_sev = ~ H.sev;
1070  if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2) {
1071  docoeffred = 1;
1072  }
1073  loop
1074  {
1075  /* cut down the lead coefficients, only possible if the degree of
1076  * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
1077  * we ask for the length of T[0] to be <= 2 */
1078  if (docoeffred) {
1079  j0 = kTestDivisibleByT0_Z(strat, &H);
1080  if (j0 == 0 && n_DivBy(pGetCoeff(H.p), pGetCoeff(T0p), currRing->cf) == FALSE
1081  && T0ecart <= H.ecart) {
1082  /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
1083  * => we try to cut down the lead coefficient at least */
1084  /* first copy T[j0] in order to multiply it with a coefficient later on */
1085  number mult, rest;
1086  TObject tj = strat->T[0];
1087  tj.Copy();
1088  /* compute division with remainder of lc(h) and lc(T[j]) */
1089  mult = n_QuotRem(pGetCoeff(H.p), pGetCoeff(T0p),
1090  &rest, currRing->cf);
1091  /* set corresponding new lead coefficient already. we do not
1092  * remove the lead term in ksReducePolyLC, but only apply
1093  * a lead coefficient reduction */
1094  tj.Mult_nn(mult);
1095  ksReducePolyLC(&H, &tj, NULL, &rest, strat);
1096  tj.Delete();
1097  tj.Clear();
1098  }
1099  }
1100  if (j > strat->tl)
1101  {
1102  return H.p;
1103  }
1104  if (TEST_V_DEG_STOP)
1105  {
1106  if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
1107  if (H.p==NULL) return NULL;
1108  }
1109  if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1110  && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1111  )
1112  {
1113  /*- remember the found T-poly -*/
1114  // poly pi = strat->T[j].p;
1115  int ei = strat->T[j].ecart;
1116  int li = strat->T[j].length;
1117  int ii = j;
1118  /*
1119  * the polynomial to reduce with (up to the moment) is;
1120  * pi with ecart ei and length li
1121  */
1122  loop
1123  {
1124  /*- look for a better one with respect to ecart -*/
1125  /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1126  j++;
1127  if (j > strat->tl) break;
1128  if (ei <= H.ecart) break;
1129  if (((strat->T[j].ecart < ei)
1130  || ((strat->T[j].ecart == ei)
1131  && (strat->T[j].length < li)))
1132  && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1133  && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1134  )
1135  {
1136  /*
1137  * the polynomial to reduce with is now;
1138  */
1139  // pi = strat->T[j].p;
1140  ei = strat->T[j].ecart;
1141  li = strat->T[j].length;
1142  ii = j;
1143  }
1144  }
1145  /*
1146  * end of search: have to reduce with pi
1147  */
1148  z++;
1149  if (z>10)
1150  {
1151  pNormalize(H.p);
1152  z=0;
1153  }
1154  if ((ei > H.ecart) && (!strat->kHEdgeFound))
1155  {
1156  /*
1157  * It is not possible to reduce h with smaller ecart;
1158  * we have to reduce with bad ecart: H has to enter in T
1159  */
1160  doRed(&H,&(strat->T[ii]),TRUE,strat,TRUE);
1161  if (H.p == NULL)
1162  return NULL;
1163  }
1164  else
1165  {
1166  /*
1167  * we reduce with good ecart, h need not to be put to T
1168  */
1169  doRed(&H,&(strat->T[ii]),FALSE,strat,TRUE);
1170  if (H.p == NULL)
1171  return NULL;
1172  }
1173  /*- try to reduce the s-polynomial -*/
1174  o = H.SetpFDeg();
1175  if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1176  H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1177  j = 0;
1178  H.sev = pGetShortExpVector(H.p);
1179  not_sev = ~ H.sev;
1180  }
1181  else
1182  {
1183  j++;
1184  }
1185  }
1186 }
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition: coeffs.h:704
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:777
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:452
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject *L)
tests if T[0] divides the leading monomial of L, returns -1 if not
Definition: kstd2.cc:140
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647

◆ redRiloc()

int redRiloc ( LObject h,
kStrategy  strat 
)

Definition at line 383 of file kstd1.cc.

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

◆ redRiloc_Z()

int redRiloc_Z ( LObject h,
kStrategy  strat 
)

Definition at line 564 of file kstd1.cc.

565 {
566  int i,at,ei,li,ii;
567  int j = 0;
568  int pass = 0;
569  long d,reddeg;
570  int docoeffred = 0;
571  poly T0p = strat->T[0].p;
572  int T0ecart = strat->T[0].ecart;
573 
574 
575  d = h->GetpFDeg()+ h->ecart;
576  reddeg = strat->LazyDegree+d;
577  h->SetShortExpVector();
578  if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2) {
579  docoeffred = 1;
580  }
581  loop
582  {
583  /* cut down the lead coefficients, only possible if the degree of
584  * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
585  * we ask for the length of T[0] to be <= 2 */
586  if (docoeffred) {
587  j = kTestDivisibleByT0_Z(strat, h);
588  if (j == 0 && n_DivBy(pGetCoeff(h->p), pGetCoeff(T0p), currRing->cf) == FALSE
589  && T0ecart <= h->ecart) {
590  /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
591  * => we try to cut down the lead coefficient at least */
592  /* first copy T[j] in order to multiply it with a coefficient later on */
593  number mult, rest;
594  TObject tj = strat->T[0];
595  tj.Copy();
596  /* compute division with remainder of lc(h) and lc(T[j]) */
597  mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(T0p),
598  &rest, currRing->cf);
599  /* set corresponding new lead coefficient already. we do not
600  * remove the lead term in ksReducePolyLC, but only apply
601  * a lead coefficient reduction */
602  tj.Mult_nn(mult);
603  ksReducePolyLC(h, &tj, NULL, &rest, strat);
604  tj.Delete();
605  tj.Clear();
606  }
607  }
608  j = kFindDivisibleByInT(strat, h);
609  if (j < 0)
610  {
611  // over ZZ: cleanup coefficients by complete reduction with monomials
612  postReduceByMon(h, strat);
613  if(h->p == NULL)
614  {
615  kDeleteLcm(h);
616  h->Clear();
617  return 0;
618  }
619  if (strat->honey) h->SetLength(strat->length_pLength);
620  if(strat->tl >= 0)
621  h->i_r1 = strat->tl;
622  else
623  h->i_r1 = -1;
624  if (h->GetLmTailRing() == NULL)
625  {
626  kDeleteLcm(h);
627  h->Clear();
628  return 0;
629  }
630  return 1;
631  }
632 
633  ei = strat->T[j].ecart;
634  ii = j;
635 #if 1
636  if (ei > h->ecart && ii < strat->tl)
637  {
638  li = strat->T[j].length;
639  // the polynomial to reduce with (up to the moment) is;
640  // pi with ecart ei and length li
641  // look for one with smaller ecart
642  i = j;
643  loop
644  {
645  /*- takes the first possible with respect to ecart -*/
646  i++;
647 #if 1
648  if (i > strat->tl) break;
649  if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
650  strat->T[i].length < li))
651  &&
652  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
653  &&
654  n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
655 #else
656  j = kFindDivisibleByInT(strat, h, i);
657  if (j < 0) break;
658  i = j;
659  if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
660  strat->T[i].length < li))
661 #endif
662  {
663  // the polynomial to reduce with is now
664  ii = i;
665  ei = strat->T[i].ecart;
666  if (ei <= h->ecart) break;
667  li = strat->T[i].length;
668  }
669  }
670  }
671 #endif
672 
673  // end of search: have to reduce with pi
674  if (ei > h->ecart)
675  {
676  // It is not possible to reduce h with smaller ecart;
677  // if possible h goes to the lazy-set L,i.e
678  // if its position in L would be not the last one
679  strat->fromT = TRUE;
680  if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
681  {
682  h->SetLmCurrRing();
683  if (strat->honey && strat->posInLDependsOnLength)
684  h->SetLength(strat->length_pLength);
685  assume(h->FDeg == h->pFDeg());
686  at = strat->posInL(strat->L,strat->Ll,h,strat);
687  if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
688  {
689  /*- h will not become the next element to reduce -*/
690  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
691 #ifdef KDEBUG
692  if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
693 #endif
694  h->Clear();
695  strat->fromT = FALSE;
696  return -1;
697  }
698  }
699  doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
700  }
701  else
702  {
703  // now we finally can reduce
704  doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
705  }
706  strat->fromT=FALSE;
707  // are we done ???
708  if (h->IsNull())
709  {
710  kDeleteLcm(h);
711  h->Clear();
712  return 0;
713  }
714 
715  // NO!
716  h->SetShortExpVector();
717  h->SetpFDeg();
718  if (strat->honey)
719  {
720  if (ei <= h->ecart)
721  h->ecart = d-h->GetpFDeg();
722  else
723  h->ecart = d-h->GetpFDeg()+ei-h->ecart;
724  }
725  else
726  // this has the side effect of setting h->length
727  h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
728  /*- try to reduce the s-polynomial -*/
729  pass++;
730  d = h->GetpFDeg()+h->ecart;
731  /*
732  *test whether the polynomial should go to the lazyset L
733  *-if the degree jumps
734  *-if the number of pre-defined reductions jumps
735  */
736  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
737  && ((d >= reddeg) || (pass > strat->LazyPass)))
738  {
739  h->SetLmCurrRing();
740  if (strat->honey && strat->posInLDependsOnLength)
741  h->SetLength(strat->length_pLength);
742  assume(h->FDeg == h->pFDeg());
743  at = strat->posInL(strat->L,strat->Ll,h,strat);
744  if (at <= strat->Ll)
745  {
746  int dummy=strat->sl;
747  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
748  {
749  if (strat->honey && !strat->posInLDependsOnLength)
750  h->SetLength(strat->length_pLength);
751  return 1;
752  }
753  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
754 #ifdef KDEBUG
755  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
756 #endif
757  h->Clear();
758  return -1;
759  }
760  }
761  else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
762  {
763  Print(".%ld",d);mflush();
764  reddeg = d+1;
765  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
766  {
767  strat->overflow=TRUE;
768  //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
769  h->GetP();
770  at = strat->posInL(strat->L,strat->Ll,h,strat);
771  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
772  h->Clear();
773  return -1;
774  }
775  }
776  }
777 }

◆ reorderL()

void reorderL ( kStrategy  strat)

Definition at line 1192 of file kstd1.cc.

1193 {
1194  int i,j,at;
1195  LObject p;
1196 
1197  for (i=1; i<=strat->Ll; i++)
1198  {
1199  at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
1200  if (at != i)
1201  {
1202  p = strat->L[i];
1203  for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
1204  strat->L[at] = p;
1205  }
1206  }
1207 }

◆ reorderT()

void reorderT ( kStrategy  strat)

Definition at line 1212 of file kstd1.cc.

1213 {
1214  int i,j,at;
1215  TObject p;
1216  unsigned long sev;
1217 
1218 
1219  for (i=1; i<=strat->tl; i++)
1220  {
1221  if (strat->T[i-1].length > strat->T[i].length)
1222  {
1223  p = strat->T[i];
1224  sev = strat->sevT[i];
1225  at = i-1;
1226  loop
1227  {
1228  at--;
1229  if (at < 0) break;
1230  if (strat->T[i].length > strat->T[at].length) break;
1231  }
1232  for (j = i-1; j>at; j--)
1233  {
1234  strat->T[j+1]=strat->T[j];
1235  strat->sevT[j+1]=strat->sevT[j];
1236  strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
1237  }
1238  strat->T[at+1]=p;
1239  strat->sevT[at+1] = sev;
1240  strat->R[p.i_r] = &(strat->T[at+1]);
1241  }
1242  }
1243 }

◆ updateL()

void updateL ( kStrategy  strat)

Definition at line 1364 of file kstd1.cc.

1365 {
1366  LObject p;
1367  int dL;
1368  int j=strat->Ll;
1369  loop
1370  {
1371  if (j<0) break;
1372  if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1373  {
1374  p=strat->L[strat->Ll];
1375  strat->L[strat->Ll]=strat->L[j];
1376  strat->L[j]=p;
1377  break;
1378  }
1379  j--;
1380  }
1381  if (j<0)
1382  {
1383  j=strat->Ll;
1384  loop
1385  {
1386  if (j<0) break;
1387  if (pNext(strat->L[j].p) == strat->tail)
1388  {
1389  if (rField_is_Ring(currRing))
1390  pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1391  else
1392  pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1393  strat->L[j].p = NULL;
1394  poly m1 = NULL, m2 = NULL;
1395  // check that spoly creation is ok
1396  while (strat->tailRing != currRing &&
1397  !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1398  {
1399  assume(m1 == NULL && m2 == NULL);
1400  // if not, change to a ring where exponents are at least
1401  // large enough
1402  kStratChangeTailRing(strat);
1403  }
1404  /* create the real one */
1405  ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1406  strat->tailRing, m1, m2, strat->R);
1407 
1408  strat->L[j].SetLmCurrRing();
1409  if (!strat->honey)
1410  strat->initEcart(&strat->L[j]);
1411  else
1412  strat->L[j].SetLength(strat->length_pLength);
1413 
1414  BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1415 
1416  if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
1417 
1418  if (pp)
1419  {
1420  p=strat->L[strat->Ll];
1421  strat->L[strat->Ll]=strat->L[j];
1422  strat->L[j]=p;
1423  break;
1424  }
1425  }
1426  j--;
1427  }
1428  }
1429 }

◆ updateLHC()

void updateLHC ( kStrategy  strat)

Definition at line 1435 of file kstd1.cc.

1436 {
1437 
1438  int i = 0;
1439  kTest_TS(strat);
1440  while (i <= strat->Ll)
1441  {
1442  if (pNext(strat->L[i].p) == strat->tail)
1443  {
1444  /*- deletes the int spoly and computes -*/
1445  if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
1446  {
1447  if (rField_is_Ring(currRing))
1448  pLmDelete(strat->L[i].p);
1449  else
1450  pLmFree(strat->L[i].p);
1451  strat->L[i].p = NULL;
1452  }
1453  else
1454  {
1455  if (rField_is_Ring(currRing))
1456  pLmDelete(strat->L[i].p);
1457  else
1458  pLmFree(strat->L[i].p);
1459  strat->L[i].p = NULL;
1460  poly m1 = NULL, m2 = NULL;
1461  // check that spoly creation is ok
1462  while (strat->tailRing != currRing &&
1463  !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
1464  {
1465  assume(m1 == NULL && m2 == NULL);
1466  // if not, change to a ring where exponents are at least
1467  // large enough
1468  kStratChangeTailRing(strat);
1469  }
1470  /* create the real one */
1471  ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
1472  strat->tailRing, m1, m2, strat->R);
1473  if (! strat->L[i].IsNull())
1474  {
1475  strat->L[i].SetLmCurrRing();
1476  strat->L[i].SetpFDeg();
1477  strat->L[i].ecart
1478  = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
1479  if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
1480  }
1481  }
1482  }
1483  else
1484  deleteHC(&(strat->L[i]), strat);
1485  if (strat->L[i].IsNull())
1486  deleteInL(strat->L,&strat->Ll,i,strat);
1487  else
1488  {
1489 #ifdef KDEBUG
1490  kTest_L(&(strat->L[i]), strat->tailRing, TRUE, i, strat->T, strat->tl);
1491 #endif
1492  i++;
1493  }
1494  }
1495  kTest_TS(strat);
1496 }

◆ updateT()

void updateT ( kStrategy  strat)

Definition at line 1502 of file kstd1.cc.

1503 {
1504  int i = 0;
1505  LObject p;
1506 
1507  while (i <= strat->tl)
1508  {
1509  p = strat->T[i];
1510  deleteHC(&p,strat, TRUE);
1511  /*- tries to cancel a unit: -*/
1512  cancelunit(&p);
1513  if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
1514  p.pCleardenom();
1515  if (p.p != strat->T[i].p)
1516  {
1517  strat->sevT[i] = pGetShortExpVector(p.p);
1518  p.SetpFDeg();
1519  }
1520  strat->T[i] = p;
1521  i++;
1522  }
1523 }

Variable Documentation

◆ kHomW

VAR intvec * kHomW

Definition at line 2394 of file kstd1.cc.

◆ kModW

VAR intvec* kModW

Definition at line 2394 of file kstd1.cc.

◆ kOptions

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

◆ validOpts

VAR BITSET validOpts

Definition at line 60 of file kstd1.cc.