source: git/kernel/kstd1.cc @ 720ff4

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