My Project
kstd1.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT:
6 */
7 
8 // TODO: why the following is here instead of mod2.h???
9 
10 
11 // define if buckets should be used
12 #define MORA_USE_BUCKETS
13 
14 #define PRE_INTEGER_CHECK 0
15 
16 #include "kernel/mod2.h"
17 
18 #include "misc/options.h"
19 #include "misc/intvec.h"
20 
21 #include "polys/weight.h"
22 #include "kernel/polys.h"
23 
24 #include "kernel/GBEngine/kutil.h"
25 #include "kernel/GBEngine/kstd1.h"
26 #include "kernel/GBEngine/khstd.h"
28 #include "kernel/ideals.h"
29 
30 //#include "ipprint.h"
31 
32 #ifdef HAVE_PLURAL
33 #include "polys/nc/nc.h"
34 #include "polys/nc/sca.h"
35 #include "kernel/GBEngine/nc.h"
36 #endif
37 
39 
40 #ifdef HAVE_SHIFTBBA
41 #include "polys/shiftop.h"
42 #endif
43 
44 /* the list of all options which give a warning by test */
46  |Sy_bit(OPT_REDSB) /* 1 */
47  |Sy_bit(OPT_NOT_SUGAR) /* 3 */
48  |Sy_bit(OPT_INTERRUPT) /* 4 */
49  |Sy_bit(OPT_SUGARCRIT) /* 5 */
52  |Sy_bit(OPT_FASTHC) /* 10 */
53  |Sy_bit(OPT_INTSTRATEGY) /* 26 */
54  |Sy_bit(OPT_INFREDTAIL) /* 28 */
55  |Sy_bit(OPT_NOTREGULARITY) /* 30 */
56  |Sy_bit(OPT_WEIGHTM); /* 31 */
57 
58 /* the list of all options which may be used by option and test */
59 /* defintion of ALL options: libpolys/misc/options.h */
61  |Sy_bit(1)
62  |Sy_bit(2) // obachman 10/00: replaced by notBucket
63  |Sy_bit(3)
64  |Sy_bit(4)
65  |Sy_bit(5)
66  |Sy_bit(6)
67 // |Sy_bit(7) obachman 11/00 tossed: 12/00 used for redThrough
68  |Sy_bit(7) // OPT_REDTHROUGH
69  |Sy_bit(8) // obachman 11/00 tossed -> motsak 2011 experimental: OPT_NO_SYZ_MINIM
70  |Sy_bit(9)
71  |Sy_bit(10)
72  |Sy_bit(11)
73  |Sy_bit(12)
74  |Sy_bit(13)
75  |Sy_bit(14)
76  |Sy_bit(15)
77  |Sy_bit(16)
78  |Sy_bit(17)
79  |Sy_bit(18)
80  |Sy_bit(19)
81 // |Sy_bit(20) obachman 11/00 tossed: 12/00 used for redOldStd
83  |Sy_bit(21)
84  |Sy_bit(22)
85  /*|Sy_bit(23)*/
86  /*|Sy_bit(24)*/
89  |Sy_bit(27)
90  |Sy_bit(28)
91  |Sy_bit(29)
92  |Sy_bit(30)
93  |Sy_bit(31);
94 
95 //static BOOLEAN posInLOldFlag;
96  /*FALSE, if posInL == posInL10*/
97 // returns TRUE if mora should use buckets, false otherwise
98 static BOOLEAN kMoraUseBucket(kStrategy strat);
99 
100 static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
101 {
102 // if (strat->ak == 0 && !rIsSyzIndexRing(currRing))
103  strat->length_pLength = TRUE;
104 // else
105 // strat->length_pLength = FALSE;
106 
107  if ((ldeg == pLDeg0c /*&& !rIsSyzIndexRing(currRing)*/) ||
108  (ldeg == pLDeg0 && strat->ak == 0))
109  {
110  strat->LDegLast = TRUE;
111  }
112  else
113  {
114  strat->LDegLast = FALSE;
115  }
116 }
117 
118 
119 static int doRed (LObject* h, TObject* with,BOOLEAN intoT,kStrategy strat, bool redMoraNF)
120 {
121  int ret;
122 #if KDEBUG > 0
123  kTest_L(h);
124  kTest_T(with);
125 #endif
126  // Hmmm ... why do we do this -- polys from T should already be normalized
128  with->pNorm();
129 #ifdef KDEBUG
130  if (TEST_OPT_DEBUG)
131  {
132  PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
133  }
134 #endif
135  if (intoT)
136  {
137  // need to do it exacly like this: otherwise
138  // we might get errors
139  LObject L= *h;
140  L.Copy();
141  h->GetP();
142  h->length=h->pLength=pLength(h->p);
143  ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, NULL, strat);
144  if (ret)
145  {
146  if (ret < 0) return ret;
147  if (h->tailRing != strat->tailRing)
148  h->ShallowCopyDelete(strat->tailRing,
149  pGetShallowCopyDeleteProc(h->tailRing,
150  strat->tailRing));
151  }
153  enterT_strong(*h,strat);
154  else
155  enterT(*h,strat);
156  *h = L;
157  }
158  else
159  ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, NULL, strat);
160 #ifdef KDEBUG
161  if (TEST_OPT_DEBUG)
162  {
163  PrintS("to ");h->wrp();PrintLn();
164  }
165 #endif
166  return ret;
167 }
168 
170 {
171  int i,at,ei,li,ii;
172  int j = 0;
173  int pass = 0;
174  long d,reddeg;
175 
176  d = h->GetpFDeg()+ h->ecart;
177  reddeg = strat->LazyDegree+d;
178  h->SetShortExpVector();
179  loop
180  {
181  j = kFindDivisibleByInT(strat, h);
182  if (j < 0)
183  {
184  if (strat->honey) h->SetLength(strat->length_pLength);
185  return 1;
186  }
187 
188  ei = strat->T[j].ecart;
189  ii = j;
190 
191  if (ei > h->ecart && ii < strat->tl)
192  {
193  li = strat->T[j].length;
194  // the polynomial to reduce with (up to the moment) is;
195  // pi with ecart ei and length li
196  // look for one with smaller ecart
197  i = j;
198  loop
199  {
200  /*- takes the first possible with respect to ecart -*/
201  i++;
202 #if 1
203  if (i > strat->tl) break;
204  if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
205  strat->T[i].length < li))
206  &&
207  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing))
208 #else
209  j = kFindDivisibleByInT(strat, h, i);
210  if (j < 0) break;
211  i = j;
212  if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
213  strat->T[i].length < li))
214 #endif
215  {
216  // the polynomial to reduce with is now
217  ii = i;
218  ei = strat->T[i].ecart;
219  if (ei <= h->ecart) break;
220  li = strat->T[i].length;
221  }
222  }
223  }
224 
225  // end of search: have to reduce with pi
226  if (ei > h->ecart)
227  {
228  // It is not possible to reduce h with smaller ecart;
229  // if possible h goes to the lazy-set L,i.e
230  // if its position in L would be not the last one
231  strat->fromT = TRUE;
232  if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
233  {
234  h->SetLmCurrRing();
235  if (strat->honey && strat->posInLDependsOnLength)
236  h->SetLength(strat->length_pLength);
237  assume(h->FDeg == h->pFDeg());
238  at = strat->posInL(strat->L,strat->Ll,h,strat);
239  if (at <= strat->Ll)
240  {
241  /*- h will not become the next element to reduce -*/
242  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
243 #ifdef KDEBUG
244  if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
245 #endif
246  h->Clear();
247  strat->fromT = FALSE;
248  return -1;
249  }
250  }
251  }
252 
253  // now we finally can reduce
254  doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
255  strat->fromT=FALSE;
256 
257  // are we done ???
258  if (h->IsNull())
259  {
261  kDeleteLcm(h);
262  h->Clear();
263  return 0;
264  }
265  if (TEST_OPT_IDLIFT)
266  {
267  if (h->p!=NULL)
268  {
269  if(p_GetComp(h->p,currRing)>strat->syzComp)
270  {
271  h->Delete();
272  return 0;
273  }
274  }
275  else if (h->t_p!=NULL)
276  {
277  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
278  {
279  h->Delete();
280  return 0;
281  }
282  }
283  }
284  #if 0
285  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
286  {
287  if (h->p!=NULL)
288  {
289  if(p_GetComp(h->p,currRing)>strat->syzComp)
290  {
291  return 1;
292  }
293  }
294  else if (h->t_p!=NULL)
295  {
296  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
297  {
298  return 1;
299  }
300  }
301  }
302  #endif
303 
304  // done ? NO!
305  h->SetShortExpVector();
306  h->SetpFDeg();
307  if (strat->honey)
308  {
309  if (ei <= h->ecart)
310  h->ecart = d-h->GetpFDeg();
311  else
312  h->ecart = d-h->GetpFDeg()+ei-h->ecart;
313  }
314  else
315  // this has the side effect of setting h->length
316  h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
317 #if 0
318  if (strat->syzComp!=0)
319  {
320  if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
321  {
322  assume(h->MinComp() > strat->syzComp);
323  if (strat->honey) h->SetLength();
324 #ifdef KDEBUG
325  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
326 #endif
327  return -2;
328  }
329  }
330 #endif
331  /*- try to reduce the s-polynomial -*/
332  pass++;
333  d = h->GetpFDeg()+h->ecart;
334  /*
335  *test whether the polynomial should go to the lazyset L
336  *-if the degree jumps
337  *-if the number of pre-defined reductions jumps
338  */
339  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
340  && ((d >= reddeg) || (pass > strat->LazyPass)))
341  {
342  h->SetLmCurrRing();
343  if (strat->honey && strat->posInLDependsOnLength)
344  h->SetLength(strat->length_pLength);
345  assume(h->FDeg == h->pFDeg());
346  at = strat->posInL(strat->L,strat->Ll,h,strat);
347  if (at <= strat->Ll)
348  {
349  int dummy=strat->sl;
350  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
351  {
352  if (strat->honey && !strat->posInLDependsOnLength)
353  h->SetLength(strat->length_pLength);
354  return 1;
355  }
356  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
357 #ifdef KDEBUG
358  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
359 #endif
360  h->Clear();
361  return -1;
362  }
363  }
364  else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
365  {
366  Print(".%ld",d);mflush();
367  reddeg = d+1;
368  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
369  {
370  strat->overflow=TRUE;
371  //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
372  h->GetP();
373  at = strat->posInL(strat->L,strat->Ll,h,strat);
374  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
375  h->Clear();
376  return -1;
377  }
378  }
379  }
380 }
381 
382 #ifdef HAVE_RINGS
384 {
385  int i,at,ei,li,ii;
386  int j = 0;
387  int pass = 0;
388  long d,reddeg;
389 
390  d = h->GetpFDeg()+ h->ecart;
391  reddeg = strat->LazyDegree+d;
392  h->SetShortExpVector();
393  loop
394  {
395  j = kFindDivisibleByInT(strat, h);
396  if (j < 0)
397  {
398  // over ZZ: cleanup coefficients by complete reduction with monomials
399  postReduceByMon(h, strat);
400  if(h->p == NULL)
401  {
402  kDeleteLcm(h);
403  h->Clear();
404  return 0;
405  }
406  if (strat->honey) h->SetLength(strat->length_pLength);
407  if(strat->tl >= 0)
408  h->i_r1 = strat->tl;
409  else
410  h->i_r1 = -1;
411  if (h->GetLmTailRing() == NULL)
412  {
413  kDeleteLcm(h);
414  h->Clear();
415  return 0;
416  }
417  return 1;
418  }
419 
420  ei = strat->T[j].ecart;
421  ii = j;
422  if (ei > h->ecart && ii < strat->tl)
423  {
424  li = strat->T[j].length;
425  // the polynomial to reduce with (up to the moment) is;
426  // pi with ecart ei and length li
427  // look for one with smaller ecart
428  i = j;
429  loop
430  {
431  /*- takes the first possible with respect to ecart -*/
432  i++;
433 #if 1
434  if (i > strat->tl) break;
435  if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
436  strat->T[i].length < li))
437  &&
438  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
439  &&
440  n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
441 #else
442  j = kFindDivisibleByInT(strat, h, i);
443  if (j < 0) break;
444  i = j;
445  if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
446  strat->T[i].length < li))
447 #endif
448  {
449  // the polynomial to reduce with is now
450  ii = i;
451  ei = strat->T[i].ecart;
452  if (ei <= h->ecart) break;
453  li = strat->T[i].length;
454  }
455  }
456  }
457 
458  // end of search: have to reduce with pi
459  if (ei > h->ecart)
460  {
461  // It is not possible to reduce h with smaller ecart;
462  // if possible h goes to the lazy-set L,i.e
463  // if its position in L would be not the last one
464  strat->fromT = TRUE;
465  if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
466  {
467  h->SetLmCurrRing();
468  if (strat->honey && strat->posInLDependsOnLength)
469  h->SetLength(strat->length_pLength);
470  assume(h->FDeg == h->pFDeg());
471  at = strat->posInL(strat->L,strat->Ll,h,strat);
472  if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
473  {
474  /*- h will not become the next element to reduce -*/
475  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
476  #ifdef KDEBUG
477  if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
478  #endif
479  h->Clear();
480  strat->fromT = FALSE;
481  return -1;
482  }
483  }
484  doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
485  }
486  else
487  {
488  // now we finally can reduce
489  doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
490  }
491  strat->fromT=FALSE;
492  // are we done ???
493  if (h->IsNull())
494  {
495  kDeleteLcm(h);
496  h->Clear();
497  return 0;
498  }
499 
500  // NO!
501  h->SetShortExpVector();
502  h->SetpFDeg();
503  if (strat->honey)
504  {
505  if (ei <= h->ecart)
506  h->ecart = d-h->GetpFDeg();
507  else
508  h->ecart = d-h->GetpFDeg()+ei-h->ecart;
509  }
510  else
511  // this has the side effect of setting h->length
512  h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
513  /*- try to reduce the s-polynomial -*/
514  pass++;
515  d = h->GetpFDeg()+h->ecart;
516  /*
517  *test whether the polynomial should go to the lazyset L
518  *-if the degree jumps
519  *-if the number of pre-defined reductions jumps
520  */
521  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
522  && ((d >= reddeg) || (pass > strat->LazyPass)))
523  {
524  h->SetLmCurrRing();
525  if (strat->honey && strat->posInLDependsOnLength)
526  h->SetLength(strat->length_pLength);
527  assume(h->FDeg == h->pFDeg());
528  at = strat->posInL(strat->L,strat->Ll,h,strat);
529  if (at <= strat->Ll)
530  {
531  int dummy=strat->sl;
532  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
533  {
534  if (strat->honey && !strat->posInLDependsOnLength)
535  h->SetLength(strat->length_pLength);
536  return 1;
537  }
538  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
539 #ifdef KDEBUG
540  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
541 #endif
542  h->Clear();
543  return -1;
544  }
545  }
546  else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
547  {
548  Print(".%ld",d);mflush();
549  reddeg = d+1;
550  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
551  {
552  strat->overflow=TRUE;
553  //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
554  h->GetP();
555  at = strat->posInL(strat->L,strat->Ll,h,strat);
556  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
557  h->Clear();
558  return -1;
559  }
560  }
561  }
562 }
563 
565 {
566  int i,at,ei,li,ii;
567  int j = 0;
568  int pass = 0;
569  long d,reddeg;
570  int docoeffred = 0;
571  poly T0p = strat->T[0].p;
572  int T0ecart = strat->T[0].ecart;
573 
574 
575  d = h->GetpFDeg()+ h->ecart;
576  reddeg = strat->LazyDegree+d;
577  h->SetShortExpVector();
578  if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2) {
579  docoeffred = 1;
580  }
581  loop
582  {
583  /* cut down the lead coefficients, only possible if the degree of
584  * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
585  * we ask for the length of T[0] to be <= 2 */
586  if (docoeffred) {
587  j = kTestDivisibleByT0_Z(strat, h);
588  if (j == 0 && n_DivBy(pGetCoeff(h->p), pGetCoeff(T0p), currRing->cf) == FALSE
589  && T0ecart <= h->ecart) {
590  /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
591  * => we try to cut down the lead coefficient at least */
592  /* first copy T[j] in order to multiply it with a coefficient later on */
593  number mult, rest;
594  TObject tj = strat->T[0];
595  tj.Copy();
596  /* compute division with remainder of lc(h) and lc(T[j]) */
597  mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(T0p),
598  &rest, currRing->cf);
599  /* set corresponding new lead coefficient already. we do not
600  * remove the lead term in ksReducePolyLC, but only apply
601  * a lead coefficient reduction */
602  tj.Mult_nn(mult);
603  ksReducePolyLC(h, &tj, NULL, &rest, strat);
604  tj.Delete();
605  tj.Clear();
606  }
607  }
608  j = kFindDivisibleByInT(strat, h);
609  if (j < 0)
610  {
611  // over ZZ: cleanup coefficients by complete reduction with monomials
612  postReduceByMon(h, strat);
613  if(h->p == NULL)
614  {
615  kDeleteLcm(h);
616  h->Clear();
617  return 0;
618  }
619  if (strat->honey) h->SetLength(strat->length_pLength);
620  if(strat->tl >= 0)
621  h->i_r1 = strat->tl;
622  else
623  h->i_r1 = -1;
624  if (h->GetLmTailRing() == NULL)
625  {
626  kDeleteLcm(h);
627  h->Clear();
628  return 0;
629  }
630  return 1;
631  }
632 
633  ei = strat->T[j].ecart;
634  ii = j;
635 #if 1
636  if (ei > h->ecart && ii < strat->tl)
637  {
638  li = strat->T[j].length;
639  // the polynomial to reduce with (up to the moment) is;
640  // pi with ecart ei and length li
641  // look for one with smaller ecart
642  i = j;
643  loop
644  {
645  /*- takes the first possible with respect to ecart -*/
646  i++;
647 #if 1
648  if (i > strat->tl) break;
649  if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
650  strat->T[i].length < li))
651  &&
652  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
653  &&
654  n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
655 #else
656  j = kFindDivisibleByInT(strat, h, i);
657  if (j < 0) break;
658  i = j;
659  if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
660  strat->T[i].length < li))
661 #endif
662  {
663  // the polynomial to reduce with is now
664  ii = i;
665  ei = strat->T[i].ecart;
666  if (ei <= h->ecart) break;
667  li = strat->T[i].length;
668  }
669  }
670  }
671 #endif
672 
673  // end of search: have to reduce with pi
674  if (ei > h->ecart)
675  {
676  // It is not possible to reduce h with smaller ecart;
677  // if possible h goes to the lazy-set L,i.e
678  // if its position in L would be not the last one
679  strat->fromT = TRUE;
680  if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
681  {
682  h->SetLmCurrRing();
683  if (strat->honey && strat->posInLDependsOnLength)
684  h->SetLength(strat->length_pLength);
685  assume(h->FDeg == h->pFDeg());
686  at = strat->posInL(strat->L,strat->Ll,h,strat);
687  if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
688  {
689  /*- h will not become the next element to reduce -*/
690  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
691 #ifdef KDEBUG
692  if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
693 #endif
694  h->Clear();
695  strat->fromT = FALSE;
696  return -1;
697  }
698  }
699  doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
700  }
701  else
702  {
703  // now we finally can reduce
704  doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
705  }
706  strat->fromT=FALSE;
707  // are we done ???
708  if (h->IsNull())
709  {
710  kDeleteLcm(h);
711  h->Clear();
712  return 0;
713  }
714 
715  // NO!
716  h->SetShortExpVector();
717  h->SetpFDeg();
718  if (strat->honey)
719  {
720  if (ei <= h->ecart)
721  h->ecart = d-h->GetpFDeg();
722  else
723  h->ecart = d-h->GetpFDeg()+ei-h->ecart;
724  }
725  else
726  // this has the side effect of setting h->length
727  h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
728  /*- try to reduce the s-polynomial -*/
729  pass++;
730  d = h->GetpFDeg()+h->ecart;
731  /*
732  *test whether the polynomial should go to the lazyset L
733  *-if the degree jumps
734  *-if the number of pre-defined reductions jumps
735  */
736  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
737  && ((d >= reddeg) || (pass > strat->LazyPass)))
738  {
739  h->SetLmCurrRing();
740  if (strat->honey && strat->posInLDependsOnLength)
741  h->SetLength(strat->length_pLength);
742  assume(h->FDeg == h->pFDeg());
743  at = strat->posInL(strat->L,strat->Ll,h,strat);
744  if (at <= strat->Ll)
745  {
746  int dummy=strat->sl;
747  if (kFindDivisibleByInS(strat, &dummy, h) < 0)
748  {
749  if (strat->honey && !strat->posInLDependsOnLength)
750  h->SetLength(strat->length_pLength);
751  return 1;
752  }
753  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
754 #ifdef KDEBUG
755  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
756 #endif
757  h->Clear();
758  return -1;
759  }
760  }
761  else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
762  {
763  Print(".%ld",d);mflush();
764  reddeg = d+1;
765  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
766  {
767  strat->overflow=TRUE;
768  //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
769  h->GetP();
770  at = strat->posInL(strat->L,strat->Ll,h,strat);
771  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
772  h->Clear();
773  return -1;
774  }
775  }
776  }
777 }
778 #endif
779 
780 /*2
781 *reduces h with elements from T choosing the first possible
782 * element in t with respect to the given pDivisibleBy
783 */
785 {
786  if (h->IsNull()) return 0;
787 
788  int at;
789  long reddeg,d;
790  int pass = 0;
791  int j = 0;
792 
793  if (! strat->homog)
794  {
795  d = h->GetpFDeg() + h->ecart;
796  reddeg = strat->LazyDegree+d;
797  }
798  h->SetShortExpVector();
799  loop
800  {
801  j = kFindDivisibleByInT(strat, h);
802  if (j < 0)
803  {
804  h->SetDegStuffReturnLDeg(strat->LDegLast);
805  return 1;
806  }
807 
809  strat->T[j].pNorm();
810 #ifdef KDEBUG
811  if (TEST_OPT_DEBUG)
812  {
813  PrintS("reduce ");
814  h->wrp();
815  PrintS(" with ");
816  strat->T[j].wrp();
817  }
818 #endif
819  ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
820 #ifdef KDEBUG
821  if (TEST_OPT_DEBUG)
822  {
823  PrintS(" to ");
824  wrp(h->p);
825  PrintLn();
826  }
827 #endif
828  if (h->IsNull())
829  {
831  kDeleteLcm(h);
832  h->Clear();
833  return 0;
834  }
835  if (TEST_OPT_IDLIFT)
836  {
837  if (h->p!=NULL)
838  {
839  if(p_GetComp(h->p,currRing)>strat->syzComp)
840  {
841  h->Delete();
842  return 0;
843  }
844  }
845  else if (h->t_p!=NULL)
846  {
847  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
848  {
849  h->Delete();
850  return 0;
851  }
852  }
853  }
854  #if 0
855  else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
856  {
857  if (h->p!=NULL)
858  {
859  if(p_GetComp(h->p,currRing)>strat->syzComp)
860  {
861  return 1;
862  }
863  }
864  else if (h->t_p!=NULL)
865  {
866  if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
867  {
868  return 1;
869  }
870  }
871  }
872  #endif
873  h->SetShortExpVector();
874 
875 #if 0
876  if ((strat->syzComp!=0) && !strat->honey)
877  {
878  if ((strat->syzComp>0) &&
879  (h->Comp() > strat->syzComp))
880  {
881  assume(h->MinComp() > strat->syzComp);
882 #ifdef KDEBUG
883  if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
884 #endif
885  if (strat->homog)
886  h->SetDegStuffReturnLDeg(strat->LDegLast);
887  return -2;
888  }
889  }
890 #endif
891  if (!strat->homog)
892  {
893  if (!TEST_OPT_OLDSTD && strat->honey)
894  {
895  h->SetpFDeg();
896  if (strat->T[j].ecart <= h->ecart)
897  h->ecart = d - h->GetpFDeg();
898  else
899  h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
900 
901  d = h->GetpFDeg() + h->ecart;
902  }
903  else
904  d = h->SetDegStuffReturnLDeg(strat->LDegLast);
905  /*- try to reduce the s-polynomial -*/
906  pass++;
907  /*
908  *test whether the polynomial should go to the lazyset L
909  *-if the degree jumps
910  *-if the number of pre-defined reductions jumps
911  */
912  if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
913  && ((d >= reddeg) || (pass > strat->LazyPass)))
914  {
915  h->SetLmCurrRing();
916  if (strat->posInLDependsOnLength)
917  h->SetLength(strat->length_pLength);
918  at = strat->posInL(strat->L,strat->Ll,h,strat);
919  if (at <= strat->Ll)
920  {
921  int dummy=strat->sl;
922  if (kFindDivisibleByInS(strat,&dummy, h) < 0)
923  return 1;
924  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
925 #ifdef KDEBUG
926  if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
927 #endif
928  h->Clear();
929  return -1;
930  }
931  }
932  if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
933  {
934  reddeg = d+1;
935  Print(".%ld",d);mflush();
936  if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
937  {
938  strat->overflow=TRUE;
939  //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
940  h->GetP();
941  at = strat->posInL(strat->L,strat->Ll,h,strat);
942  enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
943  h->Clear();
944  return -1;
945  }
946  }
947  }
948  }
949 }
950 
951 /*2
952 * reduces h with elements from T choosing first possible
953 * element in T with respect to the given ecart
954 * used for computing normal forms outside kStd
955 */
956 static poly redMoraNF (poly h,kStrategy strat, int flag)
957 {
958  LObject H;
959  H.p = h;
960  int j = 0;
961  int z = 10;
962  int o = H.SetpFDeg();
963  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
964  if ((flag & 2) == 0) cancelunit(&H,TRUE);
965  H.sev = pGetShortExpVector(H.p);
966  unsigned long not_sev = ~ H.sev;
967  loop
968  {
969  if (j > strat->tl)
970  {
971  return H.p;
972  }
973  if (TEST_V_DEG_STOP)
974  {
975  if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
976  if (H.p==NULL) return NULL;
977  }
978  if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
979  )
980  {
981  /*- remember the found T-poly -*/
982  // poly pi = strat->T[j].p;
983  int ei = strat->T[j].ecart;
984  int li = strat->T[j].length;
985  int ii = j;
986  /*
987  * the polynomial to reduce with (up to the moment) is;
988  * pi with ecart ei and length li
989  */
990  loop
991  {
992  /*- look for a better one with respect to ecart -*/
993  /*- stop, if the ecart is small enough (<=ecart(H)) -*/
994  j++;
995  if (j > strat->tl) break;
996  if (ei <= H.ecart) break;
997  if (((strat->T[j].ecart < ei)
998  || ((strat->T[j].ecart == ei)
999  && (strat->T[j].length < li)))
1000  && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1001  )
1002  {
1003  /*
1004  * the polynomial to reduce with is now;
1005  */
1006  // pi = strat->T[j].p;
1007  ei = strat->T[j].ecart;
1008  li = strat->T[j].length;
1009  ii = j;
1010  }
1011  }
1012  /*
1013  * end of search: have to reduce with pi
1014  */
1015  z++;
1016  if (z>10)
1017  {
1018  pNormalize(H.p);
1019  z=0;
1020  }
1021  if ((ei > H.ecart) && (!strat->kHEdgeFound))
1022  {
1023  /*
1024  * It is not possible to reduce h with smaller ecart;
1025  * we have to reduce with bad ecart: H has to enter in T
1026  */
1027  doRed(&H,&(strat->T[ii]),TRUE,strat,TRUE);
1028  if (H.p == NULL)
1029  return NULL;
1030  }
1031  else
1032  {
1033  /*
1034  * we reduce with good ecart, h need not to be put to T
1035  */
1036  doRed(&H,&(strat->T[ii]),FALSE,strat,TRUE);
1037  if (H.p == NULL)
1038  return NULL;
1039  }
1040  /*- try to reduce the s-polynomial -*/
1041  o = H.SetpFDeg();
1042  if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1043  H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1044  j = 0;
1045  H.sev = pGetShortExpVector(H.p);
1046  not_sev = ~ H.sev;
1047  }
1048  else
1049  {
1050  j++;
1051  }
1052  }
1053 }
1054 
1055 #ifdef HAVE_RINGS
1056 static poly redMoraNFRing (poly h,kStrategy strat, int flag)
1057 {
1058  LObject H;
1059  H.p = h;
1060  int j0, j = 0;
1061  int z = 10;
1062  int docoeffred = 0;
1063  poly T0p = strat->T[0].p;
1064  int T0ecart = strat->T[0].ecart;
1065  int o = H.SetpFDeg();
1066  H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
1067  if ((flag & 2) == 0) cancelunit(&H,TRUE);
1068  H.sev = pGetShortExpVector(H.p);
1069  unsigned long not_sev = ~ H.sev;
1070  if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2) {
1071  docoeffred = 1;
1072  }
1073  loop
1074  {
1075  /* cut down the lead coefficients, only possible if the degree of
1076  * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
1077  * we ask for the length of T[0] to be <= 2 */
1078  if (docoeffred) {
1079  j0 = kTestDivisibleByT0_Z(strat, &H);
1080  if (j0 == 0 && n_DivBy(pGetCoeff(H.p), pGetCoeff(T0p), currRing->cf) == FALSE
1081  && T0ecart <= H.ecart) {
1082  /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
1083  * => we try to cut down the lead coefficient at least */
1084  /* first copy T[j0] in order to multiply it with a coefficient later on */
1085  number mult, rest;
1086  TObject tj = strat->T[0];
1087  tj.Copy();
1088  /* compute division with remainder of lc(h) and lc(T[j]) */
1089  mult = n_QuotRem(pGetCoeff(H.p), pGetCoeff(T0p),
1090  &rest, currRing->cf);
1091  /* set corresponding new lead coefficient already. we do not
1092  * remove the lead term in ksReducePolyLC, but only apply
1093  * a lead coefficient reduction */
1094  tj.Mult_nn(mult);
1095  ksReducePolyLC(&H, &tj, NULL, &rest, strat);
1096  tj.Delete();
1097  tj.Clear();
1098  }
1099  }
1100  if (j > strat->tl)
1101  {
1102  return H.p;
1103  }
1104  if (TEST_V_DEG_STOP)
1105  {
1106  if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
1107  if (H.p==NULL) return NULL;
1108  }
1109  if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1110  && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1111  )
1112  {
1113  /*- remember the found T-poly -*/
1114  // poly pi = strat->T[j].p;
1115  int ei = strat->T[j].ecart;
1116  int li = strat->T[j].length;
1117  int ii = j;
1118  /*
1119  * the polynomial to reduce with (up to the moment) is;
1120  * pi with ecart ei and length li
1121  */
1122  loop
1123  {
1124  /*- look for a better one with respect to ecart -*/
1125  /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1126  j++;
1127  if (j > strat->tl) break;
1128  if (ei <= H.ecart) break;
1129  if (((strat->T[j].ecart < ei)
1130  || ((strat->T[j].ecart == ei)
1131  && (strat->T[j].length < li)))
1132  && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1133  && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1134  )
1135  {
1136  /*
1137  * the polynomial to reduce with is now;
1138  */
1139  // pi = strat->T[j].p;
1140  ei = strat->T[j].ecart;
1141  li = strat->T[j].length;
1142  ii = j;
1143  }
1144  }
1145  /*
1146  * end of search: have to reduce with pi
1147  */
1148  z++;
1149  if (z>10)
1150  {
1151  pNormalize(H.p);
1152  z=0;
1153  }
1154  if ((ei > H.ecart) && (!strat->kHEdgeFound))
1155  {
1156  /*
1157  * It is not possible to reduce h with smaller ecart;
1158  * we have to reduce with bad ecart: H has to enter in T
1159  */
1160  doRed(&H,&(strat->T[ii]),TRUE,strat,TRUE);
1161  if (H.p == NULL)
1162  return NULL;
1163  }
1164  else
1165  {
1166  /*
1167  * we reduce with good ecart, h need not to be put to T
1168  */
1169  doRed(&H,&(strat->T[ii]),FALSE,strat,TRUE);
1170  if (H.p == NULL)
1171  return NULL;
1172  }
1173  /*- try to reduce the s-polynomial -*/
1174  o = H.SetpFDeg();
1175  if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1176  H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1177  j = 0;
1178  H.sev = pGetShortExpVector(H.p);
1179  not_sev = ~ H.sev;
1180  }
1181  else
1182  {
1183  j++;
1184  }
1185  }
1186 }
1187 #endif
1188 
1189 /*2
1190 *reorders L with respect to posInL
1191 */
1192 void reorderL(kStrategy strat)
1193 {
1194  int i,j,at;
1195  LObject p;
1196 
1197  for (i=1; i<=strat->Ll; i++)
1198  {
1199  at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
1200  if (at != i)
1201  {
1202  p = strat->L[i];
1203  for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
1204  strat->L[at] = p;
1205  }
1206  }
1207 }
1208 
1209 /*2
1210 *reorders T with respect to length
1211 */
1212 void reorderT(kStrategy strat)
1213 {
1214  int i,j,at;
1215  TObject p;
1216  unsigned long sev;
1217 
1218 
1219  for (i=1; i<=strat->tl; i++)
1220  {
1221  if (strat->T[i-1].length > strat->T[i].length)
1222  {
1223  p = strat->T[i];
1224  sev = strat->sevT[i];
1225  at = i-1;
1226  loop
1227  {
1228  at--;
1229  if (at < 0) break;
1230  if (strat->T[i].length > strat->T[at].length) break;
1231  }
1232  for (j = i-1; j>at; j--)
1233  {
1234  strat->T[j+1]=strat->T[j];
1235  strat->sevT[j+1]=strat->sevT[j];
1236  strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
1237  }
1238  strat->T[at+1]=p;
1239  strat->sevT[at+1] = sev;
1240  strat->R[p.i_r] = &(strat->T[at+1]);
1241  }
1242  }
1243 }
1244 
1245 /*2
1246 *looks whether exactly (currRing->N)-1 axis are used
1247 *returns last != 0 in this case
1248 *last is the (first) unused axis
1249 */
1250 void missingAxis (int* last,kStrategy strat)
1251 {
1252  int i = 0;
1253  int k = 0;
1254 
1255  *last = 0;
1257  {
1258  loop
1259  {
1260  i++;
1261  if (i > (currRing->N)) break;
1262  if (strat->NotUsedAxis[i])
1263  {
1264  *last = i;
1265  k++;
1266  }
1267  if (k>1)
1268  {
1269  *last = 0;
1270  break;
1271  }
1272  }
1273  }
1274 }
1275 
1276 /*2
1277 *last is the only non used axis, it looks
1278 *for a monomial in p being a pure power of this
1279 *variable and returns TRUE in this case
1280 *(*length) gives the length between the pure power and the leading term
1281 *(should be minimal)
1282 */
1283 BOOLEAN hasPurePower (const poly p,int last, int *length,kStrategy strat)
1284 {
1285  poly h;
1286  int i;
1287 
1288  if (pNext(p) == strat->tail)
1289  return FALSE;
1290  pp_Test(p, currRing, strat->tailRing);
1291  if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
1292  {
1293  i = p_IsPurePower(p, currRing);
1294  if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
1295  if (i == last)
1296  {
1297  *length = 0;
1298  return TRUE;
1299  }
1300  *length = 1;
1301  h = pNext(p);
1302  while (h != NULL)
1303  {
1304  i = p_IsPurePower(h, strat->tailRing);
1305  if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
1306  if (i==last) return TRUE;
1307  (*length)++;
1308  pIter(h);
1309  }
1310  }
1311  return FALSE;
1312 }
1313 
1315 {
1316  if (L->bucket != NULL)
1317  {
1318  poly p = L->GetP();
1319  return hasPurePower(p, last, length, strat);
1320  }
1321  else
1322  {
1323  return hasPurePower(L->p, last, length, strat);
1324  }
1325 }
1326 
1327 /*2
1328 * looks up the position of polynomial p in L
1329 * in the case of looking for the pure powers
1330 */
1331 int posInL10 (const LSet set,const int length, LObject* p,const kStrategy strat)
1332 {
1333  int j,dp,dL;
1334 
1335  if (length<0) return 0;
1336  if (hasPurePower(p,strat->lastAxis,&dp,strat))
1337  {
1338  int op= p->GetpFDeg() +p->ecart;
1339  for (j=length; j>=0; j--)
1340  {
1341  if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1342  return j+1;
1343  if (dp < dL)
1344  return j+1;
1345  if ((dp == dL)
1346  && (set[j].GetpFDeg()+set[j].ecart >= op))
1347  return j+1;
1348  }
1349  }
1350  j=length;
1351  loop
1352  {
1353  if (j<0) break;
1354  if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1355  j--;
1356  }
1357  return strat->posInLOld(set,j,p,strat);
1358 }
1359 
1360 
1361 /*2
1362 * computes the s-polynomials L[ ].p in L
1363 */
1364 void updateL(kStrategy strat)
1365 {
1366  LObject p;
1367  int dL;
1368  int j=strat->Ll;
1369  loop
1370  {
1371  if (j<0) break;
1372  if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1373  {
1374  p=strat->L[strat->Ll];
1375  strat->L[strat->Ll]=strat->L[j];
1376  strat->L[j]=p;
1377  break;
1378  }
1379  j--;
1380  }
1381  if (j<0)
1382  {
1383  j=strat->Ll;
1384  loop
1385  {
1386  if (j<0) break;
1387  if (pNext(strat->L[j].p) == strat->tail)
1388  {
1389  if (rField_is_Ring(currRing))
1390  pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1391  else
1392  pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1393  strat->L[j].p = NULL;
1394  poly m1 = NULL, m2 = NULL;
1395  // check that spoly creation is ok
1396  while (strat->tailRing != currRing &&
1397  !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1398  {
1399  assume(m1 == NULL && m2 == NULL);
1400  // if not, change to a ring where exponents are at least
1401  // large enough
1402  kStratChangeTailRing(strat);
1403  }
1404  /* create the real one */
1405  ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1406  strat->tailRing, m1, m2, strat->R);
1407 
1408  strat->L[j].SetLmCurrRing();
1409  if (!strat->honey)
1410  strat->initEcart(&strat->L[j]);
1411  else
1412  strat->L[j].SetLength(strat->length_pLength);
1413 
1414  BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1415 
1416  if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
1417 
1418  if (pp)
1419  {
1420  p=strat->L[strat->Ll];
1421  strat->L[strat->Ll]=strat->L[j];
1422  strat->L[j]=p;
1423  break;
1424  }
1425  }
1426  j--;
1427  }
1428  }
1429 }
1430 
1431 /*2
1432 * computes the s-polynomials L[ ].p in L and
1433 * cuts elements in L above noether
1434 */
1436 {
1437 
1438  int i = 0;
1439  kTest_TS(strat);
1440  while (i <= strat->Ll)
1441  {
1442  if (pNext(strat->L[i].p) == strat->tail)
1443  {
1444  /*- deletes the int spoly and computes -*/
1445  if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
1446  {
1447  if (rField_is_Ring(currRing))
1448  pLmDelete(strat->L[i].p);
1449  else
1450  pLmFree(strat->L[i].p);
1451  strat->L[i].p = NULL;
1452  }
1453  else
1454  {
1455  if (rField_is_Ring(currRing))
1456  pLmDelete(strat->L[i].p);
1457  else
1458  pLmFree(strat->L[i].p);
1459  strat->L[i].p = NULL;
1460  poly m1 = NULL, m2 = NULL;
1461  // check that spoly creation is ok
1462  while (strat->tailRing != currRing &&
1463  !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
1464  {
1465  assume(m1 == NULL && m2 == NULL);
1466  // if not, change to a ring where exponents are at least
1467  // large enough
1468  kStratChangeTailRing(strat);
1469  }
1470  /* create the real one */
1471  ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
1472  strat->tailRing, m1, m2, strat->R);
1473  if (! strat->L[i].IsNull())
1474  {
1475  strat->L[i].SetLmCurrRing();
1476  strat->L[i].SetpFDeg();
1477  strat->L[i].ecart
1478  = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
1479  if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
1480  }
1481  }
1482  }
1483  else
1484  deleteHC(&(strat->L[i]), strat);
1485  if (strat->L[i].IsNull())
1486  deleteInL(strat->L,&strat->Ll,i,strat);
1487  else
1488  {
1489 #ifdef KDEBUG
1490  kTest_L(&(strat->L[i]), strat->tailRing, TRUE, i, strat->T, strat->tl);
1491 #endif
1492  i++;
1493  }
1494  }
1495  kTest_TS(strat);
1496 }
1497 
1498 /*2
1499 * cuts in T above strat->kNoether and tries to cancel a unit
1500 * changes also S as S is a subset of T
1501 */
1502 void updateT(kStrategy strat)
1503 {
1504  int i = 0;
1505  LObject p;
1506 
1507  while (i <= strat->tl)
1508  {
1509  p = strat->T[i];
1510  deleteHC(&p,strat, TRUE);
1511  /*- tries to cancel a unit: -*/
1512  cancelunit(&p);
1513  if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
1514  p.pCleardenom();
1515  if (p.p != strat->T[i].p)
1516  {
1517  strat->sevT[i] = pGetShortExpVector(p.p);
1518  p.SetpFDeg();
1519  }
1520  strat->T[i] = p;
1521  i++;
1522  }
1523 }
1524 
1525 /*2
1526 * arranges red, pos and T if strat->kHEdgeFound (first time)
1527 */
1529 {
1530  if (strat->update)
1531  {
1532  kTest_TS(strat);
1533  strat->update = (strat->tl == -1);
1534  if (TEST_OPT_WEIGHTM)
1535  {
1536  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1537  if (strat->tailRing != currRing)
1538  {
1539  strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1540  strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1541  }
1542  int i;
1543  for (i=strat->Ll; i>=0; i--)
1544  {
1545  strat->L[i].SetpFDeg();
1546  }
1547  for (i=strat->tl; i>=0; i--)
1548  {
1549  strat->T[i].SetpFDeg();
1550  }
1551  if (ecartWeights)
1552  {
1553  omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1555  }
1556  }
1557  if (TEST_OPT_FASTHC)
1558  {
1559  strat->posInL = strat->posInLOld;
1560  strat->lastAxis = 0;
1561  }
1562  if (TEST_OPT_FINDET)
1563  return;
1564 
1566  {
1567  strat->red = redFirst;
1568  strat->use_buckets = kMoraUseBucket(strat);
1569  }
1570  updateT(strat);
1571 
1573  {
1574  strat->posInT = posInT2;
1575  reorderT(strat);
1576  }
1577  }
1578  kTest_TS(strat);
1579 }
1580 
1581 /*2
1582 *-puts p to the standardbasis s at position at
1583 *-reduces the tail of p if TEST_OPT_REDTAIL
1584 *-tries to cancel a unit
1585 *-HEckeTest
1586 * if TRUE
1587 * - decides about reduction-strategies
1588 * - computes noether
1589 * - stops computation if TEST_OPT_FINDET
1590 * - cuts the tails of the polynomials
1591 * in s,t and the elements in L above noether
1592 * and cancels units if possible
1593 * - reorders s,L
1594 */
1595 void enterSMora (LObject &p,int atS,kStrategy strat, int atR = -1)
1596 {
1597  enterSBba(p, atS, strat, atR);
1598  #ifdef KDEBUG
1599  if (TEST_OPT_DEBUG)
1600  {
1601  Print("new s%d:",atS);
1602  p_wrp(p.p,currRing,strat->tailRing);
1603  PrintLn();
1604  }
1605  #endif
1606  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1607  if (strat->kHEdgeFound)
1608  {
1609  if (newHEdge(strat))
1610  {
1611  firstUpdate(strat);
1612  if (TEST_OPT_FINDET)
1613  return;
1614 
1615  /*- cuts elements in L above noether and reorders L -*/
1616  updateLHC(strat);
1617  /*- reorders L with respect to posInL -*/
1618  reorderL(strat);
1619  }
1620  }
1621  else if (strat->kNoether!=NULL)
1622  strat->kHEdgeFound = TRUE;
1623  else if (TEST_OPT_FASTHC)
1624  {
1625  if (strat->posInLOldFlag)
1626  {
1627  missingAxis(&strat->lastAxis,strat);
1628  if (strat->lastAxis)
1629  {
1630  strat->posInLOld = strat->posInL;
1631  strat->posInLOldFlag = FALSE;
1632  strat->posInL = posInL10;
1633  strat->posInLDependsOnLength = TRUE;
1634  updateL(strat);
1635  reorderL(strat);
1636  }
1637  }
1638  else if (strat->lastAxis)
1639  updateL(strat);
1640  }
1641 }
1642 
1643 /*2
1644 *-puts p to the standardbasis s at position at
1645 *-HEckeTest
1646 * if TRUE
1647 * - computes noether
1648 */
1649 void enterSMoraNF (LObject &p, int atS,kStrategy strat, int atR = -1)
1650 {
1651  enterSBba(p, atS, strat, atR);
1652  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1653  if (strat->kHEdgeFound)
1654  newHEdge(strat);
1655  else if (strat->kNoether!=NULL)
1656  strat->kHEdgeFound = TRUE;
1657 }
1658 
1659 void initBba(kStrategy strat)
1660 {
1661  /* setting global variables ------------------- */
1662  strat->enterS = enterSBba;
1663  strat->red = redHoney;
1664  if (strat->honey)
1665  strat->red = redHoney;
1666  else if (currRing->pLexOrder && !strat->homog)
1667  strat->red = redLazy;
1668  else
1669  {
1670  strat->LazyPass *=4;
1671  strat->red = redHomog;
1672  }
1673  if (rField_is_Ring(currRing))
1674  {
1675  if (rField_is_Z(currRing))
1676  strat->red = redRing_Z;
1677  else
1678  strat->red = redRing;
1679  }
1680  if (TEST_OPT_IDLIFT)
1681  strat->red=redLiftstd;
1682  if (currRing->pLexOrder && strat->honey)
1683  strat->initEcart = initEcartNormal;
1684  else
1685  strat->initEcart = initEcartBBA;
1686  if (strat->honey)
1688  else
1690 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1691 // {
1692 // //interred machen Aenderung
1693 // strat->pOrigFDeg=pFDeg;
1694 // strat->pOrigLDeg=pLDeg;
1695 // //h=ggetid("ecart");
1696 // //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1697 // //{
1698 // // ecartWeights=iv2array(IDINTVEC(h));
1699 // //}
1700 // //else
1701 // {
1702 // ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1703 // /*uses automatic computation of the ecartWeights to set them*/
1704 // kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1705 // }
1706 // pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1707 // if (TEST_OPT_PROT)
1708 // {
1709 // for(i=1; i<=(currRing->N); i++)
1710 // Print(" %d",ecartWeights[i]);
1711 // PrintLn();
1712 // mflush();
1713 // }
1714 // }
1715 }
1716 
1717 void initSba(ideal F,kStrategy strat)
1718 {
1719  int i;
1720  //idhdl h;
1721  /* setting global variables ------------------- */
1722  strat->enterS = enterSSba;
1723  strat->red2 = redHoney;
1724  if (strat->honey)
1725  strat->red2 = redHoney;
1726  else if (currRing->pLexOrder && !strat->homog)
1727  strat->red2 = redLazy;
1728  else
1729  {
1730  strat->LazyPass *=4;
1731  strat->red2 = redHomog;
1732  }
1733  if (rField_is_Ring(currRing))
1734  {
1736  {strat->red2 = redRiloc;}
1737  else
1738  {strat->red2 = redRing;}
1739  }
1740  if (currRing->pLexOrder && strat->honey)
1741  strat->initEcart = initEcartNormal;
1742  else
1743  strat->initEcart = initEcartBBA;
1744  if (strat->honey)
1746  else
1748  //strat->kIdeal = NULL;
1749  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1750  //else strat->kIdeal->rtyp=MODUL_CMD;
1751  //strat->kIdeal->data=(void *)strat->Shdl;
1752  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1753  {
1754  //interred machen Aenderung
1755  strat->pOrigFDeg = currRing->pFDeg;
1756  strat->pOrigLDeg = currRing->pLDeg;
1757  //h=ggetid("ecart");
1758  //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1759  //{
1760  // ecartWeights=iv2array(IDINTVEC(h));
1761  //}
1762  //else
1763  {
1764  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1765  /*uses automatic computation of the ecartWeights to set them*/
1767  }
1769  if (TEST_OPT_PROT)
1770  {
1771  for(i=1; i<=(currRing->N); i++)
1772  Print(" %d",ecartWeights[i]);
1773  PrintLn();
1774  mflush();
1775  }
1776  }
1777  // for sig-safe reductions in signature-based
1778  // standard basis computations
1780  strat->red = redSigRing;
1781  else
1782  strat->red = redSig;
1783  //strat->sbaOrder = 1;
1784  strat->currIdx = 1;
1785 }
1786 
1787 void initMora(ideal F,kStrategy strat)
1788 {
1789  int i,j;
1790 
1791  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1792  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1793  strat->enterS = enterSMora;
1794  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1795  strat->posInLOld = strat->posInL;
1796  strat->posInLOldFlag = TRUE;
1797  strat->initEcart = initEcartNormal;
1798  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1799  if ( strat->kHEdgeFound )
1800  strat->kNoether = pCopy((currRing->ppNoether));
1801  else if (strat->kHEdgeFound || strat->homog)
1802  strat->red = redFirst; /*take the first possible in T*/
1803  else
1804  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1805  if (strat->kHEdgeFound)
1806  {
1807  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1808  strat->posInT = posInT2;
1809  }
1810  else
1811  {
1812  strat->HCord = 32000;/*- very large -*/
1813  }
1814 
1815  if (rField_is_Ring(currRing)) {
1816  if (rField_is_Z(currRing))
1817  strat->red = redRiloc_Z;
1818  else
1819  strat->red = redRiloc;
1820  }
1821 
1822  /*reads the ecartWeights used for Graebes method from the
1823  *intvec ecart and set ecartWeights
1824  */
1825  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1826  {
1827  //interred machen Aenderung
1828  strat->pOrigFDeg=currRing->pFDeg;
1829  strat->pOrigLDeg=currRing->pLDeg;
1830  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1831  /*uses automatic computation of the ecartWeights to set them*/
1833 
1835  if (TEST_OPT_PROT)
1836  {
1837  for(i=1; i<=(currRing->N); i++)
1838  Print(" %d",ecartWeights[i]);
1839  PrintLn();
1840  mflush();
1841  }
1842  }
1843  kOptimizeLDeg(currRing->pLDeg, strat);
1844 }
1845 
1846 void kDebugPrint(kStrategy strat);
1847 
1848 ideal mora (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1849 {
1850  int olddeg = 0;
1851  int reduc = 0;
1852  int red_result = 1;
1853  int hilbeledeg=1,hilbcount=0;
1854  BITSET save1;
1855  SI_SAVE_OPT1(save1);
1857  {
1858  si_opt_1 &= ~Sy_bit(OPT_REDSB);
1860  }
1861 
1862  strat->update = TRUE;
1863  /*- setting global variables ------------------- -*/
1864  initBuchMoraCrit(strat);
1865  initHilbCrit(F,Q,&hilb,strat);
1866  initMora(F,strat);
1868  initBuchMoraPosRing(strat);
1869  else
1870  initBuchMoraPos(strat);
1871  /*Shdl=*/initBuchMora(F,Q,strat);
1872  if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1873  /*updateS in initBuchMora has Hecketest
1874  * and could have put strat->kHEdgdeFound FALSE*/
1875  if ((currRing->ppNoether)!=NULL)
1876  {
1877  strat->kHEdgeFound = TRUE;
1878  }
1879  if (strat->kHEdgeFound && strat->update)
1880  {
1881  firstUpdate(strat);
1882  updateLHC(strat);
1883  reorderL(strat);
1884  }
1885  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1886  {
1887  strat->posInLOld = strat->posInL;
1888  strat->posInLOldFlag = FALSE;
1889  strat->posInL = posInL10;
1890  updateL(strat);
1891  reorderL(strat);
1892  }
1893  kTest_TS(strat);
1894  strat->use_buckets = kMoraUseBucket(strat);
1895 
1896 #ifdef HAVE_TAIL_RING
1897  if (strat->homog && strat->red == redFirst)
1898  if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1899  kStratInitChangeTailRing(strat);
1900 #endif
1901 
1902  if (BVERBOSE(23))
1903  {
1904  kDebugPrint(strat);
1905  }
1906 //deleteInL(strat->L,&strat->Ll,1,strat);
1907 //deleteInL(strat->L,&strat->Ll,0,strat);
1908 
1909  /*- compute-------------------------------------------*/
1910  while (strat->Ll >= 0)
1911  {
1912  #ifdef KDEBUG
1913  if (TEST_OPT_DEBUG) messageSets(strat);
1914  #endif
1915  if (siCntrlc)
1916  {
1917  while (strat->Ll >= 0)
1918  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1919  strat->noClearS=TRUE;
1920  }
1921  if (TEST_OPT_DEGBOUND
1922  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1923  {
1924  /*
1925  * stops computation if
1926  * - 24 (degBound)
1927  * && upper degree is bigger than Kstd1_deg
1928  */
1929  while ((strat->Ll >= 0)
1930  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1931  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1932  )
1933  {
1934  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1935  //if (TEST_OPT_PROT)
1936  //{
1937  // PrintS("D"); mflush();
1938  //}
1939  }
1940  if (strat->Ll<0) break;
1941  else strat->noClearS=TRUE;
1942  }
1943  strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1944  if (strat->Ll==0) strat->interpt=TRUE;
1945  strat->Ll--;
1946  // create the real Spoly
1947  if (pNext(strat->P.p) == strat->tail)
1948  {
1949  /*- deletes the short spoly and computes -*/
1950  if (rField_is_Ring(currRing))
1951  pLmDelete(strat->P.p);
1952  else
1953  pLmFree(strat->P.p);
1954  strat->P.p = NULL;
1955  poly m1 = NULL, m2 = NULL;
1956  // check that spoly creation is ok
1957  while (strat->tailRing != currRing &&
1958  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1959  {
1960  assume(m1 == NULL && m2 == NULL);
1961  // if not, change to a ring where exponents are large enough
1962  kStratChangeTailRing(strat);
1963  }
1964  /* create the real one */
1965  ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1966  strat->tailRing, m1, m2, strat->R);
1967  if (!strat->use_buckets)
1968  strat->P.SetLength(strat->length_pLength);
1969  }
1970  else if (strat->P.p1 == NULL)
1971  {
1972  // for input polys, prepare reduction (buckets !)
1973  strat->P.SetLength(strat->length_pLength);
1974  strat->P.PrepareRed(strat->use_buckets);
1975  }
1976 
1977  // the s-poly
1978  if (!strat->P.IsNull())
1979  {
1980  // might be NULL from noether !!!
1981  if (TEST_OPT_PROT)
1982  message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1983  // reduce
1984  red_result = strat->red(&strat->P,strat);
1985  }
1986 
1987  // the reduced s-poly
1988  if (! strat->P.IsNull())
1989  {
1990  strat->P.GetP();
1991  // statistics
1992  if (TEST_OPT_PROT) PrintS("s");
1993  // normalization
1995  strat->P.pCleardenom();
1996  else
1997  strat->P.pNorm();
1998  // tailreduction
1999  strat->P.p = redtail(&(strat->P),strat->sl,strat);
2000  if (strat->P.p==NULL)
2001  {
2002  WerrorS("expoent overflow - wrong ordering");
2003  return(idInit(1,1));
2004  }
2005  // set ecart -- might have changed because of tail reductions
2006  if ((!strat->noTailReduction) && (!strat->honey))
2007  strat->initEcart(&strat->P);
2008  // cancel unit
2009  cancelunit(&strat->P);
2010  // for char 0, clear denominators
2011  if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2013  strat->P.pCleardenom();
2014 
2015  enterT(strat->P,strat);
2016  // build new pairs
2017  if (rField_is_Ring(currRing))
2018  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2019  else
2020  enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2021  // put in S
2022  strat->enterS(strat->P,
2023  posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2024  strat, strat->tl);
2025  // apply hilbert criterion
2026  if (hilb!=NULL)
2027  {
2028  if (strat->homog==isHomog)
2029  khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2030  else
2031  khCheckLocInhom(Q,w,hilb,hilbcount,strat);
2032  }
2033 
2034  // clear strat->P
2035  kDeleteLcm(&strat->P);
2036 
2037 #ifdef KDEBUG
2038  // make sure kTest_TS does not complain about strat->P
2039  strat->P.Clear();
2040 #endif
2041  }
2042  if (strat->kHEdgeFound)
2043  {
2044  if ((TEST_OPT_FINDET)
2045  || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL,strat->tailRing) < Kstd1_mu)))
2046  {
2047  // obachman: is this still used ???
2048  /*
2049  * stops computation if strat->kHEdgeFound and
2050  * - 27 (finiteDeterminacyTest)
2051  * or
2052  * - 23
2053  * (multBound)
2054  * && multiplicity of the ideal is smaller then a predefined number mu
2055  */
2056  while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2057  }
2058  }
2059  kTest_TS(strat);
2060  }
2061  /*- complete reduction of the standard basis------------------------ -*/
2062  if (TEST_OPT_REDSB) completeReduce(strat);
2063  else if (TEST_OPT_PROT) PrintLn();
2064  /*- release temp data------------------------------- -*/
2065  exitBuchMora(strat);
2066  /*- polynomials used for HECKE: HC, noether -*/
2067  if (TEST_OPT_FINDET)
2068  {
2069  if (strat->kHEdge!=NULL)
2070  Kstd1_mu=currRing->pFDeg(strat->kHEdge,currRing);
2071  else
2072  Kstd1_mu=-1;
2073  }
2074  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2075  strat->update = TRUE; //???
2076  strat->lastAxis = 0; //???
2077  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2078  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2079  if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2080 // if (TEST_OPT_WEIGHTM)
2081 // {
2082 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2083 // if (ecartWeights)
2084 // {
2085 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2086 // ecartWeights=NULL;
2087 // }
2088 // }
2089  if(nCoeff_is_Z(currRing->cf))
2090  finalReduceByMon(strat);
2091  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2092  SI_RESTORE_OPT1(save1);
2093  idTest(strat->Shdl);
2094  return (strat->Shdl);
2095 }
2096 
2097 poly kNF1 (ideal F,ideal Q,poly q, kStrategy strat, int lazyReduce)
2098 {
2099  assume(q!=NULL);
2100  assume(!(idIs0(F)&&(Q==NULL)));
2101 
2102 // lazy_reduce flags: can be combined by |
2103 //#define KSTD_NF_LAZY 1
2104  // do only a reduction of the leading term
2105 //#define KSTD_NF_ECART 2
2106  // only local: recude even with bad ecart
2107  poly p;
2108  int i;
2109  int j;
2110  int o;
2111  LObject h;
2112  BITSET save1;
2113  SI_SAVE_OPT1(save1);
2114 
2115  //if ((idIs0(F))&&(Q==NULL))
2116  // return pCopy(q); /*F=0*/
2117  //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
2118  /*- creating temp data structures------------------- -*/
2119  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2120  strat->kNoether = pCopy((currRing->ppNoether));
2124  && (! TEST_V_DEG_STOP)
2125  && (0<Kstd1_deg)
2126  && ((!strat->kHEdgeFound)
2128  {
2129  pLmDelete(&strat->kNoether);
2130  strat->kNoether=pOne();
2131  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2132  pSetm(strat->kNoether);
2133  strat->kHEdgeFound=TRUE;
2134  }
2135  initBuchMoraCrit(strat);
2137  initBuchMoraPosRing(strat);
2138  else
2139  initBuchMoraPos(strat);
2140  initMora(F,strat);
2141  strat->enterS = enterSMoraNF;
2142  /*- set T -*/
2143  strat->tl = -1;
2144  strat->tmax = setmaxT;
2145  strat->T = initT();
2146  strat->R = initR();
2147  strat->sevT = initsevT();
2148  /*- set S -*/
2149  strat->sl = -1;
2150  /*- init local data struct.-------------------------- -*/
2151  /*Shdl=*/initS(F,Q,strat);
2152  if ((strat->ak!=0)
2153  && (strat->kHEdgeFound))
2154  {
2155  if (strat->ak!=1)
2156  {
2157  pSetComp(strat->kNoether,1);
2158  pSetmComp(strat->kNoether);
2159  poly p=pHead(strat->kNoether);
2160  pSetComp(p,strat->ak);
2161  pSetmComp(p);
2162  p=pAdd(strat->kNoether,p);
2163  strat->kNoether=pNext(p);
2165  }
2166  }
2167  if ((lazyReduce & KSTD_NF_LAZY)==0)
2168  {
2169  for (i=strat->sl; i>=0; i--)
2170  pNorm(strat->S[i]);
2171  }
2172  /*- puts the elements of S also to T -*/
2173  for (i=0; i<=strat->sl; i++)
2174  {
2175  h.p = strat->S[i];
2176  h.ecart = strat->ecartS[i];
2177  if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
2178  else assume(strat->sevS[i] == pGetShortExpVector(h.p));
2179  h.length = pLength(h.p);
2180  h.sev = strat->sevS[i];
2181  h.SetpFDeg();
2182  enterT(h,strat);
2183  }
2184 #ifdef KDEBUG
2185 // kDebugPrint(strat);
2186 #endif
2187  /*- compute------------------------------------------- -*/
2188  p = pCopy(q);
2189  deleteHC(&p,&o,&j,strat);
2190  kTest(strat);
2191  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2192  if (BVERBOSE(23)) kDebugPrint(strat);
2194  {
2195  if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2196  }
2197  else
2198  {
2199  if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2200  }
2201  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2202  {
2203  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2204  p = redtail(p,strat->sl,strat);
2205  }
2206  /*- release temp data------------------------------- -*/
2207  cleanT(strat);
2208  assume(strat->L==NULL); /*strat->L unsed */
2209  assume(strat->B==NULL); /*strat->B unused */
2210  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2211  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2212  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2213  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2214  omFree(strat->sevT);
2215  omFree(strat->S_2_R);
2216  omFree(strat->R);
2217 
2218  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2219  {
2220  i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
2221  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2222  strat->fromQ=NULL;
2223  }
2224  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2225  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2226 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2227 // {
2228 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2229 // if (ecartWeights)
2230 // {
2231 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2232 // ecartWeights=NULL;
2233 // }
2234 // }
2235  idDelete(&strat->Shdl);
2236  SI_RESTORE_OPT1(save1);
2237  if (TEST_OPT_PROT) PrintLn();
2238  return p;
2239 }
2240 
2241 ideal kNF1 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce)
2242 {
2243  assume(!idIs0(q));
2244  assume(!(idIs0(F)&&(Q==NULL)));
2245 
2246 // lazy_reduce flags: can be combined by |
2247 //#define KSTD_NF_LAZY 1
2248  // do only a reduction of the leading term
2249 //#define KSTD_NF_ECART 2
2250  // only local: recude even with bad ecart
2251  poly p;
2252  int i;
2253  int j;
2254  int o;
2255  LObject h;
2256  ideal res;
2257  BITSET save1;
2258  SI_SAVE_OPT1(save1);
2259 
2260  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2261  //if ((idIs0(F))&&(Q==NULL))
2262  // return idCopy(q); /*F=0*/
2263  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2264  /*- creating temp data structures------------------- -*/
2265  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2266  strat->kNoether=pCopy((currRing->ppNoether));
2269  && (0<Kstd1_deg)
2270  && ((!strat->kHEdgeFound)
2272  {
2273  pLmDelete(&strat->kNoether);
2274  strat->kNoether=pOne();
2275  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2276  pSetm(strat->kNoether);
2277  strat->kHEdgeFound=TRUE;
2278  }
2279  initBuchMoraCrit(strat);
2281  initBuchMoraPosRing(strat);
2282  else
2283  initBuchMoraPos(strat);
2284  initMora(F,strat);
2285  strat->enterS = enterSMoraNF;
2286  /*- set T -*/
2287  strat->tl = -1;
2288  strat->tmax = setmaxT;
2289  strat->T = initT();
2290  strat->R = initR();
2291  strat->sevT = initsevT();
2292  /*- set S -*/
2293  strat->sl = -1;
2294  /*- init local data struct.-------------------------- -*/
2295  /*Shdl=*/initS(F,Q,strat);
2296  if ((strat->ak!=0)
2297  && (strat->kHEdgeFound))
2298  {
2299  if (strat->ak!=1)
2300  {
2301  pSetComp(strat->kNoether,1);
2302  pSetmComp(strat->kNoether);
2303  poly p=pHead(strat->kNoether);
2304  pSetComp(p,strat->ak);
2305  pSetmComp(p);
2306  p=pAdd(strat->kNoether,p);
2307  strat->kNoether=pNext(p);
2309  }
2310  }
2311  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
2312  {
2313  for (i=strat->sl; i>=0; i--)
2314  pNorm(strat->S[i]);
2315  }
2316  /*- compute------------------------------------------- -*/
2317  res=idInit(IDELEMS(q),strat->ak);
2318  for (i=0; i<IDELEMS(q); i++)
2319  {
2320  if (q->m[i]!=NULL)
2321  {
2322  p = pCopy(q->m[i]);
2323  deleteHC(&p,&o,&j,strat);
2324  if (p!=NULL)
2325  {
2326  /*- puts the elements of S also to T -*/
2327  for (j=0; j<=strat->sl; j++)
2328  {
2329  h.p = strat->S[j];
2330  h.ecart = strat->ecartS[j];
2331  h.pLength = h.length = pLength(h.p);
2332  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2333  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2334  h.sev = strat->sevS[j];
2335  h.SetpFDeg();
2337  enterT_strong(h,strat);
2338  else
2339  enterT(h,strat);
2340  }
2341  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2343  {
2344  p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2345  }
2346  else
2347  p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2348  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2349  {
2350  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2351  p = redtail(p,strat->sl,strat);
2352  }
2353  cleanT(strat);
2354  }
2355  res->m[i]=p;
2356  }
2357  //else
2358  // res->m[i]=NULL;
2359  }
2360  /*- release temp data------------------------------- -*/
2361  assume(strat->L==NULL); /*strat->L unsed */
2362  assume(strat->B==NULL); /*strat->B unused */
2363  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2364  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2365  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2366  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2367  omFree(strat->sevT);
2368  omFree(strat->S_2_R);
2369  omFree(strat->R);
2370  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2371  {
2373  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2374  strat->fromQ=NULL;
2375  }
2376  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2377  if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2378 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2379 // {
2380 // pFDeg=strat->pOrigFDeg;
2381 // pLDeg=strat->pOrigLDeg;
2382 // if (ecartWeights)
2383 // {
2384 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2385 // ecartWeights=NULL;
2386 // }
2387 // }
2388  idDelete(&strat->Shdl);
2389  SI_RESTORE_OPT1(save1);
2390  if (TEST_OPT_PROT) PrintLn();
2391  return res;
2392 }
2393 
2395 
2396 long kModDeg(poly p, ring r)
2397 {
2398  long o=p_WDegree(p, r);
2399  long i=__p_GetComp(p, r);
2400  if (i==0) return o;
2401  //assume((i>0) && (i<=kModW->length()));
2402  if (i<=kModW->length())
2403  return o+(*kModW)[i-1];
2404  return o;
2405 }
2406 long kHomModDeg(poly p, ring r)
2407 {
2408  int i;
2409  long j=0;
2410 
2411  for (i=r->N;i>0;i--)
2412  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2413  if (kModW == NULL) return j;
2414  i = __p_GetComp(p,r);
2415  if (i==0) return j;
2416  return j+(*kModW)[i-1];
2417 }
2418 
2419 ideal kStd(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2420  int newIdeal, intvec *vw, s_poly_proc_t sp)
2421 {
2422  if(idIs0(F))
2423  return idInit(1,F->rank);
2424 
2425 #ifdef HAVE_SHIFTBBA
2426  if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2427 #endif
2428 
2429  ideal r;
2430  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2431  BOOLEAN delete_w=(w==NULL);
2432  kStrategy strat=new skStrategy;
2433 
2434  strat->s_poly=sp;
2435  if(!TEST_OPT_RETURN_SB)
2436  strat->syzComp = syzComp;
2437  if (TEST_OPT_SB_1
2438  &&(!rField_is_Ring(currRing))
2439  )
2440  strat->newIdeal = newIdeal;
2442  strat->LazyPass=20;
2443  else
2444  strat->LazyPass=2;
2445  strat->LazyDegree = 1;
2446  strat->ak = id_RankFreeModule(F,currRing);
2447  strat->kModW=kModW=NULL;
2448  strat->kHomW=kHomW=NULL;
2449  if (vw != NULL)
2450  {
2451  currRing->pLexOrder=FALSE;
2452  strat->kHomW=kHomW=vw;
2453  strat->pOrigFDeg = currRing->pFDeg;
2454  strat->pOrigLDeg = currRing->pLDeg;
2456  toReset = TRUE;
2457  }
2458  if (h==testHomog)
2459  {
2460  if (strat->ak == 0)
2461  {
2462  h = (tHomog)idHomIdeal(F,Q);
2463  w=NULL;
2464  }
2465  else if (!TEST_OPT_DEGBOUND)
2466  {
2467  if (w!=NULL)
2468  h = (tHomog)idHomModule(F,Q,w);
2469  else
2470  h = (tHomog)idHomIdeal(F,Q);
2471  }
2472  }
2473  currRing->pLexOrder=b;
2474  if (h==isHomog)
2475  {
2476  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2477  {
2478  strat->kModW = kModW = *w;
2479  if (vw == NULL)
2480  {
2481  strat->pOrigFDeg = currRing->pFDeg;
2482  strat->pOrigLDeg = currRing->pLDeg;
2484  toReset = TRUE;
2485  }
2486  }
2487  currRing->pLexOrder = TRUE;
2488  if (hilb==NULL) strat->LazyPass*=2;
2489  }
2490  strat->homog=h;
2491 #ifdef KDEBUG
2492  idTest(F);
2493  if (Q!=NULL) idTest(Q);
2494 #endif
2495 #ifdef HAVE_PLURAL
2496  if (rIsPluralRing(currRing))
2497  {
2498  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2499  strat->no_prod_crit = ! bIsSCA;
2500  if (w!=NULL)
2501  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2502  else
2503  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2504  }
2505  else
2506 #endif
2507  {
2508  #if PRE_INTEGER_CHECK
2509  //the preinteger check strategy is not for modules
2510  if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2511  {
2512  ideal FCopy = idCopy(F);
2513  poly pFmon = preIntegerCheck(FCopy, Q);
2514  if(pFmon != NULL)
2515  {
2516  idInsertPoly(FCopy, pFmon);
2517  strat->kModW=kModW=NULL;
2518  if (h==testHomog)
2519  {
2520  if (strat->ak == 0)
2521  {
2522  h = (tHomog)idHomIdeal(FCopy,Q);
2523  w=NULL;
2524  }
2525  else if (!TEST_OPT_DEGBOUND)
2526  {
2527  if (w!=NULL)
2528  h = (tHomog)idHomModule(FCopy,Q,w);
2529  else
2530  h = (tHomog)idHomIdeal(FCopy,Q);
2531  }
2532  }
2533  currRing->pLexOrder=b;
2534  if (h==isHomog)
2535  {
2536  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2537  {
2538  strat->kModW = kModW = *w;
2539  if (vw == NULL)
2540  {
2541  strat->pOrigFDeg = currRing->pFDeg;
2542  strat->pOrigLDeg = currRing->pLDeg;
2544  toReset = TRUE;
2545  }
2546  }
2547  currRing->pLexOrder = TRUE;
2548  if (hilb==NULL) strat->LazyPass*=2;
2549  }
2550  strat->homog=h;
2551  }
2552  omTestMemory(1);
2553  if(w == NULL)
2554  {
2556  r=mora(FCopy,Q,NULL,hilb,strat);
2557  else
2558  r=bba(FCopy,Q,NULL,hilb,strat);
2559  }
2560  else
2561  {
2563  r=mora(FCopy,Q,*w,hilb,strat);
2564  else
2565  r=bba(FCopy,Q,*w,hilb,strat);
2566  }
2567  idDelete(&FCopy);
2568  }
2569  else
2570  #endif
2571  {
2572  if(w==NULL)
2573  {
2575  r=mora(F,Q,NULL,hilb,strat);
2576  else
2577  r=bba(F,Q,NULL,hilb,strat);
2578  }
2579  else
2580  {
2582  r=mora(F,Q,*w,hilb,strat);
2583  else
2584  r=bba(F,Q,*w,hilb,strat);
2585  }
2586  }
2587  }
2588 #ifdef KDEBUG
2589  idTest(r);
2590 #endif
2591  if (toReset)
2592  {
2593  kModW = NULL;
2594  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2595  }
2596  currRing->pLexOrder = b;
2597 //Print("%d reductions canceled \n",strat->cel);
2598  HCord=strat->HCord;
2599  delete(strat);
2600  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2601  return r;
2602 }
2603 
2604 ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int sbaOrder, int arri, intvec *hilb,int syzComp,
2605  int newIdeal, intvec *vw)
2606 {
2607  if(idIs0(F))
2608  return idInit(1,F->rank);
2609  if(!rField_is_Ring(currRing))
2610  {
2611  ideal r;
2612  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2613  BOOLEAN delete_w=(w==NULL);
2614  kStrategy strat=new skStrategy;
2615  strat->sbaOrder = sbaOrder;
2616  if (arri!=0)
2617  {
2618  strat->rewCrit1 = arriRewDummy;
2619  strat->rewCrit2 = arriRewCriterion;
2620  strat->rewCrit3 = arriRewCriterionPre;
2621  }
2622  else
2623  {
2624  strat->rewCrit1 = faugereRewCriterion;
2625  strat->rewCrit2 = faugereRewCriterion;
2626  strat->rewCrit3 = faugereRewCriterion;
2627  }
2628 
2629  if(!TEST_OPT_RETURN_SB)
2630  strat->syzComp = syzComp;
2631  if (TEST_OPT_SB_1)
2632  //if(!rField_is_Ring(currRing)) // always true here
2633  strat->newIdeal = newIdeal;
2635  strat->LazyPass=20;
2636  else
2637  strat->LazyPass=2;
2638  strat->LazyDegree = 1;
2640  strat->chainCrit=chainCritNormal;
2642  strat->ak = id_RankFreeModule(F,currRing);
2643  strat->kModW=kModW=NULL;
2644  strat->kHomW=kHomW=NULL;
2645  if (vw != NULL)
2646  {
2647  currRing->pLexOrder=FALSE;
2648  strat->kHomW=kHomW=vw;
2649  strat->pOrigFDeg = currRing->pFDeg;
2650  strat->pOrigLDeg = currRing->pLDeg;
2652  toReset = TRUE;
2653  }
2654  if (h==testHomog)
2655  {
2656  if (strat->ak == 0)
2657  {
2658  h = (tHomog)idHomIdeal(F,Q);
2659  w=NULL;
2660  }
2661  else if (!TEST_OPT_DEGBOUND)
2662  {
2663  if (w!=NULL)
2664  h = (tHomog)idHomModule(F,Q,w);
2665  else
2666  h = (tHomog)idHomIdeal(F,Q);
2667  }
2668  }
2669  currRing->pLexOrder=b;
2670  if (h==isHomog)
2671  {
2672  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2673  {
2674  strat->kModW = kModW = *w;
2675  if (vw == NULL)
2676  {
2677  strat->pOrigFDeg = currRing->pFDeg;
2678  strat->pOrigLDeg = currRing->pLDeg;
2680  toReset = TRUE;
2681  }
2682  }
2683  currRing->pLexOrder = TRUE;
2684  if (hilb==NULL) strat->LazyPass*=2;
2685  }
2686  strat->homog=h;
2687  #ifdef KDEBUG
2688  idTest(F);
2689  if(Q != NULL)
2690  idTest(Q);
2691  #endif
2692  #ifdef HAVE_PLURAL
2693  if (rIsPluralRing(currRing))
2694  {
2695  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2696  strat->no_prod_crit = ! bIsSCA;
2697  if (w!=NULL)
2698  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2699  else
2700  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2701  }
2702  else
2703  #endif
2704  {
2706  {
2707  if (w!=NULL)
2708  r=mora(F,Q,*w,hilb,strat);
2709  else
2710  r=mora(F,Q,NULL,hilb,strat);
2711  }
2712  else
2713  {
2714  strat->sigdrop = FALSE;
2715  if (w!=NULL)
2716  r=sba(F,Q,*w,hilb,strat);
2717  else
2718  r=sba(F,Q,NULL,hilb,strat);
2719  }
2720  }
2721  #ifdef KDEBUG
2722  idTest(r);
2723  #endif
2724  if (toReset)
2725  {
2726  kModW = NULL;
2727  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2728  }
2729  currRing->pLexOrder = b;
2730  //Print("%d reductions canceled \n",strat->cel);
2731  HCord=strat->HCord;
2732  //delete(strat);
2733  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2734  return r;
2735  }
2736  else
2737  {
2738  //--------------------------RING CASE-------------------------
2739  assume(sbaOrder == 1);
2740  assume(arri == 0);
2741  ideal r;
2742  r = idCopy(F);
2743  int sbaEnterS = -1;
2744  bool sigdrop = TRUE;
2745  //This is how we set the SBA algorithm;
2746  int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2747  while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2748  && (blockred <= blockedreductions))
2749  {
2750  loops++;
2751  if(loops == 1)
2752  sigdrop = FALSE;
2753  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2754  BOOLEAN delete_w=(w==NULL);
2755  kStrategy strat=new skStrategy;
2756  strat->sbaEnterS = sbaEnterS;
2757  strat->sigdrop = sigdrop;
2758  #if 0
2759  strat->blockred = blockred;
2760  #else
2761  strat->blockred = 0;
2762  #endif
2763  strat->blockredmax = blockedreductions;
2764  //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2765  //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2766  strat->sbaOrder = sbaOrder;
2767  if (arri!=0)
2768  {
2769  strat->rewCrit1 = arriRewDummy;
2770  strat->rewCrit2 = arriRewCriterion;
2771  strat->rewCrit3 = arriRewCriterionPre;
2772  }
2773  else
2774  {
2775  strat->rewCrit1 = faugereRewCriterion;
2776  strat->rewCrit2 = faugereRewCriterion;
2777  strat->rewCrit3 = faugereRewCriterion;
2778  }
2779 
2780  if(!TEST_OPT_RETURN_SB)
2781  strat->syzComp = syzComp;
2782  if (TEST_OPT_SB_1)
2783  if(!rField_is_Ring(currRing))
2784  strat->newIdeal = newIdeal;
2786  strat->LazyPass=20;
2787  else
2788  strat->LazyPass=2;
2789  strat->LazyDegree = 1;
2791  strat->chainCrit=chainCritNormal;
2793  strat->ak = id_RankFreeModule(F,currRing);
2794  strat->kModW=kModW=NULL;
2795  strat->kHomW=kHomW=NULL;
2796  if (vw != NULL)
2797  {
2798  currRing->pLexOrder=FALSE;
2799  strat->kHomW=kHomW=vw;
2800  strat->pOrigFDeg = currRing->pFDeg;
2801  strat->pOrigLDeg = currRing->pLDeg;
2803  toReset = TRUE;
2804  }
2805  if (h==testHomog)
2806  {
2807  if (strat->ak == 0)
2808  {
2809  h = (tHomog)idHomIdeal(F,Q);
2810  w=NULL;
2811  }
2812  else if (!TEST_OPT_DEGBOUND)
2813  {
2814  if (w!=NULL)
2815  h = (tHomog)idHomModule(F,Q,w);
2816  else
2817  h = (tHomog)idHomIdeal(F,Q);
2818  }
2819  }
2820  currRing->pLexOrder=b;
2821  if (h==isHomog)
2822  {
2823  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2824  {
2825  strat->kModW = kModW = *w;
2826  if (vw == NULL)
2827  {
2828  strat->pOrigFDeg = currRing->pFDeg;
2829  strat->pOrigLDeg = currRing->pLDeg;
2831  toReset = TRUE;
2832  }
2833  }
2834  currRing->pLexOrder = TRUE;
2835  if (hilb==NULL) strat->LazyPass*=2;
2836  }
2837  strat->homog=h;
2838  #ifdef KDEBUG
2839  idTest(F);
2840  if(Q != NULL)
2841  idTest(Q);
2842  #endif
2843  #ifdef HAVE_PLURAL
2844  if (rIsPluralRing(currRing))
2845  {
2846  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2847  strat->no_prod_crit = ! bIsSCA;
2848  if (w!=NULL)
2849  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2850  else
2851  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2852  }
2853  else
2854  #endif
2855  {
2857  {
2858  if (w!=NULL)
2859  r=mora(F,Q,*w,hilb,strat);
2860  else
2861  r=mora(F,Q,NULL,hilb,strat);
2862  }
2863  else
2864  {
2865  if (w!=NULL)
2866  r=sba(r,Q,*w,hilb,strat);
2867  else
2868  {
2869  r=sba(r,Q,NULL,hilb,strat);
2870  }
2871  }
2872  }
2873  #ifdef KDEBUG
2874  idTest(r);
2875  #endif
2876  if (toReset)
2877  {
2878  kModW = NULL;
2879  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2880  }
2881  currRing->pLexOrder = b;
2882  //Print("%d reductions canceled \n",strat->cel);
2883  HCord=strat->HCord;
2884  sigdrop = strat->sigdrop;
2885  sbaEnterS = strat->sbaEnterS;
2886  blockred = strat->blockred;
2887  delete(strat);
2888  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2889  }
2890  // Go to std
2891  if(sigdrop || blockred > blockedreductions)
2892  {
2893  r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2894  }
2895  return r;
2896  }
2897 }
2898 
2899 #ifdef HAVE_SHIFTBBA
2900 ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2901  int newIdeal, intvec *vw, BOOLEAN rightGB)
2902 {
2904  assume(idIsInV(F));
2905  ideal r;
2906  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2907  BOOLEAN delete_w=(w==NULL);
2908  kStrategy strat=new skStrategy;
2909  intvec* temp_w=NULL;
2910 
2911  strat->rightGB = rightGB;
2912 
2913  if(!TEST_OPT_RETURN_SB)
2914  strat->syzComp = syzComp;
2915  if (TEST_OPT_SB_1)
2916  if(!rField_is_Ring(currRing))
2917  strat->newIdeal = newIdeal;
2919  strat->LazyPass=20;
2920  else
2921  strat->LazyPass=2;
2922  strat->LazyDegree = 1;
2923  strat->ak = id_RankFreeModule(F,currRing);
2924  strat->kModW=kModW=NULL;
2925  strat->kHomW=kHomW=NULL;
2926  if (vw != NULL)
2927  {
2928  currRing->pLexOrder=FALSE;
2929  strat->kHomW=kHomW=vw;
2930  strat->pOrigFDeg = currRing->pFDeg;
2931  strat->pOrigLDeg = currRing->pLDeg;
2933  toReset = TRUE;
2934  }
2935  if (h==testHomog)
2936  {
2937  if (strat->ak == 0)
2938  {
2939  h = (tHomog)idHomIdeal(F,Q);
2940  w=NULL;
2941  }
2942  else if (!TEST_OPT_DEGBOUND)
2943  {
2944  if (w!=NULL)
2945  h = (tHomog)idHomModule(F,Q,w);
2946  else
2947  h = (tHomog)idHomIdeal(F,Q);
2948  }
2949  }
2950  currRing->pLexOrder=b;
2951  if (h==isHomog)
2952  {
2953  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2954  {
2955  strat->kModW = kModW = *w;
2956  if (vw == NULL)
2957  {
2958  strat->pOrigFDeg = currRing->pFDeg;
2959  strat->pOrigLDeg = currRing->pLDeg;
2961  toReset = TRUE;
2962  }
2963  }
2964  currRing->pLexOrder = TRUE;
2965  if (hilb==NULL) strat->LazyPass*=2;
2966  }
2967  strat->homog=h;
2968 #ifdef KDEBUG
2969  idTest(F);
2970 #endif
2972  {
2973  /* error: no local ord yet with shifts */
2974  WerrorS("No local ordering possible for shift algebra");
2975  return(NULL);
2976  }
2977  else
2978  {
2979  /* global ordering */
2980  if (w!=NULL)
2981  r=bbaShift(F,Q,*w,hilb,strat);
2982  else
2983  r=bbaShift(F,Q,NULL,hilb,strat);
2984  }
2985 #ifdef KDEBUG
2986  idTest(r);
2987 #endif
2988  if (toReset)
2989  {
2990  kModW = NULL;
2991  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2992  }
2993  currRing->pLexOrder = b;
2994 //Print("%d reductions canceled \n",strat->cel);
2995  HCord=strat->HCord;
2996  delete(strat);
2997  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2998  assume(idIsInV(r));
2999  return r;
3000 }
3001 #endif
3002 
3003 //##############################################################
3004 //##############################################################
3005 //##############################################################
3006 //##############################################################
3007 //##############################################################
3008 
3009 ideal kMin_std(ideal F, ideal Q, tHomog h,intvec ** w, ideal &M, intvec *hilb,
3010  int syzComp, int reduced)
3011 {
3012  if(idIs0(F))
3013  {
3014  M=idInit(1,F->rank);
3015  return idInit(1,F->rank);
3016  }
3018  {
3019  ideal sb;
3020  sb = kStd(F, Q, h, w, hilb);
3021  idSkipZeroes(sb);
3022  if(IDELEMS(sb) <= IDELEMS(F))
3023  {
3024  M = idCopy(sb);
3025  idSkipZeroes(M);
3026  return(sb);
3027  }
3028  else
3029  {
3030  M = idCopy(F);
3031  idSkipZeroes(M);
3032  return(sb);
3033  }
3034  }
3035  ideal r=NULL;
3036  int Kstd1_OldDeg = Kstd1_deg,i;
3037  intvec* temp_w=NULL;
3038  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3039  BOOLEAN delete_w=(w==NULL);
3040  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3041  kStrategy strat=new skStrategy;
3042 
3043  if(!TEST_OPT_RETURN_SB)
3044  strat->syzComp = syzComp;
3046  strat->LazyPass=20;
3047  else
3048  strat->LazyPass=2;
3049  strat->LazyDegree = 1;
3050  strat->minim=(reduced % 2)+1;
3051  strat->ak = id_RankFreeModule(F,currRing);
3052  if (delete_w)
3053  {
3054  temp_w=new intvec((strat->ak)+1);
3055  w = &temp_w;
3056  }
3057  if (h==testHomog)
3058  {
3059  if (strat->ak == 0)
3060  {
3061  h = (tHomog)idHomIdeal(F,Q);
3062  w=NULL;
3063  }
3064  else
3065  {
3066  h = (tHomog)idHomModule(F,Q,w);
3067  }
3068  }
3069  if (h==isHomog)
3070  {
3071  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3072  {
3073  kModW = *w;
3074  strat->kModW = *w;
3075  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3076  strat->pOrigFDeg = currRing->pFDeg;
3077  strat->pOrigLDeg = currRing->pLDeg;
3079 
3080  toReset = TRUE;
3081  if (reduced>1)
3082  {
3083  Kstd1_OldDeg=Kstd1_deg;
3084  Kstd1_deg = -1;
3085  for (i=IDELEMS(F)-1;i>=0;i--)
3086  {
3087  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3088  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3089  }
3090  }
3091  }
3092  currRing->pLexOrder = TRUE;
3093  strat->LazyPass*=2;
3094  }
3095  strat->homog=h;
3097  {
3098  if (w!=NULL)
3099  r=mora(F,Q,*w,hilb,strat);
3100  else
3101  r=mora(F,Q,NULL,hilb,strat);
3102  }
3103  else
3104  {
3105  if (w!=NULL)
3106  r=bba(F,Q,*w,hilb,strat);
3107  else
3108  r=bba(F,Q,NULL,hilb,strat);
3109  }
3110 #ifdef KDEBUG
3111  {
3112  int i;
3113  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3114  }
3115 #endif
3116  idSkipZeroes(r);
3117  if (toReset)
3118  {
3119  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3120  kModW = NULL;
3121  }
3122  currRing->pLexOrder = b;
3123  HCord=strat->HCord;
3124  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3125  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3126  {
3127  M=idInit(1,F->rank);
3128  M->m[0]=pOne();
3129  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3130  if (strat->M!=NULL) idDelete(&strat->M);
3131  }
3132  else if (strat->M==NULL)
3133  {
3134  M=idInit(1,F->rank);
3135  WarnS("no minimal generating set computed");
3136  }
3137  else
3138  {
3139  idSkipZeroes(strat->M);
3140  M=strat->M;
3141  }
3142  delete(strat);
3143  if (reduced>2)
3144  {
3145  Kstd1_deg=Kstd1_OldDeg;
3146  if (!oldDegBound)
3148  }
3149  else
3150  {
3151  if (IDELEMS(M)>IDELEMS(r)) {
3152  idDelete(&M);
3153  M=idCopy(r); }
3154  }
3155  return r;
3156 }
3157 
3158 poly kNF(ideal F, ideal Q, poly p,int syzComp, int lazyReduce)
3159 {
3160  if (p==NULL)
3161  return NULL;
3162 
3163  poly pp = p;
3164 
3165 #ifdef HAVE_PLURAL
3166  if(rIsSCA(currRing))
3167  {
3168  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3169  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3170  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3171 
3172  if(Q == currRing->qideal)
3173  Q = SCAQuotient(currRing);
3174  }
3175 #endif
3176 
3177  if ((idIs0(F))&&(Q==NULL))
3178  {
3179 #ifdef HAVE_PLURAL
3180  if(p != pp)
3181  return pp;
3182 #endif
3183  return pCopy(p); /*F+Q=0*/
3184  }
3185 
3186  kStrategy strat=new skStrategy;
3187  strat->syzComp = syzComp;
3188  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3189  poly res;
3190 
3192  {
3193 #ifdef HAVE_SHIFTBBA
3194  if (currRing->isLPring)
3195  {
3196  WerrorS("No local ordering possible for shift algebra");
3197  return(NULL);
3198  }
3199 #endif
3200  res=kNF1(F,Q,pp,strat,lazyReduce);
3201  }
3202  else
3203  res=kNF2(F,Q,pp,strat,lazyReduce);
3204  delete(strat);
3205 
3206 #ifdef HAVE_PLURAL
3207  if(pp != p)
3208  p_Delete(&pp, currRing);
3209 #endif
3210  return res;
3211 }
3212 
3213 poly kNFBound(ideal F, ideal Q, poly p,int bound,int syzComp, int lazyReduce)
3214 {
3215  if (p==NULL)
3216  return NULL;
3217 
3218  poly pp = p;
3219 
3220 #ifdef HAVE_PLURAL
3221  if(rIsSCA(currRing))
3222  {
3223  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3224  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3225  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3226 
3227  if(Q == currRing->qideal)
3228  Q = SCAQuotient(currRing);
3229  }
3230 #endif
3231 
3232  if ((idIs0(F))&&(Q==NULL))
3233  {
3234 #ifdef HAVE_PLURAL
3235  if(p != pp)
3236  return pp;
3237 #endif
3238  return pCopy(p); /*F+Q=0*/
3239  }
3240 
3241  kStrategy strat=new skStrategy;
3242  strat->syzComp = syzComp;
3243  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
3244  poly res;
3245  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3246  delete(strat);
3247 
3248 #ifdef HAVE_PLURAL
3249  if(pp != p)
3250  p_Delete(&pp, currRing);
3251 #endif
3252  return res;
3253 }
3254 
3255 ideal kNF(ideal F, ideal Q, ideal p,int syzComp,int lazyReduce)
3256 {
3257  ideal res;
3258  if (TEST_OPT_PROT)
3259  {
3260  Print("(S:%d)",IDELEMS(p));mflush();
3261  }
3262  if (idIs0(p))
3263  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3264 
3265  ideal pp = p;
3266 #ifdef HAVE_PLURAL
3267  if(rIsSCA(currRing))
3268  {
3269  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3270  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3271  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3272 
3273  if(Q == currRing->qideal)
3274  Q = SCAQuotient(currRing);
3275  }
3276 #endif
3277 
3278  if ((idIs0(F))&&(Q==NULL))
3279  {
3280 #ifdef HAVE_PLURAL
3281  if(p != pp)
3282  return pp;
3283 #endif
3284  return idCopy(p); /*F+Q=0*/
3285  }
3286 
3287  kStrategy strat=new skStrategy;
3288  strat->syzComp = syzComp;
3290  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3291  {
3292  strat->ak = si_max(strat->ak,(int)F->rank);
3293  }
3294 
3296  {
3297 #ifdef HAVE_SHIFTBBA
3298  if (currRing->isLPring)
3299  {
3300  WerrorS("No local ordering possible for shift algebra");
3301  return(NULL);
3302  }
3303 #endif
3304  res=kNF1(F,Q,pp,strat,lazyReduce);
3305  }
3306  else
3307  res=kNF2(F,Q,pp,strat,lazyReduce);
3308  delete(strat);
3309 
3310 #ifdef HAVE_PLURAL
3311  if(pp != p)
3312  id_Delete(&pp, currRing);
3313 #endif
3314 
3315  return res;
3316 }
3317 
3318 ideal kNFBound(ideal F, ideal Q, ideal p,int bound,int syzComp,int lazyReduce)
3319 {
3320  ideal res;
3321  if (TEST_OPT_PROT)
3322  {
3323  Print("(S:%d)",IDELEMS(p));mflush();
3324  }
3325  if (idIs0(p))
3326  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3327 
3328  ideal pp = p;
3329 #ifdef HAVE_PLURAL
3330  if(rIsSCA(currRing))
3331  {
3332  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3333  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3334  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3335 
3336  if(Q == currRing->qideal)
3337  Q = SCAQuotient(currRing);
3338  }
3339 #endif
3340 
3341  if ((idIs0(F))&&(Q==NULL))
3342  {
3343 #ifdef HAVE_PLURAL
3344  if(p != pp)
3345  return pp;
3346 #endif
3347  return idCopy(p); /*F+Q=0*/
3348  }
3349 
3350  kStrategy strat=new skStrategy;
3351  strat->syzComp = syzComp;
3353  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3354  {
3355  strat->ak = si_max(strat->ak,(int)F->rank);
3356  }
3357 
3358  res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3359  delete(strat);
3360 
3361 #ifdef HAVE_PLURAL
3362  if(pp != p)
3363  id_Delete(&pp, currRing);
3364 #endif
3365 
3366  return res;
3367 }
3368 
3369 poly k_NF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing)
3370 {
3371  const ring save = currRing;
3372  if( currRing != _currRing ) rChangeCurrRing(_currRing);
3373  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3374  if( currRing != save ) rChangeCurrRing(save);
3375  return ret;
3376 }
3377 
3378 /*2
3379 *interreduces F
3380 */
3381 // old version
3382 ideal kInterRedOld (ideal F, ideal Q)
3383 {
3384  int j;
3385  kStrategy strat = new skStrategy;
3386 
3387  ideal tempF = F;
3388  ideal tempQ = Q;
3389 
3390 #ifdef HAVE_PLURAL
3391  if(rIsSCA(currRing))
3392  {
3393  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3394  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3395  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3396 
3397  // this should be done on the upper level!!! :
3398  // tempQ = SCAQuotient(currRing);
3399 
3400  if(Q == currRing->qideal)
3401  tempQ = SCAQuotient(currRing);
3402  }
3403 #endif
3404 
3405 // if (TEST_OPT_PROT)
3406 // {
3407 // writeTime("start InterRed:");
3408 // mflush();
3409 // }
3410  //strat->syzComp = 0;
3411  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3412  strat->kNoether=pCopy((currRing->ppNoether));
3413  strat->ak = id_RankFreeModule(tempF,currRing);
3414  initBuchMoraCrit(strat);
3415  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3416  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3417  strat->enterS = enterSBba;
3418  strat->posInT = posInT17;
3419  strat->initEcart = initEcartNormal;
3420  strat->sl = -1;
3421  strat->tl = -1;
3422  strat->tmax = setmaxT;
3423  strat->T = initT();
3424  strat->R = initR();
3425  strat->sevT = initsevT();
3427  initS(tempF, tempQ, strat);
3428  if (TEST_OPT_REDSB)
3429  strat->noTailReduction=FALSE;
3430  updateS(TRUE,strat);
3432  completeReduce(strat);
3433  //else if (TEST_OPT_PROT) PrintLn();
3434  cleanT(strat);
3435  if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3436  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3437  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3438  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3439  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3440  omfree(strat->sevT);
3441  omfree(strat->S_2_R);
3442  omfree(strat->R);
3443 
3444  if (strat->fromQ)
3445  {
3446  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3447  {
3448  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3449  }
3450  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3451  }
3452 // if (TEST_OPT_PROT)
3453 // {
3454 // writeTime("end Interred:");
3455 // mflush();
3456 // }
3457  ideal shdl=strat->Shdl;
3458  idSkipZeroes(shdl);
3459  if (strat->fromQ)
3460  {
3461  strat->fromQ=NULL;
3462  ideal res=kInterRed(shdl,NULL);
3463  idDelete(&shdl);
3464  shdl=res;
3465  }
3466  delete(strat);
3467 #ifdef HAVE_PLURAL
3468  if( tempF != F )
3469  id_Delete( &tempF, currRing);
3470 #endif
3471  return shdl;
3472 }
3473 // new version
3474 ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
3475 {
3476  need_retry=0;
3477  int red_result = 1;
3478  int olddeg,reduc;
3479  BOOLEAN withT = FALSE;
3480  // BOOLEAN toReset=FALSE;
3481  kStrategy strat=new skStrategy;
3482  tHomog h;
3483 
3485  strat->LazyPass=20;
3486  else
3487  strat->LazyPass=2;
3488  strat->LazyDegree = 1;
3489  strat->ak = id_RankFreeModule(F,currRing);
3490  strat->syzComp = strat->ak;
3491  strat->kModW=kModW=NULL;
3492  strat->kHomW=kHomW=NULL;
3493  if (strat->ak == 0)
3494  {
3495  h = (tHomog)idHomIdeal(F,Q);
3496  }
3497  else if (!TEST_OPT_DEGBOUND)
3498  {
3499  h = (tHomog)idHomIdeal(F,Q);
3500  }
3501  else
3502  h = isNotHomog;
3503  if (h==isHomog)
3504  {
3505  strat->LazyPass*=2;
3506  }
3507  strat->homog=h;
3508 #ifdef KDEBUG
3509  idTest(F);
3510 #endif
3511 
3512  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3514  initBuchMoraPosRing(strat);
3515  else
3516  initBuchMoraPos(strat);
3517  initBba(strat);
3518  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3519  strat->posInL=posInL0; /* ord according pComp */
3520 
3521  /*Shdl=*/initBuchMora(F, Q, strat);
3522  reduc = olddeg = 0;
3523 
3524 #ifndef NO_BUCKETS
3525  if (!TEST_OPT_NOT_BUCKETS)
3526  strat->use_buckets = 1;
3527 #endif
3528 
3529  // redtailBBa against T for inhomogenous input
3530  if (!TEST_OPT_OLDSTD)
3531  withT = ! strat->homog;
3532 
3533  // strat->posInT = posInT_pLength;
3534  kTest_TS(strat);
3535 
3536 #ifdef HAVE_TAIL_RING
3537  kStratInitChangeTailRing(strat);
3538 #endif
3539 
3540  /* compute------------------------------------------------------- */
3541  while (strat->Ll >= 0)
3542  {
3543  #ifdef KDEBUG
3544  if (TEST_OPT_DEBUG) messageSets(strat);
3545  #endif
3546  if (strat->Ll== 0) strat->interpt=TRUE;
3547  /* picks the last element from the lazyset L */
3548  strat->P = strat->L[strat->Ll];
3549  strat->Ll--;
3550 
3551  if (strat->P.p1 == NULL)
3552  {
3553  // for input polys, prepare reduction
3554  strat->P.PrepareRed(strat->use_buckets);
3555  }
3556 
3557  if (strat->P.p == NULL && strat->P.t_p == NULL)
3558  {
3559  red_result = 0;
3560  }
3561  else
3562  {
3563  if (TEST_OPT_PROT)
3564  message(strat->P.pFDeg(),
3565  &olddeg,&reduc,strat, red_result);
3566 
3567  /* reduction of the element chosen from L */
3568  red_result = strat->red(&strat->P,strat);
3569  }
3570 
3571  // reduction to non-zero new poly
3572  if (red_result == 1)
3573  {
3574  /* statistic */
3575  if (TEST_OPT_PROT) PrintS("s");
3576 
3577  // get the polynomial (canonicalize bucket, make sure P.p is set)
3578  strat->P.GetP(strat->lmBin);
3579 
3580  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3581 
3582  // reduce the tail and normalize poly
3583  // in the ring case we cannot expect LC(f) = 1,
3584  // therefore we call pCleardenom instead of pNorm
3586  {
3587  strat->P.pCleardenom();
3588  if (0)
3589  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3590  {
3591  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3592  strat->P.pCleardenom();
3593  }
3594  }
3595  else
3596  {
3597  strat->P.pNorm();
3598  if (0)
3599  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3600  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3601  }
3602 
3603 #ifdef KDEBUG
3604  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3605 #endif
3606 
3607  // enter into S, L, and T
3608  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3609  {
3610  enterT(strat->P, strat);
3611  // posInS only depends on the leading term
3612  strat->enterS(strat->P, pos, strat, strat->tl);
3613 
3614  if (pos<strat->sl)
3615  {
3616  need_retry++;
3617  // move all "larger" elements fromS to L
3618  // remove them from T
3619  int ii=pos+1;
3620  for(;ii<=strat->sl;ii++)
3621  {
3622  LObject h;
3623  h.Clear();
3624  h.tailRing=strat->tailRing;
3625  h.p=strat->S[ii]; strat->S[ii]=NULL;
3626  strat->initEcart(&h);
3627  h.sev=strat->sevS[ii];
3628  int jj=strat->tl;
3629  while (jj>=0)
3630  {
3631  if (strat->T[jj].p==h.p)
3632  {
3633  strat->T[jj].p=NULL;
3634  if (jj<strat->tl)
3635  {
3636  memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3637  (strat->tl-jj)*sizeof(strat->T[jj]));
3638  memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3639  (strat->tl-jj)*sizeof(strat->sevT[jj]));
3640  }
3641  strat->tl--;
3642  break;
3643  }
3644  jj--;
3645  }
3646  int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3647  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3648  #ifdef KDEBUG
3649  if (TEST_OPT_DEBUG)
3650  {
3651  Print("move S[%d] -> L[%d]: ",ii,pos);
3652  p_wrp(h.p,currRing, strat->tailRing);
3653  PrintLn();
3654  }
3655  #endif
3656  }
3657  if (strat->fromQ!=NULL)
3658  {
3659  for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3660  }
3661  strat->sl=pos;
3662  }
3663  }
3664  else
3665  {
3666  // clean P
3667  }
3668  kDeleteLcm(&strat->P);
3669  }
3670 
3671 #ifdef KDEBUG
3672  if (TEST_OPT_DEBUG)
3673  {
3674  messageSets(strat);
3675  }
3676  strat->P.Clear();
3677 #endif
3678  //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3679  }
3680 #ifdef KDEBUG
3681  //if (TEST_OPT_DEBUG) messageSets(strat);
3682 #endif
3683  /* complete reduction of the standard basis--------- */
3684 
3685  if((need_retry<=0) && (TEST_OPT_REDSB))
3686  {
3687  completeReduce(strat);
3688  if (strat->completeReduce_retry)
3689  {
3690  // completeReduce needed larger exponents, retry
3691  // hopefully: kStratChangeTailRing already provided a larger tailRing
3692  // (otherwise: it will fail again)
3693  strat->completeReduce_retry=FALSE;
3694  completeReduce(strat);
3695  if (strat->completeReduce_retry)
3696  {
3697 #ifdef HAVE_TAIL_RING
3698  if(currRing->bitmask>strat->tailRing->bitmask)
3699  {
3700  // retry without T
3701  strat->completeReduce_retry=FALSE;
3702  cleanT(strat);strat->tailRing=currRing;
3703  int i;
3704  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3705  completeReduce(strat);
3706  }
3707  if (strat->completeReduce_retry)
3708 #endif
3709  Werror("exponent bound is %ld",currRing->bitmask);
3710  }
3711  }
3712  }
3713  else if (TEST_OPT_PROT) PrintLn();
3714 
3715 
3716  /* release temp data-------------------------------- */
3717  exitBuchMora(strat);
3718 // if (TEST_OPT_WEIGHTM)
3719 // {
3720 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3721 // if (ecartWeights)
3722 // {
3723 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3724 // ecartWeights=NULL;
3725 // }
3726 // }
3727  //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3728  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3729  ideal res=strat->Shdl;
3730  strat->Shdl=NULL;
3731  delete strat;
3732  return res;
3733 }
3734 ideal kInterRed (ideal F, ideal Q)
3735 {
3736 #ifdef HAVE_PLURAL
3737  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3738 #endif
3741  )
3742  return kInterRedOld(F,Q);
3743 
3744  //return kInterRedOld(F,Q);
3745 
3746  BITSET save1;
3747  SI_SAVE_OPT1(save1);
3748  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3750  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3751  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3752  //extern char * showOption() ;
3753  //Print("%s\n",showOption());
3754 
3755  int need_retry;
3756  int counter=3;
3757  ideal res, res1;
3758  int elems;
3759  ideal null=NULL;
3760  if ((Q==NULL) || (!TEST_OPT_REDSB))
3761  {
3762  elems=idElem(F);
3763  res=kInterRedBba(F,Q,need_retry);
3764  }
3765  else
3766  {
3767  ideal FF=idSimpleAdd(F,Q);
3768  res=kInterRedBba(FF,NULL,need_retry);
3769  idDelete(&FF);
3770  null=idInit(1,1);
3771  if (need_retry)
3772  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3773  else
3774  res1=kNF(null,Q,res);
3775  idDelete(&res);
3776  res=res1;
3777  need_retry=1;
3778  }
3779  if (idElem(res)<=1) need_retry=0;
3780  while (need_retry && (counter>0))
3781  {
3782  #ifdef KDEBUG
3783  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3784  #endif
3785  res1=kInterRedBba(res,Q,need_retry);
3786  int new_elems=idElem(res1);
3787  counter -= (new_elems >= elems);
3788  elems = new_elems;
3789  idDelete(&res);
3790  if (idElem(res1)<=1) need_retry=0;
3791  if ((Q!=NULL) && (TEST_OPT_REDSB))
3792  {
3793  if (need_retry)
3794  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3795  else
3796  res=kNF(null,Q,res1);
3797  idDelete(&res1);
3798  }
3799  else
3800  res = res1;
3801  if (idElem(res)<=1) need_retry=0;
3802  }
3803  if (null!=NULL) idDelete(&null);
3804  SI_RESTORE_OPT1(save1);
3805  idSkipZeroes(res);
3806  return res;
3807 }
3808 
3809 // returns TRUE if mora should use buckets, false otherwise
3811 {
3812 #ifdef MORA_USE_BUCKETS
3814  return FALSE;
3815  if (strat->red == redFirst)
3816  {
3817 #ifdef NO_LDEG
3818  if (strat->syzComp==0)
3819  return TRUE;
3820 #else
3821  if ((strat->homog || strat->honey) && (strat->syzComp==0))
3822  return TRUE;
3823 #endif
3824  }
3825  else
3826  {
3827  #ifdef HAVE_RINGS
3828  assume(strat->red == redEcart || strat->red == redRiloc);
3829  #else
3830  assume(strat->red == redEcart);
3831  #endif
3832  if (strat->honey && (strat->syzComp==0))
3833  return TRUE;
3834  }
3835 #endif
3836  return FALSE;
3837 }
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
void * ADDRESS
Definition: auxiliary.h:119
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
CanonicalForm b
Definition: cfModGcd.cc:4105
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
Definition: intvec.h:23
KINLINE poly kNoetherTail()
Definition: kInline.h:66
intvec * kModW
Definition: kutil.h:334
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
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:288
char noTailReduction
Definition: kutil.h:378
int currIdx
Definition: kutil.h:314
char posInLOldFlag
Definition: kutil.h:382
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:295
int Ll
Definition: kutil.h:350
TSet T
Definition: kutil.h:323
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:290
omBin lmBin
Definition: kutil.h:343
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
BOOLEAN * NotUsedAxis
Definition: kutil.h:331
LSet B
Definition: kutil.h:325
int ak
Definition: kutil.h:352
TObject ** R
Definition: kutil.h:339
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:292
poly kHEdge
Definition: kutil.h:326
int lastAxis
Definition: kutil.h:355
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
intvec * kHomW
Definition: kutil.h:335
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
unsigned sbaOrder
Definition: kutil.h:313
pFDegProc pOrigFDeg
Definition: kutil.h:293
int blockredmax
Definition: kutil.h:365
int tmax
Definition: kutil.h:349
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:285
char LDegLast
Definition: kutil.h:385
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:284
intset fromQ
Definition: kutil.h:318
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:283
char use_buckets
Definition: kutil.h:383
char interpt
Definition: kutil.h:371
int newIdeal
Definition: kutil.h:356
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
char z2homog
Definition: kutil.h:374
int LazyPass
Definition: kutil.h:352
char no_prod_crit
Definition: kutil.h:394
char overflow
Definition: kutil.h:404
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:287
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 kHEdgeFound
Definition: kutil.h:376
char posInLDependsOnLength
Definition: kutil.h:389
unsigned long * sevS
Definition: kutil.h:319
int HCord
Definition: kutil.h:354
char homog
Definition: kutil.h:372
pLDegProc pOrigLDeg
Definition: kutil.h:294
char update
Definition: kutil.h:381
s_poly_proc_t s_poly
Definition: kutil.h:297
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:296
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:840
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition: coeffs.h:516
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition: coeffs.h:704
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
#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
CanonicalForm H
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define VAR
Definition: globaldefs.h:5
int scMult0Int(ideal S, ideal Q, const ring tailRing)
Definition: hdegree.cc:992
STATIC_VAR poly last
Definition: hdegree.cc:1150
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
#define idTest(id)
Definition: ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:91
ideal idCopy(ideal A)
Definition: ideals.h:60
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR Poly * h
Definition: janet.cc:971
STATIC_VAR jList * Q
Definition: janet.cc:30
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
KINLINE TSet initT()
Definition: kInline.h:84
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1180
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition: kInline.h:1225
KINLINE TObject ** initR()
Definition: kInline.h:95
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:161
static ideal nc_GB(const ideal F, const ideal Q, const intvec *w, const intvec *hilb, kStrategy strat, const ring r)
Definition: nc.h:27
void khCheckLocInhom(ideal Q, intvec *w, intvec *hilb, int &count, kStrategy strat)
Definition: khstd.cc:133
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
ideal kInterRedOld(ideal F, ideal Q)
Definition: kstd1.cc:3382
void reorderT(kStrategy strat)
Definition: kstd1.cc:1212
poly kNFBound(ideal F, ideal Q, poly p, int bound, int syzComp, int lazyReduce)
Definition: kstd1.cc:3213
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd1.cc:1848
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1787
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:784
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1528
poly k_NF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce, const ring _currRing)
NOTE: this is just a wrapper which sets currRing for the actual kNF call.
Definition: kstd1.cc:3369
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1649
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2396
static int doRed(LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
Definition: kstd1.cc:119
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition: kstd1.cc:3009
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1435
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 missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:1250
void reorderL(kStrategy strat)
Definition: kstd1.cc:1192
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1331
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3474
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3810
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:2097
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:100
void initBba(kStrategy strat)
Definition: kstd1.cc:1659
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:383
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1717
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2406
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1056
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:12080
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1595
VAR intvec * kHomW
Definition: kstd1.cc:2394
VAR intvec * kModW
Definition: kstd1.cc:2394
void updateL(kStrategy strat)
Definition: kstd1.cc:1364
VAR BITSET validOpts
Definition: kstd1.cc:60
void updateT(kStrategy strat)
Definition: kstd1.cc:1502
BOOLEAN hasPurePower(const poly p, int last, int *length, kStrategy strat)
Definition: kstd1.cc:1283
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3158
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:956
VAR BITSET kOptions
Definition: kstd1.cc:45
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:564
ideal kSba(ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, intvec *hilb, int syzComp, int newIdeal, intvec *vw)
Definition: kstd1.cc:2604
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2419
#define KSTD_NF_LAZY
Definition: kstd1.h:17
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition: kstd1.h:14
#define KSTD_NF_ECART
Definition: kstd1.h:19
EXTERN_VAR int Kstd1_mu
Definition: kstd1.h:49
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:640
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 kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3712
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1842
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
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1111
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
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:8033
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7480
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5805
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10322
VAR int HCord
Definition: kutil.cc:246
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition: kutil.cc:7287
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9699
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:7262
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9473
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1010
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1071
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:1975
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1301
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition: kutil.cc:7203
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5370
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 initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9979
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1347
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
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6139
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3476
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9799
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
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:475
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10406
void initEcartNormal(TObject *h)
Definition: kutil.cc:1325
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:5109
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:9115
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:11045
void cleanT(kStrategy strat)
Definition: kutil.cc:545
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 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
BOOLEAN kTest_T(TObject *T, ring strat_tailRing, int i, char TN)
Definition: kutil.cc:801
void messageSets(kStrategy strat)
Definition: kutil.cc:8106
poly preIntegerCheck(const ideal Forig, const ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition: kutil.cc:11107
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3240
void initEcartBBA(TObject *h)
Definition: kutil.cc:1333
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1340
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:8074
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
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10981
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:343
#define setmaxTinc
Definition: kutil.h:34
LObject * LSet
Definition: kutil.h:56
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
#define setmaxT
Definition: kutil.h:33
class sTObject TObject
Definition: kutil.h:53
class sLObject LObject
Definition: kutil.h:54
if(yy_init)
Definition: libparse.cc:1420
static bool rIsSCA(const ring r)
Definition: nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1520
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1465
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 nEqual(n1, n2)
Definition: numbers.h:20
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
omError_t omTestMemory(int check_level)
Definition: omDebug.c:94
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define NULL
Definition: omList.c:12
VAR BOOLEAN siCntrlc
Definition: options.c:14
VAR unsigned si_opt_1
Definition: options.c:5
#define TEST_OPT_WEIGHTM
Definition: options.h:120
#define OPT_SUGARCRIT
Definition: options.h:79
#define OPT_PROT
Definition: options.h:74
#define OPT_INFREDTAIL
Definition: options.h:93
#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 OPT_WEIGHTM
Definition: options.h:96
#define TEST_OPT_FINDET
Definition: options.h:110
#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 OPT_NOT_SUGAR
Definition: options.h:77
#define TEST_OPT_OLDSTD
Definition: options.h:122
#define OPT_REDTHROUGH
Definition: options.h:81
#define OPT_REDSB
Definition: options.h:75
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:103
#define OPT_NOTREGULARITY
Definition: options.h:95
#define TEST_OPT_DEGBOUND
Definition: options.h:112
#define TEST_OPT_SB_1
Definition: options.h:118
#define TEST_OPT_RETURN_SB
Definition: options.h:111
#define TEST_OPT_MULTBOUND
Definition: options.h:113
#define TEST_OPT_PROT
Definition: options.h:102
#define TEST_OPT_REDTHROUGH
Definition: options.h:121
#define OPT_INTERRUPT
Definition: options.h:78
#define OPT_DEGBOUND
Definition: options.h:89
#define TEST_V_DEG_STOP
Definition: options.h:136
#define TEST_OPT_FASTHC
Definition: options.h:108
#define TEST_OPT_DEBUG
Definition: options.h:107
#define OPT_FASTHC
Definition: options.h:84
#define TEST_OPT_REDTAIL_SYZ
Definition: options.h:116
#define OPT_OLDSTD
Definition: options.h:85
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:114
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:104
pShallowCopyDeleteProc pGetShallowCopyDeleteProc(ring, ring)
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1221
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3719
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:765
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:734
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3707
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:709
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:711
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:313
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:164
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 void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
static unsigned pLength(poly a)
Definition: p_polys.h:191
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:373
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 pAdd(p, q)
Definition: polys.h:203
#define pTest(p)
Definition: polys.h:415
#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 pSetm(p)
Definition: polys.h:271
#define pIsConstant(p)
like above, except that Comp must be 0
Definition: polys.h:238
#define pGetComp(p)
Component.
Definition: polys.h:37
#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 pMaxComp(p)
Definition: polys.h:299
#define pSetComp(p, v)
Definition: polys.h:38
#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
#define pSetmComp(p)
TODO:
Definition: polys.h:273
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 pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define pOne()
Definition: polys.h:315
#define pWTotaldegree(p)
Definition: polys.h:283
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
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
long(* pLDegProc)(poly p, int *length, ring r)
Definition: ring.h:37
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:520
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:766
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:597
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:764
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:765
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:553
ideal SCAQuotient(const ring r)
Definition: sca.h:10
static short scaLastAltVar(ring r)
Definition: sca.h:25
static short scaFirstAltVar(ring r)
Definition: sca.h:18
#define idIsInV(I)
Definition: shiftop.h:49
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
int idElem(const ideal F)
count non-zero elements
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23
#define M
Definition: sirandom.c:25
tHomog
Definition: structs.h:40
@ isHomog
Definition: structs.h:42
@ testHomog
Definition: structs.h:43
@ isNotHomog
Definition: structs.h:41
#define BITSET
Definition: structs.h:20
#define loop
Definition: structs.h:80
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition: weight.cc:247
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition: weight.cc:182
EXTERN_VAR short * ecartWeights
Definition: weight.h:12