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