source: git/kernel/kstd1.cc @ faa12b1

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