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