source: git/kernel/kstd2.cc @ 576f5b

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