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