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