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