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