1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT - Kernel: alg. of Buchberger
6 */
7
8 // #define PDEBUG 2
9
10 #include "kernel/mod2.h"
11
12 #define GCD_SBA 1
13
14 // define if no buckets should be used
15 // #define NO_BUCKETS
16
17 #ifdef HAVE_PLURAL
18 #define PLURAL_INTERNAL_DECLARATIONS 1
19 #endif
20
21 /***********************************************
22 * SBA stuff -- start
23 ***********************************************/
24 #define DEBUGF50 0
25 #define DEBUGF51 0
26
27 #ifdef DEBUGF5
28 #undef DEBUGF5
29 //#define DEBUGF5 1
30 #endif
31
32 #define F5C 1
33 #if F5C
34 #define F5CTAILRED 1
35 #endif
36
37 #define SBA_INTERRED_START 0
38 #define SBA_TAIL_RED 1
39 #define SBA_PRODUCT_CRITERION 0
40 #define SBA_PRINT_ZERO_REDUCTIONS 0
41 #define SBA_PRINT_REDUCTION_STEPS 0
42 #define SBA_PRINT_OPERATIONS 0
43 #define SBA_PRINT_SIZE_G 0
44 #define SBA_PRINT_SIZE_SYZ 0
45 #define SBA_PRINT_PRODUCT_CRITERION 0
46
47 // counts sba's reduction steps
48 #if SBA_PRINT_REDUCTION_STEPS
49 VAR long sba_reduction_steps;
50 VAR long sba_interreduction_steps;
51 #endif
52 #if SBA_PRINT_OPERATIONS
53 VAR long sba_operations;
54 VAR long sba_interreduction_operations;
55 #endif
56
57 /***********************************************
58 * SBA stuff -- done
59 ***********************************************/
60
61 #include "kernel/GBEngine/kutil.h"
62 #include "misc/options.h"
63 #include "kernel/polys.h"
64 #include "kernel/ideals.h"
65 #include "kernel/GBEngine/kstd1.h"
66 #include "kernel/GBEngine/khstd.h"
67 #include "polys/kbuckets.h"
68 #include "polys/prCopy.h"
69 #include "polys/weight.h"
70 #include "misc/intvec.h"
71 #ifdef HAVE_PLURAL
72 #include "polys/nc/nc.h"
73 #endif
74 // #include "timer.h"
75
76 #ifdef HAVE_SHIFTBBA
77 #include "polys/shiftop.h"
78 #endif
79
80 VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
81 VAR int (*test_PosInL)(const LSet set, const int length,
82 LObject* L,const kStrategy strat);
83
kFindSameLMInT_Z(const kStrategy strat,const LObject * L,const int start)84 int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start)
85 {
86 unsigned long not_sev = ~L->sev;
87 int j = start;
88 int o = -1;
89
90 const TSet T=strat->T;
91 const unsigned long* sevT=strat->sevT;
92 number gcd, ogcd;
93 if (L->p!=NULL)
94 {
95 const ring r=currRing;
96 const poly p=L->p;
97 ogcd = pGetCoeff(p);
98
99 pAssume(~not_sev == p_GetShortExpVector(p, r));
100
101 loop
102 {
103 if (j > strat->tl) return o;
104 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
105 {
106 gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
107 if (o == -1
108 || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
109 {
110 ogcd = gcd;
111 o = j;
112 }
113 }
114 j++;
115 }
116 }
117 else
118 {
119 const ring r=strat->tailRing;
120 const poly p=L->t_p;
121 ogcd = pGetCoeff(p);
122 loop
123 {
124 if (j > strat->tl) return o;
125 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
126 {
127 gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
128 if (o == -1
129 || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
130 {
131 ogcd = gcd;
132 o = j;
133 }
134 }
135 j++;
136 }
137 }
138 }
139 // return -1 if T[0] does not divide the leading monomial
kTestDivisibleByT0_Z(const kStrategy strat,const LObject * L)140 int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L)
141 {
142 if (strat->tl < 1)
143 return -1;
144
145 unsigned long not_sev = ~L->sev;
146 const unsigned long sevT0 = strat->sevT[0];
147 number rest, orest, mult;
148 if (L->p!=NULL)
149 {
150 const poly T0p = strat->T[0].p;
151 const ring r = currRing;
152 const poly p = L->p;
153 orest = pGetCoeff(p);
154
155 pAssume(~not_sev == p_GetShortExpVector(p, r));
156
157 #if defined(PDEBUG) || defined(PDIV_DEBUG)
158 if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
159 {
160 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
161 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
162 {
163 return 0;
164 }
165 }
166 #else
167 if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
168 {
169 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
170 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
171 {
172 return 0;
173 }
174 }
175 #endif
176 }
177 else
178 {
179 const poly T0p = strat->T[0].t_p;
180 const ring r = strat->tailRing;
181 const poly p = L->t_p;
182 orest = pGetCoeff(p);
183 #if defined(PDEBUG) || defined(PDIV_DEBUG)
184 if (p_LmShortDivisibleBy(T0p, sevT0,
185 p, not_sev, r))
186 {
187 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
188 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
189 {
190 return 0;
191 }
192 }
193 #else
194 if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
195 {
196 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
197 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
198 {
199 return 0;
200 }
201 }
202 #endif
203 }
204 return -1;
205 }
206
kFindDivisibleByInT_Z(const kStrategy strat,const LObject * L,const int start)207 int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start)
208 {
209 unsigned long not_sev = ~L->sev;
210 int j = start;
211 int o = -1;
212
213 const TSet T=strat->T;
214 const unsigned long* sevT=strat->sevT;
215 number rest, orest, mult;
216 if (L->p!=NULL)
217 {
218 const ring r=currRing;
219 const poly p=L->p;
220 orest = pGetCoeff(p);
221
222 pAssume(~not_sev == p_GetShortExpVector(p, r));
223
224 loop
225 {
226 if (j > strat->tl) return o;
227 #if defined(PDEBUG) || defined(PDIV_DEBUG)
228 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
229 {
230 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
231 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
232 {
233 o = j;
234 orest = rest;
235 }
236 }
237 #else
238 if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
239 {
240 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
241 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
242 {
243 o = j;
244 orest = rest;
245 }
246 }
247 #endif
248 j++;
249 }
250 }
251 else
252 {
253 const ring r=strat->tailRing;
254 const poly p=L->t_p;
255 orest = pGetCoeff(p);
256 loop
257 {
258 if (j > strat->tl) return o;
259 #if defined(PDEBUG) || defined(PDIV_DEBUG)
260 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
261 p, not_sev, r))
262 {
263 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
264 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
265 {
266 o = j;
267 orest = rest;
268 }
269 }
270 #else
271 if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
272 {
273 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
274 if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
275 {
276 o = j;
277 orest = rest;
278 }
279 }
280 #endif
281 j++;
282 }
283 }
284 }
285
286 // return -1 if no divisor is found
287 // number of first divisor, otherwise
kFindDivisibleByInT(const kStrategy strat,const LObject * L,const int start)288 int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
289 {
290 unsigned long not_sev = ~L->sev;
291 int j = start;
292
293 const TSet T=strat->T;
294 const unsigned long* sevT=strat->sevT;
295 const ring r=currRing;
296 const BOOLEAN is_Ring=rField_is_Ring(r);
297 if (L->p!=NULL)
298 {
299 const poly p=L->p;
300
301 pAssume(~not_sev == p_GetShortExpVector(p, r));
302
303 if(is_Ring)
304 {
305 loop
306 {
307 if (j > strat->tl) return -1;
308 #if defined(PDEBUG) || defined(PDIV_DEBUG)
309 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
310 {
311 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
312 return j;
313 }
314 #else
315 if (!(sevT[j] & not_sev) &&
316 p_LmDivisibleBy(T[j].p, p, r))
317 {
318 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
319 return j;
320 }
321 #endif
322 j++;
323 }
324 }
325 else
326 {
327 loop
328 {
329 if (j > strat->tl) return -1;
330 #if defined(PDEBUG) || defined(PDIV_DEBUG)
331 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
332 {
333 return j;
334 }
335 #else
336 if (!(sevT[j] & not_sev) &&
337 p_LmDivisibleBy(T[j].p, p, r))
338 {
339 return j;
340 }
341 #endif
342 j++;
343 }
344 }
345 }
346 else
347 {
348 const poly p=L->t_p;
349 const ring r=strat->tailRing;
350 if(is_Ring)
351 {
352 loop
353 {
354 if (j > strat->tl) return -1;
355 #if defined(PDEBUG) || defined(PDIV_DEBUG)
356 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
357 p, not_sev, r))
358 {
359 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
360 return j;
361 }
362 #else
363 if (!(sevT[j] & not_sev) &&
364 p_LmDivisibleBy(T[j].t_p, p, r))
365 {
366 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
367 return j;
368 }
369 #endif
370 j++;
371 }
372 }
373 else
374 {
375 loop
376 {
377 if (j > strat->tl) return -1;
378 #if defined(PDEBUG) || defined(PDIV_DEBUG)
379 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
380 p, not_sev, r))
381 {
382 return j;
383 }
384 #else
385 if (!(sevT[j] & not_sev) &&
386 p_LmDivisibleBy(T[j].t_p, p, r))
387 {
388 return j;
389 }
390 #endif
391 j++;
392 }
393 }
394 }
395 }
396
397 // same as above, only with set S
kFindDivisibleByInS(const kStrategy strat,int * max_ind,LObject * L)398 int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
399 {
400 unsigned long not_sev = ~L->sev;
401 poly p = L->GetLmCurrRing();
402 int j = 0;
403
404 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
405
406 BOOLEAN is_Ring=rField_is_Ring(currRing);
407 #if 1
408 int ende;
409 if (is_Ring
410 || (strat->ak>0)
411 || currRing->pLexOrder)
412 ende=strat->sl;
413 else
414 {
415 ende=posInS(strat,*max_ind,p,0)+1;
416 if (ende>(*max_ind)) ende=(*max_ind);
417 }
418 #else
419 int ende=strat->sl;
420 #endif
421 if(is_Ring)
422 {
423 loop
424 {
425 if (j > ende) return -1;
426 #if defined(PDEBUG) || defined(PDIV_DEBUG)
427 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
428 p, not_sev, currRing))
429 {
430 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
431 return j;
432 }
433 #else
434 if ( !(strat->sevS[j] & not_sev) &&
435 p_LmDivisibleBy(strat->S[j], p, currRing))
436 {
437 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
438 return j;
439 }
440 #endif
441 j++;
442 }
443 }
444 else
445 {
446 loop
447 {
448 if (j > ende) return -1;
449 #if defined(PDEBUG) || defined(PDIV_DEBUG)
450 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
451 p, not_sev, currRing))
452 {
453 return j;
454 }
455 #else
456 if ( !(strat->sevS[j] & not_sev) &&
457 p_LmDivisibleBy(strat->S[j], p, currRing))
458 {
459 return j;
460 }
461 #endif
462 j++;
463 }
464 }
465 }
466
kFindNextDivisibleByInS(const kStrategy strat,int start,int max_ind,LObject * L)467 int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
468 {
469 unsigned long not_sev = ~L->sev;
470 poly p = L->GetLmCurrRing();
471 int j = start;
472
473 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
474 #if 1
475 int ende=max_ind;
476 #else
477 int ende=strat->sl;
478 #endif
479 if(rField_is_Ring(currRing))
480 {
481 loop
482 {
483 if (j > ende) return -1;
484 #if defined(PDEBUG) || defined(PDIV_DEBUG)
485 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
486 p, not_sev, currRing))
487 {
488 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
489 return j;
490 }
491 #else
492 if ( !(strat->sevS[j] & not_sev) &&
493 p_LmDivisibleBy(strat->S[j], p, currRing))
494 {
495 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
496 return j;
497 }
498 #endif
499 j++;
500 }
501 }
502 else
503 {
504 loop
505 {
506 if (j > ende) return -1;
507 #if defined(PDEBUG) || defined(PDIV_DEBUG)
508 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
509 p, not_sev, currRing))
510 {
511 return j;
512 }
513 #else
514 if ( !(strat->sevS[j] & not_sev) &&
515 p_LmDivisibleBy(strat->S[j], p, currRing))
516 {
517 return j;
518 }
519 #endif
520 j++;
521 }
522 }
523 }
524
525 #ifdef HAVE_RINGS
ind2(long arg)526 static long ind2(long arg)
527 {
528 if (arg <= 0) return 0;
529 long ind = 0;
530 while (arg%2 == 0)
531 {
532 arg = arg / 2;
533 ind++;
534 }
535 return ind;
536 }
537
ind_fact_2(long arg)538 static long ind_fact_2(long arg)
539 {
540 if (arg <= 0) return 0;
541 long ind = 0;
542 if (arg%2 == 1) { arg--; }
543 while (arg > 0)
544 {
545 ind += ind2(arg);
546 arg = arg - 2;
547 }
548 return ind;
549 }
550 #endif
551
552 #ifdef HAVE_RINGS
kFindZeroPoly(poly input_p,ring leadRing,ring tailRing)553 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
554 {
555 // m = currRing->ch
556
557 if (input_p == NULL) return NULL;
558
559 poly p = input_p;
560 poly zeroPoly = NULL;
561 unsigned long a = (unsigned long) pGetCoeff(p);
562
563 int k_ind2 = 0;
564 int a_ind2 = ind2(a);
565
566 // unsigned long k = 1;
567 // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
568 for (int i = 1; i <= leadRing->N; i++)
569 {
570 k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
571 }
572
573 a = (unsigned long) pGetCoeff(p);
574
575 number tmp1;
576 poly tmp2, tmp3;
577 poly lead_mult = p_ISet(1, tailRing);
578 if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
579 {
580 int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
581 int s_exp;
582 zeroPoly = p_ISet(a, tailRing);
583 for (int i = 1; i <= leadRing->N; i++)
584 {
585 s_exp = p_GetExp(p, i,leadRing);
586 if (s_exp % 2 != 0)
587 {
588 s_exp = s_exp - 1;
589 }
590 while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
591 {
592 too_much = too_much - ind2(s_exp);
593 s_exp = s_exp - 2;
594 }
595 p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
596 for (int j = 1; j <= s_exp; j++)
597 {
598 tmp1 = nInit(j);
599 tmp2 = p_ISet(1, tailRing);
600 p_SetExp(tmp2, i, 1, tailRing);
601 p_Setm(tmp2, tailRing);
602 if (nIsZero(tmp1))
603 { // should nowbe obsolet, test ! TODO OLIVER
604 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
605 }
606 else
607 {
608 tmp3 = p_NSet(nCopy(tmp1), tailRing);
609 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
610 }
611 }
612 }
613 p_Setm(lead_mult, tailRing);
614 zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
615 tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
616 for (int i = 1; i <= leadRing->N; i++)
617 {
618 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
619 }
620 p_Setm(tmp2, leadRing);
621 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
622 pNext(tmp2) = zeroPoly;
623 return tmp2;
624 }
625 /* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
626 if (1 == 0 && alpha_k <= a)
627 { // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
628 zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
629 for (int i = 1; i <= leadRing->N; i++)
630 {
631 for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
632 {
633 tmp1 = nInit(j);
634 tmp2 = p_ISet(1, tailRing);
635 p_SetExp(tmp2, i, 1, tailRing);
636 p_Setm(tmp2, tailRing);
637 if (nIsZero(tmp1))
638 {
639 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
640 }
641 else
642 {
643 tmp3 = p_ISet((unsigned long) tmp1, tailRing);
644 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
645 }
646 }
647 }
648 tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
649 for (int i = 1; i <= leadRing->N; i++)
650 {
651 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
652 }
653 p_Setm(tmp2, leadRing);
654 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
655 pNext(tmp2) = zeroPoly;
656 return tmp2;
657 } */
658 return NULL;
659 }
660 #endif
661
662
663 #ifdef HAVE_RINGS
664 /*2
665 * reduction procedure for the ring Z/2^m
666 */
redRing_Z(LObject * h,kStrategy strat)667 int redRing_Z (LObject* h,kStrategy strat)
668 {
669 if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
670 if (strat->tl<0) return 1;
671
672 int at;
673 long d;
674 int j = 0;
675 int pass = 0;
676
677 // TODO warum SetpFDeg notwendig?
678 h->SetpFDeg();
679 assume(h->pFDeg() == h->FDeg);
680 long reddeg = h->GetpFDeg();
681
682 h->SetShortExpVector();
683 loop
684 {
685 /* check if a reducer of the lead term exists */
686 j = kFindDivisibleByInT(strat, h);
687 if (j < 0)
688 {
689 /* check if a reducer with the same lead monomial exists */
690 j = kFindSameLMInT_Z(strat, h);
691 if (j < 0)
692 {
693 /* check if a reducer of the lead monomial exists, by the above
694 * check this is a real divisor of the lead monomial */
695 j = kFindDivisibleByInT_Z(strat, h);
696 if (j < 0)
697 {
698 // over ZZ: cleanup coefficients by complete reduction with monomials
699 if (rHasLocalOrMixedOrdering(currRing))
700 postReduceByMon(h, strat);
701 if(h->p == NULL)
702 {
703 if (h->lcm!=NULL) pLmDelete(h->lcm);
704 h->Clear();
705 return 0;
706 }
707 if(nIsZero(pGetCoeff(h->p))) return 2;
708 j = kFindDivisibleByInT(strat, h);
709 if(j < 0)
710 {
711 if(strat->tl >= 0)
712 h->i_r1 = strat->tl;
713 else
714 h->i_r1 = -1;
715 if (h->GetLmTailRing() == NULL)
716 {
717 if (h->lcm!=NULL) pLmDelete(h->lcm);
718 h->Clear();
719 return 0;
720 }
721 return 1;
722 }
723 }
724 else
725 {
726 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
727 * => we try to cut down the lead coefficient at least */
728 /* first copy T[j] in order to multiply it with a coefficient later on */
729 number mult, rest;
730 TObject tj = strat->T[j];
731 tj.Copy();
732 /* tj.max_exp = strat->T[j].max_exp; */
733 /* compute division with remainder of lc(h) and lc(T[j]) */
734 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
735 &rest, currRing->cf);
736 /* set corresponding new lead coefficient already. we do not
737 * remove the lead term in ksReducePolyLC, but only apply
738 * a lead coefficient reduction */
739 tj.Mult_nn(mult);
740 ksReducePolyLC(h, &tj, NULL, &rest, strat);
741 tj.Delete();
742 tj.Clear();
743 }
744 }
745 else
746 {
747 /* same lead monomial but lead coefficients do not divide each other:
748 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
749 LObject h2 = *h;
750 h2.Copy();
751
752 ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
753 ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
754 if (!rHasLocalOrMixedOrdering(currRing))
755 {
756 redtailBbaAlsoLC_Z(&h2, j, strat);
757 h2.pCleardenom();
758 }
759 /* replace h2 for tj in L (already generated pairs with tj), S and T */
760 replaceInLAndSAndT(h2, j, strat);
761 }
762 }
763 else
764 {
765 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat);
766 }
767 /* printf("\nAfter small red: ");pWrite(h->p); */
768 if (h->GetLmTailRing() == NULL)
769 {
770 if (h->lcm!=NULL) pLmDelete(h->lcm);
771 #ifdef KDEBUG
772 h->lcm=NULL;
773 #endif
774 h->Clear();
775 return 0;
776 }
777 h->SetShortExpVector();
778 d = h->SetpFDeg();
779 /*- try to reduce the s-polynomial -*/
780 pass++;
781 if (!TEST_OPT_REDTHROUGH &&
782 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
783 {
784 h->SetLmCurrRing();
785 if (strat->posInLDependsOnLength)
786 h->SetLength(strat->length_pLength);
787 at = strat->posInL(strat->L,strat->Ll,h,strat);
788 if (at <= strat->Ll)
789 {
790 #ifdef KDEBUG
791 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
792 #endif
793 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
794 h->Clear();
795 return -1;
796 }
797 }
798 if (d != reddeg)
799 {
800 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
801 {
802 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
803 {
804 strat->overflow=TRUE;
805 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
806 h->GetP();
807 at = strat->posInL(strat->L,strat->Ll,h,strat);
808 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
809 h->Clear();
810 return -1;
811 }
812 }
813 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
814 {
815 Print(".%ld",d);mflush();
816 reddeg = d;
817 }
818 }
819 }
820 }
821
redRing(LObject * h,kStrategy strat)822 int redRing (LObject* h,kStrategy strat)
823 {
824 if (strat->tl<0) return 1;
825 if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
826
827 int at/*,i*/;
828 long d;
829 int j = 0;
830 int pass = 0;
831 // poly zeroPoly = NULL;
832
833 // TODO warum SetpFDeg notwendig?
834 h->SetpFDeg();
835 assume(h->pFDeg() == h->FDeg);
836 long reddeg = h->GetpFDeg();
837
838 h->SetShortExpVector();
839 loop
840 {
841 j = kFindDivisibleByInT(strat, h);
842 if (j < 0)
843 {
844 // over ZZ: cleanup coefficients by complete reduction with monomials
845 postReduceByMon(h, strat);
846 if(h->p == NULL)
847 {
848 kDeleteLcm(h);
849 h->Clear();
850 return 0;
851 }
852 if(nIsZero(pGetCoeff(h->p))) return 2;
853 j = kFindDivisibleByInT(strat, h);
854 if(j < 0)
855 {
856 if(strat->tl >= 0)
857 h->i_r1 = strat->tl;
858 else
859 h->i_r1 = -1;
860 if (h->GetLmTailRing() == NULL)
861 {
862 kDeleteLcm(h);
863 h->Clear();
864 return 0;
865 }
866 return 1;
867 }
868 }
869 //printf("\nFound one: ");pWrite(strat->T[j].p);
870 //enterT(*h, strat);
871 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
872 //printf("\nAfter small red: ");pWrite(h->p);
873 if (h->GetLmTailRing() == NULL)
874 {
875 kDeleteLcm(h);
876 h->Clear();
877 return 0;
878 }
879 h->SetShortExpVector();
880 d = h->SetpFDeg();
881 /*- try to reduce the s-polynomial -*/
882 pass++;
883 if (!TEST_OPT_REDTHROUGH &&
884 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
885 {
886 h->SetLmCurrRing();
887 if (strat->posInLDependsOnLength)
888 h->SetLength(strat->length_pLength);
889 at = strat->posInL(strat->L,strat->Ll,h,strat);
890 if (at <= strat->Ll)
891 {
892 #ifdef KDEBUG
893 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
894 #endif
895 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
896 h->Clear();
897 return -1;
898 }
899 }
900 if (d != reddeg)
901 {
902 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
903 {
904 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
905 {
906 strat->overflow=TRUE;
907 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
908 h->GetP();
909 at = strat->posInL(strat->L,strat->Ll,h,strat);
910 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
911 h->Clear();
912 return -1;
913 }
914 }
915 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
916 {
917 Print(".%ld",d);mflush();
918 reddeg = d;
919 }
920 }
921 }
922 }
923 #endif
924
925 /*2
926 * reduction procedure for the homogeneous case
927 * and the case of a degree-ordering
928 */
redHomog(LObject * h,kStrategy strat)929 int redHomog (LObject* h,kStrategy strat)
930 {
931 if (strat->tl<0) return 1;
932 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
933 assume(h->FDeg == h->pFDeg());
934
935 poly h_p;
936 int i,j,at,pass,cnt,ii;
937 unsigned long not_sev;
938 // long reddeg,d;
939 int li;
940 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
941
942 pass = j = 0;
943 cnt = RED_CANONICALIZE;
944 // d = reddeg = h->GetpFDeg();
945 h->SetShortExpVector();
946 h_p = h->GetLmTailRing();
947 not_sev = ~ h->sev;
948 h->PrepareRed(strat->use_buckets);
949 loop
950 {
951 j = kFindDivisibleByInT(strat, h);
952 if (j < 0) return 1;
953
954 li = strat->T[j].pLength;
955 ii = j;
956 /*
957 * the polynomial to reduce with (up to the moment) is;
958 * pi with length li
959 */
960 i = j;
961 #if 1
962 if (test_opt_length)
963 {
964 if (li<=0) li=strat->T[j].GetpLength();
965 if (li>2)
966 loop
967 {
968 /*- search the shortest possible with respect to length -*/
969 i++;
970 if (i > strat->tl)
971 break;
972 if ((strat->T[i].pLength < li)
973 &&
974 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
975 h_p, not_sev, strat->tailRing))
976 {
977 /*
978 * the polynomial to reduce with is now;
979 */
980 li = strat->T[i].pLength;
981 if (li<=0) li=strat->T[i].GetpLength();
982 ii = i;
983 if (li<3) break;
984 }
985 }
986 }
987 #endif
988
989 /*
990 * end of search: have to reduce with pi
991 */
992 #ifdef KDEBUG
993 if (TEST_OPT_DEBUG)
994 {
995 PrintS("red:");
996 h->wrp();
997 PrintS(" with ");
998 strat->T[ii].wrp();
999 }
1000 #endif
1001 assume(strat->fromT == FALSE);
1002
1003 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1004 #if SBA_PRINT_REDUCTION_STEPS
1005 sba_interreduction_steps++;
1006 #endif
1007 #if SBA_PRINT_OPERATIONS
1008 sba_interreduction_operations += pLength(strat->T[ii].p);
1009 #endif
1010
1011 #ifdef KDEBUG
1012 if (TEST_OPT_DEBUG)
1013 {
1014 PrintS("\nto ");
1015 h->wrp();
1016 PrintLn();
1017 }
1018 #endif
1019
1020 h_p = h->GetLmTailRing();
1021 if (h_p == NULL)
1022 {
1023 kDeleteLcm(h);
1024 return 0;
1025 }
1026 if (UNLIKELY(TEST_OPT_IDLIFT))
1027 {
1028 if (h->p!=NULL)
1029 {
1030 if(p_GetComp(h->p,currRing)>strat->syzComp)
1031 {
1032 h->Delete();
1033 return 0;
1034 }
1035 }
1036 else if (h->t_p!=NULL)
1037 {
1038 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1039 {
1040 h->Delete();
1041 return 0;
1042 }
1043 }
1044 }
1045 #if 0
1046 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1047 {
1048 if (h->p!=NULL)
1049 {
1050 if(p_GetComp(h->p,currRing)>strat->syzComp)
1051 {
1052 return 1;
1053 }
1054 }
1055 else if (h->t_p!=NULL)
1056 {
1057 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1058 {
1059 return 1;
1060 }
1061 }
1062 }
1063 #endif
1064 h->SetShortExpVector();
1065 not_sev = ~ h->sev;
1066 /*
1067 * try to reduce the s-polynomial h
1068 *test first whether h should go to the lazyset L
1069 *-if the degree jumps
1070 *-if the number of pre-defined reductions jumps
1071 */
1072 cnt--;
1073 pass++;
1074 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1075 {
1076 h->SetLmCurrRing();
1077 at = strat->posInL(strat->L,strat->Ll,h,strat);
1078 if (at <= strat->Ll)
1079 {
1080 #ifdef HAVE_SHIFTBBA
1081 if (rIsLPRing(currRing))
1082 {
1083 if (kFindDivisibleByInT(strat, h) < 0)
1084 return 1;
1085 }
1086 else
1087 #endif
1088 {
1089 int dummy=strat->sl;
1090 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1091 return 1;
1092 }
1093 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1094 #ifdef KDEBUG
1095 if (TEST_OPT_DEBUG)
1096 Print(" lazy: -> L%d\n",at);
1097 #endif
1098 h->Clear();
1099 return -1;
1100 }
1101 }
1102 else if (UNLIKELY(cnt==0))
1103 {
1104 h->CanonicalizeP();
1105 cnt=RED_CANONICALIZE;
1106 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1107 }
1108 }
1109 }
1110
ksReducePolyTailSig(LObject * PR,TObject * PW,LObject * Red,kStrategy strat)1111 KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red, kStrategy strat)
1112 {
1113 BOOLEAN ret;
1114 number coef;
1115 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1116 if(!rField_is_Ring(currRing))
1117 Red->HeadNormalize();
1118 /*
1119 printf("------------------------\n");
1120 pWrite(Red->GetLmCurrRing());
1121 */
1122 if(rField_is_Ring(currRing))
1123 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1124 else
1125 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1126 if (!ret)
1127 {
1128 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1129 {
1130 PR->Mult_nn(coef);
1131 // HANNES: mark for Normalize
1132 }
1133 n_Delete(&coef, currRing->cf);
1134 }
1135 return ret;
1136 }
1137
1138 /*2
1139 * reduction procedure for signature-based standard
1140 * basis algorithms:
1141 * all reductions have to be sig-safe!
1142 *
1143 * 2 is returned if and only if the pair is rejected by the rewritten criterion
1144 * at exactly this point of the computations. This is the last possible point
1145 * such a check can be done => checks with the biggest set of available
1146 * signatures
1147 */
1148
redSig(LObject * h,kStrategy strat)1149 int redSig (LObject* h,kStrategy strat)
1150 {
1151 if (strat->tl<0) return 1;
1152 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1153 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1154 assume(h->FDeg == h->pFDeg());
1155 //#if 1
1156 #ifdef DEBUGF5
1157 PrintS("------- IN REDSIG -------\n");
1158 Print("p: ");
1159 pWrite(pHead(h->p));
1160 PrintS("p1: ");
1161 pWrite(pHead(h->p1));
1162 PrintS("p2: ");
1163 pWrite(pHead(h->p2));
1164 PrintS("---------------------------\n");
1165 #endif
1166 poly h_p;
1167 int i,j,at,pass, ii;
1168 int start=0;
1169 int sigSafe;
1170 unsigned long not_sev;
1171 // long reddeg,d;
1172 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1173 int li;
1174
1175 pass = j = 0;
1176 // d = reddeg = h->GetpFDeg();
1177 h->SetShortExpVector();
1178 h_p = h->GetLmTailRing();
1179 not_sev = ~ h->sev;
1180 loop
1181 {
1182 j = kFindDivisibleByInT(strat, h, start);
1183 if (j < 0)
1184 {
1185 return 1;
1186 }
1187
1188 li = strat->T[j].pLength;
1189 if (li<=0) li=strat->T[j].GetpLength();
1190 ii = j;
1191 /*
1192 * the polynomial to reduce with (up to the moment) is;
1193 * pi with length li
1194 */
1195 i = j;
1196 #if 1
1197 if (test_opt_length)
1198 loop
1199 {
1200 /*- search the shortest possible with respect to length -*/
1201 i++;
1202 if (i > strat->tl)
1203 break;
1204 if (li==1)
1205 break;
1206 if ((strat->T[i].pLength < li)
1207 &&
1208 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1209 h_p, not_sev, strat->tailRing))
1210 {
1211 /*
1212 * the polynomial to reduce with is now;
1213 */
1214 li = strat->T[i].pLength;
1215 if (li<=0) li=strat->T[i].GetpLength();
1216 ii = i;
1217 }
1218 }
1219 start = ii+1;
1220 #endif
1221
1222 /*
1223 * end of search: have to reduce with pi
1224 */
1225 #ifdef KDEBUG
1226 if (TEST_OPT_DEBUG)
1227 {
1228 PrintS("red:");
1229 h->wrp();
1230 PrintS(" with ");
1231 strat->T[ii].wrp();
1232 }
1233 #endif
1234 assume(strat->fromT == FALSE);
1235 //#if 1
1236 #ifdef DEBUGF5
1237 Print("BEFORE REDUCTION WITH %d:\n",ii);
1238 PrintS("--------------------------------\n");
1239 pWrite(h->sig);
1240 pWrite(strat->T[ii].sig);
1241 pWrite(h->GetLmCurrRing());
1242 pWrite(pHead(h->p1));
1243 pWrite(pHead(h->p2));
1244 pWrite(pHead(strat->T[ii].p));
1245 PrintS("--------------------------------\n");
1246 printf("INDEX OF REDUCER T: %d\n",ii);
1247 #endif
1248 sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1249 #if SBA_PRINT_REDUCTION_STEPS
1250 if (sigSafe != 3)
1251 sba_reduction_steps++;
1252 #endif
1253 #if SBA_PRINT_OPERATIONS
1254 if (sigSafe != 3)
1255 sba_operations += pLength(strat->T[ii].p);
1256 #endif
1257 // if reduction has taken place, i.e. the reduction was sig-safe
1258 // otherwise start is already at the next position and the loop
1259 // searching reducers in T goes on from index start
1260 //#if 1
1261 #ifdef DEBUGF5
1262 Print("SigSAFE: %d\n",sigSafe);
1263 #endif
1264 if (sigSafe != 3)
1265 {
1266 // start the next search for reducers in T from the beginning
1267 start = 0;
1268 #ifdef KDEBUG
1269 if (TEST_OPT_DEBUG)
1270 {
1271 PrintS("\nto ");
1272 h->wrp();
1273 PrintLn();
1274 }
1275 #endif
1276
1277 h_p = h->GetLmTailRing();
1278 if (h_p == NULL)
1279 {
1280 kDeleteLcm(h);
1281 return 0;
1282 }
1283 h->SetShortExpVector();
1284 not_sev = ~ h->sev;
1285 /*
1286 * try to reduce the s-polynomial h
1287 *test first whether h should go to the lazyset L
1288 *-if the degree jumps
1289 *-if the number of pre-defined reductions jumps
1290 */
1291 pass++;
1292 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1293 {
1294 h->SetLmCurrRing();
1295 at = strat->posInL(strat->L,strat->Ll,h,strat);
1296 if (at <= strat->Ll)
1297 {
1298 int dummy=strat->sl;
1299 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1300 {
1301 return 1;
1302 }
1303 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1304 #ifdef KDEBUG
1305 if (TEST_OPT_DEBUG)
1306 Print(" lazy: -> L%d\n",at);
1307 #endif
1308 h->Clear();
1309 return -1;
1310 }
1311 }
1312 }
1313 }
1314 }
1315
1316
redSigRing(LObject * h,kStrategy strat)1317 int redSigRing (LObject* h,kStrategy strat)
1318 {
1319 //Since reduce is really bad for SBA we use the following idea:
1320 // We first check if we can build a gcd pair between h and S
1321 //where the sig remains the same and replace h by this gcd poly
1322 assume(rField_is_Ring(currRing));
1323 #if GCD_SBA
1324 while(sbaCheckGcdPair(h,strat))
1325 {
1326 h->sev = pGetShortExpVector(h->p);
1327 }
1328 #endif
1329 poly beforeredsig;
1330 beforeredsig = pCopy(h->sig);
1331
1332 if (strat->tl<0) return 1;
1333 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1334 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1335 assume(h->FDeg == h->pFDeg());
1336 //#if 1
1337 #ifdef DEBUGF5
1338 Print("------- IN REDSIG -------\n");
1339 Print("p: ");
1340 pWrite(pHead(h->p));
1341 Print("p1: ");
1342 pWrite(pHead(h->p1));
1343 Print("p2: ");
1344 pWrite(pHead(h->p2));
1345 Print("---------------------------\n");
1346 #endif
1347 poly h_p;
1348 int i,j,at,pass, ii;
1349 int start=0;
1350 int sigSafe;
1351 unsigned long not_sev;
1352 // long reddeg,d;
1353 int li;
1354 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1355
1356 pass = j = 0;
1357 // d = reddeg = h->GetpFDeg();
1358 h->SetShortExpVector();
1359 h_p = h->GetLmTailRing();
1360 not_sev = ~ h->sev;
1361 loop
1362 {
1363 j = kFindDivisibleByInT(strat, h, start);
1364 if (j < 0)
1365 {
1366 #if GCD_SBA
1367 while(sbaCheckGcdPair(h,strat))
1368 {
1369 h->sev = pGetShortExpVector(h->p);
1370 h->is_redundant = FALSE;
1371 start = 0;
1372 }
1373 #endif
1374 // over ZZ: cleanup coefficients by complete reduction with monomials
1375 postReduceByMonSig(h, strat);
1376 if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
1377 j = kFindDivisibleByInT(strat, h,start);
1378 if(j < 0)
1379 {
1380 if(strat->tl >= 0)
1381 h->i_r1 = strat->tl;
1382 else
1383 h->i_r1 = -1;
1384 if (h->GetLmTailRing() == NULL)
1385 {
1386 kDeleteLcm(h);
1387 h->Clear();
1388 return 0;
1389 }
1390 //Check for sigdrop after reduction
1391 if(pLtCmp(beforeredsig,h->sig) == 1)
1392 {
1393 strat->sigdrop = TRUE;
1394 //Reduce it as much as you can
1395 int red_result = redRing(h,strat);
1396 if(red_result == 0)
1397 {
1398 //It reduced to 0, cancel the sigdrop
1399 strat->sigdrop = FALSE;
1400 p_Delete(&h->sig,currRing);h->sig = NULL;
1401 return 0;
1402 }
1403 else
1404 {
1405 //strat->enterS(*h, strat->sl+1, strat, strat->tl);
1406 return 0;
1407 }
1408 }
1409 p_Delete(&beforeredsig,currRing);
1410 return 1;
1411 }
1412 }
1413
1414 li = strat->T[j].pLength;
1415 if (li<=0) li=strat->T[j].GetpLength();
1416 ii = j;
1417 /*
1418 * the polynomial to reduce with (up to the moment) is;
1419 * pi with length li
1420 */
1421 i = j;
1422 if (test_opt_length)
1423 loop
1424 {
1425 /*- search the shortest possible with respect to length -*/
1426 i++;
1427 if (i > strat->tl)
1428 break;
1429 if (li==1)
1430 break;
1431 if ((strat->T[i].pLength < li)
1432 && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1433 && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1434 h_p, not_sev, strat->tailRing))
1435 {
1436 /*
1437 * the polynomial to reduce with is now;
1438 */
1439 li = strat->T[i].pLength;
1440 if (li<=0) li=strat->T[i].GetpLength();
1441 ii = i;
1442 }
1443 }
1444
1445 start = ii+1;
1446
1447 /*
1448 * end of search: have to reduce with pi
1449 */
1450 #ifdef KDEBUG
1451 if (TEST_OPT_DEBUG)
1452 {
1453 PrintS("red:");
1454 h->wrp();
1455 PrintS(" with ");
1456 strat->T[ii].wrp();
1457 }
1458 #endif
1459 assume(strat->fromT == FALSE);
1460 //#if 1
1461 #ifdef DEBUGF5
1462 Print("BEFORE REDUCTION WITH %d:\n",ii);
1463 Print("--------------------------------\n");
1464 pWrite(h->sig);
1465 pWrite(strat->T[ii].sig);
1466 pWrite(h->GetLmCurrRing());
1467 pWrite(pHead(h->p1));
1468 pWrite(pHead(h->p2));
1469 pWrite(pHead(strat->T[ii].p));
1470 Print("--------------------------------\n");
1471 printf("INDEX OF REDUCER T: %d\n",ii);
1472 #endif
1473 sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1474 if(h->p == NULL && h->sig == NULL)
1475 {
1476 //Trivial case catch
1477 strat->sigdrop = FALSE;
1478 }
1479 #if 0
1480 //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1481 //In some cases this proves to be very bad
1482 if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1483 {
1484 int red_result = redRing(h,strat);
1485 if(red_result == 0)
1486 {
1487 pDelete(&h->sig);h->sig = NULL;
1488 return 0;
1489 }
1490 else
1491 {
1492 strat->sigdrop = TRUE;
1493 return 1;
1494 }
1495 }
1496 #endif
1497 if(strat->sigdrop)
1498 return 1;
1499 #if SBA_PRINT_REDUCTION_STEPS
1500 if (sigSafe != 3)
1501 sba_reduction_steps++;
1502 #endif
1503 #if SBA_PRINT_OPERATIONS
1504 if (sigSafe != 3)
1505 sba_operations += pLength(strat->T[ii].p);
1506 #endif
1507 // if reduction has taken place, i.e. the reduction was sig-safe
1508 // otherwise start is already at the next position and the loop
1509 // searching reducers in T goes on from index start
1510 //#if 1
1511 #ifdef DEBUGF5
1512 Print("SigSAFE: %d\n",sigSafe);
1513 #endif
1514 if (sigSafe != 3)
1515 {
1516 // start the next search for reducers in T from the beginning
1517 start = 0;
1518 #ifdef KDEBUG
1519 if (TEST_OPT_DEBUG)
1520 {
1521 PrintS("\nto ");
1522 h->wrp();
1523 PrintLn();
1524 }
1525 #endif
1526
1527 h_p = h->GetLmTailRing();
1528 if (h_p == NULL)
1529 {
1530 kDeleteLcm(h);
1531 return 0;
1532 }
1533 h->SetShortExpVector();
1534 not_sev = ~ h->sev;
1535 /*
1536 * try to reduce the s-polynomial h
1537 *test first whether h should go to the lazyset L
1538 *-if the degree jumps
1539 *-if the number of pre-defined reductions jumps
1540 */
1541 pass++;
1542 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1543 {
1544 h->SetLmCurrRing();
1545 at = strat->posInL(strat->L,strat->Ll,h,strat);
1546 if (at <= strat->Ll)
1547 {
1548 int dummy=strat->sl;
1549 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1550 {
1551 return 1;
1552 }
1553 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1554 #ifdef KDEBUG
1555 if (TEST_OPT_DEBUG)
1556 Print(" lazy: -> L%d\n",at);
1557 #endif
1558 h->Clear();
1559 return -1;
1560 }
1561 }
1562 }
1563 }
1564 }
1565
1566 // tail reduction for SBA
redtailSba(LObject * L,int pos,kStrategy strat,BOOLEAN withT,BOOLEAN normalize)1567 poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
1568 {
1569 strat->redTailChange=FALSE;
1570 if (strat->noTailReduction) return L->GetLmCurrRing();
1571 poly h, p;
1572 p = h = L->GetLmTailRing();
1573 if ((h==NULL) || (pNext(h)==NULL))
1574 return L->GetLmCurrRing();
1575
1576 TObject* With;
1577 // placeholder in case strat->tl < 0
1578 TObject With_s(strat->tailRing);
1579
1580 LObject Ln(pNext(h), strat->tailRing);
1581 Ln.sig = L->sig;
1582 Ln.sevSig = L->sevSig;
1583 Ln.pLength = L->GetpLength() - 1;
1584
1585 pNext(h) = NULL;
1586 if (L->p != NULL) pNext(L->p) = NULL;
1587 L->pLength = 1;
1588
1589 Ln.PrepareRed(strat->use_buckets);
1590
1591 int cnt=REDTAIL_CANONICALIZE;
1592 while(!Ln.IsNull())
1593 {
1594 loop
1595 {
1596 if(rField_is_Ring(currRing) && strat->sigdrop)
1597 break;
1598 Ln.SetShortExpVector();
1599 if (withT)
1600 {
1601 int j;
1602 j = kFindDivisibleByInT(strat, &Ln);
1603 if (j < 0) break;
1604 With = &(strat->T[j]);
1605 }
1606 else
1607 {
1608 With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1609 if (With == NULL) break;
1610 }
1611 cnt--;
1612 if (cnt==0)
1613 {
1614 cnt=REDTAIL_CANONICALIZE;
1615 /*poly tmp=*/Ln.CanonicalizeP();
1616 if (normalize && !rField_is_Ring(currRing))
1617 {
1618 Ln.Normalize();
1619 //pNormalize(tmp);
1620 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1621 }
1622 }
1623 if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
1624 {
1625 With->pNorm();
1626 }
1627 strat->redTailChange=TRUE;
1628 int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1629 if(rField_is_Ring(currRing))
1630 L->sig = Ln.sig;
1631 //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1632 // I delete it an then set Ln.sig. Hence L->sig is lost
1633 #if SBA_PRINT_REDUCTION_STEPS
1634 if (ret != 3)
1635 sba_reduction_steps++;
1636 #endif
1637 #if SBA_PRINT_OPERATIONS
1638 if (ret != 3)
1639 sba_operations += pLength(With->p);
1640 #endif
1641 if (ret)
1642 {
1643 // reducing the tail would violate the exp bound
1644 // set a flag and hope for a retry (in bba)
1645 strat->completeReduce_retry=TRUE;
1646 if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1647 do
1648 {
1649 pNext(h) = Ln.LmExtractAndIter();
1650 pIter(h);
1651 L->pLength++;
1652 } while (!Ln.IsNull());
1653 goto all_done;
1654 }
1655 if (Ln.IsNull()) goto all_done;
1656 if (! withT) With_s.Init(currRing);
1657 if(rField_is_Ring(currRing) && strat->sigdrop)
1658 {
1659 //Cannot break the loop here so easily
1660 break;
1661 }
1662 }
1663 pNext(h) = Ln.LmExtractAndIter();
1664 pIter(h);
1665 if(!rField_is_Ring(currRing))
1666 pNormalize(h);
1667 L->pLength++;
1668 }
1669 all_done:
1670 Ln.Delete();
1671 if (L->p != NULL) pNext(L->p) = pNext(p);
1672
1673 if (strat->redTailChange)
1674 {
1675 L->length = 0;
1676 }
1677 //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1678 //L->Normalize(); // HANNES: should have a test
1679 kTest_L(L,strat->tailRing);
1680 return L->GetLmCurrRing();
1681 }
1682
1683 /*2
1684 * reduction procedure for the inhomogeneous case
1685 * and not a degree-ordering
1686 */
redLazy(LObject * h,kStrategy strat)1687 int redLazy (LObject* h,kStrategy strat)
1688 {
1689 if (strat->tl<0) return 1;
1690 int at,i,ii,li;
1691 int j = 0;
1692 int pass = 0;
1693 int cnt = RED_CANONICALIZE;
1694 assume(h->pFDeg() == h->FDeg);
1695 long reddeg = h->GetpFDeg();
1696 long d;
1697 unsigned long not_sev;
1698 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1699
1700 h->SetShortExpVector();
1701 poly h_p = h->GetLmTailRing();
1702 not_sev = ~ h->sev;
1703 h->PrepareRed(strat->use_buckets);
1704 loop
1705 {
1706 j = kFindDivisibleByInT(strat, h);
1707 if (j < 0) return 1;
1708
1709 li = strat->T[j].pLength;
1710 ii = j;
1711 /*
1712 * the polynomial to reduce with (up to the moment) is;
1713 * pi with length li
1714 */
1715
1716 i = j;
1717 #if 1
1718 if (test_opt_length)
1719 {
1720 if (li<=0) li=strat->T[j].GetpLength();
1721 if(li>2)
1722 loop
1723 {
1724 /*- search the shortest possible with respect to length -*/
1725 i++;
1726 if (i > strat->tl)
1727 break;
1728 if ((strat->T[i].pLength < li)
1729 &&
1730 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1731 h_p, not_sev, strat->tailRing))
1732 {
1733 /*
1734 * the polynomial to reduce with is now;
1735 */
1736 li = strat->T[i].pLength;
1737 if (li<=0) li=strat->T[i].GetpLength();
1738 ii = i;
1739 if (li<3) break;
1740 }
1741 }
1742 }
1743 #endif
1744
1745 /*
1746 * end of search: have to reduce with pi
1747 */
1748
1749
1750 #ifdef KDEBUG
1751 if (TEST_OPT_DEBUG)
1752 {
1753 PrintS("red:");
1754 h->wrp();
1755 PrintS(" with ");
1756 strat->T[ii].wrp();
1757 }
1758 #endif
1759
1760 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1761 #if SBA_PRINT_REDUCTION_STEPS
1762 sba_interreduction_steps++;
1763 #endif
1764 #if SBA_PRINT_OPERATIONS
1765 sba_interreduction_operations += pLength(strat->T[ii].p);
1766 #endif
1767
1768 #ifdef KDEBUG
1769 if (TEST_OPT_DEBUG)
1770 {
1771 PrintS("\nto ");
1772 h->wrp();
1773 PrintLn();
1774 }
1775 #endif
1776
1777 h_p=h->GetLmTailRing();
1778
1779 if (h_p == NULL)
1780 {
1781 kDeleteLcm(h);
1782 return 0;
1783 }
1784 if (UNLIKELY(TEST_OPT_IDLIFT))
1785 {
1786 if (h->p!=NULL)
1787 {
1788 if(p_GetComp(h->p,currRing)>strat->syzComp)
1789 {
1790 h->Delete();
1791 return 0;
1792 }
1793 }
1794 else if (h->t_p!=NULL)
1795 {
1796 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1797 {
1798 h->Delete();
1799 return 0;
1800 }
1801 }
1802 }
1803 #if 0
1804 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1805 {
1806 if (h->p!=NULL)
1807 {
1808 if(p_GetComp(h->p,currRing)>strat->syzComp)
1809 {
1810 return 1;
1811 }
1812 }
1813 else if (h->t_p!=NULL)
1814 {
1815 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1816 {
1817 return 1;
1818 }
1819 }
1820 }
1821 #endif
1822 h->SetShortExpVector();
1823 not_sev = ~ h->sev;
1824 d = h->SetpFDeg();
1825 /*- try to reduce the s-polynomial -*/
1826 cnt--;
1827 pass++;
1828 if (//!TEST_OPT_REDTHROUGH &&
1829 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1830 {
1831 h->SetLmCurrRing();
1832 at = strat->posInL(strat->L,strat->Ll,h,strat);
1833 if (at <= strat->Ll)
1834 {
1835 #if 1
1836 #ifdef HAVE_SHIFTBBA
1837 if (rIsLPRing(currRing))
1838 {
1839 if (kFindDivisibleByInT(strat, h) < 0)
1840 return 1;
1841 }
1842 else
1843 #endif
1844 {
1845 int dummy=strat->sl;
1846 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1847 return 1;
1848 }
1849 #endif
1850 #ifdef KDEBUG
1851 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1852 #endif
1853 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1854 h->Clear();
1855 return -1;
1856 }
1857 }
1858 else if (d != reddeg)
1859 {
1860 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1861 {
1862 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1863 {
1864 strat->overflow=TRUE;
1865 //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1866 h->GetP();
1867 at = strat->posInL(strat->L,strat->Ll,h,strat);
1868 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1869 h->Clear();
1870 return -1;
1871 }
1872 }
1873 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1874 {
1875 Print(".%ld",d);mflush();
1876 reddeg = d;
1877 }
1878 }
1879 else if (UNLIKELY(cnt==0))
1880 {
1881 h->CanonicalizeP();
1882 cnt=RED_CANONICALIZE;
1883 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1884 }
1885 }
1886 }
1887 /*2
1888 * reduction procedure for the sugar-strategy (honey)
1889 * reduces h with elements from T choosing first possible
1890 * element in T with respect to the given ecart
1891 */
redHoney(LObject * h,kStrategy strat)1892 int redHoney (LObject* h, kStrategy strat)
1893 {
1894 if (strat->tl<0) return 1;
1895 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1896 assume(h->FDeg == h->pFDeg());
1897 poly h_p;
1898 int i,j,at,pass,ei, ii, h_d;
1899 unsigned long not_sev;
1900 long reddeg,d;
1901 int li;
1902 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1903
1904 pass = j = 0;
1905 d = reddeg = h->GetpFDeg() + h->ecart;
1906 h->SetShortExpVector();
1907 h_p = h->GetLmTailRing();
1908 not_sev = ~ h->sev;
1909
1910 h->PrepareRed(strat->use_buckets);
1911 loop
1912 {
1913 j=kFindDivisibleByInT(strat, h);
1914 if (j < 0) return 1;
1915
1916 ei = strat->T[j].ecart;
1917 li = strat->T[j].pLength;
1918 ii = j;
1919 /*
1920 * the polynomial to reduce with (up to the moment) is;
1921 * pi with ecart ei (T[ii])
1922 */
1923 i = j;
1924 if (test_opt_length)
1925 {
1926 if (li<=0) li=strat->T[j].GetpLength();
1927 if (li>2)
1928 loop
1929 {
1930 /*- takes the first possible with respect to ecart -*/
1931 i++;
1932 if (i > strat->tl) break;
1933 if (ei <= h->ecart) break;
1934 if(p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1935 h_p, not_sev, strat->tailRing))
1936 {
1937 strat->T[i].GetpLength();
1938 if (((strat->T[i].ecart < ei) && (ei> h->ecart))
1939 || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1940 {
1941 /*
1942 * the polynomial to reduce with is now;
1943 */
1944 ei = strat->T[i].ecart;
1945 li = strat->T[i].pLength;
1946 ii = i;
1947 if (li==1) break;
1948 if (ei<=h->ecart) break;
1949 }
1950 }
1951 }
1952 }
1953
1954 /*
1955 * end of search: have to reduce with pi
1956 */
1957 if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
1958 {
1959 h->GetTP(); // clears bucket
1960 h->SetLmCurrRing();
1961 /*
1962 * It is not possible to reduce h with smaller ecart;
1963 * if possible h goes to the lazy-set L,i.e
1964 * if its position in L would be not the last one
1965 */
1966 if (strat->Ll >= 0) /* L is not empty */
1967 {
1968 at = strat->posInL(strat->L,strat->Ll,h,strat);
1969 if(at <= strat->Ll)
1970 /*- h will not become the next element to reduce -*/
1971 {
1972 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1973 #ifdef KDEBUG
1974 if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1975 #endif
1976 h->Clear();
1977 return -1;
1978 }
1979 }
1980 }
1981 #ifdef KDEBUG
1982 if (TEST_OPT_DEBUG)
1983 {
1984 PrintS("red:");
1985 h->wrp();
1986 Print("\nwith T[%d]:",ii);
1987 strat->T[ii].wrp();
1988 }
1989 #endif
1990 assume(strat->fromT == FALSE);
1991
1992 ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
1993 #if SBA_PRINT_REDUCTION_STEPS
1994 sba_interreduction_steps++;
1995 #endif
1996 #if SBA_PRINT_OPERATIONS
1997 sba_interreduction_operations += strat->T[ii].pLength;
1998 #endif
1999 #ifdef KDEBUG
2000 if (TEST_OPT_DEBUG)
2001 {
2002 PrintS("\nto:");
2003 h->wrp();
2004 PrintLn();
2005 }
2006 #endif
2007 if(h->IsNull())
2008 {
2009 kDeleteLcm(h);
2010 h->Clear();
2011 return 0;
2012 }
2013 if (UNLIKELY(TEST_OPT_IDLIFT))
2014 {
2015 if (h->p!=NULL)
2016 {
2017 if(p_GetComp(h->p,currRing)>strat->syzComp)
2018 {
2019 h->Delete();
2020 return 0;
2021 }
2022 }
2023 else if (h->t_p!=NULL)
2024 {
2025 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2026 {
2027 h->Delete();
2028 return 0;
2029 }
2030 }
2031 }
2032 else if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
2033 {
2034 if (h->p!=NULL)
2035 {
2036 if(p_GetComp(h->p,currRing)>strat->syzComp)
2037 {
2038 return 1;
2039 }
2040 }
2041 else if (h->t_p!=NULL)
2042 {
2043 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2044 {
2045 return 1;
2046 }
2047 }
2048 }
2049 h->SetShortExpVector();
2050 not_sev = ~ h->sev;
2051 h_d = h->SetpFDeg();
2052 /* compute the ecart */
2053 if (ei <= h->ecart)
2054 h->ecart = d-h_d;
2055 else
2056 h->ecart = d-h_d+ei-h->ecart;
2057
2058 /*
2059 * try to reduce the s-polynomial h
2060 *test first whether h should go to the lazyset L
2061 *-if the degree jumps
2062 *-if the number of pre-defined reductions jumps
2063 */
2064 pass++;
2065 d = h_d + h->ecart;
2066 if (UNLIKELY(!TEST_OPT_REDTHROUGH
2067 && (strat->Ll >= 0)
2068 && ((d > reddeg) || (pass > strat->LazyPass))))
2069 {
2070 h->GetTP(); // clear bucket
2071 h->SetLmCurrRing();
2072 at = strat->posInL(strat->L,strat->Ll,h,strat);
2073 if (at <= strat->Ll)
2074 {
2075 #ifdef HAVE_SHIFTBBA
2076 if (rIsLPRing(currRing))
2077 {
2078 if (kFindDivisibleByInT(strat, h) < 0)
2079 return 1;
2080 }
2081 else
2082 #endif
2083 {
2084 int dummy=strat->sl;
2085 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2086 return 1;
2087 }
2088 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2089 #ifdef KDEBUG
2090 if (TEST_OPT_DEBUG)
2091 Print(" degree jumped: -> L%d\n",at);
2092 #endif
2093 h->Clear();
2094 return -1;
2095 }
2096 }
2097 else if (d > reddeg)
2098 {
2099 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2100 {
2101 if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2102 {
2103 strat->overflow=TRUE;
2104 //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2105 h->GetP();
2106 at = strat->posInL(strat->L,strat->Ll,h,strat);
2107 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2108 h->Clear();
2109 return -1;
2110 }
2111 }
2112 else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
2113 {
2114 //h->wrp(); Print("<%d>\n",h->GetpLength());
2115 reddeg = d;
2116 Print(".%ld",d); mflush();
2117 }
2118 }
2119 }
2120 }
2121
2122 /*2
2123 * reduction procedure for the normal form
2124 */
2125
redNF(poly h,int & max_ind,int nonorm,kStrategy strat)2126 poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
2127 {
2128 if (h==NULL) return NULL;
2129 int j;
2130 int cnt=REDNF_CANONICALIZE;
2131 max_ind=strat->sl;
2132
2133 if (0 > strat->sl)
2134 {
2135 return h;
2136 }
2137 LObject P(h);
2138 P.SetShortExpVector();
2139 P.bucket = kBucketCreate(currRing);
2140 kBucketInit(P.bucket,P.p,pLength(P.p));
2141 kbTest(P.bucket);
2142 #ifdef HAVE_RINGS
2143 BOOLEAN is_ring = rField_is_Ring(currRing);
2144 #endif
2145 #ifdef KDEBUG
2146 // if (TEST_OPT_DEBUG)
2147 // {
2148 // PrintS("redNF: starting S:\n");
2149 // for( j = 0; j <= max_ind; j++ )
2150 // {
2151 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2152 // pWrite(strat->S[j]);
2153 // }
2154 // };
2155 #endif
2156
2157 loop
2158 {
2159 j=kFindDivisibleByInS(strat,&max_ind,&P);
2160 if (j>=0)
2161 {
2162 #ifdef HAVE_RINGS
2163 if (!is_ring)
2164 {
2165 #endif
2166 int sl=pSize(strat->S[j]);
2167 int jj=j;
2168 loop
2169 {
2170 int sll;
2171 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2172 if (jj<0) break;
2173 sll=pSize(strat->S[jj]);
2174 if (sll<sl)
2175 {
2176 #ifdef KDEBUG
2177 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2178 #endif
2179 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2180 j=jj;
2181 sl=sll;
2182 }
2183 }
2184 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2185 {
2186 pNorm(strat->S[j]);
2187 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2188 }
2189 #ifdef HAVE_RINGS
2190 }
2191 #endif
2192 nNormalize(pGetCoeff(P.p));
2193 #ifdef KDEBUG
2194 if (TEST_OPT_DEBUG)
2195 {
2196 PrintS("red:");
2197 wrp(h);
2198 PrintS(" with ");
2199 wrp(strat->S[j]);
2200 }
2201 #endif
2202 #ifdef HAVE_PLURAL
2203 if (rIsPluralRing(currRing))
2204 {
2205 number coef;
2206 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2207 nDelete(&coef);
2208 }
2209 else
2210 #endif
2211 {
2212 number coef;
2213 coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2214 nDelete(&coef);
2215 }
2216 cnt--;
2217 if (cnt==0)
2218 {
2219 kBucketCanonicalize(P.bucket);
2220 cnt=REDNF_CANONICALIZE;
2221 }
2222 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2223 if (h==NULL)
2224 {
2225 kBucketDestroy(&P.bucket);
2226 return NULL;
2227 }
2228 kbTest(P.bucket);
2229 P.p=h;
2230 P.t_p=NULL;
2231 P.SetShortExpVector();
2232 #ifdef KDEBUG
2233 if (TEST_OPT_DEBUG)
2234 {
2235 PrintS("\nto:");
2236 wrp(h);
2237 PrintLn();
2238 }
2239 #endif
2240 }
2241 else
2242 {
2243 P.p=kBucketClear(P.bucket);
2244 kBucketDestroy(&P.bucket);
2245 pNormalize(P.p);
2246 return P.p;
2247 }
2248 }
2249 }
2250
2251 /*2
2252 * reduction procedure from global case but with jet bound
2253 */
2254
redNFBound(poly h,int & max_ind,int nonorm,kStrategy strat,int bound)2255 poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
2256 {
2257 h = pJet(h,bound);
2258 if (h==NULL) return NULL;
2259 int j;
2260 max_ind=strat->sl;
2261
2262 if (0 > strat->sl)
2263 {
2264 return h;
2265 }
2266 LObject P(h);
2267 P.SetShortExpVector();
2268 P.bucket = kBucketCreate(currRing);
2269 kBucketInit(P.bucket,P.p,pLength(P.p));
2270 kbTest(P.bucket);
2271 #ifdef HAVE_RINGS
2272 BOOLEAN is_ring = rField_is_Ring(currRing);
2273 #endif
2274
2275 loop
2276 {
2277 j=kFindDivisibleByInS(strat,&max_ind,&P);
2278 if (j>=0)
2279 {
2280 #ifdef HAVE_RINGS
2281 if (!is_ring)
2282 {
2283 #endif
2284 int sl=pSize(strat->S[j]);
2285 int jj=j;
2286 loop
2287 {
2288 int sll;
2289 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2290 if (jj<0) break;
2291 sll=pSize(strat->S[jj]);
2292 if (sll<sl)
2293 {
2294 #ifdef KDEBUG
2295 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2296 #endif
2297 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2298 j=jj;
2299 sl=sll;
2300 }
2301 }
2302 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2303 {
2304 pNorm(strat->S[j]);
2305 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2306 }
2307 #ifdef HAVE_RINGS
2308 }
2309 #endif
2310 nNormalize(pGetCoeff(P.p));
2311 #ifdef KDEBUG
2312 if (TEST_OPT_DEBUG)
2313 {
2314 PrintS("red:");
2315 wrp(h);
2316 PrintS(" with ");
2317 wrp(strat->S[j]);
2318 }
2319 #endif
2320 #ifdef HAVE_PLURAL
2321 if (rIsPluralRing(currRing))
2322 {
2323 number coef;
2324 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2325 nDelete(&coef);
2326 }
2327 else
2328 #endif
2329 {
2330 number coef;
2331 coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2332 P.p = kBucketClear(P.bucket);
2333 P.p = pJet(P.p,bound);
2334 if(!P.IsNull())
2335 {
2336 kBucketDestroy(&P.bucket);
2337 P.SetShortExpVector();
2338 P.bucket = kBucketCreate(currRing);
2339 kBucketInit(P.bucket,P.p,pLength(P.p));
2340 }
2341 nDelete(&coef);
2342 }
2343 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2344 if (h==NULL)
2345 {
2346 kBucketDestroy(&P.bucket);
2347 return NULL;
2348 }
2349 kbTest(P.bucket);
2350 P.p=h;
2351 P.t_p=NULL;
2352 P.SetShortExpVector();
2353 #ifdef KDEBUG
2354 if (TEST_OPT_DEBUG)
2355 {
2356 PrintS("\nto:");
2357 wrp(h);
2358 PrintLn();
2359 }
2360 #endif
2361 }
2362 else
2363 {
2364 P.p=kBucketClear(P.bucket);
2365 kBucketDestroy(&P.bucket);
2366 pNormalize(P.p);
2367 return P.p;
2368 }
2369 }
2370 }
2371
2372 void kDebugPrint(kStrategy strat);
2373
bba(ideal F,ideal Q,intvec * w,intvec * hilb,kStrategy strat)2374 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2375 {
2376 int red_result = 1;
2377 int olddeg,reduc;
2378 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2379 BOOLEAN withT = FALSE;
2380 BITSET save;
2381 SI_SAVE_OPT1(save);
2382
2383 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2384 if(rField_is_Ring(currRing))
2385 initBuchMoraPosRing(strat);
2386 else
2387 initBuchMoraPos(strat);
2388 initHilbCrit(F,Q,&hilb,strat);
2389 initBba(strat);
2390 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2391 /*Shdl=*/initBuchMora(F, Q,strat);
2392 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2393 reduc = olddeg = 0;
2394
2395 #ifndef NO_BUCKETS
2396 if (!TEST_OPT_NOT_BUCKETS)
2397 strat->use_buckets = 1;
2398 #endif
2399 // redtailBBa against T for inhomogenous input
2400 if (!TEST_OPT_OLDSTD)
2401 withT = ! strat->homog;
2402
2403 // strat->posInT = posInT_pLength;
2404 kTest_TS(strat);
2405
2406 #ifdef HAVE_TAIL_RING
2407 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2408 kStratInitChangeTailRing(strat);
2409 #endif
2410 if (BVERBOSE(23))
2411 {
2412 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2413 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2414 kDebugPrint(strat);
2415 }
2416
2417
2418 #ifdef KDEBUG
2419 //kDebugPrint(strat);
2420 #endif
2421 /* compute------------------------------------------------------- */
2422 while (strat->Ll >= 0)
2423 {
2424 #ifdef KDEBUG
2425 if (TEST_OPT_DEBUG) messageSets(strat);
2426 #endif
2427 if (siCntrlc)
2428 {
2429 while (strat->Ll >= 0)
2430 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2431 strat->noClearS=TRUE;
2432 }
2433 if (TEST_OPT_DEGBOUND
2434 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2435 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2436 {
2437 /*
2438 *stops computation if
2439 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2440 *a predefined number Kstd1_deg
2441 */
2442 while ((strat->Ll >= 0)
2443 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2444 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2445 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2446 )
2447 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2448 if (strat->Ll<0) break;
2449 else strat->noClearS=TRUE;
2450 }
2451 if (strat->Ll== 0) strat->interpt=TRUE;
2452 /* picks the last element from the lazyset L */
2453 strat->P = strat->L[strat->Ll];
2454 strat->Ll--;
2455
2456 if (pNext(strat->P.p) == strat->tail)
2457 {
2458 // deletes the short spoly
2459 if (rField_is_Ring(currRing))
2460 pLmDelete(strat->P.p);
2461 else
2462 pLmFree(strat->P.p);
2463 strat->P.p = NULL;
2464 poly m1 = NULL, m2 = NULL;
2465
2466 // check that spoly creation is ok
2467 while (strat->tailRing != currRing &&
2468 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2469 {
2470 assume(m1 == NULL && m2 == NULL);
2471 // if not, change to a ring where exponents are at least
2472 // large enough
2473 if (!kStratChangeTailRing(strat))
2474 {
2475 WerrorS("OVERFLOW...");
2476 break;
2477 }
2478 }
2479 // create the real one
2480 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2481 strat->tailRing, m1, m2, strat->R);
2482 }
2483 else if (strat->P.p1 == NULL)
2484 {
2485 if (strat->minim > 0)
2486 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2487 // for input polys, prepare reduction
2488 strat->P.PrepareRed(strat->use_buckets);
2489 }
2490
2491 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2492 {
2493 red_result = 0;
2494 }
2495 else
2496 {
2497 if (TEST_OPT_PROT)
2498 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2499 &olddeg,&reduc,strat, red_result);
2500
2501 /* reduction of the element chosen from L */
2502 red_result = strat->red(&strat->P,strat);
2503 if (errorreported) break;
2504 }
2505
2506 if (strat->overflow)
2507 {
2508 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2509 }
2510
2511 // reduction to non-zero new poly
2512 if (red_result == 1)
2513 {
2514 // get the polynomial (canonicalize bucket, make sure P.p is set)
2515 strat->P.GetP(strat->lmBin);
2516 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2517 // but now, for entering S, T, we reset it
2518 // in the inhomogeneous case: FDeg == pFDeg
2519 if (strat->homog) strat->initEcart(&(strat->P));
2520
2521 /* statistic */
2522 if (TEST_OPT_PROT) PrintS("s");
2523
2524 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2525
2526 // reduce the tail and normalize poly
2527 // in the ring case we cannot expect LC(f) = 1,
2528 // therefore we call pCleardenom instead of pNorm
2529 strat->redTailChange=FALSE;
2530
2531 /* if we are computing over Z we always want to try and cut down
2532 * the coefficients in the tail terms */
2533 if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing))
2534 {
2535 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2536 strat->P.pCleardenom();
2537 }
2538
2539 if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
2540 {
2541 strat->P.pCleardenom();
2542 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2543 {
2544 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2545 strat->P.pCleardenom();
2546 if (strat->redTailChange) { strat->P.t_p=NULL; }
2547 }
2548 }
2549 else
2550 {
2551 strat->P.pNorm();
2552 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2553 {
2554 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2555 if (strat->redTailChange) { strat->P.t_p=NULL; }
2556 }
2557 }
2558
2559 #ifdef KDEBUG
2560 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2561 #endif /* KDEBUG */
2562
2563 // min_std stuff
2564 if ((strat->P.p1==NULL) && (strat->minim>0))
2565 {
2566 if (strat->minim==1)
2567 {
2568 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2569 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2570 }
2571 else
2572 {
2573 strat->M->m[minimcnt]=strat->P.p2;
2574 strat->P.p2=NULL;
2575 }
2576 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2577 pNext(strat->M->m[minimcnt])
2578 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2579 strat->tailRing, currRing,
2580 currRing->PolyBin);
2581 minimcnt++;
2582 }
2583
2584 // enter into S, L, and T
2585 if (((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2586 && ((!TEST_OPT_IDELIM) || (p_Deg(strat->P.p,currRing) > 0)))
2587 {
2588 enterT(strat->P, strat);
2589 if (rField_is_Ring(currRing))
2590 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2591 else
2592 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2593 // posInS only depends on the leading term
2594 strat->enterS(strat->P, pos, strat, strat->tl);
2595 #if 0
2596 int pl=pLength(strat->P.p);
2597 if (pl==1)
2598 {
2599 //if (TEST_OPT_PROT)
2600 //PrintS("<1>");
2601 }
2602 else if (pl==2)
2603 {
2604 //if (TEST_OPT_PROT)
2605 //PrintS("<2>");
2606 }
2607 #endif
2608 }
2609 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2610 // Print("[%d]",hilbeledeg);
2611 kDeleteLcm(&strat->P);
2612 if (strat->s_poly!=NULL)
2613 {
2614 // the only valid entries are: strat->P.p,
2615 // strat->tailRing (read-only, keep it)
2616 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2617 if (strat->s_poly(strat))
2618 {
2619 // we are called AFTER enterS, i.e. if we change P
2620 // we have to add it also to S/T
2621 // and add pairs
2622 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2623 enterT(strat->P, strat);
2624 if (rField_is_Ring(currRing))
2625 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2626 else
2627 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2628 strat->enterS(strat->P, pos, strat, strat->tl);
2629 }
2630 }
2631 }
2632 else if (strat->P.p1 == NULL && strat->minim > 0)
2633 {
2634 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2635 }
2636
2637 #ifdef KDEBUG
2638 memset(&(strat->P), 0, sizeof(strat->P));
2639 #endif /* KDEBUG */
2640 kTest_TS(strat);
2641 }
2642 #ifdef KDEBUG
2643 if (TEST_OPT_DEBUG) messageSets(strat);
2644 #endif /* KDEBUG */
2645
2646 if (TEST_OPT_SB_1)
2647 {
2648 if(!rField_is_Ring(currRing))
2649 {
2650 int k=1;
2651 int j;
2652 while(k<=strat->sl)
2653 {
2654 j=0;
2655 loop
2656 {
2657 if (j>=k) break;
2658 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2659 j++;
2660 }
2661 k++;
2662 }
2663 }
2664 }
2665 /* complete reduction of the standard basis--------- */
2666 if (TEST_OPT_REDSB)
2667 {
2668 completeReduce(strat);
2669 if (strat->completeReduce_retry)
2670 {
2671 // completeReduce needed larger exponents, retry
2672 // to reduce with S (instead of T)
2673 // and in currRing (instead of strat->tailRing)
2674 #ifdef HAVE_TAIL_RING
2675 if(currRing->bitmask>strat->tailRing->bitmask)
2676 {
2677 strat->completeReduce_retry=FALSE;
2678 cleanT(strat);strat->tailRing=currRing;
2679 int i;
2680 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2681 completeReduce(strat);
2682 }
2683 if (strat->completeReduce_retry)
2684 #endif
2685 Werror("exponent bound is %ld",currRing->bitmask);
2686 }
2687 }
2688 else if (TEST_OPT_PROT) PrintLn();
2689 /* release temp data-------------------------------- */
2690 exitBuchMora(strat);
2691 /* postprocessing for GB over ZZ --------------------*/
2692 if (!errorreported)
2693 {
2694 if(rField_is_Z(currRing))
2695 {
2696 for(int i = 0;i<=strat->sl;i++)
2697 {
2698 if(!nGreaterZero(pGetCoeff(strat->S[i])))
2699 {
2700 strat->S[i] = pNeg(strat->S[i]);
2701 }
2702 }
2703 finalReduceByMon(strat);
2704 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2705 {
2706 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2707 {
2708 strat->S[i] = pNeg(strat->Shdl->m[i]);
2709 }
2710 }
2711 }
2712 //else if (rField_is_Ring(currRing))
2713 // finalReduceByMon(strat);
2714 }
2715 // if (TEST_OPT_WEIGHTM)
2716 // {
2717 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2718 // if (ecartWeights)
2719 // {
2720 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2721 // ecartWeights=NULL;
2722 // }
2723 // }
2724 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2725 SI_RESTORE_OPT1(save);
2726 /* postprocessing for GB over Q-rings ------------------*/
2727 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2728
2729 idTest(strat->Shdl);
2730
2731 return (strat->Shdl);
2732 }
2733
sba(ideal F0,ideal Q,intvec * w,intvec * hilb,kStrategy strat)2734 ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2735 {
2736 // ring order stuff:
2737 // in sba we have (until now) two possibilities:
2738 // 1. an incremental computation w.r.t. (C,monomial order)
2739 // 2. a (possibly non-incremental) computation w.r.t. the
2740 // induced Schreyer order.
2741 // The corresponding orders are computed in sbaRing(), depending
2742 // on the flag strat->sbaOrder
2743 #if SBA_PRINT_ZERO_REDUCTIONS
2744 long zeroreductions = 0;
2745 #endif
2746 #if SBA_PRINT_PRODUCT_CRITERION
2747 long product_criterion = 0;
2748 #endif
2749 #if SBA_PRINT_SIZE_G
2750 int size_g = 0;
2751 int size_g_non_red = 0;
2752 #endif
2753 #if SBA_PRINT_SIZE_SYZ
2754 long size_syz = 0;
2755 #endif
2756 // global variable
2757 #if SBA_PRINT_REDUCTION_STEPS
2758 sba_reduction_steps = 0;
2759 sba_interreduction_steps = 0;
2760 #endif
2761 #if SBA_PRINT_OPERATIONS
2762 sba_operations = 0;
2763 sba_interreduction_operations = 0;
2764 #endif
2765
2766 ideal F1 = F0;
2767 ring sRing, currRingOld;
2768 currRingOld = currRing;
2769 if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
2770 {
2771 sRing = sbaRing(strat);
2772 if (sRing!=currRingOld)
2773 {
2774 rChangeCurrRing (sRing);
2775 F1 = idrMoveR (F0, currRingOld, currRing);
2776 }
2777 }
2778 ideal F;
2779 // sort ideal F
2780 //Put the SigDrop element on the correct position (think of sbaEnterS)
2781 //We also sort them
2782 if(rField_is_Ring(currRing) && strat->sigdrop)
2783 {
2784 #if 1
2785 F = idInit(IDELEMS(F1),F1->rank);
2786 for (int i=0; i<IDELEMS(F1);++i)
2787 F->m[i] = F1->m[i];
2788 if(strat->sbaEnterS >= 0)
2789 {
2790 poly dummy;
2791 dummy = pCopy(F->m[0]); //the sigdrop element
2792 for(int i = 0;i<strat->sbaEnterS;i++)
2793 F->m[i] = F->m[i+1];
2794 F->m[strat->sbaEnterS] = dummy;
2795 }
2796 #else
2797 F = idInit(1,F1->rank);
2798 //printf("\nBefore the initial block sorting:\n");idPrint(F1);
2799 F->m[0] = F1->m[0];
2800 int pos;
2801 if(strat->sbaEnterS >= 0)
2802 {
2803 for(int i=1;i<=strat->sbaEnterS;i++)
2804 {
2805 pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2806 idInsertPolyOnPos(F,F1->m[i],pos);
2807 }
2808 for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2809 {
2810 pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2811 idInsertPolyOnPos(F,F1->m[i],pos);
2812 }
2813 poly dummy;
2814 dummy = pCopy(F->m[0]); //the sigdrop element
2815 for(int i = 0;i<strat->sbaEnterS;i++)
2816 F->m[i] = F->m[i+1];
2817 F->m[strat->sbaEnterS] = dummy;
2818 }
2819 else
2820 {
2821 for(int i=1;i<IDELEMS(F1);i++)
2822 {
2823 pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2824 idInsertPolyOnPos(F,F1->m[i],pos);
2825 }
2826 }
2827 #endif
2828 //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2829 }
2830 else
2831 {
2832 F = idInit(IDELEMS(F1),F1->rank);
2833 intvec *sort = idSort(F1);
2834 for (int i=0; i<sort->length();++i)
2835 F->m[i] = F1->m[(*sort)[i]-1];
2836 if(rField_is_Ring(currRing))
2837 {
2838 // put the monomials after the sbaEnterS polynomials
2839 //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2840 int nrmon = 0;
2841 for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2842 {
2843 //pWrite(F->m[i]);
2844 if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2845 {
2846 poly mon = F->m[i];
2847 for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2848 {
2849 F->m[j] = F->m[j-1];
2850 }
2851 F->m[j] = mon;
2852 nrmon++;
2853 }
2854 //idPrint(F);
2855 }
2856 }
2857 }
2858 //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2859 if(rField_is_Ring(currRing))
2860 strat->sigdrop = FALSE;
2861 strat->nrsyzcrit = 0;
2862 strat->nrrewcrit = 0;
2863 #if SBA_INTERRED_START
2864 F = kInterRed(F,NULL);
2865 #endif
2866 #if F5DEBUG
2867 printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2868 rWrite (currRing);
2869 printf("ordSgn = %d\n",currRing->OrdSgn);
2870 printf("\n");
2871 #endif
2872 int srmax,lrmax, red_result = 1;
2873 int olddeg,reduc;
2874 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2875 LObject L;
2876 BOOLEAN withT = TRUE;
2877 strat->max_lower_index = 0;
2878 //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2879 initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
2880 initSbaPos(strat);
2881 initHilbCrit(F,Q,&hilb,strat);
2882 initSba(F,strat);
2883 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2884 /*Shdl=*/initSbaBuchMora(F, Q,strat);
2885 idTest(strat->Shdl);
2886 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2887 srmax = strat->sl;
2888 reduc = olddeg = lrmax = 0;
2889 #ifndef NO_BUCKETS
2890 if (!TEST_OPT_NOT_BUCKETS)
2891 strat->use_buckets = 1;
2892 #endif
2893
2894 // redtailBBa against T for inhomogenous input
2895 // if (!TEST_OPT_OLDSTD)
2896 // withT = ! strat->homog;
2897
2898 // strat->posInT = posInT_pLength;
2899 kTest_TS(strat);
2900
2901 #ifdef HAVE_TAIL_RING
2902 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2903 kStratInitChangeTailRing(strat);
2904 #endif
2905 if (BVERBOSE(23))
2906 {
2907 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2908 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2909 kDebugPrint(strat);
2910 }
2911 // We add the elements directly in S from the previous loop
2912 if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2913 {
2914 for(int i = 0;i<strat->sbaEnterS;i++)
2915 {
2916 //Update: now the element is at the corect place
2917 //i+1 because on the 0 position is the sigdrop element
2918 enterT(strat->L[strat->Ll-(i)],strat);
2919 strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2920 }
2921 strat->Ll = strat->Ll - strat->sbaEnterS;
2922 strat->sbaEnterS = -1;
2923 }
2924 kTest_TS(strat);
2925 #ifdef KDEBUG
2926 //kDebugPrint(strat);
2927 #endif
2928 /* compute------------------------------------------------------- */
2929 while (strat->Ll >= 0)
2930 {
2931 if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2932 #ifdef KDEBUG
2933 if (TEST_OPT_DEBUG) messageSets(strat);
2934 #endif
2935 if (strat->Ll== 0) strat->interpt=TRUE;
2936 /*
2937 if (TEST_OPT_DEGBOUND
2938 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2939 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2940 {
2941
2942 //stops computation if
2943 // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2944 //a predefined number Kstd1_deg
2945 while ((strat->Ll >= 0)
2946 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2947 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2948 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2949 )
2950 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2951 if (strat->Ll<0) break;
2952 else strat->noClearS=TRUE;
2953 }
2954 */
2955 if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2956 {
2957 strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2958 #if F5C
2959 // 1. interreduction of the current standard basis
2960 // 2. generation of new principal syzygy rules for syzCriterion
2961 f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2962 lrmax, reduc, Q, w, hilb );
2963 #endif
2964 // initialize new syzygy rules for the next iteration step
2965 initSyzRules(strat);
2966 }
2967 /*********************************************************************
2968 * interrreduction step is done, we can go on with the next iteration
2969 * step of the signature-based algorithm
2970 ********************************************************************/
2971 /* picks the last element from the lazyset L */
2972 strat->P = strat->L[strat->Ll];
2973 strat->Ll--;
2974
2975 if(rField_is_Ring(currRing))
2976 strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2977 /* reduction of the element chosen from L */
2978 if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2979 {
2980 //#if 1
2981 #ifdef DEBUGF5
2982 PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2983 PrintS("-------------------------------------------------\n");
2984 pWrite(strat->P.sig);
2985 pWrite(pHead(strat->P.p));
2986 pWrite(pHead(strat->P.p1));
2987 pWrite(pHead(strat->P.p2));
2988 PrintS("-------------------------------------------------\n");
2989 #endif
2990 if (pNext(strat->P.p) == strat->tail)
2991 {
2992 // deletes the short spoly
2993 /*
2994 if (rField_is_Ring(currRing))
2995 pLmDelete(strat->P.p);
2996 else
2997 pLmFree(strat->P.p);
2998 */
2999 // TODO: needs some masking
3000 // TODO: masking needs to vanish once the signature
3001 // sutff is completely implemented
3002 strat->P.p = NULL;
3003 poly m1 = NULL, m2 = NULL;
3004
3005 // check that spoly creation is ok
3006 while (strat->tailRing != currRing &&
3007 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3008 {
3009 assume(m1 == NULL && m2 == NULL);
3010 // if not, change to a ring where exponents are at least
3011 // large enough
3012 if (!kStratChangeTailRing(strat))
3013 {
3014 WerrorS("OVERFLOW...");
3015 break;
3016 }
3017 }
3018 // create the real one
3019 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3020 strat->tailRing, m1, m2, strat->R);
3021
3022 }
3023 else if (strat->P.p1 == NULL)
3024 {
3025 if (strat->minim > 0)
3026 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3027 // for input polys, prepare reduction
3028 if(!rField_is_Ring(currRing))
3029 strat->P.PrepareRed(strat->use_buckets);
3030 }
3031 if (strat->P.p == NULL && strat->P.t_p == NULL)
3032 {
3033 red_result = 0;
3034 }
3035 else
3036 {
3037 //#if 1
3038 #ifdef DEBUGF5
3039 PrintS("Poly before red: ");
3040 pWrite(pHead(strat->P.p));
3041 pWrite(strat->P.sig);
3042 #endif
3043 #if SBA_PRODUCT_CRITERION
3044 if (strat->P.prod_crit)
3045 {
3046 #if SBA_PRINT_PRODUCT_CRITERION
3047 product_criterion++;
3048 #endif
3049 int pos = posInSyz(strat, strat->P.sig);
3050 enterSyz(strat->P, strat, pos);
3051 kDeleteLcm(&strat->P);
3052 red_result = 2;
3053 }
3054 else
3055 {
3056 red_result = strat->red(&strat->P,strat);
3057 }
3058 #else
3059 red_result = strat->red(&strat->P,strat);
3060 #endif
3061 }
3062 }
3063 else
3064 {
3065 /*
3066 if (strat->P.lcm != NULL)
3067 pLmFree(strat->P.lcm);
3068 */
3069 red_result = 2;
3070 }
3071 if(rField_is_Ring(currRing))
3072 {
3073 if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3074 {
3075 strat->P.p = pNeg(strat->P.p);
3076 strat->P.sig = pNeg(strat->P.sig);
3077 }
3078 strat->P.pLength = pLength(strat->P.p);
3079 if(strat->P.sig != NULL)
3080 strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3081 if(strat->P.p != NULL)
3082 strat->P.sev = pGetShortExpVector(strat->P.p);
3083 }
3084 //sigdrop case
3085 if(rField_is_Ring(currRing) && strat->sigdrop)
3086 {
3087 //First reduce it as much as one can
3088 red_result = redRing(&strat->P,strat);
3089 if(red_result == 0)
3090 {
3091 strat->sigdrop = FALSE;
3092 pDelete(&strat->P.sig);
3093 strat->P.sig = NULL;
3094 }
3095 else
3096 {
3097 strat->enterS(strat->P, 0, strat, strat->tl);
3098 if (TEST_OPT_PROT)
3099 PrintS("-");
3100 break;
3101 }
3102 }
3103 if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3104 {
3105 strat->sigdrop = TRUE;
3106 break;
3107 }
3108
3109 if (errorreported) break;
3110
3111 //#if 1
3112 #ifdef DEBUGF5
3113 if (red_result != 0)
3114 {
3115 PrintS("Poly after red: ");
3116 pWrite(pHead(strat->P.p));
3117 pWrite(strat->P.GetLmCurrRing());
3118 pWrite(strat->P.sig);
3119 printf("%d\n",red_result);
3120 }
3121 #endif
3122 if (TEST_OPT_PROT)
3123 {
3124 if(strat->P.p != NULL)
3125 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3126 &olddeg,&reduc,strat, red_result);
3127 else
3128 message((strat->honey ? strat->P.ecart : 0),
3129 &olddeg,&reduc,strat, red_result);
3130 }
3131
3132 if (strat->overflow)
3133 {
3134 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3135 }
3136 // reduction to non-zero new poly
3137 if (red_result == 1)
3138 {
3139 // get the polynomial (canonicalize bucket, make sure P.p is set)
3140 strat->P.GetP(strat->lmBin);
3141
3142 // sig-safe computations may lead to wrong FDeg computation, thus we need
3143 // to recompute it to make sure everything is alright
3144 (strat->P).FDeg = (strat->P).pFDeg();
3145 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3146 // but now, for entering S, T, we reset it
3147 // in the inhomogeneous case: FDeg == pFDeg
3148 if (strat->homog) strat->initEcart(&(strat->P));
3149
3150 /* statistic */
3151 if (TEST_OPT_PROT) PrintS("s");
3152
3153 //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3154 // in F5E we know that the last reduced element is already the
3155 // the one with highest signature
3156 int pos = strat->sl+1;
3157
3158 // reduce the tail and normalize poly
3159 // in the ring case we cannot expect LC(f) = 1,
3160 // therefore we call pCleardenom instead of pNorm
3161 #ifdef HAVE_RINGS
3162 poly beforetailred;
3163 if(rField_is_Ring(currRing))
3164 beforetailred = pCopy(strat->P.sig);
3165 #endif
3166 #if SBA_TAIL_RED
3167 if(rField_is_Ring(currRing))
3168 {
3169 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3170 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3171 }
3172 else
3173 {
3174 if (strat->sbaOrder != 2)
3175 {
3176 if (TEST_OPT_INTSTRATEGY)
3177 {
3178 strat->P.pCleardenom();
3179 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3180 {
3181 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3182 strat->P.pCleardenom();
3183 }
3184 }
3185 else
3186 {
3187 strat->P.pNorm();
3188 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3189 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3190 }
3191 }
3192 }
3193 // It may happen that we have lost the sig in redtailsba
3194 // It cannot reduce to 0 since here we are doing just tail reduction.
3195 // Best case scenerio: remains the leading term
3196 if(rField_is_Ring(currRing) && strat->sigdrop)
3197 {
3198 strat->enterS(strat->P, 0, strat, strat->tl);
3199 break;
3200 }
3201 #endif
3202 if(rField_is_Ring(currRing))
3203 {
3204 if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
3205 {
3206 strat->sigdrop = TRUE;
3207 //Reduce it as much as you can
3208 red_result = redRing(&strat->P,strat);
3209 if(red_result == 0)
3210 {
3211 //It reduced to 0, cancel the sigdrop
3212 strat->sigdrop = FALSE;
3213 p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3214 }
3215 else
3216 {
3217 strat->enterS(strat->P, 0, strat, strat->tl);
3218 break;
3219 }
3220 }
3221 p_Delete(&beforetailred,currRing);
3222 // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3223 if(strat->P.p == NULL)
3224 goto case_when_red_result_changed;
3225 }
3226 // remove sigsafe label since it is no longer valid for the next element to
3227 // be reduced
3228 if (strat->sbaOrder == 1)
3229 {
3230 for (int jj = 0; jj<strat->tl+1; jj++)
3231 {
3232 if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3233 {
3234 strat->T[jj].is_sigsafe = FALSE;
3235 }
3236 }
3237 }
3238 else
3239 {
3240 for (int jj = 0; jj<strat->tl+1; jj++)
3241 {
3242 strat->T[jj].is_sigsafe = FALSE;
3243 }
3244 }
3245 #ifdef KDEBUG
3246 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3247 #endif /* KDEBUG */
3248
3249 // min_std stuff
3250 if ((strat->P.p1==NULL) && (strat->minim>0))
3251 {
3252 if (strat->minim==1)
3253 {
3254 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3255 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3256 }
3257 else
3258 {
3259 strat->M->m[minimcnt]=strat->P.p2;
3260 strat->P.p2=NULL;
3261 }
3262 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3263 pNext(strat->M->m[minimcnt])
3264 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3265 strat->tailRing, currRing,
3266 currRing->PolyBin);
3267 minimcnt++;
3268 }
3269
3270 // enter into S, L, and T
3271 //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3272 enterT(strat->P, strat);
3273 strat->T[strat->tl].is_sigsafe = FALSE;
3274 /*
3275 printf("hier\n");
3276 pWrite(strat->P.GetLmCurrRing());
3277 pWrite(strat->P.sig);
3278 */
3279 if (rField_is_Ring(currRing))
3280 superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3281 else
3282 enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3283 if(rField_is_Ring(currRing) && strat->sigdrop)
3284 break;
3285 if(rField_is_Ring(currRing))
3286 strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3287 strat->enterS(strat->P, pos, strat, strat->tl);
3288 if(strat->sbaOrder != 1)
3289 {
3290 BOOLEAN overwrite = FALSE;
3291 for (int tk=0; tk<strat->sl+1; tk++)
3292 {
3293 if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3294 {
3295 //printf("TK %d / %d\n",tk,strat->sl);
3296 overwrite = FALSE;
3297 break;
3298 }
3299 }
3300 //printf("OVERWRITE %d\n",overwrite);
3301 if (overwrite)
3302 {
3303 int cmp = pGetComp(strat->P.sig);
3304 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3305 p_GetExpV (strat->P.p,vv,currRing);
3306 p_SetExpV (strat->P.sig, vv,currRing);
3307 p_SetComp (strat->P.sig,cmp,currRing);
3308
3309 strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3310 int i;
3311 LObject Q;
3312 for(int ps=0;ps<strat->sl+1;ps++)
3313 {
3314
3315 strat->newt = TRUE;
3316 if (strat->syzl == strat->syzmax)
3317 {
3318 pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3319 strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3320 (strat->syzmax)*sizeof(unsigned long),
3321 ((strat->syzmax)+setmaxTinc)
3322 *sizeof(unsigned long));
3323 strat->syzmax += setmaxTinc;
3324 }
3325 Q.sig = pCopy(strat->P.sig);
3326 // add LM(F->m[i]) to the signature to get a Schreyer order
3327 // without changing the underlying polynomial ring at all
3328 if (strat->sbaOrder == 0)
3329 p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3330 // since p_Add_q() destroys all input
3331 // data we need to recreate help
3332 // each time
3333 // ----------------------------------------------------------
3334 // in the Schreyer order we always know that the multiplied
3335 // module monomial strat->P.sig gives the leading monomial of
3336 // the corresponding principal syzygy
3337 // => we do not need to compute the "real" syzygy completely
3338 poly help = p_Copy(strat->sig[ps],currRing);
3339 p_ExpVectorAdd (help,strat->P.p,currRing);
3340 Q.sig = p_Add_q(Q.sig,help,currRing);
3341 //printf("%d. SYZ ",i+1);
3342 //pWrite(strat->syz[i]);
3343 Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3344 i = posInSyz(strat, Q.sig);
3345 enterSyz(Q, strat, i);
3346 }
3347 }
3348 }
3349 // deg - idx - lp/rp
3350 // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3351 if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3352 {
3353 int cmp = pGetComp(strat->P.sig);
3354 unsigned max_cmp = IDELEMS(F);
3355 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3356 p_GetExpV (strat->P.p,vv,currRing);
3357 LObject Q;
3358 int pos;
3359 int idx = __p_GetComp(strat->P.sig,currRing);
3360 //printf("++ -- adding syzygies -- ++\n");
3361 // if new element is the first one in this index
3362 if (strat->currIdx < idx)
3363 {
3364 for (int i=0; i<strat->sl; ++i)
3365 {
3366 Q.sig = p_Copy(strat->P.sig,currRing);
3367 p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3368 poly help = p_Copy(strat->sig[i],currRing);
3369 p_ExpVectorAdd(help,strat->P.p,currRing);
3370 Q.sig = p_Add_q(Q.sig,help,currRing);
3371 //pWrite(Q.sig);
3372 pos = posInSyz(strat, Q.sig);
3373 enterSyz(Q, strat, pos);
3374 }
3375 strat->currIdx = idx;
3376 }
3377 else
3378 {
3379 // if the element is not the first one in the given index we build all
3380 // possible syzygies with elements of higher index
3381 for (unsigned i=cmp+1; i<=max_cmp; ++i)
3382 {
3383 pos = -1;
3384 for (int j=0; j<strat->sl; ++j)
3385 {
3386 if (__p_GetComp(strat->sig[j],currRing) == i)
3387 {
3388 pos = j;
3389 break;
3390 }
3391 }
3392 if (pos != -1)
3393 {
3394 Q.sig = p_One(currRing);
3395 p_SetExpV(Q.sig, vv, currRing);
3396 // F->m[i-1] corresponds to index i
3397 p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3398 p_SetComp(Q.sig, i, currRing);
3399 poly help = p_Copy(strat->P.sig,currRing);
3400 p_ExpVectorAdd(help,strat->S[pos],currRing);
3401 Q.sig = p_Add_q(Q.sig,help,currRing);
3402 if (strat->sbaOrder == 0)
3403 {
3404 if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3405 {
3406 pos = posInSyz(strat, Q.sig);
3407 enterSyz(Q, strat, pos);
3408 }
3409 }
3410 else
3411 {
3412 pos = posInSyz(strat, Q.sig);
3413 enterSyz(Q, strat, pos);
3414 }
3415 }
3416 }
3417 //printf("++ -- done adding syzygies -- ++\n");
3418 }
3419 }
3420 //#if 1
3421 #if DEBUGF50
3422 printf("---------------------------\n");
3423 Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3424 PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3425 PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3426 #endif
3427 /*
3428 if (newrules)
3429 {
3430 newrules = FALSE;
3431 }
3432 */
3433 #if 0
3434 int pl=pLength(strat->P.p);
3435 if (pl==1)
3436 {
3437 //if (TEST_OPT_PROT)
3438 //PrintS("<1>");
3439 }
3440 else if (pl==2)
3441 {
3442 //if (TEST_OPT_PROT)
3443 //PrintS("<2>");
3444 }
3445 #endif
3446 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3447 // Print("[%d]",hilbeledeg);
3448 kDeleteLcm(&strat->P);
3449 if (strat->sl>srmax) srmax = strat->sl;
3450 }
3451 else
3452 {
3453 case_when_red_result_changed:
3454 // adds signature of the zero reduction to
3455 // strat->syz. This is the leading term of
3456 // syzygy and can be used in syzCriterion()
3457 // the signature is added if and only if the
3458 // pair was not detected by the rewritten criterion in strat->red = redSig
3459 if (red_result!=2)
3460 {
3461 #if SBA_PRINT_ZERO_REDUCTIONS
3462 zeroreductions++;
3463 #endif
3464 if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3465 {
3466 //Catch the case when p = 0, sig = 0
3467 }
3468 else
3469 {
3470 int pos = posInSyz(strat, strat->P.sig);
3471 enterSyz(strat->P, strat, pos);
3472 //#if 1
3473 #ifdef DEBUGF5
3474 Print("ADDING STUFF TO SYZ : ");
3475 //pWrite(strat->P.p);
3476 pWrite(strat->P.sig);
3477 #endif
3478 }
3479 }
3480 if (strat->P.p1 == NULL && strat->minim > 0)
3481 {
3482 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3483 }
3484 }
3485
3486 #ifdef KDEBUG
3487 memset(&(strat->P), 0, sizeof(strat->P));
3488 #endif /* KDEBUG */
3489 kTest_TS(strat);
3490 }
3491 #if 0
3492 if(strat->sigdrop)
3493 printf("\nSigDrop!\n");
3494 else
3495 printf("\nEnded with no SigDrop\n");
3496 #endif
3497 // Clean strat->P for the next sba call
3498 if(rField_is_Ring(currRing) && strat->sigdrop)
3499 {
3500 //This is used to know how many elements can we directly add to S in the next run
3501 if(strat->P.sig != NULL)
3502 strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3503 //else we already set it at the beggining of the loop
3504 #ifdef KDEBUG
3505 memset(&(strat->P), 0, sizeof(strat->P));
3506 #endif /* KDEBUG */
3507 }
3508 #ifdef KDEBUG
3509 if (TEST_OPT_DEBUG) messageSets(strat);
3510 #endif /* KDEBUG */
3511
3512 if (TEST_OPT_SB_1)
3513 {
3514 if(!rField_is_Ring(currRing))
3515 {
3516 int k=1;
3517 int j;
3518 while(k<=strat->sl)
3519 {
3520 j=0;
3521 loop
3522 {
3523 if (j>=k) break;
3524 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3525 j++;
3526 }
3527 k++;
3528 }
3529 }
3530 }
3531 /* complete reduction of the standard basis--------- */
3532 if (TEST_OPT_REDSB)
3533 {
3534 completeReduce(strat);
3535 if (strat->completeReduce_retry)
3536 {
3537 // completeReduce needed larger exponents, retry
3538 // to reduce with S (instead of T)
3539 // and in currRing (instead of strat->tailRing)
3540 #ifdef HAVE_TAIL_RING
3541 if(currRing->bitmask>strat->tailRing->bitmask)
3542 {
3543 strat->completeReduce_retry=FALSE;
3544 cleanT(strat);strat->tailRing=currRing;
3545 int i;
3546 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3547 completeReduce(strat);
3548 }
3549 if (strat->completeReduce_retry)
3550 #endif
3551 Werror("exponent bound is %ld",currRing->bitmask);
3552 }
3553 }
3554 else if (TEST_OPT_PROT) PrintLn();
3555
3556 #if SBA_PRINT_SIZE_SYZ
3557 // that is correct, syzl is counting one too far
3558 size_syz = strat->syzl;
3559 #endif
3560 // if (TEST_OPT_WEIGHTM)
3561 // {
3562 // pRestoreDegProcs(pFDegOld, pLDegOld);
3563 // if (ecartWeights)
3564 // {
3565 // omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3566 // ecartWeights=NULL;
3567 // }
3568 // }
3569 if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3570 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3571 #if SBA_PRINT_SIZE_G
3572 size_g_non_red = IDELEMS(strat->Shdl);
3573 #endif
3574 if(!rField_is_Ring(currRing))
3575 exitSba(strat);
3576 // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3577 #ifdef HAVE_RINGS
3578 int k;
3579 if(rField_is_Ring(currRing))
3580 {
3581 //for(k = strat->sl;k>=0;k--)
3582 // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3583 k = strat->Ll;
3584 #if 1
3585 // 1 - adds just the unused ones, 0 - adds everthing
3586 for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3587 {
3588 //printf("\nDeleted k = %i, %p\n",k,strat->L[k].p);pWrite(strat->L[k].p);pWrite(strat->L[k].p1);pWrite(strat->L[k].p2);
3589 deleteInL(strat->L,&strat->Ll,k,strat);
3590 }
3591 #endif
3592 //for(int kk = strat->sl;kk>=0;kk--)
3593 // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3594 //idPrint(strat->Shdl);
3595 //printf("\nk = %i\n",k);
3596 for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3597 {
3598 //printf("\nAdded k = %i\n",k);
3599 strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3600 //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3601 }
3602 }
3603 // Find the "sigdrop element" and put the same signature as the previous one - do we really need this?? - now i put it on the 0 position - no more comparing needed
3604 #if 0
3605 if(strat->sigdrop && rField_is_Ring(currRing))
3606 {
3607 for(k=strat->sl;k>=0;k--)
3608 {
3609 printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3610 if(strat->sig[k] == NULL)
3611 strat->sig[k] = pCopy(strat->sig[k-1]);
3612 }
3613 }
3614 #endif
3615 #endif
3616 //Never do this - you will damage S
3617 //idSkipZeroes(strat->Shdl);
3618 //idPrint(strat->Shdl);
3619
3620 if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3621 {
3622 rChangeCurrRing (currRingOld);
3623 F0 = idrMoveR (F1, sRing, currRing);
3624 strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3625 rChangeCurrRing (sRing);
3626 if(rField_is_Ring(currRing))
3627 exitSba(strat);
3628 rChangeCurrRing (currRingOld);
3629 if(strat->tailRing == sRing)
3630 strat->tailRing = currRing;
3631 rDelete (sRing);
3632 }
3633 if(rField_is_Ring(currRing) && !strat->sigdrop)
3634 id_DelDiv(strat->Shdl, currRing);
3635 if(!rField_is_Ring(currRing))
3636 id_DelDiv(strat->Shdl, currRing);
3637 idSkipZeroes(strat->Shdl);
3638 idTest(strat->Shdl);
3639
3640 #if SBA_PRINT_SIZE_G
3641 size_g = IDELEMS(strat->Shdl);
3642 #endif
3643 #ifdef DEBUGF5
3644 printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3645 int oo = 0;
3646 while (oo<IDELEMS(strat->Shdl))
3647 {
3648 printf(" %d. ",oo+1);
3649 pWrite(pHead(strat->Shdl->m[oo]));
3650 oo++;
3651 }
3652 #endif
3653 #if SBA_PRINT_ZERO_REDUCTIONS
3654 printf("----------------------------------------------------------\n");
3655 printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3656 zeroreductions = 0;
3657 #endif
3658 #if SBA_PRINT_REDUCTION_STEPS
3659 printf("----------------------------------------------------------\n");
3660 printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3661 #endif
3662 #if SBA_PRINT_OPERATIONS
3663 printf("OPERATIONS: %ld\n",sba_operations);
3664 #endif
3665 #if SBA_PRINT_REDUCTION_STEPS
3666 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3667 printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3668 #endif
3669 #if SBA_PRINT_OPERATIONS
3670 printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3671 #endif
3672 #if SBA_PRINT_REDUCTION_STEPS
3673 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3674 printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3675 sba_interreduction_steps = 0;
3676 sba_reduction_steps = 0;
3677 #endif
3678 #if SBA_PRINT_OPERATIONS
3679 printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3680 sba_interreduction_operations = 0;
3681 sba_operations = 0;
3682 #endif
3683 #if SBA_PRINT_SIZE_G
3684 printf("----------------------------------------------------------\n");
3685 printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3686 size_g = 0;
3687 size_g_non_red = 0;
3688 #endif
3689 #if SBA_PRINT_SIZE_SYZ
3690 printf("SIZE OF SYZ: %ld\n",size_syz);
3691 printf("----------------------------------------------------------\n");
3692 size_syz = 0;
3693 #endif
3694 #if SBA_PRINT_PRODUCT_CRITERION
3695 printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3696 product_criterion = 0;
3697 #endif
3698 return (strat->Shdl);
3699 }
3700
kNF2(ideal F,ideal Q,poly q,kStrategy strat,int lazyReduce)3701 poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3702 {
3703 assume(q!=NULL);
3704 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3705
3706 // lazy_reduce flags: can be combined by |
3707 //#define KSTD_NF_LAZY 1
3708 // do only a reduction of the leading term
3709 //#define KSTD_NF_NONORM 4
3710 // only global: avoid normalization, return a multiply of NF
3711 poly p;
3712
3713 //if ((idIs0(F))&&(Q==NULL))
3714 // return pCopy(q); /*F=0*/
3715 //strat->ak = idRankFreeModule(F);
3716 /*- creating temp data structures------------------- -*/
3717 BITSET save1;
3718 SI_SAVE_OPT1(save1);
3719 si_opt_1|=Sy_bit(OPT_REDTAIL);
3720 initBuchMoraCrit(strat);
3721 strat->initEcart = initEcartBBA;
3722 #ifdef HAVE_SHIFTBBA
3723 if (rIsLPRing(currRing))
3724 {
3725 strat->enterS = enterSBbaShift;
3726 }
3727 else
3728 #endif
3729 {
3730 strat->enterS = enterSBba;
3731 }
3732 #ifndef NO_BUCKETS
3733 strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3734 #endif
3735 /*- set S -*/
3736 strat->sl = -1;
3737 /*- init local data struct.---------------------------------------- -*/
3738 /*Shdl=*/initS(F,Q,strat);
3739 /*- compute------------------------------------------------------- -*/
3740 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3741 //{
3742 // for (i=strat->sl;i>=0;i--)
3743 // pNorm(strat->S[i]);
3744 //}
3745 kTest(strat);
3746 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3747 if (BVERBOSE(23)) kDebugPrint(strat);
3748 int max_ind;
3749 p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3750 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3751 {
3752 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3753 if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
3754 {
3755 p = redtailBba_Z(p,max_ind,strat);
3756 }
3757 else if (rField_is_Ring(currRing))
3758 {
3759 p = redtailBba_Ring(p,max_ind,strat);
3760 }
3761 else
3762 {
3763 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3764 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3765 }
3766 }
3767 /*- release temp data------------------------------- -*/
3768 assume(strat->L==NULL); /* strat->L unused */
3769 assume(strat->B==NULL); /* strat->B unused */
3770 omFree(strat->sevS);
3771 omFree(strat->ecartS);
3772 assume(strat->T==NULL);//omfree(strat->T);
3773 assume(strat->sevT==NULL);//omfree(strat->sevT);
3774 assume(strat->R==NULL);//omfree(strat->R);
3775 omfree(strat->S_2_R);
3776 omfree(strat->fromQ);
3777 idDelete(&strat->Shdl);
3778 SI_RESTORE_OPT1(save1);
3779 if (TEST_OPT_PROT) PrintLn();
3780 return p;
3781 }
3782
kNF2Bound(ideal F,ideal Q,poly q,int bound,kStrategy strat,int lazyReduce)3783 poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3784 {
3785 assume(q!=NULL);
3786 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3787
3788 // lazy_reduce flags: can be combined by |
3789 //#define KSTD_NF_LAZY 1
3790 // do only a reduction of the leading term
3791 //#define KSTD_NF_NONORM 4
3792 // only global: avoid normalization, return a multiply of NF
3793 poly p;
3794
3795 //if ((idIs0(F))&&(Q==NULL))
3796 // return pCopy(q); /*F=0*/
3797 //strat->ak = idRankFreeModule(F);
3798 /*- creating temp data structures------------------- -*/
3799 BITSET save1;
3800 SI_SAVE_OPT1(save1);
3801 si_opt_1|=Sy_bit(OPT_REDTAIL);
3802 initBuchMoraCrit(strat);
3803 strat->initEcart = initEcartBBA;
3804 strat->enterS = enterSBba;
3805 #ifndef NO_BUCKETS
3806 strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3807 #endif
3808 /*- set S -*/
3809 strat->sl = -1;
3810 /*- init local data struct.---------------------------------------- -*/
3811 /*Shdl=*/initS(F,Q,strat);
3812 /*- compute------------------------------------------------------- -*/
3813 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3814 //{
3815 // for (i=strat->sl;i>=0;i--)
3816 // pNorm(strat->S[i]);
3817 //}
3818 kTest(strat);
3819 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3820 if (BVERBOSE(23)) kDebugPrint(strat);
3821 int max_ind;
3822 p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3823 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3824 {
3825 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3826 if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
3827 {
3828 p = redtailBba_Z(p,max_ind,strat);
3829 }
3830 else if (rField_is_Ring(currRing))
3831 {
3832 p = redtailBba_Ring(p,max_ind,strat);
3833 }
3834 else
3835 {
3836 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3837 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3838 //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3839 }
3840 }
3841 /*- release temp data------------------------------- -*/
3842 assume(strat->L==NULL); /* strat->L unused */
3843 assume(strat->B==NULL); /* strat->B unused */
3844 omFree(strat->sevS);
3845 omFree(strat->ecartS);
3846 assume(strat->T==NULL);//omfree(strat->T);
3847 assume(strat->sevT==NULL);//omfree(strat->sevT);
3848 assume(strat->R==NULL);//omfree(strat->R);
3849 omfree(strat->S_2_R);
3850 omfree(strat->fromQ);
3851 idDelete(&strat->Shdl);
3852 SI_RESTORE_OPT1(save1);
3853 if (TEST_OPT_PROT) PrintLn();
3854 return p;
3855 }
3856
kNF2(ideal F,ideal Q,ideal q,kStrategy strat,int lazyReduce)3857 ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3858 {
3859 assume(!idIs0(q));
3860 assume(!(idIs0(F)&&(Q==NULL)));
3861 // lazy_reduce flags: can be combined by |
3862 //#define KSTD_NF_LAZY 1
3863 // do only a reduction of the leading term
3864 //#define KSTD_NF_NONORM 4
3865 // only global: avoid normalization, return a multiply of NF
3866 poly p;
3867 int i;
3868 ideal res;
3869 int max_ind;
3870
3871 //if (idIs0(q))
3872 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3873 //if ((idIs0(F))&&(Q==NULL))
3874 // return idCopy(q); /*F=0*/
3875 //strat->ak = idRankFreeModule(F);
3876 /*- creating temp data structures------------------- -*/
3877 BITSET save1;
3878 SI_SAVE_OPT1(save1);
3879 si_opt_1|=Sy_bit(OPT_REDTAIL);
3880 initBuchMoraCrit(strat);
3881 strat->initEcart = initEcartBBA;
3882 #ifdef HAVE_SHIFTBBA
3883 if (rIsLPRing(currRing))
3884 {
3885 strat->enterS = enterSBbaShift;
3886 }
3887 else
3888 #endif
3889 {
3890 strat->enterS = enterSBba;
3891 }
3892 /*- set S -*/
3893 strat->sl = -1;
3894 #ifndef NO_BUCKETS
3895 strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3896 #endif
3897 /*- init local data struct.---------------------------------------- -*/
3898 /*Shdl=*/initS(F,Q,strat);
3899 /*- compute------------------------------------------------------- -*/
3900 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3901 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3902 for (i=IDELEMS(q)-1; i>=0; i--)
3903 {
3904 if (q->m[i]!=NULL)
3905 {
3906 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3907 p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3908 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3909 {
3910 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3911 if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
3912 {
3913 p = redtailBba_Z(p,max_ind,strat);
3914 }
3915 else if (rField_is_Ring(currRing))
3916 {
3917 p = redtailBba_Ring(p,max_ind,strat);
3918 }
3919 else
3920 {
3921 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3922 }
3923 }
3924 res->m[i]=p;
3925 }
3926 //else
3927 // res->m[i]=NULL;
3928 }
3929 /*- release temp data------------------------------- -*/
3930 assume(strat->L==NULL); /* strat->L unused */
3931 assume(strat->B==NULL); /* strat->B unused */
3932 omFree(strat->sevS);
3933 omFree(strat->ecartS);
3934 assume(strat->T==NULL);//omfree(strat->T);
3935 assume(strat->sevT==NULL);//omfree(strat->sevT);
3936 assume(strat->R==NULL);//omfree(strat->R);
3937 omfree(strat->S_2_R);
3938 omfree(strat->fromQ);
3939 idDelete(&strat->Shdl);
3940 SI_RESTORE_OPT1(save1);
3941 if (TEST_OPT_PROT) PrintLn();
3942 return res;
3943 }
3944
kNF2Bound(ideal F,ideal Q,ideal q,int bound,kStrategy strat,int lazyReduce)3945 ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3946 {
3947 assume(!idIs0(q));
3948 assume(!(idIs0(F)&&(Q==NULL)));
3949 // lazy_reduce flags: can be combined by |
3950 //#define KSTD_NF_LAZY 1
3951 // do only a reduction of the leading term
3952 //#define KSTD_NF_NONORM 4
3953 // only global: avoid normalization, return a multiply of NF
3954 poly p;
3955 int i;
3956 ideal res;
3957 int max_ind;
3958
3959 //if (idIs0(q))
3960 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3961 //if ((idIs0(F))&&(Q==NULL))
3962 // return idCopy(q); /*F=0*/
3963 //strat->ak = idRankFreeModule(F);
3964 /*- creating temp data structures------------------- -*/
3965 BITSET save1;
3966 SI_SAVE_OPT1(save1);
3967 si_opt_1|=Sy_bit(OPT_REDTAIL);
3968 initBuchMoraCrit(strat);
3969 strat->initEcart = initEcartBBA;
3970 strat->enterS = enterSBba;
3971 /*- set S -*/
3972 strat->sl = -1;
3973 #ifndef NO_BUCKETS
3974 strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3975 #endif
3976 /*- init local data struct.---------------------------------------- -*/
3977 /*Shdl=*/initS(F,Q,strat);
3978 /*- compute------------------------------------------------------- -*/
3979 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3980 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3981 for (i=IDELEMS(q)-1; i>=0; i--)
3982 {
3983 if (q->m[i]!=NULL)
3984 {
3985 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3986 p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3987 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3988 {
3989 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3990 if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
3991 {
3992 p = redtailBba_Z(p,max_ind,strat);
3993 }
3994 else if (rField_is_Ring(currRing))
3995 {
3996 p = redtailBba_Ring(p,max_ind,strat);
3997 }
3998 else
3999 {
4000 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4001 }
4002 }
4003 res->m[i]=p;
4004 }
4005 //else
4006 // res->m[i]=NULL;
4007 }
4008 /*- release temp data------------------------------- -*/
4009 assume(strat->L==NULL); /* strat->L unused */
4010 assume(strat->B==NULL); /* strat->B unused */
4011 omFree(strat->sevS);
4012 omFree(strat->ecartS);
4013 assume(strat->T==NULL);//omfree(strat->T);
4014 assume(strat->sevT==NULL);//omfree(strat->sevT);
4015 assume(strat->R==NULL);//omfree(strat->R);
4016 omfree(strat->S_2_R);
4017 omfree(strat->fromQ);
4018 idDelete(&strat->Shdl);
4019 SI_RESTORE_OPT1(save1);
4020 if (TEST_OPT_PROT) PrintLn();
4021 return res;
4022 }
4023
4024 #if F5C
4025 /*********************************************************************
4026 * interrreduction step of the signature-based algorithm:
4027 * 1. all strat->S are interpreted as new critical pairs
4028 * 2. those pairs need to be completely reduced by the usual (non sig-
4029 * safe) reduction process (including tail reductions)
4030 * 3. strat->S and strat->T are completely new computed in these steps
4031 ********************************************************************/
f5c(kStrategy strat,int & olddeg,int & minimcnt,int & hilbeledeg,int & hilbcount,int & srmax,int & lrmax,int & reduc,ideal Q,intvec * w,intvec * hilb)4032 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
4033 int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
4034 intvec *w,intvec *hilb )
4035 {
4036 int Ll_old, red_result = 1;
4037 int pos = 0;
4038 hilbeledeg=1;
4039 hilbcount=0;
4040 minimcnt=0;
4041 srmax = 0; // strat->sl is 0 at this point
4042 reduc = olddeg = lrmax = 0;
4043 // we cannot use strat->T anymore
4044 //cleanT(strat);
4045 //strat->tl = -1;
4046 Ll_old = strat->Ll;
4047 while (strat->tl >= 0)
4048 {
4049 if(!strat->T[strat->tl].is_redundant)
4050 {
4051 LObject h;
4052 h.p = strat->T[strat->tl].p;
4053 h.tailRing = strat->T[strat->tl].tailRing;
4054 h.t_p = strat->T[strat->tl].t_p;
4055 if (h.p!=NULL)
4056 {
4057 if (currRing->OrdSgn==-1)
4058 {
4059 cancelunit(&h);
4060 deleteHC(&h, strat);
4061 }
4062 if (h.p!=NULL)
4063 {
4064 if (TEST_OPT_INTSTRATEGY)
4065 {
4066 h.pCleardenom(); // also does remove Content
4067 }
4068 else
4069 {
4070 h.pNorm();
4071 }
4072 strat->initEcart(&h);
4073 if(rField_is_Ring(currRing))
4074 pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4075 else
4076 pos = strat->Ll+1;
4077 h.sev = pGetShortExpVector(h.p);
4078 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4079 }
4080 }
4081 }
4082 strat->tl--;
4083 }
4084 strat->sl = -1;
4085 #if 0
4086 //#ifdef HAVE_TAIL_RING
4087 if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4088 kStratInitChangeTailRing(strat);
4089 #endif
4090 //enterpairs(pOne(),0,0,-1,strat,strat->tl);
4091 //strat->sl = -1;
4092 /* picks the last element from the lazyset L */
4093 while (strat->Ll>Ll_old)
4094 {
4095 strat->P = strat->L[strat->Ll];
4096 strat->Ll--;
4097 //#if 1
4098 #ifdef DEBUGF5
4099 PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4100 PrintS("-------------------------------------------------\n");
4101 pWrite(pHead(strat->P.p));
4102 pWrite(pHead(strat->P.p1));
4103 pWrite(pHead(strat->P.p2));
4104 printf("%d\n",strat->tl);
4105 PrintS("-------------------------------------------------\n");
4106 #endif
4107 if (pNext(strat->P.p) == strat->tail)
4108 {
4109 // deletes the short spoly
4110 if (rField_is_Ring(currRing))
4111 pLmDelete(strat->P.p);
4112 else
4113 pLmFree(strat->P.p);
4114
4115 // TODO: needs some masking
4116 // TODO: masking needs to vanish once the signature
4117 // sutff is completely implemented
4118 strat->P.p = NULL;
4119 poly m1 = NULL, m2 = NULL;
4120
4121 // check that spoly creation is ok
4122 while (strat->tailRing != currRing &&
4123 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4124 {
4125 assume(m1 == NULL && m2 == NULL);
4126 // if not, change to a ring where exponents are at least
4127 // large enough
4128 if (!kStratChangeTailRing(strat))
4129 {
4130 WerrorS("OVERFLOW...");
4131 break;
4132 }
4133 }
4134 // create the real one
4135 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4136 strat->tailRing, m1, m2, strat->R);
4137 }
4138 else if (strat->P.p1 == NULL)
4139 {
4140 if (strat->minim > 0)
4141 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4142 // for input polys, prepare reduction
4143 if(!rField_is_Ring(currRing))
4144 strat->P.PrepareRed(strat->use_buckets);
4145 }
4146
4147 if (strat->P.p == NULL && strat->P.t_p == NULL)
4148 {
4149 red_result = 0;
4150 }
4151 else
4152 {
4153 if (TEST_OPT_PROT)
4154 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4155 &olddeg,&reduc,strat, red_result);
4156
4157 #ifdef DEBUGF5
4158 PrintS("Poly before red: ");
4159 pWrite(strat->P.p);
4160 #endif
4161 /* complete reduction of the element chosen from L */
4162 red_result = strat->red2(&strat->P,strat);
4163 if (errorreported) break;
4164 }
4165
4166 if (strat->overflow)
4167 {
4168 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4169 }
4170
4171 // reduction to non-zero new poly
4172 if (red_result == 1)
4173 {
4174 // get the polynomial (canonicalize bucket, make sure P.p is set)
4175 strat->P.GetP(strat->lmBin);
4176 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4177 // but now, for entering S, T, we reset it
4178 // in the inhomogeneous case: FDeg == pFDeg
4179 if (strat->homog) strat->initEcart(&(strat->P));
4180
4181 /* statistic */
4182 if (TEST_OPT_PROT) PrintS("s");
4183 int pos;
4184 #if 1
4185 if(!rField_is_Ring(currRing))
4186 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4187 else
4188 pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4189 #else
4190 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4191 #endif
4192 // reduce the tail and normalize poly
4193 // in the ring case we cannot expect LC(f) = 1,
4194 // therefore we call pCleardenom instead of pNorm
4195 #if F5CTAILRED
4196 BOOLEAN withT = TRUE;
4197 if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
4198 {
4199 strat->P.pCleardenom();
4200 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
4201 {
4202 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4203 strat->P.pCleardenom();
4204 }
4205 }
4206 else
4207 {
4208 strat->P.pNorm();
4209 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
4210 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4211 }
4212 #endif
4213 #ifdef KDEBUG
4214 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4215 #endif /* KDEBUG */
4216
4217 // min_std stuff
4218 if ((strat->P.p1==NULL) && (strat->minim>0))
4219 {
4220 if (strat->minim==1)
4221 {
4222 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4223 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4224 }
4225 else
4226 {
4227 strat->M->m[minimcnt]=strat->P.p2;
4228 strat->P.p2=NULL;
4229 }
4230 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4231 pNext(strat->M->m[minimcnt])
4232 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4233 strat->tailRing, currRing,
4234 currRing->PolyBin);
4235 minimcnt++;
4236 }
4237
4238 // enter into S, L, and T
4239 // here we need to recompute new signatures, but those are trivial ones
4240 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4241 {
4242 enterT(strat->P, strat);
4243 // posInS only depends on the leading term
4244 strat->enterS(strat->P, pos, strat, strat->tl);
4245 //#if 1
4246 #ifdef DEBUGF5
4247 PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4248 pWrite(pHead(strat->S[strat->sl]));
4249 pWrite(strat->sig[strat->sl]);
4250 #endif
4251 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4252 }
4253 // Print("[%d]",hilbeledeg);
4254 kDeleteLcm(&strat->P);
4255 if (strat->sl>srmax) srmax = strat->sl;
4256 }
4257 else
4258 {
4259 // adds signature of the zero reduction to
4260 // strat->syz. This is the leading term of
4261 // syzygy and can be used in syzCriterion()
4262 // the signature is added if and only if the
4263 // pair was not detected by the rewritten criterion in strat->red = redSig
4264 if (strat->P.p1 == NULL && strat->minim > 0)
4265 {
4266 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4267 }
4268 }
4269
4270 #ifdef KDEBUG
4271 memset(&(strat->P), 0, sizeof(strat->P));
4272 #endif /* KDEBUG */
4273 }
4274 int cc = 0;
4275 while (cc<strat->tl+1)
4276 {
4277 strat->T[cc].sig = pOne();
4278 p_SetComp(strat->T[cc].sig,cc+1,currRing);
4279 strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4280 strat->sig[cc] = strat->T[cc].sig;
4281 strat->sevSig[cc] = strat->T[cc].sevSig;
4282 strat->T[cc].is_sigsafe = TRUE;
4283 cc++;
4284 }
4285 strat->max_lower_index = strat->tl;
4286 // set current signature index of upcoming iteration step
4287 // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4288 // the corresponding syzygy rules correctly
4289 strat->currIdx = cc+1;
4290 for (int cd=strat->Ll; cd>=0; cd--)
4291 {
4292 p_SetComp(strat->L[cd].sig,cc+1,currRing);
4293 cc++;
4294 }
4295 for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4296 strat->Shdl->m[cc] = NULL;
4297 #if 0
4298 printf("\nAfter f5c sorting\n");
4299 for(int i=0;i<=strat->sl;i++)
4300 pWrite(pHead(strat->S[i]));
4301 getchar();
4302 #endif
4303 //#if 1
4304 #if DEBUGF5
4305 PrintS("------------------- STRAT S ---------------------\n");
4306 cc = 0;
4307 while (cc<strat->tl+1)
4308 {
4309 pWrite(pHead(strat->S[cc]));
4310 pWrite(strat->sig[cc]);
4311 printf("- - - - - -\n");
4312 cc++;
4313 }
4314 PrintS("-------------------------------------------------\n");
4315 PrintS("------------------- STRAT T ---------------------\n");
4316 cc = 0;
4317 while (cc<strat->tl+1)
4318 {
4319 pWrite(pHead(strat->T[cc].p));
4320 pWrite(strat->T[cc].sig);
4321 printf("- - - - - -\n");
4322 cc++;
4323 }
4324 PrintS("-------------------------------------------------\n");
4325 PrintS("------------------- STRAT L ---------------------\n");
4326 cc = 0;
4327 while (cc<strat->Ll+1)
4328 {
4329 pWrite(pHead(strat->L[cc].p));
4330 pWrite(pHead(strat->L[cc].p1));
4331 pWrite(pHead(strat->L[cc].p2));
4332 pWrite(strat->L[cc].sig);
4333 printf("- - - - - -\n");
4334 cc++;
4335 }
4336 PrintS("-------------------------------------------------\n");
4337 printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4338 #endif
4339
4340 }
4341 #endif
4342
4343 /* shiftgb stuff */
4344 #ifdef HAVE_SHIFTBBA
bbaShift(ideal F,ideal Q,intvec * w,intvec * hilb,kStrategy strat)4345 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
4346 {
4347 int red_result = 1;
4348 int olddeg,reduc;
4349 int hilbeledeg=1,hilbcount=0,minimcnt=0;
4350 BOOLEAN withT = TRUE; // currently only T contains the shifts
4351 BITSET save;
4352 SI_SAVE_OPT1(save);
4353
4354 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4355 if(rField_is_Ring(currRing))
4356 initBuchMoraPosRing(strat);
4357 else
4358 initBuchMoraPos(strat);
4359 initHilbCrit(F,Q,&hilb,strat);
4360 initBba(strat);
4361 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4362 /*Shdl=*/initBuchMora(F, Q,strat);
4363 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4364 reduc = olddeg = 0;
4365
4366 #ifndef NO_BUCKETS
4367 if (!TEST_OPT_NOT_BUCKETS)
4368 strat->use_buckets = 1;
4369 #endif
4370 // redtailBBa against T for inhomogenous input
4371 // if (!TEST_OPT_OLDSTD)
4372 // withT = ! strat->homog;
4373
4374 // strat->posInT = posInT_pLength;
4375 kTest_TS(strat);
4376
4377 #ifdef HAVE_TAIL_RING
4378 // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4379 // kStratInitChangeTailRing(strat);
4380 strat->tailRing=currRing;
4381 #endif
4382 if (BVERBOSE(23))
4383 {
4384 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4385 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4386 kDebugPrint(strat);
4387 }
4388
4389 #ifdef KDEBUG
4390 //kDebugPrint(strat);
4391 #endif
4392 /* compute------------------------------------------------------- */
4393 while (strat->Ll >= 0)
4394 {
4395 #ifdef KDEBUG
4396 if (TEST_OPT_DEBUG) messageSets(strat);
4397 #endif
4398 if (siCntrlc)
4399 {
4400 while (strat->Ll >= 0)
4401 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4402 strat->noClearS=TRUE;
4403 }
4404 if (TEST_OPT_DEGBOUND
4405 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4406 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4407 {
4408 /*
4409 *stops computation if
4410 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4411 *a predefined number Kstd1_deg
4412 */
4413 while ((strat->Ll >= 0)
4414 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4415 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4416 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4417 )
4418 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4419 if (strat->Ll<0) break;
4420 else strat->noClearS=TRUE;
4421 }
4422 if (strat->Ll== 0) strat->interpt=TRUE;
4423 /* picks the last element from the lazyset L */
4424 strat->P = strat->L[strat->Ll];
4425 strat->Ll--;
4426
4427 if (pNext(strat->P.p) == strat->tail)
4428 {
4429 // deletes the short spoly
4430 if (rField_is_Ring(currRing))
4431 pLmDelete(strat->P.p);
4432 else
4433 pLmFree(strat->P.p);
4434 strat->P.p = NULL;
4435 poly m1 = NULL, m2 = NULL;
4436
4437 // check that spoly creation is ok
4438 while (strat->tailRing != currRing &&
4439 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4440 {
4441 assume(m1 == NULL && m2 == NULL);
4442 // if not, change to a ring where exponents are at least
4443 // large enough
4444 if (!kStratChangeTailRing(strat))
4445 {
4446 WerrorS("OVERFLOW...");
4447 break;
4448 }
4449 }
4450 // create the real one
4451 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4452 strat->tailRing, m1, m2, strat->R);
4453 }
4454 else if (strat->P.p1 == NULL)
4455 {
4456 if (strat->minim > 0)
4457 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4458 // for input polys, prepare reduction
4459 strat->P.PrepareRed(strat->use_buckets);
4460 }
4461
4462 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4463 {
4464 red_result = 0;
4465 }
4466 else
4467 {
4468 if (TEST_OPT_PROT)
4469 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4470 &olddeg,&reduc,strat, red_result);
4471
4472 /* reduction of the element chosen from L */
4473 red_result = strat->red(&strat->P,strat);
4474 if (errorreported) break;
4475 }
4476
4477 if (strat->overflow)
4478 {
4479 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4480 }
4481
4482 // reduction to non-zero new poly
4483 if (red_result == 1)
4484 {
4485 // get the polynomial (canonicalize bucket, make sure P.p is set)
4486 strat->P.GetP(strat->lmBin);
4487 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4488 // but now, for entering S, T, we reset it
4489 // in the inhomogeneous case: FDeg == pFDeg
4490 if (strat->homog) strat->initEcart(&(strat->P));
4491
4492 /* statistic */
4493 if (TEST_OPT_PROT) PrintS("s");
4494
4495 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4496
4497 // reduce the tail and normalize poly
4498 // in the ring case we cannot expect LC(f) = 1,
4499 // therefore we call pCleardenom instead of pNorm
4500 strat->redTailChange=FALSE;
4501
4502 /* if we are computing over Z we always want to try and cut down
4503 * the coefficients in the tail terms */
4504 if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing))
4505 {
4506 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4507 strat->P.pCleardenom();
4508 }
4509
4510 if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
4511 {
4512 strat->P.pCleardenom();
4513 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
4514 {
4515 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4516 strat->P.pCleardenom();
4517 if (strat->redTailChange)
4518 {
4519 strat->P.t_p=NULL;
4520 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4521 }
4522 }
4523 }
4524 else
4525 {
4526 strat->P.pNorm();
4527 if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
4528 {
4529 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4530 if (strat->redTailChange)
4531 {
4532 strat->P.t_p=NULL;
4533 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4534 }
4535 }
4536 }
4537
4538 #ifdef KDEBUG
4539 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4540 #endif /* KDEBUG */
4541
4542 // min_std stuff
4543 if ((strat->P.p1==NULL) && (strat->minim>0))
4544 {
4545 if (strat->minim==1)
4546 {
4547 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4548 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4549 }
4550 else
4551 {
4552 strat->M->m[minimcnt]=strat->P.p2;
4553 strat->P.p2=NULL;
4554 }
4555 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4556 pNext(strat->M->m[minimcnt])
4557 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4558 strat->tailRing, currRing,
4559 currRing->PolyBin);
4560 minimcnt++;
4561 }
4562
4563
4564 // enter into S, L, and T
4565 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4566 {
4567 enterT(strat->P, strat);
4568 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4569 // posInS only depends on the leading term
4570 strat->enterS(strat->P, pos, strat, strat->tl);
4571 if (!strat->rightGB)
4572 enterTShift(strat->P, strat);
4573 }
4574
4575 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4576 // Print("[%d]",hilbeledeg);
4577 kDeleteLcm(&strat->P);
4578 if (strat->s_poly!=NULL)
4579 {
4580 // the only valid entries are: strat->P.p,
4581 // strat->tailRing (read-only, keep it)
4582 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4583 if (strat->s_poly(strat))
4584 {
4585 // we are called AFTER enterS, i.e. if we change P
4586 // we have to add it also to S/T
4587 // and add pairs
4588 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4589 enterT(strat->P, strat);
4590 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4591 strat->enterS(strat->P, pos, strat, strat->tl);
4592 if (!strat->rightGB)
4593 enterTShift(strat->P,strat);
4594 }
4595 }
4596 }
4597 else if (strat->P.p1 == NULL && strat->minim > 0)
4598 {
4599 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4600 }
4601 #ifdef KDEBUG
4602 memset(&(strat->P), 0, sizeof(strat->P));
4603 #endif /* KDEBUG */
4604 kTest_TS(strat);
4605 }
4606 #ifdef KDEBUG
4607 if (TEST_OPT_DEBUG) messageSets(strat);
4608 #endif /* KDEBUG */
4609 /* shift case: look for elt's in S such that they are divisible by elt in T */
4610 if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4611 {
4612 if(!rField_is_Ring(currRing))
4613 {
4614 for (int k = 0; k <= strat->sl; ++k)
4615 {
4616 if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4617 for (int j = 0; j<=strat->tl; ++j)
4618 {
4619 // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4620 assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4621 assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4622 if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4623 {
4624 if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4625 { // check whether LM is different
4626 deleteInS(k, strat);
4627 --k;
4628 break;
4629 }
4630 }
4631 }
4632 }
4633 }
4634 }
4635 /* complete reduction of the standard basis--------- */
4636 if (TEST_OPT_REDSB)
4637 {
4638 completeReduce(strat, TRUE); //shift: withT = TRUE
4639 if (strat->completeReduce_retry)
4640 {
4641 // completeReduce needed larger exponents, retry
4642 // to reduce with S (instead of T)
4643 // and in currRing (instead of strat->tailRing)
4644 #ifdef HAVE_TAIL_RING
4645 if(currRing->bitmask>strat->tailRing->bitmask)
4646 {
4647 strat->completeReduce_retry=FALSE;
4648 cleanT(strat);strat->tailRing=currRing;
4649 int i;
4650 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4651 WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4652 completeReduce(strat);
4653 }
4654 if (strat->completeReduce_retry)
4655 #endif
4656 Werror("exponent bound is %ld",currRing->bitmask);
4657 }
4658 }
4659 else if (TEST_OPT_PROT) PrintLn();
4660
4661 /* release temp data-------------------------------- */
4662 exitBuchMora(strat);
4663 /* postprocessing for GB over ZZ --------------------*/
4664 if (!errorreported)
4665 {
4666 if(rField_is_Z(currRing))
4667 {
4668 for(int i = 0;i<=strat->sl;i++)
4669 {
4670 if(!nGreaterZero(pGetCoeff(strat->S[i])))
4671 {
4672 strat->S[i] = pNeg(strat->S[i]);
4673 }
4674 }
4675 finalReduceByMon(strat);
4676 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4677 {
4678 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4679 {
4680 strat->S[i] = pNeg(strat->Shdl->m[i]);
4681 }
4682 }
4683 }
4684 //else if (rField_is_Ring(currRing))
4685 // finalReduceByMon(strat);
4686 }
4687 // if (TEST_OPT_WEIGHTM)
4688 // {
4689 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4690 // if (ecartWeights)
4691 // {
4692 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4693 // ecartWeights=NULL;
4694 // }
4695 // }
4696 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4697 SI_RESTORE_OPT1(save);
4698 /* postprocessing for GB over Q-rings ------------------*/
4699 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4700
4701 idTest(strat->Shdl);
4702
4703 return (strat->Shdl);
4704 }
4705 #endif
4706
4707 #ifdef HAVE_SHIFTBBA
rightgb(ideal F,ideal Q)4708 ideal rightgb(ideal F, ideal Q)
4709 {
4710 assume(rIsLPRing(currRing));
4711 assume(idIsInV(F));
4712 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4713 idSkipZeroes(RS); // is this even necessary?
4714 assume(idIsInV(RS));
4715 return(RS);
4716 }
4717 #endif
4718
4719 /*2
4720 *reduces h with elements from T choosing the first possible
4721 * element in t with respect to the given pDivisibleBy
4722 */
4723 #ifdef HAVE_SHIFTBBA
redFirstShift(LObject * h,kStrategy strat)4724 int redFirstShift (LObject* h,kStrategy strat)
4725 {
4726 if (h->IsNull()) return 0;
4727
4728 int at, reddeg,d;
4729 int pass = 0;
4730 int j = 0;
4731
4732 if (! strat->homog)
4733 {
4734 d = h->GetpFDeg() + h->ecart;
4735 reddeg = strat->LazyDegree+d;
4736 }
4737 h->SetShortExpVector();
4738 loop
4739 {
4740 j = kFindDivisibleByInT(strat, h);
4741 if (j < 0)
4742 {
4743 h->SetDegStuffReturnLDeg(strat->LDegLast);
4744 return 1;
4745 }
4746
4747 if (!TEST_OPT_INTSTRATEGY)
4748 strat->T[j].pNorm();
4749 #ifdef KDEBUG
4750 if (TEST_OPT_DEBUG)
4751 {
4752 PrintS("reduce ");
4753 h->wrp();
4754 PrintS(" with ");
4755 strat->T[j].wrp();
4756 }
4757 #endif
4758 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
4759
4760 #ifdef KDEBUG
4761 if (TEST_OPT_DEBUG)
4762 {
4763 PrintS("\nto ");
4764 wrp(h->p);
4765 PrintLn();
4766 }
4767 #endif
4768 if (h->IsNull())
4769 {
4770 kDeleteLcm(h);
4771 h->Clear();
4772 return 0;
4773 }
4774 h->SetShortExpVector();
4775
4776 #if 0
4777 if ((strat->syzComp!=0) && !strat->honey)
4778 {
4779 if ((strat->syzComp>0) &&
4780 (h->Comp() > strat->syzComp))
4781 {
4782 assume(h->MinComp() > strat->syzComp);
4783 #ifdef KDEBUG
4784 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4785 #endif
4786 if (strat->homog)
4787 h->SetDegStuffReturnLDeg(strat->LDegLast);
4788 return -2;
4789 }
4790 }
4791 #endif
4792 if (!strat->homog)
4793 {
4794 if (!TEST_OPT_OLDSTD && strat->honey)
4795 {
4796 h->SetpFDeg();
4797 if (strat->T[j].ecart <= h->ecart)
4798 h->ecart = d - h->GetpFDeg();
4799 else
4800 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4801
4802 d = h->GetpFDeg() + h->ecart;
4803 }
4804 else
4805 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4806 /*- try to reduce the s-polynomial -*/
4807 pass++;
4808 /*
4809 *test whether the polynomial should go to the lazyset L
4810 *-if the degree jumps
4811 *-if the number of pre-defined reductions jumps
4812 */
4813 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4814 && ((d >= reddeg) || (pass > strat->LazyPass)))
4815 {
4816 h->SetLmCurrRing();
4817 if (strat->posInLDependsOnLength)
4818 h->SetLength(strat->length_pLength);
4819 at = strat->posInL(strat->L,strat->Ll,h,strat);
4820 if (at <= strat->Ll)
4821 {
4822 //int dummy=strat->sl;
4823 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4824 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4825 if (kFindDivisibleByInT(strat, h) < 0)
4826 return 1;
4827 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4828 #ifdef KDEBUG
4829 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4830 #endif
4831 h->Clear();
4832 return -1;
4833 }
4834 }
4835 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4836 {
4837 reddeg = d+1;
4838 Print(".%d",d);mflush();
4839 }
4840 }
4841 }
4842 }
4843 #endif
4844