source: git/kernel/GBEngine/kstd2.cc @ 24bc73

spielwiese
Last change on this file since 24bc73 was 24bc73, checked in by Hans Schoenemann <hannes@…>, 6 years ago
remove pContent/p_Content from GBEmgine and related p1
  • Property mode set to 100644
File size: 126.4 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/*
5*  ABSTRACT -  Kernel: alg. of Buchberger
6*/
7
8// #define PDEBUG 2
9
10#include "kernel/mod2.h"
11
12//#define ADIDEBUG 1
13#define GCD_SBA 1
14
15// define if no buckets should be used
16// #define NO_BUCKETS
17
18#ifdef HAVE_PLURAL
19#define PLURAL_INTERNAL_DECLARATIONS 1
20#endif
21
22/***********************************************
23 * SBA stuff -- start
24***********************************************/
25#define DEBUGF50  0
26#define DEBUGF51  0
27
28#ifdef DEBUGF5
29#undef DEBUGF5
30//#define DEBUGF5 1
31#endif
32
33#define F5C       1
34#if F5C
35  #define F5CTAILRED 1
36#endif
37
38#define SBA_INTERRED_START                  0
39#define SBA_TAIL_RED                        1
40#define SBA_PRODUCT_CRITERION               0
41#define SBA_PRINT_ZERO_REDUCTIONS           0
42#define SBA_PRINT_REDUCTION_STEPS           0
43#define SBA_PRINT_OPERATIONS                0
44#define SBA_PRINT_SIZE_G                    0
45#define SBA_PRINT_SIZE_SYZ                  0
46#define SBA_PRINT_PRODUCT_CRITERION         0
47
48// counts sba's reduction steps
49#if SBA_PRINT_REDUCTION_STEPS
50long sba_reduction_steps;
51long sba_interreduction_steps;
52#endif
53#if SBA_PRINT_OPERATIONS
54long sba_operations;
55long sba_interreduction_operations;
56#endif
57
58/***********************************************
59 * SBA stuff -- done
60***********************************************/
61
62#include "kernel/GBEngine/kutil.h"
63#include "misc/options.h"
64#include "omalloc/omalloc.h"
65#include "kernel/polys.h"
66#include "kernel/ideals.h"
67#include "kernel/GBEngine/kstd1.h"
68#include "kernel/GBEngine/khstd.h"
69#include "polys/kbuckets.h"
70#include "polys/prCopy.h"
71#include "polys/weight.h"
72#include "misc/intvec.h"
73#ifdef HAVE_PLURAL
74#include "polys/nc/nc.h"
75#endif
76// #include "timer.h"
77
78/* shiftgb stuff */
79#include "kernel/GBEngine/shiftgb.h"
80
81  int (*test_PosInT)(const TSet T,const int tl,LObject &h);
82  int (*test_PosInL)(const LSet set, const int length,
83                LObject* L,const kStrategy strat);
84
85// return -1 if no divisor is found
86//        number of first divisor, otherwise
87int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
88{
89  unsigned long not_sev = ~L->sev;
90  int j = start;
91
92  const TSet T=strat->T;
93  const unsigned long* sevT=strat->sevT;
94  if (L->p!=NULL)
95  {
96    const ring r=currRing;
97    const poly p=L->p;
98
99    pAssume(~not_sev == p_GetShortExpVector(p, r));
100
101    if(rField_is_Ring(r))
102    {
103      loop
104      {
105        if (j > strat->tl) return -1;
106#if defined(PDEBUG) || defined(PDIV_DEBUG)
107        if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
108        {
109          if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
110            return j;
111        }
112#else
113        if (!(sevT[j] & not_sev) &&
114          p_LmDivisibleBy(T[j].p, p, r))
115        {
116          if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
117            return j;
118        }
119#endif
120        j++;
121      }
122    }
123    else
124    {
125      loop
126      {
127        if (j > strat->tl) return -1;
128#if defined(PDEBUG) || defined(PDIV_DEBUG)
129        if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
130        {
131          return j;
132        }
133#else
134        if (!(sevT[j] & not_sev) &&
135          p_LmDivisibleBy(T[j].p, p, r))
136        {
137          return j;
138        }
139#endif
140        j++;
141      }
142    }
143  }
144  else
145  {
146    const poly p=L->t_p;
147    const ring r=strat->tailRing;
148    if(rField_is_Ring(r))
149    {
150      loop
151      {
152        if (j > strat->tl) return -1;
153#if defined(PDEBUG) || defined(PDIV_DEBUG)
154        if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
155                               p, not_sev, r))
156        {
157          if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
158            return j;
159        }
160#else
161        if (!(sevT[j] & not_sev) &&
162          p_LmDivisibleBy(T[j].t_p, p, r))
163        {
164          if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
165            return j;
166        }
167#endif
168        j++;
169      }
170    }
171    else
172    {
173      loop
174      {
175        if (j > strat->tl) return -1;
176#if defined(PDEBUG) || defined(PDIV_DEBUG)
177        if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
178                               p, not_sev, r))
179        {
180          return j;
181        }
182#else
183        if (!(sevT[j] & not_sev) &&
184          p_LmDivisibleBy(T[j].t_p, p, r))
185        {
186          return j;
187        }
188#endif
189        j++;
190      }
191    }
192  }
193}
194
195// same as above, only with set S
196int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
197{
198  unsigned long not_sev = ~L->sev;
199  poly p = L->GetLmCurrRing();
200  int j = 0;
201
202  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
203#if 1
204  int ende;
205  if ((strat->ak>0) || currRing->pLexOrder || rField_is_Ring(currRing)) ende=strat->sl;
206  else ende=posInS(strat,*max_ind,p,0)+1;
207  if (ende>(*max_ind)) ende=(*max_ind);
208#else
209  int ende=strat->sl;
210#endif
211  (*max_ind)=ende;
212  if(rField_is_Ring(currRing))
213  {
214    loop
215    {
216      if (j > ende) return -1;
217#if defined(PDEBUG) || defined(PDIV_DEBUG)
218      if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
219                             p, not_sev, currRing))
220      {
221        if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
222          return j;
223      }
224#else
225      if ( !(strat->sevS[j] & not_sev) &&
226         p_LmDivisibleBy(strat->S[j], p, currRing))
227      {
228        if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
229          return j;
230      }
231#endif
232      j++;
233    }
234  }
235  else
236  {
237    loop
238    {
239      if (j > ende) return -1;
240#if defined(PDEBUG) || defined(PDIV_DEBUG)
241      if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
242                             p, not_sev, currRing))
243      {
244        return j;
245      }
246#else
247      if ( !(strat->sevS[j] & not_sev) &&
248         p_LmDivisibleBy(strat->S[j], p, currRing))
249      {
250        return j;
251      }
252#endif
253      j++;
254    }
255  }
256}
257
258int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
259{
260  unsigned long not_sev = ~L->sev;
261  poly p = L->GetLmCurrRing();
262  int j = start;
263
264  pAssume(~not_sev == p_GetShortExpVector(p, currRing));
265#if 1
266  int ende=max_ind;
267#else
268  int ende=strat->sl;
269#endif
270  if(rField_is_Ring(currRing))
271  {
272    loop
273    {
274      if (j > ende) return -1;
275#if defined(PDEBUG) || defined(PDIV_DEBUG)
276      if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
277                             p, not_sev, currRing))
278      {
279        if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
280          return j;
281      }
282#else
283      if ( !(strat->sevS[j] & not_sev) &&
284         p_LmDivisibleBy(strat->S[j], p, currRing))
285      {
286        if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
287          return j;
288      }
289#endif
290      j++;
291    }
292  }
293  else
294  {
295    loop
296    {
297      if (j > ende) return -1;
298#if defined(PDEBUG) || defined(PDIV_DEBUG)
299      if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
300                             p, not_sev, currRing))
301      {
302        return j;
303      }
304#else
305      if ( !(strat->sevS[j] & not_sev) &&
306         p_LmDivisibleBy(strat->S[j], p, currRing))
307      {
308        return j;
309      }
310#endif
311      j++;
312    }
313  }
314}
315
316#ifdef HAVE_RINGS
317poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
318{
319  // m = currRing->ch
320
321  if (input_p == NULL) return NULL;
322
323  poly p = input_p;
324  poly zeroPoly = NULL;
325  unsigned long a = (unsigned long) pGetCoeff(p);
326
327  int k_ind2 = 0;
328  int a_ind2 = ind2(a);
329
330  // unsigned long k = 1;
331  // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
332  for (int i = 1; i <= leadRing->N; i++)
333  {
334    k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
335  }
336
337  a = (unsigned long) pGetCoeff(p);
338
339  number tmp1;
340  poly tmp2, tmp3;
341  poly lead_mult = p_ISet(1, tailRing);
342  if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
343  {
344    int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
345    int s_exp;
346    zeroPoly = p_ISet(a, tailRing);
347    for (int i = 1; i <= leadRing->N; i++)
348    {
349      s_exp = p_GetExp(p, i,leadRing);
350      if (s_exp % 2 != 0)
351      {
352        s_exp = s_exp - 1;
353      }
354      while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
355      {
356        too_much = too_much - ind2(s_exp);
357        s_exp = s_exp - 2;
358      }
359      p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
360      for (int j = 1; j <= s_exp; j++)
361      {
362        tmp1 = nInit(j);
363        tmp2 = p_ISet(1, tailRing);
364        p_SetExp(tmp2, i, 1, tailRing);
365        p_Setm(tmp2, tailRing);
366        if (nIsZero(tmp1))
367        { // should nowbe obsolet, test ! TODO OLIVER
368          zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
369        }
370        else
371        {
372          tmp3 = p_NSet(nCopy(tmp1), tailRing);
373          zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
374        }
375      }
376    }
377    p_Setm(lead_mult, tailRing);
378    zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
379    tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
380    for (int i = 1; i <= leadRing->N; i++)
381    {
382      pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
383    }
384    p_Setm(tmp2, leadRing);
385    zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
386    pNext(tmp2) = zeroPoly;
387    return tmp2;
388  }
389/*  unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
390  if (1 == 0 && alpha_k <= a)
391  {  // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
392    zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
393    for (int i = 1; i <= leadRing->N; i++)
394    {
395      for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
396      {
397        tmp1 = nInit(j);
398        tmp2 = p_ISet(1, tailRing);
399        p_SetExp(tmp2, i, 1, tailRing);
400        p_Setm(tmp2, tailRing);
401        if (nIsZero(tmp1))
402        {
403          zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
404        }
405        else
406        {
407          tmp3 = p_ISet((unsigned long) tmp1, tailRing);
408          zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
409        }
410      }
411    }
412    tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
413    for (int i = 1; i <= leadRing->N; i++)
414    {
415      pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
416    }
417    p_Setm(tmp2, leadRing);
418    zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
419    pNext(tmp2) = zeroPoly;
420    return tmp2;
421  } */
422  return NULL;
423}
424#endif
425
426
427#ifdef HAVE_RINGS
428/*2
429*  reduction procedure for the ring Z/2^m
430*/
431int redRing (LObject* h,kStrategy strat)
432{
433  if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
434  if (strat->tl<0) return 1;
435
436  int at/*,i*/;
437  long d;
438  int j = 0;
439  int pass = 0;
440  // poly zeroPoly = NULL;
441
442// TODO warum SetpFDeg notwendig?
443  h->SetpFDeg();
444  assume(h->pFDeg() == h->FDeg);
445  long reddeg = h->GetpFDeg();
446
447  h->SetShortExpVector();
448  loop
449  {
450    j = kFindDivisibleByInT(strat, h);
451    if (j < 0)
452    {
453      // over ZZ: cleanup coefficients by complete reduction with monomials
454      postReduceByMon(h, strat);
455      if(h->p == NULL)
456      {
457        if (h->lcm!=NULL) pLmDelete(h->lcm);
458        h->Clear();
459        return 0;
460      }
461      if(nIsZero(pGetCoeff(h->p))) return 2;
462      j = kFindDivisibleByInT(strat, h);
463      if(j < 0)
464      {
465        if(strat->tl >= 0)
466            h->i_r1 = strat->tl;
467        else
468            h->i_r1 = -1;
469        if (h->GetLmTailRing() == NULL)
470        {
471          if (h->lcm!=NULL) pLmDelete(h->lcm);
472          h->Clear();
473          return 0;
474        }
475        return 1;
476      }
477    }
478    //printf("\nFound one: ");pWrite(strat->T[j].p);
479    //enterT(*h, strat);
480    ksReducePoly(h, &(strat->T[j]), NULL, NULL, strat); // with debug output
481    //printf("\nAfter small red: ");pWrite(h->p);
482    if (h->GetLmTailRing() == NULL)
483    {
484      if (h->lcm!=NULL) pLmDelete(h->lcm);
485#ifdef KDEBUG
486      h->lcm=NULL;
487#endif
488      h->Clear();
489      return 0;
490    }
491    h->SetShortExpVector();
492    d = h->SetpFDeg();
493    /*- try to reduce the s-polynomial -*/
494    pass++;
495    if (!TEST_OPT_REDTHROUGH &&
496        (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
497    {
498      h->SetLmCurrRing();
499      if (strat->posInLDependsOnLength)
500        h->SetLength(strat->length_pLength);
501      at = strat->posInL(strat->L,strat->Ll,h,strat);
502      if (at <= strat->Ll)
503      {
504#ifdef KDEBUG
505        if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
506#endif
507        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);     // NOT RING CHECKED OLIVER
508        h->Clear();
509        return -1;
510      }
511    }
512    if (d != reddeg)
513    {
514      if (d >= (long)strat->tailRing->bitmask)
515      {
516        if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
517        {
518          strat->overflow=TRUE;
519          //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
520          h->GetP();
521          at = strat->posInL(strat->L,strat->Ll,h,strat);
522          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
523          h->Clear();
524          return -1;
525        }
526      }
527      else if ((TEST_OPT_PROT) && (strat->Ll < 0))
528      {
529        Print(".%ld",d);mflush();
530        reddeg = d;
531      }
532    }
533  }
534}
535#endif
536
537/*2
538*  reduction procedure for the homogeneous case
539*  and the case of a degree-ordering
540*/
541int redHomog (LObject* h,kStrategy strat)
542{
543  if (strat->tl<0) return 1;
544  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
545  assume(h->FDeg == h->pFDeg());
546
547  poly h_p;
548  int i,j,at,pass, ii;
549  unsigned long not_sev;
550  // long reddeg,d;
551
552  pass = j = 0;
553  // d = reddeg = h->GetpFDeg();
554  h->SetShortExpVector();
555  int li;
556  h_p = h->GetLmTailRing();
557  not_sev = ~ h->sev;
558  loop
559  {
560    j = kFindDivisibleByInT(strat, h);
561    if (j < 0) return 1;
562
563    li = strat->T[j].pLength;
564    if (li<=0) li=strat->T[j].GetpLength();
565    ii = j;
566    /*
567     * the polynomial to reduce with (up to the moment) is;
568     * pi with length li
569     */
570    i = j;
571#if 1
572    if (TEST_OPT_LENGTH)
573    loop
574    {
575      /*- search the shortest possible with respect to length -*/
576      i++;
577      if (i > strat->tl)
578        break;
579      if (li==1)
580        break;
581      if ((strat->T[i].pLength < li)
582         &&
583          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
584                               h_p, not_sev, strat->tailRing))
585      {
586        /*
587         * the polynomial to reduce with is now;
588         */
589        li = strat->T[i].pLength;
590        if (li<=0) li=strat->T[i].GetpLength();
591        ii = i;
592      }
593    }
594#endif
595
596    /*
597     * end of search: have to reduce with pi
598     */
599#ifdef KDEBUG
600    if (TEST_OPT_DEBUG)
601    {
602      PrintS("red:");
603      h->wrp();
604      PrintS(" with ");
605      strat->T[ii].wrp();
606    }
607#endif
608    assume(strat->fromT == FALSE);
609
610    ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
611#if SBA_PRINT_REDUCTION_STEPS
612    sba_interreduction_steps++;
613#endif
614#if SBA_PRINT_OPERATIONS
615    sba_interreduction_operations  +=  pLength(strat->T[ii].p);
616#endif
617
618#ifdef KDEBUG
619    if (TEST_OPT_DEBUG)
620    {
621      PrintS("\nto ");
622      h->wrp();
623      PrintLn();
624    }
625#endif
626
627    h_p = h->GetLmTailRing();
628    if (h_p == NULL)
629    {
630      if (h->lcm!=NULL) pLmFree(h->lcm);
631#ifdef KDEBUG
632      h->lcm=NULL;
633#endif
634      return 0;
635    }
636    h->SetShortExpVector();
637    not_sev = ~ h->sev;
638    /*
639     * try to reduce the s-polynomial h
640     *test first whether h should go to the lazyset L
641     *-if the degree jumps
642     *-if the number of pre-defined reductions jumps
643     */
644    pass++;
645    if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
646    {
647      h->SetLmCurrRing();
648      at = strat->posInL(strat->L,strat->Ll,h,strat);
649      if (at <= strat->Ll)
650      {
651        int dummy=strat->sl;
652        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
653          return 1;
654        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
655#ifdef KDEBUG
656        if (TEST_OPT_DEBUG)
657          Print(" lazy: -> L%d\n",at);
658#endif
659        h->Clear();
660        return -1;
661      }
662    }
663  }
664}
665
666KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red, kStrategy strat)
667{
668  BOOLEAN ret;
669  number coef;
670  assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
671  if(!rField_is_Ring(currRing))
672    Red->HeadNormalize();
673  /*
674  printf("------------------------\n");
675  pWrite(Red->GetLmCurrRing());
676  */
677  if(rField_is_Ring(currRing))
678    ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
679  else
680    ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
681  if (!ret)
682  {
683    if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
684    {
685      PR->Mult_nn(coef);
686      // HANNES: mark for Normalize
687    }
688    n_Delete(&coef, currRing->cf);
689  }
690  return ret;
691}
692
693/*2
694*  reduction procedure for signature-based standard
695*  basis algorithms:
696*  all reductions have to be sig-safe!
697*
698*  2 is returned if and only if the pair is rejected by the rewritten criterion
699*  at exactly this point of the computations. This is the last possible point
700*  such a check can be done => checks with the biggest set of available
701*  signatures
702*/
703
704int redSig (LObject* h,kStrategy strat)
705{
706  if (strat->tl<0) return 1;
707  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
708  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
709  assume(h->FDeg == h->pFDeg());
710//#if 1
711#ifdef DEBUGF5
712  PrintS("------- IN REDSIG -------\n");
713  Print("p: ");
714  pWrite(pHead(h->p));
715  PrintS("p1: ");
716  pWrite(pHead(h->p1));
717  PrintS("p2: ");
718  pWrite(pHead(h->p2));
719  PrintS("---------------------------\n");
720#endif
721  poly h_p;
722  int i,j,at,pass, ii;
723  int start=0;
724  int sigSafe;
725  unsigned long not_sev;
726  // long reddeg,d;
727
728  pass = j = 0;
729  // d = reddeg = h->GetpFDeg();
730  h->SetShortExpVector();
731  int li;
732  h_p = h->GetLmTailRing();
733  not_sev = ~ h->sev;
734  loop
735  {
736    j = kFindDivisibleByInT(strat, h, start);
737    if (j < 0)
738    {
739      return 1;
740    }
741
742    li = strat->T[j].pLength;
743    if (li<=0) li=strat->T[j].GetpLength();
744    ii = j;
745    /*
746     * the polynomial to reduce with (up to the moment) is;
747     * pi with length li
748     */
749    i = j;
750#if 1
751    if (TEST_OPT_LENGTH)
752    loop
753    {
754      /*- search the shortest possible with respect to length -*/
755      i++;
756      if (i > strat->tl)
757        break;
758      if (li==1)
759        break;
760      if ((strat->T[i].pLength < li)
761         &&
762          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
763                               h_p, not_sev, strat->tailRing))
764      {
765        /*
766         * the polynomial to reduce with is now;
767         */
768        li = strat->T[i].pLength;
769        if (li<=0) li=strat->T[i].GetpLength();
770        ii = i;
771      }
772    }
773    start = ii+1;
774#endif
775
776    /*
777     * end of search: have to reduce with pi
778     */
779#ifdef KDEBUG
780    if (TEST_OPT_DEBUG)
781    {
782      PrintS("red:");
783      h->wrp();
784      PrintS(" with ");
785      strat->T[ii].wrp();
786    }
787#endif
788    assume(strat->fromT == FALSE);
789//#if 1
790#ifdef DEBUGF5
791    Print("BEFORE REDUCTION WITH %d:\n",ii);
792    PrintS("--------------------------------\n");
793    pWrite(h->sig);
794    pWrite(strat->T[ii].sig);
795    pWrite(h->GetLmCurrRing());
796    pWrite(pHead(h->p1));
797    pWrite(pHead(h->p2));
798    pWrite(pHead(strat->T[ii].p));
799    PrintS("--------------------------------\n");
800    printf("INDEX OF REDUCER T: %d\n",ii);
801#endif
802    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
803#if SBA_PRINT_REDUCTION_STEPS
804    if (sigSafe != 3)
805      sba_reduction_steps++;
806#endif
807#if SBA_PRINT_OPERATIONS
808    if (sigSafe != 3)
809      sba_operations  +=  pLength(strat->T[ii].p);
810#endif
811    // if reduction has taken place, i.e. the reduction was sig-safe
812    // otherwise start is already at the next position and the loop
813    // searching reducers in T goes on from index start
814//#if 1
815#ifdef DEBUGF5
816    Print("SigSAFE: %d\n",sigSafe);
817#endif
818    if (sigSafe != 3)
819    {
820      // start the next search for reducers in T from the beginning
821      start = 0;
822#ifdef KDEBUG
823      if (TEST_OPT_DEBUG)
824      {
825        PrintS("\nto ");
826        h->wrp();
827        PrintLn();
828      }
829#endif
830
831      h_p = h->GetLmTailRing();
832      if (h_p == NULL)
833      {
834        if (h->lcm!=NULL) pLmFree(h->lcm);
835#ifdef KDEBUG
836        h->lcm=NULL;
837#endif
838        return 0;
839      }
840      h->SetShortExpVector();
841      not_sev = ~ h->sev;
842      /*
843      * try to reduce the s-polynomial h
844      *test first whether h should go to the lazyset L
845      *-if the degree jumps
846      *-if the number of pre-defined reductions jumps
847      */
848      pass++;
849      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
850      {
851        h->SetLmCurrRing();
852        at = strat->posInL(strat->L,strat->Ll,h,strat);
853        if (at <= strat->Ll)
854        {
855          int dummy=strat->sl;
856          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
857          {
858            return 1;
859          }
860          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
861#ifdef KDEBUG
862          if (TEST_OPT_DEBUG)
863            Print(" lazy: -> L%d\n",at);
864#endif
865          h->Clear();
866          return -1;
867        }
868      }
869    }
870  }
871}
872
873
874int redSigRing (LObject* h,kStrategy strat)
875{
876  //Since reduce is really bad for SBA we use the following idea:
877  // We first check if we can build a gcd pair between h and S
878  //where the sig remains the same and replace h by this gcd poly
879  assume(rField_is_Ring(currRing));
880  #if GCD_SBA
881  #ifdef ADIDEBUG
882  printf("\nBefore sbaCheckGcdPair ");pWrite(h->p);
883  #endif
884  while(sbaCheckGcdPair(h,strat))
885  {
886    #ifdef ADIDEBUG
887    printf("\nIntermidiate sbaCheckGcdPair ");pWrite(h->p);
888    #endif
889    h->sev = pGetShortExpVector(h->p);
890  }
891  #ifdef ADIDEBUG
892  printf("\nAfter sbaCheckGcdPair ");pWrite(h->p);
893  #endif
894  #endif
895  poly beforeredsig;
896  beforeredsig = pCopy(h->sig);
897
898  if (strat->tl<0) return 1;
899  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
900  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
901  assume(h->FDeg == h->pFDeg());
902  #ifdef ADIDEBUG
903  printf("\n--------------------------redSig-------------------------------------\n");
904  printf("\nBefore redSig:\n");
905  p_Write(h->p,strat->tailRing);pWrite(h->sig);
906  #endif
907//#if 1
908#ifdef DEBUGF5
909  Print("------- IN REDSIG -------\n");
910  Print("p: ");
911  pWrite(pHead(h->p));
912  Print("p1: ");
913  pWrite(pHead(h->p1));
914  Print("p2: ");
915  pWrite(pHead(h->p2));
916  Print("---------------------------\n");
917#endif
918  poly h_p;
919  int i,j,at,pass, ii;
920  int start=0;
921  int sigSafe;
922  unsigned long not_sev;
923  // long reddeg,d;
924
925  pass = j = 0;
926  // d = reddeg = h->GetpFDeg();
927  h->SetShortExpVector();
928  int li;
929  h_p = h->GetLmTailRing();
930  not_sev = ~ h->sev;
931  loop
932  {
933    j = kFindDivisibleByInT(strat, h, start);
934    if (j < 0)
935    {
936      #if GCD_SBA
937      #ifdef ADIDEBUG
938      printf("\nBefore sbaCheckGcdPair ");pWrite(h->p);
939      #endif
940      while(sbaCheckGcdPair(h,strat))
941      {
942        #ifdef ADIDEBUG
943        printf("\nIntermidiate sbaCheckGcdPair ");pWrite(h->p);
944        #endif
945        h->sev = pGetShortExpVector(h->p);
946        h->is_redundant = FALSE;
947        start = 0;
948      }
949      #ifdef ADIDEBUG
950      printf("\nAfter sbaCheckGcdPair ");pWrite(h->p);
951      #endif
952      #endif
953      // over ZZ: cleanup coefficients by complete reduction with monomials
954      postReduceByMonSig(h, strat);
955      if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
956      j = kFindDivisibleByInT(strat, h,start);
957      if(j < 0)
958      {
959        if(strat->tl >= 0)
960            h->i_r1 = strat->tl;
961        else
962            h->i_r1 = -1;
963        if (h->GetLmTailRing() == NULL)
964        {
965          if (h->lcm!=NULL) pLmDelete(h->lcm);
966          h->Clear();
967          return 0;
968        }
969        //Check for sigdrop after reduction
970        if(pLtCmp(beforeredsig,h->sig) == 1)
971        {
972          #ifdef ADIDEBUG
973          printf("\nSigDrop after reduce\n");pWrite(beforeredsig);pWrite(h->sig);
974          #endif
975          strat->sigdrop = TRUE;
976          //Reduce it as much as you can
977          int red_result = redRing(h,strat);
978          if(red_result == 0)
979          {
980            //It reduced to 0, cancel the sigdrop
981            #ifdef ADIDEBUG
982            printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
983            #endif
984            strat->sigdrop = FALSE;
985            p_Delete(&h->sig,currRing);h->sig = NULL;
986            return 0;
987          }
988          else
989          {
990            #ifdef ADIDEBUG
991            printf("\nReduced to this via redRing.SIGDROP\n");pWrite(h->p);
992            #endif
993            //strat->enterS(*h, strat->sl+1, strat, strat->tl);
994            return 0;
995          }
996        }
997        p_Delete(&beforeredsig,currRing);
998        return 1;
999      }
1000    }
1001
1002    li = strat->T[j].pLength;
1003    if (li<=0) li=strat->T[j].GetpLength();
1004    ii = j;
1005    /*
1006     * the polynomial to reduce with (up to the moment) is;
1007     * pi with length li
1008     */
1009    i = j;
1010    if (TEST_OPT_LENGTH)
1011    loop
1012    {
1013      /*- search the shortest possible with respect to length -*/
1014      i++;
1015      if (i > strat->tl)
1016        break;
1017      if (li==1)
1018        break;
1019      if ((strat->T[i].pLength < li)
1020         && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1021         && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1022                               h_p, not_sev, strat->tailRing))
1023      {
1024        /*
1025         * the polynomial to reduce with is now;
1026         */
1027        li = strat->T[i].pLength;
1028        if (li<=0) li=strat->T[i].GetpLength();
1029        ii = i;
1030      }
1031    }
1032
1033    start = ii+1;
1034
1035    /*
1036     * end of search: have to reduce with pi
1037     */
1038#ifdef KDEBUG
1039    if (TEST_OPT_DEBUG)
1040    {
1041      PrintS("red:");
1042      h->wrp();
1043      PrintS(" with ");
1044      strat->T[ii].wrp();
1045    }
1046#endif
1047    assume(strat->fromT == FALSE);
1048//#if 1
1049#ifdef DEBUGF5
1050    Print("BEFORE REDUCTION WITH %d:\n",ii);
1051    Print("--------------------------------\n");
1052    pWrite(h->sig);
1053    pWrite(strat->T[ii].sig);
1054    pWrite(h->GetLmCurrRing());
1055    pWrite(pHead(h->p1));
1056    pWrite(pHead(h->p2));
1057    pWrite(pHead(strat->T[ii].p));
1058    Print("--------------------------------\n");
1059    printf("INDEX OF REDUCER T: %d\n",ii);
1060#endif
1061    #ifdef ADIDEBUG
1062    printf("\nWe reduce it with:\n");p_Write(strat->T[ii].p,strat->tailRing);pWrite(strat->T[ii].sig);
1063    #endif
1064    sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1065    #ifdef ADIDEBUG
1066    printf("\nAfter small reduction:\n");pWrite(h->p);pWrite(h->sig);
1067    #endif
1068    if(h->p == NULL && h->sig == NULL)
1069    {
1070      //Trivial case catch
1071      strat->sigdrop = FALSE;
1072    }
1073    #if 0
1074    //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1075    //In some cases this proves to be very bad
1076    if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1077    {
1078      #ifdef ADIDEBUG
1079      printf("\nReducer and Original have same LT. Force it with redRing!\n");
1080      #endif
1081      int red_result = redRing(h,strat);
1082      if(red_result == 0)
1083      {
1084        #ifdef ADIDEBUG
1085        printf("\nRedRing reduced it to 0. Perfect\n");
1086        #endif
1087        pDelete(&h->sig);h->sig = NULL;
1088        return 0;
1089      }
1090      else
1091      {
1092        #ifdef ADIDEBUG
1093        printf("\nRedRing reduced it to *.\nHave to sigdrop now\n");pWrite(h->p);
1094        #endif
1095        strat->sigdrop = TRUE;
1096        return 1;
1097      }
1098    }
1099    #endif
1100    if(strat->sigdrop)
1101      return 1;
1102#if SBA_PRINT_REDUCTION_STEPS
1103    if (sigSafe != 3)
1104      sba_reduction_steps++;
1105#endif
1106#if SBA_PRINT_OPERATIONS
1107    if (sigSafe != 3)
1108      sba_operations  +=  pLength(strat->T[ii].p);
1109#endif
1110    // if reduction has taken place, i.e. the reduction was sig-safe
1111    // otherwise start is already at the next position and the loop
1112    // searching reducers in T goes on from index start
1113//#if 1
1114#ifdef DEBUGF5
1115    Print("SigSAFE: %d\n",sigSafe);
1116#endif
1117    if (sigSafe != 3)
1118    {
1119      // start the next search for reducers in T from the beginning
1120      start = 0;
1121#ifdef KDEBUG
1122      if (TEST_OPT_DEBUG)
1123      {
1124        PrintS("\nto ");
1125        h->wrp();
1126        PrintLn();
1127      }
1128#endif
1129
1130      h_p = h->GetLmTailRing();
1131      if (h_p == NULL)
1132      {
1133        if (h->lcm!=NULL) pLmFree(h->lcm);
1134#ifdef KDEBUG
1135        h->lcm=NULL;
1136#endif
1137        return 0;
1138      }
1139      h->SetShortExpVector();
1140      not_sev = ~ h->sev;
1141      /*
1142      * try to reduce the s-polynomial h
1143      *test first whether h should go to the lazyset L
1144      *-if the degree jumps
1145      *-if the number of pre-defined reductions jumps
1146      */
1147      pass++;
1148      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1149      {
1150        h->SetLmCurrRing();
1151        at = strat->posInL(strat->L,strat->Ll,h,strat);
1152        if (at <= strat->Ll)
1153        {
1154          int dummy=strat->sl;
1155          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1156          {
1157            return 1;
1158          }
1159          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1160#ifdef KDEBUG
1161          if (TEST_OPT_DEBUG)
1162            Print(" lazy: -> L%d\n",at);
1163#endif
1164          h->Clear();
1165          return -1;
1166        }
1167      }
1168    }
1169  }
1170}
1171
1172// tail reduction for SBA
1173poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
1174{
1175#define REDTAIL_CANONICALIZE 100
1176  strat->redTailChange=FALSE;
1177  if (strat->noTailReduction) return L->GetLmCurrRing();
1178  poly h, p;
1179  p = h = L->GetLmTailRing();
1180  if ((h==NULL) || (pNext(h)==NULL))
1181    return L->GetLmCurrRing();
1182
1183  TObject* With;
1184  // placeholder in case strat->tl < 0
1185  TObject  With_s(strat->tailRing);
1186
1187  LObject Ln(pNext(h), strat->tailRing);
1188  Ln.sig      = L->sig;
1189  Ln.sevSig   = L->sevSig;
1190  Ln.pLength  = L->GetpLength() - 1;
1191
1192  pNext(h) = NULL;
1193  if (L->p != NULL) pNext(L->p) = NULL;
1194  L->pLength = 1;
1195
1196  Ln.PrepareRed(strat->use_buckets);
1197
1198  int cnt=REDTAIL_CANONICALIZE;
1199  while(!Ln.IsNull())
1200  {
1201    loop
1202    {
1203      if(rField_is_Ring(currRing) && strat->sigdrop)
1204        break;
1205      Ln.SetShortExpVector();
1206      if (withT)
1207      {
1208        int j;
1209        j = kFindDivisibleByInT(strat, &Ln);
1210        if (j < 0) break;
1211        With = &(strat->T[j]);
1212      }
1213      else
1214      {
1215        With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1216        if (With == NULL) break;
1217      }
1218      cnt--;
1219      if (cnt==0)
1220      {
1221        cnt=REDTAIL_CANONICALIZE;
1222        /*poly tmp=*/Ln.CanonicalizeP();
1223        if (normalize && !rField_is_Ring(currRing))
1224        {
1225          Ln.Normalize();
1226          //pNormalize(tmp);
1227          //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1228        }
1229      }
1230      if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
1231      {
1232        With->pNorm();
1233      }
1234      strat->redTailChange=TRUE;
1235      #ifdef ADIDEBUG
1236      printf("\nWill TAILreduce * with *:\n");p_Write(Ln.p,strat->tailRing);pWrite(Ln.sig);
1237      p_Write(With->p,strat->tailRing);pWrite(With->sig);pWrite(L->sig);
1238      #endif
1239      int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1240      if(rField_is_Ring(currRing))
1241        L->sig = Ln.sig;
1242      //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1243      // I delete it an then set Ln.sig. Hence L->sig is lost
1244      #ifdef ADIDEBUG
1245      printf("\nAfter small TAILreduce:\n");pWrite(Ln.p);pWrite(Ln.sig);pWrite(L->sig);
1246      #endif
1247#if SBA_PRINT_REDUCTION_STEPS
1248      if (ret != 3)
1249        sba_reduction_steps++;
1250#endif
1251#if SBA_PRINT_OPERATIONS
1252      if (ret != 3)
1253        sba_operations  +=  pLength(With->p);
1254#endif
1255      if (ret)
1256      {
1257        // reducing the tail would violate the exp bound
1258        //  set a flag and hope for a retry (in bba)
1259        strat->completeReduce_retry=TRUE;
1260        if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1261        do
1262        {
1263          pNext(h) = Ln.LmExtractAndIter();
1264          pIter(h);
1265          L->pLength++;
1266        } while (!Ln.IsNull());
1267        goto all_done;
1268      }
1269      if (Ln.IsNull()) goto all_done;
1270      if (! withT) With_s.Init(currRing);
1271      if(rField_is_Ring(currRing) && strat->sigdrop)
1272      {
1273        //Cannot break the loop here so easily
1274        break;
1275      }
1276    }
1277    pNext(h) = Ln.LmExtractAndIter();
1278    pIter(h);
1279    if(!rField_is_Ring(currRing))
1280      pNormalize(h);
1281    L->pLength++;
1282  }
1283  all_done:
1284  Ln.Delete();
1285  if (L->p != NULL) pNext(L->p) = pNext(p);
1286
1287  if (strat->redTailChange)
1288  {
1289    L->length = 0;
1290  }
1291  //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1292  //L->Normalize(); // HANNES: should have a test
1293  kTest_L(L);
1294  return L->GetLmCurrRing();
1295}
1296
1297/*2
1298*  reduction procedure for the inhomogeneous case
1299*  and not a degree-ordering
1300*/
1301int redLazy (LObject* h,kStrategy strat)
1302{
1303  if (strat->tl<0) return 1;
1304  int at,i,ii,li;
1305  int j = 0;
1306  int pass = 0;
1307  assume(h->pFDeg() == h->FDeg);
1308  long reddeg = h->GetpFDeg();
1309  long d;
1310  unsigned long not_sev;
1311
1312  h->SetShortExpVector();
1313  poly h_p = h->GetLmTailRing();
1314  not_sev = ~ h->sev;
1315  loop
1316  {
1317    j = kFindDivisibleByInT(strat, h);
1318    if (j < 0) return 1;
1319
1320    li = strat->T[j].pLength;
1321    if (li<=0) li=strat->T[j].GetpLength();
1322    ii = j;
1323    /*
1324     * the polynomial to reduce with (up to the moment) is;
1325     * pi with length li
1326     */
1327
1328    i = j;
1329#if 1
1330    if (TEST_OPT_LENGTH)
1331    loop
1332    {
1333      /*- search the shortest possible with respect to length -*/
1334      i++;
1335      if (i > strat->tl)
1336        break;
1337      if (li==1)
1338        break;
1339      if ((strat->T[i].pLength < li)
1340         &&
1341          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1342                               h_p, not_sev, strat->tailRing))
1343      {
1344        /*
1345         * the polynomial to reduce with is now;
1346         */
1347        li = strat->T[i].pLength;
1348        if (li<=0) li=strat->T[i].GetpLength();
1349        ii = i;
1350      }
1351    }
1352#endif
1353
1354    /*
1355     * end of search: have to reduce with pi
1356     */
1357
1358
1359#ifdef KDEBUG
1360    if (TEST_OPT_DEBUG)
1361    {
1362      PrintS("red:");
1363      h->wrp();
1364      PrintS(" with ");
1365      strat->T[ii].wrp();
1366    }
1367#endif
1368
1369    ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
1370#if SBA_PRINT_REDUCTION_STEPS
1371    sba_interreduction_steps++;
1372#endif
1373#if SBA_PRINT_OPERATIONS
1374    sba_interreduction_operations  +=  pLength(strat->T[ii].p);
1375#endif
1376
1377#ifdef KDEBUG
1378    if (TEST_OPT_DEBUG)
1379    {
1380      PrintS("\nto ");
1381      h->wrp();
1382      PrintLn();
1383    }
1384#endif
1385
1386    h_p=h->GetLmTailRing();
1387
1388    if (h_p == NULL)
1389    {
1390      if (h->lcm!=NULL) pLmFree(h->lcm);
1391#ifdef KDEBUG
1392      h->lcm=NULL;
1393#endif
1394      return 0;
1395    }
1396    h->SetShortExpVector();
1397    not_sev = ~ h->sev;
1398    d = h->SetpFDeg();
1399    /*- try to reduce the s-polynomial -*/
1400    pass++;
1401    if (//!TEST_OPT_REDTHROUGH &&
1402        (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1403    {
1404      h->SetLmCurrRing();
1405      at = strat->posInL(strat->L,strat->Ll,h,strat);
1406      if (at <= strat->Ll)
1407      {
1408#if 1
1409        int dummy=strat->sl;
1410        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1411          return 1;
1412#endif
1413#ifdef KDEBUG
1414        if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1415#endif
1416        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1417        h->Clear();
1418        return -1;
1419      }
1420    }
1421    else if (d != reddeg)
1422    {
1423      if (d>=(long)strat->tailRing->bitmask)
1424      {
1425        if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1426        {
1427          strat->overflow=TRUE;
1428          //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1429          h->GetP();
1430          at = strat->posInL(strat->L,strat->Ll,h,strat);
1431          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1432          h->Clear();
1433          return -1;
1434        }
1435      }
1436      else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1437      {
1438        Print(".%ld",d);mflush();
1439        reddeg = d;
1440      }
1441    }
1442  }
1443}
1444/*2
1445*  reduction procedure for the sugar-strategy (honey)
1446* reduces h with elements from T choosing first possible
1447* element in T with respect to the given ecart
1448*/
1449int redHoney (LObject* h, kStrategy strat)
1450{
1451  if (strat->tl<0) return 1;
1452  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1453  assume(h->FDeg == h->pFDeg());
1454  poly h_p;
1455  int i,j,at,pass,ei, ii, h_d;
1456  unsigned long not_sev;
1457  long reddeg,d;
1458
1459  pass = j = 0;
1460  d = reddeg = h->GetpFDeg() + h->ecart;
1461  h->SetShortExpVector();
1462  int li;
1463  h_p = h->GetLmTailRing();
1464  not_sev = ~ h->sev;
1465
1466  h->PrepareRed(strat->use_buckets);
1467  loop
1468  {
1469    j=kFindDivisibleByInT(strat, h);
1470    if (j < 0) return 1;
1471
1472    ei = strat->T[j].ecart;
1473    li = strat->T[j].pLength;
1474    if (li<=0) li=strat->T[j].GetpLength();
1475    ii = j;
1476    /*
1477     * the polynomial to reduce with (up to the moment) is;
1478     * pi with ecart ei (T[ii])
1479     */
1480    i = j;
1481    if (TEST_OPT_LENGTH)
1482    loop
1483    {
1484      /*- takes the first possible with respect to ecart -*/
1485      i++;
1486      if (i > strat->tl)
1487        break;
1488      //if (ei < h->ecart)
1489      //  break;
1490      if (li==1)
1491        break;
1492      if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
1493         || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1494         &&
1495          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1496                               h_p, not_sev, strat->tailRing))
1497      {
1498        /*
1499         * the polynomial to reduce with is now;
1500         */
1501        ei = strat->T[i].ecart;
1502        li = strat->T[i].pLength;
1503        if (li<=0) li=strat->T[i].GetpLength();
1504        ii = i;
1505      }
1506    }
1507
1508    /*
1509     * end of search: have to reduce with pi
1510     */
1511    if (!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart))
1512    {
1513      h->GetTP(); // clears bucket
1514      h->SetLmCurrRing();
1515      /*
1516       * It is not possible to reduce h with smaller ecart;
1517       * if possible h goes to the lazy-set L,i.e
1518       * if its position in L would be not the last one
1519       */
1520      if (strat->Ll >= 0) /* L is not empty */
1521      {
1522        at = strat->posInL(strat->L,strat->Ll,h,strat);
1523        if(at <= strat->Ll)
1524          /*- h will not become the next element to reduce -*/
1525        {
1526          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1527#ifdef KDEBUG
1528          if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1529#endif
1530          h->Clear();
1531          return -1;
1532        }
1533      }
1534    }
1535#ifdef KDEBUG
1536    if (TEST_OPT_DEBUG)
1537    {
1538      PrintS("red:");
1539      h->wrp();
1540      Print("\nwith T[%d]:",ii);
1541      strat->T[ii].wrp();
1542    }
1543#endif
1544    assume(strat->fromT == FALSE);
1545
1546    ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,strat);
1547#if SBA_PRINT_REDUCTION_STEPS
1548    sba_interreduction_steps++;
1549#endif
1550#if SBA_PRINT_OPERATIONS
1551    sba_interreduction_operations  +=  pLength(strat->T[ii].p);
1552#endif
1553#ifdef KDEBUG
1554    if (TEST_OPT_DEBUG)
1555    {
1556      PrintS("\nto:");
1557      h->wrp();
1558      PrintLn();
1559    }
1560#endif
1561    if(h->IsNull())
1562    {
1563      h->Clear();
1564      if (h->lcm!=NULL) pLmFree(h->lcm);
1565      #ifdef KDEBUG
1566      h->lcm=NULL;
1567      #endif
1568      return 0;
1569    }
1570    if (TEST_OPT_IDLIFT)
1571    {
1572      if (h->p!=NULL)
1573      {
1574        if(p_GetComp(h->p,currRing)>strat->syzComp)
1575        {
1576          h->Delete();
1577          return 0;
1578        }
1579      }
1580      else if (h->t_p!=NULL)
1581      {
1582        if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1583        {
1584          h->Delete();
1585          return 0;
1586        }
1587      }
1588    }
1589    h->SetShortExpVector();
1590    not_sev = ~ h->sev;
1591    h_d = h->SetpFDeg();
1592    /* compute the ecart */
1593    if (ei <= h->ecart)
1594      h->ecart = d-h_d;
1595    else
1596      h->ecart = d-h_d+ei-h->ecart;
1597
1598    /*
1599     * try to reduce the s-polynomial h
1600     *test first whether h should go to the lazyset L
1601     *-if the degree jumps
1602     *-if the number of pre-defined reductions jumps
1603     */
1604    pass++;
1605    d = h_d + h->ecart;
1606    if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1607    {
1608      h->GetTP(); // clear bucket
1609      h->SetLmCurrRing();
1610      at = strat->posInL(strat->L,strat->Ll,h,strat);
1611      if (at <= strat->Ll)
1612      {
1613        int dummy=strat->sl;
1614        if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1615          return 1;
1616        enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1617#ifdef KDEBUG
1618        if (TEST_OPT_DEBUG)
1619          Print(" degree jumped: -> L%d\n",at);
1620#endif
1621        h->Clear();
1622        return -1;
1623      }
1624    }
1625    else if (d > reddeg)
1626    {
1627      if (d>=(long)strat->tailRing->bitmask)
1628      {
1629        if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
1630        {
1631          strat->overflow=TRUE;
1632          //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1633          h->GetP();
1634          at = strat->posInL(strat->L,strat->Ll,h,strat);
1635          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1636          h->Clear();
1637          return -1;
1638        }
1639      }
1640      else if (TEST_OPT_PROT && (strat->Ll < 0) )
1641      {
1642        //h->wrp(); Print("<%d>\n",h->GetpLength());
1643        reddeg = d;
1644        Print(".%ld",d); mflush();
1645      }
1646    }
1647  }
1648}
1649
1650/*2
1651*  reduction procedure for the normal form
1652*/
1653
1654poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
1655{
1656#define REDNF_CANONICALIZE 60
1657  if (h==NULL) return NULL;
1658  int j;
1659  int cnt=REDNF_CANONICALIZE;
1660  max_ind=strat->sl;
1661
1662  if (0 > strat->sl)
1663  {
1664    return h;
1665  }
1666  LObject P(h);
1667  P.SetShortExpVector();
1668  P.bucket = kBucketCreate(currRing);
1669  kBucketInit(P.bucket,P.p,pLength(P.p));
1670  kbTest(P.bucket);
1671#ifdef HAVE_RINGS
1672  BOOLEAN is_ring = rField_is_Ring(currRing);
1673#endif
1674#ifdef KDEBUG
1675//  if (TEST_OPT_DEBUG)
1676//  {
1677//    PrintS("redNF: starting S:\n");
1678//    for( j = 0; j <= max_ind; j++ )
1679//    {
1680//      Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1681//      pWrite(strat->S[j]);
1682//    }
1683//  };
1684#endif
1685
1686  loop
1687  {
1688    j=kFindDivisibleByInS(strat,&max_ind,&P);
1689    if (j>=0)
1690    {
1691#ifdef HAVE_RINGS
1692      if (!is_ring)
1693      {
1694#endif
1695        int sl=pSize(strat->S[j]);
1696        int jj=j;
1697        loop
1698        {
1699          int sll;
1700          jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
1701          if (jj<0) break;
1702          sll=pSize(strat->S[jj]);
1703          if (sll<sl)
1704          {
1705            #ifdef KDEBUG
1706            if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
1707            #endif
1708            //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
1709            j=jj;
1710            sl=sll;
1711          }
1712        }
1713        if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
1714        {
1715          pNorm(strat->S[j]);
1716          //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1717        }
1718#ifdef HAVE_RINGS
1719      }
1720#endif
1721      nNormalize(pGetCoeff(P.p));
1722#ifdef KDEBUG
1723      if (TEST_OPT_DEBUG)
1724      {
1725        PrintS("red:");
1726        wrp(h);
1727        PrintS(" with ");
1728        wrp(strat->S[j]);
1729      }
1730#endif
1731#ifdef HAVE_PLURAL
1732      if (rIsPluralRing(currRing))
1733      {
1734        number coef;
1735        nc_kBucketPolyRed(P.bucket,strat->S[j],&coef);
1736        nDelete(&coef);
1737      }
1738      else
1739#endif
1740      {
1741        number coef;
1742        coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
1743        nDelete(&coef);
1744      }
1745      cnt--;
1746      if (cnt==0)
1747      {
1748        kBucketCanonicalize(P.bucket);
1749        cnt=REDNF_CANONICALIZE;
1750      }
1751      h = kBucketGetLm(P.bucket);   // FRAGE OLIVER
1752      if (h==NULL)
1753      {
1754        kBucketDestroy(&P.bucket);
1755
1756#ifdef KDEBUG
1757//        if (TEST_OPT_DEBUG)
1758//        {
1759//          PrintS("redNF: starting S:\n");
1760//          for( j = 0; j <= max_ind; j++ )
1761//          {
1762//            Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1763//            pWrite(strat->S[j]);
1764//          }
1765//        };
1766#endif
1767
1768        return NULL;
1769      }
1770      kbTest(P.bucket);
1771      P.p=h;
1772      P.t_p=NULL;
1773      P.SetShortExpVector();
1774#ifdef KDEBUG
1775      if (TEST_OPT_DEBUG)
1776      {
1777        PrintS("\nto:");
1778        wrp(h);
1779        PrintLn();
1780      }
1781#endif
1782    }
1783    else
1784    {
1785      P.p=kBucketClear(P.bucket);
1786      kBucketDestroy(&P.bucket);
1787      pNormalize(P.p);
1788
1789#ifdef KDEBUG
1790//      if (TEST_OPT_DEBUG)
1791//      {
1792//        PrintS("redNF: starting S:\n");
1793//        for( j = 0; j <= max_ind; j++ )
1794//        {
1795//          Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1796//          pWrite(strat->S[j]);
1797//        }
1798//      };
1799#endif
1800
1801      return P.p;
1802    }
1803  }
1804}
1805
1806/*2
1807*  reduction procedure from global case but with jet bound
1808*/
1809
1810poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
1811{
1812  h = pJet(h,bound);
1813  if (h==NULL) return NULL;
1814  int j;
1815  max_ind=strat->sl;
1816
1817  if (0 > strat->sl)
1818  {
1819    return h;
1820  }
1821  LObject P(h);
1822  P.SetShortExpVector();
1823  P.bucket = kBucketCreate(currRing);
1824  kBucketInit(P.bucket,P.p,pLength(P.p));
1825  kbTest(P.bucket);
1826#ifdef HAVE_RINGS
1827  BOOLEAN is_ring = rField_is_Ring(currRing);
1828#endif
1829#ifdef KDEBUG
1830//  if (TEST_OPT_DEBUG)
1831//  {
1832//    PrintS("redNF: starting S:\n");
1833//    for( j = 0; j <= max_ind; j++ )
1834//    {
1835//      Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1836//      pWrite(strat->S[j]);
1837//    }
1838//  };
1839#endif
1840
1841  loop
1842  {
1843    j=kFindDivisibleByInS(strat,&max_ind,&P);
1844    if (j>=0)
1845    {
1846#ifdef HAVE_RINGS
1847      if (!is_ring)
1848      {
1849#endif
1850        int sl=pSize(strat->S[j]);
1851        int jj=j;
1852        loop
1853        {
1854          int sll;
1855          jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
1856          if (jj<0) break;
1857          sll=pSize(strat->S[jj]);
1858          if (sll<sl)
1859          {
1860            #ifdef KDEBUG
1861            if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
1862            #endif
1863            //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
1864            j=jj;
1865            sl=sll;
1866          }
1867        }
1868        if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
1869        {
1870          pNorm(strat->S[j]);
1871          //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1872        }
1873#ifdef HAVE_RINGS
1874      }
1875#endif
1876      nNormalize(pGetCoeff(P.p));
1877#ifdef KDEBUG
1878      if (TEST_OPT_DEBUG)
1879      {
1880        PrintS("red:");
1881        wrp(h);
1882        PrintS(" with ");
1883        wrp(strat->S[j]);
1884      }
1885#endif
1886#ifdef HAVE_PLURAL
1887      if (rIsPluralRing(currRing))
1888      {
1889        number coef;
1890        nc_kBucketPolyRed(P.bucket,strat->S[j],&coef);
1891        nDelete(&coef);
1892      }
1893      else
1894#endif
1895      {
1896        number coef;
1897        coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
1898        P.p = kBucketClear(P.bucket);
1899        P.p = pJet(P.p,bound);
1900        if(!P.IsNull())
1901        {
1902          kBucketDestroy(&P.bucket);
1903          P.SetShortExpVector();
1904          P.bucket = kBucketCreate(currRing);
1905          kBucketInit(P.bucket,P.p,pLength(P.p));
1906        }
1907        nDelete(&coef);
1908      }
1909      h = kBucketGetLm(P.bucket);   // FRAGE OLIVER
1910      if (h==NULL)
1911      {
1912        kBucketDestroy(&P.bucket);
1913
1914#ifdef KDEBUG
1915//        if (TEST_OPT_DEBUG)
1916//        {
1917//          PrintS("redNF: starting S:\n");
1918//          for( j = 0; j <= max_ind; j++ )
1919//          {
1920//            Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1921//            pWrite(strat->S[j]);
1922//          }
1923//        };
1924#endif
1925
1926        return NULL;
1927      }
1928      kbTest(P.bucket);
1929      P.p=h;
1930      P.t_p=NULL;
1931      P.SetShortExpVector();
1932#ifdef KDEBUG
1933      if (TEST_OPT_DEBUG)
1934      {
1935        PrintS("\nto:");
1936        wrp(h);
1937        PrintLn();
1938      }
1939#endif
1940    }
1941    else
1942    {
1943      P.p=kBucketClear(P.bucket);
1944      kBucketDestroy(&P.bucket);
1945      pNormalize(P.p);
1946
1947#ifdef KDEBUG
1948//      if (TEST_OPT_DEBUG)
1949//      {
1950//        PrintS("redNF: starting S:\n");
1951//        for( j = 0; j <= max_ind; j++ )
1952//        {
1953//          Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1954//          pWrite(strat->S[j]);
1955//        }
1956//      };
1957#endif
1958
1959      return P.p;
1960    }
1961  }
1962}
1963
1964void kDebugPrint(kStrategy strat);
1965
1966ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1967{
1968  int   red_result = 1;
1969  int   olddeg,reduc;
1970  int hilbeledeg=1,hilbcount=0,minimcnt=0;
1971  BOOLEAN withT = FALSE;
1972  BITSET save;
1973  SI_SAVE_OPT1(save);
1974
1975  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
1976  if(rField_is_Ring(currRing))
1977    initBuchMoraPosRing(strat);
1978  else
1979    initBuchMoraPos(strat);
1980  initHilbCrit(F,Q,&hilb,strat);
1981  initBba(strat);
1982  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
1983  /*Shdl=*/initBuchMora(F, Q,strat);
1984  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1985  reduc = olddeg = 0;
1986
1987#ifndef NO_BUCKETS
1988  if (!TEST_OPT_NOT_BUCKETS)
1989    strat->use_buckets = 1;
1990#endif
1991  // redtailBBa against T for inhomogenous input
1992  if (!TEST_OPT_OLDSTD)
1993    withT = ! strat->homog;
1994
1995  // strat->posInT = posInT_pLength;
1996  kTest_TS(strat);
1997
1998#ifdef HAVE_TAIL_RING
1999  if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
2000    kStratInitChangeTailRing(strat);
2001#endif
2002  if (BVERBOSE(23))
2003  {
2004    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2005    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2006    kDebugPrint(strat);
2007  }
2008
2009
2010#ifdef KDEBUG
2011  //kDebugPrint(strat);
2012#endif
2013  /* compute------------------------------------------------------- */
2014  while (strat->Ll >= 0)
2015  {
2016    #ifdef ADIDEBUG
2017    printf("\n      ------------------------NEW LOOP\n");
2018    printf("\nShdl = \n");
2019    #if 0
2020    idPrint(strat->Shdl);
2021    #else
2022    for(int ii = 0; ii<=strat->sl;ii++)
2023        p_Write(strat->S[ii],strat->tailRing);
2024    #endif
2025    printf("\n   list   L\n");
2026    int iii;
2027    #if 1
2028    for(iii = 0; iii<= strat->Ll; iii++)
2029    {
2030        printf("L[%i]:",iii);
2031        p_Write(strat->L[iii].p, currRing);
2032        p_Write(strat->L[iii].p1, currRing);
2033        p_Write(strat->L[iii].p2, currRing);
2034    }
2035    #else
2036    {
2037        printf("L[%i]:",strat->Ll);
2038        p_Write(strat->L[strat->Ll].p, strat->tailRing);
2039        p_Write(strat->L[strat->Ll].p1, strat->tailRing);
2040        p_Write(strat->L[strat->Ll].p2, strat->tailRing);
2041    }
2042    #endif
2043    #if 0
2044    for(iii = 0; iii<= strat->Bl; iii++)
2045    {
2046        printf("B[%i]:",iii);
2047        p_Write(strat->B[iii].p, /*strat->tailRing*/currRing);
2048        p_Write(strat->B[iii].p1, /*strat->tailRing*/currRing);
2049        p_Write(strat->B[iii].p2, strat->tailRing);
2050    }
2051    #endif
2052    //getchar();
2053    #endif
2054    #ifdef KDEBUG
2055      if (TEST_OPT_DEBUG) messageSets(strat);
2056    #endif
2057    if (strat->Ll== 0) strat->interpt=TRUE;
2058    if (TEST_OPT_DEGBOUND
2059        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2060            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2061    {
2062      /*
2063       *stops computation if
2064       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2065       *a predefined number Kstd1_deg
2066       */
2067      while ((strat->Ll >= 0)
2068        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2069        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2070            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2071        )
2072        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2073      if (strat->Ll<0) break;
2074      else strat->noClearS=TRUE;
2075    }
2076    /* picks the last element from the lazyset L */
2077    strat->P = strat->L[strat->Ll];
2078    strat->Ll--;
2079
2080    if (pNext(strat->P.p) == strat->tail)
2081    {
2082      // deletes the short spoly
2083      if (rField_is_Ring(currRing))
2084        pLmDelete(strat->P.p);
2085      else
2086        pLmFree(strat->P.p);
2087      strat->P.p = NULL;
2088      poly m1 = NULL, m2 = NULL;
2089
2090      // check that spoly creation is ok
2091      while (strat->tailRing != currRing &&
2092             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2093      {
2094        assume(m1 == NULL && m2 == NULL);
2095        // if not, change to a ring where exponents are at least
2096        // large enough
2097        if (!kStratChangeTailRing(strat))
2098        {
2099          WerrorS("OVERFLOW...");
2100          break;
2101        }
2102      }
2103      // create the real one
2104      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2105                    strat->tailRing, m1, m2, strat->R);
2106    }
2107    else if (strat->P.p1 == NULL)
2108    {
2109      if (strat->minim > 0)
2110        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2111      // for input polys, prepare reduction
2112      strat->P.PrepareRed(strat->use_buckets);
2113    }
2114
2115    if (strat->P.p == NULL && strat->P.t_p == NULL)
2116    {
2117      red_result = 0;
2118    }
2119    else
2120    {
2121      if (TEST_OPT_PROT)
2122        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2123                &olddeg,&reduc,strat, red_result);
2124
2125      /* reduction of the element chosen from L */
2126      red_result = strat->red(&strat->P,strat);
2127      if (errorreported)  break;
2128    }
2129
2130    if (strat->overflow)
2131    {
2132      if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2133    }
2134
2135    // reduction to non-zero new poly
2136    if (red_result == 1)
2137    {
2138      // get the polynomial (canonicalize bucket, make sure P.p is set)
2139      strat->P.GetP(strat->lmBin);
2140      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2141      // but now, for entering S, T, we reset it
2142      // in the inhomogeneous case: FDeg == pFDeg
2143      if (strat->homog) strat->initEcart(&(strat->P));
2144
2145      /* statistic */
2146      if (TEST_OPT_PROT) PrintS("s");
2147
2148      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2149
2150      // reduce the tail and normalize poly
2151      // in the ring case we cannot expect LC(f) = 1,
2152      // therefore we call pCleardenom instead of pNorm
2153      strat->redTailChange=FALSE;
2154      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
2155      {
2156        strat->P.pCleardenom();
2157        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2158        {
2159          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2160          strat->P.pCleardenom();
2161          if (strat->redTailChange) { strat->P.t_p=NULL; }
2162        }
2163      }
2164      else
2165      {
2166        strat->P.pNorm();
2167        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2168        {
2169          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2170          if (strat->redTailChange) { strat->P.t_p=NULL; }
2171        }
2172      }
2173
2174#ifdef KDEBUG
2175      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2176#endif /* KDEBUG */
2177
2178      // min_std stuff
2179      if ((strat->P.p1==NULL) && (strat->minim>0))
2180      {
2181        if (strat->minim==1)
2182        {
2183          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2184          p_Delete(&strat->P.p2, currRing, strat->tailRing);
2185        }
2186        else
2187        {
2188          strat->M->m[minimcnt]=strat->P.p2;
2189          strat->P.p2=NULL;
2190        }
2191        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2192          pNext(strat->M->m[minimcnt])
2193            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2194                                           strat->tailRing, currRing,
2195                                           currRing->PolyBin);
2196        minimcnt++;
2197      }
2198
2199      // enter into S, L, and T
2200      if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2201      {
2202        enterT(strat->P, strat);
2203        if (rField_is_Ring(currRing))
2204          superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2205        else
2206          enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2207        // posInS only depends on the leading term
2208        strat->enterS(strat->P, pos, strat, strat->tl);
2209        #ifdef ADIDEBUG
2210        printf("\nThis element has been added to S:\n");pWrite(strat->P.p);pWrite(strat->P.p1);pWrite(strat->P.p2);
2211        #endif
2212#if 0
2213        int pl=pLength(strat->P.p);
2214        if (pl==1)
2215        {
2216          //if (TEST_OPT_PROT)
2217          //PrintS("<1>");
2218        }
2219        else if (pl==2)
2220        {
2221          //if (TEST_OPT_PROT)
2222          //PrintS("<2>");
2223        }
2224#endif
2225      }
2226      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2227//      Print("[%d]",hilbeledeg);
2228      if (strat->P.lcm!=NULL)
2229      {
2230        if (rField_is_Ring(currRing)) pLmDelete(strat->P.lcm);
2231        else                          pLmFree(strat->P.lcm);
2232        strat->P.lcm=NULL;
2233      }
2234      if (strat->s_poly!=NULL)
2235      {
2236        // the only valid entries are: strat->P.p,
2237        // strat->tailRing (read-only, keep it)
2238        // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2239        if (strat->s_poly(strat))
2240        {
2241          // we are called AFTER enterS, i.e. if we change P
2242          // we have to add it also to S/T
2243          // and add pairs
2244          int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2245          enterT(strat->P, strat);
2246          if (rField_is_Ring(currRing))
2247            superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2248          else
2249            enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2250          strat->enterS(strat->P, pos, strat, strat->tl);
2251        }
2252      }
2253    }
2254    else if (strat->P.p1 == NULL && strat->minim > 0)
2255    {
2256      p_Delete(&strat->P.p2, currRing, strat->tailRing);
2257    }
2258
2259#ifdef KDEBUG
2260    memset(&(strat->P), 0, sizeof(strat->P));
2261#endif /* KDEBUG */
2262    kTest_TS(strat);
2263  }
2264#ifdef KDEBUG
2265  if (TEST_OPT_DEBUG) messageSets(strat);
2266#endif /* KDEBUG */
2267
2268  if (TEST_OPT_SB_1)
2269  {
2270    if(!rField_is_Ring(currRing))
2271    {
2272      int k=1;
2273      int j;
2274      while(k<=strat->sl)
2275      {
2276        j=0;
2277        loop
2278        {
2279          if (j>=k) break;
2280          clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2281          j++;
2282        }
2283        k++;
2284      }
2285    }
2286  }
2287  /* complete reduction of the standard basis--------- */
2288  if (TEST_OPT_REDSB)
2289  {
2290    completeReduce(strat);
2291    if (strat->completeReduce_retry)
2292    {
2293      // completeReduce needed larger exponents, retry
2294      // to reduce with S (instead of T)
2295      // and in currRing (instead of strat->tailRing)
2296#ifdef HAVE_TAIL_RING
2297      if(currRing->bitmask>strat->tailRing->bitmask)
2298      {
2299        strat->completeReduce_retry=FALSE;
2300        cleanT(strat);strat->tailRing=currRing;
2301        int i;
2302        for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2303        completeReduce(strat);
2304      }
2305      if (strat->completeReduce_retry)
2306#endif
2307        Werror("exponent bound is %ld",currRing->bitmask);
2308    }
2309  }
2310  else if (TEST_OPT_PROT) PrintLn();
2311  if (!errorreported)
2312  {
2313    if(rField_is_Ring_Z(currRing))
2314    {
2315      for(int i = 0;i<=strat->sl;i++)
2316      {
2317        if(!nGreaterZero(pGetCoeff(strat->S[i])))
2318        {
2319          strat->S[i] = pNeg(strat->S[i]);
2320        }
2321      }
2322      finalReduceByMon(strat);
2323      for(int i = 0;i<=strat->sl;i++)
2324      {
2325        if(!nGreaterZero(pGetCoeff(strat->S[i])))
2326        {
2327          strat->S[i] = pNeg(strat->S[i]);
2328        }
2329      }
2330    }
2331    else if (rField_is_Ring(currRing))
2332      finalReduceByMon(strat);
2333  }
2334  /* release temp data-------------------------------- */
2335  exitBuchMora(strat);
2336//  if (TEST_OPT_WEIGHTM)
2337//  {
2338//    pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2339//    if (ecartWeights)
2340//    {
2341//      omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2342//      ecartWeights=NULL;
2343//    }
2344//  }
2345  if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2346  SI_RESTORE_OPT1(save);
2347  if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2348
2349  idTest(strat->Shdl);
2350
2351  return (strat->Shdl);
2352}
2353
2354ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2355{
2356  // ring order stuff:
2357  // in sba we have (until now) two possibilities:
2358  // 1. an incremental computation w.r.t. (C,monomial order)
2359  // 2. a (possibly non-incremental) computation w.r.t. the
2360  //    induced Schreyer order.
2361  // The corresponding orders are computed in sbaRing(), depending
2362  // on the flag strat->sbaOrder
2363#if SBA_PRINT_ZERO_REDUCTIONS
2364  long zeroreductions           = 0;
2365#endif
2366#if SBA_PRINT_PRODUCT_CRITERION
2367  long product_criterion        = 0;
2368#endif
2369#if SBA_PRINT_SIZE_G
2370  int size_g                    = 0;
2371  int size_g_non_red            = 0;
2372#endif
2373#if SBA_PRINT_SIZE_SYZ
2374  long size_syz                 = 0;
2375#endif
2376  // global variable
2377#if SBA_PRINT_REDUCTION_STEPS
2378  sba_reduction_steps           = 0;
2379  sba_interreduction_steps      = 0;
2380#endif
2381#if SBA_PRINT_OPERATIONS
2382  sba_operations                = 0;
2383  sba_interreduction_operations = 0;
2384#endif
2385
2386  ideal F1 = F0;
2387  ring sRing, currRingOld;
2388  currRingOld  = currRing;
2389  if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
2390  {
2391    sRing = sbaRing(strat);
2392    if (sRing!=currRingOld)
2393    {
2394      rChangeCurrRing (sRing);
2395      F1 = idrMoveR (F0, currRingOld, currRing);
2396    }
2397  }
2398  ideal F;
2399  // sort ideal F
2400  //Put the SigDrop element on the correct position (think of sbaEnterS)
2401  //We also sort them
2402  if(rField_is_Ring(currRing) && strat->sigdrop)
2403  {
2404    #if 1
2405    F = idInit(IDELEMS(F1),F1->rank);
2406    for (int i=0; i<IDELEMS(F1);++i)
2407      F->m[i] = F1->m[i];
2408    if(strat->sbaEnterS >= 0)
2409    {
2410      poly dummy;
2411      dummy = pCopy(F->m[0]); //the sigdrop element
2412      for(int i = 0;i<strat->sbaEnterS;i++)
2413        F->m[i] = F->m[i+1];
2414      F->m[strat->sbaEnterS] = dummy;
2415    }
2416    #else
2417    F = idInit(1,F1->rank);
2418    //printf("\nBefore the initial block sorting:\n");idPrint(F1);
2419    F->m[0] = F1->m[0];
2420    int pos;
2421    if(strat->sbaEnterS >= 0)
2422    {
2423      for(int i=1;i<=strat->sbaEnterS;i++)
2424      {
2425        pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2426        idInsertPolyOnPos(F,F1->m[i],pos);
2427      }
2428      for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2429      {
2430        pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2431        idInsertPolyOnPos(F,F1->m[i],pos);
2432      }
2433      poly dummy;
2434      dummy = pCopy(F->m[0]); //the sigdrop element
2435      for(int i = 0;i<strat->sbaEnterS;i++)
2436        F->m[i] = F->m[i+1];
2437      F->m[strat->sbaEnterS] = dummy;
2438    }
2439    else
2440    {
2441      for(int i=1;i<IDELEMS(F1);i++)
2442      {
2443        pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2444        idInsertPolyOnPos(F,F1->m[i],pos);
2445      }
2446    }
2447    #endif
2448    //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2449  }
2450  else
2451  {
2452    F       = idInit(IDELEMS(F1),F1->rank);
2453    intvec *sort  = idSort(F1);
2454    for (int i=0; i<sort->length();++i)
2455      F->m[i] = F1->m[(*sort)[i]-1];
2456    if(rField_is_Ring(currRing))
2457    {
2458      // put the monomials after the sbaEnterS polynomials
2459      //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2460      int nrmon = 0;
2461      for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2462      {
2463        //pWrite(F->m[i]);
2464        if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2465        {
2466          poly mon = F->m[i];
2467          for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2468          {
2469            F->m[j] = F->m[j-1];
2470          }
2471          F->m[j] = mon;
2472          nrmon++;
2473        }
2474        //idPrint(F);
2475      }
2476    }
2477  }
2478    //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2479  if(rField_is_Ring(currRing))
2480    strat->sigdrop = FALSE;
2481  strat->nrsyzcrit = 0;
2482  strat->nrrewcrit = 0;
2483#if SBA_INTERRED_START
2484  F = kInterRed(F,NULL);
2485#endif
2486#if F5DEBUG
2487  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2488  rWrite (currRing);
2489  printf("ordSgn = %d\n",currRing->OrdSgn);
2490  printf("\n");
2491#endif
2492  int   srmax,lrmax, red_result = 1;
2493  int   olddeg,reduc;
2494  int hilbeledeg=1,hilbcount=0,minimcnt=0;
2495  LObject L;
2496  BOOLEAN withT     = TRUE;
2497  strat->max_lower_index = 0;
2498  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2499  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
2500  initSbaPos(strat);
2501  initHilbCrit(F,Q,&hilb,strat);
2502  initSba(F,strat);
2503  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2504  /*Shdl=*/initSbaBuchMora(F, Q,strat);
2505  idTest(strat->Shdl);
2506  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2507  srmax = strat->sl;
2508  reduc = olddeg = lrmax = 0;
2509#ifndef NO_BUCKETS
2510  if (!TEST_OPT_NOT_BUCKETS)
2511    strat->use_buckets = 1;
2512#endif
2513
2514  // redtailBBa against T for inhomogenous input
2515  // if (!TEST_OPT_OLDSTD)
2516  //   withT = ! strat->homog;
2517
2518  // strat->posInT = posInT_pLength;
2519  kTest_TS(strat);
2520
2521#ifdef HAVE_TAIL_RING
2522  if(!idIs0(F) &&(!rField_is_Ring(currRing)))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
2523    kStratInitChangeTailRing(strat);
2524#endif
2525  if (BVERBOSE(23))
2526  {
2527    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2528    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2529    kDebugPrint(strat);
2530  }
2531  // We add the elements directly in S from the previous loop
2532  if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2533  {
2534    for(int i = 0;i<strat->sbaEnterS;i++)
2535    {
2536      //Update: now the element is at the corect place
2537      //i+1 because on the 0 position is the sigdrop element
2538      enterT(strat->L[strat->Ll-(i)],strat);
2539      strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2540    }
2541    strat->Ll = strat->Ll - strat->sbaEnterS;
2542    strat->sbaEnterS = -1;
2543  }
2544  kTest_TS(strat);
2545#ifdef KDEBUG
2546  //kDebugPrint(strat);
2547#endif
2548  /* compute------------------------------------------------------- */
2549  while (strat->Ll >= 0)
2550  {
2551    #ifdef ADIDEBUG
2552    printf("\n      ------------------------NEW LOOP\n");
2553    printf("\nShdl = \n");
2554    #if 0
2555    idPrint(strat->Shdl);
2556    #else
2557    for(int ii = 0; ii<=strat->sl;ii++)
2558    {
2559      printf("\nS[%i]:  ",ii);p_Write(strat->S[ii],strat->tailRing);
2560      printf("sig:   ");pWrite(strat->sig[ii]);
2561    }
2562    #endif
2563    #if 0
2564    for(int iii = 0; iii< strat->syzl; iii++)
2565    {
2566        printf("\nsyz[%i]:\n",iii);
2567        p_Write(strat->syz[iii], currRing);
2568    }
2569    #endif
2570    #if 0
2571    for(int iii = 0; iii<= strat->tl; iii++)
2572    {
2573        printf("\nT[%i]:\n",iii);
2574        p_Write(strat->T[iii].p, currRing);
2575    }
2576    #endif
2577    printf("\n   list   L\n");
2578    int iii;
2579    #if 0
2580    for(iii = 0; iii<= strat->Ll; iii++)
2581    {
2582        printf("\nL[%i]:\n",iii);
2583        p_Write(strat->L[iii].p, currRing);
2584        p_Write(strat->L[iii].p1, currRing);
2585        p_Write(strat->L[iii].p2, currRing);
2586        p_Write(strat->L[iii].sig, currRing);
2587    }
2588    #else
2589    {
2590        printf("L[%i]:",strat->Ll);
2591        p_Write(strat->L[strat->Ll].p, strat->tailRing);
2592        p_Write(strat->L[strat->Ll].p1, strat->tailRing);
2593        p_Write(strat->L[strat->Ll].p2, strat->tailRing);
2594        p_Write(strat->L[strat->Ll].sig, currRing);
2595    }
2596    #endif
2597    //getchar();
2598    #endif
2599    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2600    #ifdef KDEBUG
2601      if (TEST_OPT_DEBUG) messageSets(strat);
2602    #endif
2603    if (strat->Ll== 0) strat->interpt=TRUE;
2604    /*
2605    if (TEST_OPT_DEGBOUND
2606        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2607            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2608    {
2609
2610       //stops computation if
2611       // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2612       //a predefined number Kstd1_deg
2613      while ((strat->Ll >= 0)
2614        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2615        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2616            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2617        )
2618        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2619      if (strat->Ll<0) break;
2620      else strat->noClearS=TRUE;
2621    }
2622    */
2623    if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2624    {
2625      strat->currIdx  = pGetComp(strat->L[strat->Ll].sig);
2626#if F5C
2627      // 1. interreduction of the current standard basis
2628      // 2. generation of new principal syzygy rules for syzCriterion
2629      f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2630          lrmax, reduc, Q, w, hilb );
2631#endif
2632      // initialize new syzygy rules for the next iteration step
2633      initSyzRules(strat);
2634    }
2635    /*********************************************************************
2636      * interrreduction step is done, we can go on with the next iteration
2637      * step of the signature-based algorithm
2638      ********************************************************************/
2639    /* picks the last element from the lazyset L */
2640    strat->P = strat->L[strat->Ll];
2641    strat->Ll--;
2642
2643    if(rField_is_Ring(currRing))
2644      strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2645
2646    #ifdef ADIDEBUG
2647    printf("\n-------------------------\nThis is the current element P\n");
2648    p_Write(strat->P.p,strat->tailRing);
2649    p_Write(strat->P.p1,strat->tailRing);
2650    p_Write(strat->P.p2,strat->tailRing);
2651    p_Write(strat->P.sig,currRing);
2652    #endif
2653    /* reduction of the element chosen from L */
2654    if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2655    {
2656      //#if 1
2657#ifdef DEBUGF5
2658      PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2659      PrintS("-------------------------------------------------\n");
2660      pWrite(strat->P.sig);
2661      pWrite(pHead(strat->P.p));
2662      pWrite(pHead(strat->P.p1));
2663      pWrite(pHead(strat->P.p2));
2664      PrintS("-------------------------------------------------\n");
2665#endif
2666      if (pNext(strat->P.p) == strat->tail)
2667      {
2668        // deletes the short spoly
2669        /*
2670        if (rField_is_Ring(currRing))
2671          pLmDelete(strat->P.p);
2672        else
2673          pLmFree(strat->P.p);
2674*/
2675          // TODO: needs some masking
2676          // TODO: masking needs to vanish once the signature
2677          //       sutff is completely implemented
2678          strat->P.p = NULL;
2679        poly m1 = NULL, m2 = NULL;
2680
2681        // check that spoly creation is ok
2682        while (strat->tailRing != currRing &&
2683            !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2684        {
2685          assume(m1 == NULL && m2 == NULL);
2686          // if not, change to a ring where exponents are at least
2687          // large enough
2688          if (!kStratChangeTailRing(strat))
2689          {
2690            WerrorS("OVERFLOW...");
2691            break;
2692          }
2693        }
2694        // create the real one
2695        ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2696            strat->tailRing, m1, m2, strat->R);
2697
2698      }
2699      else if (strat->P.p1 == NULL)
2700      {
2701        if (strat->minim > 0)
2702          strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2703        // for input polys, prepare reduction
2704        if(!rField_is_Ring(currRing))
2705          strat->P.PrepareRed(strat->use_buckets);
2706      }
2707      if (strat->P.p == NULL && strat->P.t_p == NULL)
2708      {
2709        red_result = 0;
2710      }
2711      else
2712      {
2713        //#if 1
2714#ifdef DEBUGF5
2715        PrintS("Poly before red: ");
2716        pWrite(pHead(strat->P.p));
2717        pWrite(strat->P.sig);
2718#endif
2719#if SBA_PRODUCT_CRITERION
2720        if (strat->P.prod_crit)
2721        {
2722#if SBA_PRINT_PRODUCT_CRITERION
2723          product_criterion++;
2724#endif
2725          int pos = posInSyz(strat, strat->P.sig);
2726          enterSyz(strat->P, strat, pos);
2727          if (strat->P.lcm!=NULL)
2728            pLmFree(strat->P.lcm);
2729          red_result = 2;
2730        }
2731        else
2732        {
2733          red_result = strat->red(&strat->P,strat);
2734        }
2735#else
2736        red_result = strat->red(&strat->P,strat);
2737#endif
2738      }
2739    }
2740    else
2741    {
2742      /*
2743      if (strat->P.lcm != NULL)
2744        pLmFree(strat->P.lcm);
2745        */
2746      red_result = 2;
2747    }
2748    if(rField_is_Ring(currRing))
2749    {
2750      if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
2751      {
2752        strat->P.p = pNeg(strat->P.p);
2753        strat->P.sig = pNeg(strat->P.sig);
2754      }
2755      strat->P.pLength = pLength(strat->P.p);
2756      if(strat->P.sig != NULL)
2757        strat->P.sevSig = pGetShortExpVector(strat->P.sig);
2758      if(strat->P.p != NULL)
2759        strat->P.sev = pGetShortExpVector(strat->P.p);
2760    }
2761    #ifdef ADIDEBUG
2762    printf("\nAfter reduce (redresult=%i): \n",red_result);pWrite(strat->P.p);pWrite(strat->P.sig);
2763    #endif
2764    //sigdrop case
2765    if(rField_is_Ring(currRing) && strat->sigdrop)
2766    {
2767      //First reduce it as much as one can
2768      #ifdef ADIDEBUG
2769      printf("\nSigdrop in the reduce. Trying redring\n");
2770      #endif
2771      red_result = redRing(&strat->P,strat);
2772      if(red_result == 0)
2773      {
2774        #ifdef ADIDEBUG
2775        printf("\nSigdrop cancelled since redRing reduced to 0\n");
2776        #endif
2777        strat->sigdrop = FALSE;
2778        pDelete(&strat->P.sig);
2779        strat->P.sig = NULL;
2780      }
2781      else
2782      {
2783        #ifdef ADIDEBUG
2784        printf("\nStill Sigdrop - redRing reduced to:\n");pWrite(strat->P.p);
2785        #endif
2786        strat->enterS(strat->P, 0, strat, strat->tl);
2787        if (TEST_OPT_PROT)
2788          PrintS("-");
2789        break;
2790      }
2791    }
2792    if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
2793    {
2794      #ifdef ADIDEBUG
2795      printf("\nToo many blocked reductions\n");
2796      #endif
2797      strat->sigdrop = TRUE;
2798      break;
2799    }
2800
2801    if (errorreported)  break;
2802
2803//#if 1
2804#ifdef DEBUGF5
2805    if (red_result != 0)
2806    {
2807        PrintS("Poly after red: ");
2808        pWrite(pHead(strat->P.p));
2809        pWrite(strat->P.GetLmCurrRing());
2810        pWrite(strat->P.sig);
2811        printf("%d\n",red_result);
2812    }
2813#endif
2814    if (TEST_OPT_PROT)
2815    {
2816      if(strat->P.p != NULL)
2817        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2818                &olddeg,&reduc,strat, red_result);
2819      else
2820        message((strat->honey ? strat->P.ecart : 0),
2821                &olddeg,&reduc,strat, red_result);
2822    }
2823
2824    if (strat->overflow)
2825    {
2826        if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2827    }
2828    // reduction to non-zero new poly
2829    if (red_result == 1)
2830    {
2831      // get the polynomial (canonicalize bucket, make sure P.p is set)
2832      strat->P.GetP(strat->lmBin);
2833
2834      // sig-safe computations may lead to wrong FDeg computation, thus we need
2835      // to recompute it to make sure everything is alright
2836      (strat->P).FDeg = (strat->P).pFDeg();
2837      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2838      // but now, for entering S, T, we reset it
2839      // in the inhomogeneous case: FDeg == pFDeg
2840      if (strat->homog) strat->initEcart(&(strat->P));
2841
2842      /* statistic */
2843      if (TEST_OPT_PROT) PrintS("s");
2844
2845      //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2846      // in F5E we know that the last reduced element is already the
2847      // the one with highest signature
2848      int pos = strat->sl+1;
2849
2850      // reduce the tail and normalize poly
2851      // in the ring case we cannot expect LC(f) = 1,
2852      // therefore we call pCleardenom instead of pNorm
2853      #ifdef HAVE_RINGS
2854      poly beforetailred;
2855      if(rField_is_Ring(currRing))
2856        beforetailred = pCopy(strat->P.sig);
2857      #endif
2858#if SBA_TAIL_RED
2859      if(rField_is_Ring(currRing))
2860      {
2861        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2862          strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2863      }
2864      else
2865      {
2866        if (strat->sbaOrder != 2)
2867        {
2868          if (TEST_OPT_INTSTRATEGY)
2869          {
2870            strat->P.pCleardenom();
2871            if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2872            {
2873              strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2874              strat->P.pCleardenom();
2875            }
2876          }
2877          else
2878          {
2879            strat->P.pNorm();
2880            if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
2881              strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2882          }
2883        }
2884      }
2885      // It may happen that we have lost the sig in redtailsba
2886      // It cannot reduce to 0 since here we are doing just tail reduction.
2887      // Best case scenerio: remains the leading term
2888      if(rField_is_Ring(currRing) && strat->sigdrop)
2889      {
2890        #ifdef ADIDEBUG
2891        printf("\n Still sigdrop after redtailSba - it reduced to \n");pWrite(strat->P.p);
2892        #endif
2893        strat->enterS(strat->P, 0, strat, strat->tl);
2894        break;
2895      }
2896#endif
2897    if(rField_is_Ring(currRing))
2898    {
2899      if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
2900      {
2901        #ifdef ADIDEBUG
2902        printf("\nSigDrop after TAILred\n");pWrite(beforetailred);pWrite(strat->P.sig);
2903        #endif
2904        strat->sigdrop = TRUE;
2905        //Reduce it as much as you can
2906        red_result = redRing(&strat->P,strat);
2907        if(red_result == 0)
2908        {
2909          //It reduced to 0, cancel the sigdrop
2910          #ifdef ADIDEBUG
2911          printf("\nReduced to 0 via redRing. Cancel sigdrop\n");
2912          #endif
2913          strat->sigdrop = FALSE;
2914          p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
2915        }
2916        else
2917        {
2918          #ifdef ADIDEBUG
2919          printf("\nReduced to this via redRing.SIGDROP\n");pWrite(strat->P.p);
2920          #endif
2921          strat->enterS(strat->P, 0, strat, strat->tl);
2922          break;
2923        }
2924      }
2925      p_Delete(&beforetailred,currRing);
2926      // strat->P.p = NULL may appear if we had  a sigdrop above and reduced to 0 via redRing
2927      if(strat->P.p == NULL)
2928        goto case_when_red_result_changed;
2929    }
2930    #ifdef ADIDEBUG
2931    printf("\nNach redTailSba: \n");
2932    p_Write(strat->P.p,strat->tailRing);p_Write(strat->P.sig,currRing);
2933    #endif
2934    // remove sigsafe label since it is no longer valid for the next element to
2935    // be reduced
2936    if (strat->sbaOrder == 1)
2937    {
2938      for (int jj = 0; jj<strat->tl+1; jj++)
2939      {
2940        if (pGetComp(strat->T[jj].sig) == strat->currIdx)
2941        {
2942          strat->T[jj].is_sigsafe = FALSE;
2943        }
2944      }
2945    }
2946    else
2947    {
2948      for (int jj = 0; jj<strat->tl+1; jj++)
2949      {
2950        strat->T[jj].is_sigsafe = FALSE;
2951      }
2952    }
2953#ifdef KDEBUG
2954      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2955#endif /* KDEBUG */
2956
2957      // min_std stuff
2958      if ((strat->P.p1==NULL) && (strat->minim>0))
2959      {
2960        if (strat->minim==1)
2961        {
2962          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2963          p_Delete(&strat->P.p2, currRing, strat->tailRing);
2964        }
2965        else
2966        {
2967          strat->M->m[minimcnt]=strat->P.p2;
2968          strat->P.p2=NULL;
2969        }
2970        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2971          pNext(strat->M->m[minimcnt])
2972            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2973                                           strat->tailRing, currRing,
2974                                           currRing->PolyBin);
2975        minimcnt++;
2976      }
2977
2978      // enter into S, L, and T
2979      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2980      enterT(strat->P, strat);
2981      strat->T[strat->tl].is_sigsafe = FALSE;
2982      /*
2983      printf("hier\n");
2984      pWrite(strat->P.GetLmCurrRing());
2985      pWrite(strat->P.sig);
2986      */
2987      if (rField_is_Ring(currRing))
2988        superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2989      else
2990        enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2991      #ifdef ADIDEBUG
2992        printf("\nThis element is added to S\n");
2993        p_Write(strat->P.p, strat->tailRing);p_Write(strat->P.p1, strat->tailRing);p_Write(strat->P.p2, strat->tailRing);pWrite(strat->P.sig);
2994        //getchar();
2995        #endif
2996      if(rField_is_Ring(currRing) && strat->sigdrop)
2997        break;
2998      if(rField_is_Ring(currRing))
2999        strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3000      strat->enterS(strat->P, pos, strat, strat->tl);
3001      if(strat->sbaOrder != 1)
3002      {
3003        BOOLEAN overwrite = FALSE;
3004        for (int tk=0; tk<strat->sl+1; tk++)
3005        {
3006          if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3007          {
3008            //printf("TK %d / %d\n",tk,strat->sl);
3009            overwrite = FALSE;
3010            break;
3011          }
3012        }
3013        //printf("OVERWRITE %d\n",overwrite);
3014        if (overwrite)
3015        {
3016          int cmp = pGetComp(strat->P.sig);
3017          int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3018          p_GetExpV (strat->P.p,vv,currRing);
3019          p_SetExpV (strat->P.sig, vv,currRing);
3020          p_SetComp (strat->P.sig,cmp,currRing);
3021
3022          strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3023          int i;
3024          LObject Q;
3025          for(int ps=0;ps<strat->sl+1;ps++)
3026          {
3027
3028            strat->newt = TRUE;
3029            if (strat->syzl == strat->syzmax)
3030            {
3031              pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3032              strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3033                  (strat->syzmax)*sizeof(unsigned long),
3034                  ((strat->syzmax)+setmaxTinc)
3035                  *sizeof(unsigned long));
3036              strat->syzmax += setmaxTinc;
3037            }
3038            Q.sig = pCopy(strat->P.sig);
3039            // add LM(F->m[i]) to the signature to get a Schreyer order
3040            // without changing the underlying polynomial ring at all
3041            if (strat->sbaOrder == 0)
3042              p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3043            // since p_Add_q() destroys all input
3044            // data we need to recreate help
3045            // each time
3046            // ----------------------------------------------------------
3047            // in the Schreyer order we always know that the multiplied
3048            // module monomial strat->P.sig gives the leading monomial of
3049            // the corresponding principal syzygy
3050            // => we do not need to compute the "real" syzygy completely
3051            poly help = p_Copy(strat->sig[ps],currRing);
3052            p_ExpVectorAdd (help,strat->P.p,currRing);
3053            Q.sig = p_Add_q(Q.sig,help,currRing);
3054            //printf("%d. SYZ  ",i+1);
3055            //pWrite(strat->syz[i]);
3056            Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3057            i = posInSyz(strat, Q.sig);
3058            enterSyz(Q, strat, i);
3059          }
3060        }
3061      }
3062      // deg - idx - lp/rp
3063      // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3064      if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3065      {
3066        int cmp     = pGetComp(strat->P.sig);
3067        int max_cmp = IDELEMS(F);
3068        int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3069        p_GetExpV (strat->P.p,vv,currRing);
3070        LObject Q;
3071        int pos;
3072        int idx = __p_GetComp(strat->P.sig,currRing);
3073        //printf("++ -- adding syzygies -- ++\n");
3074        // if new element is the first one in this index
3075        if (strat->currIdx < idx)
3076        {
3077          for (int i=0; i<strat->sl; ++i)
3078          {
3079            Q.sig = p_Copy(strat->P.sig,currRing);
3080            p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3081            poly help = p_Copy(strat->sig[i],currRing);
3082            p_ExpVectorAdd(help,strat->P.p,currRing);
3083            Q.sig = p_Add_q(Q.sig,help,currRing);
3084            //pWrite(Q.sig);
3085            pos = posInSyz(strat, Q.sig);
3086            enterSyz(Q, strat, pos);
3087          }
3088          strat->currIdx = idx;
3089        }
3090        else
3091        {
3092          // if the element is not the first one in the given index we build all
3093          // possible syzygies with elements of higher index
3094          for (int i=cmp+1; i<=max_cmp; ++i)
3095          {
3096            pos = -1;
3097            for (int j=0; j<strat->sl; ++j)
3098            {
3099              if (__p_GetComp(strat->sig[j],currRing) == i)
3100              {
3101                pos = j;
3102                break;
3103              }
3104            }
3105            if (pos != -1)
3106            {
3107              Q.sig = p_One(currRing);
3108              p_SetExpV(Q.sig, vv, currRing);
3109              // F->m[i-1] corresponds to index i
3110              p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3111              p_SetComp(Q.sig, i, currRing);
3112              poly help = p_Copy(strat->P.sig,currRing);
3113              p_ExpVectorAdd(help,strat->S[pos],currRing);
3114              Q.sig = p_Add_q(Q.sig,help,currRing);
3115              if (strat->sbaOrder == 0)
3116              {
3117                if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3118                {
3119                  pos = posInSyz(strat, Q.sig);
3120                  enterSyz(Q, strat, pos);
3121                }
3122              }
3123              else
3124              {
3125                pos = posInSyz(strat, Q.sig);
3126                enterSyz(Q, strat, pos);
3127              }
3128            }
3129          }
3130          //printf("++ -- done adding syzygies -- ++\n");
3131        }
3132      }
3133//#if 1
3134#if DEBUGF50
3135    printf("---------------------------\n");
3136    Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3137    PrintS("LEAD POLY:  "); pWrite(pHead(strat->S[strat->sl]));
3138    PrintS("SIGNATURE:  "); pWrite(strat->sig[strat->sl]);
3139#endif
3140      /*
3141      if (newrules)
3142      {
3143        newrules  = FALSE;
3144      }
3145      */
3146#if 0
3147      int pl=pLength(strat->P.p);
3148      if (pl==1)
3149      {
3150        //if (TEST_OPT_PROT)
3151        //PrintS("<1>");
3152      }
3153      else if (pl==2)
3154      {
3155        //if (TEST_OPT_PROT)
3156        //PrintS("<2>");
3157      }
3158#endif
3159      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3160//      Print("[%d]",hilbeledeg);
3161      if (strat->P.lcm!=NULL)
3162#ifdef HAVE_RINGS
3163        pLmDelete(strat->P.lcm);
3164#else
3165        pLmFree(strat->P.lcm);
3166#endif
3167      if (strat->sl>srmax) srmax = strat->sl;
3168    }
3169    else
3170    {
3171      case_when_red_result_changed:
3172      // adds signature of the zero reduction to
3173      // strat->syz. This is the leading term of
3174      // syzygy and can be used in syzCriterion()
3175      // the signature is added if and only if the
3176      // pair was not detected by the rewritten criterion in strat->red = redSig
3177      if (red_result!=2)
3178      {
3179#if SBA_PRINT_ZERO_REDUCTIONS
3180        zeroreductions++;
3181#endif
3182        if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3183        {
3184          //Catch the case when p = 0, sig = 0
3185        }
3186        else
3187        {
3188          int pos = posInSyz(strat, strat->P.sig);
3189          enterSyz(strat->P, strat, pos);
3190  //#if 1
3191  #ifdef DEBUGF5
3192          Print("ADDING STUFF TO SYZ :  ");
3193          //pWrite(strat->P.p);
3194          pWrite(strat->P.sig);
3195  #endif
3196        }
3197      }
3198      if (strat->P.p1 == NULL && strat->minim > 0)
3199      {
3200        p_Delete(&strat->P.p2, currRing, strat->tailRing);
3201      }
3202    }
3203
3204#ifdef KDEBUG
3205    memset(&(strat->P), 0, sizeof(strat->P));
3206#endif /* KDEBUG */
3207    kTest_TS(strat);
3208  }
3209  #if 0
3210  if(strat->sigdrop)
3211    printf("\nSigDrop!\n");
3212  else
3213    printf("\nEnded with no SigDrop\n");
3214  #endif
3215// Clean strat->P for the next sba call
3216  if(rField_is_Ring(currRing) && strat->sigdrop)
3217  {
3218    //This is used to know how many elements can we directly add to S in the next run
3219    if(strat->P.sig != NULL)
3220      strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3221    //else we already set it at the beggining of the loop
3222    #ifdef KDEBUG
3223    memset(&(strat->P), 0, sizeof(strat->P));
3224    #endif /* KDEBUG */
3225  }
3226#ifdef KDEBUG
3227  if (TEST_OPT_DEBUG) messageSets(strat);
3228#endif /* KDEBUG */
3229
3230  if (TEST_OPT_SB_1)
3231  {
3232    if(!rField_is_Ring(currRing))
3233    {
3234      int k=1;
3235      int j;
3236      while(k<=strat->sl)
3237      {
3238        j=0;
3239        loop
3240        {
3241          if (j>=k) break;
3242          clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3243          j++;
3244        }
3245        k++;
3246      }
3247    }
3248  }
3249  /* complete reduction of the standard basis--------- */
3250  if (TEST_OPT_REDSB)
3251  {
3252    completeReduce(strat);
3253    if (strat->completeReduce_retry)
3254    {
3255      // completeReduce needed larger exponents, retry
3256      // to reduce with S (instead of T)
3257      // and in currRing (instead of strat->tailRing)
3258#ifdef HAVE_TAIL_RING
3259      if(currRing->bitmask>strat->tailRing->bitmask)
3260      {
3261        strat->completeReduce_retry=FALSE;
3262        cleanT(strat);strat->tailRing=currRing;
3263        int i;
3264        for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3265        completeReduce(strat);
3266      }
3267      if (strat->completeReduce_retry)
3268#endif
3269        Werror("exponent bound is %ld",currRing->bitmask);
3270    }
3271  }
3272  else if (TEST_OPT_PROT) PrintLn();
3273
3274#if SBA_PRINT_SIZE_SYZ
3275  // that is correct, syzl is counting one too far
3276  size_syz = strat->syzl;
3277#endif
3278//  if (TEST_OPT_WEIGHTM)
3279//  {
3280//    pRestoreDegProcs(pFDegOld, pLDegOld);
3281//    if (ecartWeights)
3282//    {
3283//      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3284//      ecartWeights=NULL;
3285//    }
3286//  }
3287  if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3288  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3289#if SBA_PRINT_SIZE_G
3290  size_g_non_red  = IDELEMS(strat->Shdl);
3291#endif
3292  if(!rField_is_Ring(currRing))
3293      exitSba(strat);
3294  // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3295  #ifdef HAVE_RINGS
3296  int k;
3297  if(rField_is_Ring(currRing))
3298  {
3299    //for(k = strat->sl;k>=0;k--)
3300    //  {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3301    k = strat->Ll;
3302    #if 1
3303    // 1 - adds just the unused ones, 0 - adds everthing
3304    for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3305    {
3306      //printf("\nDeleted k = %i, %p\n",k,strat->L[k].p);pWrite(strat->L[k].p);pWrite(strat->L[k].p1);pWrite(strat->L[k].p2);
3307      deleteInL(strat->L,&strat->Ll,k,strat);
3308    }
3309    #endif
3310    //for(int kk = strat->sl;kk>=0;kk--)
3311    //  {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3312    //idPrint(strat->Shdl);
3313    //printf("\nk = %i\n",k);
3314    for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3315    {
3316      //printf("\nAdded k = %i\n",k);
3317      strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3318      //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3319    }
3320  }
3321  // Find the "sigdrop element" and put the same signature as the previous one - do we really need this?? - now i put it on the 0 position - no more comparing needed
3322  #if 0
3323  if(strat->sigdrop && rField_is_Ring(currRing))
3324  {
3325    for(k=strat->sl;k>=0;k--)
3326    {
3327      printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3328      if(strat->sig[k] == NULL)
3329        strat->sig[k] = pCopy(strat->sig[k-1]);
3330    }
3331  }
3332  #endif
3333  #endif
3334  //Never do this - you will damage S
3335  //idSkipZeroes(strat->Shdl);
3336  //idPrint(strat->Shdl);
3337
3338  if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3339  {
3340    rChangeCurrRing (currRingOld);
3341    F0          = idrMoveR (F1, sRing, currRing);
3342    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3343    rChangeCurrRing (sRing);
3344    if(rField_is_Ring(currRing))
3345      exitSba(strat);
3346    rChangeCurrRing (currRingOld);
3347    if(strat->tailRing == sRing)
3348      strat->tailRing = currRing;
3349    rDelete (sRing);
3350  }
3351  if(rField_is_Ring(currRing) && !strat->sigdrop)
3352    id_DelDiv(strat->Shdl, currRing);
3353  if(!rField_is_Ring(currRing))
3354    id_DelDiv(strat->Shdl, currRing);
3355  idSkipZeroes(strat->Shdl);
3356  idTest(strat->Shdl);
3357
3358#if SBA_PRINT_SIZE_G
3359  size_g   = IDELEMS(strat->Shdl);
3360#endif
3361#ifdef DEBUGF5
3362  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3363  int oo = 0;
3364  while (oo<IDELEMS(strat->Shdl))
3365  {
3366    printf(" %d.   ",oo+1);
3367    pWrite(pHead(strat->Shdl->m[oo]));
3368    oo++;
3369  }
3370#endif
3371#if SBA_PRINT_ZERO_REDUCTIONS
3372  printf("----------------------------------------------------------\n");
3373  printf("ZERO REDUCTIONS:            %ld\n",zeroreductions);
3374  zeroreductions  = 0;
3375#endif
3376#if SBA_PRINT_REDUCTION_STEPS
3377  printf("----------------------------------------------------------\n");
3378  printf("S-REDUCTIONS:               %ld\n",sba_reduction_steps);
3379#endif
3380#if SBA_PRINT_OPERATIONS
3381  printf("OPERATIONS:                 %ld\n",sba_operations);
3382#endif
3383#if SBA_PRINT_REDUCTION_STEPS
3384  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3385  printf("INTERREDUCTIONS:            %ld\n",sba_interreduction_steps);
3386#endif
3387#if SBA_PRINT_OPERATIONS
3388  printf("INTERREDUCTION OPERATIONS:  %ld\n",sba_interreduction_operations);
3389#endif
3390#if SBA_PRINT_REDUCTION_STEPS
3391  printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3392  printf("ALL REDUCTIONS:             %ld\n",sba_reduction_steps+sba_interreduction_steps);
3393  sba_interreduction_steps  = 0;
3394  sba_reduction_steps       = 0;
3395#endif
3396#if SBA_PRINT_OPERATIONS
3397  printf("ALL OPERATIONS:             %ld\n",sba_operations+sba_interreduction_operations);
3398  sba_interreduction_operations = 0;
3399  sba_operations                = 0;
3400#endif
3401#if SBA_PRINT_SIZE_G
3402  printf("----------------------------------------------------------\n");
3403  printf("SIZE OF G:                  %d / %d\n",size_g,size_g_non_red);
3404  size_g          = 0;
3405  size_g_non_red  = 0;
3406#endif
3407#if SBA_PRINT_SIZE_SYZ
3408  printf("SIZE OF SYZ:                %ld\n",size_syz);
3409  printf("----------------------------------------------------------\n");
3410  size_syz  = 0;
3411#endif
3412#if SBA_PRINT_PRODUCT_CRITERION
3413  printf("PRODUCT CRITERIA:           %ld\n",product_criterion);
3414  product_criterion = 0;
3415#endif
3416  return (strat->Shdl);
3417}
3418
3419poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3420{
3421  assume(q!=NULL);
3422  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3423
3424// lazy_reduce flags: can be combined by |
3425//#define KSTD_NF_LAZY   1
3426  // do only a reduction of the leading term
3427//#define KSTD_NF_NONORM 4
3428  // only global: avoid normalization, return a multiply of NF
3429  poly   p;
3430
3431  //if ((idIs0(F))&&(Q==NULL))
3432  //  return pCopy(q); /*F=0*/
3433  //strat->ak = idRankFreeModule(F);
3434  /*- creating temp data structures------------------- -*/
3435  BITSET save1;
3436  SI_SAVE_OPT1(save1);
3437  si_opt_1|=Sy_bit(OPT_REDTAIL);
3438  initBuchMoraCrit(strat);
3439  strat->initEcart = initEcartBBA;
3440  strat->enterS = enterSBba;
3441#ifndef NO_BUCKETS
3442  strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3443#endif
3444  /*- set S -*/
3445  strat->sl = -1;
3446  /*- init local data struct.---------------------------------------- -*/
3447  /*Shdl=*/initS(F,Q,strat);
3448  /*- compute------------------------------------------------------- -*/
3449  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3450  //{
3451  //  for (i=strat->sl;i>=0;i--)
3452  //    pNorm(strat->S[i]);
3453  //}
3454  kTest(strat);
3455  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3456  if (BVERBOSE(23)) kDebugPrint(strat);
3457  int max_ind;
3458  p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3459  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3460  {
3461    if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3462    if (rField_is_Ring(currRing))
3463    {
3464      p = redtailBba_Z(p,max_ind,strat);
3465    }
3466    else
3467    {
3468      si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3469      p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3470    }
3471  }
3472  /*- release temp data------------------------------- -*/
3473  assume(strat->L==NULL); /* strat->L unused */
3474  assume(strat->B==NULL); /* strat->B unused */
3475  omFree(strat->sevS);
3476  omFree(strat->ecartS);
3477  assume(strat->T==NULL);//omfree(strat->T);
3478  assume(strat->sevT==NULL);//omfree(strat->sevT);
3479  assume(strat->R==NULL);//omfree(strat->R);
3480  omfree(strat->S_2_R);
3481  omfree(strat->fromQ);
3482  idDelete(&strat->Shdl);
3483  SI_RESTORE_OPT1(save1);
3484  if (TEST_OPT_PROT) PrintLn();
3485  return p;
3486}
3487
3488poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3489{
3490  assume(q!=NULL);
3491  assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3492
3493// lazy_reduce flags: can be combined by |
3494//#define KSTD_NF_LAZY   1
3495  // do only a reduction of the leading term
3496//#define KSTD_NF_NONORM 4
3497  // only global: avoid normalization, return a multiply of NF
3498  poly   p;
3499
3500  //if ((idIs0(F))&&(Q==NULL))
3501  //  return pCopy(q); /*F=0*/
3502  //strat->ak = idRankFreeModule(F);
3503  /*- creating temp data structures------------------- -*/
3504  BITSET save1;
3505  SI_SAVE_OPT1(save1);
3506  si_opt_1|=Sy_bit(OPT_REDTAIL);
3507  initBuchMoraCrit(strat);
3508  strat->initEcart = initEcartBBA;
3509  strat->enterS = enterSBba;
3510#ifndef NO_BUCKETS
3511  strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3512#endif
3513  /*- set S -*/
3514  strat->sl = -1;
3515  /*- init local data struct.---------------------------------------- -*/
3516  /*Shdl=*/initS(F,Q,strat);
3517  /*- compute------------------------------------------------------- -*/
3518  //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3519  //{
3520  //  for (i=strat->sl;i>=0;i--)
3521  //    pNorm(strat->S[i]);
3522  //}
3523  kTest(strat);
3524  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3525  if (BVERBOSE(23)) kDebugPrint(strat);
3526  int max_ind;
3527  p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3528  if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3529  {
3530    if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3531    if (rField_is_Ring(currRing))
3532    {
3533      p = redtailBba_Z(p,max_ind,strat);
3534    }
3535    else
3536    {
3537      si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3538      p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3539      //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3540    }
3541  }
3542  /*- release temp data------------------------------- -*/
3543  assume(strat->L==NULL); /* strat->L unused */
3544  assume(strat->B==NULL); /* strat->B unused */
3545  omFree(strat->sevS);
3546  omFree(strat->ecartS);
3547  assume(strat->T==NULL);//omfree(strat->T);
3548  assume(strat->sevT==NULL);//omfree(strat->sevT);
3549  assume(strat->R==NULL);//omfree(strat->R);
3550  omfree(strat->S_2_R);
3551  omfree(strat->fromQ);
3552  idDelete(&strat->Shdl);
3553  SI_RESTORE_OPT1(save1);
3554  if (TEST_OPT_PROT) PrintLn();
3555  return p;
3556}
3557
3558ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3559{
3560  assume(!idIs0(q));
3561  assume(!(idIs0(F)&&(Q==NULL)));
3562// lazy_reduce flags: can be combined by |
3563//#define KSTD_NF_LAZY   1
3564  // do only a reduction of the leading term
3565//#define KSTD_NF_NONORM 4
3566  // only global: avoid normalization, return a multiply of NF
3567  poly   p;
3568  int   i;
3569  ideal res;
3570  int max_ind;
3571
3572  //if (idIs0(q))
3573  //  return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3574  //if ((idIs0(F))&&(Q==NULL))
3575  //  return idCopy(q); /*F=0*/
3576  //strat->ak = idRankFreeModule(F);
3577  /*- creating temp data structures------------------- -*/
3578  BITSET save1;
3579  SI_SAVE_OPT1(save1);
3580  si_opt_1|=Sy_bit(OPT_REDTAIL);
3581  initBuchMoraCrit(strat);
3582  strat->initEcart = initEcartBBA;
3583  strat->enterS = enterSBba;
3584  /*- set S -*/
3585  strat->sl = -1;
3586#ifndef NO_BUCKETS
3587  strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3588#endif
3589  /*- init local data struct.---------------------------------------- -*/
3590  /*Shdl=*/initS(F,Q,strat);
3591  /*- compute------------------------------------------------------- -*/
3592  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3593  si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3594  for (i=IDELEMS(q)-1; i>=0; i--)
3595  {
3596    if (q->m[i]!=NULL)
3597    {
3598      if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3599      p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3600      if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3601      {
3602        if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3603        if (rField_is_Ring(currRing))
3604        {
3605          p = redtailBba_Z(p,max_ind,strat);
3606        }
3607        else
3608        {
3609          p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3610        }
3611      }
3612      res->m[i]=p;
3613    }
3614    //else
3615    //  res->m[i]=NULL;
3616  }
3617  /*- release temp data------------------------------- -*/
3618  assume(strat->L==NULL); /* strat->L unused */
3619  assume(strat->B==NULL); /* strat->B unused */
3620  omFree(strat->sevS);
3621  omFree(strat->ecartS);
3622  assume(strat->T==NULL);//omfree(strat->T);
3623  assume(strat->sevT==NULL);//omfree(strat->sevT);
3624  assume(strat->R==NULL);//omfree(strat->R);
3625  omfree(strat->S_2_R);
3626  omfree(strat->fromQ);
3627  idDelete(&strat->Shdl);
3628  SI_RESTORE_OPT1(save1);
3629  if (TEST_OPT_PROT) PrintLn();
3630  return res;
3631}
3632
3633ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3634{
3635  assume(!idIs0(q));
3636  assume(!(idIs0(F)&&(Q==NULL)));
3637// lazy_reduce flags: can be combined by |
3638//#define KSTD_NF_LAZY   1
3639  // do only a reduction of the leading term
3640//#define KSTD_NF_NONORM 4
3641  // only global: avoid normalization, return a multiply of NF
3642  poly   p;
3643  int   i;
3644  ideal res;
3645  int max_ind;
3646
3647  //if (idIs0(q))
3648  //  return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3649  //if ((idIs0(F))&&(Q==NULL))
3650  //  return idCopy(q); /*F=0*/
3651  //strat->ak = idRankFreeModule(F);
3652  /*- creating temp data structures------------------- -*/
3653  BITSET save1;
3654  SI_SAVE_OPT1(save1);
3655  si_opt_1|=Sy_bit(OPT_REDTAIL);
3656  initBuchMoraCrit(strat);
3657  strat->initEcart = initEcartBBA;
3658  strat->enterS = enterSBba;
3659  /*- set S -*/
3660  strat->sl = -1;
3661#ifndef NO_BUCKETS
3662  strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3663#endif
3664  /*- init local data struct.---------------------------------------- -*/
3665  /*Shdl=*/initS(F,Q,strat);
3666  /*- compute------------------------------------------------------- -*/
3667  res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3668  si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3669  for (i=IDELEMS(q)-1; i>=0; i--)
3670  {
3671    if (q->m[i]!=NULL)
3672    {
3673      if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3674      p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3675      if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3676      {
3677        if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3678        if (rField_is_Ring(currRing))
3679        {
3680          p = redtailBba_Z(p,max_ind,strat);
3681        }
3682        else
3683        {
3684          p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3685        }
3686      }
3687      res->m[i]=p;
3688    }
3689    //else
3690    //  res->m[i]=NULL;
3691  }
3692  /*- release temp data------------------------------- -*/
3693  assume(strat->L==NULL); /* strat->L unused */
3694  assume(strat->B==NULL); /* strat->B unused */
3695  omFree(strat->sevS);
3696  omFree(strat->ecartS);
3697  assume(strat->T==NULL);//omfree(strat->T);
3698  assume(strat->sevT==NULL);//omfree(strat->sevT);
3699  assume(strat->R==NULL);//omfree(strat->R);
3700  omfree(strat->S_2_R);
3701  omfree(strat->fromQ);
3702  idDelete(&strat->Shdl);
3703  SI_RESTORE_OPT1(save1);
3704  if (TEST_OPT_PROT) PrintLn();
3705  return res;
3706}
3707
3708#if F5C
3709/*********************************************************************
3710* interrreduction step of the signature-based algorithm:
3711* 1. all strat->S are interpreted as new critical pairs
3712* 2. those pairs need to be completely reduced by the usual (non sig-
3713*    safe) reduction process (including tail reductions)
3714* 3. strat->S and strat->T are completely new computed in these steps
3715********************************************************************/
3716void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
3717          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
3718          intvec *w,intvec *hilb )
3719{
3720  int Ll_old, red_result = 1;
3721  int pos  = 0;
3722  hilbeledeg=1;
3723  hilbcount=0;
3724  minimcnt=0;
3725  srmax = 0; // strat->sl is 0 at this point
3726  reduc = olddeg = lrmax = 0;
3727  // we cannot use strat->T anymore
3728  //cleanT(strat);
3729  //strat->tl = -1;
3730  Ll_old    = strat->Ll;
3731  while (strat->tl >= 0)
3732  {
3733    if(!strat->T[strat->tl].is_redundant)
3734    {
3735      LObject h;
3736      h.p = strat->T[strat->tl].p;
3737      h.tailRing = strat->T[strat->tl].tailRing;
3738      h.t_p = strat->T[strat->tl].t_p;
3739      if (h.p!=NULL)
3740      {
3741        if (currRing->OrdSgn==-1)
3742        {
3743          cancelunit(&h);
3744          deleteHC(&h, strat);
3745        }
3746        if (h.p!=NULL)
3747        {
3748          if (TEST_OPT_INTSTRATEGY)
3749          {
3750            h.pCleardenom(); // also does remove Content
3751          }
3752          else
3753          {
3754            h.pNorm();
3755          }
3756          strat->initEcart(&h);
3757          if(rField_is_Ring(currRing))
3758            pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
3759          else
3760            pos = strat->Ll+1;
3761          h.sev = pGetShortExpVector(h.p);
3762          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
3763        }
3764      }
3765    }
3766    strat->tl--;
3767  }
3768  strat->sl = -1;
3769#if 0
3770//#ifdef HAVE_TAIL_RING
3771  if(!rField_is_Ring())  // create strong gcd poly computes with tailring and S[i] ->to be fixed
3772    kStratInitChangeTailRing(strat);
3773#endif
3774  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
3775  //strat->sl = -1;
3776  /* picks the last element from the lazyset L */
3777  while (strat->Ll>Ll_old)
3778  {
3779    strat->P = strat->L[strat->Ll];
3780    strat->Ll--;
3781//#if 1
3782#ifdef DEBUGF5
3783    PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
3784    PrintS("-------------------------------------------------\n");
3785    pWrite(pHead(strat->P.p));
3786    pWrite(pHead(strat->P.p1));
3787    pWrite(pHead(strat->P.p2));
3788    printf("%d\n",strat->tl);
3789    PrintS("-------------------------------------------------\n");
3790#endif
3791    if (pNext(strat->P.p) == strat->tail)
3792    {
3793      // deletes the short spoly
3794      if (rField_is_Ring(currRing))
3795        pLmDelete(strat->P.p);
3796      else
3797        pLmFree(strat->P.p);
3798
3799      // TODO: needs some masking
3800      // TODO: masking needs to vanish once the signature
3801      //       sutff is completely implemented
3802      strat->P.p = NULL;
3803      poly m1 = NULL, m2 = NULL;
3804
3805      // check that spoly creation is ok
3806      while (strat->tailRing != currRing &&
3807          !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3808      {
3809        assume(m1 == NULL && m2 == NULL);
3810        // if not, change to a ring where exponents are at least
3811        // large enough
3812        if (!kStratChangeTailRing(strat))
3813        {
3814          WerrorS("OVERFLOW...");
3815          break;
3816        }
3817      }
3818      // create the real one
3819      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3820          strat->tailRing, m1, m2, strat->R);
3821    }
3822    else if (strat->P.p1 == NULL)
3823    {
3824      if (strat->minim > 0)
3825        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3826      // for input polys, prepare reduction
3827      if(!rField_is_Ring(currRing))
3828        strat->P.PrepareRed(strat->use_buckets);
3829    }
3830
3831    if (strat->P.p == NULL && strat->P.t_p == NULL)
3832    {
3833      red_result = 0;
3834    }
3835    else
3836    {
3837      if (TEST_OPT_PROT)
3838        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3839            &olddeg,&reduc,strat, red_result);
3840
3841#ifdef DEBUGF5
3842      PrintS("Poly before red: ");
3843      pWrite(strat->P.p);
3844#endif
3845      /* complete reduction of the element chosen from L */
3846      red_result = strat->red2(&strat->P,strat);
3847      if (errorreported)  break;
3848    }
3849
3850    if (strat->overflow)
3851    {
3852      if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3853    }
3854
3855    // reduction to non-zero new poly
3856    if (red_result == 1)
3857    {
3858      // get the polynomial (canonicalize bucket, make sure P.p is set)
3859      strat->P.GetP(strat->lmBin);
3860      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3861      // but now, for entering S, T, we reset it
3862      // in the inhomogeneous case: FDeg == pFDeg
3863      if (strat->homog) strat->initEcart(&(strat->P));
3864
3865      /* statistic */
3866      if (TEST_OPT_PROT) PrintS("s");
3867      int pos;
3868      #if 1
3869      if(!rField_is_Ring(currRing))
3870        pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3871      else
3872        pos = posInSMonFirst(strat,strat->sl,strat->P.p);
3873      #else
3874      pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3875      #endif
3876      // reduce the tail and normalize poly
3877      // in the ring case we cannot expect LC(f) = 1,
3878      // therefore we call pCleardenom instead of pNorm
3879#if F5CTAILRED
3880      BOOLEAN withT = TRUE;
3881      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
3882      {
3883        strat->P.pCleardenom();
3884        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3885        {
3886          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3887          strat->P.pCleardenom();
3888        }
3889      }
3890      else
3891      {
3892        strat->P.pNorm();
3893        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3894          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3895      }
3896#endif
3897#ifdef KDEBUG
3898      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3899#endif /* KDEBUG */
3900
3901      // min_std stuff
3902      if ((strat->P.p1==NULL) && (strat->minim>0))
3903      {
3904        if (strat->minim==1)
3905        {
3906          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3907          p_Delete(&strat->P.p2, currRing, strat->tailRing);
3908        }
3909        else
3910        {
3911          strat->M->m[minimcnt]=strat->P.p2;
3912          strat->P.p2=NULL;
3913        }
3914        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3915          pNext(strat->M->m[minimcnt])
3916            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3917                strat->tailRing, currRing,
3918                currRing->PolyBin);
3919        minimcnt++;
3920      }
3921
3922      // enter into S, L, and T
3923      // here we need to recompute new signatures, but those are trivial ones
3924      if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3925      {
3926        enterT(strat->P, strat);
3927        // posInS only depends on the leading term
3928        strat->enterS(strat->P, pos, strat, strat->tl);
3929//#if 1
3930#ifdef DEBUGF5
3931        PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
3932        pWrite(pHead(strat->S[strat->sl]));
3933        pWrite(strat->sig[strat->sl]);
3934#endif
3935        if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3936      }
3937      //      Print("[%d]",hilbeledeg);
3938      if (strat->P.lcm!=NULL)
3939#ifdef HAVE_RINGS
3940        pLmDelete(strat->P.lcm);
3941#else
3942      pLmFree(strat->P.lcm);
3943#endif
3944      if (strat->sl>srmax) srmax = strat->sl;
3945    }
3946    else
3947    {
3948      // adds signature of the zero reduction to
3949      // strat->syz. This is the leading term of
3950      // syzygy and can be used in syzCriterion()
3951      // the signature is added if and only if the
3952      // pair was not detected by the rewritten criterion in strat->red = redSig
3953      if (strat->P.p1 == NULL && strat->minim > 0)
3954      {
3955        p_Delete(&strat->P.p2, currRing, strat->tailRing);
3956      }
3957    }
3958
3959#ifdef KDEBUG
3960    memset(&(strat->P), 0, sizeof(strat->P));
3961#endif /* KDEBUG */
3962  }
3963  int cc = 0;
3964  while (cc<strat->tl+1)
3965  {
3966    strat->T[cc].sig        = pOne();
3967    p_SetComp(strat->T[cc].sig,cc+1,currRing);
3968    strat->T[cc].sevSig     = pGetShortExpVector(strat->T[cc].sig);
3969    strat->sig[cc]          = strat->T[cc].sig;
3970    strat->sevSig[cc]       = strat->T[cc].sevSig;
3971    strat->T[cc].is_sigsafe = TRUE;
3972    cc++;
3973  }
3974  strat->max_lower_index = strat->tl;
3975  // set current signature index of upcoming iteration step
3976  // NOTE:  this needs to be set here, as otherwise initSyzRules cannot compute
3977  //        the corresponding syzygy rules correctly
3978  strat->currIdx = cc+1;
3979  for (int cd=strat->Ll; cd>=0; cd--)
3980  {
3981    p_SetComp(strat->L[cd].sig,cc+1,currRing);
3982    cc++;
3983  }
3984  for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
3985    strat->Shdl->m[cc]  = NULL;
3986  #if 0
3987  printf("\nAfter f5c sorting\n");
3988  for(int i=0;i<=strat->sl;i++)
3989  pWrite(pHead(strat->S[i]));
3990  getchar();
3991  #endif
3992//#if 1
3993#if DEBUGF5
3994  PrintS("------------------- STRAT S ---------------------\n");
3995  cc = 0;
3996  while (cc<strat->tl+1)
3997  {
3998    pWrite(pHead(strat->S[cc]));
3999    pWrite(strat->sig[cc]);
4000    printf("- - - - - -\n");
4001    cc++;
4002  }
4003  PrintS("-------------------------------------------------\n");
4004  PrintS("------------------- STRAT T ---------------------\n");
4005  cc = 0;
4006  while (cc<strat->tl+1)
4007  {
4008    pWrite(pHead(strat->T[cc].p));
4009    pWrite(strat->T[cc].sig);
4010    printf("- - - - - -\n");
4011    cc++;
4012  }
4013  PrintS("-------------------------------------------------\n");
4014  PrintS("------------------- STRAT L ---------------------\n");
4015  cc = 0;
4016  while (cc<strat->Ll+1)
4017  {
4018    pWrite(pHead(strat->L[cc].p));
4019    pWrite(pHead(strat->L[cc].p1));
4020    pWrite(pHead(strat->L[cc].p2));
4021    pWrite(strat->L[cc].sig);
4022    printf("- - - - - -\n");
4023    cc++;
4024  }
4025  PrintS("-------------------------------------------------\n");
4026  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4027#endif
4028
4029}
4030#endif
4031
4032/* shiftgb stuff */
4033#ifdef HAVE_SHIFTBBA
4034
4035
4036ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV)
4037{
4038  int   red_result = 1;
4039  int   olddeg,reduc;
4040  int hilbeledeg=1,hilbcount=0,minimcnt=0;
4041  BOOLEAN withT = TRUE; // very important for shifts
4042
4043  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit, NO CHANGES */
4044  if(rField_is_Ring(currRing))
4045    initBuchMoraPosRing(strat);
4046  else
4047    initBuchMoraPos(strat); /*NO CHANGES YET: perhaps later*/
4048  initHilbCrit(F,Q,&hilb,strat); /*NO CHANGES*/
4049  initBbaShift(strat); /* DONE */
4050  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4051  /*Shdl=*/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
4052  updateSShift(strat,uptodeg,lV); /* initializes T */
4053
4054  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4055  reduc = olddeg = 0;
4056  strat->lV=lV;
4057
4058#ifndef NO_BUCKETS
4059  if (!TEST_OPT_NOT_BUCKETS)
4060    strat->use_buckets = 1;
4061#endif
4062
4063  // redtailBBa against T for inhomogenous input
4064  //  if (!TEST_OPT_OLDSTD)
4065  //    withT = ! strat->homog;
4066
4067  // strat->posInT = posInT_pLength;
4068  kTest_TS(strat);
4069
4070#ifdef HAVE_TAIL_RING
4071  kStratInitChangeTailRing(strat);
4072#endif
4073
4074  /* compute------------------------------------------------------- */
4075  while (strat->Ll >= 0)
4076  {
4077#ifdef KDEBUG
4078    if (TEST_OPT_DEBUG) messageSets(strat);
4079#endif
4080    if (strat->Ll== 0) strat->interpt=TRUE;
4081    if (TEST_OPT_DEGBOUND
4082        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4083            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4084    {
4085      /*
4086       *stops computation if
4087       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4088       *a predefined number Kstd1_deg
4089       */
4090      while ((strat->Ll >= 0)
4091        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4092        && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4093            || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4094        )
4095        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4096      if (strat->Ll<0) break;
4097      else strat->noClearS=TRUE;
4098    }
4099    /* picks the last element from the lazyset L */
4100    strat->P = strat->L[strat->Ll];
4101    strat->Ll--;
4102
4103    if (pNext(strat->P.p) == strat->tail)
4104    {
4105      // deletes the short spoly
4106      pLmFree(strat->P.p);
4107      strat->P.p = NULL;
4108      poly m1 = NULL, m2 = NULL;
4109
4110      // check that spoly creation is ok
4111      while (strat->tailRing != currRing &&
4112             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4113      {
4114        assume(m1 == NULL && m2 == NULL);
4115        // if not, change to a ring where exponents are at least
4116        // large enough
4117        kStratChangeTailRing(strat);
4118      }
4119      // create the real one
4120      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4121                    strat->tailRing, m1, m2, strat->R);
4122    }
4123    else if (strat->P.p1 == NULL)
4124    {
4125      if (strat->minim > 0)
4126        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4127      // for input polys, prepare reduction
4128      strat->P.PrepareRed(strat->use_buckets);
4129    }
4130
4131    poly qq;
4132
4133    /* here in the nonhomog case we shrink the new spoly */
4134
4135    if ( ! strat->homog)
4136    {
4137      strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
4138      /* in the nonhomog case we have to shrink the polynomial */
4139      assume(strat->P.t_p!=NULL);
4140      qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
4141      if (qq != NULL)
4142      {
4143         /* we're here if Shrink is nonzero */
4144        //         strat->P.p =  NULL;
4145        //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
4146        strat->P.p   =  NULL; // is not set by Delete
4147        strat->P.t_p =  qq;
4148        strat->P.GetP(strat->lmBin);
4149        // update sev and length
4150        strat->initEcart(&(strat->P));
4151        strat->P.sev = pGetShortExpVector(strat->P.p);
4152//         strat->P.FDeg = strat->P.pFDeg();
4153//         strat->P.length = strat->P.pLDeg();
4154//         strat->P.pLength =strat->P.GetpLength(); //pLength(strat->P.p);
4155      }
4156      else
4157      {
4158         /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
4159#ifdef KDEBUG
4160         if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0\n");}
4161#endif
4162         //         strat->P.Delete();  // cause error
4163         strat->P.p = NULL;
4164         strat->P.t_p = NULL;
4165           //         strat->P.p = NULL; // or delete strat->P.p ?
4166       }
4167    }
4168      /* end shrinking poly in the nonhomog case */
4169
4170    if (strat->P.p == NULL && strat->P.t_p == NULL)
4171    {
4172      red_result = 0;
4173    }
4174    else
4175    {
4176      if (TEST_OPT_PROT)
4177        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4178                &olddeg,&reduc,strat, red_result);
4179
4180      /* reduction of the element chosen from L */
4181      red_result = strat->red(&strat->P,strat);
4182    }
4183
4184    // reduction to non-zero new poly
4185    if (red_result == 1)
4186    {
4187      /* statistic */
4188      if (TEST_OPT_PROT) PrintS("s");
4189
4190      // get the polynomial (canonicalize bucket, make sure P.p is set)
4191      strat->P.GetP(strat->lmBin);
4192
4193      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4194
4195      // reduce the tail and normalize poly
4196      if (TEST_OPT_INTSTRATEGY)
4197      {
4198        strat->P.pCleardenom();
4199        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
4200        {
4201          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4202          strat->P.pCleardenom();
4203        }
4204      }
4205      else
4206      {
4207        strat->P.pNorm();
4208        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
4209          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4210      }
4211
4212      // here we must shrink again! and optionally reduce again
4213      // or build shrink into redtailBba!
4214
4215#ifdef KDEBUG
4216      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4217#endif
4218
4219      // min_std stuff
4220      if ((strat->P.p1==NULL) && (strat->minim>0))
4221      {
4222        if (strat->minim==1)
4223        {
4224          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4225          p_Delete(&strat->P.p2, currRing, strat->tailRing);
4226        }
4227        else
4228        {
4229          strat->M->m[minimcnt]=strat->P.p2;
4230          strat->P.p2=NULL;
4231        }
4232        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4233          pNext(strat->M->m[minimcnt])
4234            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4235                                           strat->tailRing, currRing,
4236                                           currRing->PolyBin);
4237        minimcnt++;
4238      }
4239
4240    /* here in the nonhomog case we shrink the reduced poly AGAIN */
4241
4242      if ( ! strat->homog)
4243      {
4244        strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
4245        /* in the nonhomog case we have to shrink the polynomial */
4246        if (strat->P.t_p!=NULL)
4247        {
4248          qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
4249          if (qq != NULL)
4250          {
4251            /* we're here if Shrink is nonzero */
4252            //         strat->P.p =  NULL;
4253            //        strat->P.Delete(); /* deletes P.p and P.t_p */ //error
4254            strat->P.p   =  NULL; // is not set by Delete
4255            strat->P.t_p =  qq;
4256            strat->P.GetP(strat->lmBin);
4257            // update sev and length
4258            strat->initEcart(&(strat->P));
4259            strat->P.sev = pGetShortExpVector(strat->P.p);
4260          }
4261          else
4262          {
4263            /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
4264#ifdef PDEBUG
4265            if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
4266#endif
4267            //         strat->P.Delete();  // cause error
4268            strat->P.p = NULL;
4269            strat->P.t_p = NULL;
4270            //         strat->P.p = NULL; // or delete strat->P.p ?
4271            goto     red_shrink2zero;
4272          }
4273        }
4274        else
4275        {
4276          qq = p_Shrink(strat->P.p, lV, currRing); // direct shrink
4277          if (qq != NULL)
4278          {
4279            /* we're here if Shrink is nonzero */
4280            strat->P.p   =  qq;
4281            strat->P.t_p =  NULL;
4282            // update sev and length
4283            strat->initEcart(&(strat->P));
4284            strat->P.sev = pGetShortExpVector(strat->P.p);
4285          }
4286          else
4287          {
4288            /* Shrink is zero, like y(1)*y(2) - y(1)*y(3)*/
4289#ifdef PDEBUG
4290            if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
4291#endif
4292            //         strat->P.Delete();  // cause error
4293            strat->P.p = NULL;
4294            strat->P.t_p = NULL;
4295            //         strat->P.p = NULL; // or delete strat->P.p ?
4296            goto     red_shrink2zero;
4297          }
4298        }
4299      }
4300      /* end shrinking poly AGAIN in the nonhomog case */
4301
4302
4303      // enter into S, L, and T
4304      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4305      //        enterT(strat->P, strat); // this was here before Shift stuff
4306      //enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax
4307      // the default value for atT = -1 as in bba
4308      /*   strat->P.GetP(); */
4309      // because shifts are counted with .p structure // done before, but ?
4310      int atR=strat->tl+1; // enterTShift introduces T[tl+1], T[tl+2]...
4311                           // with T[tl+1]=P.p
4312      enterTShift(strat->P,strat,-1,uptodeg, lV);
4313      enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, atR,uptodeg,lV);
4314      //      enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
4315      // posInS only depends on the leading term
4316      if ((strat->P.t_p!=NULL)&&(currRing!=strat->tailRing))
4317      {
4318        // move to currRing:
4319        // need tp save t_p, as it is in also in T
4320        pNext(strat->P.p)=strat->p_shallow_copy_delete(
4321                            p_Copy(pNext(strat->P.p),strat->tailRing),
4322                            strat->tailRing, currRing,
4323                            currRing->PolyBin);
4324        strat->P.t_p=NULL;
4325      }
4326      strat->enterS(strat->P, pos, strat, atR);
4327
4328      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4329//      Print("[%d]",hilbeledeg);
4330      if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
4331    }
4332    else
4333    {
4334    red_shrink2zero:
4335      if (strat->P.p1 == NULL && strat->minim > 0)
4336      {
4337        p_Delete(&strat->P.p2, currRing, strat->tailRing);
4338      }
4339    }
4340#ifdef KDEBUG
4341    memset(&(strat->P), 0, sizeof(strat->P));
4342#endif
4343    kTest_TS(strat);
4344  }
4345#ifdef KDEBUG
4346  if (TEST_OPT_DEBUG) messageSets(strat);
4347#endif
4348  /* complete reduction of the standard basis--------- */
4349  /*  shift case: look for elt's in S such that they are divisible by elt in T */
4350  //  if (TEST_OPT_SB_1)
4351  if (TEST_OPT_REDSB)
4352  {
4353    int k=0;
4354    int j=-1;
4355    while(k<=strat->sl)
4356    {
4357//       loop
4358//       {
4359//         if (j>=k) break;
4360//         clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
4361//         j++;
4362//       }
4363      LObject Ln (strat->S[k],currRing, strat->tailRing);
4364      Ln.SetShortExpVector();
4365      j = kFindDivisibleByInT(strat, &Ln, j+1);
4366      if (j<0) {  k++; j=-1;}
4367      else
4368      {
4369        if ( pLmCmp(strat->S[k],strat->T[j].p) == 0)
4370        {
4371          j = kFindDivisibleByInT(strat, &Ln, j+1);
4372          if (j<0) {  k++; j=-1;}
4373          else
4374          {
4375            deleteInS(k,strat);
4376          }
4377        }
4378        else
4379        {
4380          deleteInS(k,strat);
4381        }
4382      }
4383    }
4384  }
4385
4386  if (TEST_OPT_REDSB)
4387  {    completeReduce(strat, TRUE); //shift: withT = TRUE
4388    if (strat->completeReduce_retry)
4389    {
4390      // completeReduce needed larger exponents, retry
4391      // to reduce with S (instead of T)
4392      // and in currRing (instead of strat->tailRing)
4393#ifdef HAVE_TAIL_RING
4394      if(currRing->bitmask>strat->tailRing->bitmask)
4395      {
4396        strat->completeReduce_retry=FALSE;
4397        cleanT(strat);strat->tailRing=currRing;
4398        int i;
4399        for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4400        completeReduce(strat);
4401      }
4402      if (strat->completeReduce_retry)
4403#endif
4404        Werror("exponent bound is %ld",currRing->bitmask);
4405    }
4406  }
4407  else if (TEST_OPT_PROT) PrintLn();
4408
4409  /* release temp data-------------------------------- */
4410  exitBuchMora(strat);
4411//  if (TEST_OPT_WEIGHTM)
4412//  {
4413//    pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4414//    if (ecartWeights)
4415//    {
4416//      omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4417//      ecartWeights=NULL;
4418//    }
4419//  }
4420  if (TEST_OPT_PROT) messageStat(hilbcount,strat);
4421  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
4422  return (strat->Shdl);
4423}
4424
4425
4426ideal freegb(ideal I, int uptodeg, int lVblock)
4427{
4428  /* todo main call */
4429
4430  /* assume: ring is prepared, ideal is copied into shifted ring */
4431  /* uptodeg and lVblock are correct - test them! */
4432
4433  /* check whether the ideal is in V */
4434
4435//  if (0)
4436  if (! ideal_isInV(I,lVblock) )
4437  {
4438    WerrorS("The input ideal contains incorrectly encoded elements! ");
4439    return(NULL);
4440  }
4441
4442  //  kStrategy strat = new skStrategy;
4443  /* ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat, int uptodeg, int lV) */
4444  /* at the moment:
4445- no quotient (check)
4446- no *w, no *hilb
4447  */
4448  /* ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
4449     int newIdeal, intvec *vw) */
4450  ideal RS = kStdShift(I,NULL, testHomog, NULL,NULL,0,0,NULL, uptodeg, lVblock);
4451    //bbaShift(I,NULL, NULL, NULL, strat, uptodeg, lVblock);
4452  idSkipZeroes(RS);
4453  return(RS);
4454}
4455
4456/*2
4457*reduces h with elements from T choosing  the first possible
4458* element in t with respect to the given pDivisibleBy
4459*/
4460int redFirstShift (LObject* h,kStrategy strat)
4461{
4462  if (h->IsNull()) return 0;
4463
4464  int at, reddeg,d;
4465  int pass = 0;
4466  int j = 0;
4467
4468  if (! strat->homog)
4469  {
4470    d = h->GetpFDeg() + h->ecart;
4471    reddeg = strat->LazyDegree+d;
4472  }
4473  h->SetShortExpVector();
4474  loop
4475  {
4476    j = kFindDivisibleByInT(strat, h);
4477    if (j < 0)
4478    {
4479      h->SetDegStuffReturnLDeg(strat->LDegLast);
4480      return 1;
4481    }
4482
4483    if (!TEST_OPT_INTSTRATEGY)
4484      strat->T[j].pNorm();
4485#ifdef KDEBUG
4486    if (TEST_OPT_DEBUG)
4487    {
4488      PrintS("reduce ");
4489      h->wrp();
4490      PrintS(" with ");
4491      strat->T[j].wrp();
4492    }
4493#endif
4494    ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
4495    if (!h->IsNull())
4496    {
4497      poly qq=p_Shrink(h->GetTP(),strat->lV,strat->tailRing);
4498      h->p=NULL;
4499      h->t_p=qq;
4500      if (qq!=NULL) h->GetP(strat->lmBin);
4501    }
4502
4503#ifdef KDEBUG
4504    if (TEST_OPT_DEBUG)
4505    {
4506      PrintS("\nto ");
4507      wrp(h->p);
4508      PrintLn();
4509    }
4510#endif
4511    if (h->IsNull())
4512    {
4513      if (h->lcm!=NULL) pLmFree(h->lcm);
4514      h->Clear();
4515      return 0;
4516    }
4517    h->SetShortExpVector();
4518
4519#if 0
4520    if ((strat->syzComp!=0) && !strat->honey)
4521    {
4522      if ((strat->syzComp>0) &&
4523          (h->Comp() > strat->syzComp))
4524      {
4525        assume(h->MinComp() > strat->syzComp);
4526#ifdef KDEBUG
4527        if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4528#endif
4529        if (strat->homog)
4530          h->SetDegStuffReturnLDeg(strat->LDegLast);
4531        return -2;
4532      }
4533    }
4534#endif
4535    if (!strat->homog)
4536    {
4537      if (!TEST_OPT_OLDSTD && strat->honey)
4538      {
4539        h->SetpFDeg();
4540        if (strat->T[j].ecart <= h->ecart)
4541          h->ecart = d - h->GetpFDeg();
4542        else
4543          h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4544
4545        d = h->GetpFDeg() + h->ecart;
4546      }
4547      else
4548        d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4549      /*- try to reduce the s-polynomial -*/
4550      pass++;
4551      /*
4552       *test whether the polynomial should go to the lazyset L
4553       *-if the degree jumps
4554       *-if the number of pre-defined reductions jumps
4555       */
4556      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4557          && ((d >= reddeg) || (pass > strat->LazyPass)))
4558      {
4559        h->SetLmCurrRing();
4560        if (strat->posInLDependsOnLength)
4561          h->SetLength(strat->length_pLength);
4562        at = strat->posInL(strat->L,strat->Ll,h,strat);
4563        if (at <= strat->Ll)
4564        {
4565          //int dummy=strat->sl;
4566          /*          if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4567          //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4568          if (kFindDivisibleByInT(strat, h) < 0)
4569            return 1;
4570          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4571#ifdef KDEBUG
4572          if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4573#endif
4574          h->Clear();
4575          return -1;
4576        }
4577      }
4578      if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4579      {
4580        reddeg = d+1;
4581        Print(".%d",d);mflush();
4582      }
4583    }
4584  }
4585}
4586
4587void initBbaShift(kStrategy strat)
4588{
4589 /* setting global variables ------------------- */
4590  strat->enterS = enterSBba; /* remains as is, we change enterT! */
4591
4592  strat->red = redFirstShift; /* no redHomog ! */
4593
4594  if (currRing->pLexOrder && strat->honey)
4595    strat->initEcart = initEcartNormal;
4596  else
4597    strat->initEcart = initEcartBBA;
4598  if (strat->honey)
4599    strat->initEcartPair = initEcartPairMora;
4600  else
4601    strat->initEcartPair = initEcartPairBba;
4602//  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
4603//  {
4604//    //interred  machen   Aenderung
4605//    pFDegOld=currRing->pFDeg;
4606//    pLDegOld=pLDeg;
4607//    //h=ggetid("ecart");
4608//    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
4609//    //{
4610//    //  ecartWeights=iv2array(IDINTVEC(h));
4611//    //}
4612//    //else
4613//    {
4614//      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
4615//      /*uses automatic computation of the ecartWeights to set them*/
4616//      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights,currRing);
4617//    }
4618//    pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
4619//    if (TEST_OPT_PROT)
4620//    {
4621//      for(int i=1; i<=rVar(currRing); i++)
4622//        Print(" %d",ecartWeights[i]);
4623//      PrintLn();
4624//      mflush();
4625//    }
4626//  }
4627}
4628#endif
Note: See TracBrowser for help on using the repository browser.