My Project  UNKNOWN_GIT_VERSION
kutil.h
Go to the documentation of this file.
1 #ifndef KUTIL_H
2 #define KUTIL_H
3 /****************************************
4 * Computer Algebra System SINGULAR *
5 ****************************************/
6 /*
7 * ABSTRACT: kernel: utils for kStd
8 */
9 
10 
11 #include <string.h>
12 
13 #include "omalloc/omalloc.h"
14 #ifndef XMEMORY_H
15 #include "omalloc/omallocClass.h"
16 #endif
17 #include "misc/mylimits.h"
18 
19 
20 #include "kernel/polys.h"
22 
23 #include "kernel/structs.h"
24 #include "kernel/GBEngine/kstd1.h" /* for s_poly_proc_t */
25 
26 // define if tailrings should be used
27 #define HAVE_TAIL_RING
28 
29 #define setmax 128
30 #define setmaxL ((4096-12)/sizeof(LObject))
31 #define setmaxLinc ((4096)/sizeof(LObject))
32 
33 #define setmaxT ((4096-12)/sizeof(TObject))
34 #define setmaxTinc ((4096)/sizeof(TObject))
35 
36 // if you want std computations as in Singular version < 2:
37 // This disables RedThrough, tailReductions against T (bba),
38 // sets posInT = posInT15 (bba, strat->honey), and enables redFirst with LDeg
39 // NOTE: can be achieved with option(oldStd)
40 
41 #undef NO_KINLINE
42 #if !defined(KDEBUG) && !defined(NO_INLINE)
43 #define KINLINE inline
44 #else
45 #define KINLINE
46 #define NO_KINLINE 1
47 #endif
48 
49 typedef int* intset;
50 typedef int64 wlen_type;
52 
53 typedef class sTObject TObject;
54 typedef class sLObject LObject;
55 typedef TObject * TSet;
56 typedef LObject * LSet;
57 
60 
63 
64 class sTObject
65 {
66 public:
67  unsigned long sevSig;
68  poly sig; // the signature of the element
69  poly p; // Lm(p) \in currRing Tail(p) \in tailRing
70  poly t_p; // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
71  poly max_exp; // p_GetMaxExpP(pNext(p))
72  ring tailRing;
73  long FDeg; // pFDeg(p)
74  int ecart,
75  length, // as of pLDeg
76  pLength, // either == 0, or == pLength(p)
77  i_r; // index of TObject in R set, or -1 if not in T
78  /*BOOLEAN*/ char is_normalized; // true, if pNorm was called on p, false otherwise
79  // used in incremental sba() with F5C:
80  // we know some of the redundant elements in
81  // strat->T beforehand, so we can just discard
82  // them and do not need to consider them in the
83  // interreduction process
84  /*BOOLEAN*/ char is_redundant;
85  // used in sba's sig-safe reduction:
86  // sometimes we already know that a reducer
87  // is sig-safe, so no need for a real
88  // sig-safeness check
89  /*BOOLEAN*/ char is_sigsafe;
90 
91 
92 #ifdef HAVE_PLURAL
93  /*BOOLEAN*/ char is_special; // true, it is a new special S-poly (e.g. for SCA)
94 #endif
95 
96  // initialization
97  KINLINE void Init(ring r = currRing);
99  KINLINE sTObject(poly p, ring tailRing = currRing);
100  KINLINE sTObject(poly p, ring c_r, ring tailRing);
101  KINLINE sTObject(sTObject* T, int copy);
102 
103  KINLINE void Set(ring r=currRing);
104  KINLINE void Set(poly p_in, ring r=currRing);
105  KINLINE void Set(poly p_in, ring c_r, ring t_r);
106 
107  // Frees the polys of T
108  KINLINE void Delete();
109  // Sets polys to NULL
110  KINLINE void Clear();
111  // makes a copy of the poly of T
112  KINLINE void Copy();
113 
114  // ring-dependent Lm access: these might result in allocation of monomials
115  KINLINE poly GetLmCurrRing();
116  KINLINE poly GetLmTailRing();
117  KINLINE poly GetLm(ring r);
118  // this returns Lm and ring r (preferably from tailRing), but does not
119  // allocate a new poly
120  KINLINE void GetLm(poly &p, ring &r) const;
121 
122 #ifdef OLIVER_PRIVAT_LT
123  // routines for calc. with rings
124  KINLINE poly GetLtCurrRing();
125  KINLINE poly GetLtTailRing();
126  KINLINE poly GetLt(ring r);
127  KINLINE void GetLt(poly &p, ring &r) const;
128 #endif
129 
130  KINLINE BOOLEAN IsNull() const;
131 
132  KINLINE int GetpLength();
133 
134  // makes sure that T.p exists
135  KINLINE void SetLmCurrRing();
136 
137  // Iterations
138  // simply get the next monomial
139  KINLINE poly Next();
140  KINLINE void LmDeleteAndIter();
141 
142  // deg stuff
143  // compute pTotalDegree
144  KINLINE long pTotalDeg() const;
145  // computes pFDeg
146  KINLINE long pFDeg() const;
147  // computes and sets FDeg
148  KINLINE long SetpFDeg();
149  // gets stored FDeg
150  KINLINE long GetpFDeg() const;
151 
152  // computes pLDeg
153  KINLINE long pLDeg();
154  // sets length, FDeg, returns LDeg
156 
157  // arithmetic
158  KINLINE void Mult_nn(number n);
159  KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin,
160  pShallowCopyDeleteProc p_shallow_copy_delete,
161  BOOLEAN set_max = TRUE);
162  // manipulations
163  KINLINE void pNorm();
164  KINLINE void pCleardenom();
165 
166 #ifdef KDEBUG
167  void wrp();
168 #endif
169 };
170 
171 extern int strat_nr;
172 
173 class sLObject : public sTObject
174 {
175 
176 public:
177  unsigned long sev;
178  poly p1,p2; /*- the pair p comes from,
179  lm(pi) in currRing, tail(pi) in tailring -*/
180 
181  poly lcm; /*- the lcm of p1,p2 -*/
183  int i_r1, i_r2;
184  unsigned checked; // this is the index of S up to which
185  // the corresponding LObject was already checked in
186  // critical pair creation => when entering the
187  // reduction process it is enough to start a second
188  // rewritten criterion check from checked+1 onwards
190  // NOTE: If prod_crit = TRUE then the corresponding pair is
191  // detected by Buchberger's Product Criterion and can be
192  // deleted
193 
194  // initialization
195  KINLINE void Init(ring tailRing = currRing);
197  KINLINE sLObject(poly p, ring tailRing = currRing);
198  KINLINE sLObject(poly p, ring c_r, ring tailRing);
199 
200  // Frees the polys of L
201  KINLINE void Delete();
202  KINLINE void Clear();
203 
204  // Iterations
205  KINLINE void LmDeleteAndIter();
206  KINLINE poly LmExtractAndIter();
207 
208  // spoly related things
209  // preparation for reduction if not spoly
210  KINLINE void PrepareRed(BOOLEAN use_bucket);
211  KINLINE void SetLmTail(poly lm, poly new_p, int length,
212  int use_bucket, ring r);
213  KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
214  KINLINE void Tail_Mult_nn(number n);
215  // deletes bucket, makes sure that p and t_p exists
216  KINLINE poly GetP(omBin lmBin = (omBin)NULL);
217  // similar, except that only t_p exists
218  KINLINE poly GetTP();
219 
220  // does not delete bucket, just canonicalizes it
221  // returned poly is such that Lm(p) \in currRing, Tail(p) \in tailRing
222  KINLINE void CanonicalizeP();
223 
224  // makes a copy of the poly of L
225  KINLINE void Copy();
226 
227  KINLINE int GetpLength();
228  KINLINE long pLDeg(BOOLEAN use_last);
229  KINLINE long pLDeg();
230  KINLINE int SetLength(BOOLEAN lengt_pLength = FALSE);
232  KINLINE long SetDegStuffReturnLDeg(BOOLEAN use_last);
233 
234  // returns minimal component of p
235  KINLINE long MinComp();
236  // returns component of p
237  KINLINE long Comp();
238 
239  KINLINE void ShallowCopyDelete(ring new_tailRing,
240  pShallowCopyDeleteProc p_shallow_copy_delete);
241 
242  // sets sev
243  KINLINE void SetShortExpVector();
244 
245  // enable assignment from TObject
247 
248  // get T's corresponding to p1, p2: they might return NULL
249  KINLINE TObject* T_1(const skStrategy* strat);
250  KINLINE TObject* T_2(const skStrategy* strat);
251  KINLINE void T_1_2(const skStrategy* strat,
252  TObject* &T_1, TObject* &T_2);
253 
254  // simplify coefficients
255  KINLINE void Normalize();
256  KINLINE void HeadNormalize();
257 };
258 
259 
260 extern int HCord;
261 
263 #ifndef XMEMORY_H
264  : public omallocClass
265 #endif
266 {
267 public:
269  int (*red)(LObject * L,kStrategy strat);
270  int (*red2)(LObject * L,kStrategy strat);
271  void (*initEcart)(TObject * L);
272  int (*posInT)(const TSet T,const int tl,LObject &h);
273  int (*posInLSba)(const LSet set, const int length,
274  LObject* L,const kStrategy strat);
275  int (*posInL)(const LSet set, const int length,
276  LObject* L,const kStrategy strat);
277  void (*enterS)(LObject &h, int pos,kStrategy strat, int atR/* =-1*/ );
278  void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
279  int (*posInLOld)(const LSet Ls,const int Ll,
280  LObject* Lo,const kStrategy strat);
281  void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
282  void (*chainCrit) (poly p,int ecart,kStrategy strat);
283  BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
284  BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
285  BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
286  BOOLEAN (*rewCrit3) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
292 
294  ideal Shdl;
295  ideal D; /*V(S) is in D(D)*/
296  ideal M; /*set of minimal generators*/
301  intset fromS; // from which S[i] S[j] comes from
302  // this is important for signature-based
303  // algorithms
304  intset syzIdx;// index in the syz array at which the first
305  // syzygy of component i comes up
306  // important for signature-based algorithms
307  unsigned sbaOrder;
308  int currIdx;
311  wlen_set lenSw; /* for tgb.ccc */
313  unsigned long* sevS;
314  unsigned long* sevSyz;
315  unsigned long* sevSig;
316  unsigned long* sevT;
320  poly kHEdge;
321  poly kNoether;
322  poly t_kHEdge; // same polys in tailring
323  KINLINE poly kNoetherTail();
326  BOOLEAN * pairtest;/*used for enterOnePair*/
327  poly tail;
330  // procedure for ShalloCopy from tailRing to currRing
332  // pointers to Tobjects R[i] is ith Tobject which is generated
334  // S_2_R[i] yields Tobject which corresponds to S[i]
335  int* S_2_R;
336  ring tailRing;
339  int nr;
340  int cp,c3;
341  int sl,mu;
343  int tl,tmax;
344  int Ll,Lmax;
345  int Bl,Bmax;
347  int syzComp;
348  int HCord;
349  int lastAxis;
350  int newIdeal;
351  int minim;
352  #ifdef HAVE_RINGS
353  bool sigdrop; //This is used to check sigdrop in sba over Z
354  int nrsyzcrit; // counts how many pairs are deleted by SyzCrit
355  int nrrewcrit; // counts how many pairs are deleted by FaugereRewCrit
356  int sbaEnterS; // sba over Z strategy: if sigdrop element has _*gen(sbaEnterS+1), then
357  // add directly sbaEnterS elements into S
358  int blockred; // counter for blocked reductions in redSig
360  #endif
361  #ifdef HAVE_SHIFTBBA
362  int lV;
363  int cv; // in shift bases: counting V criterion
364  #endif
365  /*BOOLEAN*/ char interpt;
366  /*BOOLEAN*/ char homog;
367 #ifdef HAVE_PLURAL
368  /*BOOLEAN*/ char z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
369 #endif
370  /*BOOLEAN*/ char kHEdgeFound;
371  /*BOOLEAN*/ char honey,sugarCrit;
372  /*BOOLEAN*/ char Gebauer,noTailReduction;
373  /*BOOLEAN*/ char fromT;
374  /*BOOLEAN*/ char noetherSet;
375  /*BOOLEAN*/ char update;
376  /*BOOLEAN*/ char posInLOldFlag;
377  /*BOOLEAN*/ char use_buckets;
378  // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
379  /*BOOLEAN*/ char LDegLast;
380  // if set, then L.length == L.pLength
381  /*BOOLEAN*/ char length_pLength;
382  // if set, then posInL does not depend on L.length
383  /*BOOLEAN*/ char posInLDependsOnLength;
384  /*FALSE, if posInL == posInL10*/
385 #ifdef HAVE_PLURAL
386  // set this flag to 1 to stop the product criteria
387  // use ALLOW_PROD_CRIT(strat) to test
388  /*BOOLEAN*/ char no_prod_crit;
389 #define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
390 #else
391 #define ALLOW_PROD_CRIT(A) (1)
392 #endif
394  char news;
395  char newt;/*used for messageSets*/
396  char noClearS;
398  char overflow;
399 
400  skStrategy();
401  ~skStrategy();
402 
403  // return TObject corresponding to S[i]: assume that it exists
404  // i.e. no error checking is done
405  KINLINE TObject* S_2_T(int i);
406  // like S_2_T, except that NULL is returned if it can not be found
407  KINLINE TObject* s_2_t(int i);
408 };
409 
410 void deleteHC(poly *p, int *e, int *l, kStrategy strat);
411 void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
412 void deleteInS (int i,kStrategy strat);
413 void deleteInSSba (int i,kStrategy strat);
414 void cleanT (kStrategy strat);
415 static inline LSet initL (int nr=setmaxL)
416 { return (LSet)omAlloc(nr*sizeof(LObject)); }
417 void deleteInL(LSet set, int *length, int j,kStrategy strat);
418 void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
419 void enterSBba (LObject &p,int atS,kStrategy strat, int atR = -1);
420 void enterSSba (LObject &p,int atS,kStrategy strat, int atR = -1);
421 void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
422 void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
423 int posInS (const kStrategy strat, const int length, const poly p,
424  const int ecart_p);
425 int posInSMonFirst (const kStrategy strat, const int length, const poly p);
426 int posInIdealMonFirst (const ideal F, const poly p,int start = 0,int end = -1);
427 int posInT0 (const TSet set,const int length,LObject &p);
428 int posInT1 (const TSet set,const int length,LObject &p);
429 int posInT2 (const TSet set,const int length,LObject &p);
430 int posInT11 (const TSet set,const int length,LObject &p);
431 int posInTSig (const TSet set,const int length,LObject &p);
432 int posInT110 (const TSet set,const int length,LObject &p);
433 int posInT13 (const TSet set,const int length,LObject &p);
434 int posInT15 (const TSet set,const int length,LObject &p);
435 int posInT17 (const TSet set,const int length,LObject &p);
436 int posInT17_c (const TSet set,const int length,LObject &p);
437 int posInT19 (const TSet set,const int length,LObject &p);
438 int posInT_EcartpLength(const TSet set,const int length,LObject &p);
439 int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
440 int posInT_FDegpLength(const TSet set,const int length,LObject &p);
441 int posInT_pLength(const TSet set,const int length,LObject &p);
442 
443 #ifdef HAVE_MORE_POS_IN_T
444 int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
445 int posInT_FDegpLength(const TSet set,const int length,LObject &p);
446 int posInT_pLength(const TSet set,const int length,LObject &p);
447 #endif
448 
449 
450 void reorderS (int* suc,kStrategy strat);
451 int posInLF5C (const LSet set, const int length,
452  LObject* L,const kStrategy strat);
453 int posInLSig (const LSet set, const int length,
454  LObject* L,const kStrategy strat);
455 int posInLSigRing (const LSet set, const int length,
456  LObject* L,const kStrategy strat);
457 int posInLRing (const LSet set, const int length,
458  LObject* L,const kStrategy strat);
459 int posInSyz (const kStrategy strat, const poly sig);
460 int posInL0 (const LSet set, const int length,
461  LObject* L,const kStrategy strat);
462 int posInL11 (const LSet set, const int length,
463  LObject* L,const kStrategy strat);
464 int posInL11Ring (const LSet set, const int length,
465  LObject* L,const kStrategy strat);
466 int posInLF5CRing (const LSet set, int start , const int length,
467  LObject* L,const kStrategy strat);
468 int posInL11Ringls (const LSet set, const int length,
469  LObject* L,const kStrategy strat);
470 int posInL13 (const LSet set, const int length,
471  LObject* L,const kStrategy strat);
472 int posInL15 (const LSet set, const int length,
473  LObject* L,const kStrategy strat);
474 int posInL15Ring (const LSet set, const int length,
475  LObject* L,const kStrategy strat);
476 int posInL17 (const LSet set, const int length,
477  LObject* L,const kStrategy strat);
478 int posInL10 (const LSet set, const int length,
479  LObject* L,const kStrategy strat);
480 int posInL10Ring (const LSet set, const int length,
481  LObject* L,const kStrategy strat);
482 int posInL110 (const LSet set, const int length,
483  LObject* L,const kStrategy strat);
484 KINLINE poly redtailBba (poly p,int end_pos,kStrategy strat,BOOLEAN normalize=FALSE);
485 KINLINE poly redtailBbaBound (poly p,int end_pos,kStrategy strat,int bound,BOOLEAN normalize=FALSE);
486 #ifdef HAVE_RINGS
487 KINLINE poly redtailBba_Z (poly p,int end_pos,kStrategy strat);
488 poly redtailBba_Z (LObject* L, int end_pos, kStrategy strat );
489 #endif
490 poly redtailBba (LObject *L, int end_pos,kStrategy strat,
492 poly redtailBbaBound (LObject *L, int end_pos,kStrategy strat,int bound,
494 poly redtailSba (LObject *L, int end_pos,kStrategy strat,
496 poly redtailBba (TObject *T, int end_pos,kStrategy strat);
497 poly redtail (poly p,int end_pos,kStrategy strat);
498 poly redtail (LObject *L,int end_pos,kStrategy strat);
499 poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
500 int redNF0 (LObject *P,kStrategy strat);
501 poly redNFTail (poly h,const int sl,kStrategy strat);
502 int redHoney (LObject* h, kStrategy strat);
503 #ifdef HAVE_RINGS
504 int redRing (LObject* h,kStrategy strat);
505 int redRiloc (LObject* h,kStrategy strat);
506 void enterExtendedSpoly(poly h,kStrategy strat);
507 void enterExtendedSpolySig(poly h,poly hSig,kStrategy strat);
508 void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
509 void superenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR = -1);
510 poly kCreateZeroPoly(long exp[], long cabsind, poly* t_p, ring leadRing, ring tailRing);
511 long ind2(long arg);
512 
513 long ind_fact_2(long arg);
514 long twoPow(long arg);
515 ideal createG0();
516 #endif
517 int redLazy (LObject* h,kStrategy strat);
518 int redHomog (LObject* h,kStrategy strat);
519 int redSig (LObject* h,kStrategy strat);
520 int redSigRing (LObject* h,kStrategy strat);
521 //adds hSig to be able to check with F5's criteria when entering pairs!
522 void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
523 void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
524 void entersets (LObject h);
525 void pairs ();
527 void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
528 void messageStat (int hilbcount,kStrategy strat);
529 void messageStatSBA (int hilbcount,kStrategy strat);
530 #ifdef KDEBUG
531 void messageSets (kStrategy strat);
532 #else
533 #define messageSets(s) do {} while (0)
534 #endif
535 
536 void initEcartNormal (TObject* h);
537 void initEcartBBA (TObject* h);
538 void initS (ideal F, ideal Q,kStrategy strat);
539 void initSL (ideal F, ideal Q,kStrategy strat);
540 void initSLSba (ideal F, ideal Q,kStrategy strat);
541 /*************************************************
542  * when initializing a new bunch of principal
543  * syzygies at the beginning of a new iteration
544  * step in a signature-based algorithm we
545  * compute ONLY the leading elements of those
546  * syzygies, NOT the whole syzygy
547  * NOTE: this needs to be adjusted for a more
548  * general approach on signature-based algorithms
549  ***********************************************/
550 void initSyzRules (kStrategy strat);
551 void updateS(BOOLEAN toT,kStrategy strat);
552 void enterSyz (LObject &p,kStrategy strat, int atT);
553 void enterT (LObject &p,kStrategy strat, int atT = -1);
554 #ifdef HAVE_RINGS
555 void enterT_strong (LObject &p,kStrategy strat, int atT = -1);
556 #endif
557 void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
558 void HEckeTest (poly pp,kStrategy strat);
559 void initBuchMoraCrit(kStrategy strat);
560 void initSbaCrit(kStrategy strat);
561 void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
562 void initBuchMoraPos(kStrategy strat);
563 void initBuchMoraPosRing(kStrategy strat);
564 void initSbaPos(kStrategy strat);
565 void initBuchMora (ideal F, ideal Q,kStrategy strat);
566 void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
567 void exitBuchMora (kStrategy strat);
568 void exitSba (kStrategy strat);
569 void updateResult(ideal r,ideal Q,kStrategy strat);
570 void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
571 void kFreeStrat(kStrategy strat);
572 void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
573 void chainCritNormal (poly p,int ecart,kStrategy strat);
574 void chainCritOpt_1 (poly,int,kStrategy strat);
575 void chainCritSig (poly p,int ecart,kStrategy strat);
576 BOOLEAN homogTest(polyset F, int Fmax);
577 BOOLEAN newHEdge(kStrategy strat);
578 BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
579 BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
580 KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
581 BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
582 BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
583 BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
584 BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
585 
586 /// returns index of p in TSet, or -1 if not found
587 int kFindInT(poly p, TSet T, int tlength);
588 
589 /// return -1 if no divisor is found
590 /// number of first divisor in T, otherwise
591 int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start=0);
592 
593 /// return -1 if no divisor is found
594 /// number of first divisor in S, otherwise
595 int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
596 
597 int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
598 TObject* kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject* L, TObject *T, long ecart = LONG_MAX);
599 
600 /***************************************************************
601  *
602  * stuff to be inlined
603  *
604  ***************************************************************/
605 
606 KINLINE TSet initT ();
607 KINLINE TObject** initR();
608 KINLINE unsigned long* initsevT();
609 KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
610 KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
611 KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
612 KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
613 
614 KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
615 KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
616 KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
617 KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
618 
619 // if exp bound is not violated, return TRUE and
620 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
621 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
622 // return FALSE and m1 == NULL, m2 == NULL , otherwise
623 KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
624  poly &m1, poly &m2, const ring m_r);
625 #ifdef HAVE_RINGS
626 KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
627  poly &m1, poly &m2, poly &lcm, const ring taiRing);
628 #endif
629 #ifdef KDEBUG
630 // test strat
631 BOOLEAN kTest(kStrategy strat);
632 // test strat, and test that S is contained in T
633 BOOLEAN kTest_TS(kStrategy strat);
634 // test LObject
635 BOOLEAN kTest_L(LObject* L, ring tailRing = NULL,
636  BOOLEAN testp = FALSE, int lpos = -1,
637  TSet T = NULL, int tlength = -1);
638 // test TObject
639 BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char TN = '?');
640 // test set strat->SevS
641 BOOLEAN kTest_S(kStrategy strat);
642 #else
643 #define kTest(A) (TRUE)
644 #define kTest_TS(A) (TRUE)
645 #define kTest_T(T) (TRUE)
646 #define kTest_S(T) (TRUE)
647 #define kTest_L(T) (TRUE)
648 #endif
649 
650 
651 /***************************************************************
652  *
653  * From kstd2.cc
654  *
655  ***************************************************************/
656 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
657 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
658 ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
659 poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
660 ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
661 poly kNF2Bound (ideal F, ideal Q, poly q,int bound, kStrategy strat, int lazyReduce);
662 ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound, kStrategy strat, int lazyReduce);
663 void initBba(kStrategy strat);
664 void initSba(ideal F,kStrategy strat);
665 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
666  int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
667  intvec *w,intvec *hilb );
668 
669 /***************************************************************
670  *
671  * From kspoly.cc
672  *
673  ***************************************************************/
674 // Reduces PR with PW
675 // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
676 // Changes: PR
677 // Const: PW
678 // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
679 // If strat != NULL, tailRing is changed if reduction would violate exp bound
680 // of tailRing
681 // Returns: 0 everything ok, no tailRing change
682 // 1 tailRing has successfully changed (strat != NULL)
683 // 2 no reduction performed, tailRing needs to be changed first
684 // (strat == NULL)
685 // -1 tailRing change could not be performed due to exceeding exp
686 // bound of currRing
687 int ksReducePoly(LObject* PR,
688  TObject* PW,
689  poly spNoether = NULL,
690  number *coef = NULL,
691  kStrategy strat = NULL);
692 
693 int ksReducePolyBound(LObject* PR,
694  TObject* PW,
695  int bound,
696  poly spNoether = NULL,
697  number *coef = NULL,
698  kStrategy strat = NULL);
699 
700 // Reduces PR with PW
701 // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
702 // Changes: PR
703 // Const: PW
704 // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
705 // If strat != NULL, tailRing is changed if reduction would violate exp bound
706 // of tailRing
707 // Returns: 0 everything ok, no tailRing change
708 // 1 tailRing has successfully changed (strat != NULL)
709 // 2 no reduction performed, tailRing needs to be changed first
710 // (strat == NULL)
711 // 3 no reduction performed, not sig-safe!!!
712 // -1 tailRing change could not be performed due to exceeding exp
713 // bound of currRing
714 int ksReducePolySig(LObject* PR,
715  TObject* PW,
716  long idx,
717  poly spNoether = NULL,
718  number *coef = NULL,
719  kStrategy strat = NULL);
720 
722  TObject* PW,
723  long idx,
724  poly spNoether = NULL,
725  number *coef = NULL,
726  kStrategy strat = NULL);
727 
728 // Reduces PR at Current->next with PW
729 // Assumes PR != NULL, Current contained in PR
730 // Current->next != NULL, LM(PW) devides LM(Current->next)
731 // Changes: PR
732 // Const: PW
733 // Return: see ksReducePoly
734 int ksReducePolyTail(LObject* PR,
735  TObject* PW,
736  poly Current,
737  poly spNoether = NULL);
738 
739 KINLINE int ksReducePolyTail(LObject* PR, TObject* PW, LObject* Red);
740 
741 // Creates S-Poly of Pair
742 // Const: Pair->p1, Pair->p2
743 // Changes: Pair->p == S-Poly of p1, p2
744 // Assume: Pair->p1 != NULL && Pair->p2
745 void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
746  int use_buckets=0, ring tailRing=currRing,
747  poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
748 
749 /*2
750 * creates the leading term of the S-polynomial of p1 and p2
751 * do not destroy p1 and p2
752 * remarks:
753 * 1. the coefficient is 0 (nNew)
754 * 2. pNext is undefined
755 */
756 poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
757 
758 
759 // old stuff
760 KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
761 KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
762 KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
763 KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
764 
765 /***************************************************************
766  *
767  * Routines related for ring changes during std computations
768  *
769  ***************************************************************/
770 // return TRUE and set m1, m2 to k_GetLcmTerms,
771 // if spoly creation of strat->P does not violate
772 // exponent bound of strat->tailRing
773 // FALSE, otherwise
774 BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
775 #ifdef HAVE_RINGS
776 // return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
777 // exponent bound of strat->tailRing
778 // FALSE, otherwise
779 BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
780 poly preIntegerCheck(ideal F, ideal Q);
781 void postReduceByMon(LObject* h, kStrategy strat);
782 void postReduceByMonSig(LObject* h, kStrategy strat);
783 void finalReduceByMon(kStrategy strat);
784 #endif
785 // change strat->tailRing and adjust all data in strat, L, and T:
786 // new tailRing has larger exponent bound
787 // do nothing and return FALSE if exponent bound increase would result in
788 // larger exponent bound that that of currRing
790  LObject* L = NULL, TObject* T = NULL,
791  // take this as new_expbound: if 0
792  // new expbound is 2*expbound of tailRing
793  unsigned long new_expbound = 0);
794 // initiate a change of the tailRing of strat -- should be called
795 // right before main loop in bba
797 
798 /// Output some debug info about a given strategy
799 void kDebugPrint(kStrategy strat);
800 
801 // getting sb order for sba computations
802 ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
803 
804 KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
805  kStrategy strat);
806 
807 #include "kernel/GBEngine/kInline.h"
808 
809 /* shiftgb stuff */
810 #include "kernel/GBEngine/shiftgb.h"
811 
812 poly pMove2CurrTail(poly p, kStrategy strat);
813 
814 poly pMoveCurrTail2poly(poly p, kStrategy strat);
815 
816 poly pCopyL2p(LObject h, kStrategy strat);
817 
818 void enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV);
819 
820 void initBuchMoraShift (ideal F,ideal Q,kStrategy strat);
821 
822 void enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV);
823 
824 void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS, int uptodeg, int lV); // ok
825 
826 void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR,int uptodeg, int lV);
827 
828 void updateSShift(kStrategy strat,int uptodeg,int lV);
829 
830 void initBbaShift(kStrategy strat);
831 
832 poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
833 
834 int redFirstShift (LObject* h,kStrategy strat); // ok
835 
836 ideal freegb(ideal I, int uptodeg, int lVblock);
837 
838 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV);
839 // test syz strategy: // will be removed soon
840 extern int (*test_PosInT)(const TSet T,const int tl,LObject &h);
841 extern int (*test_PosInL)(const LSet set, const int length,
842  LObject* L,const kStrategy strat);
843 
844 static inline void kDeleteLcm(LObject *P)
845 {
846  if (P->lcm!=NULL)
847  {
848  #ifdef HAVE_RINGS
850  pLmDelete(P->lcm);
851  else
852  #endif
853  pLmFree(P->lcm);
854  P->lcm=NULL;
855  }
856 }
857 #endif
KINLINE TObject ** initR()
Definition: kInline.h:92
unsigned long * sevSig
Definition: kutil.h:315
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11585
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11548
KINLINE void Init(ring tailRing=currRing)
Definition: kInline.h:507
int kFindInT(poly p, TSet T, int tlength)
returns index of p in TSet, or -1 if not found
Definition: kutil.cc:704
void deleteHC(poly *p, int *e, int *l, kStrategy strat)
Definition: kutil.cc:318
KINLINE int GetpLength()
Definition: kInline.h:776
int posInLRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6126
denominator_list_s * denominator_list
Definition: kutil.h:59
polyset sig
Definition: kutil.h:299
int posInLSig(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6039
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:275
int nr
Definition: kutil.h:339
char fromT
Definition: kutil.h:373
int j
Definition: facHensel.cc:105
char kHEdgeFound
Definition: kutil.h:370
CFArray copy(const CFList &list)
write elements of list into an array
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1389
void entersets(LObject h)
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
void initSyzRules(kStrategy strat)
Definition: kutil.cc:8205
#define setmaxL
Definition: kutil.h:30
KINLINE void SetShortExpVector()
Definition: kInline.h:703
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
int posInLF5CRing(const LSet set, int start, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6315
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9634
omBin_t * omBin
Definition: omStructs.h:12
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int syzComp
Definition: kutil.h:347
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10203
void initEcartNormal(TObject *h)
Definition: kutil.cc:1257
void enterOnePairSelfShifts(poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int uptodeg, int lV)
Definition: kutil.cc:12062
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7745
KINLINE void Set(ring r=currRing)
Definition: kInline.h:103
KINLINE poly GetP(omBin lmBin=(omBin) NULL)
Definition: kInline.h:665
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:284
int i_r1
Definition: kutil.h:183
int syzmax
Definition: kutil.h:342
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:10899
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1049
kBucket_pt bucket
Definition: kutil.h:182
poly kHEdge
Definition: kutil.h:320
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition: kutil.cc:1624
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5242
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:290
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
class sLObject LObject
Definition: kutil.h:54
TObject * TSet
Definition: kutil.h:55
bool sigdrop
Definition: kutil.h:353
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition: kutil.cc:5052
int posInL15(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6660
wlen_set lenSw
Definition: kutil.h:311
int Ll
Definition: kutil.h:344
#define kTest_S(T)
Definition: kutil.h:646
int sgn(const Rational &a)
Definition: GMPrat.cc:433
KINLINE sLObject & operator=(const sTObject &)
Definition: kInline.h:817
KINLINE poly Next()
Definition: kInline.h:283
#define FALSE
Definition: auxiliary.h:94
unsigned checked
Definition: kutil.h:184
Compatiblity layer for legacy polynomial operations (over currRing)
int * S_2_R
Definition: kutil.h:335
char noTailReduction
Definition: kutil.h:372
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L=NULL, TObject *T=NULL, unsigned long new_expbound=0)
Definition: kutil.cc:11073
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10090
int c3
Definition: kutil.h:340
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, intvec *hilb)
Definition: kstd2.cc:3515
int ksReducePolySig(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:304
BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:6961
poly redtailBbaShift(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kutil.cc:12570
char news
Definition: kutil.h:394
char is_redundant
Definition: kutil.h:84
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5552
poly preIntegerCheck(ideal F, ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition: kutil.cc:10664
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:1589
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition: kstd2.cc:196
int sbaEnterS
Definition: kutil.h:356
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR, int uptodeg, int lV)
Definition: kutil.cc:12492
char newt
Definition: kutil.h:395
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3140
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition: kspoly.cc:998
BOOLEAN * NotUsedAxis
Definition: kutil.h:325
char interpt
Definition: kutil.h:365
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition: kInline.h:931
int(* posInLSba)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:273
KINLINE sLObject(ring tailRing=currRing)
Definition: kInline.h:515
KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:897
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:285
KINLINE void Init(ring r=currRing)
Definition: kInline.h:107
int length
Definition: kutil.h:74
int cv
Definition: kutil.h:363
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7786
KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:881
BOOLEAN * pairtest
Definition: kutil.h:326
poly kNoether
Definition: kutil.h:321
int tl
Definition: kutil.h:343
KINLINE void HeadNormalize()
Definition: kInline.h:345
int Bl
Definition: kutil.h:345
void enterExtendedSpolySig(poly h, poly hSig, kStrategy strat)
Definition: kutil.cc:4603
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:1901
long int64
Definition: auxiliary.h:66
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
void initSbaPos(kStrategy strat)
Definition: kutil.cc:9988
KINLINE void CanonicalizeP()
Definition: kInline.h:339
char noClearS
Definition: kutil.h:396
#define TRUE
Definition: auxiliary.h:98
static void kDeleteLcm(LObject *P)
Definition: kutil.h:844
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:7798
int posInIdealMonFirst(const ideal F, const poly p, int start=0, int end=-1)
Definition: kutil.cc:5129
#define kTest(A)
Definition: kutil.h:643
char LDegLast
Definition: kutil.h:379
poly kCreateZeroPoly(long exp[], long cabsind, poly *t_p, ring leadRing, ring tailRing)
Definition: kutil.cc:4276
pShallowCopyDeleteProc p_shallow_copy_delete
Definition: kutil.h:331
char is_normalized
Definition: kutil.h:78
unsigned long * sevT
Definition: kutil.h:316
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:286
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:278
void enterpairsSig(poly h, poly hSig, int from, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4801
poly pMove2CurrTail(poly p, kStrategy strat)
Definition: kutil.cc:11755
BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat)
Definition: kutil.cc:10641
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4747
int ak
Definition: kutil.h:346
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7864
g
Definition: cfModGcd.cc:4031
poly max_exp
Definition: kutil.h:71
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat, int uptodeg, int lV)
Definition: kstd2.cc:3830
void initHilbCrit(ideal F, ideal Q, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9552
int k
Definition: cfEzgcd.cc:92
KINLINE void pNorm()
Definition: kInline.h:474
int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kstd2.cc:80
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9894
void enterT(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9291
#define Q
Definition: sirandom.c:25
long twoPow(long arg)
Definition: kutil.cc:4087
KINLINE unsigned long * initsevT()
Definition: kInline.h:97
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3353
void initBbaShift(kStrategy strat)
Definition: kstd2.cc:4360
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:545
void enterExtendedSpoly(poly h, kStrategy strat)
Definition: kutil.cc:4520
void initEcartBBA(TObject *h)
Definition: kutil.cc:1265
KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether)
Definition: kInline.h:581
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:269
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define KINLINE
Definition: kutil.h:45
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:467
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:272
char posInLOldFlag
Definition: kutil.h:376
int currIdx
Definition: kutil.h:308
long(* pLDegProc)(poly p, int *length, ring r)
Definition: ring.h:38
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start=0)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:86
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:9970
char length_pLength
Definition: kutil.h:381
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:10831
int minim
Definition: kutil.h:351
int posInLF5C(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6227
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9570
char use_buckets
Definition: kutil.h:377
int Bmax
Definition: kutil.h:345
KINLINE void PrepareRed(BOOLEAN use_bucket)
Definition: kInline.h:531
ideal createG0()
Definition: kutil.cc:4405
int lastAxis
Definition: kutil.h:349
void initSLSba(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8055
BOOLEAN(* syzCrit)(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.h:283
KINLINE void Tail_Mult_nn(number n)
Definition: kInline.h:567
KINLINE void LmDeleteAndIter()
Definition: kInline.h:291
KINLINE void Copy()
Definition: kInline.h:715
KINLINE void SetLmTail(poly lm, poly new_p, int length, int use_bucket, ring r)
Definition: kInline.h:549
skStrategy()
Definition: kutil.cc:11421
char completeReduce_retry
Definition: kutil.h:397
void chainCritSig(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3369
int i_r
Definition: kutil.h:74
KINLINE sTObject(ring tailRing=currRing)
Definition: kInline.h:113
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3287
int HCord
Definition: kutil.h:348
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8823
poly t_p
Definition: kutil.h:70
KINLINE int GetpLength()
Definition: kInline.h:271
pFDegProc pOrigFDeg
Definition: kutil.h:287
KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r=currRing)
Definition: kInline.h:1079
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5212
void(* initEcart)(TObject *L)
Definition: kutil.h:271
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11172
int blockredmax
Definition: kutil.h:359
long ind2(long arg)
Definition: kutil.cc:4060
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:344
poly redNFTail(poly h, const int sl, kStrategy strat)
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether=NULL, ring r=currRing)
Definition: kInline.h:1069
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:281
long ind_fact_2(long arg)
Definition: kutil.cc:4072
KINLINE void Copy()
Definition: kInline.h:202
int lV
Definition: kutil.h:362
int nrsyzcrit
Definition: kutil.h:354
int nrrewcrit
Definition: kutil.h:355
char sugarCrit
Definition: kutil.h:371
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5484
pLDegProc pOrigLDeg
Definition: kutil.h:288
int posInT0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5173
void initEcartPairMora(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1279
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9721
KINLINE TObject * S_2_T(int i)
Definition: kInline.h:35
int posInL10Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
KINLINE long pLDeg()
Definition: kInline.h:731
poly redtail(poly p, int end_pos, kStrategy strat)
Definition: kutil.cc:7391
Definition: intvec.h:17
long FDeg
Definition: kutil.h:73
int posInL17(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6736
#define kTest_TS(A)
Definition: kutil.h:644
char is_sigsafe
Definition: kutil.h:89
int posInL110(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6537
char is_special
Definition: kutil.h:93
int max_lower_index
Definition: kutil.h:309
poly p1
Definition: kutil.h:178
void pairs()
KINLINE void Clear()
Definition: kInline.h:191
KINLINE void LmDeleteAndIter()
Definition: kInline.h:603
char no_prod_crit
Definition: kutil.h:388
intset fromQ
Definition: kutil.h:312
#define messageSets(s)
Definition: kutil.h:533
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:1877
KINLINE BOOLEAN IsNull() const
Definition: kInline.h:266
KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:890
int posInTSig(const TSet set, const int length, LObject &p)
void ksCreateSpoly(LObject *Pair, poly spNoether=NULL, int use_buckets=0, ring tailRing=currRing, poly m1=NULL, poly m2=NULL, TObject **R=NULL)
Definition: kspoly.cc:752
LObject * LSet
Definition: kutil.h:56
KINLINE TObject * T_2(const skStrategy *strat)
Definition: kInline.h:834
KINLINE TSet initT()
Definition: kInline.h:81
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:277
int posInL0(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5981
int ksReducePolySigRing(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:502
void enterSSba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9153
KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin, pShallowCopyDeleteProc p_shallow_copy_delete, BOOLEAN set_max=TRUE)
Definition: kInline.h:359
ideal sba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2251
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4757
#define kTest_L(T)
Definition: kutil.h:647
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:872
void kDebugPrint(kStrategy strat)
Output some debug info about a given strategy.
Definition: kutil.cc:11619
ideal freegb(ideal I, int uptodeg, int lVblock)
Definition: kstd2.cc:4200
void deleteInSSba(int i, kStrategy strat)
Definition: kutil.cc:1121
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4951
int posInLSigRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6063
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:438
KINLINE void SetLmCurrRing()
Definition: kInline.h:277
int m
Definition: cfEzgcd.cc:121
KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kInline.h:1132
LObject P
Definition: kutil.h:293
int HCord
Definition: kutil.cc:235
ideal M
Definition: kutil.h:296
unsigned sbaOrder
Definition: kutil.h:307
poly * polyset
Definition: polys.h:254
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
poly tail
Definition: kutil.h:327
KINLINE void Normalize()
Definition: kInline.h:325
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:279
TObject ** R
Definition: kutil.h:333
poly lcm
Definition: kutil.h:181
KINLINE long Comp()
Definition: kInline.h:808
polyset S
Definition: kutil.h:297
int posInSyz(const kStrategy strat, const poly sig)
Definition: kutil.cc:6199
intset lenS
Definition: kutil.h:310
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4234
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5395
int tmax
Definition: kutil.h:343
void initBuchMoraShift(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:11907
void cleanT(kStrategy strat)
Definition: kutil.cc:537
int cp
Definition: kutil.h:340
KINLINE poly redtailBbaBound(poly p, int end_pos, kStrategy strat, int bound, BOOLEAN normalize=FALSE)
Definition: kInline.h:1093
void enterT_strong(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9372
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5647
KINLINE void pCleardenom()
Definition: kInline.h:436
int posInL11Ringls(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6351
int pLength
Definition: kutil.h:74
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10537
void initEcartPairBba(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1272
poly sig
Definition: kutil.h:68
void cancelunit(LObject *p, BOOLEAN inNF=FALSE)
Definition: kutil.cc:332
Definition: kutil.h:64
intset ecartS
Definition: kutil.h:300
void exitSba(kStrategy strat)
Definition: kutil.cc:10163
poly pMoveCurrTail2poly(poly p, kStrategy strat)
Definition: kutil.cc:11769
poly redtailSba(LObject *L, int end_pos, kStrategy strat, BOOLEAN withT=FALSE, BOOLEAN normalize=FALSE)
Definition: kstd2.cc:1121
poly t_kHEdge
Definition: kutil.h:322
void reorderS(int *suc, kStrategy strat)
Definition: kutil.cc:4898
poly(* pShallowCopyDeleteProc)(poly s_p, ring source_r, ring dest_r, omBin dest_bin)
returns a poly from dest_r which is a ShallowCopy of s_p from source_r assumes that source_r->N == de...
Definition: ring.h:45
KINLINE poly GetLmCurrRing()
Definition: kInline.h:220
s_poly_proc_t s_poly
Definition: kutil.h:291
void initBba(kStrategy strat)
Definition: kstd1.cc:1336
char homog
Definition: kutil.h:366
KINLINE long pTotalDeg() const
Definition: kInline.h:405
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:282
poly p2
Definition: kutil.h:178
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether=NULL)
Definition: kspoly.cc:870
KINLINE poly redtailBba(poly p, int end_pos, kStrategy strat, BOOLEAN normalize=FALSE)
Definition: kInline.h:1087
LSet L
Definition: kutil.h:318
char z2homog
Definition: kutil.h:368
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:475
#define NULL
Definition: omList.c:10
intvec * kHomW
Definition: kutil.h:329
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11494
LSet B
Definition: kutil.h:319
char noetherSet
Definition: kutil.h:374
int Lmax
Definition: kutil.h:344
KINLINE void Mult_nn(number n)
Definition: kInline.h:312
int64 wlen_type
Definition: kutil.h:50
int mu
Definition: kutil.h:341
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9474
void enterpairs(poly h, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4775
void enterOnePairShift(poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS, int uptodeg, int lV)
Definition: kutil.cc:12125
ring tailRing
Definition: kutil.h:336
void updateSShift(kStrategy strat, int uptodeg, int lV)
Definition: kutil.cc:11879
BOOLEAN homogTest(polyset F, int Fmax)
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:39
KINLINE poly GetLmTailRing()
Definition: kInline.h:227
void completeReduce(kStrategy strat, BOOLEAN withT=FALSE)
Definition: kutil.cc:10415
KINLINE long pLDeg()
Definition: kInline.h:420
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1233
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition: kInline.h:1107
KINLINE poly GetTP()
Definition: kInline.h:649
#define R
Definition: sirandom.c:26
denominator_list next
Definition: kutil.h:61
int blockred
Definition: kutil.h:358
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
poly t_kNoether
Definition: kutil.h:324
omBin tailBin
Definition: kutil.h:338
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition: kstd1.h:14
ideal D
Definition: kutil.h:295
const CanonicalForm & w
Definition: facAbsFact.cc:55
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:7129
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5754
char overflow
Definition: kutil.h:398
KINLINE int SetLength(BOOLEAN lengt_pLength=FALSE)
Definition: kInline.h:783
int syzidxmax
Definition: kutil.h:342
intvec * kModW
Definition: kutil.h:328
~skStrategy()
Definition: kutil.cc:11441
unsigned long * sevS
Definition: kutil.h:313
KINLINE long SetDegStuffReturnLDeg()
Definition: kInline.h:424
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1069
BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:7104
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:7045
void enterSBba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9050
intset fromS
Definition: kutil.h:301
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
char honey
Definition: kutil.h:371
unsigned long * sevSyz
Definition: kutil.h:314
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:10988
int posInL10(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd1.cc:1008
denominator_list DENOMINATOR_LIST
Definition: kutil.cc:87
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:324
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
int * intset
Definition: kutil.h:49
KINLINE void Delete()
Definition: kInline.h:500
char update
Definition: kutil.h:375
KINLINE TObject * s_2_t(int i)
Definition: kInline.h:44
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5513
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:265
polyset syz
Definition: kutil.h:298
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1176
Definition: lq.h:39
int sl
Definition: kutil.h:341
int posInL13(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6625
BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start)
TSet T
Definition: kutil.h:317
char posInLDependsOnLength
Definition: kutil.h:383
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10601
int i_r2
Definition: kutil.h:183
wlen_type * wlen_set
Definition: kutil.h:51
omBin lmBin
Definition: kutil.h:337
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart=LONG_MAX)
Definition: kutil.cc:7179
void enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV)
Definition: kutil.cc:12523
KINLINE poly LmExtractAndIter()
Definition: kInline.h:623
char Gebauer
Definition: kutil.h:372
KINLINE poly redtailBba_Z(poly p, int end_pos, kStrategy strat)
Definition: kInline.h:1100
int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd2.cc:81
BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:6996
unsigned long sevSig
Definition: kutil.h:67
void kFreeStrat(kStrategy strat)
int p
Definition: cfModGcd.cc:4019
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3218
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1059
KINLINE poly GetLm(ring r)
Definition: kInline.h:240
void wrp(poly p)
Definition: polys.h:304
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5881
#define kTest_T(T)
Definition: kutil.h:645
int strat_nr
Definition: kstdfac.cc:25
int LazyPass
Definition: kutil.h:346
KINLINE void Clear()
Definition: kInline.h:494
static jList * T
Definition: janet.cc:31
static LSet initL(int nr=setmaxL)
Definition: kutil.h:415
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9807
int newIdeal
Definition: kutil.h:350
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:872
int redNF0(LObject *P, kStrategy strat)
ideal Shdl
Definition: kutil.h:294
BOOLEAN prod_crit
Definition: kutil.h:189
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:270
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5184
static Poly * h
Definition: janet.cc:972
int BOOLEAN
Definition: auxiliary.h:85
int posInL11Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6281
KINLINE long SetpFDeg()
Definition: kInline.h:410
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1242
kStrategy next
Definition: kutil.h:268
KINLINE poly kNoetherTail()
Definition: kInline.h:63
unsigned long sev
Definition: kutil.h:177
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1387
int ecart
Definition: kutil.h:74
KINLINE void T_1_2(const skStrategy *strat, TObject *&T_1, TObject *&T_2)
Definition: kInline.h:845
char redTailChange
Definition: kutil.h:393
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:289
int posInL11(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6239
int syzl
Definition: kutil.h:342
int ksReducePolyBound(LObject *PR, TObject *PW, int bound, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:165
int LazyDegree
Definition: kutil.h:346
int l
Definition: cfEzgcd.cc:93
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:705
KINLINE long SetDegStuffReturnLDeg()
Definition: kInline.h:762
poly pCopyL2p(LObject h, kStrategy strat)
Definition: kutil.cc:11786
class sTObject TObject
Definition: kutil.h:53
ring tailRing
Definition: kutil.h:72
KINLINE void Delete()
Definition: kInline.h:177
void initSL(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7958
poly p
Definition: kutil.h:69
intset syzIdx
Definition: kutil.h:304
KINLINE long MinComp()
Definition: kInline.h:793
KINLINE long pFDeg() const
Definition: kInline.h:400
KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing, poly &m1, poly &m2, poly &lcm, const ring taiRing)
Definition: kInline.h:974
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:41
KINLINE TObject * T_1(const skStrategy *strat)
Definition: kInline.h:824
KINLINE void ShallowCopyDelete(ring new_tailRing, pShallowCopyDeleteProc p_shallow_copy_delete)
Definition: kInline.h:692
ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1)
Definition: kutil.cc:11199
int posInL15Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6695
KINLINE long GetpFDeg() const
Definition: kInline.h:415