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 #ifdef HAVE_OMALLOC
15 #include "omalloc/omallocClass.h"
16 #endif
17 
18 #include "misc/mylimits.h"
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 
79 #ifdef HAVE_SHIFTBBA
80  int shift;
81 #endif
82 
83  /*BOOLEAN*/ char is_normalized; // true, if pNorm was called on p, false otherwise
84  // used in incremental sba() with F5C:
85  // we know some of the redundant elements in
86  // strat->T beforehand, so we can just discard
87  // them and do not need to consider them in the
88  // interreduction process
89  /*BOOLEAN*/ char is_redundant;
90  // used in sba's sig-safe reduction:
91  // sometimes we already know that a reducer
92  // is sig-safe, so no need for a real
93  // sig-safeness check
94  /*BOOLEAN*/ char is_sigsafe;
95 
96 
97 #ifdef HAVE_PLURAL
98  /*BOOLEAN*/ char is_special; // true, it is a new special S-poly (e.g. for SCA)
99 #endif
100 
101  // initialization
102  KINLINE void Init(ring r = currRing);
103  KINLINE sTObject(ring tailRing = currRing);
104  KINLINE sTObject(poly p, ring tailRing = currRing);
105  KINLINE sTObject(poly p, ring c_r, ring tailRing);
106  KINLINE sTObject(sTObject* T, int copy);
107 
108  KINLINE void Set(ring r=currRing);
109  KINLINE void Set(poly p_in, ring r=currRing);
110  KINLINE void Set(poly p_in, ring c_r, ring t_r);
111 
112  // Frees the polys of T
113  KINLINE void Delete();
114  // Sets polys to NULL
115  KINLINE void Clear();
116  // makes a copy of the poly of T
117  KINLINE void Copy();
118 
119  // ring-dependent Lm access: these might result in allocation of monomials
120  KINLINE poly GetLmCurrRing();
121  KINLINE poly GetLmTailRing();
122  KINLINE poly GetLm(ring r);
123  // this returns Lm and ring r (preferably from tailRing), but does not
124  // allocate a new poly
125  KINLINE void GetLm(poly &p, ring &r) const;
126 
127 #ifdef OLIVER_PRIVAT_LT
128  // routines for calc. with rings
129  KINLINE poly GetLtCurrRing();
130  KINLINE poly GetLtTailRing();
131  KINLINE poly GetLt(ring r);
132  KINLINE void GetLt(poly &p, ring &r) const;
133 #endif
134 
135  KINLINE BOOLEAN IsNull() const;
136 
137  KINLINE int GetpLength();
138 
139  // makes sure that T.p exists
140  KINLINE void SetLmCurrRing();
141 
142  // Iterations
143  // simply get the next monomial
144  KINLINE poly Next();
145  KINLINE void LmDeleteAndIter();
146 
147  // deg stuff
148  // compute pTotalDegree
149  KINLINE long pTotalDeg() const;
150  // computes pFDeg
151  KINLINE long pFDeg() const;
152  // computes and sets FDeg
153  KINLINE long SetpFDeg();
154  // gets stored FDeg
155  KINLINE long GetpFDeg() const;
156 
157  // computes pLDeg
158  KINLINE long pLDeg();
159  // sets length, FDeg, returns LDeg
160  KINLINE long SetDegStuffReturnLDeg();
161 
162  // arithmetic
163  KINLINE void Mult_nn(number n);
164  KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin,
165  pShallowCopyDeleteProc p_shallow_copy_delete,
166  BOOLEAN set_max = TRUE);
167  // manipulations
168  KINLINE void pNorm();
169  KINLINE void pCleardenom();
170 
171 #ifdef KDEBUG
172  void wrp();
173 #endif
174 };
175 
176 extern int strat_nr;
177 
178 class sLObject : public sTObject
179 {
180 
181 public:
182  unsigned long sev;
183  poly p1,p2; /*- the pair p comes from,
184  lm(pi) in currRing, tail(pi) in tailring -*/
185 
186  poly lcm; /*- the lcm of p1,p2 -*/
188  int i_r1, i_r2;
189  unsigned checked; // this is the index of S up to which
190  // the corresponding LObject was already checked in
191  // critical pair creation => when entering the
192  // reduction process it is enough to start a second
193  // rewritten criterion check from checked+1 onwards
195  // NOTE: If prod_crit = TRUE then the corresponding pair is
196  // detected by Buchberger's Product Criterion and can be
197  // deleted
198 
199  // initialization
200  KINLINE void Init(ring tailRing = currRing);
201  KINLINE sLObject(ring tailRing = currRing);
202  KINLINE sLObject(poly p, ring tailRing = currRing);
203  KINLINE sLObject(poly p, ring c_r, ring tailRing);
204 
205  // Frees the polys of L
206  KINLINE void Delete();
207  KINLINE void Clear();
208 
209  // Iterations
210  KINLINE void LmDeleteAndIter();
211  KINLINE poly LmExtractAndIter();
212 
213  // spoly related things
214  // preparation for reduction if not spoly
215  KINLINE void PrepareRed(BOOLEAN use_bucket);
216  KINLINE void SetLmTail(poly lm, poly new_p, int length,
217  int use_bucket, ring r);
218  KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
219  KINLINE void Tail_Mult_nn(number n);
220  // deletes bucket, makes sure that p and t_p exists
221  KINLINE poly GetP(omBin lmBin = (omBin)NULL);
222  // similar, except that only t_p exists
223  KINLINE poly GetTP();
224 
225  // does not delete bucket, just canonicalizes it
226  // returned poly is such that Lm(p) \in currRing, Tail(p) \in tailRing
227  KINLINE void CanonicalizeP();
228 
229  // makes a copy of the poly of L
230  KINLINE void Copy();
231 
232  KINLINE int GetpLength();
233  KINLINE long pLDeg(BOOLEAN use_last);
234  KINLINE long pLDeg();
235  KINLINE int SetLength(BOOLEAN lengt_pLength = FALSE);
236  KINLINE long SetDegStuffReturnLDeg();
237  KINLINE long SetDegStuffReturnLDeg(BOOLEAN use_last);
238 
239  // returns minimal component of p
240  KINLINE long MinComp();
241  // returns component of p
242  KINLINE long Comp();
243 
244  KINLINE void ShallowCopyDelete(ring new_tailRing,
245  pShallowCopyDeleteProc p_shallow_copy_delete);
246 
247  // sets sev
248  KINLINE void SetShortExpVector();
249 
250  // enable assignment from TObject
251  KINLINE sLObject& operator=(const sTObject&);
252 
253  // get T's corresponding to p1, p2: they might return NULL
254  KINLINE TObject* T_1(const skStrategy* strat);
255  KINLINE TObject* T_2(const skStrategy* strat);
256  KINLINE void T_1_2(const skStrategy* strat,
257  TObject* &T_1, TObject* &T_2);
258 
259  // simplify coefficients
260  KINLINE void Normalize();
261  KINLINE void HeadNormalize();
262 };
263 
264 
265 extern int HCord;
266 
268 #ifdef HAVE_OMALLOC
269  : public omallocClass
270 #endif
271 {
272 public:
274  int (*red)(LObject * L,kStrategy strat);
275  int (*red2)(LObject * L,kStrategy strat);
276  void (*initEcart)(TObject * L);
277  int (*posInT)(const TSet T,const int tl,LObject &h);
278  int (*posInLSba)(const LSet set, const int length,
279  LObject* L,const kStrategy strat);
280  int (*posInL)(const LSet set, const int length,
281  LObject* L,const kStrategy strat);
282  void (*enterS)(LObject &h, int pos,kStrategy strat, int atR/* =-1*/ );
283  void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
284  int (*posInLOld)(const LSet Ls,const int Ll,
285  LObject* Lo,const kStrategy strat);
286  void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
287  void (*chainCrit) (poly p,int ecart,kStrategy strat);
288  BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
289  BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
290  BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
291  BOOLEAN (*rewCrit3) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
297 
299  ideal Shdl;
300  ideal D; /*V(S) is in D(D)*/
301  ideal M; /*set of minimal generators*/
306  intset fromS; // from which S[i] S[j] comes from
307  // this is important for signature-based
308  // algorithms
309  intset syzIdx;// index in the syz array at which the first
310  // syzygy of component i comes up
311  // important for signature-based algorithms
312  unsigned sbaOrder;
313  int currIdx;
316  wlen_set lenSw; /* for tgb.ccc */
318  unsigned long* sevS;
319  unsigned long* sevSyz;
320  unsigned long* sevSig;
321  unsigned long* sevT;
325  poly kHEdge;
326  poly kNoether;
327  poly t_kHEdge; // same polys in tailring
328  KINLINE poly kNoetherTail();
331  BOOLEAN * pairtest;/*used for enterOnePair*/
332  poly tail;
335  // procedure for ShalloCopy from tailRing to currRing
337  // pointers to Tobjects R[i] is ith Tobject which is generated
339  // S_2_R[i] yields Tobject which corresponds to S[i]
340  int* S_2_R;
341  ring tailRing;
344  int nr;
345  int cp,c3;
346  int sl,mu;
347  int syzl,syzmax,syzidxmax;
348  int tl,tmax;
349  int Ll,Lmax;
350  int Bl,Bmax;
352  int syzComp;
353  int HCord;
354  int lastAxis;
355  int newIdeal;
356  int minim;
357  #ifdef HAVE_RINGS
358  bool sigdrop; //This is used to check sigdrop in sba over Z
359  int nrsyzcrit; // counts how many pairs are deleted by SyzCrit
360  int nrrewcrit; // counts how many pairs are deleted by FaugereRewCrit
361  int sbaEnterS; // sba over Z strategy: if sigdrop element has _*gen(sbaEnterS+1), then
362  // add directly sbaEnterS elements into S
363  int blockred; // counter for blocked reductions in redSig
365  #endif
366  #ifdef HAVE_SHIFTBBA
367  int cv; // in shift bases: counting V criterion
368  #endif
369  /*BOOLEAN*/ char interpt;
370  /*BOOLEAN*/ char homog;
371 #ifdef HAVE_PLURAL
372  /*BOOLEAN*/ char z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
373 #endif
374  /*BOOLEAN*/ char kHEdgeFound;
375  /*BOOLEAN*/ char honey,sugarCrit;
376  /*BOOLEAN*/ char Gebauer,noTailReduction;
377  /*BOOLEAN*/ char fromT;
378  /*BOOLEAN*/ char noetherSet;
379  /*BOOLEAN*/ char update;
380  /*BOOLEAN*/ char posInLOldFlag;
381  /*BOOLEAN*/ char use_buckets;
382  // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
383  /*BOOLEAN*/ char LDegLast;
384  // if set, then L.length == L.pLength
385  /*BOOLEAN*/ char length_pLength;
386  // if set, then posInL does not depend on L.length
387  /*BOOLEAN*/ char posInLDependsOnLength;
388  /*FALSE, if posInL == posInL10*/
389 #ifdef HAVE_PLURAL
390  // set this flag to 1 to stop the product criteria
391  // use ALLOW_PROD_CRIT(strat) to test
392  /*BOOLEAN*/ char no_prod_crit;
393 #define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
394 #else
395 #define ALLOW_PROD_CRIT(A) (1)
396 #endif
398  char news;
399  char newt;/*used for messageSets*/
400  char noClearS;
402  char overflow;
403 
404  skStrategy();
405  ~skStrategy();
406 
407  // return TObject corresponding to S[i]: assume that it exists
408  // i.e. no error checking is done
409  KINLINE TObject* S_2_T(int i);
410  // like S_2_T, except that NULL is returned if it can not be found
411  KINLINE TObject* s_2_t(int i);
412 };
413 
414 void deleteHC(poly *p, int *e, int *l, kStrategy strat);
415 void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
416 void deleteInS (int i,kStrategy strat);
417 void deleteInSSba (int i,kStrategy strat);
418 void cleanT (kStrategy strat);
419 static inline LSet initL (int nr=setmaxL)
420 { return (LSet)omAlloc(nr*sizeof(LObject)); }
421 void deleteInL(LSet set, int *length, int j,kStrategy strat);
422 void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
423 void enterSBba (LObject &p,int atS,kStrategy strat, int atR = -1);
424 void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR = -1);
425 void enterSSba (LObject &p,int atS,kStrategy strat, int atR = -1);
426 void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
427 void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
428 int posInS (const kStrategy strat, const int length, const poly p,
429  const int ecart_p);
430 int posInSMonFirst (const kStrategy strat, const int length, const poly p);
431 int posInIdealMonFirst (const ideal F, const poly p,int start = 0,int end = -1);
432 int posInT0 (const TSet set,const int length,LObject &p);
433 int posInT1 (const TSet set,const int length,LObject &p);
434 int posInT2 (const TSet set,const int length,LObject &p);
435 int posInT11 (const TSet set,const int length,LObject &p);
436 int posInTSig (const TSet set,const int length,LObject &p);
437 int posInT110 (const TSet set,const int length,LObject &p);
438 int posInT13 (const TSet set,const int length,LObject &p);
439 int posInT15 (const TSet set,const int length,LObject &p);
440 int posInT17 (const TSet set,const int length,LObject &p);
441 int posInT17_c (const TSet set,const int length,LObject &p);
442 int posInT19 (const TSet set,const int length,LObject &p);
443 int posInT_EcartpLength(const TSet set,const int length,LObject &p);
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 
448 #ifdef HAVE_MORE_POS_IN_T
449 int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
450 int posInT_FDegpLength(const TSet set,const int length,LObject &p);
451 int posInT_pLength(const TSet set,const int length,LObject &p);
452 #endif
453 
454 
455 void reorderS (int* suc,kStrategy strat);
456 int posInLF5C (const LSet set, const int length,
457  LObject* L,const kStrategy strat);
458 int posInLSig (const LSet set, const int length,
459  LObject* L,const kStrategy strat);
460 int posInLSigRing (const LSet set, const int length,
461  LObject* L,const kStrategy strat);
462 int posInLRing (const LSet set, const int length,
463  LObject* L,const kStrategy strat);
464 int posInSyz (const kStrategy strat, const poly sig);
465 int posInL0 (const LSet set, const int length,
466  LObject* L,const kStrategy strat);
467 int posInL11 (const LSet set, const int length,
468  LObject* L,const kStrategy strat);
469 int posInL11Ring (const LSet set, const int length,
470  LObject* L,const kStrategy strat);
471 int posInLF5CRing (const LSet set, int start , const int length,
472  LObject* L,const kStrategy strat);
473 int posInL11Ringls (const LSet set, const int length,
474  LObject* L,const kStrategy strat);
475 int posInL13 (const LSet set, const int length,
476  LObject* L,const kStrategy strat);
477 int posInL15 (const LSet set, const int length,
478  LObject* L,const kStrategy strat);
479 int posInL15Ring (const LSet set, const int length,
480  LObject* L,const kStrategy strat);
481 int posInL17 (const LSet set, const int length,
482  LObject* L,const kStrategy strat);
483 int posInL10 (const LSet set, const int length,
484  LObject* L,const kStrategy strat);
485 int posInL10Ring (const LSet set, const int length,
486  LObject* L,const kStrategy strat);
487 int posInL110 (const LSet set, const int length,
488  LObject* L,const kStrategy strat);
489 KINLINE poly redtailBba (poly p,int end_pos,kStrategy strat,BOOLEAN normalize=FALSE);
490 KINLINE poly redtailBbaBound (poly p,int end_pos,kStrategy strat,int bound,BOOLEAN normalize=FALSE);
491 #ifdef HAVE_RINGS
492 KINLINE poly redtailBba_Z (poly p,int end_pos,kStrategy strat);
493 poly redtailBba_Z (LObject* L, int end_pos, kStrategy strat );
494 void redtailBbaAlsoLC_Z (LObject* L, int end_pos, kStrategy strat );
495 #endif
496 poly redtailBba (LObject *L, int end_pos,kStrategy strat,
498 poly redtailBbaBound (LObject *L, int end_pos,kStrategy strat,int bound,
500 poly redtailSba (LObject *L, int end_pos,kStrategy strat,
502 poly redtailBba (TObject *T, int end_pos,kStrategy strat);
503 poly redtail (poly p,int end_pos,kStrategy strat);
504 poly redtail (LObject *L,int end_pos,kStrategy strat);
505 poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
506 int redNF0 (LObject *P,kStrategy strat);
507 poly redNFTail (poly h,const int sl,kStrategy strat);
508 int redHoney (LObject* h, kStrategy strat);
509 #ifdef HAVE_RINGS
510 int redRing (LObject* h,kStrategy strat);
511 int redRing_Z (LObject* h,kStrategy strat);
512 int redRiloc (LObject* h,kStrategy strat);
513 void enterExtendedSpoly(poly h,kStrategy strat);
514 void enterExtendedSpolySig(poly h,poly hSig,kStrategy strat);
515 void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
516 void superenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR = -1);
517 poly kCreateZeroPoly(long exp[], long cabsind, poly* t_p, ring leadRing, ring tailRing);
518 long ind2(long arg);
519 
520 long ind_fact_2(long arg);
521 long twoPow(long arg);
522 ideal createG0();
523 #endif
524 int redLazy (LObject* h,kStrategy strat);
525 int redHomog (LObject* h,kStrategy strat);
526 int redSig (LObject* h,kStrategy strat);
527 int redSigRing (LObject* h,kStrategy strat);
528 //adds hSig to be able to check with F5's criteria when entering pairs!
529 void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
530 void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
531 void entersets (LObject h);
532 void pairs ();
534 void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
535 void messageStat (int hilbcount,kStrategy strat);
536 void messageStatSBA (int hilbcount,kStrategy strat);
537 #ifdef KDEBUG
538 void messageSets (kStrategy strat);
539 #else
540 #define messageSets(s) do {} while (0)
541 #endif
542 
543 void initEcartNormal (TObject* h);
544 void initEcartBBA (TObject* h);
545 void initS (ideal F, ideal Q,kStrategy strat);
546 void initSL (ideal F, ideal Q,kStrategy strat);
547 void initSLSba (ideal F, ideal Q,kStrategy strat);
548 /*************************************************
549  * when initializing a new bunch of principal
550  * syzygies at the beginning of a new iteration
551  * step in a signature-based algorithm we
552  * compute ONLY the leading elements of those
553  * syzygies, NOT the whole syzygy
554  * NOTE: this needs to be adjusted for a more
555  * general approach on signature-based algorithms
556  ***********************************************/
557 void initSyzRules (kStrategy strat);
558 void updateS(BOOLEAN toT,kStrategy strat);
559 void enterSyz (LObject &p,kStrategy strat, int atT);
560 void enterT (LObject &p,kStrategy strat, int atT = -1);
561 void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat);
562 #ifdef HAVE_RINGS
563 void enterT_strong (LObject &p,kStrategy strat, int atT = -1);
564 #endif
565 void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
566 void HEckeTest (poly pp,kStrategy strat);
567 void initBuchMoraCrit(kStrategy strat);
568 void initSbaCrit(kStrategy strat);
569 void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
570 void initBuchMoraPos(kStrategy strat);
571 void initBuchMoraPosRing(kStrategy strat);
572 void initSbaPos(kStrategy strat);
573 void initBuchMora (ideal F, ideal Q,kStrategy strat);
574 void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
575 void exitBuchMora (kStrategy strat);
576 void exitSba (kStrategy strat);
577 void updateResult(ideal r,ideal Q,kStrategy strat);
578 void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
579 void kFreeStrat(kStrategy strat);
580 void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
581 void chainCritNormal (poly p,int ecart,kStrategy strat);
582 void chainCritOpt_1 (poly,int,kStrategy strat);
583 void chainCritSig (poly p,int ecart,kStrategy strat);
584 BOOLEAN homogTest(polyset F, int Fmax);
585 BOOLEAN newHEdge(kStrategy strat);
586 BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
587 BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
588 KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
589 BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
590 BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
591 BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
592 BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
593 
594 /// returns index of p in TSet, or -1 if not found
595 int kFindInT(poly p, TSet T, int tlength);
596 
597 /// return -1 if no divisor is found
598 /// number of first divisor in T, otherwise
599 int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start=0);
600 int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start=0);
601 int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start=0);
602 
603 /// return -1 if no divisor is found
604 /// number of first divisor in S, otherwise
605 int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
606 
607 int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
608 TObject* kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject* L, TObject *T, long ecart = LONG_MAX);
609 
610 /***************************************************************
611  *
612  * stuff to be inlined
613  *
614  ***************************************************************/
615 
616 KINLINE TSet initT ();
617 KINLINE TObject** initR();
618 KINLINE unsigned long* initsevT();
619 KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
620 KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
621 KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
622 KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
623 
624 KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
625 KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
626 KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
627 KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
628 
629 // if exp bound is not violated, return TRUE and
630 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
631 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
632 // return FALSE and m1 == NULL, m2 == NULL , otherwise
633 KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
634  poly &m1, poly &m2, const ring m_r);
635 #ifdef HAVE_RINGS
636 KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
637  poly &m1, poly &m2, poly &lcm, const ring taiRing);
638 #endif
639 #ifdef KDEBUG
640 // test strat
641 BOOLEAN kTest(kStrategy strat);
642 // test strat, and test that S is contained in T
643 BOOLEAN kTest_TS(kStrategy strat);
644 // test LObject
645 BOOLEAN kTest_L(LObject* L, ring tailRing,
646  BOOLEAN testp = FALSE, int lpos = -1,
647  TSet T = NULL, int tlength = -1);
648 // test TObject
649 BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char TN = '?');
650 // test set strat->SevS
651 BOOLEAN kTest_S(kStrategy strat);
652 #else
653 #define kTest(A) (TRUE)
654 #define kTest_TS(A) (TRUE)
655 #define kTest_T(T) (TRUE)
656 #define kTest_S(T) (TRUE)
657 #define kTest_L(T,R) (TRUE)
658 #endif
659 
660 
661 /***************************************************************
662  *
663  * From kstd2.cc
664  *
665  ***************************************************************/
666 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
667 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
668 ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
669 poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
670 ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
671 poly kNF2Bound (ideal F, ideal Q, poly q,int bound, kStrategy strat, int lazyReduce);
672 ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound, kStrategy strat, int lazyReduce);
673 void initBba(kStrategy strat);
674 void initSba(ideal F,kStrategy strat);
675 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
676  int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
677  intvec *w,intvec *hilb );
678 
679 /***************************************************************
680  *
681  * From kspoly.cc
682  *
683  ***************************************************************/
684 // Reduces PR with PW
685 // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
686 // Changes: PR
687 // Const: PW
688 // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
689 // If strat != NULL, tailRing is changed if reduction would violate exp bound
690 // of tailRing
691 // Returns: 0 everything ok, no tailRing change
692 // 1 tailRing has successfully changed (strat != NULL)
693 // 2 no reduction performed, tailRing needs to be changed first
694 // (strat == NULL)
695 // -1 tailRing change could not be performed due to exceeding exp
696 // bound of currRing
697 int ksReducePoly(LObject* PR,
698  TObject* PW,
699  poly spNoether = NULL,
700  number *coef = NULL,
701  kStrategy strat = NULL);
702 
703 /* like ksReducePoly, but if the reducer has only 1 term we still
704  * compute a possible coefficient multiplier for PR. this comes from
705  * a special situation in redRing_Z and it is used only there. */
706 int ksReducePolyZ(LObject* PR,
707  TObject* PW,
708  poly spNoether = NULL,
709  number *coef = NULL,
710  kStrategy strat = NULL);
711 
712 int ksReducePolyLC(LObject* PR,
713  TObject* PW,
714  poly spNoether = NULL,
715  number *coef = NULL,
716  kStrategy strat = NULL);
717 
718 
719 int ksReducePolyGCD(LObject* PR,
720  TObject* PW,
721  poly spNoether = NULL,
722  number *coef = NULL,
723  kStrategy strat = NULL);
724 
725 int ksReducePolyBound(LObject* PR,
726  TObject* PW,
727  int bound,
728  poly spNoether = NULL,
729  number *coef = NULL,
730  kStrategy strat = NULL);
731 
732 // Reduces PR with PW
733 // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
734 // Changes: PR
735 // Const: PW
736 // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
737 // If strat != NULL, tailRing is changed if reduction would violate exp bound
738 // of tailRing
739 // Returns: 0 everything ok, no tailRing change
740 // 1 tailRing has successfully changed (strat != NULL)
741 // 2 no reduction performed, tailRing needs to be changed first
742 // (strat == NULL)
743 // 3 no reduction performed, not sig-safe!!!
744 // -1 tailRing change could not be performed due to exceeding exp
745 // bound of currRing
746 int ksReducePolySig(LObject* PR,
747  TObject* PW,
748  long idx,
749  poly spNoether = NULL,
750  number *coef = NULL,
751  kStrategy strat = NULL);
752 
754  TObject* PW,
755  long idx,
756  poly spNoether = NULL,
757  number *coef = NULL,
758  kStrategy strat = NULL);
759 
760 // Reduces PR at Current->next with PW
761 // Assumes PR != NULL, Current contained in PR
762 // Current->next != NULL, LM(PW) devides LM(Current->next)
763 // Changes: PR
764 // Const: PW
765 // Return: see ksReducePoly
766 int ksReducePolyTail(LObject* PR,
767  TObject* PW,
768  poly Current,
769  poly spNoether = NULL);
770 
771 KINLINE int ksReducePolyTail(LObject* PR, TObject* PW, LObject* Red);
772 
773 // Creates S-Poly of Pair
774 // Const: Pair->p1, Pair->p2
775 // Changes: Pair->p == S-Poly of p1, p2
776 // Assume: Pair->p1 != NULL && Pair->p2
777 void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
778  int use_buckets=0, ring tailRing=currRing,
779  poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
780 
781 /*2
782 * creates the leading term of the S-polynomial of p1 and p2
783 * do not destroy p1 and p2
784 * remarks:
785 * 1. the coefficient is 0 (nNew)
786 * 2. pNext is undefined
787 */
788 poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
789 
790 
791 // old stuff
792 KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
793 KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
794 KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
795 KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
796 
797 /***************************************************************
798  *
799  * Routines related for ring changes during std computations
800  *
801  ***************************************************************/
802 // return TRUE and set m1, m2 to k_GetLcmTerms,
803 // if spoly creation of strat->P does not violate
804 // exponent bound of strat->tailRing
805 // FALSE, otherwise
806 BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
807 #ifdef HAVE_RINGS
808 // return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
809 // exponent bound of strat->tailRing
810 // FALSE, otherwise
811 BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
812 poly preIntegerCheck(ideal F, ideal Q);
813 void postReduceByMon(LObject* h, kStrategy strat);
814 void postReduceByMonSig(LObject* h, kStrategy strat);
815 void finalReduceByMon(kStrategy strat);
816 #endif
817 // change strat->tailRing and adjust all data in strat, L, and T:
818 // new tailRing has larger exponent bound
819 // do nothing and return FALSE if exponent bound increase would result in
820 // larger exponent bound that that of currRing
822  LObject* L = NULL, TObject* T = NULL,
823  // take this as new_expbound: if 0
824  // new expbound is 2*expbound of tailRing
825  unsigned long new_expbound = 0);
826 // initiate a change of the tailRing of strat -- should be called
827 // right before main loop in bba
829 
830 /// Output some debug info about a given strategy
831 void kDebugPrint(kStrategy strat);
832 
833 // getting sb order for sba computations
834 ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
835 
836 KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
837  kStrategy strat);
838 
839 #include "kernel/GBEngine/kInline.h"
840 
841 /* shiftgb stuff */
842 #include "kernel/GBEngine/shiftgb.h"
843 
844 poly pMove2CurrTail(poly p, kStrategy strat);
845 
846 poly pMoveCurrTail2poly(poly p, kStrategy strat);
847 
848 poly pCopyL2p(LObject h, kStrategy strat);
849 
850 void enterTShift(LObject p, kStrategy strat, int atT = -1);
851 
852 void initBuchMoraShift (ideal F,ideal Q,kStrategy strat);
853 
854 void enterOnePairSelfShifts (poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR);
855 
856 void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS);
857 
858 void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
859 
860 void updateSShift(kStrategy strat);
861 
862 void initBbaShift(kStrategy strat);
863 
864 poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
865 
866 int redFirstShift (LObject* h,kStrategy strat); // ok
867 
868 ideal freegb(ideal I);
869 
870 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
871 // test syz strategy: // will be removed soon
872 extern int (*test_PosInT)(const TSet T,const int tl,LObject &h);
873 extern int (*test_PosInL)(const LSet set, const int length,
874  LObject* L,const kStrategy strat);
875 
876 static inline void kDeleteLcm(LObject *P)
877 {
878  if (P->lcm!=NULL)
879  {
880  #ifdef HAVE_RINGS
882  pLmDelete(P->lcm);
883  else
884  #endif
885  pLmFree(P->lcm);
886  P->lcm=NULL;
887  }
888 }
889 #endif
KINLINE TObject ** initR()
Definition: kInline.h:95
unsigned long * sevSig
Definition: kutil.h:320
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11889
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11852
int kFindInT(poly p, TSet T, int tlength)
returns index of p in TSet, or -1 if not found
Definition: kutil.cc:711
void deleteHC(poly *p, int *e, int *l, kStrategy strat)
Definition: kutil.cc:319
int posInLRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6210
denominator_list_s * denominator_list
Definition: kutil.h:59
polyset sig
Definition: kutil.h:304
int posInLSig(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6123
static number Copy(number a, const coeffs r)
Definition: flintcf_Q.cc:200
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:431
int nr
Definition: kutil.h:344
char fromT
Definition: kutil.h:377
int j
Definition: facHensel.cc:105
char kHEdgeFound
Definition: kutil.h:374
void updateSShift(kStrategy strat)
Definition: kutil.cc:12183
CFArray copy(const CFList &list)
write elements of list into an array
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1390
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:1026
void initSyzRules(kStrategy strat)
Definition: kutil.cc:8416
#define setmaxL
Definition: kutil.h:30
int posInLF5CRing(const LSet set, int start, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6399
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9938
omBin_t * omBin
Definition: omStructs.h:12
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int syzComp
Definition: kutil.h:352
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10507
void mu(int **points, int sizePoints)
void initEcartNormal(TObject *h)
Definition: kutil.cc:1284
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7954
int syzmax
Definition: kutil.h:347
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:11203
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1120
kBucket_pt bucket
Definition: kutil.h:187
poly kHEdge
Definition: kutil.h:325
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition: kutil.cc:1676
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5326
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:295
void enterTShift(LObject p, kStrategy strat, int atT=-1)
Definition: kutil.cc:12759
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
class sLObject LObject
Definition: kutil.h:54
TObject * TSet
Definition: kutil.h:55
bool sigdrop
Definition: kutil.h:358
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition: kutil.cc:5136
int posInL15(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6744
wlen_set lenSw
Definition: kutil.h:316
#define kTest_S(T)
Definition: kutil.h:656
int sgn(const Rational &a)
Definition: GMPrat.cc:430
#define FALSE
Definition: auxiliary.h:94
unsigned checked
Definition: kutil.h:189
Compatiblity layer for legacy polynomial operations (over currRing)
int * S_2_R
Definition: kutil.h:340
char noTailReduction
Definition: kutil.h:376
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L=NULL, TObject *T=NULL, unsigned long new_expbound=0)
Definition: kutil.cc:11377
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10394
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:3848
int ksReducePolySig(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:682
BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:7045
poly redtailBbaShift(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kutil.cc:12782
char news
Definition: kutil.h:398
char is_redundant
Definition: kutil.h:89
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5636
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:10968
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:1866
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:326
int sbaEnterS
Definition: kutil.h:361
char newt
Definition: kutil.h:399
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3192
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4163
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition: kspoly.cc:1390
BOOLEAN * NotUsedAxis
Definition: kutil.h:330
char interpt
Definition: kutil.h:369
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:964
KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:930
int cv
Definition: kutil.h:367
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7995
KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:914
BOOLEAN * pairtest
Definition: kutil.h:331
poly kNoether
Definition: kutil.h:326
void enterExtendedSpolySig(poly h, poly hSig, kStrategy strat)
Definition: kutil.cc:4687
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2178
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:10292
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:568
char noClearS
Definition: kutil.h:400
#define TRUE
Definition: auxiliary.h:98
static void kDeleteLcm(LObject *P)
Definition: kutil.h:876
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:8008
int posInIdealMonFirst(const ideal F, const poly p, int start=0, int end=-1)
Definition: kutil.cc:5213
#define kTest(A)
Definition: kutil.h:653
char LDegLast
Definition: kutil.h:383
poly kCreateZeroPoly(long exp[], long cabsind, poly *t_p, ring leadRing, ring tailRing)
Definition: kutil.cc:4327
pShallowCopyDeleteProc p_shallow_copy_delete
Definition: kutil.h:336
char is_normalized
Definition: kutil.h:83
unsigned long * sevT
Definition: kutil.h:321
void enterpairsSig(poly h, poly hSig, int from, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4885
void enterOnePairSelfShifts(poly qq, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:12337
poly pMove2CurrTail(poly p, kStrategy strat)
Definition: kutil.cc:12059
BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat)
Definition: kutil.cc:10945
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4831
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8075
g
Definition: cfModGcd.cc:4031
poly max_exp
Definition: kutil.h:71
void initHilbCrit(ideal F, ideal Q, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9856
int k
Definition: cfEzgcd.cc:92
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:10198
void enterT(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9576
#define Q
Definition: sirandom.c:25
long twoPow(long arg)
Definition: kutil.cc:4138
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3405
void initBbaShift(kStrategy strat)
Definition: kstd2.cc:4593
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:822
void enterExtendedSpoly(poly h, kStrategy strat)
Definition: kutil.cc:4604
void initEcartBBA(TObject *h)
Definition: kutil.cc:1292
#define omAlloc(size)
Definition: omAllocDecl.h:210
ideal freegb(ideal I)
Definition: kstd2.cc:4459
#define KINLINE
Definition: kutil.h:45
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:468
char posInLOldFlag
Definition: kutil.h:380
int currIdx
Definition: kutil.h:313
long(* pLDegProc)(poly p, int *length, ring r)
Definition: ring.h:37
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:216
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10274
char length_pLength
Definition: kutil.h:385
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:11135
int minim
Definition: kutil.h:356
int posInLF5C(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6311
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9874
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:315
char use_buckets
Definition: kutil.h:381
int Bmax
Definition: kutil.h:350
ideal createG0()
Definition: kutil.cc:4456
int lastAxis
Definition: kutil.h:354
void initSLSba(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8266
char completeReduce_retry
Definition: kutil.h:401
void chainCritSig(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3421
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3596
int HCord
Definition: kutil.h:353
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:9034
poly t_p
Definition: kutil.h:70
pFDegProc pOrigFDeg
Definition: kutil.h:292
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:44
KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r=currRing)
Definition: kInline.h:1150
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5296
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11476
int blockredmax
Definition: kutil.h:364
long ind2(long arg)
Definition: kutil.cc:4111
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:342
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:1140
int shift
Definition: kutil.h:80
long ind_fact_2(long arg)
Definition: kutil.cc:4123
int LazyDegree
int nrsyzcrit
Definition: kutil.h:359
int nrrewcrit
Definition: kutil.h:360
char sugarCrit
Definition: kutil.h:375
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5568
pLDegProc pOrigLDeg
Definition: kutil.h:293
int posInT0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5257
void initEcartPairMora(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1306
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:10025
int posInL10Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
poly redtail(poly p, int end_pos, kStrategy strat)
Definition: kutil.cc:7475
Definition: intvec.h:19
long FDeg
Definition: kutil.h:73
int posInL17(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6820
#define kTest_TS(A)
Definition: kutil.h:654
char is_sigsafe
Definition: kutil.h:94
int posInL110(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6621
static void Normalize(number &a, const coeffs r)
Definition: flintcf_Q.cc:314
char is_special
Definition: kutil.h:98
int max_lower_index
Definition: kutil.h:314
void pairs()
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:12728
char no_prod_crit
Definition: kutil.h:392
intset fromQ
Definition: kutil.h:317
#define messageSets(s)
Definition: kutil.h:540
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:1929
KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:923
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:1145
LObject * LSet
Definition: kutil.h:56
KINLINE TSet initT()
Definition: kInline.h:84
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
#define kTest_L(T, R)
Definition: kutil.h:657
int posInL0(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6065
int ksReducePolySigRing(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:885
void enterSSba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9380
ideal sba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2536
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4841
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start=0)
Definition: kstd2.cc:139
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1149
void kDebugPrint(kStrategy strat)
Output some debug info about a given strategy.
Definition: kutil.cc:11923
void deleteInSSba(int i, kStrategy strat)
Definition: kutil.cc:1148
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5035
int posInLSigRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6147
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:715
int m
Definition: cfEzgcd.cc:121
KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kInline.h:1203
LObject P
Definition: kutil.h:298
int HCord
Definition: kutil.cc:236
ideal M
Definition: kutil.h:301
unsigned sbaOrder
Definition: kutil.h:312
poly * polyset
Definition: polys.h:254
FILE * f
Definition: checklibs.c:9
void enterOnePairShift(poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS)
Definition: kutil.cc:12361
int i
Definition: cfEzgcd.cc:125
poly tail
Definition: kutil.h:332
TObject ** R
Definition: kutil.h:338
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7711
poly lcm
Definition: kutil.h:186
polyset S
Definition: kutil.h:302
int posInSyz(const kStrategy strat, const poly sig)
Definition: kutil.cc:6283
intset lenS
Definition: kutil.h:315
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4473
static void Delete(number *a, const coeffs r)
Definition: flintcf_Q.cc:408
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5479
int tmax
Definition: kutil.h:348
void initBuchMoraShift(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:12211
void cleanT(kStrategy strat)
Definition: kutil.cc:538
int cp
Definition: kutil.h:345
KINLINE poly redtailBbaBound(poly p, int end_pos, kStrategy strat, int bound, BOOLEAN normalize=FALSE)
Definition: kInline.h:1164
void enterT_strong(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9676
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5731
int posInL11Ringls(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6435
int pLength
Definition: kutil.h:74
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10841
void initEcartPairBba(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1299
poly sig
Definition: kutil.h:68
void cancelunit(LObject *p, BOOLEAN inNF=FALSE)
Definition: kutil.cc:333
Definition: kutil.h:64
static number Init(long i, const coeffs r)
Definition: flintcf_Q.cc:116
intset ecartS
Definition: kutil.h:305
void exitSba(kStrategy strat)
Definition: kutil.cc:10467
poly pMoveCurrTail2poly(poly p, kStrategy strat)
Definition: kutil.cc:12073
poly redtailSba(LObject *L, int end_pos, kStrategy strat, BOOLEAN withT=FALSE, BOOLEAN normalize=FALSE)
Definition: kstd2.cc:1398
poly t_kHEdge
Definition: kutil.h:327
void reorderS(int *suc, kStrategy strat)
Definition: kutil.cc:4982
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:44
s_poly_proc_t s_poly
Definition: kutil.h:296
void initBba(kStrategy strat)
Definition: kstd1.cc:1334
char homog
Definition: kutil.h:370
poly p2
Definition: kutil.h:183
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether=NULL)
Definition: kspoly.cc:1290
KINLINE poly redtailBba(poly p, int end_pos, kStrategy strat, BOOLEAN normalize=FALSE)
Definition: kInline.h:1158
LSet L
Definition: kutil.h:323
char z2homog
Definition: kutil.h:372
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:479
#define NULL
Definition: omList.c:12
intvec * kHomW
Definition: kutil.h:334
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11798
LSet B
Definition: kutil.h:324
char noetherSet
Definition: kutil.h:378
int Lmax
Definition: kutil.h:349
int64 wlen_type
Definition: kutil.h:50
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition: kutil.cc:9515
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9778
void enterpairs(poly h, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4859
ring tailRing
Definition: kutil.h:341
BOOLEAN homogTest(polyset F, int Fmax)
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:38
void completeReduce(kStrategy strat, BOOLEAN withT=FALSE)
Definition: kutil.cc:10719
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1260
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition: kInline.h:1178
#define R
Definition: sirandom.c:26
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:358
denominator_list next
Definition: kutil.h:61
int blockred
Definition: kutil.h:363
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
poly t_kNoether
Definition: kutil.h:329
omBin tailBin
Definition: kutil.h:343
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition: kstd1.h:14
ideal D
Definition: kutil.h:300
const CanonicalForm & w
Definition: facAbsFact.cc:55
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:7213
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5838
char overflow
Definition: kutil.h:402
intvec * kModW
Definition: kutil.h:333
unsigned long * sevS
Definition: kutil.h:318
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1096
BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:7188
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:7129
void enterSBba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9261
intset fromS
Definition: kutil.h:306
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
unsigned long * sevSyz
Definition: kutil.h:319
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start=0)
Definition: kstd2.cc:84
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11292
int posInL10(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd1.cc:1006
denominator_list DENOMINATOR_LIST
Definition: kutil.cc:88
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:454
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
char update
Definition: kutil.h:379
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5597
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:395
polyset syz
Definition: kutil.h:303
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1203
Definition: lq.h:39
int sl
Definition: kutil.h:346
int posInL13(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6709
BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start)
TSet T
Definition: kutil.h:322
char posInLDependsOnLength
Definition: kutil.h:387
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10905
int i_r2
Definition: kutil.h:188
wlen_type * wlen_set
Definition: kutil.h:51
omBin lmBin
Definition: kutil.h:342
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart=LONG_MAX)
Definition: kutil.cc:7263
KINLINE poly redtailBba_Z(poly p, int end_pos, kStrategy strat)
Definition: kInline.h:1171
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:7080
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:3503
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1130
void wrp(poly p)
Definition: polys.h:305
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5965
#define kTest_T(T)
Definition: kutil.h:655
int strat_nr
Definition: kstdfac.cc:21
int LazyPass
Definition: kutil.h:351
static jList * T
Definition: janet.cc:30
static LSet initL(int nr=setmaxL)
Definition: kutil.h:419
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:10111
int newIdeal
Definition: kutil.h:355
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:905
int redNF0(LObject *P, kStrategy strat)
ideal Shdl
Definition: kutil.h:299
BOOLEAN prod_crit
Definition: kutil.h:194
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5268
static Poly * h
Definition: janet.cc:971
int BOOLEAN
Definition: auxiliary.h:85
int posInL11Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6365
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1519
kStrategy next
Definition: kutil.h:273
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9361
unsigned long sev
Definition: kutil.h:182
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1664
char redTailChange
Definition: kutil.h:397
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:294
int posInL11(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6323
int ksReducePolyBound(LObject *PR, TObject *PW, int bound, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:538
int l
Definition: cfEzgcd.cc:93
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:982
poly pCopyL2p(LObject h, kStrategy strat)
Definition: kutil.cc:12090
class sTObject TObject
Definition: kutil.h:53
ring tailRing
Definition: kutil.h:72
void initSL(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8169
poly p
Definition: kutil.h:69
intset syzIdx
Definition: kutil.h:309
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:1007
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:185
ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1)
Definition: kutil.cc:11503
int posInL15Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6779