source: git/kernel/GBEngine/kstd2.cc @ f26b42

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