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(p_GetCoeff(p,r), p_GetCoeff(T[j].p,r), r))
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(p_GetCoeff(p,r), p_GetCoeff(T[j].p,r), r))
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))
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))
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))
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))
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))
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))
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 
1799 
1800 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1801 {
1802  int red_result = 1;
1803  int olddeg,reduc;
1804  int hilbeledeg=1,hilbcount=0,minimcnt=0;
1805  BOOLEAN withT = FALSE;
1806  BITSET save;
1807  SI_SAVE_OPT1(save);
1808 
1809  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
1811  initBuchMoraPosRing(strat);
1812  else
1813  initBuchMoraPos(strat);
1814  initHilbCrit(F,Q,&hilb,strat);
1815  initBba(strat);
1816  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
1817  /*Shdl=*/initBuchMora(F, Q,strat);
1818  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1819  reduc = olddeg = 0;
1820 
1821 #ifndef NO_BUCKETS
1822  if (!TEST_OPT_NOT_BUCKETS)
1823  strat->use_buckets = 1;
1824 #endif
1825  // redtailBBa against T for inhomogenous input
1826  if (!TEST_OPT_OLDSTD)
1827  withT = ! strat->homog;
1828 
1829  // strat->posInT = posInT_pLength;
1830  kTest_TS(strat);
1831 
1832 #ifdef HAVE_TAIL_RING
1833  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
1834  kStratInitChangeTailRing(strat);
1835 #endif
1836  if (BVERBOSE(23))
1837  {
1838  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1839  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1840  kDebugPrint(strat);
1841  }
1842 
1843 
1844 #ifdef KDEBUG
1845  //kDebugPrint(strat);
1846 #endif
1847  /* compute------------------------------------------------------- */
1848  while (strat->Ll >= 0)
1849  {
1850  #ifdef ADIDEBUG
1851  printf("\n ------------------------NEW LOOP\n");
1852  printf("\nShdl = \n");
1853  #if 0
1854  idPrint(strat->Shdl);
1855  #else
1856  for(int ii = 0; ii<=strat->sl;ii++)
1857  p_Write(strat->S[ii],strat->tailRing);
1858  #endif
1859  printf("\n list L\n");
1860  int iii;
1861  #if 1
1862  for(iii = 0; iii<= strat->Ll; iii++)
1863  {
1864  printf("L[%i]:",iii);
1865  p_Write(strat->L[iii].p, currRing);
1866  p_Write(strat->L[iii].p1, currRing);
1867  p_Write(strat->L[iii].p2, currRing);
1868  }
1869  #else
1870  {
1871  printf("L[%i]:",strat->Ll);
1872  p_Write(strat->L[strat->Ll].p, strat->tailRing);
1873  p_Write(strat->L[strat->Ll].p1, strat->tailRing);
1874  p_Write(strat->L[strat->Ll].p2, strat->tailRing);
1875  }
1876  #endif
1877  #if 0
1878  for(iii = 0; iii<= strat->Bl; iii++)
1879  {
1880  printf("B[%i]:",iii);
1881  p_Write(strat->B[iii].p, /*strat->tailRing*/currRing);
1882  p_Write(strat->B[iii].p1, /*strat->tailRing*/currRing);
1883  p_Write(strat->B[iii].p2, strat->tailRing);
1884  }
1885  #endif
1886  //getchar();
1887  #endif
1888  #ifdef KDEBUG
1889  if (TEST_OPT_DEBUG) messageSets(strat);
1890  #endif
1891  if (strat->Ll== 0) strat->interpt=TRUE;
1892  if (TEST_OPT_DEGBOUND
1893  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1894  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
1895  {
1896  /*
1897  *stops computation if
1898  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
1899  *a predefined number Kstd1_deg
1900  */
1901  while ((strat->Ll >= 0)
1902  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1903  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1904  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
1905  )
1906  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1907  if (strat->Ll<0) break;
1908  else strat->noClearS=TRUE;
1909  }
1910  /* picks the last element from the lazyset L */
1911  strat->P = strat->L[strat->Ll];
1912  strat->Ll--;
1913 
1914  if (pNext(strat->P.p) == strat->tail)
1915  {
1916  // deletes the short spoly
1917  if (rField_is_Ring(currRing))
1918  pLmDelete(strat->P.p);
1919  else
1920  pLmFree(strat->P.p);
1921  strat->P.p = NULL;
1922  poly m1 = NULL, m2 = NULL;
1923 
1924  // check that spoly creation is ok
1925  while (strat->tailRing != currRing &&
1926  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1927  {
1928  assume(m1 == NULL && m2 == NULL);
1929  // if not, change to a ring where exponents are at least
1930  // large enough
1931  if (!kStratChangeTailRing(strat))
1932  {
1933  WerrorS("OVERFLOW...");
1934  break;
1935  }
1936  }
1937  // create the real one
1938  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
1939  strat->tailRing, m1, m2, strat->R);
1940  }
1941  else if (strat->P.p1 == NULL)
1942  {
1943  if (strat->minim > 0)
1944  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
1945  // for input polys, prepare reduction
1946  strat->P.PrepareRed(strat->use_buckets);
1947  }
1948 
1949  if (strat->P.p == NULL && strat->P.t_p == NULL)
1950  {
1951  red_result = 0;
1952  }
1953  else
1954  {
1955  if (TEST_OPT_PROT)
1956  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
1957  &olddeg,&reduc,strat, red_result);
1958 
1959  /* reduction of the element chosen from L */
1960  red_result = strat->red(&strat->P,strat);
1961  if (errorreported) break;
1962  }
1963 
1964  if (strat->overflow)
1965  {
1966  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
1967  }
1968 
1969  // reduction to non-zero new poly
1970  if (red_result == 1)
1971  {
1972  // get the polynomial (canonicalize bucket, make sure P.p is set)
1973  strat->P.GetP(strat->lmBin);
1974  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
1975  // but now, for entering S, T, we reset it
1976  // in the inhomogeneous case: FDeg == pFDeg
1977  if (strat->homog) strat->initEcart(&(strat->P));
1978 
1979  /* statistic */
1980  if (TEST_OPT_PROT) PrintS("s");
1981 
1982  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1983 
1984  // reduce the tail and normalize poly
1985  // in the ring case we cannot expect LC(f) = 1,
1986  // therefore we call pContent instead of pNorm
1988  {
1989  strat->P.pCleardenom();
1991  {
1992  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1993  strat->P.pCleardenom();
1994  }
1995  }
1996  else
1997  {
1998  strat->P.pNorm();
2000  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2001  }
2002 
2003 #ifdef KDEBUG
2004  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2005 #endif /* KDEBUG */
2006 
2007  // min_std stuff
2008  if ((strat->P.p1==NULL) && (strat->minim>0))
2009  {
2010  if (strat->minim==1)
2011  {
2012  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2013  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2014  }
2015  else
2016  {
2017  strat->M->m[minimcnt]=strat->P.p2;
2018  strat->P.p2=NULL;
2019  }
2020  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2021  pNext(strat->M->m[minimcnt])
2022  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2023  strat->tailRing, currRing,
2024  currRing->PolyBin);
2025  minimcnt++;
2026  }
2027 
2028  // enter into S, L, and T
2029  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2030  {
2031  enterT(strat->P, strat);
2032  if (rField_is_Ring(currRing))
2033  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2034  else
2035  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2036  // posInS only depends on the leading term
2037  strat->enterS(strat->P, pos, strat, strat->tl);
2038  #ifdef ADIDEBUG
2039  printf("\nThis element has been added to S:\n");pWrite(strat->P.p);pWrite(strat->P.p1);pWrite(strat->P.p2);
2040  #endif
2041 #if 0
2042  int pl=pLength(strat->P.p);
2043  if (pl==1)
2044  {
2045  //if (TEST_OPT_PROT)
2046  //PrintS("<1>");
2047  }
2048  else if (pl==2)
2049  {
2050  //if (TEST_OPT_PROT)
2051  //PrintS("<2>");
2052  }
2053 #endif
2054  }
2055  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2056 // Print("[%d]",hilbeledeg);
2057  if (strat->P.lcm!=NULL)
2058  {
2059  if (rField_is_Ring(currRing)) pLmDelete(strat->P.lcm);
2060  else pLmFree(strat->P.lcm);
2061  strat->P.lcm=NULL;
2062  }
2063  if (strat->s_poly!=NULL)
2064  {
2065  // the only valid entries are: strat->P.p,
2066  // strat->tailRing (read-only, keep it)
2067  // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2068  if (strat->s_poly(strat))
2069  {
2070  // we are called AFTER enterS, i.e. if we change P
2071  // we have to add it also to S/T
2072  // and add pairs
2073  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2074  enterT(strat->P, strat);
2075  if (rField_is_Ring(currRing))
2076  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2077  else
2078  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2079  strat->enterS(strat->P, pos, strat, strat->tl);
2080  }
2081  }
2082  }
2083  else if (strat->P.p1 == NULL && strat->minim > 0)
2084  {
2085  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2086  }
2087 
2088 #ifdef KDEBUG
2089  memset(&(strat->P), 0, sizeof(strat->P));
2090 #endif /* KDEBUG */
2091  kTest_TS(strat);
2092  }
2093 #ifdef KDEBUG
2094  if (TEST_OPT_DEBUG) messageSets(strat);
2095 #endif /* KDEBUG */
2096 
2097  if (TEST_OPT_SB_1)
2098  {
2099  if(!rField_is_Ring(currRing))
2100  {
2101  int k=1;
2102  int j;
2103  while(k<=strat->sl)
2104  {
2105  j=0;
2106  loop
2107  {
2108  if (j>=k) break;
2109  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2110  j++;
2111  }
2112  k++;
2113  }
2114  }
2115  }
2116  /* complete reduction of the standard basis--------- */
2117  if (TEST_OPT_REDSB)
2118  {
2119  completeReduce(strat);
2120 #ifdef HAVE_TAIL_RING
2121  if (strat->completeReduce_retry)
2122  {
2123  // completeReduce needed larger exponents, retry
2124  // to reduce with S (instead of T)
2125  // and in currRing (instead of strat->tailRing)
2126  cleanT(strat);strat->tailRing=currRing;
2127  int i;
2128  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2129  completeReduce(strat);
2130  }
2131 #endif
2132  }
2133  else if (TEST_OPT_PROT) PrintLn();
2134  if(nCoeff_is_Ring_Z(currRing->cf))
2135  finalReduceByMon(strat);
2137  {
2138  for(int i = 0;i<=strat->sl;i++)
2139  {
2140  if(!nGreaterZero(pGetCoeff(strat->S[i])))
2141  {
2142  strat->S[i] = pNeg(strat->S[i]);
2143  }
2144  }
2145  }
2146  /* release temp data-------------------------------- */
2147  exitBuchMora(strat);
2148 // if (TEST_OPT_WEIGHTM)
2149 // {
2150 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2151 // if (ecartWeights)
2152 // {
2153 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2154 // ecartWeights=NULL;
2155 // }
2156 // }
2157  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2158  SI_RESTORE_OPT1(save);
2159  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2160 
2161  idTest(strat->Shdl);
2162 
2163  return (strat->Shdl);
2164 }
2165 
2166 ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2167 {
2168  // ring order stuff:
2169  // in sba we have (until now) two possibilities:
2170  // 1. an incremental computation w.r.t. (C,monomial order)
2171  // 2. a (possibly non-incremental) computation w.r.t. the
2172  // induced Schreyer order.
2173  // The corresponding orders are computed in sbaRing(), depending
2174  // on the flag strat->sbaOrder
2175 #if SBA_PRINT_ZERO_REDUCTIONS
2176  long zeroreductions = 0;
2177 #endif
2178 #if SBA_PRINT_PRODUCT_CRITERION
2179  long product_criterion = 0;
2180 #endif
2181 #if SBA_PRINT_SIZE_G
2182  int size_g = 0;
2183  int size_g_non_red = 0;
2184 #endif
2185 #if SBA_PRINT_SIZE_SYZ
2186  long size_syz = 0;
2187 #endif
2188  // global variable
2189 #if SBA_PRINT_REDUCTION_STEPS
2190  sba_reduction_steps = 0;
2191  sba_interreduction_steps = 0;
2192 #endif
2193 #if SBA_PRINT_OPERATIONS
2194  sba_operations = 0;
2195  sba_interreduction_operations = 0;
2196 #endif
2197 
2198  ideal F1 = F0;
2199  ring sRing, currRingOld;
2200  currRingOld = currRing;
2201  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
2202  {
2203  sRing = sbaRing(strat);
2204  if (sRing!=currRingOld)
2205  {
2206  rChangeCurrRing (sRing);
2207  F1 = idrMoveR (F0, currRingOld, currRing);
2208  }
2209  }
2210  ideal F;
2211  // sort ideal F
2212  //Put the SigDrop element on the correct position (think of sbaEnterS)
2213  //We also sort them
2214  if(rField_is_Ring(currRing) && strat->sigdrop)
2215  {
2216  #if 1
2217  F = idInit(IDELEMS(F1),F1->rank);
2218  for (int i=0; i<IDELEMS(F1);++i)
2219  F->m[i] = F1->m[i];
2220  if(strat->sbaEnterS >= 0)
2221  {
2222  poly dummy;
2223  dummy = pCopy(F->m[0]); //the sigdrop element
2224  for(int i = 0;i<strat->sbaEnterS;i++)
2225  F->m[i] = F->m[i+1];
2226  F->m[strat->sbaEnterS] = dummy;
2227  }
2228  #else
2229  F = idInit(1,F1->rank);
2230  //printf("\nBefore the initial block sorting:\n");idPrint(F1);
2231  F->m[0] = F1->m[0];
2232  int pos;
2233  if(strat->sbaEnterS >= 0)
2234  {
2235  for(int i=1;i<=strat->sbaEnterS;i++)
2236  {
2237  pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2238  idInsertPolyOnPos(F,F1->m[i],pos);
2239  }
2240  for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2241  {
2242  pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2243  idInsertPolyOnPos(F,F1->m[i],pos);
2244  }
2245  poly dummy;
2246  dummy = pCopy(F->m[0]); //the sigdrop element
2247  for(int i = 0;i<strat->sbaEnterS;i++)
2248  F->m[i] = F->m[i+1];
2249  F->m[strat->sbaEnterS] = dummy;
2250  }
2251  else
2252  {
2253  for(int i=1;i<IDELEMS(F1);i++)
2254  {
2255  pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2256  idInsertPolyOnPos(F,F1->m[i],pos);
2257  }
2258  }
2259  #endif
2260  //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2261  }
2262  else
2263  {
2264  F = idInit(IDELEMS(F1),F1->rank);
2265  intvec *sort = idSort(F1);
2266  for (int i=0; i<sort->length();++i)
2267  F->m[i] = F1->m[(*sort)[i]-1];
2269  {
2270  // put the monomials after the sbaEnterS polynomials
2271  //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2272  int nrmon = 0;
2273  for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2274  {
2275  //pWrite(F->m[i]);
2276  if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2277  {
2278  poly mon = F->m[i];
2279  for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2280  {
2281  F->m[j] = F->m[j-1];
2282  }
2283  F->m[j] = mon;
2284  nrmon++;
2285  }
2286  //idPrint(F);
2287  }
2288  }
2289  }
2290  //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2292  strat->sigdrop = FALSE;
2293  strat->nrsyzcrit = 0;
2294  strat->nrrewcrit = 0;
2296  F = kInterRed(F,NULL);
2297 #endif
2298 #if F5DEBUG
2299  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2300  rWrite (currRing);
2301  printf("ordSgn = %d\n",currRing->OrdSgn);
2302  printf("\n");
2303 #endif
2304  int srmax,lrmax, red_result = 1;
2305  int olddeg,reduc;
2306  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2307  LObject L;
2308  BOOLEAN withT = TRUE;
2309  strat->max_lower_index = 0;
2310  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2311  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
2312  initSbaPos(strat);
2313  initHilbCrit(F,Q,&hilb,strat);
2314  initSba(F,strat);
2315  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2316  /*Shdl=*/initSbaBuchMora(F, Q,strat);
2317  idTest(strat->Shdl);
2318  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2319  srmax = strat->sl;
2320  reduc = olddeg = lrmax = 0;
2321 #ifndef NO_BUCKETS
2322  if (!TEST_OPT_NOT_BUCKETS)
2323  strat->use_buckets = 1;
2324 #endif
2325 
2326  // redtailBBa against T for inhomogenous input
2327  // if (!TEST_OPT_OLDSTD)
2328  // withT = ! strat->homog;
2329 
2330  // strat->posInT = posInT_pLength;
2331  kTest_TS(strat);
2332 
2333 #ifdef HAVE_TAIL_RING
2334  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2335  kStratInitChangeTailRing(strat);
2336 #endif
2337  if (BVERBOSE(23))
2338  {
2339  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2340  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2341  kDebugPrint(strat);
2342  }
2343  // We add the elements directly in S from the previous loop
2344  if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2345  {
2346  for(int i = 0;i<strat->sbaEnterS;i++)
2347  {
2348  //Update: now the element is at the corect place
2349  //i+1 because on the 0 position is the sigdrop element
2350  enterT(strat->L[strat->Ll-(i)],strat);
2351  strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2352  }
2353  strat->Ll = strat->Ll - strat->sbaEnterS;
2354  strat->sbaEnterS = -1;
2355  }
2356  kTest_TS(strat);
2357 #ifdef KDEBUG
2358  //kDebugPrint(strat);
2359 #endif
2360  /* compute------------------------------------------------------- */
2361  while (strat->Ll >= 0)
2362  {
2363  #ifdef ADIDEBUG
2364  printf("\n ------------------------NEW LOOP\n");
2365  printf("\nShdl = \n");
2366  #if 0
2367  idPrint(strat->Shdl);
2368  #else
2369  for(int ii = 0; ii<=strat->sl;ii++)
2370  {
2371  printf("\nS[%i]: ",ii);p_Write(strat->S[ii],strat->tailRing);
2372  printf("sig: ");pWrite(strat->sig[ii]);
2373  }
2374  #endif
2375  #if 0
2376  for(int iii = 0; iii< strat->syzl; iii++)
2377  {
2378  printf("\nsyz[%i]:\n",iii);
2379  p_Write(strat->syz[iii], currRing);
2380  }
2381  #endif
2382  #if 0
2383  for(int iii = 0; iii<= strat->tl; iii++)
2384  {
2385  printf("\nT[%i]:\n",iii);
2386  p_Write(strat->T[iii].p, currRing);
2387  }
2388  #endif
2389  printf("\n list L\n");
2390  int iii;
2391  #if 0
2392  for(iii = 0; iii<= strat->Ll; iii++)
2393  {
2394  printf("\nL[%i]:\n",iii);
2395  p_Write(strat->L[iii].p, currRing);
2396  p_Write(strat->L[iii].p1, currRing);
2397  p_Write(strat->L[iii].p2, currRing);
2398  p_Write(strat->L[iii].sig, currRing);
2399  }
2400  #else
2401  {
2402  printf("L[%i]:",strat->Ll);
2403  p_Write(strat->L[strat->Ll].p, strat->tailRing);
2404  p_Write(strat->L[strat->Ll].p1, strat->tailRing);
2405  p_Write(strat->L[strat->Ll].p2, strat->tailRing);
2406  p_Write(strat->L[strat->Ll].sig, currRing);
2407  }
2408  #endif
2409  //getchar();
2410  #endif
2411  if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2412  #ifdef KDEBUG
2413  if (TEST_OPT_DEBUG) messageSets(strat);
2414  #endif
2415  if (strat->Ll== 0) strat->interpt=TRUE;
2416  /*
2417  if (TEST_OPT_DEGBOUND
2418  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2419  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2420  {
2421 
2422  //stops computation if
2423  // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2424  //a predefined number Kstd1_deg
2425  while ((strat->Ll >= 0)
2426  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2427  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2428  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2429  )
2430  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2431  if (strat->Ll<0) break;
2432  else strat->noClearS=TRUE;
2433  }
2434  */
2435  if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2436  {
2437  strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2438 #if F5C
2439  // 1. interreduction of the current standard basis
2440  // 2. generation of new principal syzygy rules for syzCriterion
2441  f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2442  lrmax, reduc, Q, w, hilb );
2443 #endif
2444  // initialize new syzygy rules for the next iteration step
2445  initSyzRules(strat);
2446  }
2447  /*********************************************************************
2448  * interrreduction step is done, we can go on with the next iteration
2449  * step of the signature-based algorithm
2450  ********************************************************************/
2451  /* picks the last element from the lazyset L */
2452  strat->P = strat->L[strat->Ll];
2453  strat->Ll--;
2454 
2456  strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2457 
2458  #ifdef ADIDEBUG
2459  printf("\n-------------------------\nThis is the current element P\n");
2460  p_Write(strat->P.p,strat->tailRing);
2461  p_Write(strat->P.p1,strat->tailRing);
2462  p_Write(strat->P.p2,strat->tailRing);
2463  p_Write(strat->P.sig,currRing);
2464  #endif
2465  /* reduction of the element chosen from L */
2466  if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
2467  //#if 1
2468 #ifdef DEBUGF5
2469  PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2470  PrintS("-------------------------------------------------\n");
2471  pWrite(strat->P.sig);
2472  pWrite(pHead(strat->P.p));
2473  pWrite(pHead(strat->P.p1));
2474  pWrite(pHead(strat->P.p2));
2475  PrintS("-------------------------------------------------\n");
2476 #endif
2477  if (pNext(strat->P.p) == strat->tail)
2478  {
2479  // deletes the short spoly
2480  /*
2481  if (rField_is_Ring(currRing))
2482  pLmDelete(strat->P.p);
2483  else
2484  pLmFree(strat->P.p);
2485 */
2486  // TODO: needs some masking
2487  // TODO: masking needs to vanish once the signature
2488  // sutff is completely implemented
2489  strat->P.p = NULL;
2490  poly m1 = NULL, m2 = NULL;
2491 
2492  // check that spoly creation is ok
2493  while (strat->tailRing != currRing &&
2494  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2495  {
2496  assume(m1 == NULL && m2 == NULL);
2497  // if not, change to a ring where exponents are at least
2498  // large enough
2499  if (!kStratChangeTailRing(strat))
2500  {
2501  WerrorS("OVERFLOW...");
2502  break;
2503  }
2504  }
2505  // create the real one
2506  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2507  strat->tailRing, m1, m2, strat->R);
2508 
2509  }
2510  else if (strat->P.p1 == NULL)
2511  {
2512  if (strat->minim > 0)
2513  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2514  // for input polys, prepare reduction
2515  if(!rField_is_Ring(currRing))
2516  strat->P.PrepareRed(strat->use_buckets);
2517  }
2518  if (strat->P.p == NULL && strat->P.t_p == NULL)
2519  {
2520  red_result = 0;
2521  }
2522  else
2523  {
2524  //#if 1
2525 #ifdef DEBUGF5
2526  PrintS("Poly before red: ");
2527  pWrite(pHead(strat->P.p));
2528  pWrite(strat->P.sig);
2529 #endif
2530 #if SBA_PRODUCT_CRITERION
2531  if (strat->P.prod_crit) {
2532 #if SBA_PRINT_PRODUCT_CRITERION
2533  product_criterion++;
2534 #endif
2535  int pos = posInSyz(strat, strat->P.sig);
2536  enterSyz(strat->P, strat, pos);
2537  if (strat->P.lcm!=NULL)
2538  pLmFree(strat->P.lcm);
2539  red_result = 2;
2540  } else {
2541  red_result = strat->red(&strat->P,strat);
2542  }
2543 #else
2544  red_result = strat->red(&strat->P,strat);
2545 #endif
2546  }
2547  } else {
2548  /*
2549  if (strat->P.lcm != NULL)
2550  pLmFree(strat->P.lcm);
2551  */
2552  red_result = 2;
2553  }
2555  {
2556  if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
2557  {
2558  strat->P.p = pNeg(strat->P.p);
2559  strat->P.sig = pNeg(strat->P.sig);
2560  }
2561  strat->P.pLength = pLength(strat->P.p);
2562  if(strat->P.sig != NULL)
2563  strat->P.sevSig = pGetShortExpVector(strat->P.sig);
2564  if(strat->P.p != NULL)
2565  strat->P.sev = pGetShortExpVector(strat->P.p);
2566  }
2567  #ifdef ADIDEBUG
2568  printf("\nAfter reduce (redresult=%i): \n",red_result);pWrite(strat->P.p);pWrite(strat->P.sig);
2569  #endif
2570  //sigdrop case
2571  if(rField_is_Ring(currRing) && strat->sigdrop)
2572  {
2573  //First reduce it as much as one can
2574  #ifdef ADIDEBUG
2575  printf("\nSigdrop in the reduce. Trying redring\n");
2576  #endif
2577  red_result = redRing(&strat->P,strat);
2578  if(red_result == 0)
2579  {
2580  #ifdef ADIDEBUG
2581  printf("\nSigdrop cancelled since redRing reduced to 0\n");
2582  #endif
2583  strat->sigdrop = FALSE;
2584  pDelete(&strat->P.sig);
2585  strat->P.sig = NULL;
2586  }
2587  else
2588  {
2589  #ifdef ADIDEBUG
2590  printf("\nStill Sigdrop - redRing reduced to:\n");pWrite(strat->P.p);
2591  #endif
2592  strat->enterS(strat->P, 0, strat, strat->tl);
2593  if (TEST_OPT_PROT)
2594  PrintS("-");
2595  break;
2596  }
2597  }
2598  if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
2599  {
2600  #ifdef ADIDEBUG
2601  printf("\nToo many blocked reductions\n");
2602  #endif
2603  strat->sigdrop = TRUE;
2604  break;
2605  }
2606 
2607  if (errorreported) break;
2608 
2609 //#if 1
2610 #ifdef DEBUGF5
2611  if (red_result != 0) {
2612  PrintS("Poly after red: ");
2613  pWrite(pHead(strat->P.p));
2614  pWrite(strat->P.GetLmCurrRing());
2615  pWrite(strat->P.sig);
2616  printf("%d\n",red_result);
2617  }
2618 #endif
2619  if (TEST_OPT_PROT)
2620  {
2621  if(strat->P.p != NULL)
2622  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2623  &olddeg,&reduc,strat, red_result);
2624  else
2625  message((strat->honey ? strat->P.ecart : 0),
2626  &olddeg,&reduc,strat, red_result);
2627  }
2628 
2629  if (strat->overflow)
2630  {
2631  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2632  }
2633  // reduction to non-zero new poly
2634  if (red_result == 1)
2635  {
2636  // get the polynomial (canonicalize bucket, make sure P.p is set)
2637  strat->P.GetP(strat->lmBin);
2638 
2639  // sig-safe computations may lead to wrong FDeg computation, thus we need
2640  // to recompute it to make sure everything is alright
2641  (strat->P).FDeg = (strat->P).pFDeg();
2642  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2643  // but now, for entering S, T, we reset it
2644  // in the inhomogeneous case: FDeg == pFDeg
2645  if (strat->homog) strat->initEcart(&(strat->P));
2646 
2647  /* statistic */
2648  if (TEST_OPT_PROT) PrintS("s");
2649 
2650  //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2651  // in F5E we know that the last reduced element is already the
2652  // the one with highest signature
2653  int pos = strat->sl+1;
2654 
2655  // reduce the tail and normalize poly
2656  // in the ring case we cannot expect LC(f) = 1,
2657  // therefore we call pContent instead of pNorm
2658  #ifdef HAVE_RINGS
2659  poly beforetailred;
2661  beforetailred = pCopy(strat->P.sig);
2662  #endif
2663 #if SBA_TAIL_RED
2665  {
2667  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2668  }
2669  else
2670  {
2671  if (strat->sbaOrder != 2) {
2673  {
2674  strat->P.pCleardenom();
2676  {
2677  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2678  strat->P.pCleardenom();
2679  }
2680  }
2681  else
2682  {
2683  strat->P.pNorm();
2685  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2686  }
2687  }
2688  }
2689  // It may happen that we have lost the sig in redtailsba
2690  // It cannot reduce to 0 since here we are doing just tail reduction.
2691  // Best case scenerio: remains the leading term
2692  if(rField_is_Ring(currRing) && strat->sigdrop)
2693  {
2694  #ifdef ADIDEBUG
2695  printf("\n Still sigdrop after redtailSba - it reduced to \n");pWrite(strat->P.p);
2696  #endif
2697  strat->enterS(strat->P, 0, strat, strat->tl);
2698  break;
2699  }
2700 #endif
2702  {
2703  if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
2704  {
2705  #ifdef ADIDEBUG
2706  printf("\nSigDrop after TAILred\n");pWrite(beforetailred);pWrite(strat->P.sig);
2707  #endif
2708  strat->sigdrop = TRUE;
2709  //Reduce it as much as you can
2710  red_result = redRing(&strat->P,strat);
2711  if(red_result == 0)
2712  {
2713  //It reduced to 0, cancel the sigdrop
2714  #ifdef ADIDEBUG
2715  printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
2716  #endif
2717  strat->sigdrop = FALSE;
2718  p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
2719  }
2720  else
2721  {
2722  #ifdef ADIDEBUG
2723  printf("\nReduced to this via redRing.SIGDROP\n");pWrite(strat->P.p);
2724  #endif
2725  strat->enterS(strat->P, 0, strat, strat->tl);
2726  break;
2727  }
2728  }
2729  p_Delete(&beforetailred,currRing);
2730  // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
2731  if(strat->P.p == NULL)
2732  goto case_when_red_result_changed;
2733  }
2734  #ifdef ADIDEBUG
2735  printf("\nNach redTailSba: \n");
2736  p_Write(strat->P.p,strat->tailRing);p_Write(strat->P.sig,currRing);
2737  #endif
2738  // remove sigsafe label since it is no longer valid for the next element to
2739  // be reduced
2740  if (strat->sbaOrder == 1)
2741  {
2742  for (int jj = 0; jj<strat->tl+1; jj++)
2743  {
2744  if (pGetComp(strat->T[jj].sig) == strat->currIdx)
2745  {
2746  strat->T[jj].is_sigsafe = FALSE;
2747  }
2748  }
2749  }
2750  else
2751  {
2752  for (int jj = 0; jj<strat->tl+1; jj++)
2753  {
2754  strat->T[jj].is_sigsafe = FALSE;
2755  }
2756  }
2757 #ifdef KDEBUG
2758  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2759 #endif /* KDEBUG */
2760 
2761  // min_std stuff
2762  if ((strat->P.p1==NULL) && (strat->minim>0))
2763  {
2764  if (strat->minim==1)
2765  {
2766  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2767  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2768  }
2769  else
2770  {
2771  strat->M->m[minimcnt]=strat->P.p2;
2772  strat->P.p2=NULL;
2773  }
2774  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2775  pNext(strat->M->m[minimcnt])
2776  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2777  strat->tailRing, currRing,
2778  currRing->PolyBin);
2779  minimcnt++;
2780  }
2781 
2782  // enter into S, L, and T
2783  //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2784  enterT(strat->P, strat);
2785  strat->T[strat->tl].is_sigsafe = FALSE;
2786  /*
2787  printf("hier\n");
2788  pWrite(strat->P.GetLmCurrRing());
2789  pWrite(strat->P.sig);
2790  */
2791  if (rField_is_Ring(currRing))
2792  superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2793  else
2794  enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2795  #ifdef ADIDEBUG
2796  printf("\nThis element is added to S\n");
2797  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);
2798  //getchar();
2799  #endif
2800  if(rField_is_Ring(currRing) && strat->sigdrop)
2801  break;
2803  strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
2804  strat->enterS(strat->P, pos, strat, strat->tl);
2805  if(strat->sbaOrder != 1)
2806  {
2807  BOOLEAN overwrite = FALSE;
2808  for (int tk=0; tk<strat->sl+1; tk++)
2809  {
2810  if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
2811  {
2812  //printf("TK %d / %d\n",tk,strat->sl);
2813  overwrite = FALSE;
2814  break;
2815  }
2816  }
2817  //printf("OVERWRITE %d\n",overwrite);
2818  if (overwrite)
2819  {
2820  int cmp = pGetComp(strat->P.sig);
2821  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
2822  pGetExpV (strat->P.p,vv);
2823  pSetExpV (strat->P.sig, vv);
2824  pSetComp (strat->P.sig,cmp);
2825 
2826  strat->P.sevSig = pGetShortExpVector (strat->P.sig);
2827  int i;
2828  LObject Q;
2829  for(int ps=0;ps<strat->sl+1;ps++)
2830  {
2831 
2832  strat->newt = TRUE;
2833  if (strat->syzl == strat->syzmax)
2834  {
2835  pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
2836  strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
2837  (strat->syzmax)*sizeof(unsigned long),
2838  ((strat->syzmax)+setmaxTinc)
2839  *sizeof(unsigned long));
2840  strat->syzmax += setmaxTinc;
2841  }
2842  Q.sig = pCopy(strat->P.sig);
2843  // add LM(F->m[i]) to the signature to get a Schreyer order
2844  // without changing the underlying polynomial ring at all
2845  if (strat->sbaOrder == 0)
2846  p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
2847  // since p_Add_q() destroys all input
2848  // data we need to recreate help
2849  // each time
2850  // ----------------------------------------------------------
2851  // in the Schreyer order we always know that the multiplied
2852  // module monomial strat->P.sig gives the leading monomial of
2853  // the corresponding principal syzygy
2854  // => we do not need to compute the "real" syzygy completely
2855  poly help = p_Copy(strat->sig[ps],currRing);
2856  p_ExpVectorAdd (help,strat->P.p,currRing);
2857  Q.sig = p_Add_q(Q.sig,help,currRing);
2858  //printf("%d. SYZ ",i+1);
2859  //pWrite(strat->syz[i]);
2860  Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
2861  i = posInSyz(strat, Q.sig);
2862  enterSyz(Q, strat, i);
2863  }
2864  }
2865  }
2866  // deg - idx - lp/rp
2867  // => we need to add syzygies with indices > pGetComp(strat->P.sig)
2868  if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
2869  {
2870  int cmp = pGetComp(strat->P.sig);
2871  int max_cmp = IDELEMS(F);
2872  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
2873  pGetExpV (strat->P.p,vv);
2874  LObject Q;
2875  int pos;
2876  int idx = p_GetComp(strat->P.sig,currRing);
2877  //printf("++ -- adding syzygies -- ++\n");
2878  // if new element is the first one in this index
2879  if (strat->currIdx < idx) {
2880  for (int i=0; i<strat->sl; ++i) {
2881  Q.sig = p_Copy(strat->P.sig,currRing);
2882  p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
2883  poly help = p_Copy(strat->sig[i],currRing);
2884  p_ExpVectorAdd(help,strat->P.p,currRing);
2885  Q.sig = p_Add_q(Q.sig,help,currRing);
2886  //pWrite(Q.sig);
2887  pos = posInSyz(strat, Q.sig);
2888  enterSyz(Q, strat, pos);
2889  }
2890  strat->currIdx = idx;
2891  } else {
2892  // if the element is not the first one in the given index we build all
2893  // possible syzygies with elements of higher index
2894  for (int i=cmp+1; i<=max_cmp; ++i) {
2895  pos = -1;
2896  for (int j=0; j<strat->sl; ++j) {
2897  if (p_GetComp(strat->sig[j],currRing) == i) {
2898  pos = j;
2899  break;
2900  }
2901  }
2902  if (pos != -1) {
2903  Q.sig = p_One(currRing);
2904  p_SetExpV(Q.sig, vv, currRing);
2905  // F->m[i-1] corresponds to index i
2906  p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
2907  p_SetComp(Q.sig, i, currRing);
2908  poly help = p_Copy(strat->P.sig,currRing);
2909  p_ExpVectorAdd(help,strat->S[pos],currRing);
2910  Q.sig = p_Add_q(Q.sig,help,currRing);
2911  if (strat->sbaOrder == 0) {
2912  if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn) {
2913  pos = posInSyz(strat, Q.sig);
2914  enterSyz(Q, strat, pos);
2915  }
2916  } else {
2917  pos = posInSyz(strat, Q.sig);
2918  enterSyz(Q, strat, pos);
2919  }
2920  }
2921  }
2922  //printf("++ -- done adding syzygies -- ++\n");
2923  }
2924  }
2925 //#if 1
2926 #if DEBUGF50
2927  printf("---------------------------\n");
2928  Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
2929  PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
2930  PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
2931 #endif
2932  /*
2933  if (newrules)
2934  {
2935  newrules = FALSE;
2936  }
2937  */
2938 #if 0
2939  int pl=pLength(strat->P.p);
2940  if (pl==1)
2941  {
2942  //if (TEST_OPT_PROT)
2943  //PrintS("<1>");
2944  }
2945  else if (pl==2)
2946  {
2947  //if (TEST_OPT_PROT)
2948  //PrintS("<2>");
2949  }
2950 #endif
2951  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2952 // Print("[%d]",hilbeledeg);
2953  if (strat->P.lcm!=NULL)
2954 #ifdef HAVE_RINGS
2955  pLmDelete(strat->P.lcm);
2956 #else
2957  pLmFree(strat->P.lcm);
2958 #endif
2959  if (strat->sl>srmax) srmax = strat->sl;
2960  }
2961  else
2962  {
2963  case_when_red_result_changed:
2964  // adds signature of the zero reduction to
2965  // strat->syz. This is the leading term of
2966  // syzygy and can be used in syzCriterion()
2967  // the signature is added if and only if the
2968  // pair was not detected by the rewritten criterion in strat->red = redSig
2969  if (red_result!=2) {
2970 #if SBA_PRINT_ZERO_REDUCTIONS
2971  zeroreductions++;
2972 #endif
2973  if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
2974  {
2975  //Catch the case when p = 0, sig = 0
2976  }
2977  else
2978  {
2979  int pos = posInSyz(strat, strat->P.sig);
2980  enterSyz(strat->P, strat, pos);
2981  //#if 1
2982  #ifdef DEBUGF5
2983  Print("ADDING STUFF TO SYZ : ");
2984  //pWrite(strat->P.p);
2985  pWrite(strat->P.sig);
2986  #endif
2987  }
2988  }
2989  if (strat->P.p1 == NULL && strat->minim > 0)
2990  {
2991  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2992  }
2993  }
2994 
2995 #ifdef KDEBUG
2996  memset(&(strat->P), 0, sizeof(strat->P));
2997 #endif /* KDEBUG */
2998  kTest_TS(strat);
2999  }
3000  #if 0
3001  if(strat->sigdrop)
3002  printf("\nSigDrop!\n");
3003  else
3004  printf("\nEnded with no SigDrop\n");
3005  #endif
3006 // Clean strat->P for the next sba call
3007  if(rField_is_Ring(currRing) && strat->sigdrop)
3008  {
3009  //This is used to know how many elements can we directly add to S in the next run
3010  if(strat->P.sig != NULL)
3011  strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3012  //else we already set it at the beggining of the loop
3013  #ifdef KDEBUG
3014  memset(&(strat->P), 0, sizeof(strat->P));
3015  #endif /* KDEBUG */
3016  }
3017 #ifdef KDEBUG
3018  if (TEST_OPT_DEBUG) messageSets(strat);
3019 #endif /* KDEBUG */
3020 
3021  if (TEST_OPT_SB_1)
3022  {
3023  if(!rField_is_Ring(currRing))
3024  {
3025  int k=1;
3026  int j;
3027  while(k<=strat->sl)
3028  {
3029  j=0;
3030  loop
3031  {
3032  if (j>=k) break;
3033  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3034  j++;
3035  }
3036  k++;
3037  }
3038  }
3039  }
3040  /* complete reduction of the standard basis--------- */
3041  if (TEST_OPT_REDSB)
3042  {
3043  completeReduce(strat);
3044 #ifdef HAVE_TAIL_RING
3045  if (strat->completeReduce_retry)
3046  {
3047  // completeReduce needed larger exponents, retry
3048  // to reduce with S (instead of T)
3049  // and in currRing (instead of strat->tailRing)
3050  cleanT(strat);strat->tailRing=currRing;
3051  int i;
3052  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3053  completeReduce(strat);
3054  }
3055 #endif
3056  }
3057  else if (TEST_OPT_PROT) PrintLn();
3058 
3059 #if SBA_PRINT_SIZE_SYZ
3060  // that is correct, syzl is counting one too far
3061  size_syz = strat->syzl;
3062 #endif
3063 // if (TEST_OPT_WEIGHTM)
3064 // {
3065 // pRestoreDegProcs(pFDegOld, pLDegOld);
3066 // if (ecartWeights)
3067 // {
3068 // omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3069 // ecartWeights=NULL;
3070 // }
3071 // }
3072  if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3073  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3074 #if SBA_PRINT_SIZE_G
3075  size_g_non_red = IDELEMS(strat->Shdl);
3076 #endif
3077  if(!rField_is_Ring(currRing))
3078  exitSba(strat);
3079  // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3080  #ifdef HAVE_RINGS
3081  int k;
3083  {
3084  //for(k = strat->sl;k>=0;k--)
3085  // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3086  k = strat->Ll;
3087  #if 1
3088  // 1 - adds just the unused ones, 0 - adds everthing
3089  for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3090  {
3091  //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);
3092  deleteInL(strat->L,&strat->Ll,k,strat);
3093  }
3094  #endif
3095  //for(int kk = strat->sl;kk>=0;kk--)
3096  // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3097  //idPrint(strat->Shdl);
3098  //printf("\nk = %i\n",k);
3099  for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3100  {
3101  //printf("\nAdded k = %i\n",k);
3102  strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3103  //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3104  }
3105  }
3106  // 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
3107  #if 0
3108  if(strat->sigdrop && rField_is_Ring(currRing))
3109  {
3110  for(k=strat->sl;k>=0;k--)
3111  {
3112  printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3113  if(strat->sig[k] == NULL)
3114  strat->sig[k] = pCopy(strat->sig[k-1]);
3115  }
3116  }
3117  #endif
3118  #endif
3119  //Never do this - you will damage S
3120  //idSkipZeroes(strat->Shdl);
3121  //idPrint(strat->Shdl);
3122 
3123  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3124  {
3125  rChangeCurrRing (currRingOld);
3126  F0 = idrMoveR (F1, sRing, currRing);
3127  strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3128  rChangeCurrRing (sRing);
3130  exitSba(strat);
3131  rChangeCurrRing (currRingOld);
3132  if(strat->tailRing == sRing)
3133  strat->tailRing = currRing;
3134  rDelete (sRing);
3135  }
3136  if(rField_is_Ring(currRing) && !strat->sigdrop)
3137  id_DelDiv(strat->Shdl, currRing);
3138  if(!rField_is_Ring(currRing))
3139  id_DelDiv(strat->Shdl, currRing);
3140  idSkipZeroes(strat->Shdl);
3141  idTest(strat->Shdl);
3142 
3143 #if SBA_PRINT_SIZE_G
3144  size_g = IDELEMS(strat->Shdl);
3145 #endif
3146 #ifdef DEBUGF5
3147  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3148  int oo = 0;
3149  while (oo<IDELEMS(strat->Shdl))
3150  {
3151  printf(" %d. ",oo+1);
3152  pWrite(pHead(strat->Shdl->m[oo]));
3153  oo++;
3154  }
3155 #endif
3156 #if SBA_PRINT_ZERO_REDUCTIONS
3157  printf("----------------------------------------------------------\n");
3158  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3159  zeroreductions = 0;
3160 #endif
3161 #if SBA_PRINT_REDUCTION_STEPS
3162  printf("----------------------------------------------------------\n");
3163  printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3164 #endif
3165 #if SBA_PRINT_OPERATIONS
3166  printf("OPERATIONS: %ld\n",sba_operations);
3167 #endif
3168 #if SBA_PRINT_REDUCTION_STEPS
3169  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3170  printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3171 #endif
3172 #if SBA_PRINT_OPERATIONS
3173  printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3174 #endif
3175 #if SBA_PRINT_REDUCTION_STEPS
3176  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3177  printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3178  sba_interreduction_steps = 0;
3179  sba_reduction_steps = 0;
3180 #endif
3181 #if SBA_PRINT_OPERATIONS
3182  printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3183  sba_interreduction_operations = 0;
3184  sba_operations = 0;
3185 #endif
3186 #if SBA_PRINT_SIZE_G
3187  printf("----------------------------------------------------------\n");
3188  printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3189  size_g = 0;
3190  size_g_non_red = 0;
3191 #endif
3192 #if SBA_PRINT_SIZE_SYZ
3193  printf("SIZE OF SYZ: %ld\n",size_syz);
3194  printf("----------------------------------------------------------\n");
3195  size_syz = 0;
3196 #endif
3197 #if SBA_PRINT_PRODUCT_CRITERION
3198  printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3199  product_criterion = 0;
3200 #endif
3201  return (strat->Shdl);
3202 }
3203 
3204 poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3205 {
3206  assume(q!=NULL);
3207  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3208 
3209 // lazy_reduce flags: can be combined by |
3210 //#define KSTD_NF_LAZY 1
3211  // do only a reduction of the leading term
3212 //#define KSTD_NF_NONORM 4
3213  // only global: avoid normalization, return a multiply of NF
3214  poly p;
3215 
3216  //if ((idIs0(F))&&(Q==NULL))
3217  // return pCopy(q); /*F=0*/
3218  //strat->ak = idRankFreeModule(F);
3219  /*- creating temp data structures------------------- -*/
3220  BITSET save1;
3221  SI_SAVE_OPT1(save1);
3223  initBuchMoraCrit(strat);
3224  strat->initEcart = initEcartBBA;
3225  strat->enterS = enterSBba;
3226 #ifndef NO_BUCKETS
3228 #endif
3229  /*- set S -*/
3230  strat->sl = -1;
3231  /*- init local data struct.---------------------------------------- -*/
3232  /*Shdl=*/initS(F,Q,strat);
3233  /*- compute------------------------------------------------------- -*/
3234  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3235  //{
3236  // for (i=strat->sl;i>=0;i--)
3237  // pNorm(strat->S[i]);
3238  //}
3239  kTest(strat);
3240  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3241  if (BVERBOSE(23)) kDebugPrint(strat);
3242  int max_ind;
3243  p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3244  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3245  {
3246  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3247  if (rField_is_Ring(currRing))
3248  {
3249  p = redtailBba_Z(p,max_ind,strat);
3250  }
3251  else
3252  {
3254  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3255  }
3256  }
3257  /*- release temp data------------------------------- -*/
3258  assume(strat->L==NULL); /* strat->L unused */
3259  assume(strat->B==NULL); /* strat->B unused */
3260  omFree(strat->sevS);
3261  omFree(strat->ecartS);
3262  assume(strat->T==NULL);//omfree(strat->T);
3263  assume(strat->sevT==NULL);//omfree(strat->sevT);
3264  assume(strat->R==NULL);//omfree(strat->R);
3265  omfree(strat->S_2_R);
3266  omfree(strat->fromQ);
3267  idDelete(&strat->Shdl);
3268  SI_RESTORE_OPT1(save1);
3269  if (TEST_OPT_PROT) PrintLn();
3270  return p;
3271 }
3272 
3273 ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3274 {
3275  assume(!idIs0(q));
3276  assume(!(idIs0(F)&&(Q==NULL)));
3277 // lazy_reduce flags: can be combined by |
3278 //#define KSTD_NF_LAZY 1
3279  // do only a reduction of the leading term
3280 //#define KSTD_NF_NONORM 4
3281  // only global: avoid normalization, return a multiply of NF
3282  poly p;
3283  int i;
3284  ideal res;
3285  int max_ind;
3286 
3287  //if (idIs0(q))
3288  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3289  //if ((idIs0(F))&&(Q==NULL))
3290  // return idCopy(q); /*F=0*/
3291  //strat->ak = idRankFreeModule(F);
3292  /*- creating temp data structures------------------- -*/
3293  BITSET save1;
3294  SI_SAVE_OPT1(save1);
3296  initBuchMoraCrit(strat);
3297  strat->initEcart = initEcartBBA;
3298  strat->enterS = enterSBba;
3299  /*- set S -*/
3300  strat->sl = -1;
3301 #ifndef NO_BUCKETS
3303 #endif
3304  /*- init local data struct.---------------------------------------- -*/
3305  /*Shdl=*/initS(F,Q,strat);
3306  /*- compute------------------------------------------------------- -*/
3307  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3309  for (i=IDELEMS(q)-1; i>=0; i--)
3310  {
3311  if (q->m[i]!=NULL)
3312  {
3313  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3314  p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3315  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3316  {
3317  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3318  if (rField_is_Ring(currRing))
3319  {
3320  p = redtailBba_Z(p,max_ind,strat);
3321  }
3322  else
3323  {
3324  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3325  }
3326  }
3327  res->m[i]=p;
3328  }
3329  //else
3330  // res->m[i]=NULL;
3331  }
3332  /*- release temp data------------------------------- -*/
3333  assume(strat->L==NULL); /* strat->L unused */
3334  assume(strat->B==NULL); /* strat->B unused */
3335  omFree(strat->sevS);
3336  omFree(strat->ecartS);
3337  assume(strat->T==NULL);//omfree(strat->T);
3338  assume(strat->sevT==NULL);//omfree(strat->sevT);
3339  assume(strat->R==NULL);//omfree(strat->R);
3340  omfree(strat->S_2_R);
3341  omfree(strat->fromQ);
3342  idDelete(&strat->Shdl);
3343  SI_RESTORE_OPT1(save1);
3344  if (TEST_OPT_PROT) PrintLn();
3345  return res;
3346 }
3347 
3348 #if F5C
3349 /*********************************************************************
3350 * interrreduction step of the signature-based algorithm:
3351 * 1. all strat->S are interpreted as new critical pairs
3352 * 2. those pairs need to be completely reduced by the usual (non sig-
3353 * safe) reduction process (including tail reductions)
3354 * 3. strat->S and strat->T are completely new computed in these steps
3355 ********************************************************************/
3356 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
3357  int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
3358  intvec *w,intvec *hilb )
3359 {
3360  int Ll_old, red_result = 1;
3361  int pos = 0;
3362  hilbeledeg=1;
3363  hilbcount=0;
3364  minimcnt=0;
3365  srmax = 0; // strat->sl is 0 at this point
3366  reduc = olddeg = lrmax = 0;
3367  // we cannot use strat->T anymore
3368  //cleanT(strat);
3369  //strat->tl = -1;
3370  Ll_old = strat->Ll;
3371  while (strat->tl >= 0)
3372  {
3373  if(!strat->T[strat->tl].is_redundant)
3374  {
3375  LObject h;
3376  h.p = strat->T[strat->tl].p;
3377  h.tailRing = strat->T[strat->tl].tailRing;
3378  h.t_p = strat->T[strat->tl].t_p;
3379  if (h.p!=NULL)
3380  {
3381  if (currRing->OrdSgn==-1)
3382  {
3383  cancelunit(&h);
3384  deleteHC(&h, strat);
3385  }
3386  if (h.p!=NULL)
3387  {
3389  {
3390  //pContent(h.p);
3391  h.pCleardenom(); // also does a pContent
3392  }
3393  else
3394  {
3395  h.pNorm();
3396  }
3397  strat->initEcart(&h);
3399  pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
3400  else
3401  pos = strat->Ll+1;
3402  h.sev = pGetShortExpVector(h.p);
3403  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
3404  }
3405  }
3406  }
3407  strat->tl--;
3408  }
3409  strat->sl = -1;
3410 #if 0
3411 //#ifdef HAVE_TAIL_RING
3412  if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
3413  kStratInitChangeTailRing(strat);
3414 #endif
3415  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
3416  //strat->sl = -1;
3417  /* picks the last element from the lazyset L */
3418  while (strat->Ll>Ll_old)
3419  {
3420  strat->P = strat->L[strat->Ll];
3421  strat->Ll--;
3422 //#if 1
3423 #ifdef DEBUGF5
3424  PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
3425  PrintS("-------------------------------------------------\n");
3426  pWrite(pHead(strat->P.p));
3427  pWrite(pHead(strat->P.p1));
3428  pWrite(pHead(strat->P.p2));
3429  printf("%d\n",strat->tl);
3430  PrintS("-------------------------------------------------\n");
3431 #endif
3432  if (pNext(strat->P.p) == strat->tail)
3433  {
3434  // deletes the short spoly
3435  if (rField_is_Ring(currRing))
3436  pLmDelete(strat->P.p);
3437  else
3438  pLmFree(strat->P.p);
3439 
3440  // TODO: needs some masking
3441  // TODO: masking needs to vanish once the signature
3442  // sutff is completely implemented
3443  strat->P.p = NULL;
3444  poly m1 = NULL, m2 = NULL;
3445 
3446  // check that spoly creation is ok
3447  while (strat->tailRing != currRing &&
3448  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3449  {
3450  assume(m1 == NULL && m2 == NULL);
3451  // if not, change to a ring where exponents are at least
3452  // large enough
3453  if (!kStratChangeTailRing(strat))
3454  {
3455  WerrorS("OVERFLOW...");
3456  break;
3457  }
3458  }
3459  // create the real one
3460  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3461  strat->tailRing, m1, m2, strat->R);
3462  }
3463  else if (strat->P.p1 == NULL)
3464  {
3465  if (strat->minim > 0)
3466  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3467  // for input polys, prepare reduction
3468  if(!rField_is_Ring(currRing))
3469  strat->P.PrepareRed(strat->use_buckets);
3470  }
3471 
3472  if (strat->P.p == NULL && strat->P.t_p == NULL)
3473  {
3474  red_result = 0;
3475  }
3476  else
3477  {
3478  if (TEST_OPT_PROT)
3479  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3480  &olddeg,&reduc,strat, red_result);
3481 
3482 #ifdef DEBUGF5
3483  PrintS("Poly before red: ");
3484  pWrite(strat->P.p);
3485 #endif
3486  /* complete reduction of the element chosen from L */
3487  red_result = strat->red2(&strat->P,strat);
3488  if (errorreported) break;
3489  }
3490 
3491  if (strat->overflow)
3492  {
3493  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3494  }
3495 
3496  // reduction to non-zero new poly
3497  if (red_result == 1)
3498  {
3499  // get the polynomial (canonicalize bucket, make sure P.p is set)
3500  strat->P.GetP(strat->lmBin);
3501  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3502  // but now, for entering S, T, we reset it
3503  // in the inhomogeneous case: FDeg == pFDeg
3504  if (strat->homog) strat->initEcart(&(strat->P));
3505 
3506  /* statistic */
3507  if (TEST_OPT_PROT) PrintS("s");
3508  int pos;
3509  #if 1
3510  if(!rField_is_Ring(currRing))
3511  pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3512  else
3513  pos = posInSMonFirst(strat,strat->sl,strat->P.p,strat->P.ecart);
3514  #else
3515  pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3516  #endif
3517  // reduce the tail and normalize poly
3518  // in the ring case we cannot expect LC(f) = 1,
3519  // therefore we call pContent instead of pNorm
3520 #if F5CTAILRED
3521  BOOLEAN withT = TRUE;
3523  {
3524  strat->P.pCleardenom();
3526  {
3527  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3528  strat->P.pCleardenom();
3529  }
3530  }
3531  else
3532  {
3533  strat->P.pNorm();
3535  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3536  }
3537 #endif
3538 #ifdef KDEBUG
3539  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3540 #endif /* KDEBUG */
3541 
3542  // min_std stuff
3543  if ((strat->P.p1==NULL) && (strat->minim>0))
3544  {
3545  if (strat->minim==1)
3546  {
3547  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3548  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3549  }
3550  else
3551  {
3552  strat->M->m[minimcnt]=strat->P.p2;
3553  strat->P.p2=NULL;
3554  }
3555  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3556  pNext(strat->M->m[minimcnt])
3557  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3558  strat->tailRing, currRing,
3559  currRing->PolyBin);
3560  minimcnt++;
3561  }
3562 
3563  // enter into S, L, and T
3564  // here we need to recompute new signatures, but those are trivial ones
3565  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3566  {
3567  enterT(strat->P, strat);
3568  // posInS only depends on the leading term
3569  strat->enterS(strat->P, pos, strat, strat->tl);
3570 //#if 1
3571 #ifdef DEBUGF5
3572  PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
3573  pWrite(pHead(strat->S[strat->sl]));
3574  pWrite(strat->sig[strat->sl]);
3575 #endif
3576  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3577  }
3578  // Print("[%d]",hilbeledeg);
3579  if (strat->P.lcm!=NULL)
3580 #ifdef HAVE_RINGS
3581  pLmDelete(strat->P.lcm);
3582 #else
3583  pLmFree(strat->P.lcm);
3584 #endif
3585  if (strat->sl>srmax) srmax = strat->sl;
3586  }
3587  else
3588  {
3589  // adds signature of the zero reduction to
3590  // strat->syz. This is the leading term of
3591  // syzygy and can be used in syzCriterion()
3592  // the signature is added if and only if the
3593  // pair was not detected by the rewritten criterion in strat->red = redSig
3594  if (strat->P.p1 == NULL && strat->minim > 0)
3595  {
3596  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3597  }
3598  }
3599 
3600 #ifdef KDEBUG
3601  memset(&(strat->P), 0, sizeof(strat->P));
3602 #endif /* KDEBUG */
3603  }
3604  int cc = 0;
3605  while (cc<strat->tl+1)
3606  {
3607  strat->T[cc].sig = pOne();
3608  p_SetComp(strat->T[cc].sig,cc+1,currRing);
3609  strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
3610  strat->sig[cc] = strat->T[cc].sig;
3611  strat->sevSig[cc] = strat->T[cc].sevSig;
3612  strat->T[cc].is_sigsafe = TRUE;
3613  cc++;
3614  }
3615  strat->max_lower_index = strat->tl;
3616  // set current signature index of upcoming iteration step
3617  // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
3618  // the corresponding syzygy rules correctly
3619  strat->currIdx = cc+1;
3620  for (int cd=strat->Ll; cd>=0; cd--)
3621  {
3622  p_SetComp(strat->L[cd].sig,cc+1,currRing);
3623  cc++;
3624  }
3625  for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
3626  strat->Shdl->m[cc] = NULL;
3627  #if 0
3628  printf("\nAfter f5c sorting\n");
3629  for(int i=0;i<=strat->sl;i++)
3630  pWrite(pHead(strat->S[i]));
3631  getchar();
3632  #endif
3633 //#if 1
3634 #if DEBUGF5
3635  PrintS("------------------- STRAT S ---------------------\n");
3636  cc = 0;
3637  while (cc<strat->tl+1)
3638  {
3639  pWrite(pHead(strat->S[cc]));
3640  pWrite(strat->sig[cc]);
3641  printf("- - - - - -\n");
3642  cc++;
3643  }
3644  PrintS("-------------------------------------------------\n");
3645  PrintS("------------------- STRAT T ---------------------\n");
3646  cc = 0;
3647  while (cc<strat->tl+1)
3648  {
3649  pWrite(pHead(strat->T[cc].p));
3650  pWrite(strat->T[cc].sig);
3651  printf("- - - - - -\n");
3652  cc++;
3653  }
3654  PrintS("-------------------------------------------------\n");
3655  PrintS("------------------- STRAT L ---------------------\n");
3656  cc = 0;
3657  while (cc<strat->Ll+1)
3658  {
3659  pWrite(pHead(strat->L[cc].p));
3660  pWrite(pHead(strat->L[cc].p1));
3661  pWrite(pHead(strat->L[cc].p2));
3662  pWrite(strat->L[cc].sig);
3663  printf("- - - - - -\n");
3664  cc++;
3665  }
3666  PrintS("-------------------------------------------------\n");
3667  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
3668 #endif
3669 
3670 }
3671 #endif
3672 
3673 /* shiftgb stuff */
3674 #ifdef HAVE_SHIFTBBA
3675 
3676 
3677 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV)
3678 {
3679  int red_result = 1;
3680  int olddeg,reduc;
3681  int hilbeledeg=1,hilbcount=0,minimcnt=0;
3682  BOOLEAN withT = TRUE; // very important for shifts
3683 
3684  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit, NO CHANGES */
3686  initBuchMoraPosRing(strat);
3687  else
3688  initBuchMoraPos(strat); /*NO CHANGES YET: perhaps later*/
3689  initHilbCrit(F,Q,&hilb,strat); /*NO CHANGES*/
3690  initBbaShift(strat); /* DONE */
3691  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3692  /*Shdl=*/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
3693  updateSShift(strat,uptodeg,lV); /* initializes T */
3694 
3695  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
3696  reduc = olddeg = 0;
3697  strat->lV=lV;
3698 
3699 #ifndef NO_BUCKETS
3700  if (!TEST_OPT_NOT_BUCKETS)
3701  strat->use_buckets = 1;
3702 #endif
3703 
3704  // redtailBBa against T for inhomogenous input
3705  // if (!TEST_OPT_OLDSTD)
3706  // withT = ! strat->homog;
3707 
3708  // strat->posInT = posInT_pLength;
3709  kTest_TS(strat);
3710 
3711 #ifdef HAVE_TAIL_RING
3712  kStratInitChangeTailRing(strat);
3713 #endif
3714 
3715  /* compute------------------------------------------------------- */
3716  while (strat->Ll >= 0)
3717  {
3718 #ifdef KDEBUG
3719  if (TEST_OPT_DEBUG) messageSets(strat);
3720 #endif
3721  if (strat->Ll== 0) strat->interpt=TRUE;
3722  if (TEST_OPT_DEGBOUND
3723  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3724  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
3725  {
3726  /*
3727  *stops computation if
3728  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
3729  *a predefined number Kstd1_deg
3730  */
3731  while ((strat->Ll >= 0)
3732  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
3733  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3734  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
3735  )
3736  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
3737  if (strat->Ll<0) break;
3738  else strat->noClearS=TRUE;
3739  }
3740  /* picks the last element from the lazyset L */
3741  strat->P = strat->L[strat->Ll];
3742  strat->Ll--;
3743 
3744  if (pNext(strat->P.p) == strat->tail)
3745  {
3746  // deletes the short spoly
3747  pLmFree(strat->P.p);
3748  strat->P.p = NULL;
3749  poly m1 = NULL, m2 = NULL;
3750 
3751  // check that spoly creation is ok
3752  while (strat->tailRing != currRing &&
3753  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3754  {
3755  assume(m1 == NULL && m2 == NULL);
3756  // if not, change to a ring where exponents are at least
3757  // large enough
3758  kStratChangeTailRing(strat);
3759  }
3760  // create the real one
3761  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3762  strat->tailRing, m1, m2, strat->R);
3763  }
3764  else if (strat->P.p1 == NULL)
3765  {
3766  if (strat->minim > 0)
3767  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3768  // for input polys, prepare reduction
3769  strat->P.PrepareRed(strat->use_buckets);
3770  }
3771 
3772  poly qq;
3773 
3774  /* here in the nonhomog case we shrink the new spoly */
3775 
3776  if ( ! strat->homog)
3777  {
3778  strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3779  /* in the nonhomog case we have to shrink the polynomial */
3780  assume(strat->P.t_p!=NULL);
3781  qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
3782  if (qq != NULL)
3783  {
3784  /* we're here if Shrink is nonzero */
3785  // strat->P.p = NULL;
3786  // strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3787  strat->P.p = NULL; // is not set by Delete
3788  strat->P.t_p = qq;
3789  strat->P.GetP(strat->lmBin);
3790  // update sev and length
3791  strat->initEcart(&(strat->P));
3792  strat->P.sev = pGetShortExpVector(strat->P.p);
3793 // strat->P.FDeg = strat->P.pFDeg();
3794 // strat->P.length = strat->P.pLDeg();
3795 // strat->P.pLength =strat->P.GetpLength(); //pLength(strat->P.p);
3796  }
3797  else
3798  {
3799  /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
3800 #ifdef KDEBUG
3801  if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3802 #endif
3803  // strat->P.Delete(); // cause error
3804  strat->P.p = NULL;
3805  strat->P.t_p = NULL;
3806  // strat->P.p = NULL; // or delete strat->P.p ?
3807  }
3808  }
3809  /* end shrinking poly in the nonhomog case */
3810 
3811  if (strat->P.p == NULL && strat->P.t_p == NULL)
3812  {
3813  red_result = 0;
3814  }
3815  else
3816  {
3817  if (TEST_OPT_PROT)
3818  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3819  &olddeg,&reduc,strat, red_result);
3820 
3821  /* reduction of the element chosen from L */
3822  red_result = strat->red(&strat->P,strat);
3823  }
3824 
3825  // reduction to non-zero new poly
3826  if (red_result == 1)
3827  {
3828  /* statistic */
3829  if (TEST_OPT_PROT) PrintS("s");
3830 
3831  // get the polynomial (canonicalize bucket, make sure P.p is set)
3832  strat->P.GetP(strat->lmBin);
3833 
3834  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3835 
3836  // reduce the tail and normalize poly
3838  {
3839  strat->P.pCleardenom();
3841  {
3842  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3843  strat->P.pCleardenom();
3844  }
3845  }
3846  else
3847  {
3848  strat->P.pNorm();
3850  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3851  }
3852 
3853  // here we must shrink again! and optionally reduce again
3854  // or build shrink into redtailBba!
3855 
3856 #ifdef KDEBUG
3857  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3858 #endif
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  /* here in the nonhomog case we shrink the reduced poly AGAIN */
3882 
3883  if ( ! strat->homog)
3884  {
3885  strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3886  /* assume strat->P.t_p != NULL */
3887  /* in the nonhomog case we have to shrink the polynomial */
3888  assume(strat->P.t_p!=NULL); // poly qq defined above
3889  qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
3890  if (qq != NULL)
3891  {
3892  /* we're here if Shrink is nonzero */
3893  // strat->P.p = NULL;
3894  // strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3895  strat->P.p = NULL; // is not set by Delete
3896  strat->P.t_p = qq;
3897  strat->P.GetP(strat->lmBin);
3898  // update sev and length
3899  strat->initEcart(&(strat->P));
3900  strat->P.sev = pGetShortExpVector(strat->P.p);
3901  }
3902  else
3903  {
3904  /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
3905 #ifdef PDEBUG
3906  if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3907 #endif
3908  // strat->P.Delete(); // cause error
3909  strat->P.p = NULL;
3910  strat->P.t_p = NULL;
3911  // strat->P.p = NULL; // or delete strat->P.p ?
3912  goto red_shrink2zero;
3913  }
3914  }
3915  /* end shrinking poly AGAIN in the nonhomog case */
3916 
3917 
3918  // enter into S, L, and T
3919  //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3920  // enterT(strat->P, strat); // this was here before Shift stuff
3921  //enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax
3922  // the default value for atT = -1 as in bba
3923  /* strat->P.GetP(); */
3924  // because shifts are counted with .p structure // done before, but ?
3925  enterTShift(strat->P,strat,-1,uptodeg, lV);
3926  enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3927  // enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3928  // posInS only depends on the leading term
3929  strat->enterS(strat->P, pos, strat, strat->tl);
3930 
3931  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3932 // Print("[%d]",hilbeledeg);
3933  if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
3934  }
3935  else
3936  {
3937  red_shrink2zero:
3938  if (strat->P.p1 == NULL && strat->minim > 0)
3939  {
3940  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3941  }
3942  }
3943 #ifdef KDEBUG
3944  memset(&(strat->P), 0, sizeof(strat->P));
3945 #endif
3946  kTest_TS(strat);
3947  }
3948 #ifdef KDEBUG
3949  if (TEST_OPT_DEBUG) messageSets(strat);
3950 #endif
3951  /* complete reduction of the standard basis--------- */
3952  /* shift case: look for elt's in S such that they are divisible by elt in T */
3953  // if (TEST_OPT_SB_1)
3954  if (TEST_OPT_REDSB)
3955  {
3956  int k=0;
3957  int j=-1;
3958  while(k<=strat->sl)
3959  {
3960 // loop
3961 // {
3962 // if (j>=k) break;
3963 // clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3964 // j++;
3965 // }
3966  LObject Ln (strat->S[k],currRing, strat->tailRing);
3967  Ln.SetShortExpVector();
3968  j = kFindDivisibleByInT(strat, &Ln, j+1);
3969  if (j<0) { k++; j=-1;}
3970  else
3971  {
3972  if ( pLmCmp(strat->S[k],strat->T[j].p) == 0)
3973  {
3974  j = kFindDivisibleByInT(strat, &Ln, j+1);
3975  if (j<0) { k++; j=-1;}
3976  else
3977  {
3978  deleteInS(k,strat);
3979  }
3980  }
3981  else
3982  {
3983  deleteInS(k,strat);
3984  }
3985  }
3986  }
3987  }
3988 
3989  if (TEST_OPT_REDSB)
3990  { completeReduce(strat, TRUE); //shift: withT = TRUE
3991  if (strat->completeReduce_retry)
3992  {
3993  // completeReduce needed larger exponents, retry
3994  // to reduce with S (instead of T)
3995  // and in currRing (instead of strat->tailRing)
3996  cleanT(strat);strat->tailRing=currRing;
3997  int i;
3998  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3999  completeReduce(strat, TRUE);
4000  }
4001  }
4002  else if (TEST_OPT_PROT) PrintLn();
4003 
4004  /* release temp data-------------------------------- */
4005  exitBuchMora(strat);
4006 // if (TEST_OPT_WEIGHTM)
4007 // {
4008 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4009 // if (ecartWeights)
4010 // {
4011 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4012 // ecartWeights=NULL;
4013 // }
4014 // }
4015  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
4016  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
4017  return (strat->Shdl);
4018 }
4019 
4020 
4021 ideal freegb(ideal I, int uptodeg, int lVblock)
4022 {
4023  /* todo main call */
4024 
4025  /* assume: ring is prepared, ideal is copied into shifted ring */
4026  /* uptodeg and lVblock are correct - test them! */
4027 
4028  /* check whether the ideal is in V */
4029 
4030 // if (0)
4031  if (! ideal_isInV(I,lVblock) )
4032  {
4033  WerrorS("The input ideal contains incorrectly encoded elements! ");
4034  return(NULL);
4035  }
4036 
4037  // kStrategy strat = new skStrategy;
4038  /* ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV) */
4039  /* at the moment:
4040 - no quotient (check)
4041 - no *w, no *hilb
4042  */
4043  /* ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
4044  int newIdeal, intvec *vw) */
4045  ideal RS = kStdShift(I,NULL, testHomog, NULL,NULL,0,0,NULL, uptodeg, lVblock);
4046  //bbaShift(I,NULL, NULL, NULL, strat, uptodeg, lVblock);
4047  idSkipZeroes(RS);
4048  return(RS);
4049 }
4050 
4051 /*2
4052 *reduces h with elements from T choosing the first possible
4053 * element in t with respect to the given pDivisibleBy
4054 */
4056 {
4057  if (h->IsNull()) return 0;
4058 
4059  int at, reddeg,d;
4060  int pass = 0;
4061  int j = 0;
4062 
4063  if (! strat->homog)
4064  {
4065  d = h->GetpFDeg() + h->ecart;
4066  reddeg = strat->LazyDegree+d;
4067  }
4068  h->SetShortExpVector();
4069  loop
4070  {
4071  j = kFindDivisibleByInT(strat, h);
4072  if (j < 0)
4073  {
4074  h->SetDegStuffReturnLDeg(strat->LDegLast);
4075  return 1;
4076  }
4077 
4078  if (!TEST_OPT_INTSTRATEGY)
4079  strat->T[j].pNorm();
4080 #ifdef KDEBUG
4081  if (TEST_OPT_DEBUG)
4082  {
4083  PrintS("reduce ");
4084  h->wrp();
4085  PrintS(" with ");
4086  strat->T[j].wrp();
4087  }
4088 #endif
4089  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
4090  if (!h->IsNull())
4091  {
4092  poly qq=p_Shrink(h->GetTP(),strat->lV,strat->tailRing);
4093  h->p=NULL;
4094  h->t_p=qq;
4095  if (qq!=NULL) h->GetP(strat->lmBin);
4096  }
4097 
4098 #ifdef KDEBUG
4099  if (TEST_OPT_DEBUG)
4100  {
4101  PrintS(" to ");
4102  wrp(h->p);
4103  PrintLn();
4104  }
4105 #endif
4106  if (h->IsNull())
4107  {
4108  if (h->lcm!=NULL) pLmFree(h->lcm);
4109  h->Clear();
4110  return 0;
4111  }
4112  h->SetShortExpVector();
4113 
4114 #if 0
4115  if ((strat->syzComp!=0) && !strat->honey)
4116  {
4117  if ((strat->syzComp>0) &&
4118  (h->Comp() > strat->syzComp))
4119  {
4120  assume(h->MinComp() > strat->syzComp);
4121 #ifdef KDEBUG
4122  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4123 #endif
4124  if (strat->homog)
4125  h->SetDegStuffReturnLDeg(strat->LDegLast);
4126  return -2;
4127  }
4128  }
4129 #endif
4130  if (!strat->homog)
4131  {
4132  if (!TEST_OPT_OLDSTD && strat->honey)
4133  {
4134  h->SetpFDeg();
4135  if (strat->T[j].ecart <= h->ecart)
4136  h->ecart = d - h->GetpFDeg();
4137  else
4138  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4139 
4140  d = h->GetpFDeg() + h->ecart;
4141  }
4142  else
4143  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4144  /*- try to reduce the s-polynomial -*/
4145  pass++;
4146  /*
4147  *test whether the polynomial should go to the lazyset L
4148  *-if the degree jumps
4149  *-if the number of pre-defined reductions jumps
4150  */
4151  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4152  && ((d >= reddeg) || (pass > strat->LazyPass)))
4153  {
4154  h->SetLmCurrRing();
4155  if (strat->posInLDependsOnLength)
4156  h->SetLength(strat->length_pLength);
4157  at = strat->posInL(strat->L,strat->Ll,h,strat);
4158  if (at <= strat->Ll)
4159  {
4160  //int dummy=strat->sl;
4161  /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4162  //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4163  if (kFindDivisibleByInT(strat, h) < 0)
4164  return 1;
4165  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4166 #ifdef KDEBUG
4167  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4168 #endif
4169  h->Clear();
4170  return -1;
4171  }
4172  }
4173  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4174  {
4175  reddeg = d+1;
4176  Print(".%d",d);mflush();
4177  }
4178  }
4179  }
4180 }
4181 
4183 {
4184  /* setting global variables ------------------- */
4185  strat->enterS = enterSBba; /* remains as is, we change enterT! */
4186 
4187  strat->red = redFirstShift; /* no redHomog ! */
4188 
4189  if (currRing->pLexOrder && strat->honey)
4190  strat->initEcart = initEcartNormal;
4191  else
4192  strat->initEcart = initEcartBBA;
4193  if (strat->honey)
4195  else
4197 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
4198 // {
4199 // //interred machen Aenderung
4200 // pFDegOld=currRing->pFDeg;
4201 // pLDegOld=pLDeg;
4202 // //h=ggetid("ecart");
4203 // //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
4204 // //{
4205 // // ecartWeights=iv2array(IDINTVEC(h));
4206 // //}
4207 // //else
4208 // {
4209 // ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
4210 // /*uses automatic computation of the ecartWeights to set them*/
4211 // kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights,currRing);
4212 // }
4213 // pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
4214 // if (TEST_OPT_PROT)
4215 // {
4216 // for(int i=1; i<=rVar(currRing); i++)
4217 // Print(" %d",ecartWeights[i]);
4218 // PrintLn();
4219 // mflush();
4220 // }
4221 // }
4222 }
4223 #endif
unsigned long * sevSig
Definition: kutil.h:320
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:304
#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:280
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:10081
BOOLEAN honey
Definition: kutil.h:376
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:1024
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
#define Print
Definition: emacs.cc:83
int syzComp
Definition: kutil.h:352
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:1123
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9814
int syzmax
Definition: kutil.h:347
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7810
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:31
class sLObject LObject
Definition: kutil.h:60
#define nNormalize(n)
Definition: numbers.h:30
BOOLEAN length_pLength
Definition: kutil.h:386
TObject * TSet
Definition: kutil.h:61
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7851
bool sigdrop
Definition: kutil.h:358
#define TEST_OPT_PROT
Definition: options.h:98
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:10991
loop
Definition: myNF.cc:98
int Ll
Definition: kutil.h:349
#define pSetExp(p, i, v)
Definition: polys.h:42
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
Definition: kutil.cc:5291
#define FALSE
Definition: auxiliary.h:97
BOOLEAN noTailReduction
Definition: kutil.h:377
Compatiblity layer for legacy polynomial operations (over currRing)
int * S_2_R
Definition: kutil.h:340
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:9987
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:1443
#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:361
char newt
Definition: kutil.h:400
BEGIN_NAMESPACE_SINGULARXX const ring const ring tailRing
Definition: DebugPrint.h:30
BOOLEAN posInLDependsOnLength
Definition: kutil.h:388
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:290
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:1645
#define pNeg(p)
Definition: polys.h:181
void initSyzRules(kStrategy strat)
Definition: kutil.cc:8275
int & max_ind
Definition: myNF.cc:67
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4936
poly kNoether
Definition: kutil.h:326
int tl
Definition: kutil.h:348
int Bl
Definition: kutil.h:350
#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:401
#define TRUE
Definition: auxiliary.h:101
#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:40
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:336
unsigned long * sevT
Definition: kutil.h:321
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:283
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
Definition: kutil.cc:11272
#define SI_SAVE_OPT1(A)
Definition: options.h:20
void pWrite(poly p)
Definition: polys.h:291
int ak
Definition: kutil.h:351
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:10183
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:171
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:1800
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:2166
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR, int uptodeg, int lV)
Definition: kutil.cc:12491
#define BITSET
Definition: structs.h:18
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:274
#define omAlloc(size)
Definition: omAllocDecl.h:210
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9900
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:536
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1116
#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:277
int currIdx
Definition: kutil.h:313
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4962
#define pGetComp(p)
Component.
Definition: polys.h:37
static int pLength(poly a)
Definition: p_polys.h:189
int minim
Definition: kutil.h:356
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:178
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4055
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:402
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11245
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:100
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9364
#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:11952
poly res
Definition: myNF.cc:322
BOOLEAN interpt
Definition: kutil.h:370
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
void(* initEcart)(TObject *L)
Definition: kutil.h:276
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:364
int posInSMonFirst(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5213
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7928
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3204
void enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV)
Definition: kutil.cc:12596
int lV
Definition: kutil.h:367
#define idPrint(id)
Definition: ideals.h:48
int nrsyzcrit
Definition: kutil.h:359
BOOLEAN fromT
Definition: kutil.h:378
int nrrewcrit
Definition: kutil.h:360
int posInLF5CRing(const LSet set, int start, const int length, LObject *p, const kStrategy strat)
Definition: kutil.cc:6477
const ring r
Definition: syzextra.cc:208
#define KSTD_NF_LAZY
Definition: kstd1.h:17
BOOLEAN homog
Definition: kutil.h:371
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:1313
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:314
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:9645
#define TEST_OPT_OLDSTD
Definition: options.h:117
#define assume(x)
Definition: mod2.h:403
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:404
intset fromQ
Definition: kutil.h:317
#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:7863
#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:282
#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:3436
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:637
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:11146
LObject P
Definition: kutil.h:298
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9663
ideal M
Definition: kutil.h:301
unsigned sbaOrder
Definition: kutil.h:312
static int si_max(const int a, const int b)
Definition: auxiliary.h:123
void exitSba(kStrategy strat)
Definition: kutil.cc:10256
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
poly tail
Definition: kutil.h:332
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:4909
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:3356
#define pOne()
Definition: polys.h:298
TObject ** R
Definition: kutil.h:338
void rWrite(ring r, BOOLEAN details)
Definition: ring.cc:236
#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:302
#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:4021
void initBuchMoraShift(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:11980
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:10697
#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:4182
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:4589
intset ecartS
Definition: kutil.h:305
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:296
LSet L
Definition: kutil.h:323
BOOLEAN LDegLast
Definition: kutil.h:384
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:10926
#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:3556
LSet B
Definition: kutil.h:324
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4899
int Lmax
Definition: kutil.h:349
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:4209
int posInSyz(const kStrategy strat, poly sig)
Definition: kutil.cc:6361
ring tailRing
Definition: kutil.h:341
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:346
#define TEST_OPT_SB_1
Definition: options.h:113
CFList tmp1
Definition: facFqBivar.cc:70
int blockred
Definition: kutil.h:363
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9727
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:5112
#define pDelete(p_ptr)
Definition: polys.h:169
char overflow
Definition: kutil.h:403
unsigned long * sevS
Definition: kutil.h:318
#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:3677
#define nCopy(n)
Definition: numbers.h:15
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10508
#define pNext(p)
Definition: monomials.h:43
unsigned long * sevSyz
Definition: kutil.h:319
#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:10296
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:1141
#define p_GetCoeff(p, r)
Definition: monomials.h:57
int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kstd2.cc:82
polyset syz
Definition: kutil.h:303
int sl
Definition: kutil.h:346
void sort(CFArray &A, int l=0)
quick sort A
TSet T
Definition: kutil.h:322
omBin lmBin
Definition: kutil.h:342
long ind2(long arg)
Definition: kutil.cc:4197
BOOLEAN use_buckets
Definition: kutil.h:382
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:293
kBucketDestroy & P
Definition: myNF.cc:191
int LazyPass
Definition: kutil.h:351
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:11080
ideal Shdl
Definition: kutil.h:299
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:88
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
#define pSize(p)
Definition: polys.h:301
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:1297
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020
char redTailChange
Definition: kutil.h:398
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10063
int syzl
Definition: kutil.h:347
int LazyDegree
Definition: kutil.h:351
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11692
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:9561
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:9124
#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:376
#define idTest(id)
Definition: ideals.h:49