source: git/kernel/kstd1.cc @ c536ff

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