source: git/kernel/kstd2.cc @ 6e3023a

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