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 */
1224 {
1225  int i = 0;
1226  LObject p;
1227 
1228  while (i <= strat->tl)
1229  {
1230  p = strat->T[i];
1231  deleteHC(&p,strat, TRUE);
1232  /*- tries to cancel a unit: -*/
1233  cancelunit(&p);
1234  if (p.p != strat->T[i].p)
1235  {
1236  strat->sevT[i] = pGetShortExpVector(p.p);
1237  p.SetpFDeg();
1238  }
1239  strat->T[i] = p;
1240  i++;
1241  }
1242 }
1243 
1244 /*2
1245 * arranges red, pos and T if strat->kHEdgeFound (first time)
1246 */
1248 {
1249  if (strat->update)
1250  {
1251  kTest_TS(strat);
1252  strat->update = (strat->tl == -1);
1253  if (TEST_OPT_WEIGHTM)
1254  {
1255  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1256  if (strat->tailRing != currRing)
1257  {
1258  strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1259  strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1260  }
1261  int i;
1262  for (i=strat->Ll; i>=0; i--)
1263  {
1264  strat->L[i].SetpFDeg();
1265  }
1266  for (i=strat->tl; i>=0; i--)
1267  {
1268  strat->T[i].SetpFDeg();
1269  }
1270  if (ecartWeights)
1271  {
1272  omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1273  ecartWeights=NULL;
1274  }
1275  }
1276  if (TEST_OPT_FASTHC)
1277  {
1278  strat->posInL = strat->posInLOld;
1279  strat->lastAxis = 0;
1280  }
1281  if (TEST_OPT_FINDET)
1282  return;
1283 
1284 #ifndef HAVE_RINGS
1285  strat->red = redFirst;
1286  strat->use_buckets = kMoraUseBucket(strat);
1287 #else
1289  {
1290  strat->red = redFirst;
1291  strat->use_buckets = kMoraUseBucket(strat);
1292  }
1293 #endif
1294  updateT(strat);
1295 
1296 #ifndef HAVE_RINGS
1297  strat->posInT = posInT2;
1298  reorderT(strat);
1299 #else
1301  {
1302  strat->posInT = posInT2;
1303  reorderT(strat);
1304  }
1305 #endif
1306  }
1307  kTest_TS(strat);
1308 }
1309 
1310 /*2
1311 *-puts p to the standardbasis s at position at
1312 *-reduces the tail of p if TEST_OPT_REDTAIL
1313 *-tries to cancel a unit
1314 *-HEckeTest
1315 * if TRUE
1316 * - decides about reduction-strategies
1317 * - computes noether
1318 * - stops computation if TEST_OPT_FINDET
1319 * - cuts the tails of the polynomials
1320 * in s,t and the elements in L above noether
1321 * and cancels units if possible
1322 * - reorders s,L
1323 */
1324 void enterSMora (LObject &p,int atS,kStrategy strat, int atR = -1)
1325 {
1326  enterSBba(p, atS, strat, atR);
1327  #ifdef KDEBUG
1328  if (TEST_OPT_DEBUG)
1329  {
1330  Print("new s%d:",atS);
1331  p_wrp(p.p,currRing,strat->tailRing);
1332  PrintLn();
1333  }
1334  #endif
1335  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1336  if (strat->kHEdgeFound)
1337  {
1338  if (newHEdge(strat))
1339  {
1340  firstUpdate(strat);
1341  if (TEST_OPT_FINDET)
1342  return;
1343 
1344  /*- cuts elements in L above noether and reorders L -*/
1345  updateLHC(strat);
1346  /*- reorders L with respect to posInL -*/
1347  reorderL(strat);
1348  }
1349  }
1350  else if (strat->kNoether!=NULL)
1351  strat->kHEdgeFound = TRUE;
1352  else if (TEST_OPT_FASTHC)
1353  {
1354  if (strat->posInLOldFlag)
1355  {
1356  missingAxis(&strat->lastAxis,strat);
1357  if (strat->lastAxis)
1358  {
1359  strat->posInLOld = strat->posInL;
1360  strat->posInLOldFlag = FALSE;
1361  strat->posInL = posInL10;
1362  strat->posInLDependsOnLength = TRUE;
1363  updateL(strat);
1364  reorderL(strat);
1365  }
1366  }
1367  else if (strat->lastAxis)
1368  updateL(strat);
1369  }
1370 }
1371 
1372 /*2
1373 *-puts p to the standardbasis s at position at
1374 *-HEckeTest
1375 * if TRUE
1376 * - computes noether
1377 */
1378 void enterSMoraNF (LObject &p, int atS,kStrategy strat, int atR = -1)
1379 {
1380  enterSBba(p, atS, strat, atR);
1381  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1382  if (strat->kHEdgeFound)
1383  newHEdge(strat);
1384  else if (strat->kNoether!=NULL)
1385  strat->kHEdgeFound = TRUE;
1386 }
1387 
1388 void initBba(ideal /*F*/,kStrategy strat)
1389 {
1390  /* setting global variables ------------------- */
1391  strat->enterS = enterSBba;
1392  strat->red = redHoney;
1393  if (strat->honey)
1394  strat->red = redHoney;
1395  else if (currRing->pLexOrder && !strat->homog)
1396  strat->red = redLazy;
1397  else
1398  {
1399  strat->LazyPass *=4;
1400  strat->red = redHomog;
1401  }
1402 #ifdef HAVE_RINGS //TODO Oliver
1403  if (rField_is_Ring(currRing))
1404  {
1405  strat->red = redRing;
1406  }
1407 #endif
1408  if (currRing->pLexOrder && strat->honey)
1409  strat->initEcart = initEcartNormal;
1410  else
1411  strat->initEcart = initEcartBBA;
1412  if (strat->honey)
1414  else
1416 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1417 // {
1418 // //interred machen Aenderung
1419 // strat->pOrigFDeg=pFDeg;
1420 // strat->pOrigLDeg=pLDeg;
1421 // //h=ggetid("ecart");
1422 // //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1423 // //{
1424 // // ecartWeights=iv2array(IDINTVEC(h));
1425 // //}
1426 // //else
1427 // {
1428 // ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1429 // /*uses automatic computation of the ecartWeights to set them*/
1430 // kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1431 // }
1432 // pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1433 // if (TEST_OPT_PROT)
1434 // {
1435 // for(i=1; i<=(currRing->N); i++)
1436 // Print(" %d",ecartWeights[i]);
1437 // PrintLn();
1438 // mflush();
1439 // }
1440 // }
1441 }
1442 
1443 void initSba(ideal F,kStrategy strat)
1444 {
1445  int i;
1446  //idhdl h;
1447  /* setting global variables ------------------- */
1448  strat->enterS = enterSSba;
1449  strat->red2 = redHoney;
1450  if (strat->honey)
1451  strat->red2 = redHoney;
1452  else if (currRing->pLexOrder && !strat->homog)
1453  strat->red2 = redLazy;
1454  else
1455  {
1456  strat->LazyPass *=4;
1457  strat->red2 = redHomog;
1458  }
1459 #if defined(HAVE_RINGS)
1460  if (rField_is_Ring(currRing))
1461  {
1463  {strat->red = redRiloc;}
1464  else
1465  {strat->red2 = redRing;}
1466  }
1467 #endif
1468  if (currRing->pLexOrder && strat->honey)
1469  strat->initEcart = initEcartNormal;
1470  else
1471  strat->initEcart = initEcartBBA;
1472  if (strat->honey)
1474  else
1476  //strat->kIdeal = NULL;
1477  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1478  //else strat->kIdeal->rtyp=MODUL_CMD;
1479  //strat->kIdeal->data=(void *)strat->Shdl;
1480  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1481  {
1482  //interred machen Aenderung
1483  strat->pOrigFDeg = currRing->pFDeg;
1484  strat->pOrigLDeg = currRing->pLDeg;
1485  //h=ggetid("ecart");
1486  //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1487  //{
1488  // ecartWeights=iv2array(IDINTVEC(h));
1489  //}
1490  //else
1491  {
1492  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1493  /*uses automatic computation of the ecartWeights to set them*/
1495  }
1497  if (TEST_OPT_PROT)
1498  {
1499  for(i=1; i<=(currRing->N); i++)
1500  Print(" %d",ecartWeights[i]);
1501  PrintLn();
1502  mflush();
1503  }
1504  }
1505  // for sig-safe reductions in signature-based
1506  // standard basis computations
1507  strat->red = redSig;
1508  //strat->sbaOrder = 1;
1509  strat->currIdx = 1;
1510 }
1511 
1512 void initMora(ideal F,kStrategy strat)
1513 {
1514  int i,j;
1515 
1516  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1517  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1518  strat->enterS = enterSMora;
1519  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1520  strat->posInLOld = strat->posInL;
1521  strat->posInLOldFlag = TRUE;
1522  strat->initEcart = initEcartNormal;
1523  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1524  if ( strat->kHEdgeFound )
1525  strat->kNoether = pCopy((currRing->ppNoether));
1526  else if (strat->kHEdgeFound || strat->homog)
1527  strat->red = redFirst; /*take the first possible in T*/
1528  else
1529  strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1530  if (strat->kHEdgeFound)
1531  {
1532  strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1533  strat->posInT = posInT2;
1534  }
1535  else
1536  {
1537  strat->HCord = 32000;/*- very large -*/
1538  }
1539 
1540 #ifdef HAVE_RINGS
1541  if (rField_is_Ring(currRing))
1542  strat->red = redRiloc;
1543 #endif
1544 
1545  /*reads the ecartWeights used for Graebes method from the
1546  *intvec ecart and set ecartWeights
1547  */
1548  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1549  {
1550  //interred machen Aenderung
1551  strat->pOrigFDeg=currRing->pFDeg;
1552  strat->pOrigLDeg=currRing->pLDeg;
1553  ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1554  /*uses automatic computation of the ecartWeights to set them*/
1556 
1558  if (TEST_OPT_PROT)
1559  {
1560  for(i=1; i<=(currRing->N); i++)
1561  Print(" %d",ecartWeights[i]);
1562  PrintLn();
1563  mflush();
1564  }
1565  }
1566  kOptimizeLDeg(currRing->pLDeg, strat);
1567 }
1568 
1570 
1571 ideal mora (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1572 {
1573 #ifdef HAVE_RINGS
1574 #if ADIDEBUG
1575 int loop_count;
1576 loop_count = 1;
1577 #endif
1578 #endif
1579  int olddeg = 0;
1580  int reduc = 0;
1581  int red_result = 1;
1582  int hilbeledeg=1,hilbcount=0;
1583  BITSET save1;
1584  SI_SAVE_OPT1(save1);
1585  if (currRing->MixedOrder)
1586  {
1587  si_opt_1 &= ~Sy_bit(OPT_REDSB);
1589  }
1590 
1591  strat->update = TRUE;
1592  /*- setting global variables ------------------- -*/
1593  initBuchMoraCrit(strat);
1594  initHilbCrit(F,Q,&hilb,strat);
1595  initMora(F,strat);
1596  initBuchMoraPos(strat);
1597  /*Shdl=*/initBuchMora(F,Q,strat);
1598  if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1599  /*updateS in initBuchMora has Hecketest
1600  * and could have put strat->kHEdgdeFound FALSE*/
1601  if ((currRing->ppNoether)!=NULL)
1602  {
1603  strat->kHEdgeFound = TRUE;
1604  }
1605  if (strat->kHEdgeFound && strat->update)
1606  {
1607  firstUpdate(strat);
1608  updateLHC(strat);
1609  reorderL(strat);
1610  }
1611  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1612  {
1613  strat->posInLOld = strat->posInL;
1614  strat->posInLOldFlag = FALSE;
1615  strat->posInL = posInL10;
1616  updateL(strat);
1617  reorderL(strat);
1618  }
1619  kTest_TS(strat);
1620  strat->use_buckets = kMoraUseBucket(strat);
1621  /*- compute-------------------------------------------*/
1622 
1623 #ifdef HAVE_TAIL_RING
1624  if (strat->homog && strat->red == redFirst)
1625  if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1626  kStratInitChangeTailRing(strat);
1627 #endif
1628 
1629  if (BVERBOSE(23))
1630  {
1631  kDebugPrint(strat);
1632  }
1633 
1634  while (strat->Ll >= 0)
1635  {
1636  #if ADIDEBUG
1637  printf("\n ------------------------NEW LOOP\n");
1638  printf("\nShdl = \n");
1639  for(int iii = 0; iii<= strat->sl; iii++)
1640  {
1641  printf("S[%i]:",iii);
1642  p_Write(strat->S[iii], strat->tailRing);
1643  }
1644  printf("\n list L has %i\n", strat->Ll);
1645  int iii;
1646  #if ADIDEBUG
1647  for(iii = 0; iii<= strat->Ll; iii++)
1648  {
1649  printf("L[%i]:",iii);
1650  #if 0
1651  p_Write(strat->L[iii].p, strat->tailRing);
1652  p_Write(strat->L[iii].p1, strat->tailRing);
1653  p_Write(strat->L[iii].p2, strat->tailRing);
1654  #else
1655  pWrite(strat->L[iii].p);
1656  pWrite(strat->L[iii].p1);
1657  pWrite(strat->L[iii].p2);
1658  pWrite(strat->L[iii].lcm);
1659  #endif
1660  }
1661  #endif
1662  getchar();
1663  #endif
1664  #ifdef KDEBUG
1665  if (TEST_OPT_DEBUG) messageSets(strat);
1666  #endif
1667  if (TEST_OPT_DEGBOUND
1668  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1669  {
1670  /*
1671  * stops computation if
1672  * - 24 (degBound)
1673  * && upper degree is bigger than Kstd1_deg
1674  */
1675  while ((strat->Ll >= 0)
1676  && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1677  && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1678  )
1679  {
1680  deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1681  //if (TEST_OPT_PROT)
1682  //{
1683  // PrintS("D"); mflush();
1684  //}
1685  }
1686  if (strat->Ll<0) break;
1687  else strat->noClearS=TRUE;
1688  }
1689  strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1690  if (strat->Ll==0) strat->interpt=TRUE;
1691  strat->Ll--;
1692  //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);
1693  // create the real Spoly
1694  if (pNext(strat->P.p) == strat->tail)
1695  {
1696  /*- deletes the short spoly and computes -*/
1697 #ifdef HAVE_RINGS
1698  if (rField_is_Ring(currRing))
1699  pLmDelete(strat->P.p);
1700  else
1701 #endif
1702  pLmFree(strat->P.p);
1703  strat->P.p = NULL;
1704  poly m1 = NULL, m2 = NULL;
1705  // check that spoly creation is ok
1706  while (strat->tailRing != currRing &&
1707  !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1708  {
1709  assume(m1 == NULL && m2 == NULL);
1710  // if not, change to a ring where exponents are large enough
1711  kStratChangeTailRing(strat);
1712  }
1713  /* create the real one */
1714  ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1715  strat->tailRing, m1, m2, strat->R);
1716  if (!strat->use_buckets)
1717  strat->P.SetLength(strat->length_pLength);
1718  }
1719  else if (strat->P.p1 == NULL)
1720  {
1721  // for input polys, prepare reduction (buckets !)
1722  strat->P.SetLength(strat->length_pLength);
1723  strat->P.PrepareRed(strat->use_buckets);
1724  }
1725 
1726  if (!strat->P.IsNull())
1727  {
1728  // might be NULL from noether !!!
1729  if (TEST_OPT_PROT)
1730  message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1731  // reduce
1732  #if ADIDEBUG
1733  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);
1734  printf("\nBefore Ll = %i\n", strat->Ll);
1735  #endif
1736  #ifdef HAVE_RINGS
1737  if(rField_is_Ring(strat->tailRing) && rHasLocalOrMixedOrdering(currRing))
1738  {
1739  //int inittl = strat->tl;
1740  red_result = strat->red(&strat->P,strat);
1741  //strat->tl = inittl;
1742  }
1743  else
1744  #endif
1745  red_result = strat->red(&strat->P,strat);
1746  #if ADIDEBUG
1747  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);
1748  printf("\nAfter Ll = %i\n", strat->Ll);
1749  #endif
1750  }
1751 
1752  if (! strat->P.IsNull())
1753  {
1754  strat->P.GetP();
1755  // statistics
1756  if (TEST_OPT_PROT) PrintS("s");
1757  // normalization
1758  if (!TEST_OPT_INTSTRATEGY)
1759  strat->P.pNorm();
1760  // tailreduction
1761  strat->P.p = redtail(&(strat->P),strat->sl,strat);
1762  if (strat->P.p==NULL)
1763  {
1764  WerrorS("expoent overflow - wrong ordering");
1765  return(idInit(1,1));
1766  }
1767  // set ecart -- might have changed because of tail reductions
1768  if ((!strat->noTailReduction) && (!strat->honey))
1769  strat->initEcart(&strat->P);
1770  // cancel unit
1771  cancelunit(&strat->P);
1772  // for char 0, clear denominators
1774  strat->P.pCleardenom();
1775 
1776  // put in T
1777  //if(red_result!=3)
1778  {
1779  #ifdef HAVE_RINGS
1781  {
1782  //int inittl = strat->tl;
1783  enterT(strat->P,strat);
1784  //enterT_strong(strat->P,strat);
1785  //strat->tl = inittl+1;
1786  }
1787  else
1788  #endif
1789  enterT(strat->P,strat);
1790  //enterT_strong(strat->P,strat);
1791  }
1792  // build new pairs
1793 #ifdef HAVE_RINGS
1794  if (rField_is_Ring(currRing))
1795  {
1796  superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1797  }
1798  else
1799 #endif
1800  enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1801  // put in S
1802 
1803  #if ADIDEBUG
1804  Print("\n The new pair list L -- after superenterpairs in loop %d -- is:\n",loop_count);
1805  for(int iii=0;iii<=strat->Ll;iii++)
1806  {
1807  printf("\n L[%d]:\n",iii);
1808  PrintS(" ");p_Write(strat->L[iii].p,strat->tailRing);
1809  PrintS(" ");p_Write(strat->L[iii].p1,strat->tailRing);
1810  PrintS(" ");p_Write(strat->L[iii].p2,strat->tailRing);
1811  }
1812  #endif
1813  //if(red_result!=3)
1814  strat->enterS(strat->P,
1815  posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
1816  strat, strat->tl);
1817  #if ADIDEBUG
1818  printf("\nThis pair has been added to S:\n");
1819  pWrite(strat->P.p);
1820  pWrite(strat->P.p1);
1821  pWrite(strat->P.p2);
1822  #endif
1823 
1824  // apply hilbert criterion
1825  if (hilb!=NULL)
1826  {
1827  if (strat->homog==isHomog)
1828  khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
1829  else
1830  khCheckLocInhom(Q,w,hilb,hilbcount,strat);
1831  }
1832 
1833  // clear strat->P
1834  if (strat->P.lcm!=NULL)
1835 #if defined(HAVE_RINGS)
1836  pLmDelete(strat->P.lcm);
1837 #else
1838  pLmFree(strat->P.lcm);
1839 #endif
1840  strat->P.lcm=NULL;
1841 #ifdef KDEBUG
1842  // make sure kTest_TS does not complain about strat->P
1843  memset(&strat->P,0,sizeof(strat->P));
1844 #endif
1845  }
1846  if (strat->kHEdgeFound)
1847  {
1848  if ((TEST_OPT_FINDET)
1849  || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL,strat->tailRing) < Kstd1_mu)))
1850  {
1851  // obachman: is this still used ???
1852  /*
1853  * stops computation if strat->kHEdgeFound and
1854  * - 27 (finiteDeterminacyTest)
1855  * or
1856  * - 23
1857  * (multBound)
1858  * && multiplicity of the ideal is smaller then a predefined number mu
1859  */
1860  while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1861  }
1862  }
1863  kTest_TS(strat);
1864 
1865 #if ADIDEBUG
1866  Print("\n The new reducer list T -- at the end of loop %d -- is\n",loop_count);
1867  for(int iii=0;iii<=strat->tl;iii++)
1868  {
1869  printf("\n T[%d]:",iii);
1870  p_Write(strat->T[iii].p,strat->tailRing);
1871  }
1872  PrintLn();
1873 
1874  loop_count++;
1875 #endif /* ADIDEBUG */
1876  }
1877  /*- complete reduction of the standard basis------------------------ -*/
1878  if (TEST_OPT_REDSB) completeReduce(strat);
1879  else if (TEST_OPT_PROT) PrintLn();
1880  /*- release temp data------------------------------- -*/
1881  exitBuchMora(strat);
1882  /*- polynomials used for HECKE: HC, noether -*/
1883  if (TEST_OPT_FINDET)
1884  {
1885  if (strat->kHEdge!=NULL)
1886  Kstd1_mu=currRing->pFDeg(strat->kHEdge,currRing);
1887  else
1888  Kstd1_mu=-1;
1889  }
1890  pDelete(&strat->kHEdge);
1891  strat->update = TRUE; //???
1892  strat->lastAxis = 0; //???
1893  pDelete(&strat->kNoether);
1894  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
1895  if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
1896 // if (TEST_OPT_WEIGHTM)
1897 // {
1898 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
1899 // if (ecartWeights)
1900 // {
1901 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
1902 // ecartWeights=NULL;
1903 // }
1904 // }
1905 #ifdef HAVE_RINGS
1906  if(nCoeff_is_Ring_Z(currRing->cf))
1907  finalReduceByMon(strat);
1908 #endif
1909  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
1910  SI_RESTORE_OPT1(save1);
1911  idTest(strat->Shdl);
1912  return (strat->Shdl);
1913 }
1914 
1915 poly kNF1 (ideal F,ideal Q,poly q, kStrategy strat, int lazyReduce)
1916 {
1917  assume(q!=NULL);
1918  assume(!(idIs0(F)&&(Q==NULL)));
1919 
1920 // lazy_reduce flags: can be combined by |
1921 //#define KSTD_NF_LAZY 1
1922  // do only a reduction of the leading term
1923 //#define KSTD_NF_ECART 2
1924  // only local: recude even with bad ecart
1925  poly p;
1926  int i;
1927  int j;
1928  int o;
1929  LObject h;
1930  BITSET save1;
1931  SI_SAVE_OPT1(save1);
1932 
1933  //if ((idIs0(F))&&(Q==NULL))
1934  // return pCopy(q); /*F=0*/
1935  //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
1936  /*- creating temp data structures------------------- -*/
1937  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1938  strat->kNoether = pCopy((currRing->ppNoether));
1942  && (! TEST_V_DEG_STOP)
1943  && (0<Kstd1_deg)
1944  && ((!strat->kHEdgeFound)
1946  {
1947  pDelete(&strat->kNoether);
1948  strat->kNoether=pOne();
1949  pSetExp(strat->kNoether,1, Kstd1_deg+1);
1950  pSetm(strat->kNoether);
1951  strat->kHEdgeFound=TRUE;
1952  }
1953  initBuchMoraCrit(strat);
1954  initBuchMoraPos(strat);
1955  initMora(F,strat);
1956  strat->enterS = enterSMoraNF;
1957  /*- set T -*/
1958  strat->tl = -1;
1959  strat->tmax = setmaxT;
1960  strat->T = initT();
1961  strat->R = initR();
1962  strat->sevT = initsevT();
1963  /*- set S -*/
1964  strat->sl = -1;
1965  /*- init local data struct.-------------------------- -*/
1966  /*Shdl=*/initS(F,Q,strat);
1967  if ((strat->ak!=0)
1968  && (strat->kHEdgeFound))
1969  {
1970  if (strat->ak!=1)
1971  {
1972  pSetComp(strat->kNoether,1);
1973  pSetmComp(strat->kNoether);
1974  poly p=pHead(strat->kNoether);
1975  pSetComp(p,strat->ak);
1976  pSetmComp(p);
1977  p=pAdd(strat->kNoether,p);
1978  strat->kNoether=pNext(p);
1979  p_LmFree(p,currRing);
1980  }
1981  }
1982  if ((lazyReduce & KSTD_NF_LAZY)==0)
1983  {
1984  for (i=strat->sl; i>=0; i--)
1985  pNorm(strat->S[i]);
1986  }
1987  /*- puts the elements of S also to T -*/
1988  for (i=0; i<=strat->sl; i++)
1989  {
1990  h.p = strat->S[i];
1991  h.ecart = strat->ecartS[i];
1992  if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
1993  else assume(strat->sevS[i] == pGetShortExpVector(h.p));
1994  h.length = pLength(h.p);
1995  h.sev = strat->sevS[i];
1996  h.SetpFDeg();
1997  enterT(h,strat);
1998  }
1999 #ifdef KDEBUG
2000 // kDebugPrint(strat);
2001 #endif
2002  /*- compute------------------------------------------- -*/
2003  p = pCopy(q);
2004  deleteHC(&p,&o,&j,strat);
2005  kTest(strat);
2006  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2007  if (BVERBOSE(23)) kDebugPrint(strat);
2008  if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2009  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2010  {
2011  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2012  p = redtail(p,strat->sl,strat);
2013  }
2014  /*- release temp data------------------------------- -*/
2015  cleanT(strat);
2016  assume(strat->L==NULL); /*strat->L unsed */
2017  assume(strat->B==NULL); /*strat->B unused */
2018  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2019  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2020  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2021  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2022  omFree(strat->sevT);
2023  omFree(strat->S_2_R);
2024  omFree(strat->R);
2025 
2026  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2027  {
2028  i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
2029  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2030  strat->fromQ=NULL;
2031  }
2032  pDelete(&strat->kHEdge);
2033  pDelete(&strat->kNoether);
2034 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2035 // {
2036 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2037 // if (ecartWeights)
2038 // {
2039 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2040 // ecartWeights=NULL;
2041 // }
2042 // }
2043  idDelete(&strat->Shdl);
2044  SI_RESTORE_OPT1(save1);
2045  if (TEST_OPT_PROT) PrintLn();
2046  return p;
2047 }
2048 
2049 ideal kNF1 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce)
2050 {
2051  assume(!idIs0(q));
2052  assume(!(idIs0(F)&&(Q==NULL)));
2053 
2054 // lazy_reduce flags: can be combined by |
2055 //#define KSTD_NF_LAZY 1
2056  // do only a reduction of the leading term
2057 //#define KSTD_NF_ECART 2
2058  // only local: recude even with bad ecart
2059  poly p;
2060  int i;
2061  int j;
2062  int o;
2063  LObject h;
2064  ideal res;
2065  BITSET save1;
2066  SI_SAVE_OPT1(save1);
2067 
2068  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2069  //if ((idIs0(F))&&(Q==NULL))
2070  // return idCopy(q); /*F=0*/
2071  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2072  /*- creating temp data structures------------------- -*/
2073  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2074  strat->kNoether=pCopy((currRing->ppNoether));
2077  && (0<Kstd1_deg)
2078  && ((!strat->kHEdgeFound)
2080  {
2081  pDelete(&strat->kNoether);
2082  strat->kNoether=pOne();
2083  pSetExp(strat->kNoether,1, Kstd1_deg+1);
2084  pSetm(strat->kNoether);
2085  strat->kHEdgeFound=TRUE;
2086  }
2087  initBuchMoraCrit(strat);
2088  initBuchMoraPos(strat);
2089  initMora(F,strat);
2090  strat->enterS = enterSMoraNF;
2091  /*- set T -*/
2092  strat->tl = -1;
2093  strat->tmax = setmaxT;
2094  strat->T = initT();
2095  strat->R = initR();
2096  strat->sevT = initsevT();
2097  /*- set S -*/
2098  strat->sl = -1;
2099  /*- init local data struct.-------------------------- -*/
2100  /*Shdl=*/initS(F,Q,strat);
2101  if ((strat->ak!=0)
2102  && (strat->kHEdgeFound))
2103  {
2104  if (strat->ak!=1)
2105  {
2106  pSetComp(strat->kNoether,1);
2107  pSetmComp(strat->kNoether);
2108  poly p=pHead(strat->kNoether);
2109  pSetComp(p,strat->ak);
2110  pSetmComp(p);
2111  p=pAdd(strat->kNoether,p);
2112  strat->kNoether=pNext(p);
2113  p_LmFree(p,currRing);
2114  }
2115  }
2116  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
2117  {
2118  for (i=strat->sl; i>=0; i--)
2119  pNorm(strat->S[i]);
2120  }
2121  /*- compute------------------------------------------- -*/
2122  res=idInit(IDELEMS(q),strat->ak);
2123  for (i=0; i<IDELEMS(q); i++)
2124  {
2125  if (q->m[i]!=NULL)
2126  {
2127  p = pCopy(q->m[i]);
2128  deleteHC(&p,&o,&j,strat);
2129  if (p!=NULL)
2130  {
2131  /*- puts the elements of S also to T -*/
2132  for (j=0; j<=strat->sl; j++)
2133  {
2134  h.p = strat->S[j];
2135  h.ecart = strat->ecartS[j];
2136  h.pLength = h.length = pLength(h.p);
2137  if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2138  else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2139  h.sev = strat->sevS[j];
2140  h.SetpFDeg();
2141  #ifdef HAVE_RINGS
2143  enterT_strong(h,strat);
2144  else
2145  #endif
2146  enterT(h,strat);
2147  }
2148  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2149  p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2150  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2151  {
2152  if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2153  p = redtail(p,strat->sl,strat);
2154  }
2155  cleanT(strat);
2156  }
2157  res->m[i]=p;
2158  }
2159  //else
2160  // res->m[i]=NULL;
2161  }
2162  /*- release temp data------------------------------- -*/
2163  assume(strat->L==NULL); /*strat->L unsed */
2164  assume(strat->B==NULL); /*strat->B unused */
2165  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2166  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2167  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2168  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2169  omFree(strat->sevT);
2170  omFree(strat->S_2_R);
2171  omFree(strat->R);
2172  if ((Q!=NULL)&&(strat->fromQ!=NULL))
2173  {
2174  i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
2175  omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2176  strat->fromQ=NULL;
2177  }
2178  pDelete(&strat->kHEdge);
2179  pDelete(&strat->kNoether);
2180 // if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2181 // {
2182 // pFDeg=strat->pOrigFDeg;
2183 // pLDeg=strat->pOrigLDeg;
2184 // if (ecartWeights)
2185 // {
2186 // omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2187 // ecartWeights=NULL;
2188 // }
2189 // }
2190  idDelete(&strat->Shdl);
2191  SI_RESTORE_OPT1(save1);
2192  if (TEST_OPT_PROT) PrintLn();
2193  return res;
2194 }
2195 
2197 
2198 long kModDeg(poly p, ring r)
2199 {
2200  long o=p_WDegree(p, r);
2201  long i=p_GetComp(p, r);
2202  if (i==0) return o;
2203  //assume((i>0) && (i<=kModW->length()));
2204  if (i<=kModW->length())
2205  return o+(*kModW)[i-1];
2206  return o;
2207 }
2208 long kHomModDeg(poly p, ring r)
2209 {
2210  int i;
2211  long j=0;
2212 
2213  for (i=r->N;i>0;i--)
2214  j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2215  if (kModW == NULL) return j;
2216  i = p_GetComp(p,r);
2217  if (i==0) return j;
2218  return j+(*kModW)[i-1];
2219 }
2220 
2221 ideal kStd(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2222  int newIdeal, intvec *vw, s_poly_proc_t sp)
2223 {
2224  if(idIs0(F))
2225  return idInit(1,F->rank);
2226 
2227  ideal r;
2228  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2229  BOOLEAN delete_w=(w==NULL);
2231 
2232  strat->s_poly=sp;
2233  if(!TEST_OPT_RETURN_SB)
2234  strat->syzComp = syzComp;
2235  if (TEST_OPT_SB_1
2236  #ifdef HAVE_RINGS
2237  &&(!rField_is_Ring(currRing))
2238  #endif
2239  )
2240  strat->newIdeal = newIdeal;
2242  strat->LazyPass=20;
2243  else
2244  strat->LazyPass=2;
2245  strat->LazyDegree = 1;
2246  strat->ak = id_RankFreeModule(F,currRing);
2247  strat->kModW=kModW=NULL;
2248  strat->kHomW=kHomW=NULL;
2249  if (vw != NULL)
2250  {
2251  currRing->pLexOrder=FALSE;
2252  strat->kHomW=kHomW=vw;
2253  strat->pOrigFDeg = currRing->pFDeg;
2254  strat->pOrigLDeg = currRing->pLDeg;
2256  toReset = TRUE;
2257  }
2258  if (h==testHomog)
2259  {
2260  if (strat->ak == 0)
2261  {
2262  h = (tHomog)idHomIdeal(F,Q);
2263  w=NULL;
2264  }
2265  else if (!TEST_OPT_DEGBOUND)
2266  {
2267  h = (tHomog)idHomModule(F,Q,w);
2268  }
2269  }
2270  currRing->pLexOrder=b;
2271  if (h==isHomog)
2272  {
2273  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2274  {
2275  strat->kModW = kModW = *w;
2276  if (vw == NULL)
2277  {
2278  strat->pOrigFDeg = currRing->pFDeg;
2279  strat->pOrigLDeg = currRing->pLDeg;
2281  toReset = TRUE;
2282  }
2283  }
2284  currRing->pLexOrder = TRUE;
2285  if (hilb==NULL) strat->LazyPass*=2;
2286  }
2287  strat->homog=h;
2288 #ifdef KDEBUG
2289  idTest(F);
2290  if (Q!=NULL) idTest(Q);
2291 
2292 #if MYTEST
2293  if (TEST_OPT_DEBUG)
2294  {
2295  PrintS("// kSTD: currRing: ");
2296  rWrite(currRing);
2297  }
2298 #endif
2299 
2300 #endif
2301 #ifdef HAVE_PLURAL
2302  if (rIsPluralRing(currRing))
2303  {
2304  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2305  strat->no_prod_crit = ! bIsSCA;
2306  if (w!=NULL)
2307  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2308  else
2309  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2310  }
2311  else
2312 #endif
2313 #ifdef HAVE_RINGS
2314  if (rField_is_Ring(currRing))
2315  {
2316  if(nCoeff_is_Ring_Z(currRing->cf))
2317  {
2318  #if 0
2319  if(nCoeff_is_Ring_Z(currRing->cf))
2320  {
2321  ideal FCopy = idCopy(F);
2322  poly pFmon = preIntegerCheck(FCopy, Q);
2323  if(pFmon != NULL)
2324  {
2325  idInsertPoly(FCopy, pFmon);
2326  #if ADIDEBUG
2327  printf("\nPreintegerCheck found this constant:\n");pWrite(pFmon);
2328  #endif
2329  }
2330  strat->kModW=kModW=NULL;
2331  if (h==testHomog)
2332  {
2333  if (strat->ak == 0)
2334  {
2335  h = (tHomog)idHomIdeal(FCopy,Q);
2336  w=NULL;
2337  }
2338  else if (!TEST_OPT_DEGBOUND)
2339  {
2340  h = (tHomog)idHomModule(FCopy,Q,w);
2341  }
2342  }
2343  currRing->pLexOrder=b;
2344  if (h==isHomog)
2345  {
2346  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2347  {
2348  strat->kModW = kModW = *w;
2349  if (vw == NULL)
2350  {
2351  strat->pOrigFDeg = currRing->pFDeg;
2352  strat->pOrigLDeg = currRing->pLDeg;
2354  toReset = TRUE;
2355  }
2356  }
2357  currRing->pLexOrder = TRUE;
2358  if (hilb==NULL) strat->LazyPass*=2;
2359  }
2360  strat->homog=h;
2361  omTestMemory(1);
2363  r=mora(FCopy,Q,NULL,hilb,strat);
2364  else
2365  r=bba(FCopy,Q,NULL,hilb,strat);
2366  }
2367  else
2368  #endif
2369  {
2371  r=mora(F,Q,NULL,hilb,strat);
2372  else
2373  r=bba(F,Q,NULL,hilb,strat);
2374  }
2375  }
2376  else
2377  {
2379  r=mora(F,Q,NULL,hilb,strat);
2380  else
2381  r=bba(F,Q,NULL,hilb,strat);
2382  }
2383  }
2384  else
2385 #endif
2386  {
2388  {
2389  if (w!=NULL)
2390  r=mora(F,Q,*w,hilb,strat);
2391  else
2392  r=mora(F,Q,NULL,hilb,strat);
2393  }
2394  else
2395  {
2396  if (w!=NULL)
2397  r=bba(F,Q,*w,hilb,strat);
2398  else
2399  r=bba(F,Q,NULL,hilb,strat);
2400  }
2401  }
2402 #ifdef KDEBUG
2403  idTest(r);
2404 #endif
2405  if (toReset)
2406  {
2407  kModW = NULL;
2408  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2409  }
2410  currRing->pLexOrder = b;
2411 //Print("%d reductions canceled \n",strat->cel);
2412  HCord=strat->HCord;
2413  delete(strat);
2414  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2415  return r;
2416 }
2417 
2418 ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int sbaOrder, int arri, intvec *hilb,int syzComp,
2419  int newIdeal, intvec *vw)
2420 {
2421  if(idIs0(F))
2422  return idInit(1,F->rank);
2423 
2424  ideal r;
2425  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2426  BOOLEAN delete_w=(w==NULL);
2428  strat->sbaOrder = sbaOrder;
2429  if (arri!=0)
2430  {
2431  strat->rewCrit1 = arriRewDummy;
2432  strat->rewCrit2 = arriRewCriterion;
2433  strat->rewCrit3 = arriRewCriterionPre;
2434  }
2435  else
2436  {
2437  strat->rewCrit1 = faugereRewCriterion;
2438  strat->rewCrit2 = faugereRewCriterion;
2439  strat->rewCrit3 = faugereRewCriterion;
2440  }
2441 
2442  if(!TEST_OPT_RETURN_SB)
2443  strat->syzComp = syzComp;
2444  if (TEST_OPT_SB_1)
2445  #ifdef HAVE_RINGS
2446  if(!rField_is_Ring(currRing))
2447  #endif
2448  strat->newIdeal = newIdeal;
2450  strat->LazyPass=20;
2451  else
2452  strat->LazyPass=2;
2453  strat->LazyDegree = 1;
2455  strat->chainCrit=chainCritNormal;
2457  strat->ak = id_RankFreeModule(F,currRing);
2458  strat->kModW=kModW=NULL;
2459  strat->kHomW=kHomW=NULL;
2460  if (vw != NULL)
2461  {
2462  currRing->pLexOrder=FALSE;
2463  strat->kHomW=kHomW=vw;
2464  strat->pOrigFDeg = currRing->pFDeg;
2465  strat->pOrigLDeg = currRing->pLDeg;
2467  toReset = TRUE;
2468  }
2469  if (h==testHomog)
2470  {
2471  if (strat->ak == 0)
2472  {
2473  h = (tHomog)idHomIdeal(F,Q);
2474  w=NULL;
2475  }
2476  else if (!TEST_OPT_DEGBOUND)
2477  {
2478  h = (tHomog)idHomModule(F,Q,w);
2479  }
2480  }
2481  currRing->pLexOrder=b;
2482  if (h==isHomog)
2483  {
2484  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2485  {
2486  strat->kModW = kModW = *w;
2487  if (vw == NULL)
2488  {
2489  strat->pOrigFDeg = currRing->pFDeg;
2490  strat->pOrigLDeg = currRing->pLDeg;
2492  toReset = TRUE;
2493  }
2494  }
2495  currRing->pLexOrder = TRUE;
2496  if (hilb==NULL) strat->LazyPass*=2;
2497  }
2498  strat->homog=h;
2499 #ifdef KDEBUG
2500  idTest(F);
2501  idTest(Q);
2502 
2503 #if MYTEST
2504  if (TEST_OPT_DEBUG)
2505  {
2506  PrintS("// kSTD: currRing: ");
2507  rWrite(currRing);
2508  }
2509 #endif
2510 
2511 #endif
2512 #ifdef HAVE_PLURAL
2513  if (rIsPluralRing(currRing))
2514  {
2515  const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2516  strat->no_prod_crit = ! bIsSCA;
2517  if (w!=NULL)
2518  r = nc_GB(F, Q, *w, hilb, strat, currRing);
2519  else
2520  r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2521  }
2522  else
2523 #endif
2524 #ifdef HAVE_RINGS
2525  if (rField_is_Ring(currRing))
2526  r=bba(F,Q,NULL,hilb,strat);
2527  else
2528 #endif
2529  {
2531  {
2532  if (w!=NULL)
2533  r=mora(F,Q,*w,hilb,strat);
2534  else
2535  r=mora(F,Q,NULL,hilb,strat);
2536  }
2537  else
2538  {
2539  if (w!=NULL)
2540  r=sba(F,Q,*w,hilb,strat);
2541  else
2542  r=sba(F,Q,NULL,hilb,strat);
2543  }
2544  }
2545 #ifdef KDEBUG
2546  idTest(r);
2547 #endif
2548  if (toReset)
2549  {
2550  kModW = NULL;
2551  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2552  }
2553  currRing->pLexOrder = b;
2554 //Print("%d reductions canceled \n",strat->cel);
2555  HCord=strat->HCord;
2556  delete(strat);
2557  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2558  return r;
2559 }
2560 
2561 #ifdef HAVE_SHIFTBBA
2562 ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2563  int newIdeal, intvec *vw, int uptodeg, int lV)
2564 {
2565  ideal r;
2566  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2567  BOOLEAN delete_w=(w==NULL);
2569 
2570  if(!TEST_OPT_RETURN_SB)
2571  strat->syzComp = syzComp;
2572  if (TEST_OPT_SB_1)
2573  #ifdef HAVE_RINGS
2574  if(!rField_is_Ring(currRing))
2575  #endif
2576  strat->newIdeal = newIdeal;
2578  strat->LazyPass=20;
2579  else
2580  strat->LazyPass=2;
2581  strat->LazyDegree = 1;
2582  strat->ak = id_RankFreeModule(F,currRing);
2583  strat->kModW=kModW=NULL;
2584  strat->kHomW=kHomW=NULL;
2585  if (vw != NULL)
2586  {
2587  currRing->pLexOrder=FALSE;
2588  strat->kHomW=kHomW=vw;
2589  strat->pOrigFDeg = currRing->pFDeg;
2590  strat->pOrigLDeg = currRing->pLDeg;
2592  toReset = TRUE;
2593  }
2594  if (h==testHomog)
2595  {
2596  if (strat->ak == 0)
2597  {
2598  h = (tHomog)idHomIdeal(F,Q);
2599  w=NULL;
2600  }
2601  else if (!TEST_OPT_DEGBOUND)
2602  {
2603  h = (tHomog)idHomModule(F,Q,w);
2604  }
2605  }
2606  currRing->pLexOrder=b;
2607  if (h==isHomog)
2608  {
2609  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2610  {
2611  strat->kModW = kModW = *w;
2612  if (vw == NULL)
2613  {
2614  strat->pOrigFDeg = currRing->pFDeg;
2615  strat->pOrigLDeg = currRing->pLDeg;
2617  toReset = TRUE;
2618  }
2619  }
2620  currRing->pLexOrder = TRUE;
2621  if (hilb==NULL) strat->LazyPass*=2;
2622  }
2623  strat->homog=h;
2624 #ifdef KDEBUG
2625  idTest(F);
2626 #endif
2628  {
2629  /* error: no local ord yet with shifts */
2630  Print("No local ordering possible for shifts");
2631  return(NULL);
2632  }
2633  else
2634  {
2635  /* global ordering */
2636  if (w!=NULL)
2637  r=bbaShift(F,Q,*w,hilb,strat,uptodeg,lV);
2638  else
2639  r=bbaShift(F,Q,NULL,hilb,strat,uptodeg,lV);
2640  }
2641 #ifdef KDEBUG
2642  idTest(r);
2643 #endif
2644  if (toReset)
2645  {
2646  kModW = NULL;
2647  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2648  }
2649  currRing->pLexOrder = b;
2650 //Print("%d reductions canceled \n",strat->cel);
2651  HCord=strat->HCord;
2652  delete(strat);
2653  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2654  return r;
2655 }
2656 #endif
2657 
2658 //##############################################################
2659 //##############################################################
2660 //##############################################################
2661 //##############################################################
2662 //##############################################################
2663 
2664 ideal kMin_std(ideal F, ideal Q, tHomog h,intvec ** w, ideal &M, intvec *hilb,
2665  int syzComp, int reduced)
2666 {
2667  if(idIs0(F))
2668  {
2669  M=idInit(1,F->rank);
2670  return idInit(1,F->rank);
2671  }
2672  #ifdef HAVE_RINGS
2674  {
2675  ideal sb;
2676  sb = kStd(F, Q, h, w, hilb);
2677  idSkipZeroes(sb);
2678  if(IDELEMS(sb) <= IDELEMS(F))
2679  {
2680  M = idCopy(sb);
2681  idSkipZeroes(M);
2682  return(sb);
2683  }
2684  else
2685  {
2686  M = idCopy(F);
2687  idSkipZeroes(M);
2688  return(sb);
2689  }
2690  }
2691  #endif
2692  ideal r=NULL;
2693  int Kstd1_OldDeg = Kstd1_deg,i;
2694  intvec* temp_w=NULL;
2695  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2696  BOOLEAN delete_w=(w==NULL);
2697  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
2699 
2700  if(!TEST_OPT_RETURN_SB)
2701  strat->syzComp = syzComp;
2703  strat->LazyPass=20;
2704  else
2705  strat->LazyPass=2;
2706  strat->LazyDegree = 1;
2707  strat->minim=(reduced % 2)+1;
2708  strat->ak = id_RankFreeModule(F,currRing);
2709  if (delete_w)
2710  {
2711  temp_w=new intvec((strat->ak)+1);
2712  w = &temp_w;
2713  }
2714  if (h==testHomog)
2715  {
2716  if (strat->ak == 0)
2717  {
2718  h = (tHomog)idHomIdeal(F,Q);
2719  w=NULL;
2720  }
2721  else
2722  {
2723  h = (tHomog)idHomModule(F,Q,w);
2724  }
2725  }
2726  if (h==isHomog)
2727  {
2728  if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2729  {
2730  kModW = *w;
2731  strat->kModW = *w;
2732  assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
2733  strat->pOrigFDeg = currRing->pFDeg;
2734  strat->pOrigLDeg = currRing->pLDeg;
2736 
2737  toReset = TRUE;
2738  if (reduced>1)
2739  {
2740  Kstd1_OldDeg=Kstd1_deg;
2741  Kstd1_deg = -1;
2742  for (i=IDELEMS(F)-1;i>=0;i--)
2743  {
2744  if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
2745  Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
2746  }
2747  }
2748  }
2749  currRing->pLexOrder = TRUE;
2750  strat->LazyPass*=2;
2751  }
2752  strat->homog=h;
2754  {
2755  if (w!=NULL)
2756  r=mora(F,Q,*w,hilb,strat);
2757  else
2758  r=mora(F,Q,NULL,hilb,strat);
2759  }
2760  else
2761  {
2762  if (w!=NULL)
2763  r=bba(F,Q,*w,hilb,strat);
2764  else
2765  r=bba(F,Q,NULL,hilb,strat);
2766  }
2767 #ifdef KDEBUG
2768  {
2769  int i;
2770  for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
2771  }
2772 #endif
2773  idSkipZeroes(r);
2774  if (toReset)
2775  {
2776  pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2777  kModW = NULL;
2778  }
2779  currRing->pLexOrder = b;
2780  HCord=strat->HCord;
2781  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
2782  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
2783  {
2784  M=idInit(1,F->rank);
2785  M->m[0]=pOne();
2786  //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
2787  if (strat->M!=NULL) idDelete(&strat->M);
2788  }
2789  else if (strat->M==NULL)
2790  {
2791  M=idInit(1,F->rank);
2792  Warn("no minimal generating set computed");
2793  }
2794  else
2795  {
2796  idSkipZeroes(strat->M);
2797  M=strat->M;
2798  }
2799  delete(strat);
2800  if (reduced>2)
2801  {
2802  Kstd1_deg=Kstd1_OldDeg;
2803  if (!oldDegBound)
2805  }
2806  else
2807  {
2808  if (IDELEMS(M)>IDELEMS(r)) {
2809  idDelete(&M);
2810  M=idCopy(r); }
2811  }
2812  return r;
2813 }
2814 
2815 poly kNF(ideal F, ideal Q, poly p,int syzComp, int lazyReduce)
2816 {
2817  if (p==NULL)
2818  return NULL;
2819 
2820  poly pp = p;
2821 
2822 #ifdef HAVE_PLURAL
2823  if(rIsSCA(currRing))
2824  {
2825  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2826  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2827  pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
2828 
2829  if(Q == currRing->qideal)
2830  Q = SCAQuotient(currRing);
2831  }
2832 #endif
2833 
2834  if ((idIs0(F))&&(Q==NULL))
2835  {
2836 #ifdef HAVE_PLURAL
2837  if(p != pp)
2838  return pp;
2839 #endif
2840  return pCopy(p); /*F+Q=0*/
2841  }
2842 
2844  strat->syzComp = syzComp;
2845  strat->ak = si_max(id_RankFreeModule(F,currRing),pMaxComp(p));
2846  poly res;
2847 
2849  res=kNF1(F,Q,pp,strat,lazyReduce);
2850  else
2851  res=kNF2(F,Q,pp,strat,lazyReduce);
2852  delete(strat);
2853 
2854 #ifdef HAVE_PLURAL
2855  if(pp != p)
2856  p_Delete(&pp, currRing);
2857 #endif
2858  return res;
2859 }
2860 
2861 ideal kNF(ideal F, ideal Q, ideal p,int syzComp,int lazyReduce)
2862 {
2863  ideal res;
2864  if (TEST_OPT_PROT)
2865  {
2866  Print("(S:%d)",IDELEMS(p));mflush();
2867  }
2868  if (idIs0(p))
2869  return idInit(IDELEMS(p),si_max(p->rank,F->rank));
2870 
2871  ideal pp = p;
2872 #ifdef HAVE_PLURAL
2873  if(rIsSCA(currRing))
2874  {
2875  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2876  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2877  pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
2878 
2879  if(Q == currRing->qideal)
2880  Q = SCAQuotient(currRing);
2881  }
2882 #endif
2883 
2884  if ((idIs0(F))&&(Q==NULL))
2885  {
2886 #ifdef HAVE_PLURAL
2887  if(p != pp)
2888  return pp;
2889 #endif
2890  return idCopy(p); /*F+Q=0*/
2891  }
2892 
2894  strat->syzComp = syzComp;
2896  if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
2897  {
2898  strat->ak = si_max(strat->ak,(int)F->rank);
2899  }
2900 
2902  res=kNF1(F,Q,pp,strat,lazyReduce);
2903  else
2904  res=kNF2(F,Q,pp,strat,lazyReduce);
2905  delete(strat);
2906 
2907 #ifdef HAVE_PLURAL
2908  if(pp != p)
2909  id_Delete(&pp, currRing);
2910 #endif
2911 
2912  return res;
2913 }
2914 
2915 poly k_NF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing)
2916 {
2917  const ring save = currRing;
2918  if( currRing != _currRing ) rChangeCurrRing(_currRing);
2919  poly ret = kNF(F, Q, p, syzComp, lazyReduce);
2920  if( currRing != save ) rChangeCurrRing(save);
2921  return ret;
2922 }
2923 
2924 /*2
2925 *interreduces F
2926 */
2927 // old version
2928 ideal kInterRedOld (ideal F, ideal Q)
2929 {
2930  int j;
2931  kStrategy strat = new skStrategy;
2932 
2933  ideal tempF = F;
2934  ideal tempQ = Q;
2935 
2936 #ifdef HAVE_PLURAL
2937  if(rIsSCA(currRing))
2938  {
2939  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2940  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
2941  tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
2942 
2943  // this should be done on the upper level!!! :
2944  // tempQ = SCAQuotient(currRing);
2945 
2946  if(Q == currRing->qideal)
2947  tempQ = SCAQuotient(currRing);
2948  }
2949 #endif
2950 
2951 // if (TEST_OPT_PROT)
2952 // {
2953 // writeTime("start InterRed:");
2954 // mflush();
2955 // }
2956  //strat->syzComp = 0;
2957  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2958  strat->kNoether=pCopy((currRing->ppNoether));
2959  strat->ak = id_RankFreeModule(tempF,currRing);
2960  initBuchMoraCrit(strat);
2961  strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
2962  for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
2963  strat->enterS = enterSBba;
2964  strat->posInT = posInT17;
2965  strat->initEcart = initEcartNormal;
2966  strat->sl = -1;
2967  strat->tl = -1;
2968  strat->tmax = setmaxT;
2969  strat->T = initT();
2970  strat->R = initR();
2971  strat->sevT = initsevT();
2973  initS(tempF, tempQ, strat);
2974  if (TEST_OPT_REDSB)
2975  strat->noTailReduction=FALSE;
2976  updateS(TRUE,strat);
2978  completeReduce(strat);
2979  //else if (TEST_OPT_PROT) PrintLn();
2980  pDelete(&strat->kHEdge);
2981  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2982  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2983  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2984  omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2985  omfree(strat->sevT);
2986  omfree(strat->S_2_R);
2987  omfree(strat->R);
2988 
2989  if (strat->fromQ)
2990  {
2991  for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
2992  {
2993  if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
2994  }
2995  omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
2996  }
2997 // if (TEST_OPT_PROT)
2998 // {
2999 // writeTime("end Interred:");
3000 // mflush();
3001 // }
3002  ideal shdl=strat->Shdl;
3003  idSkipZeroes(shdl);
3004  if (strat->fromQ)
3005  {
3006  strat->fromQ=NULL;
3007  ideal res=kInterRed(shdl,NULL);
3008  idDelete(&shdl);
3009  shdl=res;
3010  }
3011  delete(strat);
3012 #ifdef HAVE_PLURAL
3013  if( tempF != F )
3014  id_Delete( &tempF, currRing);
3015 #endif
3016  return shdl;
3017 }
3018 // new version
3019 ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
3020 {
3021  need_retry=0;
3022  int red_result = 1;
3023  int olddeg,reduc;
3024  BOOLEAN withT = FALSE;
3025  // BOOLEAN toReset=FALSE;
3027  tHomog h;
3028  intvec * w=NULL;
3029 
3031  strat->LazyPass=20;
3032  else
3033  strat->LazyPass=2;
3034  strat->LazyDegree = 1;
3035  strat->ak = id_RankFreeModule(F,currRing);
3036  strat->syzComp = strat->ak;
3037  strat->kModW=kModW=NULL;
3038  strat->kHomW=kHomW=NULL;
3039  if (strat->ak == 0)
3040  {
3041  h = (tHomog)idHomIdeal(F,Q);
3042  w=NULL;
3043  }
3044  else if (!TEST_OPT_DEGBOUND)
3045  {
3046  h = (tHomog)idHomModule(F,Q,&w);
3047  }
3048  if (h==isHomog)
3049  {
3050  if (strat->ak > 0 && (w!=NULL) && (w!=NULL))
3051  {
3052  strat->kModW = kModW = w;
3053  strat->pOrigFDeg = currRing->pFDeg;
3054  strat->pOrigLDeg = currRing->pLDeg;
3056  // toReset = TRUE;
3057  }
3058  strat->LazyPass*=2;
3059  }
3060  strat->homog=h;
3061 #ifdef KDEBUG
3062  idTest(F);
3063 #endif
3064 
3065  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3066  initBuchMoraPos(strat);
3067  initBba(F,strat);
3068  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3069  strat->posInL=posInL0; /* ord according pComp */
3070 
3071  /*Shdl=*/initBuchMora(F, Q, strat);
3072  reduc = olddeg = 0;
3073 
3074 #ifndef NO_BUCKETS
3075  if (!TEST_OPT_NOT_BUCKETS)
3076  strat->use_buckets = 1;
3077 #endif
3078 
3079  // redtailBBa against T for inhomogenous input
3080  if (!TEST_OPT_OLDSTD)
3081  withT = ! strat->homog;
3082 
3083  // strat->posInT = posInT_pLength;
3084  kTest_TS(strat);
3085 
3086 #ifdef HAVE_TAIL_RING
3087  kStratInitChangeTailRing(strat);
3088 #endif
3089 
3090  /* compute------------------------------------------------------- */
3091  while (strat->Ll >= 0)
3092  {
3093  #ifdef KDEBUG
3094  if (TEST_OPT_DEBUG) messageSets(strat);
3095  #endif
3096  if (strat->Ll== 0) strat->interpt=TRUE;
3097  /* picks the last element from the lazyset L */
3098  strat->P = strat->L[strat->Ll];
3099  strat->Ll--;
3100 
3101  if (strat->P.p1 == NULL)
3102  {
3103  // for input polys, prepare reduction
3104  strat->P.PrepareRed(strat->use_buckets);
3105  }
3106 
3107  if (strat->P.p == NULL && strat->P.t_p == NULL)
3108  {
3109  red_result = 0;
3110  }
3111  else
3112  {
3113  if (TEST_OPT_PROT)
3114  message(strat->P.pFDeg(),
3115  &olddeg,&reduc,strat, red_result);
3116 
3117  /* reduction of the element chosen from L */
3118  red_result = strat->red(&strat->P,strat);
3119  }
3120 
3121  // reduction to non-zero new poly
3122  if (red_result == 1)
3123  {
3124  /* statistic */
3125  if (TEST_OPT_PROT) PrintS("s");
3126 
3127  // get the polynomial (canonicalize bucket, make sure P.p is set)
3128  strat->P.GetP(strat->lmBin);
3129 
3130  int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3131 
3132  // reduce the tail and normalize poly
3133  // in the ring case we cannot expect LC(f) = 1,
3134  // therefore we call pContent instead of pNorm
3136  {
3137  strat->P.pCleardenom();
3138  if (0)
3139  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3140  {
3141  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3142  strat->P.pCleardenom();
3143  }
3144  }
3145  else
3146  {
3147  strat->P.pNorm();
3148  if (0)
3149  //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3150  strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3151  }
3152 
3153 #ifdef KDEBUG
3154  if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3155 #endif
3156 
3157  // enter into S, L, and T
3158  if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3159  {
3160  enterT(strat->P, strat);
3161  // posInS only depends on the leading term
3162  strat->enterS(strat->P, pos, strat, strat->tl);
3163 
3164  if (pos<strat->sl)
3165  {
3166  need_retry++;
3167  // move all "larger" elements fromS to L
3168  // remove them from T
3169  int ii=pos+1;
3170  for(;ii<=strat->sl;ii++)
3171  {
3172  LObject h;
3173  memset(&h,0,sizeof(h));
3174  h.tailRing=strat->tailRing;
3175  h.p=strat->S[ii]; strat->S[ii]=NULL;
3176  strat->initEcart(&h);
3177  h.sev=strat->sevS[ii];
3178  int jj=strat->tl;
3179  while (jj>=0)
3180  {
3181  if (strat->T[jj].p==h.p)
3182  {
3183  strat->T[jj].p=NULL;
3184  if (jj<strat->tl)
3185  {
3186  memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3187  (strat->tl-jj)*sizeof(strat->T[jj]));
3188  memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3189  (strat->tl-jj)*sizeof(strat->sevT[jj]));
3190  }
3191  strat->tl--;
3192  break;
3193  }
3194  jj--;
3195  }
3196  int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3197  enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3198  #ifdef KDEBUG
3199  if (TEST_OPT_DEBUG)
3200  {
3201  Print("move S[%d] -> L[%d]: ",ii,pos);
3202  p_wrp(h.p,currRing, strat->tailRing);
3203  PrintLn();
3204  }
3205  #endif
3206  }
3207  if (strat->fromQ!=NULL)
3208  {
3209  for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3210  }
3211  strat->sl=pos;
3212  }
3213  }
3214  else
3215  {
3216  // clean P
3217  }
3218  if (strat->P.lcm!=NULL)
3219 #ifdef HAVE_RINGS
3220  pLmDelete(strat->P.lcm);
3221 #else
3222  pLmFree(strat->P.lcm);
3223 #endif
3224  }
3225 
3226 #ifdef KDEBUG
3227  if (TEST_OPT_DEBUG)
3228  {
3229  messageSets(strat);
3230  }
3231  memset(&(strat->P), 0, sizeof(strat->P));
3232 #endif
3233  //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3234  }
3235 #ifdef KDEBUG
3236  //if (TEST_OPT_DEBUG) messageSets(strat);
3237 #endif
3238  /* complete reduction of the standard basis--------- */
3239 
3240  if((need_retry<=0) && (TEST_OPT_REDSB))
3241  {
3242  completeReduce(strat);
3243 #ifdef HAVE_TAIL_RING
3244  if (strat->completeReduce_retry)
3245  {
3246  // completeReduce needed larger exponents, retry
3247  // to reduce with S (instead of T)
3248  // and in currRing (instead of strat->tailRing)
3249  cleanT(strat);strat->tailRing=currRing;
3250  int i;
3251  for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3252  completeReduce(strat);
3253  }
3254 #endif
3255  }
3256  else if (TEST_OPT_PROT) PrintLn();
3257 
3258  /* release temp data-------------------------------- */
3259  exitBuchMora(strat);
3260 // if (TEST_OPT_WEIGHTM)
3261 // {
3262 // pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3263 // if (ecartWeights)
3264 // {
3265 // omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3266 // ecartWeights=NULL;
3267 // }
3268 // }
3269  //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3270  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3271  ideal res=strat->Shdl;
3272  strat->Shdl=NULL;
3273  delete strat;
3274  if (w!=NULL) delete w;
3275  return res;
3276 }
3277 ideal kInterRed (ideal F, ideal Q)
3278 {
3279 #ifdef HAVE_PLURAL
3280  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3281 #endif
3283  #ifdef HAVE_RINGS
3285  #endif
3286  )
3287  return kInterRedOld(F,Q);
3288 
3289  //return kInterRedOld(F,Q);
3290 
3291  BITSET save1;
3292  SI_SAVE_OPT1(save1);
3293  //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3295  //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3296  //si_opt_1&= ~Sy_bit(OPT_REDSB);
3297  //extern char * showOption() ;
3298  //Print("%s\n",showOption());
3299 
3300  int need_retry;
3301  int counter=3;
3302  ideal res, res1;
3303  int elems;
3304  ideal null=NULL;
3305  if ((Q==NULL) || (!TEST_OPT_REDSB))
3306  {
3307  elems=idElem(F);
3308  res=kInterRedBba(F,Q,need_retry);
3309  }
3310  else
3311  {
3312  ideal FF=idSimpleAdd(F,Q);
3313  res=kInterRedBba(FF,NULL,need_retry);
3314  idDelete(&FF);
3315  null=idInit(1,1);
3316  if (need_retry)
3317  res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3318  else
3319  res1=kNF(null,Q,res);
3320  idDelete(&res);
3321  res=res1;
3322  need_retry=1;
3323  }
3324  if (idElem(res)<=1) need_retry=0;
3325  while (need_retry && (counter>0))
3326  {
3327  #ifdef KDEBUG
3328  if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3329  #endif
3330  res1=kInterRedBba(res,Q,need_retry);
3331  int new_elems=idElem(res1);
3332  counter -= (new_elems >= elems);
3333  elems = new_elems;
3334  idDelete(&res);
3335  if (idElem(res1)<=1) need_retry=0;
3336  if ((Q!=NULL) && (TEST_OPT_REDSB))
3337  {
3338  if (need_retry)
3339  res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3340  else
3341  res=kNF(null,Q,res1);
3342  idDelete(&res1);
3343  }
3344  else
3345  res = res1;
3346  if (idElem(res)<=1) need_retry=0;
3347  }
3348  if (null!=NULL) idDelete(&null);
3349  SI_RESTORE_OPT1(save1);
3350  idSkipZeroes(res);
3351  return res;
3352 }
3353 
3354 // returns TRUE if mora should use buckets, false otherwise
3356 {
3357 #ifdef MORA_USE_BUCKETS
3359  return FALSE;
3360  if (strat->red == redFirst)
3361  {
3362 #ifdef NO_LDEG
3363  if (strat->syzComp==0)
3364  return TRUE;
3365 #else
3366  if ((strat->homog || strat->honey) && (strat->syzComp==0))
3367  return TRUE;
3368 #endif
3369  }
3370  else
3371  {
3372  assume(strat->red == redEcart || strat->red == redRiloc);
3373  if (strat->honey && (strat->syzComp==0))
3374  return TRUE;
3375  }
3376 #endif
3377  return FALSE;
3378 }
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:753
#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:1154
void updateT(kStrategy strat)
Definition: kstd1.cc:1223
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:2915
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:5975
BOOLEAN honey
Definition: kutil.h:367
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:7680
#define OPT_PROT
Definition: options.h:70
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2815
#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:322
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4345
#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:8244
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:9052
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:6278
poly kHEdge
Definition: kutil.h:325
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:295
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1512
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:6319
#define TEST_OPT_PROT
Definition: options.h:98
#define pMaxComp(p)
Definition: polys.h:270
loop
Definition: myNF.cc:98
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:5750
#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:2418
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:2451
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8338
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p
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:750
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:58
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:1443
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:540
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:3988
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:2221
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:23
int k
Definition: cfEzgcd.cc:93
#define TEST_OPT_DEBUG
Definition: options.h:103
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1115
#define Q
Definition: sirandom.c:25
#define nEqual(n1, n2)
Definition: numbers.h:20
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:677
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:1466
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:1872
#define BITSET
Definition: structs.h:17
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:274
#define omAlloc(size)
Definition: omAllocDecl.h:210
static bool rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:361
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:518
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1120
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:679
#define pGetComp(p)
Component.
Definition: polys.h:37
static int pLength(poly a)
Definition: p_polys.h:189
int int kStrategy strat if(h==NULL) return NULL
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:1536
BITSET validOpts
Definition: kstd1.cc:70
char completeReduce_retry
Definition: kutil.h:393
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:9464
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:497
pShallowCopyDeleteProc pGetShallowCopyDeleteProc(ring, ring)
#define TEST_OPT_FINDET
Definition: options.h:106
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:7811
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:1116
#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:1053
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:2562
intvec * kHomW
Definition: kstd1.cc:2196
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:956
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:6383
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:2592
BOOLEAN fromT
Definition: kutil.h:369
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3019
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:2196
BOOLEAN homog
Definition: kutil.h:362
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1161
#define TEST_OPT_INTSTRATEGY
Definition: options.h:105
Definition: intvec.h:16
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:465
#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:3481
#define omFree(addr)
Definition: omAllocDecl.h:261
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:8072
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1324
#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
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:1915
void initBba(ideal, kStrategy strat)
Definition: kstd1.cc:1388
LObject * LSet
Definition: kutil.h:62
void initEcartBBA(TObject *h)
Definition: kutil.cc:1147
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 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition: coeffs.h:771
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:2208
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1710
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3277
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:9361
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:4909
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:8092
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:2928
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:302
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:4680
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:7895
ideal idCopy(ideal A)
Definition: ideals.h:76
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3493
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:8994
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:5806
#define OPT_INTSTRATEGY
Definition: options.h:87
#define BVERBOSE(a)
Definition: options.h:33
kStrategy strat
Definition: myNF.cc:319
#define TEST_OPT_RETURN_SB
Definition: options.h:107
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:850
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:5829
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:9225
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:437
#define NULL
Definition: omList.c:10
BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:106
#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:3904
int Lmax
Definition: kutil.h:349
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1247
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:752
BOOLEAN enterOneStrongPoly(int i, poly p, int, int, kStrategy strat, int atR, bool enterTstrong)
Definition: kutil.cc:1399
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:2664
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:4201
#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:7345
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:3065
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:8801
#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:2198
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:2666
#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:8648
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:3355
#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:8924
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1378
void initEcartNormal(TObject *h)
Definition: kutil.cc:1139
#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:9294
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:1172
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:464
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:8419
BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:111
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:294
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
#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:9907
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:1571
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:7577
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
#define idTest(id)
Definition: ideals.h:63
#define Warn
Definition: emacs.cc:80