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