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