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  }
1036  #if 0 // red is redLiftstd if OPT_IDLIFT
1038  {
1039  if (h->p!=NULL)
1040  {
1041  if(p_GetComp(h->p,currRing)>strat->syzComp)
1042  {
1043  h->Delete();
1044  return 0;
1045  }
1046  }
1047  else if (h->t_p!=NULL)
1048  {
1049  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1050  {
1051  h->Delete();
1052  return 0;
1053  }
1054  }
1055  }
1056  #endif
1057  #if 0
1058  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1059  {
1060  if (h->p!=NULL)
1061  {
1062  if(p_GetComp(h->p,currRing)>strat->syzComp)
1063  {
1064  return 1;
1065  }
1066  }
1067  else if (h->t_p!=NULL)
1068  {
1069  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1070  {
1071  return 1;
1072  }
1073  }
1074  }
1075  #endif
1076  h->SetShortExpVector();
1077  /*
1078  * try to reduce the s-polynomial h
1079  *test first whether h should go to the lazyset L
1080  *-if the degree jumps
1081  *-if the number of pre-defined reductions jumps
1082  */
1083  cnt--;
1084  pass++;
1085  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1086  {
1087  h->SetLmCurrRing();
1088  at = strat->posInL(strat->L,strat->Ll,h,strat);
1089  if (at <= strat->Ll)
1090  {
1091 #ifdef HAVE_SHIFTBBA
1092  if (rIsLPRing(currRing))
1093  {
1094  if (kFindDivisibleByInT(strat, h) < 0)
1095  return 1;
1096  }
1097  else
1098 #endif
1099  {
1100  int dummy=strat->sl;
1101  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1102  return 1;
1103  }
1104  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1105 #ifdef KDEBUG
1106  if (TEST_OPT_DEBUG)
1107  Print(" lazy: -> L%d\n",at);
1108 #endif
1109  h->Clear();
1110  return -1;
1111  }
1112  }
1113  else if (UNLIKELY(cnt==0))
1114  {
1115  h->CanonicalizeP();
1116  cnt=RED_CANONICALIZE;
1117  //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1118  }
1119  }
1120 }
1121 
1123 {
1124  BOOLEAN ret;
1125  number coef;
1126  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1127  if(!rField_is_Ring(currRing))
1128  Red->HeadNormalize();
1129  /*
1130  printf("------------------------\n");
1131  pWrite(Red->GetLmCurrRing());
1132  */
1134  ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1135  else
1136  ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1137  if (!ret)
1138  {
1139  if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1140  {
1141  PR->Mult_nn(coef);
1142  // HANNES: mark for Normalize
1143  }
1144  n_Delete(&coef, currRing->cf);
1145  }
1146  return ret;
1147 }
1148 
1149 /*2
1150 * reduction procedure for signature-based standard
1151 * basis algorithms:
1152 * all reductions have to be sig-safe!
1153 *
1154 * 2 is returned if and only if the pair is rejected by the rewritten criterion
1155 * at exactly this point of the computations. This is the last possible point
1156 * such a check can be done => checks with the biggest set of available
1157 * signatures
1158 */
1159 
1161 {
1162  if (strat->tl<0) return 1;
1163  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1164  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1165  assume(h->FDeg == h->pFDeg());
1166 //#if 1
1167 #ifdef DEBUGF5
1168  PrintS("------- IN REDSIG -------\n");
1169  Print("p: ");
1170  pWrite(pHead(h->p));
1171  PrintS("p1: ");
1172  pWrite(pHead(h->p1));
1173  PrintS("p2: ");
1174  pWrite(pHead(h->p2));
1175  PrintS("---------------------------\n");
1176 #endif
1177  poly h_p;
1178  int i,j,at,pass, ii;
1179  int start=0;
1180  int sigSafe;
1181  unsigned long not_sev;
1182  // long reddeg,d;
1183  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1184  int li;
1185 
1186  pass = j = 0;
1187  // d = reddeg = h->GetpFDeg();
1188  h->SetShortExpVector();
1189  h_p = h->GetLmTailRing();
1190  not_sev = ~ h->sev;
1191  loop
1192  {
1193  j = kFindDivisibleByInT(strat, h, start);
1194  if (j < 0)
1195  {
1196  return 1;
1197  }
1198 
1199  li = strat->T[j].pLength;
1200  if (li<=0) li=strat->T[j].GetpLength();
1201  ii = j;
1202  /*
1203  * the polynomial to reduce with (up to the moment) is;
1204  * pi with length li
1205  */
1206  i = j;
1207 #if 1
1208  if (test_opt_length)
1209  loop
1210  {
1211  /*- search the shortest possible with respect to length -*/
1212  i++;
1213  if (i > strat->tl)
1214  break;
1215  if (li==1)
1216  break;
1217  if ((strat->T[i].pLength < li)
1218  &&
1219  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1220  h_p, not_sev, strat->tailRing))
1221  {
1222  /*
1223  * the polynomial to reduce with is now;
1224  */
1225  li = strat->T[i].pLength;
1226  if (li<=0) li=strat->T[i].GetpLength();
1227  ii = i;
1228  }
1229  }
1230  start = ii+1;
1231 #endif
1232 
1233  /*
1234  * end of search: have to reduce with pi
1235  */
1236 #ifdef KDEBUG
1237  if (TEST_OPT_DEBUG)
1238  {
1239  PrintS("red:");
1240  h->wrp();
1241  PrintS(" with ");
1242  strat->T[ii].wrp();
1243  }
1244 #endif
1245  assume(strat->fromT == FALSE);
1246 //#if 1
1247 #ifdef DEBUGF5
1248  Print("BEFORE REDUCTION WITH %d:\n",ii);
1249  PrintS("--------------------------------\n");
1250  pWrite(h->sig);
1251  pWrite(strat->T[ii].sig);
1252  pWrite(h->GetLmCurrRing());
1253  pWrite(pHead(h->p1));
1254  pWrite(pHead(h->p2));
1255  pWrite(pHead(strat->T[ii].p));
1256  PrintS("--------------------------------\n");
1257  printf("INDEX OF REDUCER T: %d\n",ii);
1258 #endif
1259  sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1260 #if SBA_PRINT_REDUCTION_STEPS
1261  if (sigSafe != 3)
1262  sba_reduction_steps++;
1263 #endif
1264 #if SBA_PRINT_OPERATIONS
1265  if (sigSafe != 3)
1266  sba_operations += pLength(strat->T[ii].p);
1267 #endif
1268  // if reduction has taken place, i.e. the reduction was sig-safe
1269  // otherwise start is already at the next position and the loop
1270  // searching reducers in T goes on from index start
1271 //#if 1
1272 #ifdef DEBUGF5
1273  Print("SigSAFE: %d\n",sigSafe);
1274 #endif
1275  if (sigSafe != 3)
1276  {
1277  // start the next search for reducers in T from the beginning
1278  start = 0;
1279 #ifdef KDEBUG
1280  if (TEST_OPT_DEBUG)
1281  {
1282  PrintS("\nto ");
1283  h->wrp();
1284  PrintLn();
1285  }
1286 #endif
1287 
1288  h_p = h->GetLmTailRing();
1289  if (h_p == NULL)
1290  {
1291  kDeleteLcm(h);
1292  return 0;
1293  }
1294  h->SetShortExpVector();
1295  not_sev = ~ h->sev;
1296  /*
1297  * try to reduce the s-polynomial h
1298  *test first whether h should go to the lazyset L
1299  *-if the degree jumps
1300  *-if the number of pre-defined reductions jumps
1301  */
1302  pass++;
1303  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1304  {
1305  h->SetLmCurrRing();
1306  at = strat->posInL(strat->L,strat->Ll,h,strat);
1307  if (at <= strat->Ll)
1308  {
1309  int dummy=strat->sl;
1310  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1311  {
1312  return 1;
1313  }
1314  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1315 #ifdef KDEBUG
1316  if (TEST_OPT_DEBUG)
1317  Print(" lazy: -> L%d\n",at);
1318 #endif
1319  h->Clear();
1320  return -1;
1321  }
1322  }
1323  }
1324  }
1325 }
1326 
1327 
1329 {
1330  //Since reduce is really bad for SBA we use the following idea:
1331  // We first check if we can build a gcd pair between h and S
1332  //where the sig remains the same and replace h by this gcd poly
1334  #if GCD_SBA
1335  while(sbaCheckGcdPair(h,strat))
1336  {
1337  h->sev = pGetShortExpVector(h->p);
1338  }
1339  #endif
1340  poly beforeredsig;
1341  beforeredsig = pCopy(h->sig);
1342 
1343  if (strat->tl<0) return 1;
1344  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1345  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1346  assume(h->FDeg == h->pFDeg());
1347 //#if 1
1348 #ifdef DEBUGF5
1349  Print("------- IN REDSIG -------\n");
1350  Print("p: ");
1351  pWrite(pHead(h->p));
1352  Print("p1: ");
1353  pWrite(pHead(h->p1));
1354  Print("p2: ");
1355  pWrite(pHead(h->p2));
1356  Print("---------------------------\n");
1357 #endif
1358  poly h_p;
1359  int i,j,at,pass, ii;
1360  int start=0;
1361  int sigSafe;
1362  unsigned long not_sev;
1363  // long reddeg,d;
1364  int li;
1365  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1366 
1367  pass = j = 0;
1368  // d = reddeg = h->GetpFDeg();
1369  h->SetShortExpVector();
1370  h_p = h->GetLmTailRing();
1371  not_sev = ~ h->sev;
1372  loop
1373  {
1374  j = kFindDivisibleByInT(strat, h, start);
1375  if (j < 0)
1376  {
1377  #if GCD_SBA
1378  while(sbaCheckGcdPair(h,strat))
1379  {
1380  h->sev = pGetShortExpVector(h->p);
1381  h->is_redundant = FALSE;
1382  start = 0;
1383  }
1384  #endif
1385  // over ZZ: cleanup coefficients by complete reduction with monomials
1386  postReduceByMonSig(h, strat);
1387  if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
1388  j = kFindDivisibleByInT(strat, h,start);
1389  if(j < 0)
1390  {
1391  if(strat->tl >= 0)
1392  h->i_r1 = strat->tl;
1393  else
1394  h->i_r1 = -1;
1395  if (h->GetLmTailRing() == NULL)
1396  {
1397  kDeleteLcm(h);
1398  h->Clear();
1399  return 0;
1400  }
1401  //Check for sigdrop after reduction
1402  if(pLtCmp(beforeredsig,h->sig) == 1)
1403  {
1404  strat->sigdrop = TRUE;
1405  //Reduce it as much as you can
1406  int red_result = redRing(h,strat);
1407  if(red_result == 0)
1408  {
1409  //It reduced to 0, cancel the sigdrop
1410  strat->sigdrop = FALSE;
1411  p_Delete(&h->sig,currRing);h->sig = NULL;
1412  return 0;
1413  }
1414  else
1415  {
1416  //strat->enterS(*h, strat->sl+1, strat, strat->tl);
1417  return 0;
1418  }
1419  }
1420  p_Delete(&beforeredsig,currRing);
1421  return 1;
1422  }
1423  }
1424 
1425  li = strat->T[j].pLength;
1426  if (li<=0) li=strat->T[j].GetpLength();
1427  ii = j;
1428  /*
1429  * the polynomial to reduce with (up to the moment) is;
1430  * pi with length li
1431  */
1432  i = j;
1433  if (test_opt_length)
1434  loop
1435  {
1436  /*- search the shortest possible with respect to length -*/
1437  i++;
1438  if (i > strat->tl)
1439  break;
1440  if (li==1)
1441  break;
1442  if ((strat->T[i].pLength < li)
1443  && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1444  && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1445  h_p, not_sev, strat->tailRing))
1446  {
1447  /*
1448  * the polynomial to reduce with is now;
1449  */
1450  li = strat->T[i].pLength;
1451  if (li<=0) li=strat->T[i].GetpLength();
1452  ii = i;
1453  }
1454  }
1455 
1456  start = ii+1;
1457 
1458  /*
1459  * end of search: have to reduce with pi
1460  */
1461 #ifdef KDEBUG
1462  if (TEST_OPT_DEBUG)
1463  {
1464  PrintS("red:");
1465  h->wrp();
1466  PrintS(" with ");
1467  strat->T[ii].wrp();
1468  }
1469 #endif
1470  assume(strat->fromT == FALSE);
1471 //#if 1
1472 #ifdef DEBUGF5
1473  Print("BEFORE REDUCTION WITH %d:\n",ii);
1474  Print("--------------------------------\n");
1475  pWrite(h->sig);
1476  pWrite(strat->T[ii].sig);
1477  pWrite(h->GetLmCurrRing());
1478  pWrite(pHead(h->p1));
1479  pWrite(pHead(h->p2));
1480  pWrite(pHead(strat->T[ii].p));
1481  Print("--------------------------------\n");
1482  printf("INDEX OF REDUCER T: %d\n",ii);
1483 #endif
1484  sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1485  if(h->p == NULL && h->sig == NULL)
1486  {
1487  //Trivial case catch
1488  strat->sigdrop = FALSE;
1489  }
1490  #if 0
1491  //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1492  //In some cases this proves to be very bad
1493  if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1494  {
1495  int red_result = redRing(h,strat);
1496  if(red_result == 0)
1497  {
1498  pDelete(&h->sig);h->sig = NULL;
1499  return 0;
1500  }
1501  else
1502  {
1503  strat->sigdrop = TRUE;
1504  return 1;
1505  }
1506  }
1507  #endif
1508  if(strat->sigdrop)
1509  return 1;
1510 #if SBA_PRINT_REDUCTION_STEPS
1511  if (sigSafe != 3)
1512  sba_reduction_steps++;
1513 #endif
1514 #if SBA_PRINT_OPERATIONS
1515  if (sigSafe != 3)
1516  sba_operations += pLength(strat->T[ii].p);
1517 #endif
1518  // if reduction has taken place, i.e. the reduction was sig-safe
1519  // otherwise start is already at the next position and the loop
1520  // searching reducers in T goes on from index start
1521 //#if 1
1522 #ifdef DEBUGF5
1523  Print("SigSAFE: %d\n",sigSafe);
1524 #endif
1525  if (sigSafe != 3)
1526  {
1527  // start the next search for reducers in T from the beginning
1528  start = 0;
1529 #ifdef KDEBUG
1530  if (TEST_OPT_DEBUG)
1531  {
1532  PrintS("\nto ");
1533  h->wrp();
1534  PrintLn();
1535  }
1536 #endif
1537 
1538  h_p = h->GetLmTailRing();
1539  if (h_p == NULL)
1540  {
1541  kDeleteLcm(h);
1542  return 0;
1543  }
1544  h->SetShortExpVector();
1545  not_sev = ~ h->sev;
1546  /*
1547  * try to reduce the s-polynomial h
1548  *test first whether h should go to the lazyset L
1549  *-if the degree jumps
1550  *-if the number of pre-defined reductions jumps
1551  */
1552  pass++;
1553  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1554  {
1555  h->SetLmCurrRing();
1556  at = strat->posInL(strat->L,strat->Ll,h,strat);
1557  if (at <= strat->Ll)
1558  {
1559  int dummy=strat->sl;
1560  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1561  {
1562  return 1;
1563  }
1564  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1565 #ifdef KDEBUG
1566  if (TEST_OPT_DEBUG)
1567  Print(" lazy: -> L%d\n",at);
1568 #endif
1569  h->Clear();
1570  return -1;
1571  }
1572  }
1573  }
1574  }
1575 }
1576 
1577 // tail reduction for SBA
1578 poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
1579 {
1580  strat->redTailChange=FALSE;
1581  if (strat->noTailReduction) return L->GetLmCurrRing();
1582  poly h, p;
1583  p = h = L->GetLmTailRing();
1584  if ((h==NULL) || (pNext(h)==NULL))
1585  return L->GetLmCurrRing();
1586 
1587  TObject* With;
1588  // placeholder in case strat->tl < 0
1589  TObject With_s(strat->tailRing);
1590 
1591  LObject Ln(pNext(h), strat->tailRing);
1592  Ln.sig = L->sig;
1593  Ln.sevSig = L->sevSig;
1594  Ln.pLength = L->GetpLength() - 1;
1595 
1596  pNext(h) = NULL;
1597  if (L->p != NULL) pNext(L->p) = NULL;
1598  L->pLength = 1;
1599 
1600  Ln.PrepareRed(strat->use_buckets);
1601 
1602  int cnt=REDTAIL_CANONICALIZE;
1603  while(!Ln.IsNull())
1604  {
1605  loop
1606  {
1607  if(rField_is_Ring(currRing) && strat->sigdrop)
1608  break;
1609  Ln.SetShortExpVector();
1610  if (withT)
1611  {
1612  int j;
1613  j = kFindDivisibleByInT(strat, &Ln);
1614  if (j < 0) break;
1615  With = &(strat->T[j]);
1616  }
1617  else
1618  {
1619  With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1620  if (With == NULL) break;
1621  }
1622  cnt--;
1623  if (cnt==0)
1624  {
1626  /*poly tmp=*/Ln.CanonicalizeP();
1628  {
1629  Ln.Normalize();
1630  //pNormalize(tmp);
1631  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1632  }
1633  }
1634  if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
1635  {
1636  With->pNorm();
1637  }
1638  strat->redTailChange=TRUE;
1639  int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1641  L->sig = Ln.sig;
1642  //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1643  // I delete it an then set Ln.sig. Hence L->sig is lost
1644 #if SBA_PRINT_REDUCTION_STEPS
1645  if (ret != 3)
1646  sba_reduction_steps++;
1647 #endif
1648 #if SBA_PRINT_OPERATIONS
1649  if (ret != 3)
1650  sba_operations += pLength(With->p);
1651 #endif
1652  if (ret)
1653  {
1654  // reducing the tail would violate the exp bound
1655  // set a flag and hope for a retry (in bba)
1656  strat->completeReduce_retry=TRUE;
1657  if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1658  do
1659  {
1660  pNext(h) = Ln.LmExtractAndIter();
1661  pIter(h);
1662  L->pLength++;
1663  } while (!Ln.IsNull());
1664  goto all_done;
1665  }
1666  if (Ln.IsNull()) goto all_done;
1667  if (! withT) With_s.Init(currRing);
1668  if(rField_is_Ring(currRing) && strat->sigdrop)
1669  {
1670  //Cannot break the loop here so easily
1671  break;
1672  }
1673  }
1674  pNext(h) = Ln.LmExtractAndIter();
1675  pIter(h);
1676  if(!rField_is_Ring(currRing))
1677  pNormalize(h);
1678  L->pLength++;
1679  }
1680  all_done:
1681  Ln.Delete();
1682  if (L->p != NULL) pNext(L->p) = pNext(p);
1683 
1684  if (strat->redTailChange)
1685  {
1686  L->length = 0;
1687  }
1688  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1689  //L->Normalize(); // HANNES: should have a test
1690  kTest_L(L,strat);
1691  return L->GetLmCurrRing();
1692 }
1693 
1694 /*2
1695 * reduction procedure for the inhomogeneous case
1696 * and not a degree-ordering
1697 */
1699 {
1700  if (strat->tl<0) return 1;
1701  int at,i,ii,li;
1702  int j = 0;
1703  int pass = 0;
1704  int cnt = RED_CANONICALIZE;
1705  assume(h->pFDeg() == h->FDeg);
1706  long reddeg = h->GetpFDeg();
1707  long d;
1708  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1709 
1710  h->SetShortExpVector();
1711  poly h_p = h->GetLmTailRing();
1712  h->PrepareRed(strat->use_buckets);
1713  loop
1714  {
1715  j = kFindDivisibleByInT(strat, h);
1716  if (j < 0) return 1;
1717 
1718  li = strat->T[j].pLength;
1719  ii = j;
1720  /*
1721  * the polynomial to reduce with (up to the moment) is;
1722  * pi with length li
1723  */
1724 
1725  i = j;
1726 #if 1
1727  if (test_opt_length)
1728  {
1729  if (li<=0) li=strat->T[j].GetpLength();
1730  if(li>2)
1731  {
1732  unsigned long not_sev = ~ h->sev;
1733  loop
1734  {
1735  /*- search the shortest possible with respect to length -*/
1736  i++;
1737  if (i > strat->tl)
1738  break;
1739  if ((strat->T[i].pLength < li)
1740  &&
1741  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1742  h_p, not_sev, strat->tailRing))
1743  {
1744  /*
1745  * the polynomial to reduce with is now;
1746  */
1747  li = strat->T[i].pLength;
1748  if (li<=0) li=strat->T[i].GetpLength();
1749  ii = i;
1750  if (li<3) break;
1751  }
1752  }
1753  }
1754  }
1755 #endif
1756 
1757  /*
1758  * end of search: have to reduce with pi
1759  */
1760 
1761 
1762 #ifdef KDEBUG
1763  if (TEST_OPT_DEBUG)
1764  {
1765  PrintS("red:");
1766  h->wrp();
1767  PrintS(" with ");
1768  strat->T[ii].wrp();
1769  }
1770 #endif
1771 
1772  ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1773 #if SBA_PRINT_REDUCTION_STEPS
1774  sba_interreduction_steps++;
1775 #endif
1776 #if SBA_PRINT_OPERATIONS
1777  sba_interreduction_operations += pLength(strat->T[ii].p);
1778 #endif
1779 
1780 #ifdef KDEBUG
1781  if (TEST_OPT_DEBUG)
1782  {
1783  PrintS("\nto ");
1784  h->wrp();
1785  PrintLn();
1786  }
1787 #endif
1788 
1789  h_p=h->GetLmTailRing();
1790 
1791  if (h_p == NULL)
1792  {
1793  kDeleteLcm(h);
1794  return 0;
1795  }
1796  #if 0 // red id redLiftstd if OPT_IDLIFT
1798  {
1799  if (h->p!=NULL)
1800  {
1801  if(p_GetComp(h->p,currRing)>strat->syzComp)
1802  {
1803  h->Delete();
1804  return 0;
1805  }
1806  }
1807  else if (h->t_p!=NULL)
1808  {
1809  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1810  {
1811  h->Delete();
1812  return 0;
1813  }
1814  }
1815  }
1816  #endif
1817  #if 0
1818  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1819  {
1820  if (h->p!=NULL)
1821  {
1822  if(p_GetComp(h->p,currRing)>strat->syzComp)
1823  {
1824  return 1;
1825  }
1826  }
1827  else if (h->t_p!=NULL)
1828  {
1829  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1830  {
1831  return 1;
1832  }
1833  }
1834  }
1835  #endif
1836  h->SetShortExpVector();
1837  d = h->SetpFDeg();
1838  /*- try to reduce the s-polynomial -*/
1839  cnt--;
1840  pass++;
1841  if (//!TEST_OPT_REDTHROUGH &&
1842  (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1843  {
1844  h->SetLmCurrRing();
1845  at = strat->posInL(strat->L,strat->Ll,h,strat);
1846  if (at <= strat->Ll)
1847  {
1848 #if 1
1849 #ifdef HAVE_SHIFTBBA
1850  if (rIsLPRing(currRing))
1851  {
1852  if (kFindDivisibleByInT(strat, h) < 0)
1853  return 1;
1854  }
1855  else
1856 #endif
1857  {
1858  int dummy=strat->sl;
1859  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1860  return 1;
1861  }
1862 #endif
1863 #ifdef KDEBUG
1864  if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1865 #endif
1866  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1867  h->Clear();
1868  return -1;
1869  }
1870  }
1871  else if (d != reddeg)
1872  {
1873  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1874  {
1875  if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1876  {
1877  strat->overflow=TRUE;
1878  //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1879  h->GetP();
1880  at = strat->posInL(strat->L,strat->Ll,h,strat);
1881  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1882  h->Clear();
1883  return -1;
1884  }
1885  }
1886  else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1887  {
1888  Print(".%ld",d);mflush();
1889  reddeg = d;
1890  }
1891  }
1892  else if (UNLIKELY(cnt==0))
1893  {
1894  h->CanonicalizeP();
1895  cnt=RED_CANONICALIZE;
1896  //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1897  }
1898  }
1899 }
1900 /*2
1901 * reduction procedure for the sugar-strategy (honey)
1902 * reduces h with elements from T choosing first possible
1903 * element in T with respect to the given ecart
1904 */
1906 {
1907  if (strat->tl<0) return 1;
1908  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1909  assume(h->FDeg == h->pFDeg());
1910  poly h_p;
1911  int i,j,at,pass,ei, ii, h_d;
1912  long reddeg,d;
1913  int li;
1914  BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1915 
1916  pass = j = 0;
1917  d = reddeg = h->GetpFDeg() + h->ecart;
1918  h->SetShortExpVector();
1919  h_p = h->GetLmTailRing();
1920 
1921  h->PrepareRed(strat->use_buckets);
1922  loop
1923  {
1924  j=kFindDivisibleByInT(strat, h);
1925  if (j < 0) return 1;
1926 
1927  ei = strat->T[j].ecart;
1928  li = strat->T[j].pLength;
1929  ii = j;
1930  /*
1931  * the polynomial to reduce with (up to the moment) is;
1932  * pi with ecart ei (T[ii])
1933  */
1934  i = j;
1935  if (test_opt_length)
1936  {
1937  if (li<=0) li=strat->T[j].GetpLength();
1938  if (li>2)
1939  {
1940  unsigned long not_sev = ~ h->sev;
1941  loop
1942  {
1943  /*- takes the first possible with respect to ecart -*/
1944  i++;
1945  if (i > strat->tl) break;
1946  if (ei <= h->ecart) break;
1947  if(p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1948  h_p, not_sev, strat->tailRing))
1949  {
1950  strat->T[i].GetpLength();
1951  if (((strat->T[i].ecart < ei) && (ei> h->ecart))
1952  || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1953  {
1954  /*
1955  * the polynomial to reduce with is now;
1956  */
1957  ei = strat->T[i].ecart;
1958  li = strat->T[i].pLength;
1959  ii = i;
1960  if (li==1) break;
1961  if (ei<=h->ecart) break;
1962  }
1963  }
1964  }
1965  }
1966  }
1967 
1968  /*
1969  * end of search: have to reduce with pi
1970  */
1971  if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
1972  {
1973  h->GetTP(); // clears bucket
1974  h->SetLmCurrRing();
1975  /*
1976  * It is not possible to reduce h with smaller ecart;
1977  * if possible h goes to the lazy-set L,i.e
1978  * if its position in L would be not the last one
1979  */
1980  if (strat->Ll >= 0) /* L is not empty */
1981  {
1982  at = strat->posInL(strat->L,strat->Ll,h,strat);
1983  if(at <= strat->Ll)
1984  /*- h will not become the next element to reduce -*/
1985  {
1986  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1987 #ifdef KDEBUG
1988  if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1989 #endif
1990  h->Clear();
1991  return -1;
1992  }
1993  }
1994  }
1995 #ifdef KDEBUG
1996  if (TEST_OPT_DEBUG)
1997  {
1998  PrintS("red:");
1999  h->wrp();
2000  Print("\nwith T[%d]:",ii);
2001  strat->T[ii].wrp();
2002  }
2003 #endif
2004  assume(strat->fromT == FALSE);
2005 
2006  ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
2007 #if SBA_PRINT_REDUCTION_STEPS
2008  sba_interreduction_steps++;
2009 #endif
2010 #if SBA_PRINT_OPERATIONS
2011  sba_interreduction_operations += strat->T[ii].pLength;
2012 #endif
2013 #ifdef KDEBUG
2014  if (TEST_OPT_DEBUG)
2015  {
2016  PrintS("\nto:");
2017  h->wrp();
2018  PrintLn();
2019  }
2020 #endif
2021  if(h->IsNull())
2022  {
2023  kDeleteLcm(h);
2024  h->Clear();
2025  return 0;
2026  }
2027  #if 0 // red is redLiftstd if OPT_IDLIFT
2029  {
2030  if (h->p!=NULL)
2031  {
2032  if(p_GetComp(h->p,currRing)>strat->syzComp)
2033  {
2034  h->Delete();
2035  return 0;
2036  }
2037  }
2038  else if (h->t_p!=NULL)
2039  {
2040  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2041  {
2042  h->Delete();
2043  return 0;
2044  }
2045  }
2046  }
2047  else
2048  #endif
2049  if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
2050  {
2051  if (h->p!=NULL)
2052  {
2053  if(p_GetComp(h->p,currRing)>strat->syzComp)
2054  {
2055  return 1;
2056  }
2057  }
2058  else if (h->t_p!=NULL)
2059  {
2060  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2061  {
2062  return 1;
2063  }
2064  }
2065  }
2066  h->SetShortExpVector();
2067  h_d = h->SetpFDeg();
2068  /* compute the ecart */
2069  if (ei <= h->ecart)
2070  h->ecart = d-h_d;
2071  else
2072  h->ecart = d-h_d+ei-h->ecart;
2073 
2074  /*
2075  * try to reduce the s-polynomial h
2076  *test first whether h should go to the lazyset L
2077  *-if the degree jumps
2078  *-if the number of pre-defined reductions jumps
2079  */
2080  pass++;
2081  d = h_d + h->ecart;
2083  && (strat->Ll >= 0)
2084  && ((d > reddeg) || (pass > strat->LazyPass))))
2085  {
2086  h->GetTP(); // clear bucket
2087  h->SetLmCurrRing();
2088  at = strat->posInL(strat->L,strat->Ll,h,strat);
2089  if (at <= strat->Ll)
2090  {
2091 #ifdef HAVE_SHIFTBBA
2092  if (rIsLPRing(currRing))
2093  {
2094  if (kFindDivisibleByInT(strat, h) < 0)
2095  return 1;
2096  }
2097  else
2098 #endif
2099  {
2100  int dummy=strat->sl;
2101  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2102  return 1;
2103  }
2104  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2105 #ifdef KDEBUG
2106  if (TEST_OPT_DEBUG)
2107  Print(" degree jumped: -> L%d\n",at);
2108 #endif
2109  h->Clear();
2110  return -1;
2111  }
2112  }
2113  else if (d > reddeg)
2114  {
2115  if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2116  {
2117  if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2118  {
2119  strat->overflow=TRUE;
2120  //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2121  h->GetP();
2122  at = strat->posInL(strat->L,strat->Ll,h,strat);
2123  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2124  h->Clear();
2125  return -1;
2126  }
2127  }
2128  else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
2129  {
2130  //h->wrp(); Print("<%d>\n",h->GetpLength());
2131  reddeg = d;
2132  Print(".%ld",d); mflush();
2133  }
2134  }
2135  }
2136 }
2137 
2138 /*2
2139 * reduction procedure for the normal form
2140 */
2141 
2142 poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
2143 {
2144  if (h==NULL) return NULL;
2145  int j;
2146  int cnt=REDNF_CANONICALIZE;
2147  max_ind=strat->sl;
2148 
2149  if (0 > strat->sl)
2150  {
2151  return h;
2152  }
2153  LObject P(h);
2154  P.SetShortExpVector();
2155  P.bucket = kBucketCreate(currRing);
2156  kBucketInit(P.bucket,P.p,pLength(P.p));
2157  kbTest(P.bucket);
2158 #ifdef HAVE_RINGS
2159  BOOLEAN is_ring = rField_is_Ring(currRing);
2160 #endif
2161 #ifdef KDEBUG
2162 // if (TEST_OPT_DEBUG)
2163 // {
2164 // PrintS("redNF: starting S:\n");
2165 // for( j = 0; j <= max_ind; j++ )
2166 // {
2167 // Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2168 // pWrite(strat->S[j]);
2169 // }
2170 // };
2171 #endif
2172 
2173  loop
2174  {
2175  j=kFindDivisibleByInS(strat,&max_ind,&P);
2176  if (j>=0)
2177  {
2178 #ifdef HAVE_RINGS
2179  if (!is_ring)
2180  {
2181 #endif
2182  int sl=pSize(strat->S[j]);
2183  int jj=j;
2184  loop
2185  {
2186  int sll;
2187  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2188  if (jj<0) break;
2189  sll=pSize(strat->S[jj]);
2190  if (sll<sl)
2191  {
2192  #ifdef KDEBUG
2193  if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2194  #endif
2195  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2196  j=jj;
2197  sl=sll;
2198  }
2199  }
2200  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2201  {
2202  pNorm(strat->S[j]);
2203  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2204  }
2205 #ifdef HAVE_RINGS
2206  }
2207 #endif
2208  nNormalize(pGetCoeff(P.p));
2209 #ifdef KDEBUG
2210  if (TEST_OPT_DEBUG)
2211  {
2212  PrintS("red:");
2213  wrp(h);
2214  PrintS(" with ");
2215  wrp(strat->S[j]);
2216  }
2217 #endif
2218 #ifdef HAVE_PLURAL
2219  if (rIsPluralRing(currRing))
2220  {
2221  number coef;
2222  nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2223  nDelete(&coef);
2224  }
2225  else
2226 #endif
2227  {
2228  number coef;
2229  coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2230  nDelete(&coef);
2231  }
2232  cnt--;
2233  if (cnt==0)
2234  {
2235  kBucketCanonicalize(P.bucket);
2236  cnt=REDNF_CANONICALIZE;
2237  }
2238  h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2239  if (h==NULL)
2240  {
2241  kBucketDestroy(&P.bucket);
2242  return NULL;
2243  }
2244  kbTest(P.bucket);
2245  P.p=h;
2246  P.t_p=NULL;
2247  P.SetShortExpVector();
2248 #ifdef KDEBUG
2249  if (TEST_OPT_DEBUG)
2250  {
2251  PrintS("\nto:");
2252  wrp(h);
2253  PrintLn();
2254  }
2255 #endif
2256  }
2257  else
2258  {
2259  P.p=kBucketClear(P.bucket);
2260  kBucketDestroy(&P.bucket);
2261  pNormalize(P.p);
2262  return P.p;
2263  }
2264  }
2265 }
2266 
2267 /*2
2268 * reduction procedure from global case but with jet bound
2269 */
2270 
2271 poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
2272 {
2273  h = pJet(h,bound);
2274  if (h==NULL) return NULL;
2275  int j;
2276  max_ind=strat->sl;
2277 
2278  if (0 > strat->sl)
2279  {
2280  return h;
2281  }
2282  LObject P(h);
2283  P.SetShortExpVector();
2284  P.bucket = kBucketCreate(currRing);
2285  kBucketInit(P.bucket,P.p,pLength(P.p));
2286  kbTest(P.bucket);
2287 #ifdef HAVE_RINGS
2288  BOOLEAN is_ring = rField_is_Ring(currRing);
2289 #endif
2290 
2291  loop
2292  {
2293  j=kFindDivisibleByInS(strat,&max_ind,&P);
2294  if (j>=0)
2295  {
2296 #ifdef HAVE_RINGS
2297  if (!is_ring)
2298  {
2299 #endif
2300  int sl=pSize(strat->S[j]);
2301  int jj=j;
2302  loop
2303  {
2304  int sll;
2305  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2306  if (jj<0) break;
2307  sll=pSize(strat->S[jj]);
2308  if (sll<sl)
2309  {
2310  #ifdef KDEBUG
2311  if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2312  #endif
2313  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2314  j=jj;
2315  sl=sll;
2316  }
2317  }
2318  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2319  {
2320  pNorm(strat->S[j]);
2321  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2322  }
2323 #ifdef HAVE_RINGS
2324  }
2325 #endif
2326  nNormalize(pGetCoeff(P.p));
2327 #ifdef KDEBUG
2328  if (TEST_OPT_DEBUG)
2329  {
2330  PrintS("red:");
2331  wrp(h);
2332  PrintS(" with ");
2333  wrp(strat->S[j]);
2334  }
2335 #endif
2336 #ifdef HAVE_PLURAL
2337  if (rIsPluralRing(currRing))
2338  {
2339  number coef;
2340  nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2341  nDelete(&coef);
2342  }
2343  else
2344 #endif
2345  {
2346  number coef;
2347  coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2348  P.p = kBucketClear(P.bucket);
2349  P.p = pJet(P.p,bound);
2350  if(!P.IsNull())
2351  {
2352  kBucketDestroy(&P.bucket);
2353  P.SetShortExpVector();
2354  P.bucket = kBucketCreate(currRing);
2355  kBucketInit(P.bucket,P.p,pLength(P.p));
2356  }
2357  nDelete(&coef);
2358  }
2359  h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2360  if (h==NULL)
2361  {
2362  kBucketDestroy(&P.bucket);
2363  return NULL;
2364  }
2365  kbTest(P.bucket);
2366  P.p=h;
2367  P.t_p=NULL;
2368  P.SetShortExpVector();
2369 #ifdef KDEBUG
2370  if (TEST_OPT_DEBUG)
2371  {
2372  PrintS("\nto:");
2373  wrp(h);
2374  PrintLn();
2375  }
2376 #endif
2377  }
2378  else
2379  {
2380  P.p=kBucketClear(P.bucket);
2381  kBucketDestroy(&P.bucket);
2382  pNormalize(P.p);
2383  return P.p;
2384  }
2385  }
2386 }
2387 
2388 void kDebugPrint(kStrategy strat);
2389 
2390 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2391 {
2392  int red_result = 1;
2393  int olddeg,reduc;
2394  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2395  BOOLEAN withT = FALSE;
2396  BITSET save;
2397  SI_SAVE_OPT1(save);
2398 
2399  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2401  initBuchMoraPosRing(strat);
2402  else
2403  initBuchMoraPos(strat);
2404  initHilbCrit(F,Q,&hilb,strat);
2405  initBba(strat);
2406  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2407  /*Shdl=*/initBuchMora(F, Q,strat);
2408  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2409  reduc = olddeg = 0;
2410 
2411 #ifndef NO_BUCKETS
2412  if (!TEST_OPT_NOT_BUCKETS)
2413  strat->use_buckets = 1;
2414 #endif
2415  // redtailBBa against T for inhomogenous input
2416  if (!TEST_OPT_OLDSTD)
2417  withT = ! strat->homog;
2418 
2419  // strat->posInT = posInT_pLength;
2420  kTest_TS(strat);
2421 
2422 #ifdef HAVE_TAIL_RING
2423  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2424  kStratInitChangeTailRing(strat);
2425 #endif
2426  if (BVERBOSE(23))
2427  {
2428  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2429  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2430  kDebugPrint(strat);
2431  }
2432 
2433 
2434 #ifdef KDEBUG
2435  //kDebugPrint(strat);
2436 #endif
2437  /* compute------------------------------------------------------- */
2438  while (strat->Ll >= 0)
2439  {
2440  #ifdef KDEBUG
2441  if (TEST_OPT_DEBUG) messageSets(strat);
2442  #endif
2443  if (siCntrlc)
2444  {
2445  while (strat->Ll >= 0)
2446  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2447  strat->noClearS=TRUE;
2448  }
2449  if (TEST_OPT_DEGBOUND
2450  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2451  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2452  {
2453  /*
2454  *stops computation if
2455  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2456  *a predefined number Kstd1_deg
2457  */
2458  while ((strat->Ll >= 0)
2459  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2460  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2461  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2462  )
2463  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2464  if (strat->Ll<0) break;
2465  else strat->noClearS=TRUE;
2466  }
2467  if (strat->Ll== 0) strat->interpt=TRUE;
2468  /* picks the last element from the lazyset L */
2469  strat->P = strat->L[strat->Ll];
2470  strat->Ll--;
2471 
2472  if (pNext(strat->P.p) == strat->tail)
2473  {
2474  // deletes the short spoly
2475  if (rField_is_Ring(currRing))
2476  pLmDelete(strat->P.p);
2477  else
2478  pLmFree(strat->P.p);
2479  strat->P.p = NULL;
2480  poly m1 = NULL, m2 = NULL;
2481 
2482  // check that spoly creation is ok
2483  while (strat->tailRing != currRing &&
2484  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2485  {
2486  assume(m1 == NULL && m2 == NULL);
2487  // if not, change to a ring where exponents are at least
2488  // large enough
2489  if (!kStratChangeTailRing(strat))
2490  {
2491  WerrorS("OVERFLOW...");
2492  break;
2493  }
2494  }
2495  // create the real one
2496  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2497  strat->tailRing, m1, m2, strat->R);
2498  }
2499  else if (strat->P.p1 == NULL)
2500  {
2501  if (strat->minim > 0)
2502  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2503  // for input polys, prepare reduction
2504  strat->P.PrepareRed(strat->use_buckets);
2505  }
2506 
2507  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2508  {
2509  red_result = 0;
2510  }
2511  else
2512  {
2513  if (TEST_OPT_PROT)
2514  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2515  &olddeg,&reduc,strat, red_result);
2516 
2517  /* reduction of the element chosen from L */
2518  red_result = strat->red(&strat->P,strat);
2519  if (errorreported) break;
2520  }
2521 
2522  if (strat->overflow)
2523  {
2524  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2525  }
2526 
2527  // reduction to non-zero new poly
2528  if (red_result == 1)
2529  {
2530  // get the polynomial (canonicalize bucket, make sure P.p is set)
2531  strat->P.GetP(strat->lmBin);
2532  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2533  // but now, for entering S, T, we reset it
2534  // in the inhomogeneous case: FDeg == pFDeg
2535  if (strat->homog) strat->initEcart(&(strat->P));
2536 
2537  /* statistic */
2538  if (TEST_OPT_PROT) PrintS("s");
2539 
2540  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2541 
2542  // reduce the tail and normalize poly
2543  // in the ring case we cannot expect LC(f) = 1,
2544  strat->redTailChange=FALSE;
2545 
2546  /* if we are computing over Z we always want to try and cut down
2547  * the coefficients in the tail terms */
2549  {
2550  redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2551  }
2552 
2554  {
2555  strat->P.pCleardenom();
2557  {
2558  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2559  strat->P.pCleardenom();
2560  if (strat->redTailChange) { strat->P.t_p=NULL; }
2561  }
2562  }
2563  else
2564  {
2565  strat->P.pNorm();
2567  {
2568  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2569  if (strat->redTailChange) { strat->P.t_p=NULL; }
2570  }
2571  }
2572 
2573 #ifdef KDEBUG
2574  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2575 #endif /* KDEBUG */
2576 
2577  // min_std stuff
2578  if ((strat->P.p1==NULL) && (strat->minim>0))
2579  {
2580  if (strat->minim==1)
2581  {
2582  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2583  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2584  }
2585  else
2586  {
2587  strat->M->m[minimcnt]=strat->P.p2;
2588  strat->P.p2=NULL;
2589  }
2590  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2591  pNext(strat->M->m[minimcnt])
2592  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2593  strat->tailRing, currRing,
2594  currRing->PolyBin);
2595  minimcnt++;
2596  }
2597 
2598  // enter into S, L, and T
2599  if (((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2600  && ((!TEST_OPT_IDELIM) || (p_Deg(strat->P.p,currRing) > 0)))
2601  {
2602  strat->P.SetShortExpVector();
2603  enterT(strat->P, strat);
2604  if (rField_is_Ring(currRing))
2605  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2606  else
2607  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2608  // posInS only depends on the leading term
2609  strat->enterS(strat->P, pos, strat, strat->tl);
2610 #if 0
2611  int pl=pLength(strat->P.p);
2612  if (pl==1)
2613  {
2614  //if (TEST_OPT_PROT)
2615  //PrintS("<1>");
2616  }
2617  else if (pl==2)
2618  {
2619  //if (TEST_OPT_PROT)
2620  //PrintS("<2>");
2621  }
2622 #endif
2623  }
2624  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2625 // Print("[%d]",hilbeledeg);
2626  kDeleteLcm(&strat->P);
2627  if (strat->s_poly!=NULL)
2628  {
2629  // the only valid entries are: strat->P.p,
2630  // strat->tailRing (read-only, keep it)
2631  // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2632  if (strat->s_poly(strat))
2633  {
2634  // we are called AFTER enterS, i.e. if we change P
2635  // we have to add it also to S/T
2636  // and add pairs
2637  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2638  enterT(strat->P, strat);
2639  if (rField_is_Ring(currRing))
2640  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2641  else
2642  enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2643  strat->enterS(strat->P, pos, strat, strat->tl);
2644  }
2645  }
2646  }
2647  else if (strat->P.p1 == NULL && strat->minim > 0)
2648  {
2649  p_Delete(&strat->P.p2, currRing, strat->tailRing);
2650  }
2651 
2652 #ifdef KDEBUG
2653  memset(&(strat->P), 0, sizeof(strat->P));
2654 #endif /* KDEBUG */
2655  kTest_TS(strat);
2656  }
2657 #ifdef KDEBUG
2658  if (TEST_OPT_DEBUG) messageSets(strat);
2659 #endif /* KDEBUG */
2660 
2661  if (TEST_OPT_SB_1)
2662  {
2663  if(!rField_is_Ring(currRing))
2664  {
2665  int k=1;
2666  int j;
2667  while(k<=strat->sl)
2668  {
2669  j=0;
2670  loop
2671  {
2672  if (j>=k) break;
2673  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2674  j++;
2675  }
2676  k++;
2677  }
2678  }
2679  }
2680  /* complete reduction of the standard basis--------- */
2681  if (TEST_OPT_REDSB)
2682  {
2683  completeReduce(strat);
2684  if (strat->completeReduce_retry)
2685  {
2686  // completeReduce needed larger exponents, retry
2687  // to reduce with S (instead of T)
2688  // and in currRing (instead of strat->tailRing)
2689 #ifdef HAVE_TAIL_RING
2690  if(currRing->bitmask>strat->tailRing->bitmask)
2691  {
2692  strat->completeReduce_retry=FALSE;
2693  cleanT(strat);strat->tailRing=currRing;
2694  int i;
2695  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2696  completeReduce(strat);
2697  }
2698  if (strat->completeReduce_retry)
2699 #endif
2700  Werror("exponent bound is %ld",currRing->bitmask);
2701  }
2702  }
2703  else if (TEST_OPT_PROT) PrintLn();
2704  /* release temp data-------------------------------- */
2705  exitBuchMora(strat);
2706  /* postprocessing for GB over ZZ --------------------*/
2707  if (!errorreported)
2708  {
2709  if(rField_is_Z(currRing))
2710  {
2711  for(int i = 0;i<=strat->sl;i++)
2712  {
2713  if(!nGreaterZero(pGetCoeff(strat->S[i])))
2714  {
2715  strat->S[i] = pNeg(strat->S[i]);
2716  }
2717  }
2718  finalReduceByMon(strat);
2719  for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2720  {
2721  if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2722  {
2723  strat->S[i] = pNeg(strat->Shdl->m[i]);
2724  }
2725  }
2726  }
2727  //else if (rField_is_Ring(currRing))
2728  // finalReduceByMon(strat);
2729  }
2730 // if (TEST_OPT_WEIGHTM)
2731 // {
2732 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2733 // if (ecartWeights)
2734 // {
2735 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2736 // ecartWeights=NULL;
2737 // }
2738 // }
2739  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2740  SI_RESTORE_OPT1(save);
2741  /* postprocessing for GB over Q-rings ------------------*/
2742  if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2743 
2744  idTest(strat->Shdl);
2745 
2746  return (strat->Shdl);
2747 }
2748 
2749 ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2750 {
2751  // ring order stuff:
2752  // in sba we have (until now) two possibilities:
2753  // 1. an incremental computation w.r.t. (C,monomial order)
2754  // 2. a (possibly non-incremental) computation w.r.t. the
2755  // induced Schreyer order.
2756  // The corresponding orders are computed in sbaRing(), depending
2757  // on the flag strat->sbaOrder
2758 #if SBA_PRINT_ZERO_REDUCTIONS
2759  long zeroreductions = 0;
2760 #endif
2761 #if SBA_PRINT_PRODUCT_CRITERION
2762  long product_criterion = 0;
2763 #endif
2764 #if SBA_PRINT_SIZE_G
2765  int size_g = 0;
2766  int size_g_non_red = 0;
2767 #endif
2768 #if SBA_PRINT_SIZE_SYZ
2769  long size_syz = 0;
2770 #endif
2771  // global variable
2772 #if SBA_PRINT_REDUCTION_STEPS
2773  sba_reduction_steps = 0;
2774  sba_interreduction_steps = 0;
2775 #endif
2776 #if SBA_PRINT_OPERATIONS
2777  sba_operations = 0;
2778  sba_interreduction_operations = 0;
2779 #endif
2780 
2781  ideal F1 = F0;
2782  ring sRing, currRingOld;
2783  currRingOld = currRing;
2784  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
2785  {
2786  sRing = sbaRing(strat);
2787  if (sRing!=currRingOld)
2788  {
2789  rChangeCurrRing (sRing);
2790  F1 = idrMoveR (F0, currRingOld, currRing);
2791  }
2792  }
2793  ideal F;
2794  // sort ideal F
2795  //Put the SigDrop element on the correct position (think of sbaEnterS)
2796  //We also sort them
2797  if(rField_is_Ring(currRing) && strat->sigdrop)
2798  {
2799  #if 1
2800  F = idInit(IDELEMS(F1),F1->rank);
2801  for (int i=0; i<IDELEMS(F1);++i)
2802  F->m[i] = F1->m[i];
2803  if(strat->sbaEnterS >= 0)
2804  {
2805  poly dummy;
2806  dummy = pCopy(F->m[0]); //the sigdrop element
2807  for(int i = 0;i<strat->sbaEnterS;i++)
2808  F->m[i] = F->m[i+1];
2809  F->m[strat->sbaEnterS] = dummy;
2810  }
2811  #else
2812  F = idInit(1,F1->rank);
2813  //printf("\nBefore the initial block sorting:\n");idPrint(F1);
2814  F->m[0] = F1->m[0];
2815  int pos;
2816  if(strat->sbaEnterS >= 0)
2817  {
2818  for(int i=1;i<=strat->sbaEnterS;i++)
2819  {
2820  pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2821  idInsertPolyOnPos(F,F1->m[i],pos);
2822  }
2823  for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2824  {
2825  pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2826  idInsertPolyOnPos(F,F1->m[i],pos);
2827  }
2828  poly dummy;
2829  dummy = pCopy(F->m[0]); //the sigdrop element
2830  for(int i = 0;i<strat->sbaEnterS;i++)
2831  F->m[i] = F->m[i+1];
2832  F->m[strat->sbaEnterS] = dummy;
2833  }
2834  else
2835  {
2836  for(int i=1;i<IDELEMS(F1);i++)
2837  {
2838  pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2839  idInsertPolyOnPos(F,F1->m[i],pos);
2840  }
2841  }
2842  #endif
2843  //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2844  }
2845  else
2846  {
2847  F = idInit(IDELEMS(F1),F1->rank);
2848  intvec *sort = idSort(F1);
2849  for (int i=0; i<sort->length();++i)
2850  F->m[i] = F1->m[(*sort)[i]-1];
2852  {
2853  // put the monomials after the sbaEnterS polynomials
2854  //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2855  int nrmon = 0;
2856  for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2857  {
2858  //pWrite(F->m[i]);
2859  if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2860  {
2861  poly mon = F->m[i];
2862  for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2863  {
2864  F->m[j] = F->m[j-1];
2865  }
2866  F->m[j] = mon;
2867  nrmon++;
2868  }
2869  //idPrint(F);
2870  }
2871  }
2872  }
2873  //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2875  strat->sigdrop = FALSE;
2876  strat->nrsyzcrit = 0;
2877  strat->nrrewcrit = 0;
2878 #if SBA_INTERRED_START
2879  F = kInterRed(F,NULL);
2880 #endif
2881 #if F5DEBUG
2882  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2883  rWrite (currRing);
2884  printf("ordSgn = %d\n",currRing->OrdSgn);
2885  printf("\n");
2886 #endif
2887  int srmax,lrmax, red_result = 1;
2888  int olddeg,reduc;
2889  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2890  LObject L;
2891  BOOLEAN withT = TRUE;
2892  strat->max_lower_index = 0;
2893  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2894  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
2895  initSbaPos(strat);
2896  initHilbCrit(F,Q,&hilb,strat);
2897  initSba(F,strat);
2898  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2899  /*Shdl=*/initSbaBuchMora(F, Q,strat);
2900  idTest(strat->Shdl);
2901  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2902  srmax = strat->sl;
2903  reduc = olddeg = lrmax = 0;
2904 #ifndef NO_BUCKETS
2905  if (!TEST_OPT_NOT_BUCKETS)
2906  strat->use_buckets = 1;
2907 #endif
2908 
2909  // redtailBBa against T for inhomogenous input
2910  // if (!TEST_OPT_OLDSTD)
2911  // withT = ! strat->homog;
2912 
2913  // strat->posInT = posInT_pLength;
2914  kTest_TS(strat);
2915 
2916 #ifdef HAVE_TAIL_RING
2917  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2918  kStratInitChangeTailRing(strat);
2919 #endif
2920  if (BVERBOSE(23))
2921  {
2922  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2923  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2924  kDebugPrint(strat);
2925  }
2926  // We add the elements directly in S from the previous loop
2927  if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2928  {
2929  for(int i = 0;i<strat->sbaEnterS;i++)
2930  {
2931  //Update: now the element is at the corect place
2932  //i+1 because on the 0 position is the sigdrop element
2933  enterT(strat->L[strat->Ll-(i)],strat);
2934  strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2935  }
2936  strat->Ll = strat->Ll - strat->sbaEnterS;
2937  strat->sbaEnterS = -1;
2938  }
2939  kTest_TS(strat);
2940 #ifdef KDEBUG
2941  //kDebugPrint(strat);
2942 #endif
2943  /* compute------------------------------------------------------- */
2944  while (strat->Ll >= 0)
2945  {
2946  if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2947  #ifdef KDEBUG
2948  if (TEST_OPT_DEBUG) messageSets(strat);
2949  #endif
2950  if (strat->Ll== 0) strat->interpt=TRUE;
2951  /*
2952  if (TEST_OPT_DEGBOUND
2953  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2954  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2955  {
2956 
2957  //stops computation if
2958  // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2959  //a predefined number Kstd1_deg
2960  while ((strat->Ll >= 0)
2961  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2962  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2963  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2964  )
2965  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2966  if (strat->Ll<0) break;
2967  else strat->noClearS=TRUE;
2968  }
2969  */
2970  if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2971  {
2972  strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2973 #if F5C
2974  // 1. interreduction of the current standard basis
2975  // 2. generation of new principal syzygy rules for syzCriterion
2976  f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2977  lrmax, reduc, Q, w, hilb );
2978 #endif
2979  // initialize new syzygy rules for the next iteration step
2980  initSyzRules(strat);
2981  }
2982  /*********************************************************************
2983  * interrreduction step is done, we can go on with the next iteration
2984  * step of the signature-based algorithm
2985  ********************************************************************/
2986  /* picks the last element from the lazyset L */
2987  strat->P = strat->L[strat->Ll];
2988  strat->Ll--;
2989 
2991  strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2992  /* reduction of the element chosen from L */
2993  if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2994  {
2995  //#if 1
2996 #ifdef DEBUGF5
2997  PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2998  PrintS("-------------------------------------------------\n");
2999  pWrite(strat->P.sig);
3000  pWrite(pHead(strat->P.p));
3001  pWrite(pHead(strat->P.p1));
3002  pWrite(pHead(strat->P.p2));
3003  PrintS("-------------------------------------------------\n");
3004 #endif
3005  if (pNext(strat->P.p) == strat->tail)
3006  {
3007  // deletes the short spoly
3008  /*
3009  if (rField_is_Ring(currRing))
3010  pLmDelete(strat->P.p);
3011  else
3012  pLmFree(strat->P.p);
3013 */
3014  // TODO: needs some masking
3015  // TODO: masking needs to vanish once the signature
3016  // sutff is completely implemented
3017  strat->P.p = NULL;
3018  poly m1 = NULL, m2 = NULL;
3019 
3020  // check that spoly creation is ok
3021  while (strat->tailRing != currRing &&
3022  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3023  {
3024  assume(m1 == NULL && m2 == NULL);
3025  // if not, change to a ring where exponents are at least
3026  // large enough
3027  if (!kStratChangeTailRing(strat))
3028  {
3029  WerrorS("OVERFLOW...");
3030  break;
3031  }
3032  }
3033  // create the real one
3034  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3035  strat->tailRing, m1, m2, strat->R);
3036 
3037  }
3038  else if (strat->P.p1 == NULL)
3039  {
3040  if (strat->minim > 0)
3041  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3042  // for input polys, prepare reduction
3043  if(!rField_is_Ring(currRing))
3044  strat->P.PrepareRed(strat->use_buckets);
3045  }
3046  if (strat->P.p == NULL && strat->P.t_p == NULL)
3047  {
3048  red_result = 0;
3049  }
3050  else
3051  {
3052  //#if 1
3053 #ifdef DEBUGF5
3054  PrintS("Poly before red: ");
3055  pWrite(pHead(strat->P.p));
3056  pWrite(strat->P.sig);
3057 #endif
3058 #if SBA_PRODUCT_CRITERION
3059  if (strat->P.prod_crit)
3060  {
3061 #if SBA_PRINT_PRODUCT_CRITERION
3062  product_criterion++;
3063 #endif
3064  int pos = posInSyz(strat, strat->P.sig);
3065  enterSyz(strat->P, strat, pos);
3066  kDeleteLcm(&strat->P);
3067  red_result = 2;
3068  }
3069  else
3070  {
3071  red_result = strat->red(&strat->P,strat);
3072  }
3073 #else
3074  red_result = strat->red(&strat->P,strat);
3075 #endif
3076  }
3077  }
3078  else
3079  {
3080  /*
3081  if (strat->P.lcm != NULL)
3082  pLmFree(strat->P.lcm);
3083  */
3084  red_result = 2;
3085  }
3087  {
3088  if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3089  {
3090  strat->P.p = pNeg(strat->P.p);
3091  strat->P.sig = pNeg(strat->P.sig);
3092  }
3093  strat->P.pLength = pLength(strat->P.p);
3094  if(strat->P.sig != NULL)
3095  strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3096  if(strat->P.p != NULL)
3097  strat->P.sev = pGetShortExpVector(strat->P.p);
3098  }
3099  //sigdrop case
3100  if(rField_is_Ring(currRing) && strat->sigdrop)
3101  {
3102  //First reduce it as much as one can
3103  red_result = redRing(&strat->P,strat);
3104  if(red_result == 0)
3105  {
3106  strat->sigdrop = FALSE;
3107  pDelete(&strat->P.sig);
3108  strat->P.sig = NULL;
3109  }
3110  else
3111  {
3112  strat->enterS(strat->P, 0, strat, strat->tl);
3113  if (TEST_OPT_PROT)
3114  PrintS("-");
3115  break;
3116  }
3117  }
3118  if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3119  {
3120  strat->sigdrop = TRUE;
3121  break;
3122  }
3123 
3124  if (errorreported) break;
3125 
3126 //#if 1
3127 #ifdef DEBUGF5
3128  if (red_result != 0)
3129  {
3130  PrintS("Poly after red: ");
3131  pWrite(pHead(strat->P.p));
3132  pWrite(strat->P.GetLmCurrRing());
3133  pWrite(strat->P.sig);
3134  printf("%d\n",red_result);
3135  }
3136 #endif
3137  if (TEST_OPT_PROT)
3138  {
3139  if(strat->P.p != NULL)
3140  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3141  &olddeg,&reduc,strat, red_result);
3142  else
3143  message((strat->honey ? strat->P.ecart : 0),
3144  &olddeg,&reduc,strat, red_result);
3145  }
3146 
3147  if (strat->overflow)
3148  {
3149  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3150  }
3151  // reduction to non-zero new poly
3152  if (red_result == 1)
3153  {
3154  // get the polynomial (canonicalize bucket, make sure P.p is set)
3155  strat->P.GetP(strat->lmBin);
3156 
3157  // sig-safe computations may lead to wrong FDeg computation, thus we need
3158  // to recompute it to make sure everything is alright
3159  (strat->P).FDeg = (strat->P).pFDeg();
3160  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3161  // but now, for entering S, T, we reset it
3162  // in the inhomogeneous case: FDeg == pFDeg
3163  if (strat->homog) strat->initEcart(&(strat->P));
3164 
3165  /* statistic */
3166  if (TEST_OPT_PROT) PrintS("s");
3167 
3168  //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3169  // in F5E we know that the last reduced element is already the
3170  // the one with highest signature
3171  int pos = strat->sl+1;
3172 
3173  // reduce the tail and normalize poly
3174  // in the ring case we cannot expect LC(f) = 1,
3175  #ifdef HAVE_RINGS
3176  poly beforetailred;
3178  beforetailred = pCopy(strat->P.sig);
3179  #endif
3180 #if SBA_TAIL_RED
3182  {
3184  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3185  }
3186  else
3187  {
3188  if (strat->sbaOrder != 2)
3189  {
3191  {
3192  strat->P.pCleardenom();
3194  {
3195  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3196  strat->P.pCleardenom();
3197  }
3198  }
3199  else
3200  {
3201  strat->P.pNorm();
3203  strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3204  }
3205  }
3206  }
3207  // It may happen that we have lost the sig in redtailsba
3208  // It cannot reduce to 0 since here we are doing just tail reduction.
3209  // Best case scenerio: remains the leading term
3210  if(rField_is_Ring(currRing) && strat->sigdrop)
3211  {
3212  strat->enterS(strat->P, 0, strat, strat->tl);
3213  break;
3214  }
3215 #endif
3217  {
3218  if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
3219  {
3220  strat->sigdrop = TRUE;
3221  //Reduce it as much as you can
3222  red_result = redRing(&strat->P,strat);
3223  if(red_result == 0)
3224  {
3225  //It reduced to 0, cancel the sigdrop
3226  strat->sigdrop = FALSE;
3227  p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3228  }
3229  else
3230  {
3231  strat->enterS(strat->P, 0, strat, strat->tl);
3232  break;
3233  }
3234  }
3235  p_Delete(&beforetailred,currRing);
3236  // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3237  if(strat->P.p == NULL)
3238  goto case_when_red_result_changed;
3239  }
3240  // remove sigsafe label since it is no longer valid for the next element to
3241  // be reduced
3242  if (strat->sbaOrder == 1)
3243  {
3244  for (int jj = 0; jj<strat->tl+1; jj++)
3245  {
3246  if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3247  {
3248  strat->T[jj].is_sigsafe = FALSE;
3249  }
3250  }
3251  }
3252  else
3253  {
3254  for (int jj = 0; jj<strat->tl+1; jj++)
3255  {
3256  strat->T[jj].is_sigsafe = FALSE;
3257  }
3258  }
3259 #ifdef KDEBUG
3260  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3261 #endif /* KDEBUG */
3262 
3263  // min_std stuff
3264  if ((strat->P.p1==NULL) && (strat->minim>0))
3265  {
3266  if (strat->minim==1)
3267  {
3268  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3269  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3270  }
3271  else
3272  {
3273  strat->M->m[minimcnt]=strat->P.p2;
3274  strat->P.p2=NULL;
3275  }
3276  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3277  pNext(strat->M->m[minimcnt])
3278  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3279  strat->tailRing, currRing,
3280  currRing->PolyBin);
3281  minimcnt++;
3282  }
3283 
3284  // enter into S, L, and T
3285  //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3286  enterT(strat->P, strat);
3287  strat->T[strat->tl].is_sigsafe = FALSE;
3288  /*
3289  printf("hier\n");
3290  pWrite(strat->P.GetLmCurrRing());
3291  pWrite(strat->P.sig);
3292  */
3293  if (rField_is_Ring(currRing))
3294  superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3295  else
3296  enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3297  if(rField_is_Ring(currRing) && strat->sigdrop)
3298  break;
3300  strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3301  strat->enterS(strat->P, pos, strat, strat->tl);
3302  if(strat->sbaOrder != 1)
3303  {
3304  BOOLEAN overwrite = FALSE;
3305  for (int tk=0; tk<strat->sl+1; tk++)
3306  {
3307  if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3308  {
3309  //printf("TK %d / %d\n",tk,strat->sl);
3310  overwrite = FALSE;
3311  break;
3312  }
3313  }
3314  //printf("OVERWRITE %d\n",overwrite);
3315  if (overwrite)
3316  {
3317  int cmp = pGetComp(strat->P.sig);
3318  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3319  p_GetExpV (strat->P.p,vv,currRing);
3320  p_SetExpV (strat->P.sig, vv,currRing);
3321  p_SetComp (strat->P.sig,cmp,currRing);
3322 
3323  strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3324  int i;
3325  LObject Q;
3326  for(int ps=0;ps<strat->sl+1;ps++)
3327  {
3328 
3329  strat->newt = TRUE;
3330  if (strat->syzl == strat->syzmax)
3331  {
3332  pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3333  strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3334  (strat->syzmax)*sizeof(unsigned long),
3335  ((strat->syzmax)+setmaxTinc)
3336  *sizeof(unsigned long));
3337  strat->syzmax += setmaxTinc;
3338  }
3339  Q.sig = pCopy(strat->P.sig);
3340  // add LM(F->m[i]) to the signature to get a Schreyer order
3341  // without changing the underlying polynomial ring at all
3342  if (strat->sbaOrder == 0)
3343  p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3344  // since p_Add_q() destroys all input
3345  // data we need to recreate help
3346  // each time
3347  // ----------------------------------------------------------
3348  // in the Schreyer order we always know that the multiplied
3349  // module monomial strat->P.sig gives the leading monomial of
3350  // the corresponding principal syzygy
3351  // => we do not need to compute the "real" syzygy completely
3352  poly help = p_Copy(strat->sig[ps],currRing);
3353  p_ExpVectorAdd (help,strat->P.p,currRing);
3354  Q.sig = p_Add_q(Q.sig,help,currRing);
3355  //printf("%d. SYZ ",i+1);
3356  //pWrite(strat->syz[i]);
3357  Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3358  i = posInSyz(strat, Q.sig);
3359  enterSyz(Q, strat, i);
3360  }
3361  }
3362  }
3363  // deg - idx - lp/rp
3364  // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3365  if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3366  {
3367  int cmp = pGetComp(strat->P.sig);
3368  unsigned max_cmp = IDELEMS(F);
3369  int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3370  p_GetExpV (strat->P.p,vv,currRing);
3371  LObject Q;
3372  int pos;
3373  int idx = __p_GetComp(strat->P.sig,currRing);
3374  //printf("++ -- adding syzygies -- ++\n");
3375  // if new element is the first one in this index
3376  if (strat->currIdx < idx)
3377  {
3378  for (int i=0; i<strat->sl; ++i)
3379  {
3380  Q.sig = p_Copy(strat->P.sig,currRing);
3381  p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3382  poly help = p_Copy(strat->sig[i],currRing);
3383  p_ExpVectorAdd(help,strat->P.p,currRing);
3384  Q.sig = p_Add_q(Q.sig,help,currRing);
3385  //pWrite(Q.sig);
3386  pos = posInSyz(strat, Q.sig);
3387  enterSyz(Q, strat, pos);
3388  }
3389  strat->currIdx = idx;
3390  }
3391  else
3392  {
3393  // if the element is not the first one in the given index we build all
3394  // possible syzygies with elements of higher index
3395  for (unsigned i=cmp+1; i<=max_cmp; ++i)
3396  {
3397  pos = -1;
3398  for (int j=0; j<strat->sl; ++j)
3399  {
3400  if (__p_GetComp(strat->sig[j],currRing) == i)
3401  {
3402  pos = j;
3403  break;
3404  }
3405  }
3406  if (pos != -1)
3407  {
3408  Q.sig = p_One(currRing);
3409  p_SetExpV(Q.sig, vv, currRing);
3410  // F->m[i-1] corresponds to index i
3411  p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3412  p_SetComp(Q.sig, i, currRing);
3413  poly help = p_Copy(strat->P.sig,currRing);
3414  p_ExpVectorAdd(help,strat->S[pos],currRing);
3415  Q.sig = p_Add_q(Q.sig,help,currRing);
3416  if (strat->sbaOrder == 0)
3417  {
3418  if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3419  {
3420  pos = posInSyz(strat, Q.sig);
3421  enterSyz(Q, strat, pos);
3422  }
3423  }
3424  else
3425  {
3426  pos = posInSyz(strat, Q.sig);
3427  enterSyz(Q, strat, pos);
3428  }
3429  }
3430  }
3431  //printf("++ -- done adding syzygies -- ++\n");
3432  }
3433  }
3434 //#if 1
3435 #if DEBUGF50
3436  printf("---------------------------\n");
3437  Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3438  PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3439  PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3440 #endif
3441  /*
3442  if (newrules)
3443  {
3444  newrules = FALSE;
3445  }
3446  */
3447 #if 0
3448  int pl=pLength(strat->P.p);
3449  if (pl==1)
3450  {
3451  //if (TEST_OPT_PROT)
3452  //PrintS("<1>");
3453  }
3454  else if (pl==2)
3455  {
3456  //if (TEST_OPT_PROT)
3457  //PrintS("<2>");
3458  }
3459 #endif
3460  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3461 // Print("[%d]",hilbeledeg);
3462  kDeleteLcm(&strat->P);
3463  if (strat->sl>srmax) srmax = strat->sl;
3464  }
3465  else
3466  {
3467  case_when_red_result_changed:
3468  // adds signature of the zero reduction to
3469  // strat->syz. This is the leading term of
3470  // syzygy and can be used in syzCriterion()
3471  // the signature is added if and only if the
3472  // pair was not detected by the rewritten criterion in strat->red = redSig
3473  if (red_result!=2)
3474  {
3475 #if SBA_PRINT_ZERO_REDUCTIONS
3476  zeroreductions++;
3477 #endif
3478  if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3479  {
3480  //Catch the case when p = 0, sig = 0
3481  }
3482  else
3483  {
3484  int pos = posInSyz(strat, strat->P.sig);
3485  enterSyz(strat->P, strat, pos);
3486  //#if 1
3487  #ifdef DEBUGF5
3488  Print("ADDING STUFF TO SYZ : ");
3489  //pWrite(strat->P.p);
3490  pWrite(strat->P.sig);
3491  #endif
3492  }
3493  }
3494  if (strat->P.p1 == NULL && strat->minim > 0)
3495  {
3496  p_Delete(&strat->P.p2, currRing, strat->tailRing);
3497  }
3498  }
3499 
3500 #ifdef KDEBUG
3501  memset(&(strat->P), 0, sizeof(strat->P));
3502 #endif /* KDEBUG */
3503  kTest_TS(strat);
3504  }
3505  #if 0
3506  if(strat->sigdrop)
3507  printf("\nSigDrop!\n");
3508  else
3509  printf("\nEnded with no SigDrop\n");
3510  #endif
3511 // Clean strat->P for the next sba call
3512  if(rField_is_Ring(currRing) && strat->sigdrop)
3513  {
3514  //This is used to know how many elements can we directly add to S in the next run
3515  if(strat->P.sig != NULL)
3516  strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3517  //else we already set it at the beggining of the loop
3518  #ifdef KDEBUG
3519  memset(&(strat->P), 0, sizeof(strat->P));
3520  #endif /* KDEBUG */
3521  }
3522 #ifdef KDEBUG
3523  if (TEST_OPT_DEBUG) messageSets(strat);
3524 #endif /* KDEBUG */
3525 
3526  if (TEST_OPT_SB_1)
3527  {
3528  if(!rField_is_Ring(currRing))
3529  {
3530  int k=1;
3531  int j;
3532  while(k<=strat->sl)
3533  {
3534  j=0;
3535  loop
3536  {
3537  if (j>=k) break;
3538  clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3539  j++;
3540  }
3541  k++;
3542  }
3543  }
3544  }
3545  /* complete reduction of the standard basis--------- */
3546  if (TEST_OPT_REDSB)
3547  {
3548  completeReduce(strat);
3549  if (strat->completeReduce_retry)
3550  {
3551  // completeReduce needed larger exponents, retry
3552  // to reduce with S (instead of T)
3553  // and in currRing (instead of strat->tailRing)
3554 #ifdef HAVE_TAIL_RING
3555  if(currRing->bitmask>strat->tailRing->bitmask)
3556  {
3557  strat->completeReduce_retry=FALSE;
3558  cleanT(strat);strat->tailRing=currRing;
3559  int i;
3560  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3561  completeReduce(strat);
3562  }
3563  if (strat->completeReduce_retry)
3564 #endif
3565  Werror("exponent bound is %ld",currRing->bitmask);
3566  }
3567  }
3568  else if (TEST_OPT_PROT) PrintLn();
3569 
3570 #if SBA_PRINT_SIZE_SYZ
3571  // that is correct, syzl is counting one too far
3572  size_syz = strat->syzl;
3573 #endif
3574 // if (TEST_OPT_WEIGHTM)
3575 // {
3576 // pRestoreDegProcs(pFDegOld, pLDegOld);
3577 // if (ecartWeights)
3578 // {
3579 // omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3580 // ecartWeights=NULL;
3581 // }
3582 // }
3583  if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3584  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3585 #if SBA_PRINT_SIZE_G
3586  size_g_non_red = IDELEMS(strat->Shdl);
3587 #endif
3588  if(!rField_is_Ring(currRing))
3589  exitSba(strat);
3590  // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3591  #ifdef HAVE_RINGS
3592  int k;
3594  {
3595  //for(k = strat->sl;k>=0;k--)
3596  // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3597  k = strat->Ll;
3598  #if 1
3599  // 1 - adds just the unused ones, 0 - adds everthing
3600  for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3601  {
3602  //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);
3603  deleteInL(strat->L,&strat->Ll,k,strat);
3604  }
3605  #endif
3606  //for(int kk = strat->sl;kk>=0;kk--)
3607  // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3608  //idPrint(strat->Shdl);
3609  //printf("\nk = %i\n",k);
3610  for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3611  {
3612  //printf("\nAdded k = %i\n",k);
3613  strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3614  //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3615  }
3616  }
3617  // 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
3618  #if 0
3619  if(strat->sigdrop && rField_is_Ring(currRing))
3620  {
3621  for(k=strat->sl;k>=0;k--)
3622  {
3623  printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3624  if(strat->sig[k] == NULL)
3625  strat->sig[k] = pCopy(strat->sig[k-1]);
3626  }
3627  }
3628  #endif
3629  #endif
3630  //Never do this - you will damage S
3631  //idSkipZeroes(strat->Shdl);
3632  //idPrint(strat->Shdl);
3633 
3634  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3635  {
3636  rChangeCurrRing (currRingOld);
3637  F0 = idrMoveR (F1, sRing, currRing);
3638  strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3639  rChangeCurrRing (sRing);
3641  exitSba(strat);
3642  rChangeCurrRing (currRingOld);
3643  if(strat->tailRing == sRing)
3644  strat->tailRing = currRing;
3645  rDelete (sRing);
3646  }
3647  if(rField_is_Ring(currRing) && !strat->sigdrop)
3648  id_DelDiv(strat->Shdl, currRing);
3649  if(!rField_is_Ring(currRing))
3650  id_DelDiv(strat->Shdl, currRing);
3651  idSkipZeroes(strat->Shdl);
3652  idTest(strat->Shdl);
3653 
3654 #if SBA_PRINT_SIZE_G
3655  size_g = IDELEMS(strat->Shdl);
3656 #endif
3657 #ifdef DEBUGF5
3658  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3659  int oo = 0;
3660  while (oo<IDELEMS(strat->Shdl))
3661  {
3662  printf(" %d. ",oo+1);
3663  pWrite(pHead(strat->Shdl->m[oo]));
3664  oo++;
3665  }
3666 #endif
3667 #if SBA_PRINT_ZERO_REDUCTIONS
3668  printf("----------------------------------------------------------\n");
3669  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3670  zeroreductions = 0;
3671 #endif
3672 #if SBA_PRINT_REDUCTION_STEPS
3673  printf("----------------------------------------------------------\n");
3674  printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3675 #endif
3676 #if SBA_PRINT_OPERATIONS
3677  printf("OPERATIONS: %ld\n",sba_operations);
3678 #endif
3679 #if SBA_PRINT_REDUCTION_STEPS
3680  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3681  printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3682 #endif
3683 #if SBA_PRINT_OPERATIONS
3684  printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3685 #endif
3686 #if SBA_PRINT_REDUCTION_STEPS
3687  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3688  printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3689  sba_interreduction_steps = 0;
3690  sba_reduction_steps = 0;
3691 #endif
3692 #if SBA_PRINT_OPERATIONS
3693  printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3694  sba_interreduction_operations = 0;
3695  sba_operations = 0;
3696 #endif
3697 #if SBA_PRINT_SIZE_G
3698  printf("----------------------------------------------------------\n");
3699  printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3700  size_g = 0;
3701  size_g_non_red = 0;
3702 #endif
3703 #if SBA_PRINT_SIZE_SYZ
3704  printf("SIZE OF SYZ: %ld\n",size_syz);
3705  printf("----------------------------------------------------------\n");
3706  size_syz = 0;
3707 #endif
3708 #if SBA_PRINT_PRODUCT_CRITERION
3709  printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3710  product_criterion = 0;
3711 #endif
3712  return (strat->Shdl);
3713 }
3714 
3715 poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3716 {
3717  assume(q!=NULL);
3718  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3719 
3720 // lazy_reduce flags: can be combined by |
3721 //#define KSTD_NF_LAZY 1
3722  // do only a reduction of the leading term
3723 //#define KSTD_NF_NONORM 4
3724  // only global: avoid normalization, return a multiply of NF
3725  poly p;
3726 
3727  //if ((idIs0(F))&&(Q==NULL))
3728  // return pCopy(q); /*F=0*/
3729  //strat->ak = idRankFreeModule(F);
3730  /*- creating temp data structures------------------- -*/
3731  BITSET save1;
3732  SI_SAVE_OPT1(save1);
3734  initBuchMoraCrit(strat);
3735  strat->initEcart = initEcartBBA;
3736 #ifdef HAVE_SHIFTBBA
3737  if (rIsLPRing(currRing))
3738  {
3739  strat->enterS = enterSBbaShift;
3740  }
3741  else
3742 #endif
3743  {
3744  strat->enterS = enterSBba;
3745  }
3746 #ifndef NO_BUCKETS
3748 #endif
3749  /*- set S -*/
3750  strat->sl = -1;
3751  /*- init local data struct.---------------------------------------- -*/
3752  /*Shdl=*/initS(F,Q,strat);
3753  /*- compute------------------------------------------------------- -*/
3754  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3755  //{
3756  // for (i=strat->sl;i>=0;i--)
3757  // pNorm(strat->S[i]);
3758  //}
3759  kTest(strat);
3760  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3761  if (BVERBOSE(23)) kDebugPrint(strat);
3762  int max_ind;
3763  p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3764  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3765  {
3766  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3768  {
3769  p = redtailBba_Z(p,max_ind,strat);
3770  }
3771  else if (rField_is_Ring(currRing))
3772  {
3773  p = redtailBba_Ring(p,max_ind,strat);
3774  }
3775  else
3776  {
3778  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3779  }
3780  }
3781  /*- release temp data------------------------------- -*/
3782  assume(strat->L==NULL); /* strat->L unused */
3783  assume(strat->B==NULL); /* strat->B unused */
3784  omFree(strat->sevS);
3785  omFree(strat->ecartS);
3786  assume(strat->T==NULL);//omfree(strat->T);
3787  assume(strat->sevT==NULL);//omfree(strat->sevT);
3788  assume(strat->R==NULL);//omfree(strat->R);
3789  omfree(strat->S_2_R);
3790  omfree(strat->fromQ);
3791  idDelete(&strat->Shdl);
3792  SI_RESTORE_OPT1(save1);
3793  if (TEST_OPT_PROT) PrintLn();
3794  return p;
3795 }
3796 
3797 poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3798 {
3799  assume(q!=NULL);
3800  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3801 
3802 // lazy_reduce flags: can be combined by |
3803 //#define KSTD_NF_LAZY 1
3804  // do only a reduction of the leading term
3805 //#define KSTD_NF_NONORM 4
3806  // only global: avoid normalization, return a multiply of NF
3807  poly p;
3808 
3809  //if ((idIs0(F))&&(Q==NULL))
3810  // return pCopy(q); /*F=0*/
3811  //strat->ak = idRankFreeModule(F);
3812  /*- creating temp data structures------------------- -*/
3813  BITSET save1;
3814  SI_SAVE_OPT1(save1);
3816  initBuchMoraCrit(strat);
3817  strat->initEcart = initEcartBBA;
3818  strat->enterS = enterSBba;
3819 #ifndef NO_BUCKETS
3821 #endif
3822  /*- set S -*/
3823  strat->sl = -1;
3824  /*- init local data struct.---------------------------------------- -*/
3825  /*Shdl=*/initS(F,Q,strat);
3826  /*- compute------------------------------------------------------- -*/
3827  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3828  //{
3829  // for (i=strat->sl;i>=0;i--)
3830  // pNorm(strat->S[i]);
3831  //}
3832  kTest(strat);
3833  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3834  if (BVERBOSE(23)) kDebugPrint(strat);
3835  int max_ind;
3836  p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3837  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3838  {
3839  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3841  {
3842  p = redtailBba_Z(p,max_ind,strat);
3843  }
3844  else if (rField_is_Ring(currRing))
3845  {
3846  p = redtailBba_Ring(p,max_ind,strat);
3847  }
3848  else
3849  {
3851  p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3852  //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3853  }
3854  }
3855  /*- release temp data------------------------------- -*/
3856  assume(strat->L==NULL); /* strat->L unused */
3857  assume(strat->B==NULL); /* strat->B unused */
3858  omFree(strat->sevS);
3859  omFree(strat->ecartS);
3860  assume(strat->T==NULL);//omfree(strat->T);
3861  assume(strat->sevT==NULL);//omfree(strat->sevT);
3862  assume(strat->R==NULL);//omfree(strat->R);
3863  omfree(strat->S_2_R);
3864  omfree(strat->fromQ);
3865  idDelete(&strat->Shdl);
3866  SI_RESTORE_OPT1(save1);
3867  if (TEST_OPT_PROT) PrintLn();
3868  return p;
3869 }
3870 
3871 ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3872 {
3873  assume(!idIs0(q));
3874  assume(!(idIs0(F)&&(Q==NULL)));
3875 // lazy_reduce flags: can be combined by |
3876 //#define KSTD_NF_LAZY 1
3877  // do only a reduction of the leading term
3878 //#define KSTD_NF_NONORM 4
3879  // only global: avoid normalization, return a multiply of NF
3880  poly p;
3881  int i;
3882  ideal res;
3883  int max_ind;
3884 
3885  //if (idIs0(q))
3886  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3887  //if ((idIs0(F))&&(Q==NULL))
3888  // return idCopy(q); /*F=0*/
3889  //strat->ak = idRankFreeModule(F);
3890  /*- creating temp data structures------------------- -*/
3891  BITSET save1;
3892  SI_SAVE_OPT1(save1);
3894  initBuchMoraCrit(strat);
3895  strat->initEcart = initEcartBBA;
3896 #ifdef HAVE_SHIFTBBA
3897  if (rIsLPRing(currRing))
3898  {
3899  strat->enterS = enterSBbaShift;
3900  }
3901  else
3902 #endif
3903  {
3904  strat->enterS = enterSBba;
3905  }
3906  /*- set S -*/
3907  strat->sl = -1;
3908 #ifndef NO_BUCKETS
3910 #endif
3911  /*- init local data struct.---------------------------------------- -*/
3912  /*Shdl=*/initS(F,Q,strat);
3913  /*- compute------------------------------------------------------- -*/
3914  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3915  for (i=IDELEMS(q)-1; i>=0; i--)
3916  {
3917  if (q->m[i]!=NULL)
3918  {
3919  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3920  p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3921  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3922  {
3923  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3925  {
3926  p = redtailBba_Z(p,max_ind,strat);
3927  }
3928  else if (rField_is_Ring(currRing))
3929  {
3930  p = redtailBba_Ring(p,max_ind,strat);
3931  }
3932  else
3933  {
3935  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3936  }
3937  }
3938  res->m[i]=p;
3939  }
3940  //else
3941  // res->m[i]=NULL;
3942  }
3943  /*- release temp data------------------------------- -*/
3944  assume(strat->L==NULL); /* strat->L unused */
3945  assume(strat->B==NULL); /* strat->B unused */
3946  omFree(strat->sevS);
3947  omFree(strat->ecartS);
3948  assume(strat->T==NULL);//omfree(strat->T);
3949  assume(strat->sevT==NULL);//omfree(strat->sevT);
3950  assume(strat->R==NULL);//omfree(strat->R);
3951  omfree(strat->S_2_R);
3952  omfree(strat->fromQ);
3953  idDelete(&strat->Shdl);
3954  SI_RESTORE_OPT1(save1);
3955  if (TEST_OPT_PROT) PrintLn();
3956  return res;
3957 }
3958 
3959 ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3960 {
3961  assume(!idIs0(q));
3962  assume(!(idIs0(F)&&(Q==NULL)));
3963 // lazy_reduce flags: can be combined by |
3964 //#define KSTD_NF_LAZY 1
3965  // do only a reduction of the leading term
3966 //#define KSTD_NF_NONORM 4
3967  // only global: avoid normalization, return a multiply of NF
3968  poly p;
3969  int i;
3970  ideal res;
3971  int max_ind;
3972 
3973  //if (idIs0(q))
3974  // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3975  //if ((idIs0(F))&&(Q==NULL))
3976  // return idCopy(q); /*F=0*/
3977  //strat->ak = idRankFreeModule(F);
3978  /*- creating temp data structures------------------- -*/
3979  BITSET save1;
3980  SI_SAVE_OPT1(save1);
3982  initBuchMoraCrit(strat);
3983  strat->initEcart = initEcartBBA;
3984  strat->enterS = enterSBba;
3985  /*- set S -*/
3986  strat->sl = -1;
3987 #ifndef NO_BUCKETS
3989 #endif
3990  /*- init local data struct.---------------------------------------- -*/
3991  /*Shdl=*/initS(F,Q,strat);
3992  /*- compute------------------------------------------------------- -*/
3993  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3994  for (i=IDELEMS(q)-1; i>=0; i--)
3995  {
3996  if (q->m[i]!=NULL)
3997  {
3998  if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3999  p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
4000  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4001  {
4002  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4004  {
4005  p = redtailBba_Z(p,max_ind,strat);
4006  }
4007  else if (rField_is_Ring(currRing))
4008  {
4009  p = redtailBba_Ring(p,max_ind,strat);
4010  }
4011  else
4012  {
4014  p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4015  }
4016  }
4017  res->m[i]=p;
4018  }
4019  //else
4020  // res->m[i]=NULL;
4021  }
4022  /*- release temp data------------------------------- -*/
4023  assume(strat->L==NULL); /* strat->L unused */
4024  assume(strat->B==NULL); /* strat->B unused */
4025  omFree(strat->sevS);
4026  omFree(strat->ecartS);
4027  assume(strat->T==NULL);//omfree(strat->T);
4028  assume(strat->sevT==NULL);//omfree(strat->sevT);
4029  assume(strat->R==NULL);//omfree(strat->R);
4030  omfree(strat->S_2_R);
4031  omfree(strat->fromQ);
4032  idDelete(&strat->Shdl);
4033  SI_RESTORE_OPT1(save1);
4034  if (TEST_OPT_PROT) PrintLn();
4035  return res;
4036 }
4037 
4038 #if F5C
4039 /*********************************************************************
4040 * interrreduction step of the signature-based algorithm:
4041 * 1. all strat->S are interpreted as new critical pairs
4042 * 2. those pairs need to be completely reduced by the usual (non sig-
4043 * safe) reduction process (including tail reductions)
4044 * 3. strat->S and strat->T are completely new computed in these steps
4045 ********************************************************************/
4046 void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
4047  int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
4048  intvec *w,intvec *hilb )
4049 {
4050  int Ll_old, red_result = 1;
4051  int pos = 0;
4052  hilbeledeg=1;
4053  hilbcount=0;
4054  minimcnt=0;
4055  srmax = 0; // strat->sl is 0 at this point
4056  reduc = olddeg = lrmax = 0;
4057  // we cannot use strat->T anymore
4058  //cleanT(strat);
4059  //strat->tl = -1;
4060  Ll_old = strat->Ll;
4061  while (strat->tl >= 0)
4062  {
4063  if(!strat->T[strat->tl].is_redundant)
4064  {
4065  LObject h;
4066  h.p = strat->T[strat->tl].p;
4067  h.tailRing = strat->T[strat->tl].tailRing;
4068  h.t_p = strat->T[strat->tl].t_p;
4069  if (h.p!=NULL)
4070  {
4071  if (currRing->OrdSgn==-1)
4072  {
4073  cancelunit(&h);
4074  deleteHC(&h, strat);
4075  }
4076  if (h.p!=NULL)
4077  {
4079  {
4080  h.pCleardenom(); // also does remove Content
4081  }
4082  else
4083  {
4084  h.pNorm();
4085  }
4086  strat->initEcart(&h);
4088  pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4089  else
4090  pos = strat->Ll+1;
4091  h.sev = pGetShortExpVector(h.p);
4092  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4093  }
4094  }
4095  }
4096  strat->tl--;
4097  }
4098  strat->sl = -1;
4099 #if 0
4100 //#ifdef HAVE_TAIL_RING
4101  if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4102  kStratInitChangeTailRing(strat);
4103 #endif
4104  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
4105  //strat->sl = -1;
4106  /* picks the last element from the lazyset L */
4107  while (strat->Ll>Ll_old)
4108  {
4109  strat->P = strat->L[strat->Ll];
4110  strat->Ll--;
4111 //#if 1
4112 #ifdef DEBUGF5
4113  PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4114  PrintS("-------------------------------------------------\n");
4115  pWrite(pHead(strat->P.p));
4116  pWrite(pHead(strat->P.p1));
4117  pWrite(pHead(strat->P.p2));
4118  printf("%d\n",strat->tl);
4119  PrintS("-------------------------------------------------\n");
4120 #endif
4121  if (pNext(strat->P.p) == strat->tail)
4122  {
4123  // deletes the short spoly
4124  if (rField_is_Ring(currRing))
4125  pLmDelete(strat->P.p);
4126  else
4127  pLmFree(strat->P.p);
4128 
4129  // TODO: needs some masking
4130  // TODO: masking needs to vanish once the signature
4131  // sutff is completely implemented
4132  strat->P.p = NULL;
4133  poly m1 = NULL, m2 = NULL;
4134 
4135  // check that spoly creation is ok
4136  while (strat->tailRing != currRing &&
4137  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4138  {
4139  assume(m1 == NULL && m2 == NULL);
4140  // if not, change to a ring where exponents are at least
4141  // large enough
4142  if (!kStratChangeTailRing(strat))
4143  {
4144  WerrorS("OVERFLOW...");
4145  break;
4146  }
4147  }
4148  // create the real one
4149  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4150  strat->tailRing, m1, m2, strat->R);
4151  }
4152  else if (strat->P.p1 == NULL)
4153  {
4154  if (strat->minim > 0)
4155  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4156  // for input polys, prepare reduction
4157  if(!rField_is_Ring(currRing))
4158  strat->P.PrepareRed(strat->use_buckets);
4159  }
4160 
4161  if (strat->P.p == NULL && strat->P.t_p == NULL)
4162  {
4163  red_result = 0;
4164  }
4165  else
4166  {
4167  if (TEST_OPT_PROT)
4168  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4169  &olddeg,&reduc,strat, red_result);
4170 
4171 #ifdef DEBUGF5
4172  PrintS("Poly before red: ");
4173  pWrite(strat->P.p);
4174 #endif
4175  /* complete reduction of the element chosen from L */
4176  red_result = strat->red2(&strat->P,strat);
4177  if (errorreported) break;
4178  }
4179 
4180  if (strat->overflow)
4181  {
4182  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4183  }
4184 
4185  // reduction to non-zero new poly
4186  if (red_result == 1)
4187  {
4188  // get the polynomial (canonicalize bucket, make sure P.p is set)
4189  strat->P.GetP(strat->lmBin);
4190  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4191  // but now, for entering S, T, we reset it
4192  // in the inhomogeneous case: FDeg == pFDeg
4193  if (strat->homog) strat->initEcart(&(strat->P));
4194 
4195  /* statistic */
4196  if (TEST_OPT_PROT) PrintS("s");
4197  int pos;
4198  #if 1
4199  if(!rField_is_Ring(currRing))
4200  pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4201  else
4202  pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4203  #else
4204  pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4205  #endif
4206  // reduce the tail and normalize poly
4207  // in the ring case we cannot expect LC(f) = 1,
4208 #if F5CTAILRED
4209  BOOLEAN withT = TRUE;
4211  {
4212  strat->P.pCleardenom();
4214  {
4215  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4216  strat->P.pCleardenom();
4217  }
4218  }
4219  else
4220  {
4221  strat->P.pNorm();
4223  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4224  }
4225 #endif
4226 #ifdef KDEBUG
4227  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4228 #endif /* KDEBUG */
4229 
4230  // min_std stuff
4231  if ((strat->P.p1==NULL) && (strat->minim>0))
4232  {
4233  if (strat->minim==1)
4234  {
4235  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4236  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4237  }
4238  else
4239  {
4240  strat->M->m[minimcnt]=strat->P.p2;
4241  strat->P.p2=NULL;
4242  }
4243  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4244  pNext(strat->M->m[minimcnt])
4245  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4246  strat->tailRing, currRing,
4247  currRing->PolyBin);
4248  minimcnt++;
4249  }
4250 
4251  // enter into S, L, and T
4252  // here we need to recompute new signatures, but those are trivial ones
4253  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4254  {
4255  enterT(strat->P, strat);
4256  // posInS only depends on the leading term
4257  strat->enterS(strat->P, pos, strat, strat->tl);
4258 //#if 1
4259 #ifdef DEBUGF5
4260  PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4261  pWrite(pHead(strat->S[strat->sl]));
4262  pWrite(strat->sig[strat->sl]);
4263 #endif
4264  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4265  }
4266  // Print("[%d]",hilbeledeg);
4267  kDeleteLcm(&strat->P);
4268  if (strat->sl>srmax) srmax = strat->sl;
4269  }
4270  else
4271  {
4272  // adds signature of the zero reduction to
4273  // strat->syz. This is the leading term of
4274  // syzygy and can be used in syzCriterion()
4275  // the signature is added if and only if the
4276  // pair was not detected by the rewritten criterion in strat->red = redSig
4277  if (strat->P.p1 == NULL && strat->minim > 0)
4278  {
4279  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4280  }
4281  }
4282 
4283 #ifdef KDEBUG
4284  memset(&(strat->P), 0, sizeof(strat->P));
4285 #endif /* KDEBUG */
4286  }
4287  int cc = 0;
4288  while (cc<strat->tl+1)
4289  {
4290  strat->T[cc].sig = pOne();
4291  p_SetComp(strat->T[cc].sig,cc+1,currRing);
4292  strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4293  strat->sig[cc] = strat->T[cc].sig;
4294  strat->sevSig[cc] = strat->T[cc].sevSig;
4295  strat->T[cc].is_sigsafe = TRUE;
4296  cc++;
4297  }
4298  strat->max_lower_index = strat->tl;
4299  // set current signature index of upcoming iteration step
4300  // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4301  // the corresponding syzygy rules correctly
4302  strat->currIdx = cc+1;
4303  for (int cd=strat->Ll; cd>=0; cd--)
4304  {
4305  p_SetComp(strat->L[cd].sig,cc+1,currRing);
4306  cc++;
4307  }
4308  for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4309  strat->Shdl->m[cc] = NULL;
4310  #if 0
4311  printf("\nAfter f5c sorting\n");
4312  for(int i=0;i<=strat->sl;i++)
4313  pWrite(pHead(strat->S[i]));
4314  getchar();
4315  #endif
4316 //#if 1
4317 #if DEBUGF5
4318  PrintS("------------------- STRAT S ---------------------\n");
4319  cc = 0;
4320  while (cc<strat->tl+1)
4321  {
4322  pWrite(pHead(strat->S[cc]));
4323  pWrite(strat->sig[cc]);
4324  printf("- - - - - -\n");
4325  cc++;
4326  }
4327  PrintS("-------------------------------------------------\n");
4328  PrintS("------------------- STRAT T ---------------------\n");
4329  cc = 0;
4330  while (cc<strat->tl+1)
4331  {
4332  pWrite(pHead(strat->T[cc].p));
4333  pWrite(strat->T[cc].sig);
4334  printf("- - - - - -\n");
4335  cc++;
4336  }
4337  PrintS("-------------------------------------------------\n");
4338  PrintS("------------------- STRAT L ---------------------\n");
4339  cc = 0;
4340  while (cc<strat->Ll+1)
4341  {
4342  pWrite(pHead(strat->L[cc].p));
4343  pWrite(pHead(strat->L[cc].p1));
4344  pWrite(pHead(strat->L[cc].p2));
4345  pWrite(strat->L[cc].sig);
4346  printf("- - - - - -\n");
4347  cc++;
4348  }
4349  PrintS("-------------------------------------------------\n");
4350  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4351 #endif
4352 
4353 }
4354 #endif
4355 
4356 /* shiftgb stuff */
4357 #ifdef HAVE_SHIFTBBA
4358 ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
4359 {
4360  int red_result = 1;
4361  int olddeg,reduc;
4362  int hilbeledeg=1,hilbcount=0,minimcnt=0;
4363  BOOLEAN withT = TRUE; // currently only T contains the shifts
4364  BITSET save;
4365  SI_SAVE_OPT1(save);
4366 
4367  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4369  initBuchMoraPosRing(strat);
4370  else
4371  initBuchMoraPos(strat);
4372  initHilbCrit(F,Q,&hilb,strat);
4373  initBba(strat);
4374  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4375  /*Shdl=*/initBuchMora(F, Q,strat);
4376  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4377  reduc = olddeg = 0;
4378 
4379 #ifndef NO_BUCKETS
4380  if (!TEST_OPT_NOT_BUCKETS)
4381  strat->use_buckets = 1;
4382 #endif
4383  // redtailBBa against T for inhomogenous input
4384  // if (!TEST_OPT_OLDSTD)
4385  // withT = ! strat->homog;
4386 
4387  // strat->posInT = posInT_pLength;
4388  kTest_TS(strat);
4389 
4390 #ifdef HAVE_TAIL_RING
4391  // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4392  // kStratInitChangeTailRing(strat);
4393  strat->tailRing=currRing;
4394 #endif
4395  if (BVERBOSE(23))
4396  {
4397  if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4398  if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4399  kDebugPrint(strat);
4400  }
4401 
4402 #ifdef KDEBUG
4403  //kDebugPrint(strat);
4404 #endif
4405  /* compute------------------------------------------------------- */
4406  while (strat->Ll >= 0)
4407  {
4408  #ifdef KDEBUG
4409  if (TEST_OPT_DEBUG) messageSets(strat);
4410  #endif
4411  if (siCntrlc)
4412  {
4413  while (strat->Ll >= 0)
4414  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4415  strat->noClearS=TRUE;
4416  }
4417  if (TEST_OPT_DEGBOUND
4418  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4419  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4420  {
4421  /*
4422  *stops computation if
4423  * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4424  *a predefined number Kstd1_deg
4425  */
4426  while ((strat->Ll >= 0)
4427  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4428  && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4429  || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4430  )
4431  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4432  if (strat->Ll<0) break;
4433  else strat->noClearS=TRUE;
4434  }
4435  if (strat->Ll== 0) strat->interpt=TRUE;
4436  /* picks the last element from the lazyset L */
4437  strat->P = strat->L[strat->Ll];
4438  strat->Ll--;
4439 
4440  if (pNext(strat->P.p) == strat->tail)
4441  {
4442  // deletes the short spoly
4443  if (rField_is_Ring(currRing))
4444  pLmDelete(strat->P.p);
4445  else
4446  pLmFree(strat->P.p);
4447  strat->P.p = NULL;
4448  poly m1 = NULL, m2 = NULL;
4449 
4450  // check that spoly creation is ok
4451  while (strat->tailRing != currRing &&
4452  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4453  {
4454  assume(m1 == NULL && m2 == NULL);
4455  // if not, change to a ring where exponents are at least
4456  // large enough
4457  if (!kStratChangeTailRing(strat))
4458  {
4459  WerrorS("OVERFLOW...");
4460  break;
4461  }
4462  }
4463  // create the real one
4464  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4465  strat->tailRing, m1, m2, strat->R);
4466  }
4467  else if (strat->P.p1 == NULL)
4468  {
4469  if (strat->minim > 0)
4470  strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4471  // for input polys, prepare reduction
4472  strat->P.PrepareRed(strat->use_buckets);
4473  }
4474 
4475  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4476  {
4477  red_result = 0;
4478  }
4479  else
4480  {
4481  if (TEST_OPT_PROT)
4482  message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4483  &olddeg,&reduc,strat, red_result);
4484 
4485  /* reduction of the element chosen from L */
4486  red_result = strat->red(&strat->P,strat);
4487  if (errorreported) break;
4488  }
4489 
4490  if (strat->overflow)
4491  {
4492  if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4493  }
4494 
4495  // reduction to non-zero new poly
4496  if (red_result == 1)
4497  {
4498  // get the polynomial (canonicalize bucket, make sure P.p is set)
4499  strat->P.GetP(strat->lmBin);
4500  // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4501  // but now, for entering S, T, we reset it
4502  // in the inhomogeneous case: FDeg == pFDeg
4503  if (strat->homog) strat->initEcart(&(strat->P));
4504 
4505  /* statistic */
4506  if (TEST_OPT_PROT) PrintS("s");
4507 
4508  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4509 
4510  // reduce the tail and normalize poly
4511  // in the ring case we cannot expect LC(f) = 1,
4512  strat->redTailChange=FALSE;
4513 
4514  /* if we are computing over Z we always want to try and cut down
4515  * the coefficients in the tail terms */
4517  {
4518  redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4519  }
4520 
4522  {
4523  strat->P.pCleardenom();
4525  {
4526  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4527  strat->P.pCleardenom();
4528  if (strat->redTailChange)
4529  {
4530  strat->P.t_p=NULL;
4531  strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4532  }
4533  }
4534  }
4535  else
4536  {
4537  strat->P.pNorm();
4539  {
4540  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4541  if (strat->redTailChange)
4542  {
4543  strat->P.t_p=NULL;
4544  strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4545  }
4546  }
4547  }
4548 
4549 #ifdef KDEBUG
4550  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4551 #endif /* KDEBUG */
4552 
4553  // min_std stuff
4554  if ((strat->P.p1==NULL) && (strat->minim>0))
4555  {
4556  if (strat->minim==1)
4557  {
4558  strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4559  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4560  }
4561  else
4562  {
4563  strat->M->m[minimcnt]=strat->P.p2;
4564  strat->P.p2=NULL;
4565  }
4566  if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4567  pNext(strat->M->m[minimcnt])
4568  = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4569  strat->tailRing, currRing,
4570  currRing->PolyBin);
4571  minimcnt++;
4572  }
4573 
4574 
4575  // enter into S, L, and T
4576  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4577  {
4578  enterT(strat->P, strat);
4579  enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4580  // posInS only depends on the leading term
4581  strat->enterS(strat->P, pos, strat, strat->tl);
4582  if (!strat->rightGB)
4583  enterTShift(strat->P, strat);
4584  }
4585 
4586  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4587 // Print("[%d]",hilbeledeg);
4588  kDeleteLcm(&strat->P);
4589  if (strat->s_poly!=NULL)
4590  {
4591  // the only valid entries are: strat->P.p,
4592  // strat->tailRing (read-only, keep it)
4593  // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4594  if (strat->s_poly(strat))
4595  {
4596  // we are called AFTER enterS, i.e. if we change P
4597  // we have to add it also to S/T
4598  // and add pairs
4599  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4600  enterT(strat->P, strat);
4601  enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4602  strat->enterS(strat->P, pos, strat, strat->tl);
4603  if (!strat->rightGB)
4604  enterTShift(strat->P,strat);
4605  }
4606  }
4607  }
4608  else if (strat->P.p1 == NULL && strat->minim > 0)
4609  {
4610  p_Delete(&strat->P.p2, currRing, strat->tailRing);
4611  }
4612 #ifdef KDEBUG
4613  memset(&(strat->P), 0, sizeof(strat->P));
4614 #endif /* KDEBUG */
4615  kTest_TS(strat);
4616  }
4617 #ifdef KDEBUG
4618  if (TEST_OPT_DEBUG) messageSets(strat);
4619 #endif /* KDEBUG */
4620  /* shift case: look for elt's in S such that they are divisible by elt in T */
4621  if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4622  {
4623  if(!rField_is_Ring(currRing))
4624  {
4625  for (int k = 0; k <= strat->sl; ++k)
4626  {
4627  if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4628  for (int j = 0; j<=strat->tl; ++j)
4629  {
4630  if (strat->T[j].p!=NULL)
4631  {
4632  // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4633  assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4634  assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4635  if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4636  {
4637  if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4638  { // check whether LM is different
4639  deleteInS(k, strat);
4640  --k;
4641  break;
4642  }
4643  }
4644  }
4645  }
4646  }
4647  }
4648  }
4649  /* complete reduction of the standard basis--------- */
4650  if (TEST_OPT_REDSB)
4651  {
4652  completeReduce(strat, TRUE); //shift: withT = TRUE
4653  if (strat->completeReduce_retry)
4654  {
4655  // completeReduce needed larger exponents, retry
4656  // to reduce with S (instead of T)
4657  // and in currRing (instead of strat->tailRing)
4658 #ifdef HAVE_TAIL_RING
4659  if(currRing->bitmask>strat->tailRing->bitmask)
4660  {
4661  strat->completeReduce_retry=FALSE;
4662  cleanT(strat);strat->tailRing=currRing;
4663  int i;
4664  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4665  WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4666  completeReduce(strat);
4667  }
4668  if (strat->completeReduce_retry)
4669 #endif
4670  Werror("exponent bound is %ld",currRing->bitmask);
4671  }
4672  }
4673  else if (TEST_OPT_PROT) PrintLn();
4674 
4675  /* release temp data-------------------------------- */
4676  exitBuchMora(strat);
4677  /* postprocessing for GB over ZZ --------------------*/
4678  if (!errorreported)
4679  {
4680  if(rField_is_Z(currRing))
4681  {
4682  for(int i = 0;i<=strat->sl;i++)
4683  {
4684  if(!nGreaterZero(pGetCoeff(strat->S[i])))
4685  {
4686  strat->S[i] = pNeg(strat->S[i]);
4687  }
4688  }
4689  finalReduceByMon(strat);
4690  for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4691  {
4692  if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4693  {
4694  strat->S[i] = pNeg(strat->Shdl->m[i]);
4695  }
4696  }
4697  }
4698  //else if (rField_is_Ring(currRing))
4699  // finalReduceByMon(strat);
4700  }
4701 // if (TEST_OPT_WEIGHTM)
4702 // {
4703 // pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4704 // if (ecartWeights)
4705 // {
4706 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4707 // ecartWeights=NULL;
4708 // }
4709 // }
4710  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4711  SI_RESTORE_OPT1(save);
4712  /* postprocessing for GB over Q-rings ------------------*/
4713  if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4714 
4715  idTest(strat->Shdl);
4716 
4717  return (strat->Shdl);
4718 }
4719 #endif
4720 
4721 #ifdef HAVE_SHIFTBBA
4722 ideal rightgb(ideal F, ideal Q)
4723 {
4725  assume(idIsInV(F));
4726  ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4727  idSkipZeroes(RS); // is this even necessary?
4728  assume(idIsInV(RS));
4729  return(RS);
4730 }
4731 #endif
4732 
4733 /*2
4734 *reduces h with elements from T choosing the first possible
4735 * element in t with respect to the given pDivisibleBy
4736 */
4737 #ifdef HAVE_SHIFTBBA
4739 {
4740  if (h->IsNull()) return 0;
4741 
4742  int at, reddeg,d;
4743  int pass = 0;
4744  int j = 0;
4745 
4746  if (! strat->homog)
4747  {
4748  d = h->GetpFDeg() + h->ecart;
4749  reddeg = strat->LazyDegree+d;
4750  }
4751  h->SetShortExpVector();
4752  loop
4753  {
4754  j = kFindDivisibleByInT(strat, h);
4755  if (j < 0)
4756  {
4757  h->SetDegStuffReturnLDeg(strat->LDegLast);
4758  return 1;
4759  }
4760 
4761  if (!TEST_OPT_INTSTRATEGY)
4762  strat->T[j].pNorm();
4763 #ifdef KDEBUG
4764  if (TEST_OPT_DEBUG)
4765  {
4766  PrintS("reduce ");
4767  h->wrp();
4768  PrintS(" with ");
4769  strat->T[j].wrp();
4770  }
4771 #endif
4772  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
4773 
4774 #ifdef KDEBUG
4775  if (TEST_OPT_DEBUG)
4776  {
4777  PrintS("\nto ");
4778  wrp(h->p);
4779  PrintLn();
4780  }
4781 #endif
4782  if (h->IsNull())
4783  {
4784  kDeleteLcm(h);
4785  h->Clear();
4786  return 0;
4787  }
4788  h->SetShortExpVector();
4789 
4790 #if 0
4791  if ((strat->syzComp!=0) && !strat->honey)
4792  {
4793  if ((strat->syzComp>0) &&
4794  (h->Comp() > strat->syzComp))
4795  {
4796  assume(h->MinComp() > strat->syzComp);
4797 #ifdef KDEBUG
4798  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4799 #endif
4800  if (strat->homog)
4801  h->SetDegStuffReturnLDeg(strat->LDegLast);
4802  return -2;
4803  }
4804  }
4805 #endif
4806  if (!strat->homog)
4807  {
4808  if (!TEST_OPT_OLDSTD && strat->honey)
4809  {
4810  h->SetpFDeg();
4811  if (strat->T[j].ecart <= h->ecart)
4812  h->ecart = d - h->GetpFDeg();
4813  else
4814  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4815 
4816  d = h->GetpFDeg() + h->ecart;
4817  }
4818  else
4819  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4820  /*- try to reduce the s-polynomial -*/
4821  pass++;
4822  /*
4823  *test whether the polynomial should go to the lazyset L
4824  *-if the degree jumps
4825  *-if the number of pre-defined reductions jumps
4826  */
4827  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4828  && ((d >= reddeg) || (pass > strat->LazyPass)))
4829  {
4830  h->SetLmCurrRing();
4831  if (strat->posInLDependsOnLength)
4832  h->SetLength(strat->length_pLength);
4833  at = strat->posInL(strat->L,strat->Ll,h,strat);
4834  if (at <= strat->Ll)
4835  {
4836  //int dummy=strat->sl;
4837  /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4838  //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4839  if (kFindDivisibleByInT(strat, h) < 0)
4840  return 1;
4841  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4842 #ifdef KDEBUG
4843  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4844 #endif
4845  h->Clear();
4846  return -1;
4847  }
4848  }
4849  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4850  {
4851  reddeg = d+1;
4852  Print(".%d",d);mflush();
4853  }
4854  }
4855  }
4856 }
4857 #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:4738
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:2271
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3715
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:1905
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:2749
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2390
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1698
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1328
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kstd2.cc:1578
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition: kstd2.cc:1122
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2142
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1160
static long ind2(long arg)
Definition: kstd2.cc:532
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11833
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:4046
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:3797
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:4358
ideal rightgb(ideal F, ideal Q)
Definition: kstd2.cc:4722
void initSbaPos(kStrategy strat)
Definition: kutil.cc:10184
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7784
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10073
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9652
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9450
void enterTShift(LObject p, kStrategy strat, int atT)
Definition: kutil.cc:13450
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:7452
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9730
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:9900
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7907
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11294
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
Definition: kutil.cc:11415
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:11036
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13420
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:10158
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:7838
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:8248
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10286
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10807
void cleanT(kStrategy strat)
Definition: kutil.cc:569
int posInSyz(const kStrategy strat, poly sig)
Definition: kutil.cc:6018
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition: kutil.cc:9359
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:294
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10401
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:10361
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition: kutil.cc:7005
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1295
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11387
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9748
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10613
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9986
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:11112
void messageSets(kStrategy strat)
Definition: kutil.cc:7857
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:6136
void initEcartBBA(TObject *h)
Definition: kutil.cc:1392
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9201
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7825
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:11201
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9101
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9813
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:886
#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:389
#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:1297
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4897
poly p_One(const ring r)
Definition: p_polys.cc:1313
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1469
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3812
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:938
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1116
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1413
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1725
static void p_SetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1546
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:490
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:249
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:235
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1582
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1931
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:471
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1897
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:903
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:1522
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1053
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:757
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:848
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:248
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:261
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:450
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 gcd(int a, int b)
Definition: walkSupport.cc:836