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