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