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