source: git/kernel/kstd1.cc @ 268ece

spielwiese
Last change on this file since 268ece was 268ece, checked in by Hans Schönemann <hannes@…>, 14 years ago
liftstd(a,b,c): track 174 git-svn-id: file:///usr/local/Singular/svn/trunk@12380 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 61.8 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id$ */
5/*
6* ABSTRACT:
7*/
8
9// TODO: why the following is here instead of mod2.h???
10
11// define if tailrings should be used
12#define HAVE_TAIL_RING
13
14// define if buckets should be used
15#define MORA_USE_BUCKETS
16
17#include "mod2.h"
18
19#ifndef NDEBUG
20# define MYTEST 0
21#else /* ifndef NDEBUG */
22# define MYTEST 0
23#endif /* ifndef NDEBUG */
24
25#if MYTEST
26#ifdef HAVE_TAIL_RING
27#undef HAVE_TAIL_RING
28#endif /* ifdef HAVE_TAIL_RING */
29#endif /* if MYTEST */
30
31#include "structs.h"
32#include "omalloc.h"
33#include "kutil.h"
34#include "kInline.cc"
35#include "polys.h"
36#include "febase.h"
37#include "kstd1.h"
38#include "khstd.h"
39#include "stairc.h"
40#include "weight.h"
41//#include "cntrlc.h"
42#include "intvec.h"
43#include "ideals.h"
44//#include "../Singular/ipid.h"
45#include "timer.h"
46
47//#include "ipprint.h"
48
49#ifdef HAVE_PLURAL
50#include "sca.h"
51#endif
52
53
54/* the list of all options which give a warning by test */
55BITSET kOptions=Sy_bit(OPT_PROT)           /*  0 */
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 */
60                |Sy_bit(OPT_REDTHROUGH)
61                |Sy_bit(OPT_OLDSTD)
62                |Sy_bit(OPT_FASTHC)        /* 10 */
63                |Sy_bit(OPT_KEEPVARS)      /* 21 */
64                |Sy_bit(OPT_INTSTRATEGY)   /* 26 */
65                |Sy_bit(OPT_INFREDTAIL)    /* 28 */
66                |Sy_bit(OPT_NOTREGULARITY) /* 30 */
67                |Sy_bit(OPT_WEIGHTM);      /* 31 */
68
69/* the list of all options which may be used by option and test */
70BITSET validOpts=Sy_bit(0)
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(OPT_REDTHROUGH)
79//                |Sy_bit(8) obachman 11/00 tossed
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
92  |Sy_bit(OPT_OLDSTD)
93                |Sy_bit(21)
94                |Sy_bit(22)
95                /*|Sy_bit(23)*/
96                /*|Sy_bit(24)*/
97                |Sy_bit(OPT_REDTAIL)
98                |Sy_bit(OPT_INTSTRATEGY)
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
108static BOOLEAN kMoraUseBucket(kStrategy strat);
109
110static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
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
129static int doRed (LObject* h, TObject* with,BOOLEAN intoT,kStrategy strat)
130{
131  poly hp;
132  int ret;
133#if KDEBUG > 0
134  kTest_L(h);
135  kTest_T(with);
136#endif
137  // Hmmm ... why do we do this -- polys from T should already be normalized
138  if (!TEST_OPT_INTSTRATEGY)
139    with->pNorm();
140#ifdef KDEBUG
141  if (TEST_OPT_DEBUG)
142  {
143    PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
144  }
145#endif
146  if (intoT)
147  {
148    // need to do it exacly like this: otherwise
149    // we might get errors
150    LObject L= *h;
151    L.Copy();
152    h->GetP();
153    h->SetLength(strat->length_pLength);
154    ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, strat);
155    if (ret)
156    {
157      if (ret < 0) return ret;
158      if (h->tailRing != strat->tailRing)
159        h->ShallowCopyDelete(strat->tailRing,
160                             pGetShallowCopyDeleteProc(h->tailRing,
161                                                       strat->tailRing));
162    }
163    enterT(*h,strat);
164    *h = L;
165  }
166  else
167    ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, strat);
168#ifdef KDEBUG
169  if (TEST_OPT_DEBUG)
170  {
171    PrintS("to ");h->wrp();PrintLn();
172  }
173#endif
174  return ret;
175}
176
177int redEcart (LObject* h,kStrategy strat)
178{
179  poly pi;
180  int i,at,ei,li,ii;
181  int j = 0;
182  int pass = 0;
183  long d,reddeg;
184
185  d = h->GetpFDeg()+ h->ecart;
186  reddeg = strat->LazyDegree+d;
187  h->SetShortExpVector();
188  loop
189  {
190    j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h);
191    if (j < 0)
192    {
193      if (strat->honey) h->SetLength(strat->length_pLength);
194      return 1;
195    }
196
197    ei = strat->T[j].ecart;
198    ii = j;
199
200    if (ei > h->ecart && ii < strat->tl)
201    {
202      li = strat->T[j].length;
203      // the polynomial to reduce with (up to the moment) is;
204      // pi with ecart ei and length li
205      // look for one with smaller ecart
206      i = j;
207      loop
208      {
209        /*- takes the first possible with respect to ecart -*/
210        i++;
211#if 1
212        if (i > strat->tl) break;
213        if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
214                                        strat->T[i].length < li))
215            &&
216            p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing))
217#else
218          j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h, i);
219        if (j < 0) break;
220        i = j;
221        if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
222                                        strat->T[i].length < li))
223#endif
224        {
225          // the polynomial to reduce with is now
226          ii = i;
227          ei = strat->T[i].ecart;
228          if (ei <= h->ecart) break;
229          li = strat->T[i].length;
230        }
231      }
232    }
233
234    // end of search: have to reduce with pi
235    if (ei > h->ecart)
236    {
237      // It is not possible to reduce h with smaller ecart;
238      // if possible h goes to the lazy-set L,i.e
239      // if its position in L would be not the last one
240      strat->fromT = TRUE;
241      if (!K_TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
242      {
243        h->SetLmCurrRing();
244        if (strat->honey && strat->posInLDependsOnLength)
245          h->SetLength(strat->length_pLength);
246        assume(h->FDeg == h->pFDeg());
247        at = strat->posInL(strat->L,strat->Ll,h,strat);
248        if (at <= strat->Ll)
249        {
250          /*- h will not become the next element to reduce -*/
251          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
252#ifdef KDEBUG
253          if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
254#endif
255          h->Clear();
256          strat->fromT = FALSE;
257          return -1;
258        }
259      }
260    }
261
262    // now we finally can reduce
263    doRed(h,&(strat->T[ii]),strat->fromT,strat);
264    strat->fromT=FALSE;
265
266    // are we done ???
267    if (h->IsNull())
268    {
269      if (h->lcm!=NULL) pLmFree(h->lcm);
270      h->Clear();
271      return 0;
272    }
273
274    // NO!
275    h->SetShortExpVector();
276    h->SetpFDeg();
277    if (strat->honey)
278    {
279      if (ei <= h->ecart)
280        h->ecart = d-h->GetpFDeg();
281      else
282        h->ecart = d-h->GetpFDeg()+ei-h->ecart;
283    }
284    else
285      // this has the side effect of setting h->length
286      h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
287#if 0
288    if (strat->syzComp!=0)
289    {
290      if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
291      {
292        assume(h->MinComp() > strat->syzComp);
293        if (strat->honey) h->SetLength();
294#ifdef KDEBUG
295        if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
296#endif
297        return -2;
298      }
299    }
300#endif
301    /*- try to reduce the s-polynomial -*/
302    pass++;
303    d = h->GetpFDeg()+h->ecart;
304    /*
305     *test whether the polynomial should go to the lazyset L
306     *-if the degree jumps
307     *-if the number of pre-defined reductions jumps
308     */
309    if (!K_TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
310        && ((d >= reddeg) || (pass > strat->LazyPass)))
311    {
312      h->SetLmCurrRing();
313      if (strat->honey && strat->posInLDependsOnLength)
314        h->SetLength(strat->length_pLength);
315      assume(h->FDeg == h->pFDeg());
316      at = strat->posInL(strat->L,strat->Ll,h,strat);
317      if (at <= strat->Ll)
318      {
319        int dummy=strat->sl;
320        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
321        {
322          if (strat->honey && !strat->posInLDependsOnLength)
323            h->SetLength(strat->length_pLength);
324          return 1;
325        }
326        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
327#ifdef KDEBUG
328        if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
329#endif
330        h->Clear();
331        return -1;
332      }
333    }
334    else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
335    {
336      Print(".%ld",d);mflush();
337      reddeg = d+1;
338      if (h->pTotalDeg()+h->ecart >= strat->tailRing->bitmask)
339      {
340        strat->overflow=TRUE;
341        //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
342        h->GetP();
343        at = strat->posInL(strat->L,strat->Ll,h,strat);
344        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
345        h->Clear();
346        return -1;
347      }
348    }
349  }
350}
351
352/*2
353*reduces h with elements from T choosing  the first possible
354* element in t with respect to the given pDivisibleBy
355*/
356int redFirst (LObject* h,kStrategy strat)
357{
358  if (h->IsNull()) return 0;
359
360  int at;
361  long reddeg,d;
362  int pass = 0;
363  int j = 0;
364
365  if (! strat->homog)
366  {
367    d = h->GetpFDeg() + h->ecart;
368    reddeg = strat->LazyDegree+d;
369  }
370  h->SetShortExpVector();
371  loop
372  {
373    j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h);
374    if (j < 0)
375    {
376      h->SetDegStuffReturnLDeg(strat->LDegLast);
377      return 1;
378    }
379
380    if (!TEST_OPT_INTSTRATEGY)
381      strat->T[j].pNorm();
382#ifdef KDEBUG
383    if (TEST_OPT_DEBUG)
384    {
385      PrintS("reduce ");
386      h->wrp();
387      PrintS(" with ");
388      strat->T[j].wrp();
389    }
390#endif
391    ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
392#ifdef KDEBUG
393    if (TEST_OPT_DEBUG)
394    {
395      PrintS(" to ");
396      wrp(h->p);
397      PrintLn();
398    }
399#endif
400    if (h->IsNull())
401    {
402      if (h->lcm!=NULL) pLmFree(h->lcm);
403      h->Clear();
404      return 0;
405    }
406    h->SetShortExpVector();
407
408#if 0
409    if ((strat->syzComp!=0) && !strat->honey)
410    {
411      if ((strat->syzComp>0) &&
412          (h->Comp() > strat->syzComp))
413      {
414        assume(h->MinComp() > strat->syzComp);
415#ifdef KDEBUG
416        if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
417#endif
418        if (strat->homog)
419          h->SetDegStuffReturnLDeg(strat->LDegLast);
420        return -2;
421      }
422    }
423#endif
424    if (!strat->homog)
425    {
426      if (!K_TEST_OPT_OLDSTD && strat->honey)
427      {
428        h->SetpFDeg();
429        if (strat->T[j].ecart <= h->ecart)
430          h->ecart = d - h->GetpFDeg();
431        else
432          h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
433
434        d = h->GetpFDeg() + h->ecart;
435      }
436      else
437        d = h->SetDegStuffReturnLDeg(strat->LDegLast);
438      /*- try to reduce the s-polynomial -*/
439      pass++;
440      /*
441       *test whether the polynomial should go to the lazyset L
442       *-if the degree jumps
443       *-if the number of pre-defined reductions jumps
444       */
445      if (!K_TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
446          && ((d >= reddeg) || (pass > strat->LazyPass)))
447      {
448        h->SetLmCurrRing();
449        if (strat->posInLDependsOnLength)
450          h->SetLength(strat->length_pLength);
451        at = strat->posInL(strat->L,strat->Ll,h,strat);
452        if (at <= strat->Ll)
453        {
454          int dummy=strat->sl;
455          if (kFindDivisibleByInS(strat,&dummy, h) < 0)
456            return 1;
457          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
458#ifdef KDEBUG
459          if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
460#endif
461          h->Clear();
462          return -1;
463        }
464      }
465      if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
466      {
467        reddeg = d+1;
468        Print(".%ld",d);mflush();
469        if (h->pTotalDeg()+h->ecart >= strat->tailRing->bitmask)
470        {
471          strat->overflow=TRUE;
472          //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
473          h->GetP();
474          at = strat->posInL(strat->L,strat->Ll,h,strat);
475          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
476          h->Clear();
477          return -1;
478        }
479      }
480    }
481  }
482}
483
484/*2
485* reduces h with elements from T choosing first possible
486* element in T with respect to the given ecart
487* used for computing normal forms outside kStd
488*/
489static poly redMoraNF (poly h,kStrategy strat, int flag)
490{
491  LObject H;
492  H.p = h;
493  int j = 0;
494  int z = 10;
495  int o = H.SetpFDeg();
496  H.ecart = pLDeg(H.p,&H.length,currRing)-o;
497  if ((flag & 2) == 0) cancelunit(&H,TRUE);
498  H.sev = pGetShortExpVector(H.p);
499  unsigned long not_sev = ~ H.sev;
500  loop
501  {
502    if (j > strat->tl)
503    {
504      return H.p;
505    }
506    if (TEST_V_DEG_STOP)
507    {
508      if (kModDeg(H.p)>Kstd1_deg) pDeleteLm(&H.p);
509      if (H.p==NULL) return NULL;
510    }
511    if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing))
512    {
513      //if (strat->interpt) test_int_std(strat->kIdeal);
514      /*- remember the found T-poly -*/
515      poly pi = strat->T[j].p;
516      int ei = strat->T[j].ecart;
517      int li = strat->T[j].length;
518      int ii = j;
519      /*
520      * the polynomial to reduce with (up to the moment) is;
521      * pi with ecart ei and length li
522      */
523      loop
524      {
525        /*- look for a better one with respect to ecart -*/
526        /*- stop, if the ecart is small enough (<=ecart(H)) -*/
527        j++;
528        if (j > strat->tl) break;
529        if (ei <= H.ecart) break;
530        if (((strat->T[j].ecart < ei)
531          || ((strat->T[j].ecart == ei)
532        && (strat->T[j].length < li)))
533        && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev))
534        {
535          /*
536          * the polynomial to reduce with is now;
537          */
538          pi = strat->T[j].p;
539          ei = strat->T[j].ecart;
540          li = strat->T[j].length;
541          ii = j;
542        }
543      }
544      /*
545      * end of search: have to reduce with pi
546      */
547      z++;
548      if (z>10)
549      {
550        pNormalize(H.p);
551        z=0;
552      }
553      if ((ei > H.ecart) && (!strat->kHEdgeFound))
554      {
555        /*
556        * It is not possible to reduce h with smaller ecart;
557        * we have to reduce with bad ecart: H has to enter in T
558        */
559        doRed(&H,&(strat->T[ii]),TRUE,strat);
560        if (H.p == NULL)
561          return NULL;
562      }
563      else
564      {
565        /*
566        * we reduce with good ecart, h need not to be put to T
567        */
568        doRed(&H,&(strat->T[ii]),FALSE,strat);
569        if (H.p == NULL)
570          return NULL;
571      }
572      /*- try to reduce the s-polynomial -*/
573      o = H.SetpFDeg();
574      if ((flag &2 ) == 0) cancelunit(&H,TRUE);
575      H.ecart = pLDeg(H.p,&(H.length),currRing)-o;
576      j = 0;
577      H.sev = pGetShortExpVector(H.p);
578      not_sev = ~ H.sev;
579    }
580    else
581    {
582      j++;
583    }
584  }
585}
586
587/*2
588*reorders  L with respect to posInL
589*/
590void reorderL(kStrategy strat)
591{
592  int i,j,at;
593  LObject p;
594
595  for (i=1; i<=strat->Ll; i++)
596  {
597    at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
598    if (at != i)
599    {
600      p = strat->L[i];
601      for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
602      strat->L[at] = p;
603    }
604  }
605}
606
607/*2
608*reorders  T with respect to length
609*/
610void reorderT(kStrategy strat)
611{
612  int i,j,at;
613  TObject p;
614  unsigned long sev;
615
616
617  for (i=1; i<=strat->tl; i++)
618  {
619    if (strat->T[i-1].length > strat->T[i].length)
620    {
621      p = strat->T[i];
622      sev = strat->sevT[i];
623      at = i-1;
624      loop
625      {
626        at--;
627        if (at < 0) break;
628        if (strat->T[i].length > strat->T[at].length) break;
629      }
630      for (j = i-1; j>at; j--)
631      {
632        strat->T[j+1]=strat->T[j];
633        strat->sevT[j+1]=strat->sevT[j];
634        strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
635      }
636      strat->T[at+1]=p;
637      strat->sevT[at+1] = sev;
638      strat->R[p.i_r] = &(strat->T[at+1]);
639    }
640  }
641}
642
643/*2
644*looks whether exactly pVariables-1 axis are used
645*returns last != 0 in this case
646*last is the (first) unused axis
647*/
648void missingAxis (int* last,kStrategy strat)
649{
650  int   i = 0;
651  int   k = 0;
652
653  *last = 0;
654  if (!currRing->MixedOrder)
655  {
656    loop
657    {
658      i++;
659      if (i > pVariables) break;
660      if (strat->NotUsedAxis[i])
661      {
662        *last = i;
663        k++;
664      }
665      if (k>1)
666      {
667        *last = 0;
668        break;
669      }
670    }
671  }
672}
673
674/*2
675*last is the only non used axis, it looks
676*for a monomial in p being a pure power of this
677*variable and returns TRUE in this case
678*(*length) gives the length between the pure power and the leading term
679*(should be minimal)
680*/
681BOOLEAN hasPurePower (const poly p,int last, int *length,kStrategy strat)
682{
683  poly h;
684  int i;
685
686  if (pNext(p) == strat->tail)
687    return FALSE;
688  pp_Test(p, currRing, strat->tailRing);
689  if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
690  {
691    i = p_IsPurePower(p, currRing);
692    if (i == last)
693    {
694      *length = 0;
695      return TRUE;
696    }
697    *length = 1;
698    h = pNext(p);
699    while (h != NULL)
700    {
701      i = p_IsPurePower(h, strat->tailRing);
702      if (i==last) return TRUE;
703      (*length)++;
704      pIter(h);
705    }
706  }
707  return FALSE;
708}
709
710BOOLEAN hasPurePower (LObject *L,int last, int *length,kStrategy strat)
711{
712  if (L->bucket != NULL)
713  {
714    poly p = L->CanonicalizeP();
715    BOOLEAN ret = hasPurePower(p, last, length, strat);
716    pNext(p) = NULL;
717    return ret;
718  }
719  else
720  {
721    return hasPurePower(L->p, last, length, strat);
722  }
723}
724
725/*2
726* looks up the position of polynomial p in L
727* in the case of looking for the pure powers
728*/
729int posInL10 (const LSet set,const int length, LObject* p,const kStrategy strat)
730{
731  int j,dp,dL;
732
733  if (length<0) return 0;
734  if (hasPurePower(p,strat->lastAxis,&dp,strat))
735  {
736    int op= p->GetpFDeg() +p->ecart;
737    for (j=length; j>=0; j--)
738    {
739      if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
740        return j+1;
741      if (dp < dL)
742        return j+1;
743      if ((dp == dL)
744          && (set[j].GetpFDeg()+set[j].ecart >= op))
745        return j+1;
746    }
747  }
748  j=length;
749  loop
750  {
751    if (j<0) break;
752    if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
753    j--;
754  }
755  return strat->posInLOld(set,j,p,strat);
756}
757
758
759/*2
760* computes the s-polynomials L[ ].p in L
761*/
762void updateL(kStrategy strat)
763{
764  LObject p;
765  int dL;
766  int j=strat->Ll;
767  loop
768  {
769    if (j<0) break;
770    if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
771    {
772      p=strat->L[strat->Ll];
773      strat->L[strat->Ll]=strat->L[j];
774      strat->L[j]=p;
775      break;
776    }
777    j--;
778  }
779  if (j<0)
780  {
781    j=strat->Ll;
782    loop
783    {
784      if (j<0) break;
785      if (pNext(strat->L[j].p) == strat->tail)
786      {
787#ifdef HAVE_RINGS
788        if (rField_is_Ring(currRing))
789          pLmDelete(strat->L[j].p);    /*deletes the short spoly and computes*/
790        else
791#else
792          pLmFree(strat->L[j].p);    /*deletes the short spoly and computes*/
793#endif
794        strat->L[j].p = NULL;
795        poly m1 = NULL, m2 = NULL;
796        // check that spoly creation is ok
797        while (strat->tailRing != currRing &&
798               !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
799        {
800          assume(m1 == NULL && m2 == NULL);
801          // if not, change to a ring where exponents are at least
802          // large enough
803          kStratChangeTailRing(strat);
804        }
805        /* create the real one */
806        ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
807                      strat->tailRing, m1, m2, strat->R);
808
809        strat->L[j].SetLmCurrRing();
810        if (!strat->honey)
811          strat->initEcart(&strat->L[j]);
812        else
813          strat->L[j].SetLength(strat->length_pLength);
814
815        BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
816
817        if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
818
819        if (pp)
820        {
821          p=strat->L[strat->Ll];
822          strat->L[strat->Ll]=strat->L[j];
823          strat->L[j]=p;
824          break;
825        }
826      }
827      j--;
828    }
829  }
830}
831
832/*2
833* computes the s-polynomials L[ ].p in L and
834* cuts elements in L above noether
835*/
836void updateLHC(kStrategy strat)
837{
838  int i = 0;
839  kTest_TS(strat);
840  while (i <= strat->Ll)
841  {
842    if (pNext(strat->L[i].p) == strat->tail)
843    {
844       /*- deletes the int spoly and computes -*/
845      if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
846      {
847        pLmFree(strat->L[i].p);
848        strat->L[i].p = NULL;
849      }
850      else
851      {
852        pLmFree(strat->L[i].p);
853        strat->L[i].p = NULL;
854        poly m1 = NULL, m2 = NULL;
855        // check that spoly creation is ok
856        while (strat->tailRing != currRing &&
857               !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
858        {
859          assume(m1 == NULL && m2 == NULL);
860          // if not, change to a ring where exponents are at least
861          // large enough
862          kStratChangeTailRing(strat);
863        }
864        /* create the real one */
865        ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
866                      strat->tailRing, m1, m2, strat->R);
867        if (! strat->L[i].IsNull())
868        {
869          strat->L[i].SetLmCurrRing();
870          strat->L[i].SetpFDeg();
871          strat->L[i].ecart
872            = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
873          if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
874        }
875      }
876    }
877    else
878      deleteHC(&(strat->L[i]), strat);
879   if (strat->L[i].IsNull())
880      deleteInL(strat->L,&strat->Ll,i,strat);
881    else
882    {
883#ifdef KDEBUG
884      kTest_L(&(strat->L[i]), strat->tailRing, TRUE, i, strat->T, strat->tl);
885#endif
886      i++;
887    }
888  }
889  kTest_TS(strat);
890}
891
892/*2
893* cuts in T above strat->kNoether and tries to cancel a unit
894*/
895void updateT(kStrategy strat)
896{
897  int i = 0;
898  LObject p;
899
900  while (i <= strat->tl)
901  {
902    p = strat->T[i];
903    deleteHC(&p,strat, TRUE);
904    /*- tries to cancel a unit: -*/
905    cancelunit(&p);
906    if (p.p != strat->T[i].p)
907    {
908      strat->sevT[i] = pGetShortExpVector(p.p);
909      p.SetpFDeg();
910    }
911    strat->T[i] = p;
912    i++;
913  }
914}
915
916/*2
917* arranges red, pos and T if strat->kHEdgeFound (first time)
918*/
919void firstUpdate(kStrategy strat)
920{
921  if (strat->update)
922  {
923    kTest_TS(strat);
924    strat->update = (strat->tl == -1);
925    if (TEST_OPT_WEIGHTM)
926    {
927      pRestoreDegProcs(pFDegOld, pLDegOld);
928      if (strat->tailRing != currRing)
929      {
930        strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
931        strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
932      }
933      int i;
934      for (i=strat->Ll; i>=0; i--)
935      {
936        strat->L[i].SetpFDeg();
937      }
938      for (i=strat->tl; i>=0; i--)
939      {
940        strat->T[i].SetpFDeg();
941      }
942      if (ecartWeights)
943      {
944        omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
945        ecartWeights=NULL;
946      }
947    }
948    if (TEST_OPT_FASTHC)
949    {
950      strat->posInL = strat->posInLOld;
951      strat->lastAxis = 0;
952    }
953    if (TEST_OPT_FINDET)
954      return;
955    strat->red = redFirst;
956    strat->use_buckets = kMoraUseBucket(strat);
957    updateT(strat);
958    strat->posInT = posInT2;
959    reorderT(strat);
960  }
961  kTest_TS(strat);
962}
963
964/*2
965*-puts p to the standardbasis s at position at
966*-reduces the tail of p if TEST_OPT_REDTAIL
967*-tries to cancel a unit
968*-HEckeTest
969*  if TRUE
970*  - decides about reduction-strategies
971*  - computes noether
972*  - stops computation if TEST_OPT_FINDET
973*  - cuts the tails of the polynomials
974*    in s,t and the elements in L above noether
975*    and cancels units if possible
976*  - reorders s,L
977*/
978void enterSMora (LObject p,int atS,kStrategy strat, int atR = -1)
979{
980  int i;
981  enterSBba(p, atS, strat, atR);
982  #ifdef KDEBUG
983  if (TEST_OPT_DEBUG)
984  {
985    Print("new s%d:",atS);
986    wrp(p.p);
987    PrintLn();
988  }
989  #endif
990  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
991  if (strat->kHEdgeFound)
992  {
993    if (newHEdge(strat->S,strat))
994    {
995      firstUpdate(strat);
996      if (TEST_OPT_FINDET)
997        return;
998      /*- cuts elements in L above noether and reorders L -*/
999      updateLHC(strat);
1000      /*- reorders L with respect to posInL -*/
1001      reorderL(strat);
1002    }
1003  }
1004  else if (strat->kNoether!=NULL)
1005    strat->kHEdgeFound = TRUE;
1006  else if (TEST_OPT_FASTHC)
1007  {
1008    if (strat->posInLOldFlag)
1009    {
1010      missingAxis(&strat->lastAxis,strat);
1011      if (strat->lastAxis)
1012      {
1013        strat->posInLOld = strat->posInL;
1014        strat->posInLOldFlag = FALSE;
1015        strat->posInL = posInL10;
1016        strat->posInLDependsOnLength = TRUE;
1017        updateL(strat);
1018        reorderL(strat);
1019      }
1020    }
1021    else if (strat->lastAxis)
1022      updateL(strat);
1023  }
1024}
1025
1026/*2
1027*-puts p to the standardbasis s at position at
1028*-HEckeTest
1029*  if TRUE
1030*  - computes noether
1031*/
1032void enterSMoraNF (LObject p, int atS,kStrategy strat, int atR = -1)
1033{
1034  int i;
1035
1036  enterSBba(p, atS, strat, atR);
1037  if ((!strat->kHEdgeFound) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1038  if (strat->kHEdgeFound)
1039    newHEdge(strat->S,strat);
1040  else if (strat->kNoether!=NULL)
1041    strat->kHEdgeFound = TRUE;
1042}
1043
1044void initBba(ideal F,kStrategy strat)
1045{
1046  int i;
1047  idhdl h;
1048 /* setting global variables ------------------- */
1049  strat->enterS = enterSBba;
1050    strat->red = redHoney;
1051  if (strat->honey)
1052    strat->red = redHoney;
1053  else if (pLexOrder && !strat->homog)
1054    strat->red = redLazy;
1055  else
1056  {
1057    strat->LazyPass *=4;
1058    strat->red = redHomog;
1059  }
1060#ifdef HAVE_RINGS  //TODO Oliver
1061  if (rField_is_Ring(currRing))
1062  {
1063    strat->red = redRing;
1064  }
1065#endif
1066  if (pLexOrder && strat->honey)
1067    strat->initEcart = initEcartNormal;
1068  else
1069    strat->initEcart = initEcartBBA;
1070  if (strat->honey)
1071    strat->initEcartPair = initEcartPairMora;
1072  else
1073    strat->initEcartPair = initEcartPairBba;
1074  strat->kIdeal = NULL;
1075  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1076  //else              strat->kIdeal->rtyp=MODUL_CMD;
1077  //strat->kIdeal->data=(void *)strat->Shdl;
1078  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1079  {
1080    //interred  machen   Aenderung
1081    pFDegOld=pFDeg;
1082    pLDegOld=pLDeg;
1083    //h=ggetid("ecart");
1084    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1085    //{
1086    //  ecartWeights=iv2array(IDINTVEC(h));
1087    //}
1088    //else
1089    {
1090      ecartWeights=(short *)omAlloc((pVariables+1)*sizeof(short));
1091      /*uses automatic computation of the ecartWeights to set them*/
1092      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1093    }
1094    pRestoreDegProcs(totaldegreeWecart, maxdegreeWecart);
1095    if (TEST_OPT_PROT)
1096    {
1097      for(i=1; i<=pVariables; i++)
1098        Print(" %d",ecartWeights[i]);
1099      PrintLn();
1100      mflush();
1101    }
1102  }
1103}
1104
1105void initMora(ideal F,kStrategy strat)
1106{
1107  int i,j;
1108  idhdl h;
1109
1110  strat->NotUsedAxis = (BOOLEAN *)omAlloc((pVariables+1)*sizeof(BOOLEAN));
1111  for (j=pVariables; j>0; j--) strat->NotUsedAxis[j] = TRUE;
1112  strat->enterS = enterSMora;
1113  strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1114  strat->posInLOld = strat->posInL;
1115  strat->posInLOldFlag = TRUE;
1116  strat->initEcart = initEcartNormal;
1117  strat->kHEdgeFound = ppNoether != NULL;
1118  if ( strat->kHEdgeFound )
1119     strat->kNoether = pCopy(ppNoether);
1120  else if (strat->kHEdgeFound || strat->homog)
1121    strat->red = redFirst;  /*take the first possible in T*/
1122  else
1123    strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1124  if (strat->kHEdgeFound)
1125  {
1126    strat->HCord = pFDeg(ppNoether,currRing)+1;
1127    strat->posInT = posInT2;
1128  }
1129  else
1130  {
1131    strat->HCord = 32000;/*- very large -*/
1132  }
1133  /*reads the ecartWeights used for Graebes method from the
1134   *intvec ecart and set ecartWeights
1135   */
1136  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1137  {
1138    //interred  machen   Aenderung
1139    pFDegOld=pFDeg;
1140    pLDegOld=pLDeg;
1141    //h=ggetid("ecart");
1142    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1143    //{
1144    //  ecartWeights=iv2array(IDINTVEC(h));
1145    //}
1146    //else
1147    {
1148      ecartWeights=(short *)omAlloc((pVariables+1)*sizeof(short));
1149      /*uses automatic computation of the ecartWeights to set them*/
1150      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1151    }
1152
1153    pSetDegProcs(totaldegreeWecart, maxdegreeWecart);
1154    if (TEST_OPT_PROT)
1155    {
1156      for(i=1; i<=pVariables; i++)
1157        Print(" %d",ecartWeights[i]);
1158      PrintLn();
1159      mflush();
1160    }
1161  }
1162  kOptimizeLDeg(pLDeg, strat);
1163}
1164
1165#ifdef HAVE_ASSUME
1166static int mora_count = 0;
1167static int mora_loop_count;
1168#endif
1169
1170void kDebugPrint(kStrategy strat);
1171
1172ideal mora (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1173{
1174#ifdef HAVE_ASSUME
1175  mora_count++;
1176  mora_loop_count = 0;
1177#endif
1178#ifdef KDEBUG
1179  om_Opts.MinTrack = 5;
1180#endif
1181  int srmax;
1182  int lrmax = 0;
1183  int olddeg = 0;
1184  int reduc = 0;
1185  int red_result = 1;
1186  int hilbeledeg=1,hilbcount=0;
1187
1188  strat->update = TRUE;
1189  /*- setting global variables ------------------- -*/
1190  initBuchMoraCrit(strat);
1191  initHilbCrit(F,Q,&hilb,strat);
1192  initMora(F,strat);
1193  initBuchMoraPos(strat);
1194  /*Shdl=*/initBuchMora(F,Q,strat);
1195  if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1196  /*updateS in initBuchMora has Hecketest
1197  * and could have put strat->kHEdgdeFound FALSE*/
1198  if (ppNoether!=NULL)
1199  {
1200    strat->kHEdgeFound = TRUE;
1201  }
1202  if (strat->kHEdgeFound && strat->update)
1203  {
1204    firstUpdate(strat);
1205    updateLHC(strat);
1206    reorderL(strat);
1207  }
1208  if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1209  {
1210    strat->posInLOld = strat->posInL;
1211    strat->posInLOldFlag = FALSE;
1212    strat->posInL = posInL10;
1213    updateL(strat);
1214    reorderL(strat);
1215  }
1216  srmax = strat->sl;
1217
1218  kTest_TS(strat);
1219  strat->use_buckets = kMoraUseBucket(strat);
1220  /*- compute-------------------------------------------*/
1221
1222#ifdef HAVE_TAIL_RING
1223//  if (strat->homog && strat->red == redFirst)
1224  kStratInitChangeTailRing(strat);
1225#endif
1226  if (BVERBOSE(23))
1227  {
1228    kDebugPrint(strat);
1229  }
1230
1231  while (strat->Ll >= 0)
1232  {
1233#ifdef HAVE_ASSUME
1234    mora_loop_count++;
1235#endif
1236    if (lrmax< strat->Ll) lrmax=strat->Ll; /*stat*/
1237    //test_int_std(strat->kIdeal);
1238    #ifdef KDEBUG
1239    if (TEST_OPT_DEBUG) messageSets(strat);
1240    #endif
1241    if (TEST_OPT_DEGBOUND
1242    && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1243    {
1244      /*
1245      * stops computation if
1246      * - 24 (degBound)
1247      *   && upper degree is bigger than Kstd1_deg
1248      */
1249      while ((strat->Ll >= 0)
1250        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1251        && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1252      )
1253      {
1254        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1255        //if (TEST_OPT_PROT)
1256        //{
1257        //   PrintS("D"); mflush();
1258        //}
1259      }
1260      if (strat->Ll<0) break;
1261      else strat->noClearS=TRUE;
1262    }
1263    strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1264    if (strat->Ll==0) strat->interpt=TRUE;
1265    strat->Ll--;
1266
1267    // create the real Spoly
1268    if (pNext(strat->P.p) == strat->tail)
1269    {
1270      /*- deletes the short spoly and computes -*/
1271#ifdef HAVE_RINGS_LOC
1272      if (rField_is_Ring(currRing))
1273        pLmDelete(strat->P.p);
1274      else
1275#endif
1276      pLmFree(strat->P.p);
1277      strat->P.p = NULL;
1278      poly m1 = NULL, m2 = NULL;
1279      // check that spoly creation is ok
1280      while (strat->tailRing != currRing &&
1281             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1282      {
1283        assume(m1 == NULL && m2 == NULL);
1284        // if not, change to a ring where exponents are large enough
1285        kStratChangeTailRing(strat);
1286      }
1287      /* create the real one */
1288      ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1289                    strat->tailRing, m1, m2, strat->R);
1290      if (!strat->use_buckets)
1291        strat->P.SetLength(strat->length_pLength);
1292    }
1293    else if (strat->P.p1 == NULL)
1294    {
1295      // for input polys, prepare reduction (buckets !)
1296      strat->P.SetLength(strat->length_pLength);
1297      strat->P.PrepareRed(strat->use_buckets);
1298    }
1299
1300    if (!strat->P.IsNull())
1301    {
1302      // might be NULL from noether !!!
1303      if (TEST_OPT_PROT)
1304        message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1305      // reduce
1306      red_result = strat->red(&strat->P,strat);
1307    }
1308
1309    if (! strat->P.IsNull())
1310    {
1311      strat->P.GetP();
1312      // statistics
1313      if (TEST_OPT_PROT) PrintS("s");
1314      // normalization
1315      if (!TEST_OPT_INTSTRATEGY)
1316        strat->P.pNorm();
1317      // tailreduction
1318      strat->P.p = redtail(&(strat->P),strat->sl,strat);
1319      // set ecart -- might have changed because of tail reductions
1320      if ((!strat->noTailReduction) && (!strat->honey))
1321        strat->initEcart(&strat->P);
1322      // cancel unit
1323      cancelunit(&strat->P);
1324      // for char 0, clear denominators
1325      if (TEST_OPT_INTSTRATEGY)
1326        strat->P.pCleardenom();
1327
1328      // put in T
1329      enterT(strat->P,strat);
1330      // build new pairs
1331#ifdef HAVE_RINGS_LOC
1332      if (rField_is_Ring(currRing))
1333        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1334      else
1335#endif
1336      enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
1337      // put in S
1338      strat->enterS(strat->P,
1339                    posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
1340                    strat, strat->tl);
1341
1342      // apply hilbert criterion
1343      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
1344
1345      // clear strat->P
1346      if (strat->P.lcm!=NULL)
1347#ifdef HAVE_RINGS_LOC
1348        pLmDelete(strat->P.lcm);
1349#else
1350        pLmFree(strat->P.lcm);
1351#endif
1352      strat->P.lcm=NULL;
1353#ifdef KDEBUG
1354      // make sure kTest_TS does not complain about strat->P
1355      memset(&strat->P,0,sizeof(strat->P));
1356#endif
1357      if (strat->sl>srmax) srmax = strat->sl; /*stat.*/
1358      if (strat->Ll>lrmax) lrmax = strat->Ll;
1359    }
1360    if (strat->kHEdgeFound)
1361    {
1362      if ((TEST_OPT_FINDET)
1363      || ((TEST_OPT_MULTBOUND) && (scMult0Int((strat->Shdl)) < mu)))
1364      {
1365        // obachman: is this still used ???
1366        /*
1367        * stops computation if strat->kHEdgeFound and
1368        * - 27 (finiteDeterminacyTest)
1369        * or
1370        * - 23
1371        *   (multBound)
1372        *   && multiplicity of the ideal is smaller then a predefined number mu
1373        */
1374        while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1375      }
1376    }
1377    kTest_TS(strat);
1378  }
1379  /*- complete reduction of the standard basis------------------------ -*/
1380  if (TEST_OPT_REDSB) completeReduce(strat);
1381  else if (TEST_OPT_PROT) PrintLn();
1382  /*- release temp data------------------------------- -*/
1383  exitBuchMora(strat);
1384  /*- polynomials used for HECKE: HC, noether -*/
1385  if (TEST_OPT_FINDET)
1386  {
1387    if (strat->kHEdge!=NULL)
1388      Kstd1_mu=pFDeg(strat->kHEdge,currRing);
1389    else
1390      Kstd1_mu=-1;
1391  }
1392  pDelete(&strat->kHEdge);
1393  strat->update = TRUE; //???
1394  strat->lastAxis = 0; //???
1395  pDelete(&strat->kNoether);
1396  omFreeSize((ADDRESS)strat->NotUsedAxis,(pVariables+1)*sizeof(BOOLEAN));
1397  if (TEST_OPT_PROT) messageStat(srmax,lrmax,hilbcount,strat);
1398  if (TEST_OPT_WEIGHTM)
1399  {
1400    pRestoreDegProcs(pFDegOld, pLDegOld);
1401    if (ecartWeights)
1402    {
1403      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
1404      ecartWeights=NULL;
1405    }
1406  }
1407  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
1408  idTest(strat->Shdl);
1409  return (strat->Shdl);
1410}
1411
1412poly kNF1 (ideal F,ideal Q,poly q, kStrategy strat, int lazyReduce)
1413{
1414  assume(q!=NULL);
1415  assume(!(idIs0(F)&&(Q==NULL)));
1416
1417// lazy_reduce flags: can be combined by |
1418//#define KSTD_NF_LAZY   1
1419  // do only a reduction of the leading term
1420//#define KSTD_NF_ECART  2
1421  // only local: recude even with bad ecart
1422  poly   p;
1423  int   i;
1424  int   j;
1425  int   o;
1426  LObject   h;
1427  BITSET save_test=test;
1428
1429  //if ((idIs0(F))&&(Q==NULL))
1430  //  return pCopy(q); /*F=0*/
1431  //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
1432  /*- creating temp data structures------------------- -*/
1433  strat->kHEdgeFound = ppNoether != NULL;
1434  strat->kNoether    = pCopy(ppNoether);
1435  test|=Sy_bit(OPT_REDTAIL);
1436  test&=~Sy_bit(OPT_INTSTRATEGY);
1437  if (TEST_OPT_STAIRCASEBOUND
1438  && (! TEST_V_DEG_STOP)
1439  && (0<Kstd1_deg)
1440  && ((!strat->kHEdgeFound)
1441    ||(TEST_OPT_DEGBOUND && (pWTotaldegree(strat->kNoether)<Kstd1_deg))))
1442  {
1443    pDelete(&strat->kNoether);
1444    strat->kNoether=pOne();
1445    pSetExp(strat->kNoether,1, Kstd1_deg+1);
1446    pSetm(strat->kNoether);
1447    strat->kHEdgeFound=TRUE;
1448  }
1449  initBuchMoraCrit(strat);
1450  initBuchMoraPos(strat);
1451  initMora(F,strat);
1452  strat->enterS = enterSMoraNF;
1453  /*- set T -*/
1454  strat->tl = -1;
1455  strat->tmax = setmaxT;
1456  strat->T = initT();
1457  strat->R = initR();
1458  strat->sevT = initsevT();
1459  /*- set S -*/
1460  strat->sl = -1;
1461  /*- init local data struct.-------------------------- -*/
1462  /*Shdl=*/initS(F,Q,strat);
1463  if ((strat->ak!=0)
1464  && (strat->kHEdgeFound))
1465  {
1466    if (strat->ak!=1)
1467    {
1468      pSetComp(strat->kNoether,1);
1469      pSetmComp(strat->kNoether);
1470      poly p=pHead(strat->kNoether);
1471      pSetComp(p,strat->ak);
1472      pSetmComp(p);
1473      p=pAdd(strat->kNoether,p);
1474      strat->kNoether=pNext(p);
1475      p_LmFree(p,currRing);
1476    }
1477  }
1478  if ((lazyReduce & KSTD_NF_LAZY)==0)
1479  {
1480    for (i=strat->sl; i>=0; i--)
1481      pNorm(strat->S[i]);
1482  }
1483  /*- puts the elements of S also to T -*/
1484  for (i=0; i<=strat->sl; i++)
1485  {
1486    h.p = strat->S[i];
1487    h.ecart = strat->ecartS[i];
1488    if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
1489    else assume(strat->sevS[i] == pGetShortExpVector(h.p));
1490    h.length = pLength(h.p);
1491    h.sev = strat->sevS[i];
1492    h.SetpFDeg();
1493    enterT(h,strat);
1494  }
1495  /*- compute------------------------------------------- -*/
1496  p = pCopy(q);
1497  deleteHC(&p,&o,&j,strat);
1498  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
1499  if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
1500  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
1501  {
1502    if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
1503    p = redtail(p,strat->sl,strat);
1504  }
1505  /*- release temp data------------------------------- -*/
1506  cleanT(strat);
1507  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
1508  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
1509  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
1510  omFreeSize((ADDRESS)strat->NotUsedAxis,(pVariables+1)*sizeof(BOOLEAN));
1511  omfree(strat->sevT);
1512  omfree(strat->S_2_R);
1513  omfree(strat->R);
1514
1515  if ((Q!=NULL)&&(strat->fromQ!=NULL))
1516  {
1517    i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
1518    omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
1519    strat->fromQ=NULL;
1520  }
1521  pDelete(&strat->kHEdge);
1522  pDelete(&strat->kNoether);
1523  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1524  {
1525    pRestoreDegProcs(pFDegOld, pLDegOld);
1526    if (ecartWeights)
1527    {
1528      omFreeSize((ADDRESS *)&ecartWeights,(pVariables+1)*sizeof(short));
1529      ecartWeights=NULL;
1530    }
1531  }
1532  idDelete(&strat->Shdl);
1533  test=save_test;
1534  if (TEST_OPT_PROT) PrintLn();
1535  return p;
1536}
1537
1538ideal kNF1 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce)
1539{
1540  assume(!idIs0(q));
1541  assume(!(idIs0(F)&&(Q==NULL)));
1542
1543// lazy_reduce flags: can be combined by |
1544//#define KSTD_NF_LAZY   1
1545  // do only a reduction of the leading term
1546//#define KSTD_NF_ECART  2
1547  // only local: recude even with bad ecart
1548  poly   p;
1549  int   i;
1550  int   j;
1551  int   o;
1552  LObject   h;
1553  ideal res;
1554  BITSET save_test=test;
1555
1556  //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
1557  //if ((idIs0(F))&&(Q==NULL))
1558  //  return idCopy(q); /*F=0*/
1559  //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
1560  /*- creating temp data structures------------------- -*/
1561  strat->kHEdgeFound = ppNoether != NULL;
1562  strat->kNoether=pCopy(ppNoether);
1563  test|=Sy_bit(OPT_REDTAIL);
1564  if (TEST_OPT_STAIRCASEBOUND
1565  && (0<Kstd1_deg)
1566  && ((!strat->kHEdgeFound)
1567    ||(TEST_OPT_DEGBOUND && (pWTotaldegree(strat->kNoether)<Kstd1_deg))))
1568  {
1569    pDelete(&strat->kNoether);
1570    strat->kNoether=pOne();
1571    pSetExp(strat->kNoether,1, Kstd1_deg+1);
1572    pSetm(strat->kNoether);
1573    strat->kHEdgeFound=TRUE;
1574  }
1575  initBuchMoraCrit(strat);
1576  initBuchMoraPos(strat);
1577  initMora(F,strat);
1578  strat->enterS = enterSMoraNF;
1579  /*- set T -*/
1580  strat->tl = -1;
1581  strat->tmax = setmaxT;
1582  strat->T = initT();
1583  strat->R = initR();
1584  strat->sevT = initsevT();
1585  /*- set S -*/
1586  strat->sl = -1;
1587  /*- init local data struct.-------------------------- -*/
1588  /*Shdl=*/initS(F,Q,strat);
1589  if ((strat->ak!=0)
1590  && (strat->kHEdgeFound))
1591  {
1592    if (strat->ak!=1)
1593    {
1594      pSetComp(strat->kNoether,1);
1595      pSetmComp(strat->kNoether);
1596      poly p=pHead(strat->kNoether);
1597      pSetComp(p,strat->ak);
1598      pSetmComp(p);
1599      p=pAdd(strat->kNoether,p);
1600      strat->kNoether=pNext(p);
1601      p_LmFree(p,currRing);
1602    }
1603  }
1604  if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
1605  {
1606    for (i=strat->sl; i>=0; i--)
1607      pNorm(strat->S[i]);
1608  }
1609  /*- compute------------------------------------------- -*/
1610  res=idInit(IDELEMS(q),strat->ak);
1611  for (i=0; i<IDELEMS(q); i++)
1612  {
1613    if (q->m[i]!=NULL)
1614    {
1615      p = pCopy(q->m[i]);
1616      deleteHC(&p,&o,&j,strat);
1617      if (p!=NULL)
1618      {
1619        /*- puts the elements of S also to T -*/
1620        for (j=0; j<=strat->sl; j++)
1621        {
1622          h.p = strat->S[j];
1623          h.ecart = strat->ecartS[j];
1624          h.pLength = h.length = pLength(h.p);
1625          if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
1626          else assume(strat->sevS[j] == pGetShortExpVector(h.p));
1627          h.sev = strat->sevS[j];
1628          h.SetpFDeg();
1629          enterT(h,strat);
1630        }
1631        if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
1632        p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
1633        if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
1634        {
1635          if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
1636          p = redtail(p,strat->sl,strat);
1637        }
1638        cleanT(strat);
1639      }
1640      res->m[i]=p;
1641    }
1642    //else
1643    //  res->m[i]=NULL;
1644  }
1645  /*- release temp data------------------------------- -*/
1646  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
1647  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
1648  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
1649  omFreeSize((ADDRESS)strat->NotUsedAxis,(pVariables+1)*sizeof(BOOLEAN));
1650  omfree(strat->sevT);
1651  omfree(strat->S_2_R);
1652  omfree(strat->R);
1653  if ((Q!=NULL)&&(strat->fromQ!=NULL))
1654  {
1655    i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
1656    omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
1657    strat->fromQ=NULL;
1658  }
1659  pDelete(&strat->kHEdge);
1660  pDelete(&strat->kNoether);
1661  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1662  {
1663    pFDeg=pFDegOld;
1664    pLDeg=pLDegOld;
1665    if (ecartWeights)
1666    {
1667      omFreeSize((ADDRESS *)&ecartWeights,(pVariables+1)*sizeof(short));
1668      ecartWeights=NULL;
1669    }
1670  }
1671  idDelete(&strat->Shdl);
1672  test=save_test;
1673  if (TEST_OPT_PROT) PrintLn();
1674  return res;
1675}
1676
1677pFDegProc pFDegOld;
1678pLDegProc pLDegOld;
1679intvec * kModW, * kHomW;
1680
1681long kModDeg(poly p, ring r)
1682{
1683  long o=pWDegree(p, r);
1684  long i=p_GetComp(p, r);
1685  if (i==0) return o;
1686  //assume((i>0) && (i<=kModW->length()));
1687  if (i<=kModW->length())
1688    return o+(*kModW)[i-1];
1689  return o;
1690}
1691long kHomModDeg(poly p, ring r)
1692{
1693  int i;
1694  long j=0;
1695
1696  for (i=r->N;i>0;i--)
1697    j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
1698  if (kModW == NULL) return j;
1699  i = p_GetComp(p,r);
1700  if (i==0) return j;
1701  return j+(*kModW)[i-1];
1702}
1703
1704ideal kStd(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
1705          int newIdeal, intvec *vw)
1706{
1707  if(idIs0(F))
1708    return idInit(1,F->rank);
1709
1710  ideal r;
1711  BOOLEAN b=pLexOrder,toReset=FALSE;
1712  BOOLEAN delete_w=(w==NULL);
1713  kStrategy strat=new skStrategy;
1714
1715  if(!TEST_OPT_RETURN_SB)
1716    strat->syzComp = syzComp;
1717  if (TEST_OPT_SB_1)
1718    strat->newIdeal = newIdeal;
1719  if (rField_has_simple_inverse())
1720    strat->LazyPass=20;
1721  else
1722    strat->LazyPass=2;
1723  strat->LazyDegree = 1;
1724  strat->enterOnePair=enterOnePairNormal;
1725  strat->chainCrit=chainCritNormal;
1726  strat->ak = idRankFreeModule(F);
1727  strat->kModW=kModW=NULL;
1728  strat->kHomW=kHomW=NULL;
1729  if (vw != NULL)
1730  {
1731    pLexOrder=FALSE;
1732    strat->kHomW=kHomW=vw;
1733    pFDegOld = pFDeg;
1734    pLDegOld = pLDeg;
1735    pSetDegProcs(kHomModDeg);
1736    toReset = TRUE;
1737  }
1738  if (h==testHomog)
1739  {
1740    if (strat->ak == 0)
1741    {
1742      h = (tHomog)idHomIdeal(F,Q);
1743      w=NULL;
1744    }
1745    else if (!TEST_OPT_DEGBOUND)
1746    {
1747      h = (tHomog)idHomModule(F,Q,w);
1748    }
1749  }
1750  pLexOrder=b;
1751  if (h==isHomog)
1752  {
1753    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
1754    {
1755      strat->kModW = kModW = *w;
1756      if (vw == NULL)
1757      {
1758        pFDegOld = pFDeg;
1759        pLDegOld = pLDeg;
1760        pSetDegProcs(kModDeg);
1761        toReset = TRUE;
1762      }
1763    }
1764    pLexOrder = TRUE;
1765    if (hilb==NULL) strat->LazyPass*=2;
1766  }
1767  strat->homog=h;
1768#ifdef KDEBUG
1769  idTest(F);
1770  idTest(Q);
1771
1772#if MYTEST
1773  if (TEST_OPT_DEBUG)
1774  {
1775    PrintS("// kSTD: currRing: ");
1776    rWrite(currRing);
1777  }
1778#endif
1779
1780#endif
1781#ifdef HAVE_PLURAL
1782  if (rIsPluralRing(currRing))
1783  {
1784    const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
1785    strat->no_prod_crit   = ! bIsSCA;
1786    if (w!=NULL)
1787      r = nc_GB(F, Q, *w, hilb, strat);
1788    else
1789      r = nc_GB(F, Q, NULL, hilb, strat);
1790  }
1791  else
1792#endif
1793  {
1794    if (pOrdSgn==-1)
1795    {
1796      if (w!=NULL)
1797        r=mora(F,Q,*w,hilb,strat);
1798      else
1799        r=mora(F,Q,NULL,hilb,strat);
1800    }
1801    else
1802    {
1803      if (w!=NULL)
1804        r=bba(F,Q,*w,hilb,strat);
1805      else
1806        r=bba(F,Q,NULL,hilb,strat);
1807    }
1808  }
1809#ifdef KDEBUG
1810  idTest(r);
1811#endif
1812  if (toReset)
1813  {
1814    kModW = NULL;
1815    pRestoreDegProcs(pFDegOld, pLDegOld);
1816  }
1817  pLexOrder = b;
1818//Print("%d reductions canceled \n",strat->cel);
1819  HCord=strat->HCord;
1820  delete(strat);
1821  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
1822  return r;
1823}
1824
1825#ifdef HAVE_SHIFTBBA
1826ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
1827                int newIdeal, intvec *vw, int uptodeg, int lV)
1828{
1829  ideal r;
1830  BOOLEAN b=pLexOrder,toReset=FALSE;
1831  BOOLEAN delete_w=(w==NULL);
1832  kStrategy strat=new skStrategy;
1833
1834  if(!TEST_OPT_RETURN_SB)
1835    strat->syzComp = syzComp;
1836  if (TEST_OPT_SB_1)
1837    strat->newIdeal = newIdeal;
1838  if (rField_has_simple_inverse())
1839    strat->LazyPass=20;
1840  else
1841    strat->LazyPass=2;
1842  strat->LazyDegree = 1;
1843  strat->ak = idRankFreeModule(F);
1844  strat->kModW=kModW=NULL;
1845  strat->kHomW=kHomW=NULL;
1846  if (vw != NULL)
1847  {
1848    pLexOrder=FALSE;
1849    strat->kHomW=kHomW=vw;
1850    pFDegOld = pFDeg;
1851    pLDegOld = pLDeg;
1852    pSetDegProcs(kHomModDeg);
1853    toReset = TRUE;
1854  }
1855  if (h==testHomog)
1856  {
1857    if (strat->ak == 0)
1858    {
1859      h = (tHomog)idHomIdeal(F,Q);
1860      w=NULL;
1861    }
1862    else if (!TEST_OPT_DEGBOUND)
1863    {
1864      h = (tHomog)idHomModule(F,Q,w);
1865    }
1866  }
1867  pLexOrder=b;
1868  if (h==isHomog)
1869  {
1870    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
1871    {
1872      strat->kModW = kModW = *w;
1873      if (vw == NULL)
1874      {
1875        pFDegOld = pFDeg;
1876        pLDegOld = pLDeg;
1877        pSetDegProcs(kModDeg);
1878        toReset = TRUE;
1879      }
1880    }
1881    pLexOrder = TRUE;
1882    if (hilb==NULL) strat->LazyPass*=2;
1883  }
1884  strat->homog=h;
1885#ifdef KDEBUG
1886  idTest(F);
1887#endif
1888  if (pOrdSgn==-1)
1889  {
1890    /* error: no local ord yet with shifts */
1891    Print("No local ordering possible for shifts");
1892    return(NULL);
1893  }
1894  else
1895  {
1896    /* global ordering */
1897    if (w!=NULL)
1898      r=bbaShift(F,Q,*w,hilb,strat,uptodeg,lV);
1899    else
1900      r=bbaShift(F,Q,NULL,hilb,strat,uptodeg,lV);
1901  }
1902#ifdef KDEBUG
1903  idTest(r);
1904#endif
1905  if (toReset)
1906  {
1907    kModW = NULL;
1908    pRestoreDegProcs(pFDegOld, pLDegOld);
1909  }
1910  pLexOrder = b;
1911//Print("%d reductions canceled \n",strat->cel);
1912  HCord=strat->HCord;
1913  delete(strat);
1914  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
1915  return r;
1916}
1917#endif
1918
1919//##############################################################
1920//##############################################################
1921//##############################################################
1922//##############################################################
1923//##############################################################
1924
1925ideal kMin_std(ideal F, ideal Q, tHomog h,intvec ** w, ideal &M, intvec *hilb,
1926              int syzComp, int reduced)
1927{
1928  if(idIs0(F))
1929  {
1930    M=idInit(1,F->rank);
1931    return idInit(1,F->rank);
1932  }
1933
1934  ideal r=NULL;
1935  int Kstd1_OldDeg = Kstd1_deg,i;
1936  intvec* temp_w=NULL;
1937  BOOLEAN b=pLexOrder,toReset=FALSE;
1938  BOOLEAN delete_w=(w==NULL);
1939  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
1940  kStrategy strat=new skStrategy;
1941
1942  if(!TEST_OPT_RETURN_SB)
1943     strat->syzComp = syzComp;
1944  if (rField_has_simple_inverse())
1945    strat->LazyPass=20;
1946  else
1947    strat->LazyPass=2;
1948  strat->LazyDegree = 1;
1949  strat->minim=(reduced % 2)+1;
1950  strat->ak = idRankFreeModule(F);
1951  if (delete_w)
1952  {
1953    temp_w=new intvec((strat->ak)+1);
1954    w = &temp_w;
1955  }
1956  if ((h==testHomog)
1957  )
1958  {
1959    if (strat->ak == 0)
1960    {
1961      h = (tHomog)idHomIdeal(F,Q);
1962      w=NULL;
1963    }
1964    else
1965    {
1966      h = (tHomog)idHomModule(F,Q,w);
1967    }
1968  }
1969  if (h==isHomog)
1970  {
1971    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
1972    {
1973      kModW = *w;
1974      strat->kModW = *w;
1975      assume(pFDeg != NULL && pLDeg != NULL);
1976      pFDegOld = pFDeg;
1977      pLDegOld = pLDeg;
1978      pSetDegProcs(kModDeg);
1979
1980      toReset = TRUE;
1981      if (reduced>1)
1982      {
1983        Kstd1_OldDeg=Kstd1_deg;
1984        Kstd1_deg = -1;
1985        for (i=IDELEMS(F)-1;i>=0;i--)
1986        {
1987          if ((F->m[i]!=NULL) && (pFDeg(F->m[i],currRing)>=Kstd1_deg))
1988            Kstd1_deg = pFDeg(F->m[i],currRing)+1;
1989        }
1990      }
1991    }
1992    pLexOrder = TRUE;
1993    strat->LazyPass*=2;
1994  }
1995  strat->homog=h;
1996  if (pOrdSgn==-1)
1997  {
1998    if (w!=NULL)
1999      r=mora(F,Q,*w,hilb,strat);
2000    else
2001      r=mora(F,Q,NULL,hilb,strat);
2002  }
2003  else
2004  {
2005    if (w!=NULL)
2006      r=bba(F,Q,*w,hilb,strat);
2007    else
2008      r=bba(F,Q,NULL,hilb,strat);
2009  }
2010#ifdef KDEBUG
2011  {
2012    int i;
2013    for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
2014  }
2015#endif
2016  idSkipZeroes(r);
2017  if (toReset)
2018  {
2019    pRestoreDegProcs(pFDegOld, pLDegOld);
2020    kModW = NULL;
2021  }
2022  pLexOrder = b;
2023  HCord=strat->HCord;
2024  if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
2025  if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
2026  {
2027    M=idInit(1,F->rank);
2028    M->m[0]=pOne();
2029    //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
2030    if (strat->M!=NULL) idDelete(&strat->M);
2031  }
2032  else if (strat->M==NULL)
2033  {
2034    M=idInit(1,F->rank);
2035    Warn("no minimal generating set computed");
2036  }
2037  else
2038  {
2039    idSkipZeroes(strat->M);
2040    M=strat->M;
2041  }
2042  delete(strat);
2043  if (reduced>2)
2044  {
2045    Kstd1_deg=Kstd1_OldDeg;
2046    if (!oldDegBound)
2047      test &= ~Sy_bit(OPT_DEGBOUND);
2048  }
2049  else
2050  {
2051    if (IDELEMS(M)>IDELEMS(r)) { idDelete(&M); M=idCopy(r); }
2052  }
2053  return r;
2054}
2055
2056poly kNF(ideal F, ideal Q, poly p,int syzComp, int lazyReduce)
2057{
2058  if (p==NULL)
2059     return NULL;
2060
2061  poly pp = p;
2062
2063#ifdef HAVE_PLURAL
2064  if(rIsSCA(currRing))
2065  {
2066    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2067    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
2068    pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
2069
2070    if(Q == currQuotient)
2071      Q = SCAQuotient(currRing);
2072  }
2073#endif
2074
2075  if ((idIs0(F))&&(Q==NULL))
2076  {
2077#ifdef HAVE_PLURAL
2078    if(p != pp)
2079      return pp;
2080#endif
2081    return pCopy(p); /*F+Q=0*/
2082  }
2083
2084  kStrategy strat=new skStrategy;
2085  strat->syzComp = syzComp;
2086  strat->ak = si_max(idRankFreeModule(F),pMaxComp(p));
2087  poly res;
2088
2089  if (pOrdSgn==-1)
2090    res=kNF1(F,Q,pp,strat,lazyReduce);
2091  else
2092    res=kNF2(F,Q,pp,strat,lazyReduce);
2093  delete(strat);
2094
2095#ifdef HAVE_PLURAL
2096  if(pp != p)
2097    p_Delete(&pp, currRing);
2098#endif
2099  return res;
2100}
2101
2102ideal kNF(ideal F, ideal Q, ideal p,int syzComp,int lazyReduce)
2103{
2104  ideal res;
2105  if (TEST_OPT_PROT)
2106  {
2107    Print("(S:%d)",IDELEMS(p));mflush();
2108  }
2109  if (idIs0(p))
2110    return idInit(IDELEMS(p),si_max(p->rank,F->rank));
2111
2112  ideal pp = p;
2113#ifdef HAVE_PLURAL
2114  if(rIsSCA(currRing))
2115  {
2116    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2117    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
2118    pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
2119
2120    if(Q == currQuotient)
2121      Q = SCAQuotient(currRing);
2122  }
2123#endif
2124
2125  if ((idIs0(F))&&(Q==NULL))
2126  {
2127#ifdef HAVE_PLURAL
2128    if(p != pp)
2129      return pp;
2130#endif
2131    return idCopy(p); /*F+Q=0*/
2132  }
2133
2134  kStrategy strat=new skStrategy;
2135  strat->syzComp = syzComp;
2136  strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(p));
2137  strat->ak = si_max(strat->ak,(int)F->rank);
2138
2139  if (pOrdSgn==-1)
2140    res=kNF1(F,Q,pp,strat,lazyReduce);
2141  else
2142    res=kNF2(F,Q,pp,strat,lazyReduce);
2143  delete(strat);
2144
2145#ifdef HAVE_PLURAL
2146  if(pp != p)
2147    id_Delete(&pp, currRing);
2148#endif
2149
2150  return res;
2151}
2152
2153/*2
2154*interreduces F
2155*/
2156// old version
2157ideal kInterRedOld (ideal F, ideal Q)
2158{
2159  int j;
2160  kStrategy strat = new skStrategy;
2161
2162  ideal tempF = F;
2163  ideal tempQ = Q;
2164
2165#ifdef HAVE_PLURAL
2166  if(rIsSCA(currRing))
2167  {
2168    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
2169    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
2170    tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
2171
2172    // this should be done on the upper level!!! :
2173    //    tempQ = SCAQuotient(currRing);
2174
2175    if(Q == currQuotient)
2176      tempQ = SCAQuotient(currRing);
2177  }
2178#endif
2179
2180//  if (TEST_OPT_PROT)
2181//  {
2182//    writeTime("start InterRed:");
2183//    mflush();
2184//  }
2185  //strat->syzComp     = 0;
2186  strat->kHEdgeFound = ppNoether != NULL;
2187  strat->kNoether=pCopy(ppNoether);
2188  strat->ak = idRankFreeModule(tempF);
2189  initBuchMoraCrit(strat);
2190  strat->NotUsedAxis = (BOOLEAN *)omAlloc((pVariables+1)*sizeof(BOOLEAN));
2191  for (j=pVariables; j>0; j--) strat->NotUsedAxis[j] = TRUE;
2192  strat->enterS      = enterSBba;
2193  strat->posInT      = posInT17;
2194  strat->initEcart   = initEcartNormal;
2195  strat->sl   = -1;
2196  strat->tl          = -1;
2197  strat->tmax        = setmaxT;
2198  strat->T           = initT();
2199  strat->R           = initR();
2200  strat->sevT        = initsevT();
2201  if (pOrdSgn == -1)   strat->honey = TRUE;
2202  initS(tempF, tempQ, strat);
2203  if (TEST_OPT_REDSB)
2204    strat->noTailReduction=FALSE;
2205  updateS(TRUE,strat);
2206  if (TEST_OPT_REDSB && TEST_OPT_INTSTRATEGY)
2207    completeReduce(strat);
2208  //else if (TEST_OPT_PROT) PrintLn();
2209  pDelete(&strat->kHEdge);
2210  omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2211  omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2212  omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2213  omFreeSize((ADDRESS)strat->NotUsedAxis,(pVariables+1)*sizeof(BOOLEAN));
2214  omfree(strat->sevT);
2215  omfree(strat->S_2_R);
2216  omfree(strat->R);
2217
2218  if (strat->fromQ)
2219  {
2220    for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
2221    {
2222      if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
2223    }
2224    omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
2225  }
2226//  if (TEST_OPT_PROT)
2227//  {
2228//    writeTime("end Interred:");
2229//    mflush();
2230//  }
2231  ideal shdl=strat->Shdl;
2232  idSkipZeroes(shdl);
2233  if (strat->fromQ)
2234  {
2235    strat->fromQ=NULL;
2236    ideal res=kInterRed(shdl,NULL);
2237    idDelete(&shdl);
2238    shdl=res;
2239  }
2240  delete(strat);
2241#ifdef HAVE_PLURAL
2242  if( tempF != F )
2243    id_Delete( &tempF, currRing);
2244#endif
2245  return shdl;
2246}
2247// new version
2248ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
2249{
2250  need_retry=0;
2251  int   srmax,lrmax, red_result = 1;
2252  int   olddeg,reduc;
2253  BOOLEAN withT = FALSE;
2254  BOOLEAN b=pLexOrder;
2255  BOOLEAN toReset=FALSE;
2256  kStrategy strat=new skStrategy;
2257  tHomog h;
2258  intvec * w=NULL;
2259
2260  if (rField_has_simple_inverse())
2261    strat->LazyPass=20;
2262  else
2263    strat->LazyPass=2;
2264  strat->LazyDegree = 1;
2265  strat->ak = idRankFreeModule(F);
2266  strat->syzComp = strat->ak;
2267  strat->kModW=kModW=NULL;
2268  strat->kHomW=kHomW=NULL;
2269  if (strat->ak == 0)
2270  {
2271    h = (tHomog)idHomIdeal(F,Q);
2272    w=NULL;
2273  }
2274  else if (!TEST_OPT_DEGBOUND)
2275  {
2276    h = (tHomog)idHomModule(F,Q,&w);
2277  }
2278  pLexOrder=b;
2279  if (h==isHomog)
2280  {
2281    if (strat->ak > 0 && (w!=NULL) && (w!=NULL))
2282    {
2283      strat->kModW = kModW = w;
2284      pFDegOld = pFDeg;
2285      pLDegOld = pLDeg;
2286      pSetDegProcs(kModDeg);
2287      toReset = TRUE;
2288    }
2289    pLexOrder = TRUE;
2290    strat->LazyPass*=2;
2291  }
2292  strat->homog=h;
2293#ifdef KDEBUG
2294  idTest(F);
2295#endif
2296
2297  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2298  initBuchMoraPos(strat);
2299  initBba(F,strat);
2300  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2301  strat->posInL=posInL0; /* ord according pComp */
2302
2303  /*Shdl=*/initBuchMora(F, Q,strat);
2304  srmax = strat->sl;
2305  reduc = olddeg = lrmax = 0;
2306
2307#ifndef NO_BUCKETS
2308  if (!TEST_OPT_NOT_BUCKETS)
2309    strat->use_buckets = 1;
2310#endif
2311
2312  // redtailBBa against T for inhomogenous input
2313  if (!K_TEST_OPT_OLDSTD)
2314    withT = ! strat->homog;
2315
2316  // strat->posInT = posInT_pLength;
2317  kTest_TS(strat);
2318
2319#ifdef HAVE_TAIL_RING
2320  kStratInitChangeTailRing(strat);
2321#endif
2322
2323  /* compute------------------------------------------------------- */
2324  while (strat->Ll >= 0)
2325  {
2326    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2327    #ifdef KDEBUG
2328      if (TEST_OPT_DEBUG) messageSets(strat);
2329    #endif
2330    if (strat->Ll== 0) strat->interpt=TRUE;
2331    /* picks the last element from the lazyset L */
2332    strat->P = strat->L[strat->Ll];
2333    strat->Ll--;
2334
2335    if (strat->P.p1 == NULL)
2336    {
2337      // for input polys, prepare reduction
2338      strat->P.PrepareRed(strat->use_buckets);
2339    }
2340
2341    if (strat->P.p == NULL && strat->P.t_p == NULL)
2342    {
2343      red_result = 0;
2344    }
2345    else
2346    {
2347      int deg_before=olddeg;
2348      if (TEST_OPT_PROT)
2349        message(strat->P.pFDeg(),
2350                &olddeg,&reduc,strat, red_result);
2351
2352      /* reduction of the element choosen from L */
2353      red_result = strat->red(&strat->P,strat);
2354    }
2355
2356    // reduction to non-zero new poly
2357    if (red_result == 1)
2358    {
2359      /* statistic */
2360      if (TEST_OPT_PROT) PrintS("s");
2361
2362      // get the polynomial (canonicalize bucket, make sure P.p is set)
2363      strat->P.GetP(strat->lmBin);
2364
2365      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2366
2367      // reduce the tail and normalize poly
2368      // in the ring case we cannot expect LC(f) = 1,
2369      // therefore we call pContent instead of pNorm
2370      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
2371      {
2372        strat->P.pCleardenom();
2373        if (0)
2374        //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2375        {
2376          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2377          strat->P.pCleardenom();
2378        }
2379      }
2380      else
2381      {
2382        strat->P.pNorm();
2383        if (0)
2384        //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2385          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2386      }
2387
2388#ifdef KDEBUG
2389      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2390#endif
2391
2392      // enter into S, L, and T
2393      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2394        enterT(strat->P, strat);
2395      // posInS only depends on the leading term
2396      strat->enterS(strat->P, pos, strat, strat->tl);
2397
2398      if (strat->P.lcm!=NULL)
2399#ifdef HAVE_RINGS
2400        pLmDelete(strat->P.lcm);
2401#else
2402        pLmFree(strat->P.lcm);
2403#endif
2404      if (strat->sl>srmax) srmax = strat->sl;
2405      if (pos<strat->sl)
2406      {
2407        need_retry++;
2408        // move all "larger" elements fromS to L
2409        // remove them from T
2410        int ii=pos+1;
2411        for(;ii<=strat->sl;ii++)
2412        {
2413          LObject h;
2414          memset(&h,0,sizeof(h));
2415          h.tailRing=strat->tailRing;
2416          h.p=strat->S[ii]; strat->S[ii]=NULL;
2417          strat->initEcart(&h);
2418          h.sev=strat->sevS[ii];
2419          int jj=strat->tl;
2420          while (jj>=0)
2421          {
2422            if (strat->T[jj].p==h.p)
2423            {
2424              strat->T[jj].p=NULL;
2425              if (jj<strat->tl)
2426              {
2427                memmove(&(strat->T[jj]),&(strat->T[jj+1]),
2428                        (strat->tl-jj)*sizeof(strat->T[jj]));
2429                memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
2430                        (strat->tl-jj)*sizeof(strat->sevT[jj]));
2431              }
2432              strat->tl--;
2433              break;
2434            }
2435            jj--;
2436          }
2437          int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
2438          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
2439        }
2440        strat->sl=pos;
2441      }
2442    }
2443
2444#ifdef KDEBUG
2445    memset(&(strat->P), 0, sizeof(strat->P));
2446#endif
2447    //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
2448  }
2449#ifdef KDEBUG
2450  //if (TEST_OPT_DEBUG) messageSets(strat);
2451#endif
2452  /* complete reduction of the standard basis--------- */
2453
2454  if((need_retry==0) && (TEST_OPT_REDSB))
2455  {
2456    completeReduce(strat);
2457#ifdef HAVE_TAIL_RING
2458    if (strat->completeReduce_retry)
2459    {
2460      // completeReduce needed larger exponents, retry
2461      // to reduce with S (instead of T)
2462      // and in currRing (instead of strat->tailRing)
2463      cleanT(strat);strat->tailRing=currRing;
2464      int i;
2465      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2466      completeReduce(strat);
2467    }
2468#endif
2469  }
2470  else if (TEST_OPT_PROT) PrintLn();
2471
2472  /* release temp data-------------------------------- */
2473  exitBuchMora(strat);
2474  if (TEST_OPT_WEIGHTM)
2475  {
2476    pRestoreDegProcs(pFDegOld, pLDegOld);
2477    if (ecartWeights)
2478    {
2479      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
2480      ecartWeights=NULL;
2481    }
2482  }
2483  //if (TEST_OPT_PROT) messageStat(srmax,lrmax,0/*hilbcount*/,strat);
2484  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2485  ideal res=strat->Shdl;
2486  strat->Shdl=NULL;
2487  delete strat;
2488  if (w!=NULL) delete w;
2489  return res;
2490}
2491ideal kInterRed (ideal F, ideal Q)
2492{
2493#ifdef HAVE_PLURAL
2494  if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
2495#endif
2496  if ((pOrdSgn==-1)
2497  || (rField_is_numeric(currRing)))
2498    return kInterRedOld(F,Q);
2499
2500    //return kInterRedOld(F,Q);
2501
2502  BITSET save=test;
2503  //test|=Sy_bit(OPT_NOT_SUGAR);
2504  test|=Sy_bit(OPT_REDTHROUGH);
2505  //test&= ~Sy_bit(OPT_REDTAIL);
2506  //test&= ~Sy_bit(OPT_REDSB);
2507  //extern char * showOption() ;
2508  //Print("%s\n",showOption());
2509
2510  int need_retry;
2511  int counter=3;
2512  int elems=idElem(F);
2513  ideal res=kInterRedBba(F,Q,need_retry);
2514  while (need_retry && (counter>0))
2515  {
2516    ideal res1=kInterRedBba(res,Q,need_retry);
2517    int new_elems=idElem(res1);
2518    counter -= (new_elems >= elems);
2519    elems = new_elems;
2520    idDelete(&res);
2521    res = res1;
2522  }
2523  test=save;
2524  idSkipZeroes(res);
2525  return res;
2526}
2527
2528
2529// returns TRUE if mora should use buckets, false otherwise
2530static BOOLEAN kMoraUseBucket(kStrategy strat)
2531{
2532#ifdef MORA_USE_BUCKETS
2533  if (TEST_OPT_NOT_BUCKETS)
2534    return FALSE;
2535  if (strat->red == redFirst)
2536  {
2537#ifdef NO_LDEG
2538    if (strat->syzComp==0)
2539      return TRUE;
2540#else
2541    if ((strat->homog || strat->honey) && (strat->syzComp==0))
2542      return TRUE;
2543#endif
2544  }
2545  else
2546  {
2547    assume(strat->red == redEcart);
2548    if (strat->honey && (strat->syzComp==0))
2549      return TRUE;
2550  }
2551#endif
2552  return FALSE;
2553}
Note: See TracBrowser for help on using the repository browser.