source: git/kernel/GBEngine/kstd2.cc @ ede2ad8

spielwiese
Last change on this file since ede2ad8 was ede2ad8, checked in by Hans Schoenemann <hannes@…>, 8 years ago
fix tr. #712: std(SB,I) does not allow crit3 because of the (wrong) order of reductions if size(I)*4 > 3*size(SB), use std(SB+I), otherwise disable crit3
  • Property mode set to 100644
File size: 91.9 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/*
5*  ABSTRACT -  Kernel: alg. of Buchberger
6*/
7
8// #define PDEBUG 2
9
10
11
12
13
14#include <kernel/mod2.h>
15
16#ifndef SING_NDEBUG
17# define MYTEST 0
18#else /* ifndef SING_NDEBUG */
19# define MYTEST 0
20#endif /* ifndef SING_NDEBUG */
21
22#if MYTEST
23# ifdef HAVE_TAIL_RING
24#  undef HAVE_TAIL_RING
25# endif // ifdef HAVE_TAIL_RING
26#endif
27
28// define if no buckets should be used
29// #define NO_BUCKETS
30
31#ifdef HAVE_PLURAL
32#define PLURAL_INTERNAL_DECLARATIONS 1
33#endif
34
35/***********************************************
36 * SBA stuff -- start
37***********************************************/
38#define DEBUGF50  0
39#define DEBUGF51  0
40
41#ifdef DEBUGF5
42#undef DEBUGF5
43//#define DEBUGF5 1
44#endif
45
46#define F5C       1
47#if F5C
48  #define F5CTAILRED 1
49#endif
50
51#define SBA_INTERRED_START                  0
52#define SBA_TAIL_RED                        1
53#define SBA_PRODUCT_CRITERION               0
54#define SBA_PRINT_ZERO_REDUCTIONS           0
55#define SBA_PRINT_REDUCTION_STEPS           0
56#define SBA_PRINT_OPERATIONS                0
57#define SBA_PRINT_SIZE_G                    0
58#define SBA_PRINT_SIZE_SYZ                  0
59#define SBA_PRINT_PRODUCT_CRITERION         0
60
61// counts sba's reduction steps
62#if SBA_PRINT_REDUCTION_STEPS
63long sba_reduction_steps;
64long sba_interreduction_steps;
65#endif
66#if SBA_PRINT_OPERATIONS
67long sba_operations;
68long sba_interreduction_operations;
69#endif
70
71/***********************************************
72 * SBA stuff -- done
73***********************************************/
74
75#include <kernel/GBEngine/kutil.h>
76#include <misc/options.h>
77#include <omalloc/omalloc.h>
78#include <kernel/polys.h>
79#include <kernel/ideals.h>
80#include <kernel/GBEngine/kstd1.h>
81#include <kernel/GBEngine/khstd.h>
82#include <polys/kbuckets.h>
83#include <polys/prCopy.h>
84//#include "cntrlc.h"
85#include <polys/weight.h>
86#include <misc/intvec.h>
87#ifdef HAVE_PLURAL
88#include <polys/nc/nc.h>
89#endif
90// #include "timer.h"
91
92/* shiftgb stuff */
93#include <kernel/GBEngine/shiftgb.h>
94
95  int (*test_PosInT)(const TSet T,const int tl,LObject &h);
96  int (*test_PosInL)(const LSet set, const int length,
97                LObject* L,const kStrategy strat);
98
99// return -1 if no divisor is found
100//        number of first divisor, otherwise
101int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
102{
103  unsigned long not_sev = ~L->sev;
104  int j = start;
105
106  const TSet T=strat->T;
107  const unsigned long* sevT=strat->sevT;
108  if (L->p!=NULL)
109  {
110    const ring r=currRing;
111    const poly p=L->p;
112
113    pAssume(~not_sev == p_GetShortExpVector(p, r));
114
115    loop
116    {
117      if (j > strat->tl) return -1;
118#if defined(PDEBUG) || defined(PDIV_DEBUG)
119      if (p_LmShortDivisibleBy(T[j].p, sevT[j],
120                               p, not_sev, r))
121        return j;
122#else
123      if (!(sevT[j] & not_sev) &&
124          p_LmDivisibleBy(T[j].p, p, r))
125        return j;
126#endif
127      j++;
128    }
129  }
130  else
131  {
132    const poly p=L->t_p;
133    const ring r=strat->tailRing;
134    loop
135    {
136      if (j > strat->tl) return -1;
137#if defined(PDEBUG) || defined(PDIV_DEBUG)
138      if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
139                               p, not_sev, r))
140        return j;
141#else
142      if (!(sevT[j] & not_sev) &&
143          p_LmDivisibleBy(T[j].t_p, p, r))
144        return j;
145#endif
146      j++;
147    }
148  }
149}
150
151// same as above, only with set S
152int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
153{
154  unsigned long not_sev = ~L->sev;
155  poly p = L->GetLmCurrRing();
156  int j = 0;
157
158  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
159#if 1
160  int ende;
161  if ((strat->ak>0) || currRing->pLexOrder) ende=strat->sl;
162  else ende=posInS(strat,*max_ind,p,0)+1;
163  if (ende>(*max_ind)) ende=(*max_ind);
164#else
165  int ende=strat->sl;
166#endif
167  (*max_ind)=ende;
168  loop
169  {
170    if (j > ende) return -1;
171#if defined(PDEBUG) || defined(PDIV_DEBUG)
172    if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
173                             p, not_sev, currRing))
174        return j;
175#else
176    if ( !(strat->sevS[j] & not_sev) &&
177         p_LmDivisibleBy(strat->S[j], p, currRing))
178      return j;
179#endif
180    j++;
181  }
182}
183
184int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
185{
186  unsigned long not_sev = ~L->sev;
187  poly p = L->GetLmCurrRing();
188  int j = start;
189
190  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
191#if 1
192  int ende=max_ind;
193#else
194  int ende=strat->sl;
195#endif
196  loop
197  {
198    if (j > ende) return -1;
199#if defined(PDEBUG) || defined(PDIV_DEBUG)
200    if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
201                             p, not_sev, currRing))
202        return j;
203#else
204    if ( !(strat->sevS[j] & not_sev) &&
205         p_LmDivisibleBy(strat->S[j], p, currRing))
206      return j;
207#endif
208    j++;
209  }
210}
211
212#ifdef HAVE_RINGS
213poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
214{
215  // m = currRing->ch
216
217  if (input_p == NULL) return NULL;
218
219  poly p = input_p;
220  poly zeroPoly = NULL;
221  unsigned long a = (unsigned long) pGetCoeff(p);
222
223  int k_ind2 = 0;
224  int a_ind2 = ind2(a);
225
226  // unsigned long k = 1;
227  // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
228  for (int i = 1; i <= leadRing->N; i++)
229  {
230    k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
231  }
232
233  a = (unsigned long) pGetCoeff(p);
234
235  number tmp1;
236  poly tmp2, tmp3;
237  poly lead_mult = p_ISet(1, tailRing);
238  if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
239  {
240    int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
241    int s_exp;
242    zeroPoly = p_ISet(a, tailRing);
243    for (int i = 1; i <= leadRing->N; i++)
244    {
245      s_exp = p_GetExp(p, i,leadRing);
246      if (s_exp % 2 != 0)
247      {
248        s_exp = s_exp - 1;
249      }
250      while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
251      {
252        too_much = too_much - ind2(s_exp);
253        s_exp = s_exp - 2;
254      }
255      p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
256      for (int j = 1; j <= s_exp; j++)
257      {
258        tmp1 = nInit(j);
259        tmp2 = p_ISet(1, tailRing);
260        p_SetExp(tmp2, i, 1, tailRing);
261        p_Setm(tmp2, tailRing);
262        if (nIsZero(tmp1))
263        { // should nowbe obsolet, test ! TODO OLIVER
264          zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
265        }
266        else
267        {
268          tmp3 = p_NSet(nCopy(tmp1), tailRing);
269          zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
270        }
271      }
272    }
273    p_Setm(lead_mult, tailRing);
274    zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
275    tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
276    for (int i = 1; i <= leadRing->N; i++)
277    {
278      pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
279    }
280    p_Setm(tmp2, leadRing);
281    zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
282    pNext(tmp2) = zeroPoly;
283    return tmp2;
284  }
285/*  unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
286  if (1 == 0 && alpha_k <= a)
287  {  // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
288    zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
289    for (int i = 1; i <= leadRing->N; i++)
290    {
291      for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
292      {
293        tmp1 = nInit(j);
294        tmp2 = p_ISet(1, tailRing);
295        p_SetExp(tmp2, i, 1, tailRing);
296        p_Setm(tmp2, tailRing);
297        if (nIsZero(tmp1))
298        {
299          zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
300        }
301        else
302        {
303          tmp3 = p_ISet((unsigned long) tmp1, tailRing);
304          zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
305        }
306      }
307    }
308    tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
309    for (int i = 1; i <= leadRing->N; i++)
310    {
311      pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
312    }
313    p_Setm(tmp2, leadRing);
314    zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
315    pNext(tmp2) = zeroPoly;
316    return tmp2;
317  } */
318  return NULL;
319}
320#endif
321
322
323#ifdef HAVE_RINGS
324/*2
325*  reduction procedure for the ring Z/2^m
326*/
327int redRing (LObject* h,kStrategy strat)
328{
329  if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
330  if (strat->tl<0) return 1;
331
332  int at/*,i*/;
333  long d;
334  int j = 0;
335  int pass = 0;
336  // poly zeroPoly = NULL;
337
338// TODO warum SetpFDeg notwendig?
339  h->SetpFDeg();
340  assume(h->pFDeg() == h->FDeg);
341  long reddeg = h->GetpFDeg();
342
343  h->SetShortExpVector();
344  loop
345  {
346    j = kFindDivisibleByInT(strat, h);
347    if (j < 0) return 1;
348    ksReducePoly(h, &(strat->T[j]), NULL, NULL, strat); // with debug output
349
350    if (h->GetLmTailRing() == NULL)
351    {
352      if (h->lcm!=NULL) pLmDelete(h->lcm);
353#ifdef KDEBUG
354      h->lcm=NULL;
355#endif
356      h->Clear();
357      return 0;
358    }
359    h->SetShortExpVector();
360    d = h->SetpFDeg();
361    /*- try to reduce the s-polynomial -*/
362    pass++;
363    if (!TEST_OPT_REDTHROUGH &&
364        (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
365    {
366      h->SetLmCurrRing();
367      if (strat->posInLDependsOnLength)
368        h->SetLength(strat->length_pLength);
369      at = strat->posInL(strat->L,strat->Ll,h,strat);
370      if (at <= strat->Ll)
371      {
372#ifdef KDEBUG
373        if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
374#endif
375        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);     // NOT RING CHECKED OLIVER
376        h->Clear();
377        return -1;
378      }
379    }
380    if (d != reddeg)
381    {
382      if (d >= (long)strat->tailRing->bitmask)
383      {
384        if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
385        {
386          strat->overflow=TRUE;
387          //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
388          h->GetP();
389          at = strat->posInL(strat->L,strat->Ll,h,strat);
390          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
391          h->Clear();
392          return -1;
393        }
394      }
395      else if ((TEST_OPT_PROT) && (strat->Ll < 0))
396      {
397        Print(".%ld",d);mflush();
398        reddeg = d;
399      }
400    }
401  }
402}
403#endif
404
405/*2
406*  reduction procedure for the homogeneous case
407*  and the case of a degree-ordering
408*/
409int redHomog (LObject* h,kStrategy strat)
410{
411  if (strat->tl<0) return 1;
412  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
413  assume(h->FDeg == h->pFDeg());
414
415  poly h_p;
416  int i,j,at,pass, ii;
417  unsigned long not_sev;
418  // long reddeg,d;
419
420  pass = j = 0;
421  // d = reddeg = h->GetpFDeg();
422  h->SetShortExpVector();
423  int li;
424  h_p = h->GetLmTailRing();
425  not_sev = ~ h->sev;
426  loop
427  {
428    j = kFindDivisibleByInT(strat, h);
429    if (j < 0) return 1;
430
431    li = strat->T[j].pLength;
432    ii = j;
433    /*
434     * the polynomial to reduce with (up to the moment) is;
435     * pi with length li
436     */
437    i = j;
438#if 1
439    if (TEST_OPT_LENGTH)
440    loop
441    {
442      /*- search the shortest possible with respect to length -*/
443      i++;
444      if (i > strat->tl)
445        break;
446      if (li<=1)
447        break;
448      if ((strat->T[i].pLength < li)
449         &&
450          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
451                               h_p, not_sev, strat->tailRing))
452      {
453        /*
454         * the polynomial to reduce with is now;
455         */
456        li = strat->T[i].pLength;
457        ii = i;
458      }
459    }
460#endif
461
462    /*
463     * end of search: have to reduce with pi
464     */
465#ifdef KDEBUG
466    if (TEST_OPT_DEBUG)
467    {
468      PrintS("red:");
469      h->wrp();
470      PrintS(" with ");
471      strat->T[ii].wrp();
472    }
473#endif
474    assume(strat->fromT == FALSE);
475
476    ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
477#if SBA_PRINT_REDUCTION_STEPS
478    sba_interreduction_steps++;
479#endif
480#if SBA_PRINT_OPERATIONS
481    sba_interreduction_operations  +=  pLength(strat->T[ii].p);
482#endif
483
484#ifdef KDEBUG
485    if (TEST_OPT_DEBUG)
486    {
487      PrintS("\nto ");
488      h->wrp();
489      PrintLn();
490    }
491#endif
492
493    h_p = h->GetLmTailRing();
494    if (h_p == NULL)
495    {
496      if (h->lcm!=NULL) pLmFree(h->lcm);
497#ifdef KDEBUG
498      h->lcm=NULL;
499#endif
500      return 0;
501    }
502    h->SetShortExpVector();
503    not_sev = ~ h->sev;
504    /*
505     * try to reduce the s-polynomial h
506     *test first whether h should go to the lazyset L
507     *-if the degree jumps
508     *-if the number of pre-defined reductions jumps
509     */
510    pass++;
511    if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
512    {
513      h->SetLmCurrRing();
514      at = strat->posInL(strat->L,strat->Ll,h,strat);
515      if (at <= strat->Ll)
516      {
517        int dummy=strat->sl;
518        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
519          return 1;
520        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
521#ifdef KDEBUG
522        if (TEST_OPT_DEBUG)
523          Print(" lazy: -> L%d\n",at);
524#endif
525        h->Clear();
526        return -1;
527      }
528    }
529  }
530}
531
532KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red)
533{
534  BOOLEAN ret;
535  number coef;
536
537  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
538  Red->HeadNormalize();
539  /*
540  printf("------------------------\n");
541  pWrite(Red->GetLmCurrRing());
542  */
543  ret = ksReducePolySig(Red, PW, 1, NULL, &coef);
544
545
546  if (!ret)
547  {
548    if (! n_IsOne(coef, currRing->cf))
549    {
550      PR->Mult_nn(coef);
551      // HANNES: mark for Normalize
552    }
553    n_Delete(&coef, currRing->cf);
554  }
555  return ret;
556}
557
558/*2
559*  reduction procedure for signature-based standard
560*  basis algorithms:
561*  all reductions have to be sig-safe!
562*
563*  2 is returned if and only if the pair is rejected by the rewritten criterion
564*  at exactly this point of the computations. This is the last possible point
565*  such a check can be done => checks with the biggest set of available
566*  signatures
567*/
568int redSig (LObject* h,kStrategy strat)
569{
570  if (strat->tl<0) return 1;
571  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
572  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
573  assume(h->FDeg == h->pFDeg());
574//#if 1
575#ifdef DEBUGF5
576  Print("------- IN REDSIG -------\n");
577  Print("p: ");
578  pWrite(pHead(h->p));
579  Print("p1: ");
580  pWrite(pHead(h->p1));
581  Print("p2: ");
582  pWrite(pHead(h->p2));
583  Print("---------------------------\n");
584#endif
585  poly h_p;
586  int i,j,at,pass, ii;
587  int start=0;
588  int sigSafe;
589  unsigned long not_sev;
590  // long reddeg,d;
591
592  pass = j = 0;
593  // d = reddeg = h->GetpFDeg();
594  h->SetShortExpVector();
595  int li;
596  h_p = h->GetLmTailRing();
597  not_sev = ~ h->sev;
598  loop
599  {
600    j = kFindDivisibleByInT(strat, h, start);
601    if (j < 0)
602    {
603      return 1;
604    }
605
606    li = strat->T[j].pLength;
607    ii = j;
608    /*
609     * the polynomial to reduce with (up to the moment) is;
610     * pi with length li
611     */
612    i = j;
613#if 1
614    if (TEST_OPT_LENGTH)
615    loop
616    {
617      /*- search the shortest possible with respect to length -*/
618      i++;
619      if (i > strat->tl)
620        break;
621      if (li<=1)
622        break;
623      if ((strat->T[i].pLength < li)
624         &&
625          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
626                               h_p, not_sev, strat->tailRing))
627      {
628        /*
629         * the polynomial to reduce with is now;
630         */
631        li = strat->T[i].pLength;
632        ii = i;
633      }
634    }
635    start = ii+1;
636#endif
637
638    /*
639     * end of search: have to reduce with pi
640     */
641#ifdef KDEBUG
642    if (TEST_OPT_DEBUG)
643    {
644      PrintS("red:");
645      h->wrp();
646      PrintS(" with ");
647      strat->T[ii].wrp();
648    }
649#endif
650    assume(strat->fromT == FALSE);
651//#if 1
652#ifdef DEBUGF5
653    Print("BEFORE REDUCTION WITH %d:\n",ii);
654    Print("--------------------------------\n");
655    pWrite(h->sig);
656    pWrite(strat->T[ii].sig);
657    pWrite(h->GetLmCurrRing());
658    pWrite(pHead(h->p1));
659    pWrite(pHead(h->p2));
660    pWrite(pHead(strat->T[ii].p));
661    Print("--------------------------------\n");
662    printf("INDEX OF REDUCER T: %d\n",ii);
663#endif
664    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
665#if SBA_PRINT_REDUCTION_STEPS
666    if (sigSafe != 3)
667      sba_reduction_steps++;
668#endif
669#if SBA_PRINT_OPERATIONS
670    if (sigSafe != 3)
671      sba_operations  +=  pLength(strat->T[ii].p);
672#endif
673    // if reduction has taken place, i.e. the reduction was sig-safe
674    // otherwise start is already at the next position and the loop
675    // searching reducers in T goes on from index start
676//#if 1
677#ifdef DEBUGF5
678    Print("SigSAFE: %d\n",sigSafe);
679#endif
680    if (sigSafe != 3)
681    {
682      // start the next search for reducers in T from the beginning
683      start = 0;
684#ifdef KDEBUG
685      if (TEST_OPT_DEBUG)
686      {
687        PrintS("\nto ");
688        h->wrp();
689        PrintLn();
690      }
691#endif
692
693      h_p = h->GetLmTailRing();
694      if (h_p == NULL)
695      {
696        if (h->lcm!=NULL) pLmFree(h->lcm);
697#ifdef KDEBUG
698        h->lcm=NULL;
699#endif
700        return 0;
701      }
702      h->SetShortExpVector();
703      not_sev = ~ h->sev;
704      /*
705      * try to reduce the s-polynomial h
706      *test first whether h should go to the lazyset L
707      *-if the degree jumps
708      *-if the number of pre-defined reductions jumps
709      */
710      pass++;
711      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
712      {
713        h->SetLmCurrRing();
714        at = strat->posInL(strat->L,strat->Ll,h,strat);
715        if (at <= strat->Ll)
716        {
717          int dummy=strat->sl;
718          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
719          {
720            return 1;
721          }
722          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
723#ifdef KDEBUG
724          if (TEST_OPT_DEBUG)
725            Print(" lazy: -> L%d\n",at);
726#endif
727          h->Clear();
728          return -1;
729        }
730      }
731    }
732  }
733}
734
735// tail reduction for SBA
736poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
737{
738#define REDTAIL_CANONICALIZE 100
739  strat->redTailChange=FALSE;
740  if (strat->noTailReduction) return L->GetLmCurrRing();
741  poly h, p;
742  p = h = L->GetLmTailRing();
743  if ((h==NULL) || (pNext(h)==NULL))
744    return L->GetLmCurrRing();
745
746  TObject* With;
747  // placeholder in case strat->tl < 0
748  TObject  With_s(strat->tailRing);
749
750  LObject Ln(pNext(h), strat->tailRing);
751  Ln.sig      = L->sig;
752  Ln.sevSig   = L->sevSig;
753  Ln.pLength  = L->GetpLength() - 1;
754
755  pNext(h) = NULL;
756  if (L->p != NULL) pNext(L->p) = NULL;
757  L->pLength = 1;
758
759  Ln.PrepareRed(strat->use_buckets);
760
761  int cnt=REDTAIL_CANONICALIZE;
762  while(!Ln.IsNull())
763  {
764    loop
765    {
766      Ln.SetShortExpVector();
767      if (withT)
768      {
769        int j;
770        j = kFindDivisibleByInT(strat, &Ln);
771        if (j < 0) break;
772        With = &(strat->T[j]);
773      }
774      else
775      {
776        With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
777        if (With == NULL) break;
778      }
779      cnt--;
780      if (cnt==0)
781      {
782        cnt=REDTAIL_CANONICALIZE;
783        /*poly tmp=*/Ln.CanonicalizeP();
784        if (normalize)
785        {
786          Ln.Normalize();
787          //pNormalize(tmp);
788          //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
789        }
790      }
791      if (normalize && (!TEST_OPT_INTSTRATEGY) && (!nIsOne(pGetCoeff(With->p))))
792      {
793        With->pNorm();
794      }
795      strat->redTailChange=TRUE;
796      int ret = ksReducePolyTailSig(L, With, &Ln);
797#if SBA_PRINT_REDUCTION_STEPS
798      if (ret != 3)
799        sba_reduction_steps++;
800#endif
801#if SBA_PRINT_OPERATIONS
802      if (ret != 3)
803        sba_operations  +=  pLength(With->p);
804#endif
805      if (ret)
806      {
807        // reducing the tail would violate the exp bound
808        //  set a flag and hope for a retry (in bba)
809        strat->completeReduce_retry=TRUE;
810        if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
811        do
812        {
813          pNext(h) = Ln.LmExtractAndIter();
814          pIter(h);
815          L->pLength++;
816        } while (!Ln.IsNull());
817        goto all_done;
818      }
819      if (Ln.IsNull()) goto all_done;
820      if (! withT) With_s.Init(currRing);
821    }
822    pNext(h) = Ln.LmExtractAndIter();
823    pIter(h);
824    pNormalize(h);
825    L->pLength++;
826  }
827
828  all_done:
829  Ln.Delete();
830  if (L->p != NULL) pNext(L->p) = pNext(p);
831
832  if (strat->redTailChange)
833  {
834    L->length = 0;
835  }
836
837  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
838  //L->Normalize(); // HANNES: should have a test
839  kTest_L(L);
840  return L->GetLmCurrRing();
841}
842
843/*2
844*  reduction procedure for the inhomogeneous case
845*  and not a degree-ordering
846*/
847int redLazy (LObject* h,kStrategy strat)
848{
849  if (strat->tl<0) return 1;
850  int at,i,ii,li;
851  int j = 0;
852  int pass = 0;
853  assume(h->pFDeg() == h->FDeg);
854  long reddeg = h->GetpFDeg();
855  long d;
856  unsigned long not_sev;
857
858  h->SetShortExpVector();
859  poly h_p = h->GetLmTailRing();
860  not_sev = ~ h->sev;
861  loop
862  {
863    j = kFindDivisibleByInT(strat, h);
864    if (j < 0) return 1;
865
866    li = strat->T[j].pLength;
867    #if 0
868    if (li==0)
869    {
870      li=strat->T[j].pLength=pLength(strat->T[j].p);
871    }
872    #endif
873    ii = j;
874    /*
875     * the polynomial to reduce with (up to the moment) is;
876     * pi with length li
877     */
878
879    i = j;
880#if 1
881    if (TEST_OPT_LENGTH)
882    loop
883    {
884      /*- search the shortest possible with respect to length -*/
885      i++;
886      if (i > strat->tl)
887        break;
888      if (li<=1)
889        break;
890    #if 0
891      if (strat->T[i].pLength==0)
892      {
893        PrintS("!");
894        strat->T[i].pLength=pLength(strat->T[i].p);
895      }
896   #endif
897      if ((strat->T[i].pLength < li)
898         &&
899          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
900                               h_p, not_sev, strat->tailRing))
901      {
902        /*
903         * the polynomial to reduce with is now;
904         */
905        PrintS("+");
906        li = strat->T[i].pLength;
907        ii = i;
908      }
909    }
910#endif
911
912    /*
913     * end of search: have to reduce with pi
914     */
915
916
917#ifdef KDEBUG
918    if (TEST_OPT_DEBUG)
919    {
920      PrintS("red:");
921      h->wrp();
922      PrintS(" with ");
923      strat->T[ii].wrp();
924    }
925#endif
926
927    ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
928#if SBA_PRINT_REDUCTION_STEPS
929    sba_interreduction_steps++;
930#endif
931#if SBA_PRINT_OPERATIONS
932    sba_interreduction_operations  +=  pLength(strat->T[ii].p);
933#endif
934
935#ifdef KDEBUG
936    if (TEST_OPT_DEBUG)
937    {
938      PrintS("\nto ");
939      h->wrp();
940      PrintLn();
941    }
942#endif
943
944    h_p=h->GetLmTailRing();
945
946    if (h_p == NULL)
947    {
948      if (h->lcm!=NULL) pLmFree(h->lcm);
949#ifdef KDEBUG
950      h->lcm=NULL;
951#endif
952      return 0;
953    }
954    h->SetShortExpVector();
955    not_sev = ~ h->sev;
956    d = h->SetpFDeg();
957    /*- try to reduce the s-polynomial -*/
958    pass++;
959    if (//!TEST_OPT_REDTHROUGH &&
960        (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
961    {
962      h->SetLmCurrRing();
963      at = strat->posInL(strat->L,strat->Ll,h,strat);
964      if (at <= strat->Ll)
965      {
966#if 1
967        int dummy=strat->sl;
968        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
969          return 1;
970#endif
971#ifdef KDEBUG
972        if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
973#endif
974        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
975        h->Clear();
976        return -1;
977      }
978    }
979    else if (d != reddeg)
980    {
981      if (d>=(long)strat->tailRing->bitmask)
982      {
983        if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
984        {
985          strat->overflow=TRUE;
986          //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
987          h->GetP();
988          at = strat->posInL(strat->L,strat->Ll,h,strat);
989          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
990          h->Clear();
991          return -1;
992        }
993      }
994      else if ((TEST_OPT_PROT) && (strat->Ll < 0))
995      {
996        Print(".%ld",d);mflush();
997        reddeg = d;
998      }
999    }
1000  }
1001}
1002/*2
1003*  reduction procedure for the sugar-strategy (honey)
1004* reduces h with elements from T choosing first possible
1005* element in T with respect to the given ecart
1006*/
1007int redHoney (LObject* h, kStrategy strat)
1008{
1009  if (strat->tl<0) return 1;
1010  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1011  assume(h->FDeg == h->pFDeg());
1012  poly h_p;
1013  int i,j,at,pass,ei, ii, h_d;
1014  unsigned long not_sev;
1015  long reddeg,d;
1016
1017  pass = j = 0;
1018  d = reddeg = h->GetpFDeg() + h->ecart;
1019  h->SetShortExpVector();
1020  int li;
1021  h_p = h->GetLmTailRing();
1022  not_sev = ~ h->sev;
1023
1024  h->PrepareRed(strat->use_buckets);
1025  loop
1026  {
1027    j=kFindDivisibleByInT(strat, h);
1028    if (j < 0) return 1;
1029
1030    ei = strat->T[j].ecart;
1031    li = strat->T[j].pLength;
1032    ii = j;
1033    /*
1034     * the polynomial to reduce with (up to the moment) is;
1035     * pi with ecart ei
1036     */
1037    i = j;
1038    if (TEST_OPT_LENGTH)
1039    loop
1040    {
1041      /*- takes the first possible with respect to ecart -*/
1042      i++;
1043      if (i > strat->tl)
1044        break;
1045      //if (ei < h->ecart)
1046      //  break;
1047      if (li<=1)
1048        break;
1049      if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
1050         || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1051         &&
1052          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1053                               h_p, not_sev, strat->tailRing))
1054      {
1055        /*
1056         * the polynomial to reduce with is now;
1057         */
1058        ei = strat->T[i].ecart;
1059        li = strat->T[i].pLength;
1060        ii = i;
1061      }
1062    }
1063
1064    /*
1065     * end of search: have to reduce with pi
1066     */
1067    if (!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart))
1068    {
1069      h->GetTP(); // clears bucket
1070      h->SetLmCurrRing();
1071      /*
1072       * It is not possible to reduce h with smaller ecart;
1073       * if possible h goes to the lazy-set L,i.e
1074       * if its position in L would be not the last one
1075       */
1076      if (strat->Ll >= 0) /* L is not empty */
1077      {
1078        at = strat->posInL(strat->L,strat->Ll,h,strat);
1079        if(at <= strat->Ll)
1080          /*- h will not become the next element to reduce -*/
1081        {
1082          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1083#ifdef KDEBUG
1084          if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1085#endif
1086          h->Clear();
1087          return -1;
1088        }
1089      }
1090    }
1091#ifdef KDEBUG
1092    if (TEST_OPT_DEBUG)
1093    {
1094      PrintS("red:");
1095      h->wrp();
1096      PrintS(" with ");
1097      strat->T[ii].wrp();
1098    }
1099#endif
1100    assume(strat->fromT == FALSE);
1101
1102    number coef;
1103    ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),&coef,strat);
1104#if SBA_PRINT_REDUCTION_STEPS
1105    sba_interreduction_steps++;
1106#endif
1107#if SBA_PRINT_OPERATIONS
1108    sba_interreduction_operations  +=  pLength(strat->T[ii].p);
1109#endif
1110#ifdef KDEBUG
1111    if (TEST_OPT_DEBUG)
1112    {
1113      PrintS("\nto:");
1114      h->wrp();
1115      PrintLn();
1116    }
1117#endif
1118    if(h->IsNull())
1119    {
1120      h->Clear();
1121      if (h->lcm!=NULL) pLmFree(h->lcm);
1122      #ifdef KDEBUG
1123      h->lcm=NULL;
1124      #endif
1125      return 0;
1126    }
1127    if (TEST_OPT_IDLIFT)
1128    {
1129      if (h->p!=NULL)
1130      {
1131        if(p_GetComp(h->p,currRing)>strat->syzComp)
1132        {
1133          h->Delete();
1134          return 0;
1135        }
1136      }
1137      else if (h->t_p!=NULL)
1138      {
1139        if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1140        {
1141          h->Delete();
1142          return 0;
1143        }
1144      }
1145    }
1146    h->SetShortExpVector();
1147    not_sev = ~ h->sev;
1148    h_d = h->SetpFDeg();
1149    /* compute the ecart */
1150    if (ei <= h->ecart)
1151      h->ecart = d-h_d;
1152    else
1153      h->ecart = d-h_d+ei-h->ecart;
1154
1155    /*
1156     * try to reduce the s-polynomial h
1157     *test first whether h should go to the lazyset L
1158     *-if the degree jumps
1159     *-if the number of pre-defined reductions jumps
1160     */
1161    pass++;
1162    d = h_d + h->ecart;
1163    if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1164    {
1165      h->GetTP(); // clear bucket
1166      h->SetLmCurrRing();
1167      at = strat->posInL(strat->L,strat->Ll,h,strat);
1168      if (at <= strat->Ll)
1169      {
1170        int dummy=strat->sl;
1171        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1172          return 1;
1173        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1174#ifdef KDEBUG
1175        if (TEST_OPT_DEBUG)
1176          Print(" degree jumped: -> L%d\n",at);
1177#endif
1178        h->Clear();
1179        return -1;
1180      }
1181    }
1182    else if (d > reddeg)
1183    {
1184      if (d>=(long)strat->tailRing->bitmask)
1185      {
1186        if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
1187        {
1188          strat->overflow=TRUE;
1189          //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1190          h->GetP();
1191          at = strat->posInL(strat->L,strat->Ll,h,strat);
1192          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1193          h->Clear();
1194          return -1;
1195        }
1196      }
1197      else if (TEST_OPT_PROT && (strat->Ll < 0) )
1198      {
1199        //h->wrp(); Print("<%d>\n",h->GetpLength());
1200        reddeg = d;
1201        Print(".%ld",d); mflush();
1202      }
1203    }
1204  }
1205}
1206
1207/*2
1208*  reduction procedure for the normal form
1209*/
1210
1211poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
1212{
1213  if (h==NULL) return NULL;
1214  int j;
1215  max_ind=strat->sl;
1216
1217  if (0 > strat->sl)
1218  {
1219    return h;
1220  }
1221  LObject P(h);
1222  P.SetShortExpVector();
1223  P.bucket = kBucketCreate(currRing);
1224  kBucketInit(P.bucket,P.p,pLength(P.p));
1225  kbTest(P.bucket);
1226#ifdef HAVE_RINGS
1227  BOOLEAN is_ring = rField_is_Ring(currRing);
1228#endif
1229#ifdef KDEBUG
1230//  if (TEST_OPT_DEBUG)
1231//  {
1232//    PrintS("redNF: starting S:\n");
1233//    for( j = 0; j <= max_ind; j++ )
1234//    {
1235//      Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1236//      pWrite(strat->S[j]);
1237//    }
1238//  };
1239#endif
1240
1241  loop
1242  {
1243    j=kFindDivisibleByInS(strat,&max_ind,&P);
1244    if (j>=0)
1245    {
1246#ifdef HAVE_RINGS
1247      if (!is_ring)
1248      {
1249#endif
1250        int sl=pSize(strat->S[j]);
1251        int jj=j;
1252        loop
1253        {
1254          int sll;
1255          jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
1256          if (jj<0) break;
1257          sll=pSize(strat->S[jj]);
1258          if (sll<sl)
1259          {
1260            #ifdef KDEBUG
1261            if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
1262            #endif
1263            //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
1264            j=jj;
1265            sl=sll;
1266          }
1267        }
1268        if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
1269        {
1270          pNorm(strat->S[j]);
1271          //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1272        }
1273#ifdef HAVE_RINGS
1274      }
1275#endif
1276      nNormalize(pGetCoeff(P.p));
1277#ifdef KDEBUG
1278      if (TEST_OPT_DEBUG)
1279      {
1280        PrintS("red:");
1281        wrp(h);
1282        PrintS(" with ");
1283        wrp(strat->S[j]);
1284      }
1285#endif
1286#ifdef HAVE_PLURAL
1287      if (rIsPluralRing(currRing))
1288      {
1289        number coef;
1290        nc_kBucketPolyRed(P.bucket,strat->S[j],&coef);
1291        nDelete(&coef);
1292      }
1293      else
1294#endif
1295      {
1296        number coef;
1297        coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
1298        nDelete(&coef);
1299      }
1300      h = kBucketGetLm(P.bucket);   // FRAGE OLIVER
1301      if (h==NULL)
1302      {
1303        kBucketDestroy(&P.bucket);
1304
1305#ifdef KDEBUG
1306//        if (TEST_OPT_DEBUG)
1307//        {
1308//          PrintS("redNF: starting S:\n");
1309//          for( j = 0; j <= max_ind; j++ )
1310//          {
1311//            Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1312//            pWrite(strat->S[j]);
1313//          }
1314//        };
1315#endif
1316
1317        return NULL;
1318      }
1319      kbTest(P.bucket);
1320      P.p=h;
1321      P.t_p=NULL;
1322      P.SetShortExpVector();
1323#ifdef KDEBUG
1324      if (TEST_OPT_DEBUG)
1325      {
1326        PrintS("\nto:");
1327        wrp(h);
1328        PrintLn();
1329      }
1330#endif
1331    }
1332    else
1333    {
1334      P.p=kBucketClear(P.bucket);
1335      kBucketDestroy(&P.bucket);
1336      pNormalize(P.p);
1337
1338#ifdef KDEBUG
1339//      if (TEST_OPT_DEBUG)
1340//      {
1341//        PrintS("redNF: starting S:\n");
1342//        for( j = 0; j <= max_ind; j++ )
1343//        {
1344//          Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1345//          pWrite(strat->S[j]);
1346//        }
1347//      };
1348#endif
1349
1350      return P.p;
1351    }
1352  }
1353}
1354
1355void kDebugPrint(kStrategy strat);
1356
1357ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1358{
1359  int   red_result = 1;
1360  int   olddeg,reduc;
1361  int hilbeledeg=1,hilbcount=0,minimcnt=0;
1362  BOOLEAN withT = FALSE;
1363  BITSET save;
1364  SI_SAVE_OPT1(save);
1365
1366  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
1367  initBuchMoraPos(strat);
1368  initHilbCrit(F,Q,&hilb,strat);
1369  initBba(F,strat);
1370  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
1371  /*Shdl=*/initBuchMora(F, Q,strat);
1372  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1373  reduc = olddeg = 0;
1374
1375#ifndef NO_BUCKETS
1376  if (!TEST_OPT_NOT_BUCKETS)
1377    strat->use_buckets = 1;
1378#endif
1379  // redtailBBa against T for inhomogenous input
1380  if (!TEST_OPT_OLDSTD)
1381    withT = ! strat->homog;
1382
1383  // strat->posInT = posInT_pLength;
1384  kTest_TS(strat);
1385
1386#ifdef KDEBUG
1387#if MYTEST
1388  if (TEST_OPT_DEBUG)
1389  {
1390    PrintS("bba start GB: currRing: ");
1391    // rWrite(currRing);PrintLn();
1392    rDebugPrint(currRing);
1393    PrintLn();
1394  }
1395#endif /* MYTEST */
1396#endif /* KDEBUG */
1397
1398#ifdef HAVE_TAIL_RING
1399  if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
1400    kStratInitChangeTailRing(strat);
1401#endif
1402  if (BVERBOSE(23))
1403  {
1404    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1405    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1406    kDebugPrint(strat);
1407  }
1408
1409
1410#ifdef KDEBUG
1411  //kDebugPrint(strat);
1412#endif
1413  /* compute------------------------------------------------------- */
1414  while (strat->Ll >= 0)
1415  {
1416    #ifdef KDEBUG
1417      if (TEST_OPT_DEBUG) messageSets(strat);
1418    #endif
1419    if (strat->Ll== 0) strat->interpt=TRUE;
1420    if (TEST_OPT_DEGBOUND
1421        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1422            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
1423    {
1424      /*
1425       *stops computation if
1426       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
1427       *a predefined number Kstd1_deg
1428       */
1429      while ((strat->Ll >= 0)
1430        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1431        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1432            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
1433        )
1434        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1435      if (strat->Ll<0) break;
1436      else strat->noClearS=TRUE;
1437    }
1438    /* picks the last element from the lazyset L */
1439    strat->P = strat->L[strat->Ll];
1440    strat->Ll--;
1441
1442    if (pNext(strat->P.p) == strat->tail)
1443    {
1444      // deletes the short spoly
1445#ifdef HAVE_RINGS
1446      if (rField_is_Ring(currRing))
1447        pLmDelete(strat->P.p);
1448      else
1449#endif
1450        pLmFree(strat->P.p);
1451      strat->P.p = NULL;
1452      poly m1 = NULL, m2 = NULL;
1453
1454      // check that spoly creation is ok
1455      while (strat->tailRing != currRing &&
1456             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1457      {
1458        assume(m1 == NULL && m2 == NULL);
1459        // if not, change to a ring where exponents are at least
1460        // large enough
1461        if (!kStratChangeTailRing(strat))
1462        {
1463          WerrorS("OVERFLOW...");
1464          break;
1465        }
1466      }
1467      // create the real one
1468      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
1469                    strat->tailRing, m1, m2, strat->R);
1470    }
1471    else if (strat->P.p1 == NULL)
1472    {
1473      if (strat->minim > 0)
1474        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
1475      // for input polys, prepare reduction
1476      strat->P.PrepareRed(strat->use_buckets);
1477    }
1478
1479    if (strat->P.p == NULL && strat->P.t_p == NULL)
1480    {
1481      red_result = 0;
1482    }
1483    else
1484    {
1485      if (TEST_OPT_PROT)
1486        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
1487                &olddeg,&reduc,strat, red_result);
1488
1489      /* reduction of the element chosen from L */
1490      red_result = strat->red(&strat->P,strat);
1491      if (errorreported)  break;
1492    }
1493
1494    if (strat->overflow)
1495    {
1496      if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
1497    }
1498
1499    // reduction to non-zero new poly
1500    if (red_result == 1)
1501    {
1502      // get the polynomial (canonicalize bucket, make sure P.p is set)
1503      strat->P.GetP(strat->lmBin);
1504      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
1505      // but now, for entering S, T, we reset it
1506      // in the inhomogeneous case: FDeg == pFDeg
1507      if (strat->homog) strat->initEcart(&(strat->P));
1508
1509      /* statistic */
1510      if (TEST_OPT_PROT) PrintS("s");
1511
1512      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1513
1514#ifdef KDEBUG
1515#if MYTEST
1516      PrintS("New S: "); p_DebugPrint(strat->P.p, currRing); PrintLn();
1517#endif /* MYTEST */
1518#endif /* KDEBUG */
1519
1520      // reduce the tail and normalize poly
1521      // in the ring case we cannot expect LC(f) = 1,
1522      // therefore we call pContent instead of pNorm
1523      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
1524      {
1525        strat->P.pCleardenom();
1526        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
1527        {
1528          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1529          strat->P.pCleardenom();
1530        }
1531      }
1532      else
1533      {
1534        strat->P.pNorm();
1535        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
1536          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1537      }
1538
1539#ifdef KDEBUG
1540      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
1541#if MYTEST
1542      PrintS("New (reduced) S: "); p_DebugPrint(strat->P.p, currRing); PrintLn();
1543#endif /* MYTEST */
1544#endif /* KDEBUG */
1545
1546      // min_std stuff
1547      if ((strat->P.p1==NULL) && (strat->minim>0))
1548      {
1549        if (strat->minim==1)
1550        {
1551          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
1552          p_Delete(&strat->P.p2, currRing, strat->tailRing);
1553        }
1554        else
1555        {
1556          strat->M->m[minimcnt]=strat->P.p2;
1557          strat->P.p2=NULL;
1558        }
1559        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
1560          pNext(strat->M->m[minimcnt])
1561            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
1562                                           strat->tailRing, currRing,
1563                                           currRing->PolyBin);
1564        minimcnt++;
1565      }
1566
1567      // enter into S, L, and T
1568      if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
1569      {
1570        enterT(strat->P, strat);
1571#ifdef HAVE_RINGS
1572        if (rField_is_Ring(currRing))
1573          superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1574        else
1575#endif
1576          enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1577        // posInS only depends on the leading term
1578        strat->enterS(strat->P, pos, strat, strat->tl);
1579#if 0
1580        int pl=pLength(strat->P.p);
1581        if (pl==1)
1582        {
1583          //if (TEST_OPT_PROT)
1584          //PrintS("<1>");
1585        }
1586        else if (pl==2)
1587        {
1588          //if (TEST_OPT_PROT)
1589          //PrintS("<2>");
1590        }
1591#endif
1592      }
1593      if (strat->s_poly!=NULL)
1594      {
1595        if (strat->s_poly(strat))
1596        {
1597          // we are called AFTER enterS, i.e. if we change P
1598          // we have it also to S/T
1599          // and add pairs
1600          int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1601          enterT(strat->P, strat);
1602          #ifdef HAVE_RINGS
1603          if (rField_is_Ring(currRing))
1604            superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1605          else
1606          #endif
1607            enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1608          strat->enterS(strat->P, pos, strat, strat->tl);
1609        }
1610      }
1611
1612      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
1613//      Print("[%d]",hilbeledeg);
1614      if (strat->P.lcm!=NULL)
1615#ifdef HAVE_RINGS
1616        pLmDelete(strat->P.lcm);
1617#else
1618        pLmFree(strat->P.lcm);
1619#endif
1620    }
1621    else if (strat->P.p1 == NULL && strat->minim > 0)
1622    {
1623      p_Delete(&strat->P.p2, currRing, strat->tailRing);
1624    }
1625
1626#ifdef KDEBUG
1627    memset(&(strat->P), 0, sizeof(strat->P));
1628#endif /* KDEBUG */
1629    kTest_TS(strat);
1630  }
1631#ifdef KDEBUG
1632#if MYTEST
1633  PrintS("bba finish GB: currRing: "); rWrite(currRing);
1634#endif /* MYTEST */
1635  if (TEST_OPT_DEBUG) messageSets(strat);
1636#endif /* KDEBUG */
1637
1638  if (TEST_OPT_SB_1)
1639  {
1640    #ifdef HAVE_RINGS
1641    if(!rField_is_Ring(currRing))
1642    #endif
1643    {
1644      int k=1;
1645      int j;
1646      while(k<=strat->sl)
1647      {
1648        j=0;
1649        loop
1650        {
1651          if (j>=k) break;
1652          clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
1653          j++;
1654        }
1655        k++;
1656      }
1657    }
1658  }
1659
1660  /* complete reduction of the standard basis--------- */
1661  if (TEST_OPT_REDSB)
1662  {
1663    completeReduce(strat);
1664#ifdef HAVE_TAIL_RING
1665    if (strat->completeReduce_retry)
1666    {
1667      // completeReduce needed larger exponents, retry
1668      // to reduce with S (instead of T)
1669      // and in currRing (instead of strat->tailRing)
1670      cleanT(strat);strat->tailRing=currRing;
1671      int i;
1672      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
1673      completeReduce(strat);
1674    }
1675#endif
1676  }
1677  else if (TEST_OPT_PROT) PrintLn();
1678
1679  /* release temp data-------------------------------- */
1680  exitBuchMora(strat);
1681//  if (TEST_OPT_WEIGHTM)
1682//  {
1683//    pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
1684//    if (ecartWeights)
1685//    {
1686//      omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
1687//      ecartWeights=NULL;
1688//    }
1689//  }
1690  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
1691  SI_RESTORE_OPT1(save);
1692  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
1693
1694#ifdef KDEBUG
1695#if MYTEST
1696  PrintS("bba_end: currRing: "); rWrite(currRing);
1697#endif /* MYTEST */
1698#endif /* KDEBUG */
1699  idTest(strat->Shdl);
1700
1701  return (strat->Shdl);
1702}
1703ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1704{
1705  // ring order stuff:
1706  // in sba we have (until now) two possibilities:
1707  // 1. an incremental computation w.r.t. (C,monomial order)
1708  // 2. a (possibly non-incremental) computation w.r.t. the
1709  //    induced Schreyer order.
1710  // The corresponding orders are computed in sbaRing(), depending
1711  // on the flag strat->sbaOrder
1712#if SBA_PRINT_ZERO_REDUCTIONS
1713  long zeroreductions           = 0;
1714#endif
1715#if SBA_PRINT_PRODUCT_CRITERION
1716  long product_criterion        = 0;
1717#endif
1718#if SBA_PRINT_SIZE_G
1719  int size_g                    = 0;
1720  int size_g_non_red            = 0;
1721#endif
1722#if SBA_PRINT_SIZE_SYZ
1723  long size_syz                 = 0;
1724#endif
1725  // global variable
1726#if SBA_PRINT_REDUCTION_STEPS
1727  sba_reduction_steps           = 0;
1728  sba_interreduction_steps      = 0;
1729#endif
1730#if SBA_PRINT_OPERATIONS
1731  sba_operations                = 0;
1732  sba_interreduction_operations = 0;
1733#endif
1734
1735  ideal F1 = F0;
1736  ring sRing, currRingOld;
1737  currRingOld  = currRing;
1738  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
1739  {
1740    sRing = sbaRing(strat);
1741    if (sRing!=currRingOld)
1742    {
1743      rChangeCurrRing (sRing);
1744      F1 = idrMoveR (F0, currRingOld, currRing);
1745    }
1746  }
1747  // sort ideal F
1748  ideal F       = idInit(IDELEMS(F1),F1->rank);
1749  intvec *sort  = idSort(F1);
1750  for (int i=0; i<sort->length();++i)
1751    F->m[i] = F1->m[(*sort)[i]-1];
1752#if SBA_INTERRED_START
1753  F = kInterRed(F,NULL);
1754#endif
1755#if F5DEBUG
1756  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
1757  rWrite (currRing);
1758  printf("ordSgn = %d\n",currRing->OrdSgn);
1759  printf("\n");
1760#endif
1761  int   srmax,lrmax, red_result = 1;
1762  int   olddeg,reduc;
1763  int hilbeledeg=1,hilbcount=0,minimcnt=0;
1764  LObject L;
1765  BOOLEAN withT     = TRUE;
1766  strat->max_lower_index = 0;
1767
1768  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
1769  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
1770  initSbaPos(strat);
1771  //initBuchMoraPos(strat);
1772  initHilbCrit(F,Q,&hilb,strat);
1773  initSba(F,strat);
1774  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
1775  /*Shdl=*/initSbaBuchMora(F, Q,strat);
1776  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1777  srmax = strat->sl;
1778  reduc = olddeg = lrmax = 0;
1779
1780#ifndef NO_BUCKETS
1781  if (!TEST_OPT_NOT_BUCKETS)
1782    strat->use_buckets = 1;
1783#endif
1784
1785  // redtailBBa against T for inhomogenous input
1786  // if (!TEST_OPT_OLDSTD)
1787  //   withT = ! strat->homog;
1788
1789  // strat->posInT = posInT_pLength;
1790  kTest_TS(strat);
1791
1792#ifdef KDEBUG
1793#if MYTEST
1794  if (TEST_OPT_DEBUG)
1795  {
1796    PrintS("bba start GB: currRing: ");
1797    // rWrite(currRing);PrintLn();
1798    rDebugPrint(currRing);
1799    PrintLn();
1800  }
1801#endif /* MYTEST */
1802#endif /* KDEBUG */
1803
1804#ifdef HAVE_TAIL_RING
1805  if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
1806    kStratInitChangeTailRing(strat);
1807#endif
1808  if (BVERBOSE(23))
1809  {
1810    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1811    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1812    kDebugPrint(strat);
1813  }
1814
1815
1816#ifdef KDEBUG
1817  //kDebugPrint(strat);
1818#endif
1819  /* compute------------------------------------------------------- */
1820  while (strat->Ll >= 0)
1821  {
1822    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
1823    #ifdef KDEBUG
1824      if (TEST_OPT_DEBUG) messageSets(strat);
1825    #endif
1826    if (strat->Ll== 0) strat->interpt=TRUE;
1827    /*
1828    if (TEST_OPT_DEGBOUND
1829        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1830            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
1831    {
1832
1833       //stops computation if
1834       // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
1835       //a predefined number Kstd1_deg
1836      while ((strat->Ll >= 0)
1837        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1838        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1839            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
1840        )
1841        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1842      if (strat->Ll<0) break;
1843      else strat->noClearS=TRUE;
1844    }
1845    */
1846    if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
1847    {
1848      strat->currIdx  = pGetComp(strat->L[strat->Ll].sig);
1849#if F5C
1850      // 1. interreduction of the current standard basis
1851      // 2. generation of new principal syzygy rules for syzCriterion
1852      f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
1853          lrmax, reduc, Q, w, hilb );
1854#endif
1855      // initialize new syzygy rules for the next iteration step
1856      initSyzRules(strat);
1857
1858    }
1859    /*********************************************************************
1860      * interrreduction step is done, we can go on with the next iteration
1861      * step of the signature-based algorithm
1862      ********************************************************************/
1863    /* picks the last element from the lazyset L */
1864    strat->P = strat->L[strat->Ll];
1865    strat->Ll--;
1866    /* reduction of the element chosen from L */
1867
1868    if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
1869      //#if 1
1870#ifdef DEBUGF5
1871      Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
1872      Print("-------------------------------------------------\n");
1873      pWrite(strat->P.sig);
1874      pWrite(pHead(strat->P.p));
1875      pWrite(pHead(strat->P.p1));
1876      pWrite(pHead(strat->P.p2));
1877      Print("-------------------------------------------------\n");
1878#endif
1879      if (pNext(strat->P.p) == strat->tail)
1880      {
1881        // deletes the short spoly
1882        /*
1883#ifdef HAVE_RINGS
1884        if (rField_is_Ring(currRing))
1885          pLmDelete(strat->P.p);
1886        else
1887#endif
1888          pLmFree(strat->P.p);
1889*/
1890          // TODO: needs some masking
1891          // TODO: masking needs to vanish once the signature
1892          //       sutff is completely implemented
1893          strat->P.p = NULL;
1894        poly m1 = NULL, m2 = NULL;
1895
1896        // check that spoly creation is ok
1897        while (strat->tailRing != currRing &&
1898            !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1899        {
1900          assume(m1 == NULL && m2 == NULL);
1901          // if not, change to a ring where exponents are at least
1902          // large enough
1903          if (!kStratChangeTailRing(strat))
1904          {
1905            WerrorS("OVERFLOW...");
1906            break;
1907          }
1908        }
1909        // create the real one
1910        ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
1911            strat->tailRing, m1, m2, strat->R);
1912
1913      }
1914      else if (strat->P.p1 == NULL)
1915      {
1916        if (strat->minim > 0)
1917          strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
1918        // for input polys, prepare reduction
1919        strat->P.PrepareRed(strat->use_buckets);
1920      }
1921      if (strat->P.p == NULL && strat->P.t_p == NULL)
1922      {
1923        red_result = 0;
1924      }
1925      else
1926      {
1927        //#if 1
1928#ifdef DEBUGF5
1929        Print("Poly before red: ");
1930        pWrite(pHead(strat->P.p));
1931        pWrite(strat->P.sig);
1932#endif
1933#if SBA_PRODUCT_CRITERION
1934        if (strat->P.prod_crit) {
1935#if SBA_PRINT_PRODUCT_CRITERION
1936          product_criterion++;
1937#endif
1938          int pos = posInSyz(strat, strat->P.sig);
1939          enterSyz(strat->P, strat, pos);
1940          if (strat->P.lcm!=NULL)
1941            pLmFree(strat->P.lcm);
1942          red_result = 2;
1943        } else {
1944          red_result = strat->red(&strat->P,strat);
1945        }
1946#else
1947        red_result = strat->red(&strat->P,strat);
1948#endif
1949      }
1950    } else {
1951      /*
1952      if (strat->P.lcm != NULL)
1953        pLmFree(strat->P.lcm);
1954        */
1955      red_result = 2;
1956    }
1957    if (errorreported)  break;
1958
1959//#if 1
1960#ifdef DEBUGF5
1961    if (red_result != 0) {
1962        Print("Poly after red: ");
1963        pWrite(pHead(strat->P.p));
1964        pWrite(strat->P.GetLmCurrRing());
1965        pWrite(strat->P.sig);
1966        printf("%d\n",red_result);
1967    }
1968#endif
1969
1970    if (strat->overflow)
1971    {
1972        if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
1973    }
1974
1975    // reduction to non-zero new poly
1976    if (red_result == 1)
1977    {
1978      // get the polynomial (canonicalize bucket, make sure P.p is set)
1979      strat->P.GetP(strat->lmBin);
1980
1981      // sig-safe computations may lead to wrong FDeg computation, thus we need
1982      // to recompute it to make sure everything is alright
1983      (strat->P).FDeg = (strat->P).pFDeg();
1984      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
1985      // but now, for entering S, T, we reset it
1986      // in the inhomogeneous case: FDeg == pFDeg
1987      if (strat->homog) strat->initEcart(&(strat->P));
1988
1989      /* statistic */
1990      if (TEST_OPT_PROT) PrintS("s");
1991
1992      //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1993      // in F5E we know that the last reduced element is already the
1994      // the one with highest signature
1995      int pos = strat->sl+1;
1996
1997#ifdef KDEBUG
1998#if MYTEST
1999      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
2000#endif /* MYTEST */
2001#endif /* KDEBUG */
2002
2003      // reduce the tail and normalize poly
2004      // in the ring case we cannot expect LC(f) = 1,
2005      // therefore we call pContent instead of pNorm
2006#if SBA_TAIL_RED
2007      if (strat->sbaOrder != 2) {
2008        if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
2009        {
2010          strat->P.pCleardenom();
2011          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2012          {
2013            strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2014            strat->P.pCleardenom();
2015          }
2016        }
2017        else
2018        {
2019          strat->P.pNorm();
2020          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2021            strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2022        }
2023      }
2024#endif
2025
2026    // remove sigsafe label since it is no longer valid for the next element to
2027    // be reduced
2028    if (strat->sbaOrder == 1)
2029    {
2030      for (int jj = 0; jj<strat->tl+1; jj++)
2031      {
2032        if (pGetComp(strat->T[jj].sig) == strat->currIdx)
2033        {
2034          strat->T[jj].is_sigsafe = FALSE;
2035        }
2036      }
2037    }
2038    else
2039    {
2040      for (int jj = 0; jj<strat->tl+1; jj++)
2041      {
2042        strat->T[jj].is_sigsafe = FALSE;
2043      }
2044    }
2045#ifdef KDEBUG
2046      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2047#if MYTEST
2048//#if 1
2049      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
2050#endif /* MYTEST */
2051#endif /* KDEBUG */
2052
2053      // min_std stuff
2054      if ((strat->P.p1==NULL) && (strat->minim>0))
2055      {
2056        if (strat->minim==1)
2057        {
2058          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2059          p_Delete(&strat->P.p2, currRing, strat->tailRing);
2060        }
2061        else
2062        {
2063          strat->M->m[minimcnt]=strat->P.p2;
2064          strat->P.p2=NULL;
2065        }
2066        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2067          pNext(strat->M->m[minimcnt])
2068            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2069                                           strat->tailRing, currRing,
2070                                           currRing->PolyBin);
2071        minimcnt++;
2072      }
2073
2074      // enter into S, L, and T
2075      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2076      enterT(strat->P, strat);
2077      strat->T[strat->tl].is_sigsafe = FALSE;
2078      /*
2079      printf("hier\n");
2080      pWrite(strat->P.GetLmCurrRing());
2081      pWrite(strat->P.sig);
2082      */
2083#ifdef HAVE_RINGS
2084      if (rField_is_Ring(currRing))
2085        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2086      else
2087#endif
2088        enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2089      // posInS only depends on the leading term
2090      strat->enterS(strat->P, pos, strat, strat->tl);
2091      if(strat->sbaOrder != 1)
2092      {
2093        BOOLEAN overwrite = FALSE;
2094        for (int tk=0; tk<strat->sl+1; tk++)
2095        {
2096          if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
2097          {
2098            //printf("TK %d / %d\n",tk,strat->sl);
2099            overwrite = FALSE;
2100            break;
2101          }
2102        }
2103        //printf("OVERWRITE %d\n",overwrite);
2104        if (overwrite)
2105        {
2106          int cmp = pGetComp(strat->P.sig);
2107          int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
2108          pGetExpV (strat->P.p,vv);
2109          pSetExpV (strat->P.sig, vv);
2110          pSetComp (strat->P.sig,cmp);
2111
2112          strat->P.sevSig = pGetShortExpVector (strat->P.sig);
2113          int i;
2114          LObject Q;
2115          for(int ps=0;ps<strat->sl+1;ps++)
2116          {
2117
2118            strat->newt = TRUE;
2119            if (strat->syzl == strat->syzmax)
2120            {
2121              pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
2122              strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
2123                  (strat->syzmax)*sizeof(unsigned long),
2124                  ((strat->syzmax)+setmaxTinc)
2125                  *sizeof(unsigned long));
2126              strat->syzmax += setmaxTinc;
2127            }
2128            Q.sig = pCopy(strat->P.sig);
2129            // add LM(F->m[i]) to the signature to get a Schreyer order
2130            // without changing the underlying polynomial ring at all
2131            if (strat->sbaOrder == 0)
2132              p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
2133            // since p_Add_q() destroys all input
2134            // data we need to recreate help
2135            // each time
2136            // ----------------------------------------------------------
2137            // in the Schreyer order we always know that the multiplied
2138            // module monomial strat->P.sig gives the leading monomial of
2139            // the corresponding principal syzygy
2140            // => we do not need to compute the "real" syzygy completely
2141            poly help = p_Copy(strat->sig[ps],currRing);
2142            p_ExpVectorAdd (help,strat->P.p,currRing);
2143            Q.sig = p_Add_q(Q.sig,help,currRing);
2144            //printf("%d. SYZ  ",i+1);
2145            //pWrite(strat->syz[i]);
2146            Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
2147            i = posInSyz(strat, Q.sig);
2148            enterSyz(Q, strat, i);
2149          }
2150        }
2151      }
2152      // deg - idx - lp/rp
2153      // => we need to add syzygies with indices > pGetComp(strat->P.sig)
2154      if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
2155      {
2156        int cmp     = pGetComp(strat->P.sig);
2157        int max_cmp = IDELEMS(F);
2158        int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
2159        pGetExpV (strat->P.p,vv);
2160        LObject Q;
2161        int pos;
2162        int idx = p_GetComp(strat->P.sig,currRing);
2163        //printf("++ -- adding syzygies -- ++\n");
2164        // if new element is the first one in this index
2165        if (strat->currIdx < idx) {
2166          for (int i=0; i<strat->sl; ++i) {
2167            Q.sig = p_Copy(strat->P.sig,currRing);
2168            p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
2169            poly help = p_Copy(strat->sig[i],currRing);
2170            p_ExpVectorAdd(help,strat->P.p,currRing);
2171            Q.sig = p_Add_q(Q.sig,help,currRing);
2172            //pWrite(Q.sig);
2173            pos = posInSyz(strat, Q.sig);
2174            enterSyz(Q, strat, pos);
2175          }
2176          strat->currIdx = idx;
2177        } else {
2178          // if the element is not the first one in the given index we build all
2179          // possible syzygies with elements of higher index
2180          for (int i=cmp+1; i<=max_cmp; ++i) {
2181            pos = -1;
2182            for (int j=0; j<strat->sl; ++j) {
2183              if (p_GetComp(strat->sig[j],currRing) == i) {
2184                pos = j;
2185                break;
2186              }
2187            }
2188            if (pos != -1) {
2189              Q.sig = p_One(currRing);
2190              p_SetExpV(Q.sig, vv, currRing);
2191              // F->m[i-1] corresponds to index i
2192              p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
2193              p_SetComp(Q.sig, i, currRing);
2194              poly help = p_Copy(strat->P.sig,currRing);
2195              p_ExpVectorAdd(help,strat->S[pos],currRing);
2196              Q.sig = p_Add_q(Q.sig,help,currRing);
2197              if (strat->sbaOrder == 0) {
2198                if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn) {
2199                  pos = posInSyz(strat, Q.sig);
2200                  enterSyz(Q, strat, pos);
2201                }
2202              } else {
2203                pos = posInSyz(strat, Q.sig);
2204                enterSyz(Q, strat, pos);
2205              }
2206            }
2207          }
2208          //printf("++ -- done adding syzygies -- ++\n");
2209        }
2210      }
2211//#if 1
2212#if DEBUGF50
2213    printf("---------------------------\n");
2214    Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
2215    Print("LEAD POLY:  "); pWrite(pHead(strat->S[strat->sl]));
2216    Print("SIGNATURE:  "); pWrite(strat->sig[strat->sl]);
2217#endif
2218      /*
2219      if (newrules)
2220      {
2221        newrules  = FALSE;
2222      }
2223      */
2224#if 0
2225      int pl=pLength(strat->P.p);
2226      if (pl==1)
2227      {
2228        //if (TEST_OPT_PROT)
2229        //PrintS("<1>");
2230      }
2231      else if (pl==2)
2232      {
2233        //if (TEST_OPT_PROT)
2234        //PrintS("<2>");
2235      }
2236#endif
2237      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2238//      Print("[%d]",hilbeledeg);
2239      if (strat->P.lcm!=NULL)
2240#ifdef HAVE_RINGS
2241        pLmDelete(strat->P.lcm);
2242#else
2243        pLmFree(strat->P.lcm);
2244#endif
2245      if (strat->sl>srmax) srmax = strat->sl;
2246    }
2247    else
2248    {
2249      // adds signature of the zero reduction to
2250      // strat->syz. This is the leading term of
2251      // syzygy and can be used in syzCriterion()
2252      // the signature is added if and only if the
2253      // pair was not detected by the rewritten criterion in strat->red = redSig
2254      if (red_result!=2) {
2255#if SBA_PRINT_ZERO_REDUCTIONS
2256        zeroreductions++;
2257#endif
2258        int pos = posInSyz(strat, strat->P.sig);
2259        enterSyz(strat->P, strat, pos);
2260//#if 1
2261#ifdef DEBUGF5
2262        Print("ADDING STUFF TO SYZ :  ");
2263        //pWrite(strat->P.p);
2264        pWrite(strat->P.sig);
2265#endif
2266      }
2267      if (strat->P.p1 == NULL && strat->minim > 0)
2268      {
2269        p_Delete(&strat->P.p2, currRing, strat->tailRing);
2270      }
2271    }
2272
2273#ifdef KDEBUG
2274    memset(&(strat->P), 0, sizeof(strat->P));
2275#endif /* KDEBUG */
2276    kTest_TS(strat);
2277  }
2278#ifdef KDEBUG
2279#if MYTEST
2280  PrintS("bba finish GB: currRing: "); rWrite(currRing);
2281#endif /* MYTEST */
2282  if (TEST_OPT_DEBUG) messageSets(strat);
2283#endif /* KDEBUG */
2284
2285  if (TEST_OPT_SB_1)
2286  {
2287    #ifdef HAVE_RINGS
2288    if(!rField_is_Ring(currRing))
2289    #endif
2290    {
2291        int k=1;
2292        int j;
2293        while(k<=strat->sl)
2294        {
2295          j=0;
2296          loop
2297          {
2298            if (j>=k) break;
2299            clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2300            j++;
2301          }
2302          k++;
2303        }
2304    }
2305  }
2306
2307  /* complete reduction of the standard basis--------- */
2308  if (TEST_OPT_REDSB)
2309  {
2310    completeReduce(strat);
2311#ifdef HAVE_TAIL_RING
2312    if (strat->completeReduce_retry)
2313    {
2314      // completeReduce needed larger exponents, retry
2315      // to reduce with S (instead of T)
2316      // and in currRing (instead of strat->tailRing)
2317      cleanT(strat);strat->tailRing=currRing;
2318      int i;
2319      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2320      completeReduce(strat);
2321    }
2322#endif
2323  }
2324  else if (TEST_OPT_PROT) PrintLn();
2325
2326#if SBA_PRINT_SIZE_SYZ
2327  // that is correct, syzl is counting one too far
2328  size_syz = strat->syzl;
2329#endif
2330  exitSba(strat);
2331//  if (TEST_OPT_WEIGHTM)
2332//  {
2333//    pRestoreDegProcs(pFDegOld, pLDegOld);
2334//    if (ecartWeights)
2335//    {
2336//      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
2337//      ecartWeights=NULL;
2338//    }
2339//  }
2340  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
2341  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2342
2343#ifdef KDEBUG
2344#if MYTEST
2345  PrintS("bba_end: currRing: "); rWrite(currRing);
2346#endif /* MYTEST */
2347#endif /* KDEBUG */
2348#if SBA_PRINT_SIZE_G
2349  size_g_non_red  = IDELEMS(strat->Shdl);
2350#endif
2351  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
2352  {
2353    rChangeCurrRing (currRingOld);
2354    F0          = idrMoveR (F1, sRing, currRing);
2355    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
2356    rDelete (sRing);
2357  }
2358  id_DelDiv(strat->Shdl, currRing);
2359  idSkipZeroes(strat->Shdl);
2360  idTest(strat->Shdl);
2361
2362#if SBA_PRINT_SIZE_G
2363  size_g   = IDELEMS(strat->Shdl);
2364#endif
2365#ifdef DEBUGF5
2366  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
2367  int oo = 0;
2368  while (oo<IDELEMS(strat->Shdl))
2369  {
2370    printf(" %d.   ",oo+1);
2371    pWrite(pHead(strat->Shdl->m[oo]));
2372    oo++;
2373  }
2374#endif
2375#if SBA_PRINT_ZERO_REDUCTIONS
2376  printf("----------------------------------------------------------\n");
2377  printf("ZERO REDUCTIONS:            %ld\n",zeroreductions);
2378  zeroreductions  = 0;
2379#endif
2380#if SBA_PRINT_REDUCTION_STEPS
2381  printf("----------------------------------------------------------\n");
2382  printf("S-REDUCTIONS:               %ld\n",sba_reduction_steps);
2383#endif
2384#if SBA_PRINT_OPERATIONS
2385  printf("OPERATIONS:                 %ld\n",sba_operations);
2386#endif
2387#if SBA_PRINT_REDUCTION_STEPS
2388  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
2389  printf("INTERREDUCTIONS:            %ld\n",sba_interreduction_steps);
2390#endif
2391#if SBA_PRINT_OPERATIONS
2392  printf("INTERREDUCTION OPERATIONS:  %ld\n",sba_interreduction_operations);
2393#endif
2394#if SBA_PRINT_REDUCTION_STEPS
2395  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
2396  printf("ALL REDUCTIONS:             %ld\n",sba_reduction_steps+sba_interreduction_steps);
2397  sba_interreduction_steps  = 0;
2398  sba_reduction_steps       = 0;
2399#endif
2400#if SBA_PRINT_OPERATIONS
2401  printf("ALL OPERATIONS:             %ld\n",sba_operations+sba_interreduction_operations);
2402  sba_interreduction_operations = 0;
2403  sba_operations                = 0;
2404#endif
2405#if SBA_PRINT_SIZE_G
2406  printf("----------------------------------------------------------\n");
2407  printf("SIZE OF G:                  %d / %d\n",size_g,size_g_non_red);
2408  size_g          = 0;
2409  size_g_non_red  = 0;
2410#endif
2411#if SBA_PRINT_SIZE_SYZ
2412  printf("SIZE OF SYZ:                %ld\n",size_syz);
2413  printf("----------------------------------------------------------\n");
2414  size_syz  = 0;
2415#endif
2416#if SBA_PRINT_PRODUCT_CRITERION
2417  printf("PRODUCT CRITERIA:           %ld\n",product_criterion);
2418  product_criterion = 0;
2419#endif
2420  return (strat->Shdl);
2421}
2422
2423poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
2424{
2425  assume(q!=NULL);
2426  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
2427
2428// lazy_reduce flags: can be combined by |
2429//#define KSTD_NF_LAZY   1
2430  // do only a reduction of the leading term
2431//#define KSTD_NF_NONORM 4
2432  // only global: avoid normalization, return a multiply of NF
2433  poly   p;
2434
2435  //if ((idIs0(F))&&(Q==NULL))
2436  //  return pCopy(q); /*F=0*/
2437  //strat->ak = idRankFreeModule(F);
2438  /*- creating temp data structures------------------- -*/
2439  BITSET save1;
2440  SI_SAVE_OPT1(save1);
2441  si_opt_1|=Sy_bit(OPT_REDTAIL);
2442  initBuchMoraCrit(strat);
2443  strat->initEcart = initEcartBBA;
2444  strat->enterS = enterSBba;
2445#ifndef NO_BUCKETS
2446  strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
2447#endif
2448  /*- set S -*/
2449  strat->sl = -1;
2450  /*- init local data struct.---------------------------------------- -*/
2451  /*Shdl=*/initS(F,Q,strat);
2452  /*- compute------------------------------------------------------- -*/
2453  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
2454  //{
2455  //  for (i=strat->sl;i>=0;i--)
2456  //    pNorm(strat->S[i]);
2457  //}
2458  kTest(strat);
2459  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2460  if (BVERBOSE(23)) kDebugPrint(strat);
2461  int max_ind;
2462  p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
2463  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2464  {
2465    if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2466    #ifdef HAVE_RINGS
2467    if (rField_is_Ring(currRing))
2468    {
2469      p = redtailBba_Z(p,max_ind,strat);
2470    }
2471    else
2472    #endif
2473    {
2474      si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
2475      p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
2476    }
2477  }
2478  /*- release temp data------------------------------- -*/
2479  assume(strat->L==NULL); /* strat->L unused */
2480  assume(strat->B==NULL); /* strat->B unused */
2481  omFree(strat->sevS);
2482  omFree(strat->ecartS);
2483  assume(strat->T==NULL);//omfree(strat->T);
2484  assume(strat->sevT==NULL);//omfree(strat->sevT);
2485  assume(strat->R==NULL);//omfree(strat->R);
2486  omfree(strat->S_2_R);
2487  omfree(strat->fromQ);
2488  idDelete(&strat->Shdl);
2489  SI_RESTORE_OPT1(save1);
2490  if (TEST_OPT_PROT) PrintLn();
2491  return p;
2492}
2493
2494ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
2495{
2496  assume(!idIs0(q));
2497  assume(!(idIs0(F)&&(Q==NULL)));
2498// lazy_reduce flags: can be combined by |
2499//#define KSTD_NF_LAZY   1
2500  // do only a reduction of the leading term
2501//#define KSTD_NF_NONORM 4
2502  // only global: avoid normalization, return a multiply of NF
2503  poly   p;
2504  int   i;
2505  ideal res;
2506  int max_ind;
2507
2508  //if (idIs0(q))
2509  //  return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2510  //if ((idIs0(F))&&(Q==NULL))
2511  //  return idCopy(q); /*F=0*/
2512  //strat->ak = idRankFreeModule(F);
2513  /*- creating temp data structures------------------- -*/
2514  BITSET save1;
2515  SI_SAVE_OPT1(save1);
2516  si_opt_1|=Sy_bit(OPT_REDTAIL);
2517  initBuchMoraCrit(strat);
2518  strat->initEcart = initEcartBBA;
2519  strat->enterS = enterSBba;
2520  /*- set S -*/
2521  strat->sl = -1;
2522#ifndef NO_BUCKETS
2523  strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
2524#endif
2525  /*- init local data struct.---------------------------------------- -*/
2526  /*Shdl=*/initS(F,Q,strat);
2527  /*- compute------------------------------------------------------- -*/
2528  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
2529  si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
2530  for (i=IDELEMS(q)-1; i>=0; i--)
2531  {
2532    if (q->m[i]!=NULL)
2533    {
2534      if (TEST_OPT_PROT) { PrintS("r");mflush(); }
2535      p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
2536      if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2537      {
2538        if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2539        #ifdef HAVE_RINGS
2540        if (rField_is_Ring(currRing))
2541        {
2542          p = redtailBba_Z(p,max_ind,strat);
2543        }
2544        else
2545        #endif
2546        {
2547          p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
2548        }
2549      }
2550      res->m[i]=p;
2551    }
2552    //else
2553    //  res->m[i]=NULL;
2554  }
2555  /*- release temp data------------------------------- -*/
2556  assume(strat->L==NULL); /* strat->L unused */
2557  assume(strat->B==NULL); /* strat->B unused */
2558  omFree(strat->sevS);
2559  omFree(strat->ecartS);
2560  assume(strat->T==NULL);//omfree(strat->T);
2561  assume(strat->sevT==NULL);//omfree(strat->sevT);
2562  assume(strat->R==NULL);//omfree(strat->R);
2563  omfree(strat->S_2_R);
2564  omfree(strat->fromQ);
2565  idDelete(&strat->Shdl);
2566  SI_RESTORE_OPT1(save1);
2567  if (TEST_OPT_PROT) PrintLn();
2568  return res;
2569}
2570
2571#if F5C
2572/*********************************************************************
2573* interrreduction step of the signature-based algorithm:
2574* 1. all strat->S are interpreted as new critical pairs
2575* 2. those pairs need to be completely reduced by the usual (non sig-
2576*    safe) reduction process (including tail reductions)
2577* 3. strat->S and strat->T are completely new computed in these steps
2578********************************************************************/
2579void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
2580          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
2581          intvec *w,intvec *hilb )
2582{
2583  int Ll_old, red_result = 1;
2584  int pos  = 0;
2585  hilbeledeg=1;
2586  hilbcount=0;
2587  minimcnt=0;
2588  srmax = 0; // strat->sl is 0 at this point
2589  reduc = olddeg = lrmax = 0;
2590  // we cannot use strat->T anymore
2591  //cleanT(strat);
2592  //strat->tl = -1;
2593  Ll_old    = strat->Ll;
2594  while (strat->tl >= 0)
2595  {
2596    if(!strat->T[strat->tl].is_redundant)
2597    {
2598      LObject h;
2599      h.p = strat->T[strat->tl].p;
2600      h.tailRing = strat->T[strat->tl].tailRing;
2601      h.t_p = strat->T[strat->tl].t_p;
2602      if (h.p!=NULL)
2603      {
2604        if (currRing->OrdSgn==-1)
2605        {
2606          cancelunit(&h);
2607          deleteHC(&h, strat);
2608        }
2609        if (h.p!=NULL)
2610        {
2611          if (TEST_OPT_INTSTRATEGY)
2612          {
2613            //pContent(h.p);
2614            h.pCleardenom(); // also does a pContent
2615          }
2616          else
2617          {
2618            h.pNorm();
2619          }
2620          strat->initEcart(&h);
2621          pos = strat->Ll+1;
2622          h.sev = pGetShortExpVector(h.p);
2623          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
2624        }
2625      }
2626    }
2627    strat->tl--;
2628  }
2629  strat->sl = -1;
2630#if 0
2631//#ifdef HAVE_TAIL_RING
2632  if(!rField_is_Ring())  // create strong gcd poly computes with tailring and S[i] ->to be fixed
2633    kStratInitChangeTailRing(strat);
2634#endif
2635  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
2636  //strat->sl = -1;
2637  /* picks the last element from the lazyset L */
2638  while (strat->Ll>Ll_old)
2639  {
2640    strat->P = strat->L[strat->Ll];
2641    strat->Ll--;
2642//#if 1
2643#ifdef DEBUGF5
2644    Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
2645    Print("-------------------------------------------------\n");
2646    pWrite(pHead(strat->P.p));
2647    pWrite(pHead(strat->P.p1));
2648    pWrite(pHead(strat->P.p2));
2649    printf("%d\n",strat->tl);
2650    Print("-------------------------------------------------\n");
2651#endif
2652    if (pNext(strat->P.p) == strat->tail)
2653    {
2654      // deletes the short spoly
2655#ifdef HAVE_RINGS
2656      if (rField_is_Ring(currRing))
2657        pLmDelete(strat->P.p);
2658      else
2659#endif
2660        pLmFree(strat->P.p);
2661
2662      // TODO: needs some masking
2663      // TODO: masking needs to vanish once the signature
2664      //       sutff is completely implemented
2665      strat->P.p = NULL;
2666      poly m1 = NULL, m2 = NULL;
2667
2668      // check that spoly creation is ok
2669      while (strat->tailRing != currRing &&
2670          !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2671      {
2672        assume(m1 == NULL && m2 == NULL);
2673        // if not, change to a ring where exponents are at least
2674        // large enough
2675        if (!kStratChangeTailRing(strat))
2676        {
2677          WerrorS("OVERFLOW...");
2678          break;
2679        }
2680      }
2681      // create the real one
2682      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2683          strat->tailRing, m1, m2, strat->R);
2684    }
2685    else if (strat->P.p1 == NULL)
2686    {
2687      if (strat->minim > 0)
2688        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2689      // for input polys, prepare reduction
2690      strat->P.PrepareRed(strat->use_buckets);
2691    }
2692
2693    if (strat->P.p == NULL && strat->P.t_p == NULL)
2694    {
2695      red_result = 0;
2696    }
2697    else
2698    {
2699      if (TEST_OPT_PROT)
2700        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2701            &olddeg,&reduc,strat, red_result);
2702
2703#ifdef DEBUGF5
2704      Print("Poly before red: ");
2705      pWrite(strat->P.p);
2706#endif
2707      /* complete reduction of the element chosen from L */
2708      red_result = strat->red2(&strat->P,strat);
2709      if (errorreported)  break;
2710    }
2711
2712    if (strat->overflow)
2713    {
2714      if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
2715    }
2716
2717    // reduction to non-zero new poly
2718    if (red_result == 1)
2719    {
2720      // get the polynomial (canonicalize bucket, make sure P.p is set)
2721      strat->P.GetP(strat->lmBin);
2722      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2723      // but now, for entering S, T, we reset it
2724      // in the inhomogeneous case: FDeg == pFDeg
2725      if (strat->homog) strat->initEcart(&(strat->P));
2726
2727      /* statistic */
2728      if (TEST_OPT_PROT) PrintS("s");
2729
2730      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2731
2732#ifdef KDEBUG
2733#if MYTEST
2734      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
2735#endif /* MYTEST */
2736#endif /* KDEBUG */
2737
2738      // reduce the tail and normalize poly
2739      // in the ring case we cannot expect LC(f) = 1,
2740      // therefore we call pContent instead of pNorm
2741#if F5CTAILRED
2742      BOOLEAN withT = TRUE;
2743      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
2744      {
2745        strat->P.pCleardenom();
2746        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2747        {
2748          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2749          strat->P.pCleardenom();
2750        }
2751      }
2752      else
2753      {
2754        strat->P.pNorm();
2755        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2756          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2757      }
2758#endif
2759#ifdef KDEBUG
2760      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2761#if MYTEST
2762//#if 1
2763      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
2764#endif /* MYTEST */
2765#endif /* KDEBUG */
2766
2767      // min_std stuff
2768      if ((strat->P.p1==NULL) && (strat->minim>0))
2769      {
2770        if (strat->minim==1)
2771        {
2772          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2773          p_Delete(&strat->P.p2, currRing, strat->tailRing);
2774        }
2775        else
2776        {
2777          strat->M->m[minimcnt]=strat->P.p2;
2778          strat->P.p2=NULL;
2779        }
2780        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2781          pNext(strat->M->m[minimcnt])
2782            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2783                strat->tailRing, currRing,
2784                currRing->PolyBin);
2785        minimcnt++;
2786      }
2787
2788      // enter into S, L, and T
2789      // here we need to recompute new signatures, but those are trivial ones
2790      if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2791      {
2792        enterT(strat->P, strat);
2793        // posInS only depends on the leading term
2794        strat->enterS(strat->P, pos, strat, strat->tl);
2795//#if 1
2796#ifdef DEBUGF5
2797        Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
2798        pWrite(pHead(strat->S[strat->sl]));
2799        pWrite(strat->sig[strat->sl]);
2800#endif
2801        if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2802      }
2803      //      Print("[%d]",hilbeledeg);
2804      if (strat->P.lcm!=NULL)
2805#ifdef HAVE_RINGS
2806        pLmDelete(strat->P.lcm);
2807#else
2808      pLmFree(strat->P.lcm);
2809#endif
2810      if (strat->sl>srmax) srmax = strat->sl;
2811    }
2812    else
2813    {
2814      // adds signature of the zero reduction to
2815      // strat->syz. This is the leading term of
2816      // syzygy and can be used in syzCriterion()
2817      // the signature is added if and only if the
2818      // pair was not detected by the rewritten criterion in strat->red = redSig
2819      if (strat->P.p1 == NULL && strat->minim > 0)
2820      {
2821        p_Delete(&strat->P.p2, currRing, strat->tailRing);
2822      }
2823    }
2824
2825#ifdef KDEBUG
2826    memset(&(strat->P), 0, sizeof(strat->P));
2827#endif /* KDEBUG */
2828  }
2829  int cc = 0;
2830  while (cc<strat->tl+1)
2831  {
2832    strat->T[cc].sig        = pOne();
2833    p_SetComp(strat->T[cc].sig,cc+1,currRing);
2834    strat->T[cc].sevSig     = pGetShortExpVector(strat->T[cc].sig);
2835    strat->sig[cc]          = strat->T[cc].sig;
2836    strat->sevSig[cc]       = strat->T[cc].sevSig;
2837    strat->T[cc].is_sigsafe = TRUE;
2838    cc++;
2839  }
2840  strat->max_lower_index = strat->tl;
2841  // set current signature index of upcoming iteration step
2842  // NOTE:  this needs to be set here, as otherwise initSyzRules cannot compute
2843  //        the corresponding syzygy rules correctly
2844  strat->currIdx = cc+1;
2845  for (int cd=strat->Ll; cd>=0; cd--)
2846  {
2847    p_SetComp(strat->L[cd].sig,cc+1,currRing);
2848    cc++;
2849  }
2850  for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
2851    strat->Shdl->m[cc]  = NULL;
2852//#if 1
2853#if DEBUGF5
2854  Print("------------------- STRAT S ---------------------\n");
2855  cc = 0;
2856  while (cc<strat->tl+1)
2857  {
2858    pWrite(pHead(strat->S[cc]));
2859    pWrite(strat->sig[cc]);
2860    printf("- - - - - -\n");
2861    cc++;
2862  }
2863  Print("-------------------------------------------------\n");
2864  Print("------------------- STRAT T ---------------------\n");
2865  cc = 0;
2866  while (cc<strat->tl+1)
2867  {
2868    pWrite(pHead(strat->T[cc].p));
2869    pWrite(strat->T[cc].sig);
2870    printf("- - - - - -\n");
2871    cc++;
2872  }
2873  Print("-------------------------------------------------\n");
2874  Print("------------------- STRAT L ---------------------\n");
2875  cc = 0;
2876  while (cc<strat->Ll+1)
2877  {
2878    pWrite(pHead(strat->L[cc].p));
2879    pWrite(pHead(strat->L[cc].p1));
2880    pWrite(pHead(strat->L[cc].p2));
2881    pWrite(strat->L[cc].sig);
2882    printf("- - - - - -\n");
2883    cc++;
2884  }
2885  Print("-------------------------------------------------\n");
2886  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
2887#endif
2888
2889}
2890#endif
2891
2892/* shiftgb stuff */
2893#ifdef HAVE_SHIFTBBA
2894
2895
2896ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV)
2897{
2898  int   red_result = 1;
2899  int   olddeg,reduc;
2900  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2901  BOOLEAN withT = TRUE; // very important for shifts
2902
2903  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit, NO CHANGES */
2904  initBuchMoraPos(strat); /*NO CHANGES YET: perhaps later*/
2905  initHilbCrit(F,Q,&hilb,strat); /*NO CHANGES*/
2906  initBbaShift(F,strat); /* DONE */
2907  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2908  /*Shdl=*/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
2909  updateSShift(strat,uptodeg,lV); /* initializes T */
2910
2911  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2912  reduc = olddeg = 0;
2913  strat->lV=lV;
2914
2915#ifndef NO_BUCKETS
2916  if (!TEST_OPT_NOT_BUCKETS)
2917    strat->use_buckets = 1;
2918#endif
2919
2920  // redtailBBa against T for inhomogenous input
2921  //  if (!TEST_OPT_OLDSTD)
2922  //    withT = ! strat->homog;
2923
2924  // strat->posInT = posInT_pLength;
2925  kTest_TS(strat);
2926
2927#ifdef HAVE_TAIL_RING
2928  kStratInitChangeTailRing(strat);
2929#endif
2930
2931  /* compute------------------------------------------------------- */
2932  while (strat->Ll >= 0)
2933  {
2934#ifdef KDEBUG
2935    if (TEST_OPT_DEBUG) messageSets(strat);
2936#endif
2937    if (strat->Ll== 0) strat->interpt=TRUE;
2938    if (TEST_OPT_DEGBOUND
2939        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2940            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2941    {
2942      /*
2943       *stops computation if
2944       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2945       *a predefined number Kstd1_deg
2946       */
2947      while ((strat->Ll >= 0)
2948        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2949        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2950            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2951        )
2952        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2953      if (strat->Ll<0) break;
2954      else strat->noClearS=TRUE;
2955    }
2956    /* picks the last element from the lazyset L */
2957    strat->P = strat->L[strat->Ll];
2958    strat->Ll--;
2959
2960    if (pNext(strat->P.p) == strat->tail)
2961    {
2962      // deletes the short spoly
2963      pLmFree(strat->P.p);
2964      strat->P.p = NULL;
2965      poly m1 = NULL, m2 = NULL;
2966
2967      // check that spoly creation is ok
2968      while (strat->tailRing != currRing &&
2969             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2970      {
2971        assume(m1 == NULL && m2 == NULL);
2972        // if not, change to a ring where exponents are at least
2973        // large enough
2974        kStratChangeTailRing(strat);
2975      }
2976      // create the real one
2977      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2978                    strat->tailRing, m1, m2, strat->R);
2979    }
2980    else if (strat->P.p1 == NULL)
2981    {
2982      if (strat->minim > 0)
2983        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2984      // for input polys, prepare reduction
2985      strat->P.PrepareRed(strat->use_buckets);
2986    }
2987
2988    poly qq;
2989
2990    /* here in the nonhomog case we shrink the new spoly */
2991
2992    if ( ! strat->homog)
2993    {
2994      strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
2995      /* in the nonhomog case we have to shrink the polynomial */
2996      assume(strat->P.t_p!=NULL);
2997      qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
2998      if (qq != NULL)
2999      {
3000         /* we're here if Shrink is nonzero */
3001        //         strat->P.p =  NULL;
3002        //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3003        strat->P.p   =  NULL; // is not set by Delete
3004        strat->P.t_p =  qq;
3005        strat->P.GetP(strat->lmBin);
3006        // update sev and length
3007        strat->initEcart(&(strat->P));
3008        strat->P.sev = pGetShortExpVector(strat->P.p);
3009//         strat->P.FDeg = strat->P.pFDeg();
3010//         strat->P.length = strat->P.pLDeg();
3011//         strat->P.pLength =strat->P.GetpLength(); //pLength(strat->P.p);
3012      }
3013      else
3014      {
3015         /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
3016#ifdef KDEBUG
3017         if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3018#endif
3019         //         strat->P.Delete();  // cause error
3020         strat->P.p = NULL;
3021         strat->P.t_p = NULL;
3022           //         strat->P.p = NULL; // or delete strat->P.p ?
3023       }
3024    }
3025      /* end shrinking poly in the nonhomog case */
3026
3027    if (strat->P.p == NULL && strat->P.t_p == NULL)
3028    {
3029      red_result = 0;
3030    }
3031    else
3032    {
3033      if (TEST_OPT_PROT)
3034        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3035                &olddeg,&reduc,strat, red_result);
3036
3037      /* reduction of the element chosen from L */
3038      red_result = strat->red(&strat->P,strat);
3039    }
3040
3041    // reduction to non-zero new poly
3042    if (red_result == 1)
3043    {
3044      /* statistic */
3045      if (TEST_OPT_PROT) PrintS("s");
3046
3047      // get the polynomial (canonicalize bucket, make sure P.p is set)
3048      strat->P.GetP(strat->lmBin);
3049
3050      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3051
3052      // reduce the tail and normalize poly
3053      if (TEST_OPT_INTSTRATEGY)
3054      {
3055        strat->P.pCleardenom();
3056        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3057        {
3058          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3059          strat->P.pCleardenom();
3060        }
3061      }
3062      else
3063      {
3064        strat->P.pNorm();
3065        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3066          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3067      }
3068
3069      // here we must shrink again! and optionally reduce again
3070      // or build shrink into redtailBba!
3071
3072#ifdef KDEBUG
3073      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3074#endif
3075
3076      // min_std stuff
3077      if ((strat->P.p1==NULL) && (strat->minim>0))
3078      {
3079        if (strat->minim==1)
3080        {
3081          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3082          p_Delete(&strat->P.p2, currRing, strat->tailRing);
3083        }
3084        else
3085        {
3086          strat->M->m[minimcnt]=strat->P.p2;
3087          strat->P.p2=NULL;
3088        }
3089        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3090          pNext(strat->M->m[minimcnt])
3091            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3092                                           strat->tailRing, currRing,
3093                                           currRing->PolyBin);
3094        minimcnt++;
3095      }
3096
3097    /* here in the nonhomog case we shrink the reduced poly AGAIN */
3098
3099    if ( ! strat->homog)
3100    {
3101      strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3102      /* assume strat->P.t_p != NULL */
3103      /* in the nonhomog case we have to shrink the polynomial */
3104      assume(strat->P.t_p!=NULL); // poly qq defined above
3105      qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
3106      if (qq != NULL)
3107      {
3108         /* we're here if Shrink is nonzero */
3109        //         strat->P.p =  NULL;
3110        //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3111        strat->P.p   =  NULL; // is not set by Delete
3112        strat->P.t_p =  qq;
3113        strat->P.GetP(strat->lmBin);
3114        // update sev and length
3115        strat->initEcart(&(strat->P));
3116        strat->P.sev = pGetShortExpVector(strat->P.p);
3117      }
3118      else
3119      {
3120         /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
3121#ifdef PDEBUG
3122         if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3123#endif
3124         //         strat->P.Delete();  // cause error
3125         strat->P.p = NULL;
3126         strat->P.t_p = NULL;
3127           //         strat->P.p = NULL; // or delete strat->P.p ?
3128         goto     red_shrink2zero;
3129       }
3130    }
3131      /* end shrinking poly AGAIN in the nonhomog case */
3132
3133
3134      // enter into S, L, and T
3135      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3136      //        enterT(strat->P, strat); // this was here before Shift stuff
3137      //enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax
3138      // the default value for atT = -1 as in bba
3139      /*   strat->P.GetP(); */
3140      // because shifts are counted with .p structure // done before, but ?
3141      enterTShift(strat->P,strat,-1,uptodeg, lV);
3142      enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3143      //      enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3144      // posInS only depends on the leading term
3145      strat->enterS(strat->P, pos, strat, strat->tl);
3146
3147      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3148//      Print("[%d]",hilbeledeg);
3149      if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
3150    }
3151    else
3152    {
3153    red_shrink2zero:
3154      if (strat->P.p1 == NULL && strat->minim > 0)
3155      {
3156        p_Delete(&strat->P.p2, currRing, strat->tailRing);
3157      }
3158    }
3159#ifdef KDEBUG
3160    memset(&(strat->P), 0, sizeof(strat->P));
3161#endif
3162    kTest_TS(strat);
3163  }
3164#ifdef KDEBUG
3165  if (TEST_OPT_DEBUG) messageSets(strat);
3166#endif
3167  /* complete reduction of the standard basis--------- */
3168  /*  shift case: look for elt's in S such that they are divisible by elt in T */
3169  //  if (TEST_OPT_SB_1)
3170  if (TEST_OPT_REDSB)
3171  {
3172    int k=0;
3173    int j=-1;
3174    while(k<=strat->sl)
3175    {
3176//       loop
3177//       {
3178//         if (j>=k) break;
3179//         clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3180//         j++;
3181//       }
3182      LObject Ln (strat->S[k],currRing, strat->tailRing);
3183      Ln.SetShortExpVector();
3184      j = kFindDivisibleByInT(strat, &Ln, j+1);
3185      if (j<0) {  k++; j=-1;}
3186      else
3187      {
3188        if ( pLmCmp(strat->S[k],strat->T[j].p) == 0)
3189        {
3190          j = kFindDivisibleByInT(strat, &Ln, j+1);
3191          if (j<0) {  k++; j=-1;}
3192          else
3193          {
3194            deleteInS(k,strat);
3195          }
3196        }
3197        else
3198        {
3199          deleteInS(k,strat);
3200        }
3201      }
3202    }
3203  }
3204
3205  if (TEST_OPT_REDSB)
3206  {    completeReduce(strat, TRUE); //shift: withT = TRUE
3207    if (strat->completeReduce_retry)
3208    {
3209      // completeReduce needed larger exponents, retry
3210      // to reduce with S (instead of T)
3211      // and in currRing (instead of strat->tailRing)
3212      cleanT(strat);strat->tailRing=currRing;
3213      int i;
3214      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3215      completeReduce(strat, TRUE);
3216    }
3217  }
3218  else if (TEST_OPT_PROT) PrintLn();
3219
3220  /* release temp data-------------------------------- */
3221  exitBuchMora(strat);
3222//  if (TEST_OPT_WEIGHTM)
3223//  {
3224//    pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
3225//    if (ecartWeights)
3226//    {
3227//      omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3228//      ecartWeights=NULL;
3229//    }
3230//  }
3231  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
3232  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3233  return (strat->Shdl);
3234}
3235
3236
3237ideal freegb(ideal I, int uptodeg, int lVblock)
3238{
3239  /* todo main call */
3240
3241  /* assume: ring is prepared, ideal is copied into shifted ring */
3242  /* uptodeg and lVblock are correct - test them! */
3243
3244  /* check whether the ideal is in V */
3245
3246//  if (0)
3247  if (! ideal_isInV(I,lVblock) )
3248  {
3249    WerrorS("The input ideal contains incorrectly encoded elements! ");
3250    return(NULL);
3251  }
3252
3253  //  kStrategy strat = new skStrategy;
3254  /* ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV) */
3255  /* at the moment:
3256- no quotient (check)
3257- no *w, no *hilb
3258  */
3259  /* ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
3260     int newIdeal, intvec *vw) */
3261  ideal RS = kStdShift(I,NULL, testHomog, NULL,NULL,0,0,NULL, uptodeg, lVblock);
3262    //bbaShift(I,NULL, NULL, NULL, strat, uptodeg, lVblock);
3263  idSkipZeroes(RS);
3264  return(RS);
3265}
3266
3267/*2
3268*reduces h with elements from T choosing  the first possible
3269* element in t with respect to the given pDivisibleBy
3270*/
3271int redFirstShift (LObject* h,kStrategy strat)
3272{
3273  if (h->IsNull()) return 0;
3274
3275  int at, reddeg,d;
3276  int pass = 0;
3277  int j = 0;
3278
3279  if (! strat->homog)
3280  {
3281    d = h->GetpFDeg() + h->ecart;
3282    reddeg = strat->LazyDegree+d;
3283  }
3284  h->SetShortExpVector();
3285  loop
3286  {
3287    j = kFindDivisibleByInT(strat, h);
3288    if (j < 0)
3289    {
3290      h->SetDegStuffReturnLDeg(strat->LDegLast);
3291      return 1;
3292    }
3293
3294    if (!TEST_OPT_INTSTRATEGY)
3295      strat->T[j].pNorm();
3296#ifdef KDEBUG
3297    if (TEST_OPT_DEBUG)
3298    {
3299      PrintS("reduce ");
3300      h->wrp();
3301      PrintS(" with ");
3302      strat->T[j].wrp();
3303    }
3304#endif
3305    ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
3306    if (!h->IsNull())
3307    {
3308      poly qq=p_Shrink(h->GetTP(),strat->lV,strat->tailRing);
3309      h->p=NULL;
3310      h->t_p=qq;
3311      if (qq!=NULL) h->GetP(strat->lmBin);
3312    }
3313
3314#ifdef KDEBUG
3315    if (TEST_OPT_DEBUG)
3316    {
3317      PrintS(" to ");
3318      wrp(h->p);
3319      PrintLn();
3320    }
3321#endif
3322    if (h->IsNull())
3323    {
3324      if (h->lcm!=NULL) pLmFree(h->lcm);
3325      h->Clear();
3326      return 0;
3327    }
3328    h->SetShortExpVector();
3329
3330#if 0
3331    if ((strat->syzComp!=0) && !strat->honey)
3332    {
3333      if ((strat->syzComp>0) &&
3334          (h->Comp() > strat->syzComp))
3335      {
3336        assume(h->MinComp() > strat->syzComp);
3337#ifdef KDEBUG
3338        if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
3339#endif
3340        if (strat->homog)
3341          h->SetDegStuffReturnLDeg(strat->LDegLast);
3342        return -2;
3343      }
3344    }
3345#endif
3346    if (!strat->homog)
3347    {
3348      if (!TEST_OPT_OLDSTD && strat->honey)
3349      {
3350        h->SetpFDeg();
3351        if (strat->T[j].ecart <= h->ecart)
3352          h->ecart = d - h->GetpFDeg();
3353        else
3354          h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
3355
3356        d = h->GetpFDeg() + h->ecart;
3357      }
3358      else
3359        d = h->SetDegStuffReturnLDeg(strat->LDegLast);
3360      /*- try to reduce the s-polynomial -*/
3361      pass++;
3362      /*
3363       *test whether the polynomial should go to the lazyset L
3364       *-if the degree jumps
3365       *-if the number of pre-defined reductions jumps
3366       */
3367      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
3368          && ((d >= reddeg) || (pass > strat->LazyPass)))
3369      {
3370        h->SetLmCurrRing();
3371        if (strat->posInLDependsOnLength)
3372          h->SetLength(strat->length_pLength);
3373        at = strat->posInL(strat->L,strat->Ll,h,strat);
3374        if (at <= strat->Ll)
3375        {
3376          //int dummy=strat->sl;
3377          /*          if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
3378          //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
3379          if (kFindDivisibleByInT(strat, h) < 0)
3380            return 1;
3381          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
3382#ifdef KDEBUG
3383          if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
3384#endif
3385          h->Clear();
3386          return -1;
3387        }
3388      }
3389      if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
3390      {
3391        reddeg = d+1;
3392        Print(".%d",d);mflush();
3393      }
3394    }
3395  }
3396}
3397
3398void initBbaShift(ideal /*F*/,kStrategy strat)
3399{
3400 /* setting global variables ------------------- */
3401  strat->enterS = enterSBba; /* remains as is, we change enterT! */
3402
3403  strat->red = redFirstShift; /* no redHomog ! */
3404
3405  if (currRing->pLexOrder && strat->honey)
3406    strat->initEcart = initEcartNormal;
3407  else
3408    strat->initEcart = initEcartBBA;
3409  if (strat->honey)
3410    strat->initEcartPair = initEcartPairMora;
3411  else
3412    strat->initEcartPair = initEcartPairBba;
3413//  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
3414//  {
3415//    //interred  machen   Aenderung
3416//    pFDegOld=currRing->pFDeg;
3417//    pLDegOld=pLDeg;
3418//    //h=ggetid("ecart");
3419//    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
3420//    //{
3421//    //  ecartWeights=iv2array(IDINTVEC(h));
3422//    //}
3423//    //else
3424//    {
3425//      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
3426//      /*uses automatic computation of the ecartWeights to set them*/
3427//      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights,currRing);
3428//    }
3429//    pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
3430//    if (TEST_OPT_PROT)
3431//    {
3432//      for(int i=1; i<=rVar(currRing); i++)
3433//        Print(" %d",ecartWeights[i]);
3434//      PrintLn();
3435//      mflush();
3436//    }
3437//  }
3438}
3439#endif
Note: See TracBrowser for help on using the repository browser.