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