source: git/kernel/kstd2.cc @ 351415

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