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 
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 
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  /*BOOLEAN*/ char rightGB;
369  #endif
370  /*BOOLEAN*/ char interpt;
371  /*BOOLEAN*/ char homog;
372 #ifdef HAVE_PLURAL
373  /*BOOLEAN*/ char z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
374 #endif
375  /*BOOLEAN*/ char kHEdgeFound;
376  /*BOOLEAN*/ char honey,sugarCrit;
377  /*BOOLEAN*/ char Gebauer,noTailReduction;
378  /*BOOLEAN*/ char fromT;
379  /*BOOLEAN*/ char noetherSet;
380  /*BOOLEAN*/ char update;
381  /*BOOLEAN*/ char posInLOldFlag;
382  /*BOOLEAN*/ char use_buckets;
383  // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
384  /*BOOLEAN*/ char LDegLast;
385  // if set, then L.length == L.pLength
386  /*BOOLEAN*/ char length_pLength;
387  // if set, then posInL does not depend on L.length
388  /*BOOLEAN*/ char posInLDependsOnLength;
389  /*FALSE, if posInL == posInL10*/
390 #ifdef HAVE_PLURAL
391  // set this flag to 1 to stop the product criteria
392  // use ALLOW_PROD_CRIT(strat) to test
393  /*BOOLEAN*/ char no_prod_crit;
394 #define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
395 #else
396 #define ALLOW_PROD_CRIT(A) (1)
397 #endif
399  char news;
400  char newt;/*used for messageSets*/
401  char noClearS;
403  char overflow;
404 
405  skStrategy();
406  ~skStrategy();
407 
408  // return TObject corresponding to S[i]: assume that it exists
409  // i.e. no error checking is done
410  KINLINE TObject* S_2_T(int i);
411  // like S_2_T, except that NULL is returned if it can not be found
412  KINLINE TObject* s_2_t(int i);
413 };
414 
415 void deleteHC(poly *p, int *e, int *l, kStrategy strat);
416 void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
417 void deleteInS (int i,kStrategy strat);
418 void deleteInSSba (int i,kStrategy strat);
419 void cleanT (kStrategy strat);
420 static inline LSet initL (int nr=setmaxL)
421 { return (LSet)omAlloc(nr*sizeof(LObject)); }
422 void deleteInL(LSet set, int *length, int j,kStrategy strat);
423 void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
424 void enterSBba (LObject &p,int atS,kStrategy strat, int atR = -1);
425 void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR = -1);
426 void enterSSba (LObject &p,int atS,kStrategy strat, int atR = -1);
427 void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
428 void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
429 int posInS (const kStrategy strat, const int length, const poly p,
430  const int ecart_p);
431 int posInSMonFirst (const kStrategy strat, const int length, const poly p);
432 int posInIdealMonFirst (const ideal F, const poly p,int start = 0,int end = -1);
433 int posInT0 (const TSet set,const int length,LObject &p);
434 int posInT1 (const TSet set,const int length,LObject &p);
435 int posInT2 (const TSet set,const int length,LObject &p);
436 int posInT11 (const TSet set,const int length,LObject &p);
437 int posInTSig (const TSet set,const int length,LObject &p);
438 int posInT110 (const TSet set,const int length,LObject &p);
439 int posInT13 (const TSet set,const int length,LObject &p);
440 int posInT15 (const TSet set,const int length,LObject &p);
441 int posInT17 (const TSet set,const int length,LObject &p);
442 int posInT17_c (const TSet set,const int length,LObject &p);
443 int posInT19 (const TSet set,const int length,LObject &p);
444 int posInT_EcartpLength(const TSet set,const int length,LObject &p);
445 int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
446 int posInT_FDegpLength(const TSet set,const int length,LObject &p);
447 int posInT_pLength(const TSet set,const int length,LObject &p);
448 
449 #ifdef HAVE_MORE_POS_IN_T
450 int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
451 int posInT_FDegpLength(const TSet set,const int length,LObject &p);
452 int posInT_pLength(const TSet set,const int length,LObject &p);
453 #endif
454 
455 
456 void reorderS (int* suc,kStrategy strat);
457 int posInLF5C (const LSet set, const int length,
458  LObject* L,const kStrategy strat);
459 int posInLSig (const LSet set, const int length,
460  LObject* L,const kStrategy strat);
461 int posInLSigRing (const LSet set, const int length,
462  LObject* L,const kStrategy strat);
463 int posInLRing (const LSet set, const int length,
464  LObject* L,const kStrategy strat);
465 int posInSyz (const kStrategy strat, const poly sig);
466 int posInL0 (const LSet set, const int length,
467  LObject* L,const kStrategy strat);
468 int posInL11 (const LSet set, const int length,
469  LObject* L,const kStrategy strat);
470 int posInL11Ring (const LSet set, const int length,
471  LObject* L,const kStrategy strat);
472 int posInLF5CRing (const LSet set, int start , const int length,
473  LObject* L,const kStrategy strat);
474 int posInL11Ringls (const LSet set, const int length,
475  LObject* L,const kStrategy strat);
476 int posInL13 (const LSet set, const int length,
477  LObject* L,const kStrategy strat);
478 int posInL15 (const LSet set, const int length,
479  LObject* L,const kStrategy strat);
480 int posInL15Ring (const LSet set, const int length,
481  LObject* L,const kStrategy strat);
482 int posInL17 (const LSet set, const int length,
483  LObject* L,const kStrategy strat);
484 int posInL10 (const LSet set, const int length,
485  LObject* L,const kStrategy strat);
486 int posInL10Ring (const LSet set, const int length,
487  LObject* L,const kStrategy strat);
488 int posInL110 (const LSet set, const int length,
489  LObject* L,const kStrategy strat);
490 KINLINE poly redtailBba (poly p,int end_pos,kStrategy strat,BOOLEAN normalize=FALSE);
491 KINLINE poly redtailBbaBound (poly p,int end_pos,kStrategy strat,int bound,BOOLEAN normalize=FALSE);
492 #ifdef HAVE_RINGS
493 KINLINE poly redtailBba_Z (poly p,int end_pos,kStrategy strat);
494 poly redtailBba_Z (LObject* L, int end_pos, kStrategy strat );
495 void redtailBbaAlsoLC_Z (LObject* L, int end_pos, kStrategy strat );
496 #endif
497 poly redtailBba (LObject *L, int end_pos,kStrategy strat,
499 poly redtailBbaBound (LObject *L, int end_pos,kStrategy strat,int bound,
501 poly redtailSba (LObject *L, int end_pos,kStrategy strat,
503 poly redtailBba (TObject *T, int end_pos,kStrategy strat);
504 poly redtail (poly p,int end_pos,kStrategy strat);
505 poly redtail (LObject *L,int end_pos,kStrategy strat);
506 poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
507 int redNF0 (LObject *P,kStrategy strat);
508 poly redNFTail (poly h,const int sl,kStrategy strat);
509 int redHoney (LObject* h, kStrategy strat);
510 #ifdef HAVE_RINGS
511 int redRing (LObject* h,kStrategy strat);
512 int redRing_Z (LObject* h,kStrategy strat);
513 int redRiloc (LObject* h,kStrategy strat);
514 void enterExtendedSpoly(poly h,kStrategy strat);
515 void enterExtendedSpolySig(poly h,poly hSig,kStrategy strat);
516 void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
517 void superenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR = -1);
518 poly kCreateZeroPoly(long exp[], long cabsind, poly* t_p, ring leadRing, ring tailRing);
519 long ind2(long arg);
520 
521 long ind_fact_2(long arg);
522 long twoPow(long arg);
523 ideal createG0();
524 #endif
525 int redLazy (LObject* h,kStrategy strat);
526 int redHomog (LObject* h,kStrategy strat);
527 int redSig (LObject* h,kStrategy strat);
528 int redSigRing (LObject* h,kStrategy strat);
529 //adds hSig to be able to check with F5's criteria when entering pairs!
530 void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
531 void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
532 void entersets (LObject h);
533 void pairs ();
535 void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
536 void messageStat (int hilbcount,kStrategy strat);
537 void messageStatSBA (int hilbcount,kStrategy strat);
538 #ifdef KDEBUG
539 void messageSets (kStrategy strat);
540 #else
541 #define messageSets(s) do {} while (0)
542 #endif
543 
544 void initEcartNormal (TObject* h);
545 void initEcartBBA (TObject* h);
546 void initS (ideal F, ideal Q,kStrategy strat);
547 void initSL (ideal F, ideal Q,kStrategy strat);
548 void initSLSba (ideal F, ideal Q,kStrategy strat);
549 /*************************************************
550  * when initializing a new bunch of principal
551  * syzygies at the beginning of a new iteration
552  * step in a signature-based algorithm we
553  * compute ONLY the leading elements of those
554  * syzygies, NOT the whole syzygy
555  * NOTE: this needs to be adjusted for a more
556  * general approach on signature-based algorithms
557  ***********************************************/
558 void initSyzRules (kStrategy strat);
559 void updateS(BOOLEAN toT,kStrategy strat);
560 void enterSyz (LObject &p,kStrategy strat, int atT);
561 void enterT (LObject &p,kStrategy strat, int atT = -1);
562 void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat);
563 #ifdef HAVE_RINGS
564 void enterT_strong (LObject &p,kStrategy strat, int atT = -1);
565 #endif
566 void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
567 void HEckeTest (poly pp,kStrategy strat);
568 void initBuchMoraCrit(kStrategy strat);
569 void initSbaCrit(kStrategy strat);
570 void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
571 void initBuchMoraPos(kStrategy strat);
572 void initBuchMoraPosRing(kStrategy strat);
573 void initSbaPos(kStrategy strat);
574 void initBuchMora (ideal F, ideal Q,kStrategy strat);
575 void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
576 void exitBuchMora (kStrategy strat);
577 void exitSba (kStrategy strat);
578 void updateResult(ideal r,ideal Q,kStrategy strat);
579 void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
580 void kFreeStrat(kStrategy strat);
581 void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
582 void chainCritNormal (poly p,int ecart,kStrategy strat);
583 void chainCritOpt_1 (poly,int,kStrategy strat);
584 void chainCritSig (poly p,int ecart,kStrategy strat);
585 BOOLEAN homogTest(polyset F, int Fmax);
586 BOOLEAN newHEdge(kStrategy strat);
587 BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
588 BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
589 KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
590 BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
591 BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
592 BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
593 BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
594 
595 /// returns index of p in TSet, or -1 if not found
596 int kFindInT(poly p, TSet T, int tlength);
597 
598 /// return -1 if no divisor is found
599 /// number of first divisor in T, otherwise
600 int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start=0);
601 int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start=0);
602 int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start=0);
603 
604 /// return -1 if no divisor is found
605 /// number of first divisor in S, otherwise
606 int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
607 
608 int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
609 TObject* kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject* L, TObject *T, long ecart = LONG_MAX);
610 
611 /***************************************************************
612  *
613  * stuff to be inlined
614  *
615  ***************************************************************/
616 
617 KINLINE TSet initT ();
618 KINLINE TObject** initR();
619 KINLINE unsigned long* initsevT();
620 KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
621 KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
622 KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
623 KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
624 
625 KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
626 KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
627 KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
628 KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
629 
630 // if exp bound is not violated, return TRUE and
631 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
632 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
633 // return FALSE and m1 == NULL, m2 == NULL , otherwise
634 KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
635  poly &m1, poly &m2, const ring m_r);
636 #ifdef HAVE_RINGS
637 KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
638  poly &m1, poly &m2, poly &lcm, const ring taiRing);
639 #endif
640 #ifdef KDEBUG
641 // test strat
642 BOOLEAN kTest(kStrategy strat);
643 // test strat, and test that S is contained in T
644 BOOLEAN kTest_TS(kStrategy strat);
645 // test LObject
646 BOOLEAN kTest_L(LObject* L, ring tailRing,
647  BOOLEAN testp = FALSE, int lpos = -1,
648  TSet T = NULL, int tlength = -1);
649 // test TObject
650 BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char TN = '?');
651 // test set strat->SevS
652 BOOLEAN kTest_S(kStrategy strat);
653 #else
654 #define kTest(A) (TRUE)
655 #define kTest_TS(A) (TRUE)
656 #define kTest_T(T) (TRUE)
657 #define kTest_S(T) (TRUE)
658 #define kTest_L(T,R) (TRUE)
659 #endif
660 
661 
662 /***************************************************************
663  *
664  * From kstd2.cc
665  *
666  ***************************************************************/
667 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
668 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
669 ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
670 poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
671 ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
672 poly kNF2Bound (ideal F, ideal Q, poly q,int bound, kStrategy strat, int lazyReduce);
673 ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound, kStrategy strat, int lazyReduce);
674 void initBba(kStrategy strat);
675 void initSba(ideal F,kStrategy strat);
676 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
677  int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
678  intvec *w,intvec *hilb );
679 
680 /***************************************************************
681  *
682  * From kspoly.cc
683  *
684  ***************************************************************/
685 // Reduces PR with PW
686 // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
687 // Changes: PR
688 // Const: PW
689 // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
690 // If strat != NULL, tailRing is changed if reduction would violate exp bound
691 // of tailRing
692 // Returns: 0 everything ok, no tailRing change
693 // 1 tailRing has successfully changed (strat != NULL)
694 // 2 no reduction performed, tailRing needs to be changed first
695 // (strat == NULL)
696 // -1 tailRing change could not be performed due to exceeding exp
697 // bound of currRing
698 int ksReducePoly(LObject* PR,
699  TObject* PW,
700  poly spNoether = NULL,
701  number *coef = NULL,
702  kStrategy strat = NULL);
703 
704 /* like ksReducePoly, but if the reducer has only 1 term we still
705  * compute a possible coefficient multiplier for PR. this comes from
706  * a special situation in redRing_Z and it is used only there. */
707 int ksReducePolyZ(LObject* PR,
708  TObject* PW,
709  poly spNoether = NULL,
710  number *coef = NULL,
711  kStrategy strat = NULL);
712 
713 int ksReducePolyLC(LObject* PR,
714  TObject* PW,
715  poly spNoether = NULL,
716  number *coef = NULL,
717  kStrategy strat = NULL);
718 
719 
720 int ksReducePolyGCD(LObject* PR,
721  TObject* PW,
722  poly spNoether = NULL,
723  number *coef = NULL,
724  kStrategy strat = NULL);
725 
726 int ksReducePolyBound(LObject* PR,
727  TObject* PW,
728  int bound,
729  poly spNoether = NULL,
730  number *coef = NULL,
731  kStrategy strat = NULL);
732 
733 // Reduces PR with PW
734 // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
735 // Changes: PR
736 // Const: PW
737 // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
738 // If strat != NULL, tailRing is changed if reduction would violate exp bound
739 // of tailRing
740 // Returns: 0 everything ok, no tailRing change
741 // 1 tailRing has successfully changed (strat != NULL)
742 // 2 no reduction performed, tailRing needs to be changed first
743 // (strat == NULL)
744 // 3 no reduction performed, not sig-safe!!!
745 // -1 tailRing change could not be performed due to exceeding exp
746 // bound of currRing
747 int ksReducePolySig(LObject* PR,
748  TObject* PW,
749  long idx,
750  poly spNoether = NULL,
751  number *coef = NULL,
752  kStrategy strat = NULL);
753 
755  TObject* PW,
756  long idx,
757  poly spNoether = NULL,
758  number *coef = NULL,
759  kStrategy strat = NULL);
760 
761 // Reduces PR at Current->next with PW
762 // Assumes PR != NULL, Current contained in PR
763 // Current->next != NULL, LM(PW) devides LM(Current->next)
764 // Changes: PR
765 // Const: PW
766 // Return: see ksReducePoly
767 int ksReducePolyTail(LObject* PR,
768  TObject* PW,
769  poly Current,
770  poly spNoether = NULL);
771 
772 KINLINE int ksReducePolyTail(LObject* PR, TObject* PW, LObject* Red);
773 
774 // Creates S-Poly of Pair
775 // Const: Pair->p1, Pair->p2
776 // Changes: Pair->p == S-Poly of p1, p2
777 // Assume: Pair->p1 != NULL && Pair->p2
778 void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
779  int use_buckets=0, ring tailRing=currRing,
780  poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
781 
782 /*2
783 * creates the leading term of the S-polynomial of p1 and p2
784 * do not destroy p1 and p2
785 * remarks:
786 * 1. the coefficient is 0 (nNew)
787 * 2. pNext is undefined
788 */
789 poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
790 
791 
792 // old stuff
793 KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
794 KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
795 KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
796 KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
797 
798 /***************************************************************
799  *
800  * Routines related for ring changes during std computations
801  *
802  ***************************************************************/
803 // return TRUE and set m1, m2 to k_GetLcmTerms,
804 // if spoly creation of strat->P does not violate
805 // exponent bound of strat->tailRing
806 // FALSE, otherwise
807 BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
808 #ifdef HAVE_RINGS
809 // return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
810 // exponent bound of strat->tailRing
811 // FALSE, otherwise
812 BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
813 poly preIntegerCheck(ideal F, ideal Q);
814 void postReduceByMon(LObject* h, kStrategy strat);
815 void postReduceByMonSig(LObject* h, kStrategy strat);
816 void finalReduceByMon(kStrategy strat);
817 #endif
818 // change strat->tailRing and adjust all data in strat, L, and T:
819 // new tailRing has larger exponent bound
820 // do nothing and return FALSE if exponent bound increase would result in
821 // larger exponent bound that that of currRing
823  LObject* L = NULL, TObject* T = NULL,
824  // take this as new_expbound: if 0
825  // new expbound is 2*expbound of tailRing
826  unsigned long new_expbound = 0);
827 // initiate a change of the tailRing of strat -- should be called
828 // right before main loop in bba
830 
831 /// Output some debug info about a given strategy
832 void kDebugPrint(kStrategy strat);
833 
834 // getting sb order for sba computations
835 ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
836 
837 KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
838  kStrategy strat);
839 
840 #include "kernel/GBEngine/kInline.h"
841 
842 /* shiftgb stuff */
843 #include "kernel/GBEngine/shiftgb.h"
844 
845 poly pMove2CurrTail(poly p, kStrategy strat);
846 
847 poly pMoveCurrTail2poly(poly p, kStrategy strat);
848 
849 poly pCopyL2p(LObject h, kStrategy strat);
850 
851 void enterTShift(LObject p, kStrategy strat, int atT = -1);
852 
853 void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS);
854 
855 void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
856 
857 void initBbaShift(kStrategy strat);
858 
859 poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
860 
861 int redFirstShift (LObject* h,kStrategy strat); // ok
862 
863 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
864 // test syz strategy: // will be removed soon
865 EXTERN_VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
866 EXTERN_VAR int (*test_PosInL)(const LSet set, const int length,
867  LObject* L,const kStrategy strat);
868 
869 static inline void kDeleteLcm(LObject *P)
870 {
871  if (P->lcm!=NULL)
872  {
873  #ifdef HAVE_RINGS
875  pLmDelete(P->lcm);
876  else
877  #endif
878  pLmFree(P->lcm);
879  P->lcm=NULL;
880  }
881 }
882 #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:11915
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11878
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
STATIC_VAR jList * Q
Definition: janet.cc:30
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:436
int nr
Definition: kutil.h:344
char fromT
Definition: kutil.h:378
int j
Definition: facHensel.cc:105
char kHEdgeFound
Definition: kutil.h:375
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:8418
#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:9948
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:10533
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:11229
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
char rightGB
Definition: kutil.h:368
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:295
void enterTShift(LObject p, kStrategy strat, int atT=-1)
Definition: kutil.cc:12807
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:657
int sgn(const Rational &a)
Definition: GMPrat.cc:430
#define FALSE
Definition: auxiliary.h:96
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:377
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L=NULL, TObject *T=NULL, unsigned long new_expbound=0)
Definition: kutil.cc:11403
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10420
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:690
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:12830
char news
Definition: kutil.h:399
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:10994
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:400
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:1409
#define EXTERN_VAR
Definition: globaldefs.h:6
BOOLEAN * NotUsedAxis
Definition: kutil.h:330
char interpt
Definition: kutil.h:370
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:68
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
void initSbaPos(kStrategy strat)
Definition: kutil.cc:10318
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:568
char noClearS
Definition: kutil.h:401
#define TRUE
Definition: auxiliary.h:100
static void kDeleteLcm(LObject *P)
Definition: kutil.h:869
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:654
char LDegLast
Definition: kutil.h:384
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
poly pMove2CurrTail(poly p, kStrategy strat)
Definition: kutil.cc:12085
BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat)
Definition: kutil.cc:10971
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:8077
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:9866
int k
Definition: cfEzgcd.cc:92
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10208
void enterT(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9586
EXTERN_VAR int strat_nr
Definition: kutil.h:176
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:4605
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
#define KINLINE
Definition: kutil.h:45
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:468
char posInLOldFlag
Definition: kutil.h:381
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:10292
char length_pLength
Definition: kutil.h:386
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:11161
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:9884
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:320
char use_buckets
Definition: kutil.h:382
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:8268
char completeReduce_retry
Definition: kutil.h:402
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:9036
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
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5296
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11502
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 nrsyzcrit
Definition: kutil.h:359
int nrrewcrit
Definition: kutil.h:360
char sugarCrit
Definition: kutil.h:376
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:10035
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:655
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
EXTERN_VAR denominator_list DENOMINATOR_LIST
Definition: kutil.h:62
void pairs()
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:12777
char no_prod_crit
Definition: kutil.h:393
intset fromQ
Definition: kutil.h:317
#define messageSets(s)
Definition: kutil.h:541
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:1159
LObject * LSet
Definition: kutil.h:56
EXTERN_VAR int HCord
Definition: kutil.h:265
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:658
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:896
void enterSSba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9390
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:11949
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
ideal M
Definition: kutil.h:301
unsigned sbaOrder
Definition: kutil.h:312
poly * polyset
Definition: polys.h:255
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:12270
int i
Definition: cfEzgcd.cc:125
poly tail
Definition: kutil.h:332
EXTERN_VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:866
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
EXTERN_VAR int LazyDegree
Definition: kstd1.h:50
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:4485
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 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:9686
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:10867
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:10493
poly pMoveCurrTail2poly(poly p, kStrategy strat)
Definition: kutil.cc:12099
poly redtailSba(LObject *L, int end_pos, kStrategy strat, BOOLEAN withT=FALSE, BOOLEAN normalize=FALSE)
Definition: kstd2.cc:1398
STATIC_VAR Poly * h
Definition: janet.cc:971
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:371
poly p2
Definition: kutil.h:183
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether=NULL)
Definition: kspoly.cc:1309
KINLINE poly redtailBba(poly p, int end_pos, kStrategy strat, BOOLEAN normalize=FALSE)
Definition: kInline.h:1158
EXTERN_VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:865
LSet L
Definition: kutil.h:323
char z2homog
Definition: kutil.h:373
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:11824
LSet B
Definition: kutil.h:324
char noetherSet
Definition: kutil.h:379
int Lmax
Definition: kutil.h:349
int64 wlen_type
Definition: kutil.h:50
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition: kutil.cc:9525
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9788
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:10745
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:27
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:359
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:403
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:9271
intset fromS
Definition: kutil.h:306
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:11318
int posInL10(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd1.cc:1006
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:380
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:388
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10931
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
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:306
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5965
#define kTest_T(T)
Definition: kutil.h:656
int LazyPass
Definition: kutil.h:351
static LSet initL(int nr=setmaxL)
Definition: kutil.h:420
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:10121
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
int BOOLEAN
Definition: auxiliary.h:87
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:9371
unsigned long sev
Definition: kutil.h:182
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1664
char redTailChange
Definition: kutil.h:398
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:543
int l
Definition: cfEzgcd.cc:93
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:982
STATIC_VAR jList * T
Definition: janet.cc:30
poly pCopyL2p(LObject h, kStrategy strat)
Definition: kutil.cc:12116
class sTObject TObject
Definition: kutil.h:53
ring tailRing
Definition: kutil.h:72
void initSL(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8171
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:188
ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1)
Definition: kutil.cc:11529
int posInL15Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6779