source: git/kernel/kstd2.cc @ fbc7cb

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