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