source: git/kernel/GBEngine/kstd2.cc @ 115e3b

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