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