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 
11 
12 
13 
14 #include <kernel/mod2.h>
15 
16 #ifndef SING_NDEBUG
17 # define MYTEST 0
18 #else /* ifndef SING_NDEBUG */
19 # define MYTEST 0
20 #endif /* ifndef SING_NDEBUG */
21 
22 #define ADIDEBUG 0
23 #define ADIDEBUG_COUNT 0
24 
25 #if MYTEST
26 # ifdef HAVE_TAIL_RING
27 # undef HAVE_TAIL_RING
28 # endif // ifdef HAVE_TAIL_RING
29 #endif
30 
31 // define if no buckets should be used
32 // #define NO_BUCKETS
33 
34 #ifdef HAVE_PLURAL
35 #define PLURAL_INTERNAL_DECLARATIONS 1
36 #endif
37 
38 /***********************************************
39  * SBA stuff -- start
40 ***********************************************/
41 #define DEBUGF50 0
42 #define DEBUGF51 0
43 
44 #ifdef DEBUGF5
45 #undef DEBUGF5
46 //#define DEBUGF5 1
47 #endif
48 
49 #define F5C 1
50 #if F5C
51  #define F5CTAILRED 1
52 #endif
53 
54 #define SBA_INTERRED_START 0
55 #define SBA_TAIL_RED 1
56 #define SBA_PRODUCT_CRITERION 0
57 #define SBA_PRINT_ZERO_REDUCTIONS 0
58 #define SBA_PRINT_REDUCTION_STEPS 0
59 #define SBA_PRINT_OPERATIONS 0
60 #define SBA_PRINT_SIZE_G 0
61 #define SBA_PRINT_SIZE_SYZ 0
62 #define SBA_PRINT_PRODUCT_CRITERION 0
63 
64 // counts sba's reduction steps
65 #if SBA_PRINT_REDUCTION_STEPS
66 long sba_reduction_steps;
67 long sba_interreduction_steps;
68 #endif
69 #if SBA_PRINT_OPERATIONS
70 long sba_operations;
71 long sba_interreduction_operations;
72 #endif
73 
74 /***********************************************
75  * SBA stuff -- done
76 ***********************************************/
77 
78 #include <kernel/GBEngine/kutil.h>
79 #include <misc/options.h>
80 #include <omalloc/omalloc.h>
81 #include <kernel/polys.h>
82 #include <kernel/ideals.h>
83 #include <kernel/GBEngine/kstd1.h>
84 #include <kernel/GBEngine/khstd.h>
85 #include <polys/kbuckets.h>
86 #include <polys/prCopy.h>
87 //#include "cntrlc.h"
88 #include <polys/weight.h>
89 #include <misc/intvec.h>
90 #ifdef HAVE_PLURAL
91 #include <polys/nc/nc.h>
92 #endif
93 // #include "timer.h"
94 
95 /* shiftgb stuff */
97 
98  int (*test_PosInT)(const TSet T,const int tl,LObject &h);
99  int (*test_PosInL)(const LSet set, const int length,
100  LObject* L,const kStrategy strat);
101 
102 // return -1 if no divisor is found
103 // number of first divisor, otherwise
104 int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
105 {
106  unsigned long not_sev = ~L->sev;
107  int j = start;
108 
109  const TSet T=strat->T;
110  const unsigned long* sevT=strat->sevT;
111  if (L->p!=NULL)
112  {
113  const ring r=currRing;
114  const poly p=L->p;
115 
116  pAssume(~not_sev == p_GetShortExpVector(p, r));
117 
118  loop
119  {
120  if (j > strat->tl) return -1;
121 #if defined(PDEBUG) || defined(PDIV_DEBUG)
122  if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
123  {
124 #ifdef HAVE_RINGS
125  if(rField_is_Ring(r))
126  {if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r))
127  return j;}
128  else {
129  return j;
130  }
131 #else
132  return j;
133 #endif
134 
135  }
136 #else
137  if (!(sevT[j] & not_sev) &&
138  p_LmDivisibleBy(T[j].p, p, r))
139  {
140 #ifdef HAVE_RINGS
141  if(rField_is_Ring(r))
142  {if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r))
143  return j;}
144  else {
145  return j;
146  }
147 #else
148  return j;
149 #endif
150 
151  }
152 #endif
153  j++;
154  }
155  }
156  else
157  {
158  const poly p=L->t_p;
159  const ring r=strat->tailRing;
160  loop
161  {
162  if (j > strat->tl) return -1;
163 #if defined(PDEBUG) || defined(PDIV_DEBUG)
164  if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
165  p, not_sev, r))
166  {
167 #ifdef HAVE_RINGS
168  if(rField_is_Ring(r))
169  {if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r))
170  return j;}
171  else {
172  return j;
173  }
174 #else
175  return j;
176 #endif
177 
178  }
179 #else
180  if (!(sevT[j] & not_sev) &&
181  p_LmDivisibleBy(T[j].t_p, p, r))
182  {
183 #ifdef HAVE_RINGS
184  if(rField_is_Ring(r))
185  {if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r))
186  return j;}
187  else {
188  return j;
189  }
190 #else
191  return j;
192 #endif
193 
194  }
195 #endif
196  j++;
197  }
198  }
199 }
200 
201 // same as above, only with set S
203 {
204  unsigned long not_sev = ~L->sev;
205  poly p = L->GetLmCurrRing();
206  int j = 0;
207 
208  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
209 #if 1
210  int ende;
211  if ((strat->ak>0) || currRing->pLexOrder) ende=strat->sl;
212  else ende=posInS(strat,*max_ind,p,0)+1;
213  if (ende>(*max_ind)) ende=(*max_ind);
214 #else
215  int ende=strat->sl;
216 #endif
217  (*max_ind)=ende;
218  loop
219  {
220  if (j > ende) return -1;
221 #if defined(PDEBUG) || defined(PDIV_DEBUG)
222  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
223  p, not_sev, currRing))
224  {
225 #ifdef HAVE_RINGS
227  {if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
228  return j;}
229  else
230 #endif
231  return j;
232  }
233 #else
234  if ( !(strat->sevS[j] & not_sev) &&
235  p_LmDivisibleBy(strat->S[j], p, currRing))
236  {
237 #ifdef HAVE_RINGS
239  {if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
240  return j;}
241  else
242 #endif
243  return j;
244  }
245 #endif
246  j++;
247  }
248 }
249 
251 {
252  unsigned long not_sev = ~L->sev;
253  poly p = L->GetLmCurrRing();
254  int j = start;
255 
256  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
257 #if 1
258  int ende=max_ind;
259 #else
260  int ende=strat->sl;
261 #endif
262  loop
263  {
264  if (j > ende) return -1;
265 #if defined(PDEBUG) || defined(PDIV_DEBUG)
266  if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
267  p, not_sev, currRing))
268  {
269 #ifdef HAVE_RINGS
271  {if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
272  return j;}
273  else
274 #endif
275  return j;
276  }
277 #else
278  if ( !(strat->sevS[j] & not_sev) &&
279  p_LmDivisibleBy(strat->S[j], p, currRing))
280  {
281 #ifdef HAVE_RINGS
283  {if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
284  return j;}
285  else
286 #endif
287  return j;
288  }
289 #endif
290  j++;
291  }
292 }
293 
294 #ifdef HAVE_RINGS
295 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
296 {
297  // m = currRing->ch
298 
299  if (input_p == NULL) return NULL;
300 
301  poly p = input_p;
302  poly zeroPoly = NULL;
303  unsigned long a = (unsigned long) pGetCoeff(p);
304 
305  int k_ind2 = 0;
306  int a_ind2 = ind2(a);
307 
308  // unsigned long k = 1;
309  // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
310  for (int i = 1; i <= leadRing->N; i++)
311  {
312  k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
313  }
314 
315  a = (unsigned long) pGetCoeff(p);
316 
317  number tmp1;
318  poly tmp2, tmp3;
319  poly lead_mult = p_ISet(1, tailRing);
320  if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
321  {
322  int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
323  int s_exp;
324  zeroPoly = p_ISet(a, tailRing);
325  for (int i = 1; i <= leadRing->N; i++)
326  {
327  s_exp = p_GetExp(p, i,leadRing);
328  if (s_exp % 2 != 0)
329  {
330  s_exp = s_exp - 1;
331  }
332  while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
333  {
334  too_much = too_much - ind2(s_exp);
335  s_exp = s_exp - 2;
336  }
337  p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
338  for (int j = 1; j <= s_exp; j++)
339  {
340  tmp1 = nInit(j);
341  tmp2 = p_ISet(1, tailRing);
342  p_SetExp(tmp2, i, 1, tailRing);
343  p_Setm(tmp2, tailRing);
344  if (nIsZero(tmp1))
345  { // should nowbe obsolet, test ! TODO OLIVER
346  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
347  }
348  else
349  {
350  tmp3 = p_NSet(nCopy(tmp1), tailRing);
351  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
352  }
353  }
354  }
355  p_Setm(lead_mult, tailRing);
356  zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
357  tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
358  for (int i = 1; i <= leadRing->N; i++)
359  {
360  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
361  }
362  p_Setm(tmp2, leadRing);
363  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
364  pNext(tmp2) = zeroPoly;
365  return tmp2;
366  }
367 /* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
368  if (1 == 0 && alpha_k <= a)
369  { // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
370  zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
371  for (int i = 1; i <= leadRing->N; i++)
372  {
373  for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
374  {
375  tmp1 = nInit(j);
376  tmp2 = p_ISet(1, tailRing);
377  p_SetExp(tmp2, i, 1, tailRing);
378  p_Setm(tmp2, tailRing);
379  if (nIsZero(tmp1))
380  {
381  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
382  }
383  else
384  {
385  tmp3 = p_ISet((unsigned long) tmp1, tailRing);
386  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
387  }
388  }
389  }
390  tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
391  for (int i = 1; i <= leadRing->N; i++)
392  {
393  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
394  }
395  p_Setm(tmp2, leadRing);
396  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
397  pNext(tmp2) = zeroPoly;
398  return tmp2;
399  } */
400  return NULL;
401 }
402 #endif
403 
404 
405 #ifdef HAVE_RINGS
406 /*2
407 * reduction procedure for the ring Z/2^m
408 */
410 {
411  if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
412  if (strat->tl<0) return 1;
413 
414  int at/*,i*/;
415  long d;
416  int j = 0;
417  int pass = 0;
418  // poly zeroPoly = NULL;
419 
420 // TODO warum SetpFDeg notwendig?
421  h->SetpFDeg();
422  assume(h->pFDeg() == h->FDeg);
423  long reddeg = h->GetpFDeg();
424 
425  h->SetShortExpVector();
426  loop
427  {
428  j = kFindDivisibleByInT(strat, h);
429  if (j < 0)
430  {
431  // over ZZ: cleanup coefficients by complete reduction with monomials
432  postReduceByMon(h, strat);
433  if(nIsZero(pGetCoeff(h->p))) return 2;
434  j = kFindDivisibleByInT(strat, h);
435  if(j < 0)
436  {
437  if(strat->tl >= 0)
438  h->i_r1 = strat->tl;
439  else
440  h->i_r1 = -1;
441  if (h->GetLmTailRing() == NULL)
442  {
443  if (h->lcm!=NULL) pLmDelete(h->lcm);
444  h->Clear();
445  return 0;
446  }
447  return 1;
448  }
449  }
450  #if ADIDEBUG
451  pWrite(h->p);
452  printf("\nFound j = %i\n",j);pWrite(strat->T[j].p);
453  #endif
454  ksReducePoly(h, &(strat->T[j]), NULL, NULL, strat); // with debug output
455  #if ADIDEBUG
456  printf("\nand after reduce: \n");pWrite(h->p);
457  #endif
458 
459  if (h->GetLmTailRing() == NULL)
460  {
461  if (h->lcm!=NULL) pLmDelete(h->lcm);
462 #ifdef KDEBUG
463  h->lcm=NULL;
464 #endif
465  h->Clear();
466  return 0;
467  }
468  h->SetShortExpVector();
469  d = h->SetpFDeg();
470  /*- try to reduce the s-polynomial -*/
471  pass++;
472  if (!TEST_OPT_REDTHROUGH &&
473  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
474  {
475  h->SetLmCurrRing();
476  if (strat->posInLDependsOnLength)
477  h->SetLength(strat->length_pLength);
478  at = strat->posInL(strat->L,strat->Ll,h,strat);
479  if (at <= strat->Ll)
480  {
481 #ifdef KDEBUG
482  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
483 #endif
484  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
485  h->Clear();
486  return -1;
487  }
488  }
489  if (d != reddeg)
490  {
491  if (d >= (long)strat->tailRing->bitmask)
492  {
493  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
494  {
495  strat->overflow=TRUE;
496  //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
497  h->GetP();
498  at = strat->posInL(strat->L,strat->Ll,h,strat);
499  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
500  h->Clear();
501  return -1;
502  }
503  }
504  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
505  {
506  Print(".%ld",d);mflush();
507  reddeg = d;
508  }
509  }
510  }
511 }
512 #endif
513 
514 /*2
515 * reduction procedure for the homogeneous case
516 * and the case of a degree-ordering
517 */
519 {
520  if (strat->tl<0) return 1;
521  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
522  assume(h->FDeg == h->pFDeg());
523 
524  poly h_p;
525  int i,j,at,pass, ii;
526  unsigned long not_sev;
527  // long reddeg,d;
528 
529  pass = j = 0;
530  // d = reddeg = h->GetpFDeg();
531  h->SetShortExpVector();
532  int li;
533  h_p = h->GetLmTailRing();
534  not_sev = ~ h->sev;
535  loop
536  {
537  j = kFindDivisibleByInT(strat, h);
538  if (j < 0) return 1;
539 
540  li = strat->T[j].pLength;
541  ii = j;
542  /*
543  * the polynomial to reduce with (up to the moment) is;
544  * pi with length li
545  */
546  i = j;
547 #if 1
548  if (TEST_OPT_LENGTH)
549  loop
550  {
551  /*- search the shortest possible with respect to length -*/
552  i++;
553  if (i > strat->tl)
554  break;
555  if (li<=1)
556  break;
557  if ((strat->T[i].pLength < li)
558  &&
559  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
560  h_p, not_sev, strat->tailRing))
561  {
562  /*
563  * the polynomial to reduce with is now;
564  */
565  li = strat->T[i].pLength;
566  ii = i;
567  }
568  }
569 #endif
570 
571  /*
572  * end of search: have to reduce with pi
573  */
574 #ifdef KDEBUG
575  if (TEST_OPT_DEBUG)
576  {
577  PrintS("red:");
578  h->wrp();
579  PrintS(" with ");
580  strat->T[ii].wrp();
581  }
582 #endif
583  assume(strat->fromT == FALSE);
584 
585  ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
586 #if SBA_PRINT_REDUCTION_STEPS
587  sba_interreduction_steps++;
588 #endif
589 #if SBA_PRINT_OPERATIONS
590  sba_interreduction_operations += pLength(strat->T[ii].p);
591 #endif
592 
593 #ifdef KDEBUG
594  if (TEST_OPT_DEBUG)
595  {
596  PrintS("\nto ");
597  h->wrp();
598  PrintLn();
599  }
600 #endif
601 
602  h_p = h->GetLmTailRing();
603  if (h_p == NULL)
604  {
605  if (h->lcm!=NULL) pLmFree(h->lcm);
606 #ifdef KDEBUG
607  h->lcm=NULL;
608 #endif
609  return 0;
610  }
611  h->SetShortExpVector();
612  not_sev = ~ h->sev;
613  /*
614  * try to reduce the s-polynomial h
615  *test first whether h should go to the lazyset L
616  *-if the degree jumps
617  *-if the number of pre-defined reductions jumps
618  */
619  pass++;
620  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
621  {
622  h->SetLmCurrRing();
623  at = strat->posInL(strat->L,strat->Ll,h,strat);
624  if (at <= strat->Ll)
625  {
626  int dummy=strat->sl;
627  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
628  return 1;
629  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
630 #ifdef KDEBUG
631  if (TEST_OPT_DEBUG)
632  Print(" lazy: -> L%d\n",at);
633 #endif
634  h->Clear();
635  return -1;
636  }
637  }
638  }
639 }
640 
642 {
643  BOOLEAN ret;
644  number coef;
645 
646  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
647  Red->HeadNormalize();
648  /*
649  printf("------------------------\n");
650  pWrite(Red->GetLmCurrRing());
651  */
652  ret = ksReducePolySig(Red, PW, 1, NULL, &coef);
653 
654 
655  if (!ret)
656  {
657  if (! n_IsOne(coef, currRing->cf))
658  {
659  PR->Mult_nn(coef);
660  // HANNES: mark for Normalize
661  }
662  n_Delete(&coef, currRing->cf);
663  }
664  return ret;
665 }
666 
667 /*2
668 * reduction procedure for signature-based standard
669 * basis algorithms:
670 * all reductions have to be sig-safe!
671 *
672 * 2 is returned if and only if the pair is rejected by the rewritten criterion
673 * at exactly this point of the computations. This is the last possible point
674 * such a check can be done => checks with the biggest set of available
675 * signatures
676 */
678 {
679  if (strat->tl<0) return 1;
680  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
681  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
682  assume(h->FDeg == h->pFDeg());
683 //#if 1
684 #ifdef DEBUGF5
685  Print("------- IN REDSIG -------\n");
686  Print("p: ");
687  pWrite(pHead(h->p));
688  Print("p1: ");
689  pWrite(pHead(h->p1));
690  Print("p2: ");
691  pWrite(pHead(h->p2));
692  Print("---------------------------\n");
693 #endif
694  poly h_p;
695  int i,j,at,pass, ii;
696  int start=0;
697  int sigSafe;
698  unsigned long not_sev;
699  // long reddeg,d;
700 
701  pass = j = 0;
702  // d = reddeg = h->GetpFDeg();
703  h->SetShortExpVector();
704  int li;
705  h_p = h->GetLmTailRing();
706  not_sev = ~ h->sev;
707  loop
708  {
709  j = kFindDivisibleByInT(strat, h, start);
710  if (j < 0)
711  {
712  return 1;
713  }
714 
715  li = strat->T[j].pLength;
716  ii = j;
717  /*
718  * the polynomial to reduce with (up to the moment) is;
719  * pi with length li
720  */
721  i = j;
722 #if 1
723  if (TEST_OPT_LENGTH)
724  loop
725  {
726  /*- search the shortest possible with respect to length -*/
727  i++;
728  if (i > strat->tl)
729  break;
730  if (li<=1)
731  break;
732  if ((strat->T[i].pLength < li)
733  &&
734  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
735  h_p, not_sev, strat->tailRing))
736  {
737  /*
738  * the polynomial to reduce with is now;
739  */
740  li = strat->T[i].pLength;
741  ii = i;
742  }
743  }
744  start = ii+1;
745 #endif
746 
747  /*
748  * end of search: have to reduce with pi
749  */
750 #ifdef KDEBUG
751  if (TEST_OPT_DEBUG)
752  {
753  PrintS("red:");
754  h->wrp();
755  PrintS(" with ");
756  strat->T[ii].wrp();
757  }
758 #endif
759  assume(strat->fromT == FALSE);
760 //#if 1
761 #ifdef DEBUGF5
762  Print("BEFORE REDUCTION WITH %d:\n",ii);
763  Print("--------------------------------\n");
764  pWrite(h->sig);
765  pWrite(strat->T[ii].sig);
766  pWrite(h->GetLmCurrRing());
767  pWrite(pHead(h->p1));
768  pWrite(pHead(h->p2));
769  pWrite(pHead(strat->T[ii].p));
770  Print("--------------------------------\n");
771  printf("INDEX OF REDUCER T: %d\n",ii);
772 #endif
773  sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
774 #if SBA_PRINT_REDUCTION_STEPS
775  if (sigSafe != 3)
776  sba_reduction_steps++;
777 #endif
778 #if SBA_PRINT_OPERATIONS
779  if (sigSafe != 3)
780  sba_operations += pLength(strat->T[ii].p);
781 #endif
782  // if reduction has taken place, i.e. the reduction was sig-safe
783  // otherwise start is already at the next position and the loop
784  // searching reducers in T goes on from index start
785 //#if 1
786 #ifdef DEBUGF5
787  Print("SigSAFE: %d\n",sigSafe);
788 #endif
789  if (sigSafe != 3)
790  {
791  // start the next search for reducers in T from the beginning
792  start = 0;
793 #ifdef KDEBUG
794  if (TEST_OPT_DEBUG)
795  {
796  PrintS("\nto ");
797  h->wrp();
798  PrintLn();
799  }
800 #endif
801 
802  h_p = h->GetLmTailRing();
803  if (h_p == NULL)
804  {
805  if (h->lcm!=NULL) pLmFree(h->lcm);
806 #ifdef KDEBUG
807  h->lcm=NULL;
808 #endif
809  return 0;
810  }
811  h->SetShortExpVector();
812  not_sev = ~ h->sev;
813  /*
814  * try to reduce the s-polynomial h
815  *test first whether h should go to the lazyset L
816  *-if the degree jumps
817  *-if the number of pre-defined reductions jumps
818  */
819  pass++;
820  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
821  {
822  h->SetLmCurrRing();
823  at = strat->posInL(strat->L,strat->Ll,h,strat);
824  if (at <= strat->Ll)
825  {
826  int dummy=strat->sl;
827  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
828  {
829  return 1;
830  }
831  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
832 #ifdef KDEBUG
833  if (TEST_OPT_DEBUG)
834  Print(" lazy: -> L%d\n",at);
835 #endif
836  h->Clear();
837  return -1;
838  }
839  }
840  }
841  }
842 }
843 
844 // tail reduction for SBA
846 {
847 #define REDTAIL_CANONICALIZE 100
848  strat->redTailChange=FALSE;
849  if (strat->noTailReduction) return L->GetLmCurrRing();
850  poly h, p;
851  p = h = L->GetLmTailRing();
852  if ((h==NULL) || (pNext(h)==NULL))
853  return L->GetLmCurrRing();
854 
855  TObject* With;
856  // placeholder in case strat->tl < 0
857  TObject With_s(strat->tailRing);
858 
859  LObject Ln(pNext(h), strat->tailRing);
860  Ln.sig = L->sig;
861  Ln.sevSig = L->sevSig;
862  Ln.pLength = L->GetpLength() - 1;
863 
864  pNext(h) = NULL;
865  if (L->p != NULL) pNext(L->p) = NULL;
866  L->pLength = 1;
867 
868  Ln.PrepareRed(strat->use_buckets);
869 
870  int cnt=REDTAIL_CANONICALIZE;
871  while(!Ln.IsNull())
872  {
873  loop
874  {
875  Ln.SetShortExpVector();
876  if (withT)
877  {
878  int j;
879  j = kFindDivisibleByInT(strat, &Ln);
880  if (j < 0) break;
881  With = &(strat->T[j]);
882  }
883  else
884  {
885  With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
886  if (With == NULL) break;
887  }
888  cnt--;
889  if (cnt==0)
890  {
892  /*poly tmp=*/Ln.CanonicalizeP();
893  if (normalize)
894  {
895  Ln.Normalize();
896  //pNormalize(tmp);
897  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
898  }
899  }
900  if (normalize && (!TEST_OPT_INTSTRATEGY) && (!nIsOne(pGetCoeff(With->p))))
901  {
902  With->pNorm();
903  }
904  strat->redTailChange=TRUE;
905  int ret = ksReducePolyTailSig(L, With, &Ln);
906 #if SBA_PRINT_REDUCTION_STEPS
907  if (ret != 3)
908  sba_reduction_steps++;
909 #endif
910 #if SBA_PRINT_OPERATIONS
911  if (ret != 3)
912  sba_operations += pLength(With->p);
913 #endif
914  if (ret)
915  {
916  // reducing the tail would violate the exp bound
917  // set a flag and hope for a retry (in bba)
918  strat->completeReduce_retry=TRUE;
919  if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
920  do
921  {
922  pNext(h) = Ln.LmExtractAndIter();
923  pIter(h);
924  L->pLength++;
925  } while (!Ln.IsNull());
926  goto all_done;
927  }
928  if (Ln.IsNull()) goto all_done;
929  if (! withT) With_s.Init(currRing);
930  }
931  pNext(h) = Ln.LmExtractAndIter();
932  pIter(h);
933  pNormalize(h);
934  L->pLength++;
935  }
936 
937  all_done:
938  Ln.Delete();
939  if (L->p != NULL) pNext(L->p) = pNext(p);
940 
941  if (strat->redTailChange)
942  {
943  L->length = 0;
944  }
945 
946  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
947  //L->Normalize(); // HANNES: should have a test
948  kTest_L(L);
949  return L->GetLmCurrRing();
950 }
951 
952 /*2
953 * reduction procedure for the inhomogeneous case
954 * and not a degree-ordering
955 */
957 {
958  if (strat->tl<0) return 1;
959  int at,i,ii,li;
960  int j = 0;
961  int pass = 0;
962  assume(h->pFDeg() == h->FDeg);
963  long reddeg = h->GetpFDeg();
964  long d;
965  unsigned long not_sev;
966 
967  h->SetShortExpVector();
968  poly h_p = h->GetLmTailRing();
969  not_sev = ~ h->sev;
970  loop
971  {
972  j = kFindDivisibleByInT(strat, h);
973  if (j < 0) return 1;
974 
975  li = strat->T[j].pLength;
976  #if 0
977  if (li==0)
978  {
979  li=strat->T[j].pLength=pLength(strat->T[j].p);
980  }
981  #endif
982  ii = j;
983  /*
984  * the polynomial to reduce with (up to the moment) is;
985  * pi with length li
986  */
987 
988  i = j;
989 #if 1
990  if (TEST_OPT_LENGTH)
991  loop
992  {
993  /*- search the shortest possible with respect to length -*/
994  i++;
995  if (i > strat->tl)
996  break;
997  if (li<=1)
998  break;
999  #if 0
1000  if (strat->T[i].pLength==0)
1001  {
1002  PrintS("!");
1003  strat->T[i].pLength=pLength(strat->T[i].p);
1004  }
1005  #endif
1006  if ((strat->T[i].pLength < li)
1007  &&
1008  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1009  h_p, not_sev, strat->tailRing))
1010  {
1011  /*
1012  * the polynomial to reduce with is now;
1013  */
1014  PrintS("+");
1015  li = strat->T[i].pLength;
1016  ii = i;
1017  }
1018  }
1019 #endif
1020 
1021  /*
1022  * end of search: have to reduce with pi
1023  */
1024 
1025 
1026 #ifdef KDEBUG
1027  if (TEST_OPT_DEBUG)
1028  {
1029  PrintS("red:");
1030  h->wrp();
1031  PrintS(" with ");
1032  strat->T[ii].wrp();
1033  }
1034 #endif
1035 
1036  ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
1037 #if SBA_PRINT_REDUCTION_STEPS
1038  sba_interreduction_steps++;
1039 #endif
1040 #if SBA_PRINT_OPERATIONS
1041  sba_interreduction_operations += pLength(strat->T[ii].p);
1042 #endif
1043 
1044 #ifdef KDEBUG
1045  if (TEST_OPT_DEBUG)
1046  {
1047  PrintS("\nto ");
1048  h->wrp();
1049  PrintLn();
1050  }
1051 #endif
1052 
1053  h_p=h->GetLmTailRing();
1054 
1055  if (h_p == NULL)
1056  {
1057  if (h->lcm!=NULL) pLmFree(h->lcm);
1058 #ifdef KDEBUG
1059  h->lcm=NULL;
1060 #endif
1061  return 0;
1062  }
1063  h->SetShortExpVector();
1064  not_sev = ~ h->sev;
1065  d = h->SetpFDeg();
1066  /*- try to reduce the s-polynomial -*/
1067  pass++;
1068  if (//!TEST_OPT_REDTHROUGH &&
1069  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1070  {
1071  h->SetLmCurrRing();
1072  at = strat->posInL(strat->L,strat->Ll,h,strat);
1073  if (at <= strat->Ll)
1074  {
1075 #if 1
1076  int dummy=strat->sl;
1077  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1078  return 1;
1079 #endif
1080 #ifdef KDEBUG
1081  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1082 #endif
1083  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1084  h->Clear();
1085  return -1;
1086  }
1087  }
1088  else if (d != reddeg)
1089  {
1090  if (d>=(long)strat->tailRing->bitmask)
1091  {
1092  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1093  {
1094  strat->overflow=TRUE;
1095  //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1096  h->GetP();
1097  at = strat->posInL(strat->L,strat->Ll,h,strat);
1098  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1099  h->Clear();
1100  return -1;
1101  }
1102  }
1103  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1104  {
1105  Print(".%ld",d);mflush();
1106  reddeg = d;
1107  }
1108  }
1109  }
1110 }
1111 /*2
1112 * reduction procedure for the sugar-strategy (honey)
1113 * reduces h with elements from T choosing first possible
1114 * element in T with respect to the given ecart
1115 */
1117 {
1118  if (strat->tl<0) return 1;
1119  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1120  assume(h->FDeg == h->pFDeg());
1121  poly h_p;
1122  int i,j,at,pass,ei, ii, h_d;
1123  unsigned long not_sev;
1124  long reddeg,d;
1125 
1126  pass = j = 0;
1127  d = reddeg = h->GetpFDeg() + h->ecart;
1128  h->SetShortExpVector();
1129  int li;
1130  h_p = h->GetLmTailRing();
1131  not_sev = ~ h->sev;
1132 
1133  h->PrepareRed(strat->use_buckets);
1134  loop
1135  {
1136  j=kFindDivisibleByInT(strat, h);
1137  if (j < 0) return 1;
1138 
1139  ei = strat->T[j].ecart;
1140  li = strat->T[j].pLength;
1141  ii = j;
1142  /*
1143  * the polynomial to reduce with (up to the moment) is;
1144  * pi with ecart ei
1145  */
1146  i = j;
1147  if (TEST_OPT_LENGTH)
1148  loop
1149  {
1150  /*- takes the first possible with respect to ecart -*/
1151  i++;
1152  if (i > strat->tl)
1153  break;
1154  //if (ei < h->ecart)
1155  // break;
1156  if (li<=1)
1157  break;
1158  if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
1159  || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1160  &&
1161  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1162  h_p, not_sev, strat->tailRing))
1163  {
1164  /*
1165  * the polynomial to reduce with is now;
1166  */
1167  ei = strat->T[i].ecart;
1168  li = strat->T[i].pLength;
1169  ii = i;
1170  }
1171  }
1172 
1173  /*
1174  * end of search: have to reduce with pi
1175  */
1176  if (!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart))
1177  {
1178  h->GetTP(); // clears bucket
1179  h->SetLmCurrRing();
1180  /*
1181  * It is not possible to reduce h with smaller ecart;
1182  * if possible h goes to the lazy-set L,i.e
1183  * if its position in L would be not the last one
1184  */
1185  if (strat->Ll >= 0) /* L is not empty */
1186  {
1187  at = strat->posInL(strat->L,strat->Ll,h,strat);
1188  if(at <= strat->Ll)
1189  /*- h will not become the next element to reduce -*/
1190  {
1191  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1192 #ifdef KDEBUG
1193  if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1194 #endif
1195  h->Clear();
1196  return -1;
1197  }
1198  }
1199  }
1200 #ifdef KDEBUG
1201  if (TEST_OPT_DEBUG)
1202  {
1203  PrintS("red:");
1204  h->wrp();
1205  PrintS(" with ");
1206  strat->T[ii].wrp();
1207  }
1208 #endif
1209  assume(strat->fromT == FALSE);
1210 
1211  number coef;
1212  ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),&coef,strat);
1213 #if SBA_PRINT_REDUCTION_STEPS
1214  sba_interreduction_steps++;
1215 #endif
1216 #if SBA_PRINT_OPERATIONS
1217  sba_interreduction_operations += pLength(strat->T[ii].p);
1218 #endif
1219 #ifdef KDEBUG
1220  if (TEST_OPT_DEBUG)
1221  {
1222  PrintS("\nto:");
1223  h->wrp();
1224  PrintLn();
1225  }
1226 #endif
1227  if(h->IsNull())
1228  {
1229  h->Clear();
1230  if (h->lcm!=NULL) pLmFree(h->lcm);
1231  #ifdef KDEBUG
1232  h->lcm=NULL;
1233  #endif
1234  return 0;
1235  }
1236  if (TEST_OPT_IDLIFT)
1237  {
1238  if (h->p!=NULL)
1239  {
1240  if(p_GetComp(h->p,currRing)>strat->syzComp)
1241  {
1242  h->Delete();
1243  return 0;
1244  }
1245  }
1246  else if (h->t_p!=NULL)
1247  {
1248  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1249  {
1250  h->Delete();
1251  return 0;
1252  }
1253  }
1254  }
1255  h->SetShortExpVector();
1256  not_sev = ~ h->sev;
1257  h_d = h->SetpFDeg();
1258  /* compute the ecart */
1259  if (ei <= h->ecart)
1260  h->ecart = d-h_d;
1261  else
1262  h->ecart = d-h_d+ei-h->ecart;
1263 
1264  /*
1265  * try to reduce the s-polynomial h
1266  *test first whether h should go to the lazyset L
1267  *-if the degree jumps
1268  *-if the number of pre-defined reductions jumps
1269  */
1270  pass++;
1271  d = h_d + h->ecart;
1272  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1273  {
1274  h->GetTP(); // clear bucket
1275  h->SetLmCurrRing();
1276  at = strat->posInL(strat->L,strat->Ll,h,strat);
1277  if (at <= strat->Ll)
1278  {
1279  int dummy=strat->sl;
1280  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1281  return 1;
1282  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1283 #ifdef KDEBUG
1284  if (TEST_OPT_DEBUG)
1285  Print(" degree jumped: -> L%d\n",at);
1286 #endif
1287  h->Clear();
1288  return -1;
1289  }
1290  }
1291  else if (d > reddeg)
1292  {
1293  if (d>=(long)strat->tailRing->bitmask)
1294  {
1295  if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
1296  {
1297  strat->overflow=TRUE;
1298  //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1299  h->GetP();
1300  at = strat->posInL(strat->L,strat->Ll,h,strat);
1301  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1302  h->Clear();
1303  return -1;
1304  }
1305  }
1306  else if (TEST_OPT_PROT && (strat->Ll < 0) )
1307  {
1308  //h->wrp(); Print("<%d>\n",h->GetpLength());
1309  reddeg = d;
1310  Print(".%ld",d); mflush();
1311  }
1312  }
1313  }
1314 }
1315 
1316 /*2
1317 * reduction procedure for the normal form
1318 */
1319 
1321 {
1322  if (h==NULL) return NULL;
1323  int j;
1324  max_ind=strat->sl;
1325 
1326  if (0 > strat->sl)
1327  {
1328  return h;
1329  }
1330  LObject P(h);
1331  P.SetShortExpVector();
1332  P.bucket = kBucketCreate(currRing);
1333  kBucketInit(P.bucket,P.p,pLength(P.p));
1334  kbTest(P.bucket);
1335 #ifdef HAVE_RINGS
1337 #endif
1338 #ifdef KDEBUG
1339 // if (TEST_OPT_DEBUG)
1340 // {
1341 // PrintS("redNF: starting S:\n");
1342 // for( j = 0; j <= max_ind; j++ )
1343 // {
1344 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1345 // pWrite(strat->S[j]);
1346 // }
1347 // };
1348 #endif
1349 
1350  loop
1351  {
1352  j=kFindDivisibleByInS(strat,&max_ind,&P);
1353  if (j>=0)
1354  {
1355 #ifdef HAVE_RINGS
1356  if (!is_ring)
1357  {
1358 #endif
1359  int sl=pSize(strat->S[j]);
1360  int jj=j;
1361  loop
1362  {
1363  int sll;
1364  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
1365  if (jj<0) break;
1366  sll=pSize(strat->S[jj]);
1367  if (sll<sl)
1368  {
1369  #ifdef KDEBUG
1370  if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
1371  #endif
1372  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
1373  j=jj;
1374  sl=sll;
1375  }
1376  }
1377  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
1378  {
1379  pNorm(strat->S[j]);
1380  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1381  }
1382 #ifdef HAVE_RINGS
1383  }
1384 #endif
1385  nNormalize(pGetCoeff(P.p));
1386 #ifdef KDEBUG
1387  if (TEST_OPT_DEBUG)
1388  {
1389  PrintS("red:");
1390  wrp(h);
1391  PrintS(" with ");
1392  wrp(strat->S[j]);
1393  }
1394 #endif
1395 #ifdef HAVE_PLURAL
1396  if (rIsPluralRing(currRing))
1397  {
1398  number coef;
1399  nc_kBucketPolyRed(P.bucket,strat->S[j],&coef);
1400  nDelete(&coef);
1401  }
1402  else
1403 #endif
1404  {
1405  number coef;
1406  coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
1407  nDelete(&coef);
1408  }
1409  h = kBucketGetLm(P.bucket); // FRAGE OLIVER
1410  if (h==NULL)
1411  {
1412  kBucketDestroy(&P.bucket);
1413 
1414 #ifdef KDEBUG
1415 // if (TEST_OPT_DEBUG)
1416 // {
1417 // PrintS("redNF: starting S:\n");
1418 // for( j = 0; j <= max_ind; j++ )
1419 // {
1420 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1421 // pWrite(strat->S[j]);
1422 // }
1423 // };
1424 #endif
1425 
1426  return NULL;
1427  }
1428  kbTest(P.bucket);
1429  P.p=h;
1430  P.t_p=NULL;
1431  P.SetShortExpVector();
1432 #ifdef KDEBUG
1433  if (TEST_OPT_DEBUG)
1434  {
1435  PrintS("\nto:");
1436  wrp(h);
1437  PrintLn();
1438  }
1439 #endif
1440  }
1441  else
1442  {
1443  P.p=kBucketClear(P.bucket);
1444  kBucketDestroy(&P.bucket);
1445  pNormalize(P.p);
1446 
1447 #ifdef KDEBUG
1448 // if (TEST_OPT_DEBUG)
1449 // {
1450 // PrintS("redNF: starting S:\n");
1451 // for( j = 0; j <= max_ind; j++ )
1452 // {
1453 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1454 // pWrite(strat->S[j]);
1455 // }
1456 // };
1457 #endif
1458 
1459  return P.p;
1460  }
1461  }
1462 }
1463 
1465 
1466 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1467 {
1468  int red_result = 1;
1469  int olddeg,reduc;
1470  int hilbeledeg=1,hilbcount=0,minimcnt=0;
1471  BOOLEAN withT = FALSE;
1472  BITSET save;
1473  SI_SAVE_OPT1(save);
1474 
1475  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
1476  initBuchMoraPos(strat);
1477  initHilbCrit(F,Q,&hilb,strat);
1478  initBba(F,strat);
1479  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
1480  /*Shdl=*/initBuchMora(F, Q,strat);
1481  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1482  reduc = olddeg = 0;
1483 
1484 #ifndef NO_BUCKETS
1485  if (!TEST_OPT_NOT_BUCKETS)
1486  strat->use_buckets = 1;
1487 #endif
1488  // redtailBBa against T for inhomogenous input
1489  if (!TEST_OPT_OLDSTD)
1490  withT = ! strat->homog;
1491 
1492  // strat->posInT = posInT_pLength;
1493  kTest_TS(strat);
1494 
1495 #ifdef KDEBUG
1496 #if MYTEST
1497  if (TEST_OPT_DEBUG)
1498  {
1499  PrintS("bba start GB: currRing: ");
1500  // rWrite(currRing);PrintLn();
1502  PrintLn();
1503  }
1504 #endif /* MYTEST */
1505 #endif /* KDEBUG */
1506 
1507 #ifdef HAVE_TAIL_RING
1508  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
1509  kStratInitChangeTailRing(strat);
1510 #endif
1511  if (BVERBOSE(23))
1512  {
1513  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1514  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1515  kDebugPrint(strat);
1516  }
1517 
1518 
1519 #ifdef KDEBUG
1520  //kDebugPrint(strat);
1521 #endif
1522  /* compute------------------------------------------------------- */
1523  while (strat->Ll >= 0)
1524  {
1525  #if ADIDEBUG
1526  printf("\n ------------------------NEW LOOP\n");
1527  printf("\nShdl = \n");
1528  #if 0
1529  idPrint(strat->Shdl);
1530  #else
1531  for(int ii = 0; ii<=strat->sl;ii++)
1532  p_Write(strat->S[ii],strat->tailRing);
1533  #endif
1534  printf("\n list L\n");
1535  int iii;
1536  #if 1
1537  for(iii = 0; iii<= strat->Ll; iii++)
1538  {
1539  printf("L[%i]:",iii);
1540  p_Write(strat->L[iii].p, currRing);
1541  p_Write(strat->L[iii].p1, currRing);
1542  p_Write(strat->L[iii].p2, currRing);
1543  }
1544  #else
1545  {
1546  printf("L[%i]:",strat->Ll);
1547  p_Write(strat->L[strat->Ll].p, strat->tailRing);
1548  p_Write(strat->L[strat->Ll].p1, strat->tailRing);
1549  p_Write(strat->L[strat->Ll].p2, strat->tailRing);
1550  }
1551  #endif
1552  #if 1
1553  for(iii = 0; iii<= strat->Bl; iii++)
1554  {
1555  printf("B[%i]:",iii);
1556  p_Write(strat->B[iii].p, /*strat->tailRing*/currRing);
1557  p_Write(strat->B[iii].p1, /*strat->tailRing*/currRing);
1558  p_Write(strat->B[iii].p2, strat->tailRing);
1559  }
1560  #endif
1561  getchar();
1562  #endif
1563  #ifdef KDEBUG
1564  if (TEST_OPT_DEBUG) messageSets(strat);
1565  #endif
1566  if (strat->Ll== 0) strat->interpt=TRUE;
1567  if (TEST_OPT_DEGBOUND
1568  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1569  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
1570  {
1571  /*
1572  *stops computation if
1573  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
1574  *a predefined number Kstd1_deg
1575  */
1576  while ((strat->Ll >= 0)
1577  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1578  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1579  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
1580  )
1581  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1582  if (strat->Ll<0) break;
1583  else strat->noClearS=TRUE;
1584  }
1585  /* picks the last element from the lazyset L */
1586  strat->P = strat->L[strat->Ll];
1587  strat->Ll--;
1588 
1589  if (pNext(strat->P.p) == strat->tail)
1590  {
1591  // deletes the short spoly
1592 #ifdef HAVE_RINGS
1593  if (rField_is_Ring(currRing))
1594  pLmDelete(strat->P.p);
1595  else
1596 #endif
1597  pLmFree(strat->P.p);
1598  strat->P.p = NULL;
1599  poly m1 = NULL, m2 = NULL;
1600 
1601  // check that spoly creation is ok
1602  while (strat->tailRing != currRing &&
1603  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1604  {
1605  assume(m1 == NULL && m2 == NULL);
1606  // if not, change to a ring where exponents are at least
1607  // large enough
1608  if (!kStratChangeTailRing(strat))
1609  {
1610  WerrorS("OVERFLOW...");
1611  break;
1612  }
1613  }
1614  // create the real one
1615  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
1616  strat->tailRing, m1, m2, strat->R);
1617  }
1618  else if (strat->P.p1 == NULL)
1619  {
1620  if (strat->minim > 0)
1621  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
1622  // for input polys, prepare reduction
1623  strat->P.PrepareRed(strat->use_buckets);
1624  }
1625 
1626  if (strat->P.p == NULL && strat->P.t_p == NULL)
1627  {
1628  red_result = 0;
1629  }
1630  else
1631  {
1632  if (TEST_OPT_PROT)
1633  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
1634  &olddeg,&reduc,strat, red_result);
1635 
1636  /* reduction of the element chosen from L */
1637  #if ADIDEBUG
1638  printf("\nBefore \n");pWrite(strat->P.p);
1639  #endif
1640  red_result = strat->red(&strat->P,strat);
1641  #if ADIDEBUG
1642  printf("\nAfter \n");pWrite(strat->P.p);
1643  #endif
1644  if (errorreported) break;
1645  }
1646 
1647  if (strat->overflow)
1648  {
1649  if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
1650  }
1651 
1652  // reduction to non-zero new poly
1653  if (red_result == 1)
1654  {
1655  // get the polynomial (canonicalize bucket, make sure P.p is set)
1656  strat->P.GetP(strat->lmBin);
1657  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
1658  // but now, for entering S, T, we reset it
1659  // in the inhomogeneous case: FDeg == pFDeg
1660  if (strat->homog) strat->initEcart(&(strat->P));
1661 
1662  /* statistic */
1663  if (TEST_OPT_PROT) PrintS("s");
1664 
1665  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1666 
1667 #ifdef KDEBUG
1668 #if MYTEST
1669  PrintS("New S: "); p_DebugPrint(strat->P.p, currRing); PrintLn();
1670 #endif /* MYTEST */
1671 #endif /* KDEBUG */
1672 
1673  // reduce the tail and normalize poly
1674  // in the ring case we cannot expect LC(f) = 1,
1675  // therefore we call pContent instead of pNorm
1677  {
1678  strat->P.pCleardenom();
1680  {
1681  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1682  strat->P.pCleardenom();
1683  }
1684  }
1685  else
1686  {
1687  strat->P.pNorm();
1689  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1690  }
1691 
1692 #ifdef KDEBUG
1693  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
1694 #if MYTEST
1695  PrintS("New (reduced) S: "); p_DebugPrint(strat->P.p, currRing); PrintLn();
1696 #endif /* MYTEST */
1697 #endif /* KDEBUG */
1698 
1699  // min_std stuff
1700  if ((strat->P.p1==NULL) && (strat->minim>0))
1701  {
1702  if (strat->minim==1)
1703  {
1704  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
1705  p_Delete(&strat->P.p2, currRing, strat->tailRing);
1706  }
1707  else
1708  {
1709  strat->M->m[minimcnt]=strat->P.p2;
1710  strat->P.p2=NULL;
1711  }
1712  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
1713  pNext(strat->M->m[minimcnt])
1714  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
1715  strat->tailRing, currRing,
1716  currRing->PolyBin);
1717  minimcnt++;
1718  }
1719 
1720  // enter into S, L, and T
1721  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
1722  {
1723  enterT(strat->P, strat);
1724 #ifdef HAVE_RINGS
1725  if (rField_is_Ring(currRing))
1726  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1727  else
1728 #endif
1729  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1730  // posInS only depends on the leading term
1731  #if ADIDEBUG
1732  printf("\nThis element is added to S\n");
1733  p_Write(strat->P.p, strat->tailRing);p_Write(strat->P.p1, strat->tailRing);p_Write(strat->P.p2, strat->tailRing);
1734  #endif
1735  strat->enterS(strat->P, pos, strat, strat->tl);
1736 #if 0
1737  int pl=pLength(strat->P.p);
1738  if (pl==1)
1739  {
1740  //if (TEST_OPT_PROT)
1741  //PrintS("<1>");
1742  }
1743  else if (pl==2)
1744  {
1745  //if (TEST_OPT_PROT)
1746  //PrintS("<2>");
1747  }
1748 #endif
1749  }
1750  if (strat->s_poly!=NULL)
1751  {
1752  if (strat->s_poly(strat))
1753  {
1754  // we are called AFTER enterS, i.e. if we change P
1755  // we have it also to S/T
1756  // and add pairs
1757  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1758  enterT(strat->P, strat);
1759  #ifdef HAVE_RINGS
1760  if (rField_is_Ring(currRing))
1761  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1762  else
1763  #endif
1764  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1765  strat->enterS(strat->P, pos, strat, strat->tl);
1766  }
1767  }
1768 
1769  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
1770 // Print("[%d]",hilbeledeg);
1771  if (strat->P.lcm!=NULL)
1772 #ifdef HAVE_RINGS
1773  pLmDelete(strat->P.lcm);
1774 #else
1775  pLmFree(strat->P.lcm);
1776 #endif
1777  }
1778  else if (strat->P.p1 == NULL && strat->minim > 0)
1779  {
1780  p_Delete(&strat->P.p2, currRing, strat->tailRing);
1781  }
1782 
1783 #ifdef KDEBUG
1784  memset(&(strat->P), 0, sizeof(strat->P));
1785 #endif /* KDEBUG */
1786  kTest_TS(strat);
1787  }
1788 #ifdef KDEBUG
1789 #if MYTEST
1790  PrintS("bba finish GB: currRing: "); rWrite(currRing);
1791 #endif /* MYTEST */
1792  if (TEST_OPT_DEBUG) messageSets(strat);
1793 #endif /* KDEBUG */
1794 
1795  if (TEST_OPT_SB_1)
1796  {
1797  #ifdef HAVE_RINGS
1798  if(!rField_is_Ring(currRing))
1799  #endif
1800  {
1801  int k=1;
1802  int j;
1803  while(k<=strat->sl)
1804  {
1805  j=0;
1806  loop
1807  {
1808  if (j>=k) break;
1809  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
1810  j++;
1811  }
1812  k++;
1813  }
1814  }
1815  }
1816  /* complete reduction of the standard basis--------- */
1817  if (TEST_OPT_REDSB)
1818  {
1819  completeReduce(strat);
1820 #ifdef HAVE_TAIL_RING
1821  if (strat->completeReduce_retry)
1822  {
1823  // completeReduce needed larger exponents, retry
1824  // to reduce with S (instead of T)
1825  // and in currRing (instead of strat->tailRing)
1826  cleanT(strat);strat->tailRing=currRing;
1827  int i;
1828  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
1829  completeReduce(strat);
1830  }
1831 #endif
1832  }
1833  else if (TEST_OPT_PROT) PrintLn();
1834  #ifdef HAVE_RINGS
1835  if(nCoeff_is_Ring_Z(currRing->cf))
1836  finalReduceByMon(strat);
1838  {
1839  for(int i = 0;i<=strat->sl;i++)
1840  {
1841  if(!nGreaterZero(pGetCoeff(strat->S[i])))
1842  {
1843  strat->S[i] = pNeg(strat->S[i]);
1844  }
1845  }
1846  }
1847  #endif
1848  /* release temp data-------------------------------- */
1849  exitBuchMora(strat);
1850 // if (TEST_OPT_WEIGHTM)
1851 // {
1852 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
1853 // if (ecartWeights)
1854 // {
1855 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
1856 // ecartWeights=NULL;
1857 // }
1858 // }
1859  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
1860  SI_RESTORE_OPT1(save);
1861  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
1862 
1863 #ifdef KDEBUG
1864 #if MYTEST
1865  PrintS("bba_end: currRing: "); rWrite(currRing);
1866 #endif /* MYTEST */
1867 #endif /* KDEBUG */
1868  idTest(strat->Shdl);
1869 
1870  return (strat->Shdl);
1871 }
1872 ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1873 {
1874  // ring order stuff:
1875  // in sba we have (until now) two possibilities:
1876  // 1. an incremental computation w.r.t. (C,monomial order)
1877  // 2. a (possibly non-incremental) computation w.r.t. the
1878  // induced Schreyer order.
1879  // The corresponding orders are computed in sbaRing(), depending
1880  // on the flag strat->sbaOrder
1881 #if SBA_PRINT_ZERO_REDUCTIONS
1882  long zeroreductions = 0;
1883 #endif
1884 #if SBA_PRINT_PRODUCT_CRITERION
1885  long product_criterion = 0;
1886 #endif
1887 #if SBA_PRINT_SIZE_G
1888  int size_g = 0;
1889  int size_g_non_red = 0;
1890 #endif
1891 #if SBA_PRINT_SIZE_SYZ
1892  long size_syz = 0;
1893 #endif
1894  // global variable
1895 #if SBA_PRINT_REDUCTION_STEPS
1896  sba_reduction_steps = 0;
1897  sba_interreduction_steps = 0;
1898 #endif
1899 #if SBA_PRINT_OPERATIONS
1900  sba_operations = 0;
1901  sba_interreduction_operations = 0;
1902 #endif
1903 
1904  ideal F1 = F0;
1905  ring sRing, currRingOld;
1906  currRingOld = currRing;
1907  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
1908  {
1909  sRing = sbaRing(strat);
1910  if (sRing!=currRingOld)
1911  {
1912  rChangeCurrRing (sRing);
1913  F1 = idrMoveR (F0, currRingOld, currRing);
1914  }
1915  }
1916  // sort ideal F
1917  ideal F = idInit(IDELEMS(F1),F1->rank);
1918  intvec *sort = idSort(F1);
1919  for (int i=0; i<sort->length();++i)
1920  F->m[i] = F1->m[(*sort)[i]-1];
1921 #if SBA_INTERRED_START
1922  F = kInterRed(F,NULL);
1923 #endif
1924 #if F5DEBUG
1925  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
1926  rWrite (currRing);
1927  printf("ordSgn = %d\n",currRing->OrdSgn);
1928  printf("\n");
1929 #endif
1930  int srmax,lrmax, red_result = 1;
1931  int olddeg,reduc;
1932  int hilbeledeg=1,hilbcount=0,minimcnt=0;
1933  LObject L;
1934  BOOLEAN withT = TRUE;
1935  strat->max_lower_index = 0;
1936 
1937  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
1938  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
1939  initSbaPos(strat);
1940  //initBuchMoraPos(strat);
1941  initHilbCrit(F,Q,&hilb,strat);
1942  initSba(F,strat);
1943  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
1944  /*Shdl=*/initSbaBuchMora(F, Q,strat);
1945  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1946  srmax = strat->sl;
1947  reduc = olddeg = lrmax = 0;
1948 
1949 #ifndef NO_BUCKETS
1950  if (!TEST_OPT_NOT_BUCKETS)
1951  strat->use_buckets = 1;
1952 #endif
1953 
1954  // redtailBBa against T for inhomogenous input
1955  // if (!TEST_OPT_OLDSTD)
1956  // withT = ! strat->homog;
1957 
1958  // strat->posInT = posInT_pLength;
1959  kTest_TS(strat);
1960 
1961 #ifdef KDEBUG
1962 #if MYTEST
1963  if (TEST_OPT_DEBUG)
1964  {
1965  PrintS("bba start GB: currRing: ");
1966  // rWrite(currRing);PrintLn();
1968  PrintLn();
1969  }
1970 #endif /* MYTEST */
1971 #endif /* KDEBUG */
1972 
1973 #ifdef HAVE_TAIL_RING
1974  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
1975  kStratInitChangeTailRing(strat);
1976 #endif
1977  if (BVERBOSE(23))
1978  {
1979  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1980  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1981  kDebugPrint(strat);
1982  }
1983 
1984 
1985 #ifdef KDEBUG
1986  //kDebugPrint(strat);
1987 #endif
1988  /* compute------------------------------------------------------- */
1989  while (strat->Ll >= 0)
1990  {
1991  if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
1992  #ifdef KDEBUG
1993  if (TEST_OPT_DEBUG) messageSets(strat);
1994  #endif
1995  if (strat->Ll== 0) strat->interpt=TRUE;
1996  /*
1997  if (TEST_OPT_DEGBOUND
1998  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1999  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2000  {
2001 
2002  //stops computation if
2003  // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2004  //a predefined number Kstd1_deg
2005  while ((strat->Ll >= 0)
2006  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2007  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2008  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2009  )
2010  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2011  if (strat->Ll<0) break;
2012  else strat->noClearS=TRUE;
2013  }
2014  */
2015  if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2016  {
2017  strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2018 #if F5C
2019  // 1. interreduction of the current standard basis
2020  // 2. generation of new principal syzygy rules for syzCriterion
2021  f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2022  lrmax, reduc, Q, w, hilb );
2023 #endif
2024  // initialize new syzygy rules for the next iteration step
2025  initSyzRules(strat);
2026 
2027  }
2028  /*********************************************************************
2029  * interrreduction step is done, we can go on with the next iteration
2030  * step of the signature-based algorithm
2031  ********************************************************************/
2032  /* picks the last element from the lazyset L */
2033  strat->P = strat->L[strat->Ll];
2034  strat->Ll--;
2035  /* reduction of the element chosen from L */
2036 
2037  if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
2038  //#if 1
2039 #ifdef DEBUGF5
2040  Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2041  Print("-------------------------------------------------\n");
2042  pWrite(strat->P.sig);
2043  pWrite(pHead(strat->P.p));
2044  pWrite(pHead(strat->P.p1));
2045  pWrite(pHead(strat->P.p2));
2046  Print("-------------------------------------------------\n");
2047 #endif
2048  if (pNext(strat->P.p) == strat->tail)
2049  {
2050  // deletes the short spoly
2051  /*
2052 #ifdef HAVE_RINGS
2053  if (rField_is_Ring(currRing))
2054  pLmDelete(strat->P.p);
2055  else
2056 #endif
2057  pLmFree(strat->P.p);
2058 */
2059  // TODO: needs some masking
2060  // TODO: masking needs to vanish once the signature
2061  // sutff is completely implemented
2062  strat->P.p = NULL;
2063  poly m1 = NULL, m2 = NULL;
2064 
2065  // check that spoly creation is ok
2066  while (strat->tailRing != currRing &&
2067  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2068  {
2069  assume(m1 == NULL && m2 == NULL);
2070  // if not, change to a ring where exponents are at least
2071  // large enough
2072  if (!kStratChangeTailRing(strat))
2073  {
2074  WerrorS("OVERFLOW...");
2075  break;
2076  }
2077  }
2078  // create the real one
2079  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2080  strat->tailRing, m1, m2, strat->R);
2081 
2082  }
2083  else if (strat->P.p1 == NULL)
2084  {
2085  if (strat->minim > 0)
2086  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2087  // for input polys, prepare reduction
2088  strat->P.PrepareRed(strat->use_buckets);
2089  }
2090  if (strat->P.p == NULL && strat->P.t_p == NULL)
2091  {
2092  red_result = 0;
2093  }
2094  else
2095  {
2096  //#if 1
2097 #ifdef DEBUGF5
2098  Print("Poly before red: ");
2099  pWrite(pHead(strat->P.p));
2100  pWrite(strat->P.sig);
2101 #endif
2102 #if SBA_PRODUCT_CRITERION
2103  if (strat->P.prod_crit) {
2104 #if SBA_PRINT_PRODUCT_CRITERION
2105  product_criterion++;
2106 #endif
2107  int pos = posInSyz(strat, strat->P.sig);
2108  enterSyz(strat->P, strat, pos);
2109  if (strat->P.lcm!=NULL)
2110  pLmFree(strat->P.lcm);
2111  red_result = 2;
2112  } else {
2113  red_result = strat->red(&strat->P,strat);
2114  }
2115 #else
2116  red_result = strat->red(&strat->P,strat);
2117 #endif
2118  }
2119  } else {
2120  /*
2121  if (strat->P.lcm != NULL)
2122  pLmFree(strat->P.lcm);
2123  */
2124  red_result = 2;
2125  }
2126  if (errorreported) break;
2127 
2128 //#if 1
2129 #ifdef DEBUGF5
2130  if (red_result != 0) {
2131  Print("Poly after red: ");
2132  pWrite(pHead(strat->P.p));
2133  pWrite(strat->P.GetLmCurrRing());
2134  pWrite(strat->P.sig);
2135  printf("%d\n",red_result);
2136  }
2137 #endif
2138 
2139  if (strat->overflow)
2140  {
2141  if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
2142  }
2143 
2144  // reduction to non-zero new poly
2145  if (red_result == 1)
2146  {
2147  // get the polynomial (canonicalize bucket, make sure P.p is set)
2148  strat->P.GetP(strat->lmBin);
2149 
2150  // sig-safe computations may lead to wrong FDeg computation, thus we need
2151  // to recompute it to make sure everything is alright
2152  (strat->P).FDeg = (strat->P).pFDeg();
2153  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2154  // but now, for entering S, T, we reset it
2155  // in the inhomogeneous case: FDeg == pFDeg
2156  if (strat->homog) strat->initEcart(&(strat->P));
2157 
2158  /* statistic */
2159  if (TEST_OPT_PROT) PrintS("s");
2160 
2161  //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2162  // in F5E we know that the last reduced element is already the
2163  // the one with highest signature
2164  int pos = strat->sl+1;
2165 
2166 #ifdef KDEBUG
2167 #if MYTEST
2168  PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
2169 #endif /* MYTEST */
2170 #endif /* KDEBUG */
2171 
2172  // reduce the tail and normalize poly
2173  // in the ring case we cannot expect LC(f) = 1,
2174  // therefore we call pContent instead of pNorm
2175 #if SBA_TAIL_RED
2176  if (strat->sbaOrder != 2) {
2178  {
2179  strat->P.pCleardenom();
2181  {
2182  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2183  strat->P.pCleardenom();
2184  }
2185  }
2186  else
2187  {
2188  strat->P.pNorm();
2190  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2191  }
2192  }
2193 #endif
2194 
2195  // remove sigsafe label since it is no longer valid for the next element to
2196  // be reduced
2197  if (strat->sbaOrder == 1)
2198  {
2199  for (int jj = 0; jj<strat->tl+1; jj++)
2200  {
2201  if (pGetComp(strat->T[jj].sig) == strat->currIdx)
2202  {
2203  strat->T[jj].is_sigsafe = FALSE;
2204  }
2205  }
2206  }
2207  else
2208  {
2209  for (int jj = 0; jj<strat->tl+1; jj++)
2210  {
2211  strat->T[jj].is_sigsafe = FALSE;
2212  }
2213  }
2214 #ifdef KDEBUG
2215  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2216 #if MYTEST
2217 //#if 1
2218  PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
2219 #endif /* MYTEST */
2220 #endif /* KDEBUG */
2221 
2222  // min_std stuff
2223  if ((strat->P.p1==NULL) && (strat->minim>0))
2224  {
2225  if (strat->minim==1)
2226  {
2227  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2228  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2229  }
2230  else
2231  {
2232  strat->M->m[minimcnt]=strat->P.p2;
2233  strat->P.p2=NULL;
2234  }
2235  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2236  pNext(strat->M->m[minimcnt])
2237  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2238  strat->tailRing, currRing,
2239  currRing->PolyBin);
2240  minimcnt++;
2241  }
2242 
2243  // enter into S, L, and T
2244  //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2245  enterT(strat->P, strat);
2246  strat->T[strat->tl].is_sigsafe = FALSE;
2247  /*
2248  printf("hier\n");
2249  pWrite(strat->P.GetLmCurrRing());
2250  pWrite(strat->P.sig);
2251  */
2252 #ifdef HAVE_RINGS
2253  if (rField_is_Ring(currRing))
2254  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2255  else
2256 #endif
2257  enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2258  // posInS only depends on the leading term
2259  strat->enterS(strat->P, pos, strat, strat->tl);
2260  if(strat->sbaOrder != 1)
2261  {
2262  BOOLEAN overwrite = FALSE;
2263  for (int tk=0; tk<strat->sl+1; tk++)
2264  {
2265  if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
2266  {
2267  //printf("TK %d / %d\n",tk,strat->sl);
2268  overwrite = FALSE;
2269  break;
2270  }
2271  }
2272  //printf("OVERWRITE %d\n",overwrite);
2273  if (overwrite)
2274  {
2275  int cmp = pGetComp(strat->P.sig);
2276  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
2277  pGetExpV (strat->P.p,vv);
2278  pSetExpV (strat->P.sig, vv);
2279  pSetComp (strat->P.sig,cmp);
2280 
2281  strat->P.sevSig = pGetShortExpVector (strat->P.sig);
2282  int i;
2283  LObject Q;
2284  for(int ps=0;ps<strat->sl+1;ps++)
2285  {
2286 
2287  strat->newt = TRUE;
2288  if (strat->syzl == strat->syzmax)
2289  {
2290  pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
2291  strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
2292  (strat->syzmax)*sizeof(unsigned long),
2293  ((strat->syzmax)+setmaxTinc)
2294  *sizeof(unsigned long));
2295  strat->syzmax += setmaxTinc;
2296  }
2297  Q.sig = pCopy(strat->P.sig);
2298  // add LM(F->m[i]) to the signature to get a Schreyer order
2299  // without changing the underlying polynomial ring at all
2300  if (strat->sbaOrder == 0)
2301  p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
2302  // since p_Add_q() destroys all input
2303  // data we need to recreate help
2304  // each time
2305  // ----------------------------------------------------------
2306  // in the Schreyer order we always know that the multiplied
2307  // module monomial strat->P.sig gives the leading monomial of
2308  // the corresponding principal syzygy
2309  // => we do not need to compute the "real" syzygy completely
2310  poly help = p_Copy(strat->sig[ps],currRing);
2311  p_ExpVectorAdd (help,strat->P.p,currRing);
2312  Q.sig = p_Add_q(Q.sig,help,currRing);
2313  //printf("%d. SYZ ",i+1);
2314  //pWrite(strat->syz[i]);
2315  Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
2316  i = posInSyz(strat, Q.sig);
2317  enterSyz(Q, strat, i);
2318  }
2319  }
2320  }
2321  // deg - idx - lp/rp
2322  // => we need to add syzygies with indices > pGetComp(strat->P.sig)
2323  if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
2324  {
2325  int cmp = pGetComp(strat->P.sig);
2326  int max_cmp = IDELEMS(F);
2327  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
2328  pGetExpV (strat->P.p,vv);
2329  LObject Q;
2330  int pos;
2331  int idx = p_GetComp(strat->P.sig,currRing);
2332  //printf("++ -- adding syzygies -- ++\n");
2333  // if new element is the first one in this index
2334  if (strat->currIdx < idx) {
2335  for (int i=0; i<strat->sl; ++i) {
2336  Q.sig = p_Copy(strat->P.sig,currRing);
2337  p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
2338  poly help = p_Copy(strat->sig[i],currRing);
2339  p_ExpVectorAdd(help,strat->P.p,currRing);
2340  Q.sig = p_Add_q(Q.sig,help,currRing);
2341  //pWrite(Q.sig);
2342  pos = posInSyz(strat, Q.sig);
2343  enterSyz(Q, strat, pos);
2344  }
2345  strat->currIdx = idx;
2346  } else {
2347  // if the element is not the first one in the given index we build all
2348  // possible syzygies with elements of higher index
2349  for (int i=cmp+1; i<=max_cmp; ++i) {
2350  pos = -1;
2351  for (int j=0; j<strat->sl; ++j) {
2352  if (p_GetComp(strat->sig[j],currRing) == i) {
2353  pos = j;
2354  break;
2355  }
2356  }
2357  if (pos != -1) {
2358  Q.sig = p_One(currRing);
2359  p_SetExpV(Q.sig, vv, currRing);
2360  // F->m[i-1] corresponds to index i
2361  p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
2362  p_SetComp(Q.sig, i, currRing);
2363  poly help = p_Copy(strat->P.sig,currRing);
2364  p_ExpVectorAdd(help,strat->S[pos],currRing);
2365  Q.sig = p_Add_q(Q.sig,help,currRing);
2366  if (strat->sbaOrder == 0) {
2367  if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn) {
2368  pos = posInSyz(strat, Q.sig);
2369  enterSyz(Q, strat, pos);
2370  }
2371  } else {
2372  pos = posInSyz(strat, Q.sig);
2373  enterSyz(Q, strat, pos);
2374  }
2375  }
2376  }
2377  //printf("++ -- done adding syzygies -- ++\n");
2378  }
2379  }
2380 //#if 1
2381 #if DEBUGF50
2382  printf("---------------------------\n");
2383  Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
2384  Print("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
2385  Print("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
2386 #endif
2387  /*
2388  if (newrules)
2389  {
2390  newrules = FALSE;
2391  }
2392  */
2393 #if 0
2394  int pl=pLength(strat->P.p);
2395  if (pl==1)
2396  {
2397  //if (TEST_OPT_PROT)
2398  //PrintS("<1>");
2399  }
2400  else if (pl==2)
2401  {
2402  //if (TEST_OPT_PROT)
2403  //PrintS("<2>");
2404  }
2405 #endif
2406  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2407 // Print("[%d]",hilbeledeg);
2408  if (strat->P.lcm!=NULL)
2409 #ifdef HAVE_RINGS
2410  pLmDelete(strat->P.lcm);
2411 #else
2412  pLmFree(strat->P.lcm);
2413 #endif
2414  if (strat->sl>srmax) srmax = strat->sl;
2415  }
2416  else
2417  {
2418  // adds signature of the zero reduction to
2419  // strat->syz. This is the leading term of
2420  // syzygy and can be used in syzCriterion()
2421  // the signature is added if and only if the
2422  // pair was not detected by the rewritten criterion in strat->red = redSig
2423  if (red_result!=2) {
2424 #if SBA_PRINT_ZERO_REDUCTIONS
2425  zeroreductions++;
2426 #endif
2427  int pos = posInSyz(strat, strat->P.sig);
2428  enterSyz(strat->P, strat, pos);
2429 //#if 1
2430 #ifdef DEBUGF5
2431  Print("ADDING STUFF TO SYZ : ");
2432  //pWrite(strat->P.p);
2433  pWrite(strat->P.sig);
2434 #endif
2435  }
2436  if (strat->P.p1 == NULL && strat->minim > 0)
2437  {
2438  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2439  }
2440  }
2441 
2442 #ifdef KDEBUG
2443  memset(&(strat->P), 0, sizeof(strat->P));
2444 #endif /* KDEBUG */
2445  kTest_TS(strat);
2446  }
2447 #ifdef KDEBUG
2448 #if MYTEST
2449  PrintS("bba finish GB: currRing: "); rWrite(currRing);
2450 #endif /* MYTEST */
2451  if (TEST_OPT_DEBUG) messageSets(strat);
2452 #endif /* KDEBUG */
2453 
2454  if (TEST_OPT_SB_1)
2455  {
2456  #ifdef HAVE_RINGS
2457  if(!rField_is_Ring(currRing))
2458  #endif
2459  {
2460  int k=1;
2461  int j;
2462  while(k<=strat->sl)
2463  {
2464  j=0;
2465  loop
2466  {
2467  if (j>=k) break;
2468  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2469  j++;
2470  }
2471  k++;
2472  }
2473  }
2474  }
2475 
2476  /* complete reduction of the standard basis--------- */
2477  if (TEST_OPT_REDSB)
2478  {
2479  completeReduce(strat);
2480 #ifdef HAVE_TAIL_RING
2481  if (strat->completeReduce_retry)
2482  {
2483  // completeReduce needed larger exponents, retry
2484  // to reduce with S (instead of T)
2485  // and in currRing (instead of strat->tailRing)
2486  cleanT(strat);strat->tailRing=currRing;
2487  int i;
2488  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2489  completeReduce(strat);
2490  }
2491 #endif
2492  }
2493  else if (TEST_OPT_PROT) PrintLn();
2494 
2495 #if SBA_PRINT_SIZE_SYZ
2496  // that is correct, syzl is counting one too far
2497  size_syz = strat->syzl;
2498 #endif
2499  exitSba(strat);
2500 // if (TEST_OPT_WEIGHTM)
2501 // {
2502 // pRestoreDegProcs(pFDegOld, pLDegOld);
2503 // if (ecartWeights)
2504 // {
2505 // omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
2506 // ecartWeights=NULL;
2507 // }
2508 // }
2509  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
2510  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2511 
2512 #ifdef KDEBUG
2513 #if MYTEST
2514  PrintS("bba_end: currRing: "); rWrite(currRing);
2515 #endif /* MYTEST */
2516 #endif /* KDEBUG */
2517 #if SBA_PRINT_SIZE_G
2518  size_g_non_red = IDELEMS(strat->Shdl);
2519 #endif
2520  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
2521  {
2522  rChangeCurrRing (currRingOld);
2523  F0 = idrMoveR (F1, sRing, currRing);
2524  strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
2525  rDelete (sRing);
2526  }
2527  id_DelDiv(strat->Shdl, currRing);
2528  idSkipZeroes(strat->Shdl);
2529  idTest(strat->Shdl);
2530 
2531 #if SBA_PRINT_SIZE_G
2532  size_g = IDELEMS(strat->Shdl);
2533 #endif
2534 #ifdef DEBUGF5
2535  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
2536  int oo = 0;
2537  while (oo<IDELEMS(strat->Shdl))
2538  {
2539  printf(" %d. ",oo+1);
2540  pWrite(pHead(strat->Shdl->m[oo]));
2541  oo++;
2542  }
2543 #endif
2544 #if SBA_PRINT_ZERO_REDUCTIONS
2545  printf("----------------------------------------------------------\n");
2546  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
2547  zeroreductions = 0;
2548 #endif
2549 #if SBA_PRINT_REDUCTION_STEPS
2550  printf("----------------------------------------------------------\n");
2551  printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
2552 #endif
2553 #if SBA_PRINT_OPERATIONS
2554  printf("OPERATIONS: %ld\n",sba_operations);
2555 #endif
2556 #if SBA_PRINT_REDUCTION_STEPS
2557  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
2558  printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
2559 #endif
2560 #if SBA_PRINT_OPERATIONS
2561  printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
2562 #endif
2563 #if SBA_PRINT_REDUCTION_STEPS
2564  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
2565  printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
2566  sba_interreduction_steps = 0;
2567  sba_reduction_steps = 0;
2568 #endif
2569 #if SBA_PRINT_OPERATIONS
2570  printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
2571  sba_interreduction_operations = 0;
2572  sba_operations = 0;
2573 #endif
2574 #if SBA_PRINT_SIZE_G
2575  printf("----------------------------------------------------------\n");
2576  printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
2577  size_g = 0;
2578  size_g_non_red = 0;
2579 #endif
2580 #if SBA_PRINT_SIZE_SYZ
2581  printf("SIZE OF SYZ: %ld\n",size_syz);
2582  printf("----------------------------------------------------------\n");
2583  size_syz = 0;
2584 #endif
2585 #if SBA_PRINT_PRODUCT_CRITERION
2586  printf("PRODUCT CRITERIA: %ld\n",product_criterion);
2587  product_criterion = 0;
2588 #endif
2589  return (strat->Shdl);
2590 }
2591 
2592 poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
2593 {
2594  assume(q!=NULL);
2595  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
2596 
2597 // lazy_reduce flags: can be combined by |
2598 //#define KSTD_NF_LAZY 1
2599  // do only a reduction of the leading term
2600 //#define KSTD_NF_NONORM 4
2601  // only global: avoid normalization, return a multiply of NF
2602  poly p;
2603 
2604  //if ((idIs0(F))&&(Q==NULL))
2605  // return pCopy(q); /*F=0*/
2606  //strat->ak = idRankFreeModule(F);
2607  /*- creating temp data structures------------------- -*/
2608  BITSET save1;
2609  SI_SAVE_OPT1(save1);
2611  initBuchMoraCrit(strat);
2612  strat->initEcart = initEcartBBA;
2613  strat->enterS = enterSBba;
2614 #ifndef NO_BUCKETS
2616 #endif
2617  /*- set S -*/
2618  strat->sl = -1;
2619  /*- init local data struct.---------------------------------------- -*/
2620  /*Shdl=*/initS(F,Q,strat);
2621  /*- compute------------------------------------------------------- -*/
2622  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
2623  //{
2624  // for (i=strat->sl;i>=0;i--)
2625  // pNorm(strat->S[i]);
2626  //}
2627  kTest(strat);
2628  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2629  if (BVERBOSE(23)) kDebugPrint(strat);
2630  int max_ind;
2631  p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
2632  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2633  {
2634  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2635  #ifdef HAVE_RINGS
2636  if (rField_is_Ring(currRing))
2637  {
2638  p = redtailBba_Z(p,max_ind,strat);
2639  }
2640  else
2641  #endif
2642  {
2644  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
2645  }
2646  }
2647  /*- release temp data------------------------------- -*/
2648  assume(strat->L==NULL); /* strat->L unused */
2649  assume(strat->B==NULL); /* strat->B unused */
2650  omFree(strat->sevS);
2651  omFree(strat->ecartS);
2652  assume(strat->T==NULL);//omfree(strat->T);
2653  assume(strat->sevT==NULL);//omfree(strat->sevT);
2654  assume(strat->R==NULL);//omfree(strat->R);
2655  omfree(strat->S_2_R);
2656  omfree(strat->fromQ);
2657  idDelete(&strat->Shdl);
2658  SI_RESTORE_OPT1(save1);
2659  if (TEST_OPT_PROT) PrintLn();
2660  return p;
2661 }
2662 
2663 ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
2664 {
2665  assume(!idIs0(q));
2666  assume(!(idIs0(F)&&(Q==NULL)));
2667 // lazy_reduce flags: can be combined by |
2668 //#define KSTD_NF_LAZY 1
2669  // do only a reduction of the leading term
2670 //#define KSTD_NF_NONORM 4
2671  // only global: avoid normalization, return a multiply of NF
2672  poly p;
2673  int i;
2674  ideal res;
2675  int max_ind;
2676 
2677  //if (idIs0(q))
2678  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2679  //if ((idIs0(F))&&(Q==NULL))
2680  // return idCopy(q); /*F=0*/
2681  //strat->ak = idRankFreeModule(F);
2682  /*- creating temp data structures------------------- -*/
2683  BITSET save1;
2684  SI_SAVE_OPT1(save1);
2686  initBuchMoraCrit(strat);
2687  strat->initEcart = initEcartBBA;
2688  strat->enterS = enterSBba;
2689  /*- set S -*/
2690  strat->sl = -1;
2691 #ifndef NO_BUCKETS
2693 #endif
2694  /*- init local data struct.---------------------------------------- -*/
2695  /*Shdl=*/initS(F,Q,strat);
2696  /*- compute------------------------------------------------------- -*/
2697  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
2699  for (i=IDELEMS(q)-1; i>=0; i--)
2700  {
2701  if (q->m[i]!=NULL)
2702  {
2703  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
2704  p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
2705  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2706  {
2707  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2708  #ifdef HAVE_RINGS
2709  if (rField_is_Ring(currRing))
2710  {
2711  p = redtailBba_Z(p,max_ind,strat);
2712  }
2713  else
2714  #endif
2715  {
2716  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
2717  }
2718  }
2719  res->m[i]=p;
2720  }
2721  //else
2722  // res->m[i]=NULL;
2723  }
2724  /*- release temp data------------------------------- -*/
2725  assume(strat->L==NULL); /* strat->L unused */
2726  assume(strat->B==NULL); /* strat->B unused */
2727  omFree(strat->sevS);
2728  omFree(strat->ecartS);
2729  assume(strat->T==NULL);//omfree(strat->T);
2730  assume(strat->sevT==NULL);//omfree(strat->sevT);
2731  assume(strat->R==NULL);//omfree(strat->R);
2732  omfree(strat->S_2_R);
2733  omfree(strat->fromQ);
2734  idDelete(&strat->Shdl);
2735  SI_RESTORE_OPT1(save1);
2736  if (TEST_OPT_PROT) PrintLn();
2737  return res;
2738 }
2739 
2740 #if F5C
2741 /*********************************************************************
2742 * interrreduction step of the signature-based algorithm:
2743 * 1. all strat->S are interpreted as new critical pairs
2744 * 2. those pairs need to be completely reduced by the usual (non sig-
2745 * safe) reduction process (including tail reductions)
2746 * 3. strat->S and strat->T are completely new computed in these steps
2747 ********************************************************************/
2748 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
2749  int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
2750  intvec *w,intvec *hilb )
2751 {
2752  int Ll_old, red_result = 1;
2753  int pos = 0;
2754  hilbeledeg=1;
2755  hilbcount=0;
2756  minimcnt=0;
2757  srmax = 0; // strat->sl is 0 at this point
2758  reduc = olddeg = lrmax = 0;
2759  // we cannot use strat->T anymore
2760  //cleanT(strat);
2761  //strat->tl = -1;
2762  Ll_old = strat->Ll;
2763  while (strat->tl >= 0)
2764  {
2765  if(!strat->T[strat->tl].is_redundant)
2766  {
2767  LObject h;
2768  h.p = strat->T[strat->tl].p;
2769  h.tailRing = strat->T[strat->tl].tailRing;
2770  h.t_p = strat->T[strat->tl].t_p;
2771  if (h.p!=NULL)
2772  {
2773  if (currRing->OrdSgn==-1)
2774  {
2775  cancelunit(&h);
2776  deleteHC(&h, strat);
2777  }
2778  if (h.p!=NULL)
2779  {
2781  {
2782  //pContent(h.p);
2783  h.pCleardenom(); // also does a pContent
2784  }
2785  else
2786  {
2787  h.pNorm();
2788  }
2789  strat->initEcart(&h);
2790  pos = strat->Ll+1;
2791  h.sev = pGetShortExpVector(h.p);
2792  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
2793  }
2794  }
2795  }
2796  strat->tl--;
2797  }
2798  strat->sl = -1;
2799 #if 0
2800 //#ifdef HAVE_TAIL_RING
2801  if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2802  kStratInitChangeTailRing(strat);
2803 #endif
2804  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
2805  //strat->sl = -1;
2806  /* picks the last element from the lazyset L */
2807  while (strat->Ll>Ll_old)
2808  {
2809  strat->P = strat->L[strat->Ll];
2810  strat->Ll--;
2811 //#if 1
2812 #ifdef DEBUGF5
2813  Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
2814  Print("-------------------------------------------------\n");
2815  pWrite(pHead(strat->P.p));
2816  pWrite(pHead(strat->P.p1));
2817  pWrite(pHead(strat->P.p2));
2818  printf("%d\n",strat->tl);
2819  Print("-------------------------------------------------\n");
2820 #endif
2821  if (pNext(strat->P.p) == strat->tail)
2822  {
2823  // deletes the short spoly
2824 #ifdef HAVE_RINGS
2825  if (rField_is_Ring(currRing))
2826  pLmDelete(strat->P.p);
2827  else
2828 #endif
2829  pLmFree(strat->P.p);
2830 
2831  // TODO: needs some masking
2832  // TODO: masking needs to vanish once the signature
2833  // sutff is completely implemented
2834  strat->P.p = NULL;
2835  poly m1 = NULL, m2 = NULL;
2836 
2837  // check that spoly creation is ok
2838  while (strat->tailRing != currRing &&
2839  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2840  {
2841  assume(m1 == NULL && m2 == NULL);
2842  // if not, change to a ring where exponents are at least
2843  // large enough
2844  if (!kStratChangeTailRing(strat))
2845  {
2846  WerrorS("OVERFLOW...");
2847  break;
2848  }
2849  }
2850  // create the real one
2851  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2852  strat->tailRing, m1, m2, strat->R);
2853  }
2854  else if (strat->P.p1 == NULL)
2855  {
2856  if (strat->minim > 0)
2857  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2858  // for input polys, prepare reduction
2859  strat->P.PrepareRed(strat->use_buckets);
2860  }
2861 
2862  if (strat->P.p == NULL && strat->P.t_p == NULL)
2863  {
2864  red_result = 0;
2865  }
2866  else
2867  {
2868  if (TEST_OPT_PROT)
2869  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2870  &olddeg,&reduc,strat, red_result);
2871 
2872 #ifdef DEBUGF5
2873  Print("Poly before red: ");
2874  pWrite(strat->P.p);
2875 #endif
2876  /* complete reduction of the element chosen from L */
2877  red_result = strat->red2(&strat->P,strat);
2878  if (errorreported) break;
2879  }
2880 
2881  if (strat->overflow)
2882  {
2883  if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
2884  }
2885 
2886  // reduction to non-zero new poly
2887  if (red_result == 1)
2888  {
2889  // get the polynomial (canonicalize bucket, make sure P.p is set)
2890  strat->P.GetP(strat->lmBin);
2891  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2892  // but now, for entering S, T, we reset it
2893  // in the inhomogeneous case: FDeg == pFDeg
2894  if (strat->homog) strat->initEcart(&(strat->P));
2895 
2896  /* statistic */
2897  if (TEST_OPT_PROT) PrintS("s");
2898 
2899  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2900 
2901 #ifdef KDEBUG
2902 #if MYTEST
2903  PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
2904 #endif /* MYTEST */
2905 #endif /* KDEBUG */
2906 
2907  // reduce the tail and normalize poly
2908  // in the ring case we cannot expect LC(f) = 1,
2909  // therefore we call pContent instead of pNorm
2910 #if F5CTAILRED
2911  BOOLEAN withT = TRUE;
2913  {
2914  strat->P.pCleardenom();
2916  {
2917  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2918  strat->P.pCleardenom();
2919  }
2920  }
2921  else
2922  {
2923  strat->P.pNorm();
2925  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2926  }
2927 #endif
2928 #ifdef KDEBUG
2929  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2930 #if MYTEST
2931 //#if 1
2932  PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
2933 #endif /* MYTEST */
2934 #endif /* KDEBUG */
2935 
2936  // min_std stuff
2937  if ((strat->P.p1==NULL) && (strat->minim>0))
2938  {
2939  if (strat->minim==1)
2940  {
2941  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2942  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2943  }
2944  else
2945  {
2946  strat->M->m[minimcnt]=strat->P.p2;
2947  strat->P.p2=NULL;
2948  }
2949  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2950  pNext(strat->M->m[minimcnt])
2951  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2952  strat->tailRing, currRing,
2953  currRing->PolyBin);
2954  minimcnt++;
2955  }
2956 
2957  // enter into S, L, and T
2958  // here we need to recompute new signatures, but those are trivial ones
2959  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2960  {
2961  enterT(strat->P, strat);
2962  // posInS only depends on the leading term
2963  strat->enterS(strat->P, pos, strat, strat->tl);
2964 //#if 1
2965 #ifdef DEBUGF5
2966  Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
2967  pWrite(pHead(strat->S[strat->sl]));
2968  pWrite(strat->sig[strat->sl]);
2969 #endif
2970  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2971  }
2972  // Print("[%d]",hilbeledeg);
2973  if (strat->P.lcm!=NULL)
2974 #ifdef HAVE_RINGS
2975  pLmDelete(strat->P.lcm);
2976 #else
2977  pLmFree(strat->P.lcm);
2978 #endif
2979  if (strat->sl>srmax) srmax = strat->sl;
2980  }
2981  else
2982  {
2983  // adds signature of the zero reduction to
2984  // strat->syz. This is the leading term of
2985  // syzygy and can be used in syzCriterion()
2986  // the signature is added if and only if the
2987  // pair was not detected by the rewritten criterion in strat->red = redSig
2988  if (strat->P.p1 == NULL && strat->minim > 0)
2989  {
2990  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2991  }
2992  }
2993 
2994 #ifdef KDEBUG
2995  memset(&(strat->P), 0, sizeof(strat->P));
2996 #endif /* KDEBUG */
2997  }
2998  int cc = 0;
2999  while (cc<strat->tl+1)
3000  {
3001  strat->T[cc].sig = pOne();
3002  p_SetComp(strat->T[cc].sig,cc+1,currRing);
3003  strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
3004  strat->sig[cc] = strat->T[cc].sig;
3005  strat->sevSig[cc] = strat->T[cc].sevSig;
3006  strat->T[cc].is_sigsafe = TRUE;
3007  cc++;
3008  }
3009  strat->max_lower_index = strat->tl;
3010  // set current signature index of upcoming iteration step
3011  // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
3012  // the corresponding syzygy rules correctly
3013  strat->currIdx = cc+1;
3014  for (int cd=strat->Ll; cd>=0; cd--)
3015  {
3016  p_SetComp(strat->L[cd].sig,cc+1,currRing);
3017  cc++;
3018  }
3019  for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
3020  strat->Shdl->m[cc] = NULL;
3021 //#if 1
3022 #if DEBUGF5
3023  Print("------------------- STRAT S ---------------------\n");
3024  cc = 0;
3025  while (cc<strat->tl+1)
3026  {
3027  pWrite(pHead(strat->S[cc]));
3028  pWrite(strat->sig[cc]);
3029  printf("- - - - - -\n");
3030  cc++;
3031  }
3032  Print("-------------------------------------------------\n");
3033  Print("------------------- STRAT T ---------------------\n");
3034  cc = 0;
3035  while (cc<strat->tl+1)
3036  {
3037  pWrite(pHead(strat->T[cc].p));
3038  pWrite(strat->T[cc].sig);
3039  printf("- - - - - -\n");
3040  cc++;
3041  }
3042  Print("-------------------------------------------------\n");
3043  Print("------------------- STRAT L ---------------------\n");
3044  cc = 0;
3045  while (cc<strat->Ll+1)
3046  {
3047  pWrite(pHead(strat->L[cc].p));
3048  pWrite(pHead(strat->L[cc].p1));
3049  pWrite(pHead(strat->L[cc].p2));
3050  pWrite(strat->L[cc].sig);
3051  printf("- - - - - -\n");
3052  cc++;
3053  }
3054  Print("-------------------------------------------------\n");
3055  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
3056 #endif
3057 
3058 }
3059 #endif
3060 
3061 /* shiftgb stuff */
3062 #ifdef HAVE_SHIFTBBA
3063 
3064 
3065 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV)
3066 {
3067  int red_result = 1;
3068  int olddeg,reduc;
3069  int hilbeledeg=1,hilbcount=0,minimcnt=0;
3070  BOOLEAN withT = TRUE; // very important for shifts
3071 
3072  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit, NO CHANGES */
3073  initBuchMoraPos(strat); /*NO CHANGES YET: perhaps later*/
3074  initHilbCrit(F,Q,&hilb,strat); /*NO CHANGES*/
3075  initBbaShift(F,strat); /* DONE */
3076  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3077  /*Shdl=*/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
3078  updateSShift(strat,uptodeg,lV); /* initializes T */
3079 
3080  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
3081  reduc = olddeg = 0;
3082  strat->lV=lV;
3083 
3084 #ifndef NO_BUCKETS
3085  if (!TEST_OPT_NOT_BUCKETS)
3086  strat->use_buckets = 1;
3087 #endif
3088 
3089  // redtailBBa against T for inhomogenous input
3090  // if (!TEST_OPT_OLDSTD)
3091  // withT = ! strat->homog;
3092 
3093  // strat->posInT = posInT_pLength;
3094  kTest_TS(strat);
3095 
3096 #ifdef HAVE_TAIL_RING
3097  kStratInitChangeTailRing(strat);
3098 #endif
3099 
3100  /* compute------------------------------------------------------- */
3101  while (strat->Ll >= 0)
3102  {
3103 #ifdef KDEBUG
3104  if (TEST_OPT_DEBUG) messageSets(strat);
3105 #endif
3106  if (strat->Ll== 0) strat->interpt=TRUE;
3107  if (TEST_OPT_DEGBOUND
3108  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3109  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
3110  {
3111  /*
3112  *stops computation if
3113  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
3114  *a predefined number Kstd1_deg
3115  */
3116  while ((strat->Ll >= 0)
3117  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
3118  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3119  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
3120  )
3121  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
3122  if (strat->Ll<0) break;
3123  else strat->noClearS=TRUE;
3124  }
3125  /* picks the last element from the lazyset L */
3126  strat->P = strat->L[strat->Ll];
3127  strat->Ll--;
3128 
3129  if (pNext(strat->P.p) == strat->tail)
3130  {
3131  // deletes the short spoly
3132  pLmFree(strat->P.p);
3133  strat->P.p = NULL;
3134  poly m1 = NULL, m2 = NULL;
3135 
3136  // check that spoly creation is ok
3137  while (strat->tailRing != currRing &&
3138  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3139  {
3140  assume(m1 == NULL && m2 == NULL);
3141  // if not, change to a ring where exponents are at least
3142  // large enough
3143  kStratChangeTailRing(strat);
3144  }
3145  // create the real one
3146  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3147  strat->tailRing, m1, m2, strat->R);
3148  }
3149  else if (strat->P.p1 == NULL)
3150  {
3151  if (strat->minim > 0)
3152  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3153  // for input polys, prepare reduction
3154  strat->P.PrepareRed(strat->use_buckets);
3155  }
3156 
3157  poly qq;
3158 
3159  /* here in the nonhomog case we shrink the new spoly */
3160 
3161  if ( ! strat->homog)
3162  {
3163  strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3164  /* in the nonhomog case we have to shrink the polynomial */
3165  assume(strat->P.t_p!=NULL);
3166  qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
3167  if (qq != NULL)
3168  {
3169  /* we're here if Shrink is nonzero */
3170  // strat->P.p = NULL;
3171  // strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3172  strat->P.p = NULL; // is not set by Delete
3173  strat->P.t_p = qq;
3174  strat->P.GetP(strat->lmBin);
3175  // update sev and length
3176  strat->initEcart(&(strat->P));
3177  strat->P.sev = pGetShortExpVector(strat->P.p);
3178 // strat->P.FDeg = strat->P.pFDeg();
3179 // strat->P.length = strat->P.pLDeg();
3180 // strat->P.pLength =strat->P.GetpLength(); //pLength(strat->P.p);
3181  }
3182  else
3183  {
3184  /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
3185 #ifdef KDEBUG
3186  if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3187 #endif
3188  // strat->P.Delete(); // cause error
3189  strat->P.p = NULL;
3190  strat->P.t_p = NULL;
3191  // strat->P.p = NULL; // or delete strat->P.p ?
3192  }
3193  }
3194  /* end shrinking poly in the nonhomog case */
3195 
3196  if (strat->P.p == NULL && strat->P.t_p == NULL)
3197  {
3198  red_result = 0;
3199  }
3200  else
3201  {
3202  if (TEST_OPT_PROT)
3203  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3204  &olddeg,&reduc,strat, red_result);
3205 
3206  /* reduction of the element chosen from L */
3207  red_result = strat->red(&strat->P,strat);
3208  }
3209 
3210  // reduction to non-zero new poly
3211  if (red_result == 1)
3212  {
3213  /* statistic */
3214  if (TEST_OPT_PROT) PrintS("s");
3215 
3216  // get the polynomial (canonicalize bucket, make sure P.p is set)
3217  strat->P.GetP(strat->lmBin);
3218 
3219  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3220 
3221  // reduce the tail and normalize poly
3223  {
3224  strat->P.pCleardenom();
3226  {
3227  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3228  strat->P.pCleardenom();
3229  }
3230  }
3231  else
3232  {
3233  strat->P.pNorm();
3235  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3236  }
3237 
3238  // here we must shrink again! and optionally reduce again
3239  // or build shrink into redtailBba!
3240 
3241 #ifdef KDEBUG
3242  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3243 #endif
3244 
3245  // min_std stuff
3246  if ((strat->P.p1==NULL) && (strat->minim>0))
3247  {
3248  if (strat->minim==1)
3249  {
3250  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3251  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3252  }
3253  else
3254  {
3255  strat->M->m[minimcnt]=strat->P.p2;
3256  strat->P.p2=NULL;
3257  }
3258  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3259  pNext(strat->M->m[minimcnt])
3260  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3261  strat->tailRing, currRing,
3262  currRing->PolyBin);
3263  minimcnt++;
3264  }
3265 
3266  /* here in the nonhomog case we shrink the reduced poly AGAIN */
3267 
3268  if ( ! strat->homog)
3269  {
3270  strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3271  /* assume strat->P.t_p != NULL */
3272  /* in the nonhomog case we have to shrink the polynomial */
3273  assume(strat->P.t_p!=NULL); // poly qq defined above
3274  qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
3275  if (qq != NULL)
3276  {
3277  /* we're here if Shrink is nonzero */
3278  // strat->P.p = NULL;
3279  // strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3280  strat->P.p = NULL; // is not set by Delete
3281  strat->P.t_p = qq;
3282  strat->P.GetP(strat->lmBin);
3283  // update sev and length
3284  strat->initEcart(&(strat->P));
3285  strat->P.sev = pGetShortExpVector(strat->P.p);
3286  }
3287  else
3288  {
3289  /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
3290 #ifdef PDEBUG
3291  if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3292 #endif
3293  // strat->P.Delete(); // cause error
3294  strat->P.p = NULL;
3295  strat->P.t_p = NULL;
3296  // strat->P.p = NULL; // or delete strat->P.p ?
3297  goto red_shrink2zero;
3298  }
3299  }
3300  /* end shrinking poly AGAIN in the nonhomog case */
3301 
3302 
3303  // enter into S, L, and T
3304  //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3305  // enterT(strat->P, strat); // this was here before Shift stuff
3306  //enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax
3307  // the default value for atT = -1 as in bba
3308  /* strat->P.GetP(); */
3309  // because shifts are counted with .p structure // done before, but ?
3310  enterTShift(strat->P,strat,-1,uptodeg, lV);
3311  enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3312  // enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3313  // posInS only depends on the leading term
3314  strat->enterS(strat->P, pos, strat, strat->tl);
3315 
3316  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3317 // Print("[%d]",hilbeledeg);
3318  if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
3319  }
3320  else
3321  {
3322  red_shrink2zero:
3323  if (strat->P.p1 == NULL && strat->minim > 0)
3324  {
3325  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3326  }
3327  }
3328 #ifdef KDEBUG
3329  memset(&(strat->P), 0, sizeof(strat->P));
3330 #endif
3331  kTest_TS(strat);
3332  }
3333 #ifdef KDEBUG
3334  if (TEST_OPT_DEBUG) messageSets(strat);
3335 #endif
3336  /* complete reduction of the standard basis--------- */
3337  /* shift case: look for elt's in S such that they are divisible by elt in T */
3338  // if (TEST_OPT_SB_1)
3339  if (TEST_OPT_REDSB)
3340  {
3341  int k=0;
3342  int j=-1;
3343  while(k<=strat->sl)
3344  {
3345 // loop
3346 // {
3347 // if (j>=k) break;
3348 // clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3349 // j++;
3350 // }
3351  LObject Ln (strat->S[k],currRing, strat->tailRing);
3352  Ln.SetShortExpVector();
3353  j = kFindDivisibleByInT(strat, &Ln, j+1);
3354  if (j<0) { k++; j=-1;}
3355  else
3356  {
3357  if ( pLmCmp(strat->S[k],strat->T[j].p) == 0)
3358  {
3359  j = kFindDivisibleByInT(strat, &Ln, j+1);
3360  if (j<0) { k++; j=-1;}
3361  else
3362  {
3363  deleteInS(k,strat);
3364  }
3365  }
3366  else
3367  {
3368  deleteInS(k,strat);
3369  }
3370  }
3371  }
3372  }
3373 
3374  if (TEST_OPT_REDSB)
3375  { completeReduce(strat, TRUE); //shift: withT = TRUE
3376  if (strat->completeReduce_retry)
3377  {
3378  // completeReduce needed larger exponents, retry
3379  // to reduce with S (instead of T)
3380  // and in currRing (instead of strat->tailRing)
3381  cleanT(strat);strat->tailRing=currRing;
3382  int i;
3383  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3384  completeReduce(strat, TRUE);
3385  }
3386  }
3387  else if (TEST_OPT_PROT) PrintLn();
3388 
3389  /* release temp data-------------------------------- */
3390  exitBuchMora(strat);
3391 // if (TEST_OPT_WEIGHTM)
3392 // {
3393 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
3394 // if (ecartWeights)
3395 // {
3396 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3397 // ecartWeights=NULL;
3398 // }
3399 // }
3400  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
3401  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3402  return (strat->Shdl);
3403 }
3404 
3405 
3406 ideal freegb(ideal I, int uptodeg, int lVblock)
3407 {
3408  /* todo main call */
3409 
3410  /* assume: ring is prepared, ideal is copied into shifted ring */
3411  /* uptodeg and lVblock are correct - test them! */
3412 
3413  /* check whether the ideal is in V */
3414 
3415 // if (0)
3416  if (! ideal_isInV(I,lVblock) )
3417  {
3418  WerrorS("The input ideal contains incorrectly encoded elements! ");
3419  return(NULL);
3420  }
3421 
3422  // kStrategy strat = new skStrategy;
3423  /* ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV) */
3424  /* at the moment:
3425 - no quotient (check)
3426 - no *w, no *hilb
3427  */
3428  /* ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
3429  int newIdeal, intvec *vw) */
3430  ideal RS = kStdShift(I,NULL, testHomog, NULL,NULL,0,0,NULL, uptodeg, lVblock);
3431  //bbaShift(I,NULL, NULL, NULL, strat, uptodeg, lVblock);
3432  idSkipZeroes(RS);
3433  return(RS);
3434 }
3435 
3436 /*2
3437 *reduces h with elements from T choosing the first possible
3438 * element in t with respect to the given pDivisibleBy
3439 */
3441 {
3442  if (h->IsNull()) return 0;
3443 
3444  int at, reddeg,d;
3445  int pass = 0;
3446  int j = 0;
3447 
3448  if (! strat->homog)
3449  {
3450  d = h->GetpFDeg() + h->ecart;
3451  reddeg = strat->LazyDegree+d;
3452  }
3453  h->SetShortExpVector();
3454  loop
3455  {
3456  j = kFindDivisibleByInT(strat, h);
3457  if (j < 0)
3458  {
3459  h->SetDegStuffReturnLDeg(strat->LDegLast);
3460  return 1;
3461  }
3462 
3463  if (!TEST_OPT_INTSTRATEGY)
3464  strat->T[j].pNorm();
3465 #ifdef KDEBUG
3466  if (TEST_OPT_DEBUG)
3467  {
3468  PrintS("reduce ");
3469  h->wrp();
3470  PrintS(" with ");
3471  strat->T[j].wrp();
3472  }
3473 #endif
3474  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
3475  if (!h->IsNull())
3476  {
3477  poly qq=p_Shrink(h->GetTP(),strat->lV,strat->tailRing);
3478  h->p=NULL;
3479  h->t_p=qq;
3480  if (qq!=NULL) h->GetP(strat->lmBin);
3481  }
3482 
3483 #ifdef KDEBUG
3484  if (TEST_OPT_DEBUG)
3485  {
3486  PrintS(" to ");
3487  wrp(h->p);
3488  PrintLn();
3489  }
3490 #endif
3491  if (h->IsNull())
3492  {
3493  if (h->lcm!=NULL) pLmFree(h->lcm);
3494  h->Clear();
3495  return 0;
3496  }
3497  h->SetShortExpVector();
3498 
3499 #if 0
3500  if ((strat->syzComp!=0) && !strat->honey)
3501  {
3502  if ((strat->syzComp>0) &&
3503  (h->Comp() > strat->syzComp))
3504  {
3505  assume(h->MinComp() > strat->syzComp);
3506 #ifdef KDEBUG
3507  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
3508 #endif
3509  if (strat->homog)
3510  h->SetDegStuffReturnLDeg(strat->LDegLast);
3511  return -2;
3512  }
3513  }
3514 #endif
3515  if (!strat->homog)
3516  {
3517  if (!TEST_OPT_OLDSTD && strat->honey)
3518  {
3519  h->SetpFDeg();
3520  if (strat->T[j].ecart <= h->ecart)
3521  h->ecart = d - h->GetpFDeg();
3522  else
3523  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
3524 
3525  d = h->GetpFDeg() + h->ecart;
3526  }
3527  else
3528  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
3529  /*- try to reduce the s-polynomial -*/
3530  pass++;
3531  /*
3532  *test whether the polynomial should go to the lazyset L
3533  *-if the degree jumps
3534  *-if the number of pre-defined reductions jumps
3535  */
3536  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
3537  && ((d >= reddeg) || (pass > strat->LazyPass)))
3538  {
3539  h->SetLmCurrRing();
3540  if (strat->posInLDependsOnLength)
3541  h->SetLength(strat->length_pLength);
3542  at = strat->posInL(strat->L,strat->Ll,h,strat);
3543  if (at <= strat->Ll)
3544  {
3545  //int dummy=strat->sl;
3546  /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
3547  //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
3548  if (kFindDivisibleByInT(strat, h) < 0)
3549  return 1;
3550  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
3551 #ifdef KDEBUG
3552  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
3553 #endif
3554  h->Clear();
3555  return -1;
3556  }
3557  }
3558  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
3559  {
3560  reddeg = d+1;
3561  Print(".%d",d);mflush();
3562  }
3563  }
3564  }
3565 }
3566 
3567 void initBbaShift(ideal /*F*/,kStrategy strat)
3568 {
3569  /* setting global variables ------------------- */
3570  strat->enterS = enterSBba; /* remains as is, we change enterT! */
3571 
3572  strat->red = redFirstShift; /* no redHomog ! */
3573 
3574  if (currRing->pLexOrder && strat->honey)
3575  strat->initEcart = initEcartNormal;
3576  else
3577  strat->initEcart = initEcartBBA;
3578  if (strat->honey)
3580  else
3582 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
3583 // {
3584 // //interred machen Aenderung
3585 // pFDegOld=currRing->pFDeg;
3586 // pLDegOld=pLDeg;
3587 // //h=ggetid("ecart");
3588 // //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
3589 // //{
3590 // // ecartWeights=iv2array(IDINTVEC(h));
3591 // //}
3592 // //else
3593 // {
3594 // ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
3595 // /*uses automatic computation of the ecartWeights to set them*/
3596 // kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights,currRing);
3597 // }
3598 // pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
3599 // if (TEST_OPT_PROT)
3600 // {
3601 // for(int i=1; i<=rVar(currRing); i++)
3602 // Print(" %d",ecartWeights[i]);
3603 // PrintLn();
3604 // mflush();
3605 // }
3606 // }
3607 }
3608 #endif
unsigned long * sevSig
Definition: kutil.h:320
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1154
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:499
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:250
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:185
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:8437
void p_DebugPrint(poly p, const ring r)
Definition: ring.cc:4240
BOOLEAN honey
Definition: kutil.h:367
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:409
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1028
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:471
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:322
#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:721
#define TEST_OPT_DEGBOUND
Definition: options.h:108
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
Definition: kInline.h:1127
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:8244
int syzmax
Definition: kutil.h:347
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:6278
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
class sLObject LObject
Definition: kutil.h:60
#define nNormalize(n)
Definition: numbers.h:30
BOOLEAN length_pLength
Definition: kutil.h:377
TObject * TSet
Definition: kutil.h:61
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:6319
#define TEST_OPT_PROT
Definition: options.h:98
loop
Definition: myNF.cc:98
int Ll
Definition: kutil.h:349
#define pSetExp(p, i, v)
Definition: polys.h:42
#define FALSE
Definition: auxiliary.h:140
BOOLEAN noTailReduction
Definition: kutil.h:368
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:1061
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8338
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:973
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1448
#define pAssume(cond)
Definition: monomials.h:98
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p
Definition: polys.h:105
int ideal_isInV(ideal I, int lV)
Definition: shiftgb.cc:445
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:236
#define p_GetComp(p, r)
Definition: monomials.h:72
char newt
Definition: kutil.h:391
BEGIN_NAMESPACE_SINGULARXX const ring const ring tailRing
Definition: DebugPrint.h:30
BOOLEAN posInLDependsOnLength
Definition: kutil.h:379
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_Z(const coeffs r)
Definition: coeffs.h:750
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:484
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1443
#define pNeg(p)
Definition: polys.h:169
void initSyzRules(kStrategy strat)
Definition: kutil.cc:6737
int & max_ind
Definition: myNF.cc:67
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:3988
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
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:445
char noClearS
Definition: kutil.h:392
#define TRUE
Definition: auxiliary.h:144
#define nIsOne(n)
Definition: numbers.h:25
#define TEST_OPT_REDSB
Definition: options.h:99
int length() const
Definition: intvec.h:86
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:38
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:946
#define kTest(A)
Definition: kutil.h:619
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:9491
#define SI_SAVE_OPT1(A)
Definition: options.h:20
void pWrite(poly p)
Definition: polys.h:279
int ak
Definition: kutil.h:351
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:324
void WerrorS(const char *s)
Definition: feFopen.cc:23
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:8535
#define TEST_OPT_DEBUG
Definition: options.h:103
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1115
#define Q
Definition: sirandom.c:25
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:677
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:1466
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
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red)
Definition: kstd2.cc:641
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:1872
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR, int uptodeg, int lV)
Definition: kutil.cc:10696
#define BITSET
Definition: structs.h:17
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:274
#define omAlloc(size)
Definition: omAllocDecl.h:210
static bool rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:361
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:518
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1120
#define KINLINE
Definition: kutil.h:51
kBucket_pt kBucketCreate(ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:197
#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
intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:184
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4044
#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:1456
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:175
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:3440
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:811
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:1320
void rDebugPrint(ring r)
Definition: ring.cc:4035
char completeReduce_retry
Definition: kutil.h:393
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:9464
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:100
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:7811
#define mflush()
Definition: reporter.h:55
BOOLEAN is_ring
Definition: myNF.cc:83
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1116
#define pIter(p)
Definition: monomials.h:44
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1053
void updateSShift(kStrategy strat, int uptodeg, int lV)
Definition: kutil.cc:10152
poly res
Definition: myNF.cc:322
BOOLEAN interpt
Definition: kutil.h:361
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:2562
poly p_Shrink(poly p, int lV, const ring r)
Definition: shiftgb.cc:510
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:12
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:956
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:6383
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:2592
void enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV)
Definition: kutil.cc:10803
int lV
Definition: kutil.h:358
#define idPrint(id)
Definition: ideals.h:62
BOOLEAN fromT
Definition: kutil.h:369
const ring r
Definition: syzextra.cc:208
#define KSTD_NF_LAZY
Definition: kstd1.h:17
BOOLEAN homog
Definition: kutil.h:362
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:204
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1161
#define TEST_OPT_INTSTRATEGY
Definition: options.h:105
Definition: intvec.h:16
#define kTest_TS(A)
Definition: kutil.h:620
poly p_One(const ring r)
Definition: p_polys.cc:1318
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:465
#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:8072
#define TEST_OPT_OLDSTD
Definition: options.h:117
#define assume(x)
Definition: mod2.h:405
intset fromQ
Definition: kutil.h:317
#define messageSets(s)
Definition: kutil.h:508
void initBba(ideal, kStrategy strat)
Definition: kstd1.cc:1388
LObject * LSet
Definition: kutil.h:62
#define pSetExpV(p, e)
Definition: polys.h:97
void initEcartBBA(TObject *h)
Definition: kutil.cc:1147
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl.cc )
Definition: polys.h:140
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition: coeffs.h:771
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:1710
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3277
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:379
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:202
#define kTest_L(T)
Definition: kutil.h:623
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:1472
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:9361
LObject P
Definition: kutil.h:298
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:8092
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:166
void exitSba(kStrategy strat)
Definition: kutil.cc:8614
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
poly tail
Definition: kutil.h:332
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:235
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1339
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:2748
#define pOne()
Definition: polys.h:286
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:1676
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:3406
void initBuchMoraShift(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10180
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:295
short errorreported
Definition: feFopen.cc:22
#define help
Definition: libparse.cc:1228
void rChangeCurrRing(ring r)
Definition: polys.cc:14
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:8994
#define OPT_INTSTRATEGY
Definition: options.h:87
#define BVERBOSE(a)
Definition: options.h:33
kStrategy strat
Definition: myNF.cc:319
#define REDTAIL_CANONICALIZE
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:850
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:4559
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:484
s_poly_proc_t s_poly
Definition: kutil.h:296
LSet L
Definition: kutil.h:323
BOOLEAN LDegLast
Definition: kutil.h:375
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:9225
#define nIsZero(n)
Definition: numbers.h:19
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:437
#define NULL
Definition: omList.c:10
#define TEST_OPT_IDLIFT
Definition: options.h:123
void cleanT(kStrategy strat)
Definition: kutil.cc:505
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3540
LSet B
Definition: kutil.h:324
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:3904
int Lmax
Definition: kutil.h:349
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
long ind_fact_2(long arg)
Definition: kutil.cc:3351
void initBbaShift(ideal, kStrategy strat)
Definition: kstd2.cc:3567
int posInSyz(const kStrategy strat, poly sig)
Definition: kutil.cc:5045
ring tailRing
Definition: kutil.h:341
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:334
#define TEST_OPT_SB_1
Definition: options.h:113
CFList tmp1
Definition: facFqBivar.cc:70
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:8159
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:4201
char overflow
Definition: kutil.h:394
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:3065
#define nCopy(n)
Definition: numbers.h:15
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:8801
#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:436
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:8648
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:1145
int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kstd2.cc:98
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:3339
BOOLEAN use_buckets
Definition: kutil.h:373
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
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:104
int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd2.cc:99
void initEcartNormal(TObject *h)
Definition: kutil.cc:1139
void wrp(poly p)
Definition: polys.h:281
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:884
int Kstd1_deg
Definition: kutil.cc:228
#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:9294
ideal Shdl
Definition: kutil.h:299
#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:845
int BOOLEAN
Definition: auxiliary.h:131
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
#define pSize(p)
Definition: polys.h:289
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:1302
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1025
char redTailChange
Definition: kutil.h:389
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:8419
void Werror(const char *fmt,...)
Definition: reporter.cc:199
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
int syzl
Definition: kutil.h:347
int LazyDegree
Definition: kutil.h:351
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:9907
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:8007
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:7577
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
#define idTest(id)
Definition: ideals.h:63