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