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