source: git/kernel/kstd1.cc @ 5572c1

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