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