My Project
Loading...
Searching...
No Matches
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, const ring r)
 
long kHomModDeg (poly p, const ring r)
 
static int kFindLuckyPrime (ideal F, ideal Q)
 
static poly kTryHC (ideal F, ideal Q)
 
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.
 
ideal kInterRedOld (ideal F, const ideal Q)
 
ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
 
ideal kInterRed (ideal F, const 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 exactly 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,
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:343
STATIC_VAR Poly * h
Definition janet.cc:971
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition kspoly.cc:187
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition kstd1.cc:977
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9137
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9236
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:924
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:799
class sLObject LObject
Definition kutil.h:58
#define NULL
Definition omList.c:12
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
#define TEST_OPT_DEBUG
Definition options.h:110
pShallowCopyDeleteProc pGetShallowCopyDeleteProc(ring, ring)
static int pLength(poly a)
Definition p_polys.h:190
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
#define rField_is_Ring(R)
Definition ring.h:490

◆ enterSMora()

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

Definition at line 1621 of file kstd1.cc.

1622{
1623 enterSBba(p, atS, strat, atR);
1624 #ifdef KDEBUG
1625 if (TEST_OPT_DEBUG)
1626 {
1627 Print("new s%d:",atS);
1628 p_wrp(p.p,currRing,strat->tailRing);
1629 PrintLn();
1630 }
1631 #endif
1632 HEckeTest(p.p,strat);
1633 if (strat->kAllAxis)
1634 {
1635 if (newHEdge(strat))
1636 {
1637 firstUpdate(strat);
1638 if (TEST_OPT_FINDET)
1639 return;
1640
1641 /*- cuts elements in L above noether and reorders L -*/
1642 updateLHC(strat);
1643 /*- reorders L with respect to posInL -*/
1644 reorderL(strat);
1645 }
1646 }
1647 else if ((strat->kNoether==NULL)
1648 && (TEST_OPT_FASTHC))
1649 {
1650 if (strat->posInLOldFlag)
1651 {
1652 missingAxis(&strat->lastAxis,strat);
1653 if (strat->lastAxis)
1654 {
1655 strat->posInLOld = strat->posInL;
1656 strat->posInLOldFlag = FALSE;
1657 strat->posInL = posInL10;
1658 strat->posInLDependsOnLength = TRUE;
1659 updateL(strat);
1660 reorderL(strat);
1661 }
1662 }
1663 else if (strat->lastAxis)
1664 updateL(strat);
1665 }
1666}
#define TRUE
Definition auxiliary.h:100
#define FALSE
Definition auxiliary.h:96
int p
Definition cfModGcd.cc:4086
char posInLOldFlag
Definition kutil.h:380
poly kNoether
Definition kutil.h:329
int lastAxis
Definition kutil.h:355
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:284
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition kutil.h:288
char kAllAxis
Definition kutil.h:374
char posInLDependsOnLength
Definition kutil.h:387
#define Print
Definition emacs.cc:80
void firstUpdate(kStrategy strat)
Definition kstd1.cc:1558
void updateLHC(kStrategy strat)
Definition kstd1.cc:1466
void missingAxis(int *last, kStrategy strat)
Definition kstd1.cc:1280
void reorderL(kStrategy strat)
Definition kstd1.cc:1223
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition kstd1.cc:1361
void updateL(kStrategy strat)
Definition kstd1.cc:1394
void HEckeTest(poly pp, kStrategy strat)
Definition kutil.cc:498
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8788
BOOLEAN newHEdge(kStrategy strat)
Definition kutil.cc:10401
#define TEST_OPT_FINDET
Definition options.h:113
#define TEST_OPT_FASTHC
Definition options.h:111
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 1674 of file kstd1.cc.

1675{
1676 enterSBba(p, atS, strat, atR);
1677 if ((!strat->kAllAxis) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1678 if (strat->kAllAxis)
1679 newHEdge(strat);
1680}

◆ firstUpdate()

void firstUpdate ( kStrategy strat)

Definition at line 1558 of file kstd1.cc.

1559{
1560 if (strat->update)
1561 {
1562 kTest_TS(strat);
1563 strat->update = (strat->tl == -1);
1564 if (TEST_OPT_WEIGHTM)
1565 {
1567 if (strat->tailRing != currRing)
1568 {
1569 strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1570 strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1571 }
1572 int i;
1573 for (i=strat->Ll; i>=0; i--)
1574 {
1575 strat->L[i].SetpFDeg();
1576 }
1577 for (i=strat->tl; i>=0; i--)
1578 {
1579 strat->T[i].SetpFDeg();
1580 }
1581 if (ecartWeights)
1582 {
1583 omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1585 }
1586 }
1587 if (TEST_OPT_FASTHC)
1588 {
1589 strat->posInL = strat->posInLOld;
1590 strat->lastAxis = 0;
1591 }
1592 if (TEST_OPT_FINDET)
1593 return;
1594
1595 strat->use_buckets = kMoraUseBucket(strat);
1596 updateT(strat);
1597
1599 {
1600 strat->posInT = posInT2;
1601 reorderT(strat);
1602 }
1603 }
1604 kTest_TS(strat);
1605}
void * ADDRESS
Definition auxiliary.h:119
int i
Definition cfEzgcd.cc:132
pFDegProc pOrigFDeg_TailRing
Definition kutil.h:298
int Ll
Definition kutil.h:351
TSet T
Definition kutil.h:326
int tl
Definition kutil.h:350
pFDegProc pOrigFDeg
Definition kutil.h:296
char use_buckets
Definition kutil.h:381
LSet L
Definition kutil.h:327
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:281
pLDegProc pOrigLDeg
Definition kutil.h:297
char update
Definition kutil.h:379
pLDegProc pOrigLDeg_TailRing
Definition kutil.h:299
void reorderT(kStrategy strat)
Definition kstd1.cc:1242
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition kstd1.cc:3885
void updateT(kStrategy strat)
Definition kstd1.cc:1532
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1071
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4930
#define omFreeSize(addr, size)
#define TEST_OPT_WEIGHTM
Definition options.h:123
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition p_polys.cc:3670
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:597
BOOLEAN rHasGlobalOrdering(const ring r)
Definition ring.h:766
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 1313 of file kstd1.cc.

1314{
1315 poly h;
1316 int i;
1317
1318 if (pNext(p) == strat->tail)
1319 return FALSE;
1320 pp_Test(p, currRing, strat->tailRing);
1321 if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
1322 {
1324 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
1325 if (i == last)
1326 {
1327 *length = 0;
1328 return TRUE;
1329 }
1330 *length = 1;
1331 h = pNext(p);
1332 while (h != NULL)
1333 {
1334 i = p_IsPurePower(h, strat->tailRing);
1335 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
1336 if (i==last) return TRUE;
1337 (*length)++;
1338 pIter(h);
1339 }
1340 }
1341 return FALSE;
1342}
int ak
Definition kutil.h:353
poly tail
Definition kutil.h:334
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:519
STATIC_VAR poly last
Definition hdegree.cc:1137
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:1227
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:163

◆ hasPurePower() [2/2]

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

Definition at line 1344 of file kstd1.cc.

1345{
1346 if (L->bucket != NULL)
1347 {
1348 poly p = L->GetP();
1349 return hasPurePower(p, last, length, strat);
1350 }
1351 else
1352 {
1353 return hasPurePower(L->p, last, length, strat);
1354 }
1355}
BOOLEAN hasPurePower(const poly p, int last, int *length, kStrategy strat)
Definition kstd1.cc:1313

◆ initBba()

void initBba ( kStrategy strat)

Definition at line 1682 of file kstd1.cc.

1683{
1684 /* setting global variables ------------------- */
1685 strat->enterS = enterSBba;
1686 strat->red = redHoney;
1687 if (strat->honey)
1688 strat->red = redHoney;
1689 else if (currRing->pLexOrder && !strat->homog)
1690 strat->red = redLazy;
1691 else
1692 {
1693 strat->LazyPass *=4;
1694 strat->red = redHomog;
1695 }
1697 {
1698 if (rField_is_Z(currRing))
1699 strat->red = redRing_Z;
1700 else
1701 strat->red = redRing;
1702 }
1703 if (TEST_OPT_IDLIFT
1704 && (!rIsNCRing(currRing))
1705 && (!rField_is_Ring(currRing)))
1706 strat->red=redLiftstd;
1707 if (currRing->pLexOrder && strat->honey)
1708 strat->initEcart = initEcartNormal;
1709 else
1710 strat->initEcart = initEcartBBA;
1711 if (strat->honey)
1713 else
1715// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1716// {
1717// //interred machen Aenderung
1718// strat->pOrigFDeg=pFDeg;
1719// strat->pOrigLDeg=pLDeg;
1720// //h=ggetid("ecart");
1721// //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1722// //{
1723// // ecartWeights=iv2array(IDINTVEC(h));
1724// //}
1725// //else
1726// {
1727// ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1728// /*uses automatic computation of the ecartWeights to set them*/
1729// kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1730// }
1731// pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1732// if (TEST_OPT_PROT)
1733// {
1734// for(i=1; i<=(currRing->N); i++)
1735// Print(" %d",ecartWeights[i]);
1736// PrintLn();
1737// mflush();
1738// }
1739// }
1740}
char honey
Definition kutil.h:375
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:287
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:286
void(* initEcart)(TObject *L)
Definition kutil.h:280
int LazyPass
Definition kutil.h:353
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:278
char homog
Definition kutil.h:370
int redLiftstd(LObject *h, kStrategy strat)
Definition kLiftstd.cc:167
int redRing_Z(LObject *h, kStrategy strat)
Definition kstd2.cc:724
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2114
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1154
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1909
int redRing(LObject *h, kStrategy strat)
Definition kstd2.cc:992
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1320
void initEcartNormal(TObject *h)
Definition kutil.cc:1298
void initEcartBBA(TObject *h)
Definition kutil.cc:1306
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1313
#define TEST_OPT_IDLIFT
Definition options.h:131
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:514
static BOOLEAN rIsNCRing(const ring r)
Definition ring.h:426

◆ initMora()

void initMora ( ideal F,
kStrategy strat )

Definition at line 1812 of file kstd1.cc.

1813{
1814 int i,j;
1815
1816 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1817 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1818 strat->enterS = enterSMora;
1819 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1820 strat->posInLOld = strat->posInL;
1821 strat->posInLOldFlag = TRUE;
1822 strat->initEcart = initEcartNormal;
1823 strat->kAllAxis = (currRing->ppNoether) != NULL;
1824 if ( strat->kAllAxis )
1825 {
1826 strat->kNoether = pCopy((currRing->ppNoether));
1827 if (TEST_OPT_PROT)
1828 {
1829 Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
1830 mflush();
1831 }
1832 }
1833 if (strat->homog)
1834 strat->red = redFirst; /*take the first possible in T*/
1835 else
1836 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1837 if (strat->kAllAxis)
1838 {
1839 HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
1840 }
1841 else
1842 {
1843 HCord = INT_MAX-3;/*- very large -*/
1844 }
1845
1847 {
1848 if (rField_is_Z(currRing))
1849 strat->red = redRiloc_Z;
1850 else
1851 strat->red = redRiloc;
1852 }
1853
1854 /*reads the ecartWeights used for Graebes method from the
1855 *intvec ecart and set ecartWeights
1856 */
1857 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1858 {
1859 //interred machen Aenderung
1860 strat->pOrigFDeg=currRing->pFDeg;
1861 strat->pOrigLDeg=currRing->pLDeg;
1862 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1863 /*uses automatic computation of the ecartWeights to set them*/
1865
1867 if (TEST_OPT_PROT)
1868 {
1869 for(i=1; i<=(currRing->N); i++)
1870 Print(" %d",ecartWeights[i]);
1871 PrintLn();
1872 mflush();
1873 }
1874 }
1875 kOptimizeLDeg(currRing->pLDeg, strat);
1876}
int BOOLEAN
Definition auxiliary.h:87
BOOLEAN * NotUsedAxis
Definition kutil.h:332
int j
Definition facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:795
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:386
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1621
int redRiloc_Z(LObject *h, kStrategy strat)
Definition kstd1.cc:567
VAR int HCord
Definition kutil.cc:244
#define omAlloc(size)
#define TEST_OPT_PROT
Definition options.h:105
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition p_polys.cc:3658
static long p_FDeg(const poly p, const ring r)
Definition p_polys.h:380
#define pCopy(p)
return a copy of the poly
Definition polys.h:185
#define mflush()
Definition reporter.h:58
#define IDELEMS(i)
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 1742 of file kstd1.cc.

1743{
1744 int i;
1745 //idhdl h;
1746 /* setting global variables ------------------- */
1747 strat->enterS = enterSSba;
1748 strat->red2 = redHoney;
1749 if (strat->honey)
1750 strat->red2 = redHoney;
1751 else if (currRing->pLexOrder && !strat->homog)
1752 strat->red2 = redLazy;
1753 else
1754 {
1755 strat->LazyPass *=4;
1756 strat->red2 = redHomog;
1757 }
1759 {
1761 {strat->red2 = redRiloc;}
1762 else
1763 {strat->red2 = redRing;}
1764 }
1765 if (currRing->pLexOrder && strat->honey)
1766 strat->initEcart = initEcartNormal;
1767 else
1768 strat->initEcart = initEcartBBA;
1769 if (strat->honey)
1771 else
1773 //strat->kIdeal = NULL;
1774 //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1775 //else strat->kIdeal->rtyp=MODUL_CMD;
1776 //strat->kIdeal->data=(void *)strat->Shdl;
1777 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1778 {
1779 //interred machen Aenderung
1780 strat->pOrigFDeg = currRing->pFDeg;
1781 strat->pOrigLDeg = currRing->pLDeg;
1782 //h=ggetid("ecart");
1783 //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1784 //{
1785 // ecartWeights=iv2array(IDINTVEC(h));
1786 //}
1787 //else
1788 {
1789 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1790 /*uses automatic computation of the ecartWeights to set them*/
1792 }
1794 if (TEST_OPT_PROT)
1795 {
1796 for(i=1; i<=(currRing->N); i++)
1797 Print(" %d",ecartWeights[i]);
1798 PrintLn();
1799 mflush();
1800 }
1801 }
1802 // for sig-safe reductions in signature-based
1803 // standard basis computations
1805 strat->red = redSigRing;
1806 else
1807 strat->red = redSig;
1808 //strat->sbaOrder = 1;
1809 strat->currIdx = 1;
1810}
int currIdx
Definition kutil.h:317
int(* red2)(LObject *L, kStrategy strat)
Definition kutil.h:279
int redSigRing(LObject *h, kStrategy strat)
Definition kstd2.cc:1540
int redSig(LObject *h, kStrategy strat)
Definition kstd2.cc:1373
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8911
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:767

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

3452{
3453 const ring save = currRing;
3454 if( currRing != _currRing ) rChangeCurrRing(_currRing);
3455 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3456 if( currRing != save ) rChangeCurrRing(save);
3457 return ret;
3458}
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3237
void rChangeCurrRing(ring r)
Definition polys.cc:15
#define Q
Definition sirandom.c:26

◆ kDebugPrint()

void kDebugPrint ( kStrategy strat)

Definition at line 11500 of file kutil.cc.

11501{
11502 printf("red: ");
11503 if (strat->red==redFirst) printf("redFirst\n");
11504 else if (strat->red==redHoney) printf("redHoney\n");
11505 else if (strat->red==redEcart) printf("redEcart\n");
11506 else if (strat->red==redHomog) printf("redHomog\n");
11507 else if (strat->red==redLazy) printf("redLazy\n");
11508 else if (strat->red==redLiftstd) printf("redLiftstd\n");
11509 else printf("%p\n",(void*)strat->red);
11510 printf("posInT: ");
11511 if (strat->posInT==posInT0) printf("posInT0\n");
11512 else if (strat->posInT==posInT1) printf("posInT1\n");
11513 else if (strat->posInT==posInT11) printf("posInT11\n");
11514 else if (strat->posInT==posInT110) printf("posInT110\n");
11515 else if (strat->posInT==posInT13) printf("posInT13\n");
11516 else if (strat->posInT==posInT15) printf("posInT15\n");
11517 else if (strat->posInT==posInT17) printf("posInT17\n");
11518 else if (strat->posInT==posInT17_c) printf("posInT17_c\n");
11519 else if (strat->posInT==posInT19) printf("posInT19\n");
11520 else if (strat->posInT==posInT2) printf("posInT2\n");
11521 else if (strat->posInT==posInT11Ring) printf("posInT11Ring\n");
11522 else if (strat->posInT==posInT110Ring) printf("posInT110Ring\n");
11523 else if (strat->posInT==posInT15Ring) printf("posInT15Ring\n");
11524 else if (strat->posInT==posInT17Ring) printf("posInT17Ring\n");
11525 else if (strat->posInT==posInT17_cRing) printf("posInT17_cRing\n");
11526#ifdef HAVE_MORE_POS_IN_T
11527 else if (strat->posInT==posInT_EcartFDegpLength) printf("posInT_EcartFDegpLength\n");
11528 else if (strat->posInT==posInT_FDegpLength) printf("posInT_FDegpLength\n");
11529 else if (strat->posInT==posInT_pLength) printf("posInT_pLength\n");
11530#endif
11531 else if (strat->posInT==posInT_EcartpLength) printf("posInT_EcartpLength\n");
11532 else printf("%p\n",(void*)strat->posInT);
11533 printf("posInL: ");
11534 if (strat->posInL==posInL0) printf("posInL0\n");
11535 else if (strat->posInL==posInL10) printf("posInL10\n");
11536 else if (strat->posInL==posInL11) printf("posInL11\n");
11537 else if (strat->posInL==posInL110) printf("posInL110\n");
11538 else if (strat->posInL==posInL13) printf("posInL13\n");
11539 else if (strat->posInL==posInL15) printf("posInL15\n");
11540 else if (strat->posInL==posInL17) printf("posInL17\n");
11541 else if (strat->posInL==posInL17_c) printf("posInL17_c\n");
11542 else if (strat->posInL==posInL0) printf("posInL0Ring\n");
11543 else if (strat->posInL==posInL11Ring) printf("posInL11Ring\n");
11544 else if (strat->posInL==posInL11Ringls) printf("posInL11Ringls\n");
11545 else if (strat->posInL==posInL110Ring) printf("posInL110Ring\n");
11546 else if (strat->posInL==posInL15Ring) printf("posInL15Ring\n");
11547 else if (strat->posInL==posInL17Ring) printf("posInL17Ring\n");
11548 else if (strat->posInL==posInL17_cRing) printf("posInL17_cRing\n");
11549 else if (strat->posInL==posInLSpecial) printf("posInLSpecial\n");
11550 else printf("%p\n",(void*)strat->posInL);
11551 printf("enterS: ");
11552 if (strat->enterS==enterSBba) printf("enterSBba\n");
11553 else if (strat->enterS==enterSMora) printf("enterSMora\n");
11554 else if (strat->enterS==enterSMoraNF) printf("enterSMoraNF\n");
11555 else printf("%p\n",(void*)strat->enterS);
11556 printf("initEcart: ");
11557 if (strat->initEcart==initEcartBBA) printf("initEcartBBA\n");
11558 else if (strat->initEcart==initEcartNormal) printf("initEcartNormal\n");
11559 else printf("%p\n",(void*)strat->initEcart);
11560 printf("initEcartPair: ");
11561 if (strat->initEcartPair==initEcartPairBba) printf("initEcartPairBba\n");
11562 else if (strat->initEcartPair==initEcartPairMora) printf("initEcartPairMora\n");
11563 else printf("%p\n",(void*)strat->initEcartPair);
11564 printf("homog=%d, LazyDegree=%d, LazyPass=%d, ak=%d,\n",
11565 strat->homog, strat->LazyDegree,strat->LazyPass, strat->ak);
11566 printf("honey=%d, sugarCrit=%d, Gebauer=%d, noTailReduction=%d, use_buckets=%d\n",
11567 strat->honey,strat->sugarCrit,strat->Gebauer,strat->noTailReduction,strat->use_buckets);
11568 printf("chainCrit: ");
11569 if (strat->chainCrit==chainCritNormal) printf("chainCritNormal\n");
11570 else if (strat->chainCrit==chainCritOpt_1) printf("chainCritOpt_1\n");
11571 else printf("%p\n",(void*)strat->chainCrit);
11572 printf("posInLDependsOnLength=%d\n",
11573 strat->posInLDependsOnLength);
11574 printf("%s\n",showOption());
11575 printf("LDeg: ");
11576 if (currRing->pLDeg==pLDeg0) printf("pLDeg0");
11577 else if (currRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11578 else if (currRing->pLDeg==pLDegb) printf("pLDegb");
11579 else if (currRing->pLDeg==pLDeg1) printf("pLDeg1");
11580 else if (currRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11581 else if (currRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11582 else if (currRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11583 else if (currRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11584 else if (currRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11585 else if (currRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11586 else if (currRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11587 else if (currRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11588 else printf("? (%lx)", (long)currRing->pLDeg);
11589 printf(" / ");
11590 if (strat->tailRing->pLDeg==pLDeg0) printf("pLDeg0");
11591 else if (strat->tailRing->pLDeg==pLDeg0c) printf("pLDeg0c");
11592 else if (strat->tailRing->pLDeg==pLDegb) printf("pLDegb");
11593 else if (strat->tailRing->pLDeg==pLDeg1) printf("pLDeg1");
11594 else if (strat->tailRing->pLDeg==pLDeg1c) printf("pLDeg1c");
11595 else if (strat->tailRing->pLDeg==pLDeg1_Deg) printf("pLDeg1_Deg");
11596 else if (strat->tailRing->pLDeg==pLDeg1c_Deg) printf("pLDeg1c_Deg");
11597 else if (strat->tailRing->pLDeg==pLDeg1_Totaldegree) printf("pLDeg1_Totaldegree");
11598 else if (strat->tailRing->pLDeg==pLDeg1c_Totaldegree) printf("pLDeg1c_Totaldegree");
11599 else if (strat->tailRing->pLDeg==pLDeg1_WFirstTotalDegree) printf("pLDeg1_WFirstTotalDegree");
11600 else if (strat->tailRing->pLDeg==pLDeg1c_WFirstTotalDegree) printf("pLDeg1c_WFirstTotalDegree");
11601 else if (strat->tailRing->pLDeg==maxdegreeWecart) printf("maxdegreeWecart");
11602 else printf("? (%lx)", (long)strat->tailRing->pLDeg);
11603 printf("\n");
11604 printf("currRing->pFDeg: ");
11605 if (currRing->pFDeg==p_Totaldegree) printf("p_Totaldegree");
11606 else if (currRing->pFDeg==p_WFirstTotalDegree) printf("pWFirstTotalDegree");
11607 else if (currRing->pFDeg==p_Deg) printf("p_Deg");
11608 else if (currRing->pFDeg==kHomModDeg) printf("kHomModDeg");
11609 else if (currRing->pFDeg==totaldegreeWecart) printf("totaldegreeWecart");
11610 else if (currRing->pFDeg==p_WTotaldegree) printf("p_WTotaldegree");
11611 else printf("? (%lx)", (long)currRing->pFDeg);
11612 printf("\n");
11613 printf(" syzring:%d, syzComp(strat):%d limit:%d\n",rIsSyzIndexRing(currRing),strat->syzComp,rGetCurrSyzLimit(currRing));
11615 printf(" degBound: %d\n", Kstd1_deg);
11616
11617 if( ecartWeights != NULL )
11618 {
11619 printf("ecartWeights: ");
11620 for (int i = rVar(currRing); i > 0; i--)
11621 printf("%hd ", ecartWeights[i]);
11622 printf("\n");
11624 }
11625
11626#ifndef SING_NDEBUG
11628#endif
11629}
int syzComp
Definition kutil.h:354
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:291
char noTailReduction
Definition kutil.h:376
char sugarCrit
Definition kutil.h:375
char Gebauer
Definition kutil.h:376
int LazyDegree
Definition kutil.h:353
long kHomModDeg(poly p, const ring r)
Definition kstd1.cc:2419
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1674
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:52
int posInL17Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6301
int posInL17_cRing(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6414
int posInL110(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6060
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5283
int posInL11Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5846
int posInT11(const TSet set, const int length, LObject &p)
Definition kutil.cc:4958
int posInT1(const TSet set, const int length, LObject &p)
Definition kutil.cc:4901
int posInT110Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5076
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:5151
int posInT0(const TSet, const int length, LObject &)
Definition kutil.cc:4890
int posInL13(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6147
int posInL110Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6101
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11466
int posInT13(const TSet set, const int length, LObject &p)
Definition kutil.cc:5122
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5616
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3450
int posInT11Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:4994
int posInL15(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6182
int posInT17_c(const TSet set, const int length, LObject &p)
Definition kutil.cc:5389
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11375
int posInT15(const TSet set, const int length, LObject &p)
Definition kutil.cc:5189
int posInLSpecial(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5572
int posInL11Ringls(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5914
int posInL17(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6257
int posInT110(const TSet set, const int length, LObject &p)
Definition kutil.cc:5034
int posInL15Ring(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6217
int posInT19(const TSet set, const int length, LObject &p)
Definition kutil.cc:5515
int posInT15Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5243
int posInT17Ring(const TSet set, const int length, LObject &p)
Definition kutil.cc:5344
int posInT17_cRing(const TSet set, const int length, LObject &p)
Definition kutil.cc:5450
int posInL17_c(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:6350
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11429
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3209
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5804
char * showOption()
Definition misc_ip.cc:711
#define assume(x)
Definition mod2.h:387
#define TEST_OPT_DEGBOUND
Definition options.h:115
long pLDegb(poly p, int *l, const ring r)
Definition p_polys.cc:812
long pLDeg1_Totaldegree(poly p, int *l, const ring r)
Definition p_polys.cc:976
long p_WFirstTotalDegree(poly p, const ring r)
Definition p_polys.cc:595
long pLDeg1_WFirstTotalDegree(poly p, int *l, const ring r)
Definition p_polys.cc:1039
long pLDeg1c_WFirstTotalDegree(poly p, int *l, const ring r)
Definition p_polys.cc:1069
long pLDeg1c_Deg(poly p, int *l, const ring r)
Definition p_polys.cc:942
long pLDeg1(poly p, int *l, const ring r)
Definition p_polys.cc:842
long pLDeg1_Deg(poly p, int *l, const ring r)
Definition p_polys.cc:911
long p_WTotaldegree(poly p, const ring r)
Definition p_polys.cc:612
long pLDeg1c(poly p, int *l, const ring r)
Definition p_polys.cc:878
long pLDeg1c_Totaldegree(poly p, int *l, const ring r)
Definition p_polys.cc:1006
long pLDeg0c(poly p, int *l, const ring r)
Definition p_polys.cc:771
long pLDeg0(poly p, int *l, const ring r)
Definition p_polys.cc:740
long p_Deg(poly a, const ring r)
Definition p_polys.cc:586
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1521
void rDebugPrint(const ring r)
Definition ring.cc:4153
static int rGetCurrSyzLimit(const ring r)
Definition ring.h:728
static BOOLEAN rIsSyzIndexRing(const ring r)
Definition ring.h:725

◆ kFindLuckyPrime()

static int kFindLuckyPrime ( ideal F,
ideal Q )
static

Definition at line 2431 of file kstd1.cc.

2432{
2433 int prim=32003;
2434 // assume coeff are in Q
2435 return prim;
2436}

◆ kHomModDeg()

long kHomModDeg ( poly p,
const ring r )

Definition at line 2419 of file kstd1.cc.

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

Definition at line 3809 of file kstd1.cc.

3810{
3811#ifdef HAVE_PLURAL
3812 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3813#endif
3816 )
3817 return kInterRedOld(F,Q);
3818
3819 //return kInterRedOld(F,Q);
3820
3821 BITSET save1;
3822 SI_SAVE_OPT1(save1);
3823 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3825 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3826 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3827 //extern char * showOption() ;
3828 //Print("%s\n",showOption());
3829
3830 int need_retry;
3831 int counter=3;
3832 ideal res, res1;
3833 int elems=0;
3834 ideal null=NULL;
3835 if ((Q==NULL) || (!TEST_OPT_REDSB))
3836 {
3837 elems=idElem(F);
3838 res=kInterRedBba(F,Q,need_retry);
3839 }
3840 else
3841 {
3842 ideal FF=idSimpleAdd(F,Q);
3843 res=kInterRedBba(FF,NULL,need_retry);
3844 idDelete(&FF);
3845 null=idInit(1,1);
3846 if (need_retry)
3847 res1=kNF(null,Q,res,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
3848 else
3849 res1=kNF(null,Q,res);
3850 idDelete(&res);
3851 res=res1;
3852 need_retry=1;
3853 }
3854 if (idElem(res)<=1) need_retry=0;
3855 while (need_retry && (counter>0))
3856 {
3857 #ifdef KDEBUG
3858 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3859 #endif
3860 res1=kInterRedBba(res,Q,need_retry);
3861 int new_elems=idElem(res1);
3862 counter -= (new_elems >= elems);
3863 elems = new_elems;
3864 idDelete(&res);
3865 if (idElem(res1)<=1) need_retry=0;
3866 if ((Q!=NULL) && (TEST_OPT_REDSB))
3867 {
3868 if (need_retry)
3869 res=kNF(null,Q,res1,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
3870 else
3871 res=kNF(null,Q,res1);
3872 idDelete(&res1);
3873 }
3874 else
3875 res = res1;
3876 if (idElem(res)<=1) need_retry=0;
3877 }
3878 if (null!=NULL) idDelete(&null);
3879 SI_RESTORE_OPT1(save1);
3881 return res;
3882}
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 kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition kstd1.cc:3558
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3464
#define KSTD_NF_LAZY
Definition kstd1.h:17
#define KSTD_NF_NONORM
Definition kstd1.h:21
VAR unsigned si_opt_1
Definition options.c:5
#define SI_SAVE_OPT1(A)
Definition options.h:21
#define SI_RESTORE_OPT1(A)
Definition options.h:24
#define OPT_REDTHROUGH
Definition options.h:83
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_REDSB
Definition options.h:106
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:405
static BOOLEAN rField_is_numeric(const ring r)
Definition ring.h:520
ideal idInit(int idsize, int rank)
initialise an ideal / module
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static int idElem(const ideal F)
number of non-zero polys in F
#define BITSET
Definition structs.h:16

◆ kInterRedBba()

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

Definition at line 3558 of file kstd1.cc.

3559{
3560 need_retry=0;
3561 int red_result = 1;
3562 int olddeg,reduc;
3563 BOOLEAN withT = FALSE;
3564 // BOOLEAN toReset=FALSE;
3565 kStrategy strat=new skStrategy;
3566 tHomog h;
3567
3569 strat->LazyPass=20;
3570 else
3571 strat->LazyPass=2;
3572 strat->LazyDegree = 1;
3573 strat->ak = id_RankFreeModule(F,currRing);
3574 strat->syzComp = strat->ak;
3575 strat->kModW=kModW=NULL;
3576 strat->kHomW=kHomW=NULL;
3577 if (strat->ak == 0)
3578 {
3579 h = (tHomog)idHomIdeal(F,Q);
3580 }
3581 else if (!TEST_OPT_DEGBOUND)
3582 {
3583 h = (tHomog)idHomIdeal(F,Q);
3584 }
3585 else
3586 h = isNotHomog;
3587 if (h==isHomog)
3588 {
3589 strat->LazyPass*=2;
3590 }
3591 strat->homog=h;
3592#ifdef KDEBUG
3593 idTest(F);
3594#endif
3595
3596 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3598 initBuchMoraPosRing(strat);
3599 else
3600 initBuchMoraPos(strat);
3601 initBba(strat);
3602 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3603 strat->posInL=posInL0; /* ord according pComp */
3604
3605 /*Shdl=*/initBuchMora(F, Q, strat);
3606 reduc = olddeg = 0;
3607
3608#ifndef NO_BUCKETS
3610 strat->use_buckets = 1;
3611#endif
3612
3613 // redtailBBa against T for inhomogeneous input
3614 if (!TEST_OPT_OLDSTD)
3615 withT = ! strat->homog;
3616
3617 // strat->posInT = posInT_pLength;
3618 kTest_TS(strat);
3619
3620#ifdef HAVE_TAIL_RING
3622#endif
3623
3624 /* compute------------------------------------------------------- */
3625 while (strat->Ll >= 0)
3626 {
3627 #ifdef KDEBUG
3628 if (TEST_OPT_DEBUG) messageSets(strat);
3629 #endif
3630 if (strat->Ll== 0) strat->interpt=TRUE;
3631 /* picks the last element from the lazyset L */
3632 strat->P = strat->L[strat->Ll];
3633 strat->Ll--;
3634
3635 if (strat->P.p1 == NULL)
3636 {
3637 // for input polys, prepare reduction
3638 strat->P.PrepareRed(strat->use_buckets);
3639 }
3640
3641 if (strat->P.p == NULL && strat->P.t_p == NULL)
3642 {
3643 red_result = 0;
3644 }
3645 else
3646 {
3647 if (TEST_OPT_PROT)
3648 message(strat->P.pFDeg(),
3649 &olddeg,&reduc,strat, red_result);
3650
3651 /* reduction of the element chosen from L */
3652 red_result = strat->red(&strat->P,strat);
3653 }
3654
3655 // reduction to non-zero new poly
3656 if (red_result == 1)
3657 {
3658 /* statistic */
3659 if (TEST_OPT_PROT) PrintS("s");
3660
3661 // get the polynomial (canonicalize bucket, make sure P.p is set)
3662 strat->P.GetP(strat->lmBin);
3663
3664 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3665
3666 // reduce the tail and normalize poly
3667 // in the ring case we cannot expect LC(f) = 1,
3668 // therefore we call pCleardenom instead of pNorm
3670 {
3671 strat->P.pCleardenom();
3672 }
3673 else
3674 {
3675 strat->P.pNorm();
3676 }
3677
3678#ifdef KDEBUG
3679 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3680#endif
3681
3682 // enter into S, L, and T
3683 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3684 {
3685 enterT(strat->P, strat);
3686 // posInS only depends on the leading term
3687 strat->enterS(strat->P, pos, strat, strat->tl);
3688
3689 if (pos<strat->sl)
3690 {
3691 need_retry++;
3692 // move all "larger" elements fromS to L
3693 // remove them from T
3694 int ii=pos+1;
3695 for(;ii<=strat->sl;ii++)
3696 {
3697 LObject h;
3698 h.Clear();
3699 h.tailRing=strat->tailRing;
3700 h.p=strat->S[ii]; strat->S[ii]=NULL;
3701 strat->initEcart(&h);
3702 h.sev=strat->sevS[ii];
3703 int jj=strat->tl;
3704 while (jj>=0)
3705 {
3706 if (strat->T[jj].p==h.p)
3707 {
3708 strat->T[jj].p=NULL;
3709 if (jj<strat->tl)
3710 {
3711 memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3712 (strat->tl-jj)*sizeof(strat->T[jj]));
3713 memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3714 (strat->tl-jj)*sizeof(strat->sevT[jj]));
3715 }
3716 strat->tl--;
3717 break;
3718 }
3719 jj--;
3720 }
3721 int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3722 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3723 #ifdef KDEBUG
3724 if (TEST_OPT_DEBUG)
3725 {
3726 Print("move S[%d] -> L[%d]: ",ii,pos);
3727 p_wrp(h.p,currRing, strat->tailRing);
3728 PrintLn();
3729 }
3730 #endif
3731 }
3732 if (strat->fromQ!=NULL)
3733 {
3734 for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3735 }
3736 strat->sl=pos;
3737 }
3738 }
3739 else
3740 {
3741 // clean P
3742 }
3743 kDeleteLcm(&strat->P);
3744 }
3745
3746#ifdef KDEBUG
3747 if (TEST_OPT_DEBUG)
3748 {
3749 messageSets(strat);
3750 }
3751 strat->P.Clear();
3752#endif
3753 //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3754 }
3755#ifdef KDEBUG
3756 //if (TEST_OPT_DEBUG) messageSets(strat);
3757#endif
3758 /* complete reduction of the standard basis--------- */
3759
3760 if((need_retry<=0) && (TEST_OPT_REDSB))
3761 {
3762 completeReduce(strat);
3763 if (strat->completeReduce_retry)
3764 {
3765 // completeReduce needed larger exponents, retry
3766 // hopefully: kStratChangeTailRing already provided a larger tailRing
3767 // (otherwise: it will fail again)
3769 completeReduce(strat);
3770 if (strat->completeReduce_retry)
3771 {
3772#ifdef HAVE_TAIL_RING
3773 if(currRing->bitmask>strat->tailRing->bitmask)
3774 {
3775 // retry without T
3777 cleanT(strat);strat->tailRing=currRing;
3778 int i;
3779 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3780 completeReduce(strat);
3781 }
3782 if (strat->completeReduce_retry)
3783#endif
3784 Werror("exponent bound is %ld",currRing->bitmask);
3785 }
3786 }
3787 }
3788 else if (TEST_OPT_PROT) PrintLn();
3789
3790
3791 /* release temp data-------------------------------- */
3792 exitBuchMora(strat);
3793// if (TEST_OPT_WEIGHTM)
3794// {
3795// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3796// if (ecartWeights)
3797// {
3798// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3799// ecartWeights=NULL;
3800// }
3801// }
3802 //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3803 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3804 ideal res=strat->Shdl;
3805 strat->Shdl=NULL;
3806 delete strat;
3807 return res;
3808}
intvec * kModW
Definition kutil.h:335
int * S_2_R
Definition kutil.h:342
omBin lmBin
Definition kutil.h:344
polyset S
Definition kutil.h:306
unsigned long * sevT
Definition kutil.h:325
intvec * kHomW
Definition kutil.h:336
ideal Shdl
Definition kutil.h:303
intset fromQ
Definition kutil.h:321
char interpt
Definition kutil.h:369
char completeReduce_retry
Definition kutil.h:401
LObject P
Definition kutil.h:302
int Lmax
Definition kutil.h:351
int sl
Definition kutil.h:348
unsigned long * sevS
Definition kutil.h:322
#define idTest(id)
Definition ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition ideals.h:91
void initBba(kStrategy strat)
Definition kstd1.cc:1682
VAR intvec * kHomW
Definition kstd1.cc:2407
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7465
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9745
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1274
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9574
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9830
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4668
void cleanT(kStrategy strat)
Definition kutil.cc:563
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10073
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11053
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9429
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10279
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9659
void messageSets(kStrategy strat)
Definition kutil.cc:7538
static void kDeleteLcm(LObject *P)
Definition kutil.h:869
#define TEST_OPT_OLDSTD
Definition options.h:125
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
#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:35
@ isHomog
Definition structs.h:37
@ isNotHomog
Definition structs.h:36
skStrategy * kStrategy
Definition structs.h:58

◆ kInterRedOld()

ideal kInterRedOld ( ideal F,
const ideal Q )

Definition at line 3464 of file kstd1.cc.

3465{
3466 int j;
3467 kStrategy strat = new skStrategy;
3468
3469 ideal tempF = F;
3470 ideal tempQ = Q;
3471
3472#ifdef HAVE_PLURAL
3473 if(rIsSCA(currRing))
3474 {
3475 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3476 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3477 tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3478
3479 // this should be done on the upper level!!! :
3480 // tempQ = SCAQuotient(currRing);
3481
3482 if(Q == currRing->qideal)
3483 tempQ = SCAQuotient(currRing);
3484 }
3485#endif
3486
3487// if (TEST_OPT_PROT)
3488// {
3489// writeTime("start InterRed:");
3490// mflush();
3491// }
3492 //strat->syzComp = 0;
3493 strat->kAllAxis = (currRing->ppNoether) != NULL;
3494 strat->kNoether=pCopy((currRing->ppNoether));
3495 strat->ak = id_RankFreeModule(tempF,currRing);
3496 initBuchMoraCrit(strat);
3497 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3498 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3499 strat->enterS = enterSBba;
3500 strat->posInT = posInT17;
3501 strat->initEcart = initEcartNormal;
3502 strat->sl = -1;
3503 strat->tl = -1;
3504 strat->tmax = setmaxT;
3505 strat->T = initT();
3506 strat->R = initR();
3507 strat->sevT = initsevT();
3509 initS(tempF, tempQ, strat);
3510 if (TEST_OPT_REDSB)
3511 strat->noTailReduction=FALSE;
3512 updateS(TRUE,strat);
3514 completeReduce(strat);
3515 //else if (TEST_OPT_PROT) PrintLn();
3516 cleanT(strat);
3517 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3518 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3519 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3520 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3521 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3522 omfree(strat->sevT);
3523 omfree(strat->S_2_R);
3524 omfree(strat->R);
3525
3526 if (strat->fromQ)
3527 {
3528 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3529 {
3530 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3531 }
3532 omFree((ADDRESS)strat->fromQ);
3533 strat->fromQ=NULL;
3534 }
3535// if (TEST_OPT_PROT)
3536// {
3537// writeTime("end Interred:");
3538// mflush();
3539// }
3540 ideal shdl=strat->Shdl;
3541 idSkipZeroes(shdl);
3542 if (strat->fromQ)
3543 {
3544 omfree(strat->fromQ);
3545 strat->fromQ=NULL;
3546 ideal res=kInterRed(shdl,NULL);
3547 idDelete(&shdl);
3548 shdl=res;
3549 }
3550 delete(strat);
3551#ifdef HAVE_PLURAL
3552 if( tempF != F )
3553 id_Delete( &tempF, currRing);
3554#endif
3555 return shdl;
3556}
intset ecartS
Definition kutil.h:309
TObject ** R
Definition kutil.h:340
int tmax
Definition kutil.h:350
KINLINE TSet initT()
Definition kInline.h:84
KINLINE TObject ** initR()
Definition kInline.h:95
KINLINE unsigned long * initsevT()
Definition kInline.h:100
ideal kInterRed(ideal F, const ideal Q)
Definition kstd1.cc:3809
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7588
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8553
#define setmaxT
Definition kutil.h:33
class sTObject TObject
Definition kutil.h:57
static bool rIsSCA(const ring r)
Definition nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition sca.cc:1518
#define omfree(addr)
#define omFree(addr)
#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 3086 of file kstd1.cc.

3088{
3089 if(idIs0(F))
3090 {
3091 M=idInit(1,F->rank);
3092 return idInit(1,F->rank);
3093 }
3095 {
3096 ideal sb;
3097 sb = kStd(F, Q, h, w, hilb);
3098 idSkipZeroes(sb);
3099 if(IDELEMS(sb) <= IDELEMS(F))
3100 {
3101 M = idCopy(sb);
3102 idSkipZeroes(M);
3103 return(sb);
3104 }
3105 else
3106 {
3107 M = idCopy(F);
3108 idSkipZeroes(M);
3109 return(sb);
3110 }
3111 }
3112 ideal r=NULL;
3113 int Kstd1_OldDeg = Kstd1_deg,i;
3114 intvec* temp_w=NULL;
3115 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3116 BOOLEAN delete_w=(w==NULL);
3117 BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3118 kStrategy strat=new skStrategy;
3119
3121 strat->syzComp = syzComp;
3123 strat->LazyPass=20;
3124 else
3125 strat->LazyPass=2;
3126 strat->LazyDegree = 1;
3127 strat->minim=(reduced % 2)+1;
3128 strat->ak = id_RankFreeModule(F,currRing);
3129 if (delete_w)
3130 {
3131 temp_w=new intvec((strat->ak)+1);
3132 w = &temp_w;
3133 }
3134 if (h==testHomog)
3135 {
3136 if (strat->ak == 0)
3137 {
3138 h = (tHomog)idHomIdeal(F,Q);
3139 w=NULL;
3140 }
3141 else
3142 {
3143 h = (tHomog)idHomModule(F,Q,w);
3144 }
3145 }
3146 if (h==isHomog)
3147 {
3148 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3149 {
3150 kModW = *w;
3151 strat->kModW = *w;
3152 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3153 strat->pOrigFDeg = currRing->pFDeg;
3154 strat->pOrigLDeg = currRing->pLDeg;
3156
3157 toReset = TRUE;
3158 if (reduced>1)
3159 {
3160 Kstd1_OldDeg=Kstd1_deg;
3161 Kstd1_deg = -1;
3162 for (i=IDELEMS(F)-1;i>=0;i--)
3163 {
3164 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3165 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3166 }
3167 }
3168 }
3169 currRing->pLexOrder = TRUE;
3170 strat->LazyPass*=2;
3171 }
3172 strat->homog=h;
3173 ideal SB=NULL;
3175 {
3176 r=idMinBase(F,&SB); // SB and M via minbase
3177 strat->M=r;
3178 r=SB;
3179 }
3180 else
3181 {
3182 if (w!=NULL)
3183 r=bba(F,Q,*w,hilb,strat);
3184 else
3185 r=bba(F,Q,NULL,hilb,strat);
3186 }
3187#ifdef KDEBUG
3188 {
3189 int i;
3190 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3191 }
3192#endif
3193 idSkipZeroes(r);
3194 if (toReset)
3195 {
3197 kModW = NULL;
3198 }
3199 currRing->pLexOrder = b;
3200 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3201 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3202 {
3203 M=idInit(1,F->rank);
3204 M->m[0]=pOne();
3205 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3206 if (strat->M!=NULL) idDelete(&strat->M);
3207 }
3208 else if (strat->M==NULL)
3209 {
3210 M=idInit(1,F->rank);
3211 WarnS("no minimal generating set computed");
3212 }
3213 else
3214 {
3215 idSkipZeroes(strat->M);
3216 M=strat->M;
3217 strat->M=NULL;
3218 }
3219 delete(strat);
3220 if (reduced>2)
3221 {
3222 Kstd1_deg=Kstd1_OldDeg;
3223 if (!oldDegBound)
3225 }
3226 else
3227 {
3228 if (IDELEMS(M)>IDELEMS(r))
3229 {
3230 idDelete(&M);
3231 M=idCopy(r);
3232 }
3233 }
3234 return r;
3235}
CanonicalForm b
Definition cfModGcd.cc:4111
int minim
Definition kutil.h:357
ideal M
Definition kutil.h:305
#define WarnS
Definition emacs.cc:78
const CanonicalForm & w
Definition facAbsFact.cc:51
ideal idMinBase(ideal h1, ideal *SB)
Definition ideals.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
long kModDeg(poly p, const ring r)
Definition kstd1.cc:2409
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:2484
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2622
#define TEST_OPT_RETURN_SB
Definition options.h:114
#define OPT_DEGBOUND
Definition options.h:91
#define pTest(p)
Definition polys.h:414
#define pIsConstant(p)
like above, except that Comp must be 0
Definition polys.h:238
#define pOne()
Definition polys.h:315
#define M
Definition sirandom.c:25
@ testHomog
Definition structs.h:38

◆ kModDeg()

long kModDeg ( poly p,
const ring r )

Definition at line 2409 of file kstd1.cc.

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

◆ kMoraUseBucket()

static BOOLEAN kMoraUseBucket ( kStrategy strat)
static

Definition at line 3885 of file kstd1.cc.

3886{
3887#ifdef MORA_USE_BUCKETS
3889 return FALSE;
3890 if ((strat->red == redFirst)
3891 ||((strat->red == redEcart)&&(strat->kNoether!=NULL)))
3892 {
3893#ifdef NO_LDEG
3894 if (strat->syzComp==0)
3895 return TRUE;
3896#else
3897 if ((strat->homog || strat->honey) && (strat->syzComp==0))
3898 return TRUE;
3899#endif
3900 }
3901 else
3902 {
3903 assume(strat->red == redEcart || strat->red == redRiloc || strat->red == redRiloc_Z);
3904 if (strat->honey && (strat->syzComp==0))
3905 return TRUE;
3906 }
3907#endif
3908 return FALSE;
3909}

◆ kNF() [1/2]

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

Definition at line 3335 of file kstd1.cc.

3336{
3337 ideal res;
3338 if (TEST_OPT_PROT)
3339 {
3340 Print("(S:%d)",IDELEMS(p));mflush();
3341 }
3342 if (idIs0(p))
3343 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3344
3345 ideal pp = p;
3346#ifdef HAVE_PLURAL
3347 if(rIsSCA(currRing))
3348 {
3349 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3350 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3351 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3352
3353 if(Q == currRing->qideal)
3355 }
3356#endif
3357
3358 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3359
3360 if ((idIs0(F))&&(Q==NULL))
3361 {
3362#ifdef HAVE_PLURAL
3363 if(p != pp)
3364 return pp;
3365#endif
3366 return idCopy(p); /*F+Q=0*/
3367 }
3368
3369 kStrategy strat=new skStrategy;
3370 strat->syzComp = syzComp;
3372 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3373 {
3374 strat->ak = si_max(strat->ak,(int)F->rank);
3375 }
3376
3378 {
3379#ifdef HAVE_SHIFTBBA
3380 if (currRing->isLPring)
3381 {
3382 WerrorS("No local ordering possible for shift algebra");
3383 return(NULL);
3384 }
3385#endif
3386 res=kNF1(F,Q,pp,strat,lazyReduce);
3387 }
3388 else
3389 res=kNF2(F,Q,pp,strat,lazyReduce);
3390 delete(strat);
3391
3392#ifdef HAVE_PLURAL
3393 if(pp != p)
3395#endif
3396
3397 return res;
3398}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition cf_gcd.cc:676
void WerrorS(const char *s)
Definition feFopen.cc:24
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd1.cc:2117
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3942

◆ kNF() [2/2]

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

Definition at line 3237 of file kstd1.cc.

3238{
3239 if (p==NULL)
3240 return NULL;
3241
3242 poly pp = p;
3243
3244#ifdef HAVE_PLURAL
3245 if(rIsSCA(currRing))
3246 {
3247 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3248 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3249 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3250
3251 if(Q == currRing->qideal)
3253 }
3254#endif
3255 if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3256
3257 if ((idIs0(F))&&(Q==NULL))
3258 {
3259#ifdef HAVE_PLURAL
3260 if(p != pp)
3261 return pp;
3262#endif
3263 return pCopy(p); /*F+Q=0*/
3264 }
3265
3266 kStrategy strat=new skStrategy;
3267 strat->syzComp = syzComp;
3269 poly res;
3270
3272 {
3273#ifdef HAVE_SHIFTBBA
3274 if (currRing->isLPring)
3275 {
3276 WerrorS("No local ordering possible for shift algebra");
3277 return(NULL);
3278 }
3279#endif
3280 res=kNF1(F,Q,pp,strat,lazyReduce);
3281 }
3282 else
3283 res=kNF2(F,Q,pp,strat,lazyReduce);
3284 delete(strat);
3285
3286#ifdef HAVE_PLURAL
3287 if(pp != p)
3288 p_Delete(&pp, currRing);
3289#endif
3290 return res;
3291}
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition sca.cc:1463
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
#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 2258 of file kstd1.cc.

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

◆ kNF1() [2/2]

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

Definition at line 2117 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 3400 of file kstd1.cc.

3401{
3402 ideal res;
3403 if (TEST_OPT_PROT)
3404 {
3405 Print("(S:%d)",IDELEMS(p));mflush();
3406 }
3407 if (idIs0(p))
3408 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3409
3410 ideal pp = p;
3411#ifdef HAVE_PLURAL
3412 if(rIsSCA(currRing))
3413 {
3414 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3415 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3416 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3417
3418 if(Q == currRing->qideal)
3420 }
3421#endif
3422
3423 if ((idIs0(F))&&(Q==NULL))
3424 {
3425#ifdef HAVE_PLURAL
3426 if(p != pp)
3427 return pp;
3428#endif
3429 return idCopy(p); /*F+Q=0*/
3430 }
3431
3432 kStrategy strat=new skStrategy;
3433 strat->syzComp = syzComp;
3435 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3436 {
3437 strat->ak = si_max(strat->ak,(int)F->rank);
3438 }
3439
3440 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3441 delete(strat);
3442
3443#ifdef HAVE_PLURAL
3444 if(pp != p)
3446#endif
3447
3448 return res;
3449}
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:4028

◆ kNFBound() [2/2]

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

Definition at line 3293 of file kstd1.cc.

3294{
3295 if (p==NULL)
3296 return NULL;
3297
3298 poly pp = p;
3299
3300#ifdef HAVE_PLURAL
3301 if(rIsSCA(currRing))
3302 {
3303 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3304 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3305 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3306
3307 if(Q == currRing->qideal)
3309 }
3310#endif
3311
3312 if ((idIs0(F))&&(Q==NULL))
3313 {
3314#ifdef HAVE_PLURAL
3315 if(p != pp)
3316 return pp;
3317#endif
3318 return pCopy(p); /*F+Q=0*/
3319 }
3320
3321 kStrategy strat=new skStrategy;
3322 strat->syzComp = syzComp;
3324 poly res;
3325 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3326 delete(strat);
3327
3328#ifdef HAVE_PLURAL
3329 if(pp != p)
3330 p_Delete(&pp, currRing);
3331#endif
3332 return res;
3333}

◆ 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:383
char length_pLength
Definition kutil.h:385

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

2690{
2691 if(idIs0(F))
2692 return idInit(1,F->rank);
2694 {
2695 ideal r;
2696 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2697 BOOLEAN delete_w=(w==NULL);
2698 kStrategy strat=new skStrategy;
2699 strat->sbaOrder = sbaOrder;
2700 if (arri!=0)
2701 {
2702 strat->rewCrit1 = arriRewDummy;
2703 strat->rewCrit2 = arriRewCriterion;
2705 }
2706 else
2707 {
2711 }
2712
2714 strat->syzComp = syzComp;
2715 if (TEST_OPT_SB_1)
2716 //if(!rField_is_Ring(currRing)) // always true here
2717 strat->newIdeal = newIdeal;
2719 strat->LazyPass=20;
2720 else
2721 strat->LazyPass=2;
2722 strat->LazyDegree = 1;
2726 strat->ak = id_RankFreeModule(F,currRing);
2727 strat->kModW=kModW=NULL;
2728 strat->kHomW=kHomW=NULL;
2729 if (vw != NULL)
2730 {
2731 currRing->pLexOrder=FALSE;
2732 strat->kHomW=kHomW=vw;
2733 strat->pOrigFDeg = currRing->pFDeg;
2734 strat->pOrigLDeg = currRing->pLDeg;
2736 toReset = TRUE;
2737 }
2738 if (h==testHomog)
2739 {
2740 if (strat->ak == 0)
2741 {
2742 h = (tHomog)idHomIdeal(F,Q);
2743 w=NULL;
2744 }
2745 else if (!TEST_OPT_DEGBOUND)
2746 {
2747 if (w!=NULL)
2748 h = (tHomog)idHomModule(F,Q,w);
2749 else
2750 h = (tHomog)idHomIdeal(F,Q);
2751 }
2752 }
2753 currRing->pLexOrder=b;
2754 if (h==isHomog)
2755 {
2756 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2757 {
2758 strat->kModW = kModW = *w;
2759 if (vw == NULL)
2760 {
2761 strat->pOrigFDeg = currRing->pFDeg;
2762 strat->pOrigLDeg = currRing->pLDeg;
2764 toReset = TRUE;
2765 }
2766 }
2767 currRing->pLexOrder = TRUE;
2768 if (hilb==NULL) strat->LazyPass*=2;
2769 }
2770 strat->homog=h;
2771 #ifdef KDEBUG
2772 idTest(F);
2773 if(Q != NULL)
2774 idTest(Q);
2775 #endif
2776 #ifdef HAVE_PLURAL
2778 {
2779 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2780 strat->no_prod_crit = ! bIsSCA;
2781 if (w!=NULL)
2782 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2783 else
2784 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2785 }
2786 else
2787 #endif
2788 {
2790 {
2791 if (w!=NULL)
2792 r=mora(F,Q,*w,hilb,strat);
2793 else
2794 r=mora(F,Q,NULL,hilb,strat);
2795 }
2796 else
2797 {
2798 strat->sigdrop = FALSE;
2799 if (w!=NULL)
2800 r=sba(F,Q,*w,hilb,strat);
2801 else
2802 r=sba(F,Q,NULL,hilb,strat);
2803 }
2804 }
2805 #ifdef KDEBUG
2806 idTest(r);
2807 #endif
2808 if (toReset)
2809 {
2810 kModW = NULL;
2812 }
2813 currRing->pLexOrder = b;
2814 //Print("%d reductions canceled \n",strat->cel);
2815 //delete(strat);
2816 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2817 return r;
2818 }
2819 else
2820 {
2821 //--------------------------RING CASE-------------------------
2822 assume(sbaOrder == 1);
2823 assume(arri == 0);
2824 ideal r;
2825 r = idCopy(F);
2826 int sbaEnterS = -1;
2827 bool sigdrop = TRUE;
2828 //This is how we set the SBA algorithm;
2829 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2830 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2831 && (blockred <= blockedreductions))
2832 {
2833 loops++;
2834 if(loops == 1)
2835 sigdrop = FALSE;
2836 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2837 BOOLEAN delete_w=(w==NULL);
2838 kStrategy strat=new skStrategy;
2839 strat->sbaEnterS = sbaEnterS;
2840 strat->sigdrop = sigdrop;
2841 #if 0
2842 strat->blockred = blockred;
2843 #else
2844 strat->blockred = 0;
2845 #endif
2846 strat->blockredmax = blockedreductions;
2847 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2848 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2849 strat->sbaOrder = sbaOrder;
2850 if (arri!=0)
2851 {
2852 strat->rewCrit1 = arriRewDummy;
2853 strat->rewCrit2 = arriRewCriterion;
2855 }
2856 else
2857 {
2861 }
2862
2864 strat->syzComp = syzComp;
2865 if (TEST_OPT_SB_1)
2867 strat->newIdeal = newIdeal;
2869 strat->LazyPass=20;
2870 else
2871 strat->LazyPass=2;
2872 strat->LazyDegree = 1;
2876 strat->ak = id_RankFreeModule(F,currRing);
2877 strat->kModW=kModW=NULL;
2878 strat->kHomW=kHomW=NULL;
2879 if (vw != NULL)
2880 {
2881 currRing->pLexOrder=FALSE;
2882 strat->kHomW=kHomW=vw;
2883 strat->pOrigFDeg = currRing->pFDeg;
2884 strat->pOrigLDeg = currRing->pLDeg;
2886 toReset = TRUE;
2887 }
2888 if (h==testHomog)
2889 {
2890 if (strat->ak == 0)
2891 {
2892 h = (tHomog)idHomIdeal(F,Q);
2893 w=NULL;
2894 }
2895 else if (!TEST_OPT_DEGBOUND)
2896 {
2897 if (w!=NULL)
2898 h = (tHomog)idHomModule(F,Q,w);
2899 else
2900 h = (tHomog)idHomIdeal(F,Q);
2901 }
2902 }
2903 currRing->pLexOrder=b;
2904 if (h==isHomog)
2905 {
2906 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2907 {
2908 strat->kModW = kModW = *w;
2909 if (vw == NULL)
2910 {
2911 strat->pOrigFDeg = currRing->pFDeg;
2912 strat->pOrigLDeg = currRing->pLDeg;
2914 toReset = TRUE;
2915 }
2916 }
2917 currRing->pLexOrder = TRUE;
2918 if (hilb==NULL) strat->LazyPass*=2;
2919 }
2920 strat->homog=h;
2921 #ifdef KDEBUG
2922 idTest(F);
2923 if(Q != NULL)
2924 idTest(Q);
2925 #endif
2926 #ifdef HAVE_PLURAL
2928 {
2929 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2930 strat->no_prod_crit = ! bIsSCA;
2931 if (w!=NULL)
2932 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2933 else
2934 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2935 }
2936 else
2937 #endif
2938 {
2940 {
2941 if (w!=NULL)
2942 r=mora(F,Q,*w,hilb,strat);
2943 else
2944 r=mora(F,Q,NULL,hilb,strat);
2945 }
2946 else
2947 {
2948 if (w!=NULL)
2949 r=sba(r,Q,*w,hilb,strat);
2950 else
2951 {
2952 r=sba(r,Q,NULL,hilb,strat);
2953 }
2954 }
2955 }
2956 #ifdef KDEBUG
2957 idTest(r);
2958 #endif
2959 if (toReset)
2960 {
2961 kModW = NULL;
2963 }
2964 currRing->pLexOrder = b;
2965 //Print("%d reductions canceled \n",strat->cel);
2966 sigdrop = strat->sigdrop;
2967 sbaEnterS = strat->sbaEnterS;
2968 blockred = strat->blockred;
2969 delete(strat);
2970 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2971 }
2972 // Go to std
2973 if(sigdrop || blockred > blockedreductions)
2974 {
2975 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2976 }
2977 return r;
2978 }
2979}
bool sigdrop
Definition kutil.h:358
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:293
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:295
int blockred
Definition kutil.h:363
unsigned sbaOrder
Definition kutil.h:316
int blockredmax
Definition kutil.h:364
int newIdeal
Definition kutil.h:356
char z2homog
Definition kutil.h:372
char no_prod_crit
Definition kutil.h:392
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.h:290
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
int sbaEnterS
Definition kutil.h:361
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition kInline.h:1255
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 mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd1.cc:1880
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2980
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6648
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6623
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1944
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6564
#define TEST_OPT_SB_1
Definition options.h:121

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

2486{
2487 if(idIs0(F))
2488 return idInit(1,F->rank);
2489
2490 if((Q!=NULL)&&(idIs0(Q))) Q=NULL;
2491#ifdef HAVE_SHIFTBBA
2492 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2493#endif
2494
2495 /* test HC precomputation*/
2496 int ak = id_RankFreeModule(F,currRing);
2497 poly resetppNoether = currRing->ppNoether;
2498 kStrategy strat=new skStrategy;
2499 if((ak==0)
2500 && (h!=isHomog)
2501 && (hilb==NULL)
2502 && (vw==NULL)
2503 && (newIdeal==0)
2504 && (sp==NULL)
2508 && (currRing->ppNoether==NULL))
2509 {
2510 //currRing->ppNoether=kTryHC(F,Q);
2511 strat->kNoether=kTryHC(F,Q);
2512 }
2513
2514 ideal r;
2515 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2516 BOOLEAN delete_w=(w==NULL);
2517
2518 strat->s_poly=sp;
2520 strat->syzComp = syzComp;
2521 if (TEST_OPT_SB_1
2523 )
2524 strat->newIdeal = newIdeal;
2526 strat->LazyPass=20;
2527 else
2528 strat->LazyPass=2;
2529 strat->LazyDegree = 1;
2530 strat->ak = ak;
2531 strat->kModW=kModW=NULL;
2532 strat->kHomW=kHomW=NULL;
2533 if (vw != NULL)
2534 {
2535 currRing->pLexOrder=FALSE;
2536 strat->kHomW=kHomW=vw;
2537 strat->pOrigFDeg = currRing->pFDeg;
2538 strat->pOrigLDeg = currRing->pLDeg;
2540 toReset = TRUE;
2541 }
2542 if (h==testHomog)
2543 {
2544 if (strat->ak == 0)
2545 {
2546 h = (tHomog)idHomIdeal(F,Q);
2547 w=NULL;
2548 }
2549 else if (!TEST_OPT_DEGBOUND)
2550 {
2551 if (w!=NULL)
2552 h = (tHomog)idHomModule(F,Q,w);
2553 else
2554 h = (tHomog)idHomIdeal(F,Q);
2555 }
2556 }
2557 currRing->pLexOrder=b;
2558 if (h==isHomog)
2559 {
2560 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2561 {
2562 strat->kModW = kModW = *w;
2563 if (vw == NULL)
2564 {
2565 strat->pOrigFDeg = currRing->pFDeg;
2566 strat->pOrigLDeg = currRing->pLDeg;
2568 toReset = TRUE;
2569 }
2570 }
2571 currRing->pLexOrder = TRUE;
2572 if (hilb==NULL) strat->LazyPass*=2;
2573 }
2574 strat->homog=h;
2575#ifdef KDEBUG
2576 idTest(F);
2577 if (Q!=NULL) idTest(Q);
2578#endif
2579#ifdef HAVE_PLURAL
2581 {
2582 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2583 strat->no_prod_crit = ! bIsSCA;
2584 if (w!=NULL)
2585 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2586 else
2587 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2588 }
2589 else
2590#endif
2591 {
2592 #if PRE_INTEGER_CHECK
2593 //the preinteger check strategy is not for modules
2594 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2595 {
2596 ideal FCopy = idCopy(F);
2597 poly pFmon = preIntegerCheck(FCopy, Q);
2598 if(pFmon != NULL)
2599 {
2600 idInsertPoly(FCopy, pFmon);
2601 strat->kModW=kModW=NULL;
2602 if (h==testHomog)
2603 {
2604 if (strat->ak == 0)
2605 {
2606 h = (tHomog)idHomIdeal(FCopy,Q);
2607 w=NULL;
2608 }
2609 else if (!TEST_OPT_DEGBOUND)
2610 {
2611 if (w!=NULL)
2612 h = (tHomog)idHomModule(FCopy,Q,w);
2613 else
2614 h = (tHomog)idHomIdeal(FCopy,Q);
2615 }
2616 }
2617 currRing->pLexOrder=b;
2618 if (h==isHomog)
2619 {
2620 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2621 {
2622 strat->kModW = kModW = *w;
2623 if (vw == NULL)
2624 {
2625 strat->pOrigFDeg = currRing->pFDeg;
2626 strat->pOrigLDeg = currRing->pLDeg;
2628 toReset = TRUE;
2629 }
2630 }
2631 currRing->pLexOrder = TRUE;
2632 if (hilb==NULL) strat->LazyPass*=2;
2633 }
2634 strat->homog=h;
2635 }
2636 omTestMemory(1);
2637 if(w == NULL)
2638 {
2640 r=mora(FCopy,Q,NULL,hilb,strat);
2641 else
2642 r=bba(FCopy,Q,NULL,hilb,strat);
2643 }
2644 else
2645 {
2647 r=mora(FCopy,Q,*w,hilb,strat);
2648 else
2649 r=bba(FCopy,Q,*w,hilb,strat);
2650 }
2651 idDelete(&FCopy);
2652 }
2653 else
2654 #endif
2655 {
2656 if(w==NULL)
2657 {
2659 r=mora(F,Q,NULL,hilb,strat);
2660 else
2661 r=bba(F,Q,NULL,hilb,strat);
2662 }
2663 else
2664 {
2666 r=mora(F,Q,*w,hilb,strat);
2667 else
2668 r=bba(F,Q,*w,hilb,strat);
2669 }
2670 }
2671 }
2672#ifdef KDEBUG
2673 idTest(r);
2674#endif
2675 if (toReset)
2676 {
2677 kModW = NULL;
2679 }
2680 currRing->pLexOrder = b;
2681//Print("%d reductions canceled \n",strat->cel);
2682 delete(strat);
2683 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2684 currRing->ppNoether=resetppNoether;
2685 return r;
2686}
s_poly_proc_t s_poly
Definition kutil.h:300
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition coeffs.h:809
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:2982
static poly kTryHC(ideal F, ideal Q)
Definition kstd1.cc:2438
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:10538
omError_t omTestMemory(int check_level)
Definition omDebug.c:94
BOOLEAN rOrd_is_ds(const ring r)
Definition ring.cc:2036
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:416
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:511

◆ kStdShift()

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

Definition at line 2982 of file kstd1.cc.

2984{
2986 assume(idIsInV(F));
2988 {
2989 /* error: no local ord yet with shifts */
2990 WerrorS("No local ordering possible for shift algebra");
2991 return(NULL);
2992 }
2993 ideal r;
2994 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2995 BOOLEAN delete_w=(w==NULL);
2996 kStrategy strat=new skStrategy;
2997
2998 strat->rightGB = rightGB;
2999
3001 strat->syzComp = syzComp;
3002 if (TEST_OPT_SB_1)
3004 strat->newIdeal = newIdeal;
3006 strat->LazyPass=20;
3007 else
3008 strat->LazyPass=2;
3009 strat->LazyDegree = 1;
3010 strat->ak = id_RankFreeModule(F,currRing);
3011 strat->kModW=kModW=NULL;
3012 strat->kHomW=kHomW=NULL;
3013 if (vw != NULL)
3014 {
3015 currRing->pLexOrder=FALSE;
3016 strat->kHomW=kHomW=vw;
3017 strat->pOrigFDeg = currRing->pFDeg;
3018 strat->pOrigLDeg = currRing->pLDeg;
3020 toReset = TRUE;
3021 }
3022 if (h==testHomog)
3023 {
3024 if (strat->ak == 0)
3025 {
3026 h = (tHomog)idHomIdeal(F,Q);
3027 w=NULL;
3028 }
3029 else if (!TEST_OPT_DEGBOUND)
3030 {
3031 if (w!=NULL)
3032 h = (tHomog)idHomModule(F,Q,w);
3033 else
3034 h = (tHomog)idHomIdeal(F,Q);
3035 }
3036 }
3037 currRing->pLexOrder=b;
3038 if (h==isHomog)
3039 {
3040 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3041 {
3042 strat->kModW = kModW = *w;
3043 if (vw == NULL)
3044 {
3045 strat->pOrigFDeg = currRing->pFDeg;
3046 strat->pOrigLDeg = currRing->pLDeg;
3048 toReset = TRUE;
3049 }
3050 }
3051 currRing->pLexOrder = TRUE;
3052 if (hilb==NULL) strat->LazyPass*=2;
3053 }
3054 strat->homog=h;
3055#ifdef KDEBUG
3056 idTest(F);
3057#endif
3058 /* global ordering */
3059 if (w!=NULL)
3060 r=bbaShift(F,Q,*w,hilb,strat);
3061 else
3062 r=bbaShift(F,Q,NULL,hilb,strat);
3063#ifdef KDEBUG
3064 idTest(r);
3065#endif
3066 if (toReset)
3067 {
3068 kModW = NULL;
3070 }
3071 currRing->pLexOrder = b;
3072//Print("%d reductions canceled \n",strat->cel);
3073 delete(strat);
3074 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3075 assume(idIsInV(r));
3076 return r;
3077}
char rightGB
Definition kutil.h:367
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:4590
#define idIsInV(I)
Definition shiftop.h:49

◆ kTryHC()

static poly kTryHC ( ideal F,
ideal Q )
static

Definition at line 2438 of file kstd1.cc.

2439{
2440 if (TEST_V_NO_TRY_HC)
2441 return NULL;
2442 int prim=kFindLuckyPrime(F,Q);
2443 if (TEST_OPT_PROT) Print("try HC in ring over ZZ/%d\n",prim);
2444 // create Zp_ring
2445 ring save_ring=currRing;
2446 ring Zp_ring=rCopy0(save_ring);
2447 nKillChar(Zp_ring->cf);
2448 Zp_ring->cf=nInitChar(n_Zp, (void*)(long)prim);
2449 rComplete(Zp_ring);
2450 // map data
2451 rChangeCurrRing(Zp_ring);
2452 nMapFunc nMap=n_SetMap(save_ring->cf,Zp_ring->cf);
2453 ideal FF=id_PermIdeal(F,1,IDELEMS(F),NULL,save_ring,Zp_ring,nMap,NULL,0,0);
2454 ideal QQ=NULL;
2455 if (Q!=NULL) QQ=id_PermIdeal(Q,1,IDELEMS(Q),NULL,save_ring,Zp_ring,nMap,NULL,0,0);
2456 // call std
2457 kStrategy strat=new skStrategy;
2458 strat->LazyPass=20;
2459 strat->LazyDegree = 1;
2460 strat->kModW=kModW=NULL;
2461 strat->kHomW=kHomW=NULL;
2462 strat->homog = (tHomog)idHomIdeal(F,Q);
2463 ideal res=mora(FF,QQ,NULL,NULL,strat);
2464 // clean
2465 idDelete(&FF);
2466 if (QQ!=NULL) idDelete(&QQ);
2467 idDelete(&res);
2468 poly HC=strat->kNoether; strat->kNoether=NULL;
2469 delete strat;
2470 // map back
2471 rChangeCurrRing(save_ring);
2472 if (HC!=NULL)
2473 {
2474 p_IncrExp(HC,save_ring->N,save_ring);
2475 if (TEST_OPT_PROT) Print("HC(%ld) found\n",pTotaldegree(HC));
2476 for(int i=1;i<save_ring->N;i++)
2477 p_IncrExp(HC,i,save_ring);
2478 p_Setm(HC,save_ring);
2479 }
2480 rDelete(Zp_ring);
2481 return HC;
2482}
@ n_Zp
\F{p < 2^31}
Definition coeffs.h:29
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition coeffs.h:701
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition numbers.cc:406
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition coeffs.h:80
void nKillChar(coeffs r)
undo all initialisations
Definition numbers.cc:556
static int kFindLuckyPrime(ideal F, ideal Q)
Definition kstd1.cc:2431
#define TEST_V_NO_TRY_HC
Definition options.h:137
static long p_IncrExp(poly p, int v, ring r)
Definition p_polys.h:591
static void p_Setm(poly p, const ring r)
Definition p_polys.h:233
static long pTotaldegree(poly p)
Definition polys.h:282
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition ring.cc:3465
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition ring.cc:1424
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:452
ideal id_PermIdeal(ideal I, int R, int C, const int *perm, const ring src, const ring dst, nMapFunc nMap, const int *par_perm, int P, BOOLEAN use_mult)
mapping ideals/matrices to other rings

◆ missingAxis()

void missingAxis ( int * last,
kStrategy strat )

Definition at line 1280 of file kstd1.cc.

1281{
1282 int i = 0;
1283 int k = 0;
1284
1285 *last = 0;
1287 {
1288 loop
1289 {
1290 i++;
1291 if (i > (currRing->N)) break;
1292 if (strat->NotUsedAxis[i])
1293 {
1294 *last = i;
1295 k++;
1296 }
1297 if (k>1)
1298 {
1299 *last = 0;
1300 break;
1301 }
1302 }
1303 }
1304}
int k
Definition cfEzgcd.cc:99
BOOLEAN rHasMixedOrdering(const ring r)
Definition ring.h:768
#define loop
Definition structs.h:75

◆ mora()

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

Definition at line 1880 of file kstd1.cc.

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

◆ posInL10()

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

Definition at line 1361 of file kstd1.cc.

1362{
1363 int j,dp,dL;
1364
1365 if (length<0) return 0;
1366 if (hasPurePower(p,strat->lastAxis,&dp,strat))
1367 {
1368 int op= p->GetpFDeg() +p->ecart;
1369 for (j=length; j>=0; j--)
1370 {
1371 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1372 return j+1;
1373 if (dp < dL)
1374 return j+1;
1375 if ((dp == dL)
1376 && (set[j].GetpFDeg()+set[j].ecart >= op))
1377 return j+1;
1378 }
1379 }
1380 j=length;
1381 loop
1382 {
1383 if (j<0) break;
1384 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1385 j--;
1386 }
1387 return strat->posInLOld(set,j,p,strat);
1388}

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

◆ redFirst()

int redFirst ( LObject * h,
kStrategy strat )

Definition at line 795 of file kstd1.cc.

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

◆ redMoraNF()

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

Definition at line 977 of file kstd1.cc.

978{
979 LObject H;
980 H.p = h;
981 int j = 0;
982 int z = 10;
983 int o = H.SetpFDeg();
984 H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
985 if ((flag & 2) == 0) cancelunit(&H,TRUE);
986 H.sev = pGetShortExpVector(H.p);
987 loop
988 {
989 if (j > strat->tl)
990 {
991 return H.p;
992 }
993 if (TEST_V_DEG_STOP)
994 {
995 if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
996 if (H.p==NULL) return NULL;
997 }
998 unsigned long not_sev = ~ H.sev;
999 if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1000 )
1001 {
1002 /*- remember the found T-poly -*/
1003 // poly pi = strat->T[j].p;
1004 int ei = strat->T[j].ecart;
1005 int li = strat->T[j].length;
1006 int ii = j;
1007 /*
1008 * the polynomial to reduce with (up to the moment) is;
1009 * pi with ecart ei and length li
1010 */
1011 loop
1012 {
1013 /*- look for a better one with respect to ecart -*/
1014 /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1015 j++;
1016 if (j > strat->tl) break;
1017 if (ei <= H.ecart) break;
1018 if (((strat->T[j].ecart < ei)
1019 || ((strat->T[j].ecart == ei)
1020 && (strat->T[j].length < li)))
1021 && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1022 )
1023 {
1024 /*
1025 * the polynomial to reduce with is now;
1026 */
1027 // pi = strat->T[j].p;
1028 ei = strat->T[j].ecart;
1029 li = strat->T[j].length;
1030 ii = j;
1031 }
1032 }
1033 /*
1034 * end of search: have to reduce with pi
1035 */
1036 z++;
1037 if (z>10)
1038 {
1039 pNormalize(H.p);
1040 z=0;
1041 }
1042 if ((ei > H.ecart) && (strat->kNoether==NULL))
1043 {
1044 /*
1045 * It is not possible to reduce h with smaller ecart;
1046 * we have to reduce with bad ecart: H has to enter in T
1047 */
1048 LObject L= H;
1049 L.Copy();
1050 H.GetP();
1051 H.length=H.pLength=pLength(H.p);
1052 ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1053 (flag & KSTD_NF_NONORM)==0);
1054 enterT(H,strat);
1055 H = L;
1056 }
1057 else
1058 {
1059 /*
1060 * we reduce with good ecart, h need not to be put to T
1061 */
1062 ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1063 (flag & KSTD_NF_NONORM)==0);
1064 }
1065 if (H.p == NULL)
1066 return NULL;
1067 /*- try to reduce the s-polynomial -*/
1068 o = H.SetpFDeg();
1069 if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
1070 H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1071 j = 0;
1072 H.sev = pGetShortExpVector(H.p);
1073 }
1074 else
1075 {
1076 j++;
1077 }
1078 }
1079}
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 1081 of file kstd1.cc.

1082{
1083 LObject H;
1084 H.p = h;
1085 int j0, j = 0;
1086 int docoeffred = 0;
1087 poly T0p = strat->T[0].p;
1088 int T0ecart = strat->T[0].ecart;
1089 int o = H.SetpFDeg();
1090 H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
1091 if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
1092 H.sev = pGetShortExpVector(H.p);
1093 unsigned long not_sev = ~ H.sev;
1094 if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2)
1095 {
1096 docoeffred = 1; // euclidean ring required: n_QuotRem
1097 if (currRing->cf->cfQuotRem==ndQuotRem)
1098 {
1099 docoeffred = 0;
1100 }
1101 }
1102 loop
1103 {
1104 /* cut down the lead coefficients, only possible if the degree of
1105 * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
1106 * we ask for the length of T[0] to be <= 2 */
1107 if (docoeffred)
1108 {
1109 j0 = kTestDivisibleByT0_Z(strat, &H);
1110 if ((j0 == 0)
1111 && (n_DivBy(pGetCoeff(H.p), pGetCoeff(T0p), currRing->cf) == FALSE)
1112 && (T0ecart <= H.ecart))
1113 {
1114 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
1115 * => we try to cut down the lead coefficient at least */
1116 /* first copy T[j0] in order to multiply it with a coefficient later on */
1117 number mult, rest;
1118 TObject tj = strat->T[0];
1119 tj.Copy();
1120 /* compute division with remainder of lc(h) and lc(T[j]) */
1121 mult = n_QuotRem(pGetCoeff(H.p), pGetCoeff(T0p),
1122 &rest, currRing->cf);
1123 /* set corresponding new lead coefficient already. we do not
1124 * remove the lead term in ksReducePolyLC, but only apply
1125 * a lead coefficient reduction */
1126 tj.Mult_nn(mult);
1127 ksReducePolyLC(&H, &tj, NULL, &rest, strat);
1128 tj.Delete();
1129 tj.Clear();
1130 }
1131 }
1132 if (j > strat->tl)
1133 {
1134 return H.p;
1135 }
1136 if (TEST_V_DEG_STOP)
1137 {
1138 if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
1139 if (H.p==NULL) return NULL;
1140 }
1141 if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1142 && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1143 )
1144 {
1145 /*- remember the found T-poly -*/
1146 // poly pi = strat->T[j].p;
1147 int ei = strat->T[j].ecart;
1148 int li = strat->T[j].length;
1149 int ii = j;
1150 /*
1151 * the polynomial to reduce with (up to the moment) is;
1152 * pi with ecart ei and length li
1153 */
1154 loop
1155 {
1156 /*- look for a better one with respect to ecart -*/
1157 /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1158 j++;
1159 if (j > strat->tl) break;
1160 if (ei <= H.ecart) break;
1161 if (((strat->T[j].ecart < ei)
1162 || ((strat->T[j].ecart == ei)
1163 && (strat->T[j].length < li)))
1164 && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1165 && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1166 )
1167 {
1168 /*
1169 * the polynomial to reduce with is now;
1170 */
1171 // pi = strat->T[j].p;
1172 ei = strat->T[j].ecart;
1173 li = strat->T[j].length;
1174 ii = j;
1175 }
1176 }
1177 /*
1178 * end of search: have to reduce with pi
1179 */
1180 if ((ei > H.ecart) && (strat->kNoether==NULL))
1181 {
1182 /*
1183 * It is not possible to reduce h with smaller ecart;
1184 * we have to reduce with bad ecart: H has to enter in T
1185 */
1186 LObject L= H;
1187 L.Copy();
1188 H.GetP();
1189 H.length=H.pLength=pLength(H.p);
1190 ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1191 (flag & KSTD_NF_NONORM)==0);
1192 enterT_strong(H,strat);
1193 H = L;
1194 }
1195 else
1196 {
1197 /*
1198 * we reduce with good ecart, h need not to be put to T
1199 */
1200 ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1201 (flag & KSTD_NF_NONORM)==0);
1202 }
1203 if (H.p == NULL)
1204 return NULL;
1205 /*- try to reduce the s-polynomial -*/
1206 o = H.SetpFDeg();
1207 if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1208 H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1209 j = 0;
1210 H.sev = pGetShortExpVector(H.p);
1211 not_sev = ~ H.sev;
1212 }
1213 else
1214 {
1215 j++;
1216 }
1217 }
1218}
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition coeffs.h:682
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:748
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
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:146
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:647
number ndQuotRem(number a, number b, number *r, const coeffs R)
Definition numbers.cc:350

◆ redRiloc()

int redRiloc ( LObject * h,
kStrategy strat )

Definition at line 386 of file kstd1.cc.

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

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

◆ reorderL()

void reorderL ( kStrategy strat)

Definition at line 1223 of file kstd1.cc.

1224{
1225 int i,j,at;
1226
1227 for (i=1; i<=strat->Ll; i++)
1228 {
1229 at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
1230 if (at != i)
1231 {
1232 LObject p = strat->L[i];
1233 for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
1234 strat->L[at] = p;
1235 }
1236 }
1237}

◆ reorderT()

void reorderT ( kStrategy strat)

Definition at line 1242 of file kstd1.cc.

1243{
1244 int i,j,at;
1245 TObject p;
1246 unsigned long sev;
1247
1248
1249 for (i=1; i<=strat->tl; i++)
1250 {
1251 if (strat->T[i-1].length > strat->T[i].length)
1252 {
1253 p = strat->T[i];
1254 sev = strat->sevT[i];
1255 at = i-1;
1256 loop
1257 {
1258 at--;
1259 if (at < 0) break;
1260 if (strat->T[i].length > strat->T[at].length) break;
1261 }
1262 for (j = i-1; j>at; j--)
1263 {
1264 strat->T[j+1]=strat->T[j];
1265 strat->sevT[j+1]=strat->sevT[j];
1266 strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
1267 }
1268 strat->T[at+1]=p;
1269 strat->sevT[at+1] = sev;
1270 strat->R[p.i_r] = &(strat->T[at+1]);
1271 }
1272 }
1273}

◆ updateL()

void updateL ( kStrategy strat)

Definition at line 1394 of file kstd1.cc.

1395{
1396 int dL;
1397 int j=strat->Ll;
1398 loop
1399 {
1400 if (j<0) break;
1401 if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1402 {
1403 LObject p;
1404 p=strat->L[strat->Ll];
1405 strat->L[strat->Ll]=strat->L[j];
1406 strat->L[j]=p;
1407 break;
1408 }
1409 j--;
1410 }
1411 if (j<0)
1412 {
1413 j=strat->Ll;
1414 loop
1415 {
1416 if (j<0) break;
1417 if (pNext(strat->L[j].p) == strat->tail)
1418 {
1420 pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1421 else
1422 pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1423 strat->L[j].p = NULL;
1424 poly m1 = NULL, m2 = NULL;
1425 // check that spoly creation is ok
1426 while (strat->tailRing != currRing &&
1427 !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1428 {
1429 assume(m1 == NULL && m2 == NULL);
1430 // if not, change to a ring where exponents are at least
1431 // large enough
1432 kStratChangeTailRing(strat);
1433 }
1434 /* create the real one */
1435 ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1436 strat->tailRing, m1, m2, strat->R);
1437
1438 strat->L[j].SetLmCurrRing();
1439 if (!strat->honey)
1440 strat->initEcart(&strat->L[j]);
1441 else
1442 strat->L[j].SetLength(strat->length_pLength);
1443
1444 BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1445
1446 strat->L[j].PrepareRed(strat->use_buckets);
1447
1448 if (pp)
1449 {
1450 LObject p;
1451 p=strat->L[strat->Ll];
1452 strat->L[strat->Ll]=strat->L[j];
1453 strat->L[j]=p;
1454 break;
1455 }
1456 }
1457 j--;
1458 }
1459 }
1460}

◆ updateLHC()

void updateLHC ( kStrategy strat)

Definition at line 1466 of file kstd1.cc.

1467{
1468
1469 int i = 0;
1470 kTest_TS(strat);
1471 while (i <= strat->Ll)
1472 {
1473 if (pNext(strat->L[i].p) == strat->tail)
1474 {
1475 /*- deletes the int spoly and computes -*/
1476 if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
1477 {
1479 pLmDelete(strat->L[i].p);
1480 else
1481 pLmFree(strat->L[i].p);
1482 strat->L[i].p = NULL;
1483 }
1484 else
1485 {
1487 pLmDelete(strat->L[i].p);
1488 else
1489 pLmFree(strat->L[i].p);
1490 strat->L[i].p = NULL;
1491 poly m1 = NULL, m2 = NULL;
1492 // check that spoly creation is ok
1493 while (strat->tailRing != currRing &&
1494 !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
1495 {
1496 assume(m1 == NULL && m2 == NULL);
1497 // if not, change to a ring where exponents are at least
1498 // large enough
1499 kStratChangeTailRing(strat);
1500 }
1501 /* create the real one */
1502 ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
1503 strat->tailRing, m1, m2, strat->R);
1504 if (! strat->L[i].IsNull())
1505 {
1506 strat->L[i].SetLmCurrRing();
1507 strat->L[i].SetpFDeg();
1508 strat->L[i].ecart
1509 = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
1510 if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
1511 }
1512 }
1513 }
1514 deleteHC(&(strat->L[i]), strat);
1515 if (strat->L[i].IsNull())
1516 deleteInL(strat->L,&strat->Ll,i,strat);
1517 else
1518 {
1519#ifdef KDEBUG
1520 kTest_L(&(strat->L[i]), strat, TRUE, i, strat->T, strat->tl);
1521#endif
1522 i++;
1523 }
1524 }
1525 kTest_TS(strat);
1526}

◆ updateT()

void updateT ( kStrategy strat)

Definition at line 1532 of file kstd1.cc.

1533{
1534 int i = 0;
1535 LObject p;
1536
1537 while (i <= strat->tl)
1538 {
1539 p = strat->T[i];
1540 deleteHC(&p,strat, TRUE);
1541 /*- tries to cancel a unit: -*/
1542 cancelunit(&p);
1543 if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
1544 p.pCleardenom();
1545 if (p.p != strat->T[i].p)
1546 {
1547 strat->sevT[i] = pGetShortExpVector(p.p);
1548 p.SetpFDeg();
1549 }
1550 strat->T[i] = p;
1551 i++;
1552 }
1553}

Variable Documentation

◆ kHomW

VAR intvec * kHomW

Definition at line 2407 of file kstd1.cc.

◆ kModW

VAR intvec* kModW

Definition at line 2407 of file kstd1.cc.

◆ kOptions

VAR BITSET kOptions
Initial value:
#define OPT_SUGARCRIT
Definition options.h:81
#define OPT_PROT
Definition options.h:76
#define OPT_INFREDTAIL
Definition options.h:95
#define OPT_WEIGHTM
Definition options.h:98
#define OPT_NOT_SUGAR
Definition options.h:79
#define OPT_NOTREGULARITY
Definition options.h:97
#define OPT_INTERRUPT
Definition options.h:80
#define OPT_FASTHC
Definition options.h:86
#define OPT_OLDSTD
Definition options.h:87

Definition at line 45 of file kstd1.cc.

◆ validOpts

VAR BITSET validOpts

Definition at line 60 of file kstd1.cc.