source: git/kernel/kstd2.cc @ fbc7cb

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