[35aab3]  1  /**************************************** 

 2  * Computer Algebra System SINGULAR * 

 3  ****************************************/ 

 4  /* 

 5  * ABSTRACT  Kernel: alg. of Buchberger 

 6  */ 

 7  

 8  // #define PDEBUG 2 

[645a19]  9  

 10  // TODO: why the following is here instead of mod2.h??? 

 11  

[35aab3]  12  // define to enable tailRings 

[60eb1d]  13  #define HAVE_TAIL_RING 

[645a19]  14  

[16f511]  15  #ifdef HAVE_CONFIG_H 

[ba5e9e]  16  #include "singularconfig.h" 

[16f511]  17  #endif /* HAVE_CONFIG_H */ 

[599326]  18  #include <kernel/mod2.h> 

[645a19]  19  

 20  #ifndef NDEBUG 

 21  # define MYTEST 0 

 22  #else /* ifndef NDEBUG */ 

 23  # define MYTEST 0 

 24  #endif /* ifndef NDEBUG */ 

 25  

[8d679fd]  26  #if MYTEST 

[645a19]  27  # ifdef HAVE_TAIL_RING 

 28  # undef HAVE_TAIL_RING 

 29  # endif // ifdef HAVE_TAIL_RING 

 30  #endif 

 31  

[35aab3]  32  // define if no buckets should be used 

 33  // #define NO_BUCKETS 

 34  

[cbc616]  35  #ifdef HAVE_PLURAL 

 36  #define PLURAL_INTERNAL_DECLARATIONS 1 

 37  #endif 

[83be980]  38  

[b3e94aa]  39  /*********************************************** 

 40  * SBA stuff  start 

 41  ***********************************************/ 

[83be980]  42  #define DEBUGF50 0 

 43  #define DEBUGF51 0 

 44  

 45  #ifdef DEBUGF5 

 46  #undef DEBUGF5 

 47  //#define DEBUGF5 1 

 48  #endif 

 49  

[15b211]  50  #define F5C 1 

[83be980]  51  #if F5C 

[f9d20d7]  52  #define F5CTAILRED 1 

[83be980]  53  #endif 

 54  

[b085fba]  55  #define SBA_TAIL_RED 0 

[f59aaa]  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 

[f9d20d7]  67  long sba_reduction_steps; 

[15b211]  68  long sba_operations; 

[f59aaa]  69  

 70  // counts interreduction steps if sba is used incrementally 

 71  long sba_interreduction_steps; 

 72  long sba_interreduction_operations; 

[b3e94aa]  73  /*********************************************** 

 74  * SBA stuff  done 

 75  ***********************************************/ 

 76  

[599326]  77  #include <kernel/kutil.h> 

[0f401f]  78  #include <misc/options.h> 

[b1dfaf]  79  #include <omalloc/omalloc.h> 

[737a68]  80  #include <kernel/polys.h> 

[599326]  81  #include <kernel/ideals.h> 

 82  #include <kernel/febase.h> 

 83  #include <kernel/kstd1.h> 

 84  #include <kernel/khstd.h> 

[210e07]  85  #include <polys/kbuckets.h> 

[fee33e]  86  #include <polys/prCopy.h> 

[35aab3]  87  //#include "cntrlc.h" 

[76cfef]  88  #include <polys/weight.h> 

[210e07]  89  #include <misc/intvec.h> 

[35aab3]  90  #ifdef HAVE_PLURAL 

[210e07]  91  #include <polys/nc/nc.h> 

[35aab3]  92  #endif 

 93  // #include "timer.h" 

 94  

[cb0fbe]  95  /* shiftgb stuff */ 

[599326]  96  #include <kernel/shiftgb.h> 

[cb0fbe]  97  

[57fad3a]  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  

[35aab3]  102  // return 1 if no divisor is found 

 103  // number of first divisor, otherwise 

 104  int 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; 

[dd2855]  109  poly p=L>p; 

 110  ring r=currRing; 

[35aab3]  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 

[391323]  152  int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L) 

[35aab3]  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)); 

[dd60f3c]  159  #if 1 

 160  int ende; 

[fe89b98]  161  if ((strat>ak>0)  currRing>pLexOrder) ende=strat>sl; 

[dd60f3c]  162  else ende=posInS(strat,*max_ind,p,0)+1; 

[f41bd9]  163  if (ende>(*max_ind)) ende=(*max_ind); 

 164  #else 

[e690a91]  165  int ende=strat>sl; 

[b2c236]  166  #endif 

[391323]  167  (*max_ind)=ende; 

[35aab3]  168  loop 

 169  { 

[efb860]  170  if (j > ende) return 1; 

[35aab3]  171  #if defined(PDEBUG)  defined(PDIV_DEBUG) 

[efb860]  172  if (p_LmShortDivisibleBy(strat>S[j], strat>sevS[j], 

[35aab3]  173  p, not_sev, currRing)) 

 174  return j; 

 175  #else 

[efb860]  176  if ( !(strat>sevS[j] & not_sev) && 

 177  p_LmDivisibleBy(strat>S[j], p, currRing)) 

[35aab3]  178  return j; 

 179  #endif 

 180  j++; 

 181  } 

 182  } 

 183  

[7ba059]  184  int 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  

[c90b43]  212  #ifdef HAVE_RINGS 

[a09a42]  213  poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing) 

 214  { 

[cea6f3]  215  // m = currRing>ch 

 216  

[a6889e]  217  if (input_p == NULL) return NULL; 

 218  

 219  poly p = input_p; 

[cea6f3]  220  poly zeroPoly = NULL; 

[994445]  221  NATNUMBER a = (NATNUMBER) pGetCoeff(p); 

[cea6f3]  222  

[fe7f527]  223  int k_ind2 = 0; 

 224  int a_ind2 = ind2(a); 

[cea6f3]  225  

[6909cfb]  226  // NATNUMBER k = 1; 

[6d09f28]  227  // of interest is only k_ind2, special routine for improvement ... TODO OLIVER 

[fe7f527]  228  for (int i = 1; i <= leadRing>N; i++) 

[a09a42]  229  { 

[fe7f527]  230  k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing)); 

[cea6f3]  231  } 

[fe7f527]  232  

[994445]  233  a = (NATNUMBER) pGetCoeff(p); 

[cea6f3]  234  

 235  number tmp1; 

 236  poly tmp2, tmp3; 

[fe7f527]  237  poly lead_mult = p_ISet(1, tailRing); 

[e533660]  238  if (n_GetChar(leadRing>cf) <= k_ind2 + a_ind2) 

[a09a42]  239  { 

[e533660]  240  int too_much = k_ind2 + a_ind2  n_GetChar(leadRing>cf); 

[fe7f527]  241  int s_exp; 

[a6889e]  242  zeroPoly = p_ISet(a, tailRing); 

[a09a42]  243  for (int i = 1; i <= leadRing>N; i++) 

 244  { 

[fe7f527]  245  s_exp = p_GetExp(p, i,leadRing); 

[388f91e]  246  if (s_exp % 2 != 0) 

[fe7f527]  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  } 

[388f91e]  255  p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing)  s_exp, tailRing); 

[994445]  256  for (NATNUMBER j = 1; j <= s_exp; j++) 

[a09a42]  257  { 

[cea6f3]  258  tmp1 = nInit(j); 

[a6889e]  259  tmp2 = p_ISet(1, tailRing); 

 260  p_SetExp(tmp2, i, 1, tailRing); 

 261  p_Setm(tmp2, tailRing); 

[a09a42]  262  if (nIsZero(tmp1)) 

[fe7f527]  263  { // should nowbe obsolet, test ! TODO OLIVER 

[a6889e]  264  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing); 

[cea6f3]  265  } 

[a09a42]  266  else 

 267  { 

[f92547]  268  tmp3 = p_NSet(nCopy(tmp1), tailRing); 

[fe7f527]  269  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing); 

[cea6f3]  270  } 

 271  } 

 272  } 

[fe7f527]  273  p_Setm(lead_mult, tailRing); 

[388f91e]  274  zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing); 

[f92547]  275  tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing); 

[977f94]  276  for (int i = 1; i <= leadRing>N; i++) 

 277  { 

[a725dae]  278  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing)); 

[cea6f3]  279  } 

[7f06cca]  280  p_Setm(tmp2, leadRing); 

 281  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing); 

[cea6f3]  282  pNext(tmp2) = zeroPoly; 

 283  return tmp2; 

 284  } 

[994445]  285  /* NATNUMBER alpha_k = twoPow(leadRing>ch  k_ind2); 

[977f94]  286  if (1 == 0 && alpha_k <= a) 

 287  { // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver 

[7f06cca]  288  zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing); 

[977f94]  289  for (int i = 1; i <= leadRing>N; i++) 

 290  { 

[994445]  291  for (NATNUMBER j = 1; j <= p_GetExp(p, i, leadRing); j++) 

[977f94]  292  { 

[7f06cca]  293  tmp1 = nInit(j); 

 294  tmp2 = p_ISet(1, tailRing); 

 295  p_SetExp(tmp2, i, 1, tailRing); 

 296  p_Setm(tmp2, tailRing); 

[977f94]  297  if (nIsZero(tmp1)) 

 298  { 

[7f06cca]  299  zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing); 

 300  } 

[977f94]  301  else 

 302  { 

[994445]  303  tmp3 = p_ISet((NATNUMBER) tmp1, tailRing); 

[7f06cca]  304  zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing); 

 305  } 

 306  } 

 307  } 

[994445]  308  tmp2 = p_ISet((NATNUMBER) pGetCoeff(zeroPoly), leadRing); 

[977f94]  309  for (int i = 1; i <= leadRing>N; i++) 

 310  { 

[a725dae]  311  pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing)); 

[7f06cca]  312  } 

 313  p_Setm(tmp2, leadRing); 

 314  zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing); 

 315  pNext(tmp2) = zeroPoly; 

 316  return tmp2; 

[6d09f28]  317  } */ 

[cea6f3]  318  return NULL; 

 319  } 

[206e158]  320  #endif 

[a6889e]  321  

[206e158]  322  

 323  #ifdef HAVE_RINGS 

[585bbcb]  324  /*2 

 325  * reduction procedure for the ring Z/2^m 

 326  */ 

[093f30e]  327  int redRing (LObject* h,kStrategy strat) 

[585bbcb]  328  { 

[8d679fd]  329  if (h>IsNull()) return 0; // spoly is zero (can only occure with zero divisors) 

 330  if (strat>tl<0) return 1; 

[cea6f3]  331  

[6909cfb]  332  int at/*,i*/; 

[d5564f8]  333  long d; 

[585bbcb]  334  int j = 0; 

 335  int pass = 0; 

[6909cfb]  336  // poly zeroPoly = NULL; 

[cea6f3]  337  

[388f91e]  338  // TODO warum SetpFDeg notwendig? 

[cea6f3]  339  h>SetpFDeg(); 

 340  assume(h>pFDeg() == h>FDeg); 

[388f91e]  341  long reddeg = h>GetpFDeg(); 

[585bbcb]  342  

[fe7f527]  343  h>SetShortExpVector(); 

[585bbcb]  344  loop 

 345  { 

[8d679fd]  346  j = kFindDivisibleByInT(strat>T, strat>sevT, strat>tl, h); 

 347  if (j < 0) return 1; 

[585bbcb]  348  

[94ebce]  349  ksReducePoly(h, &(strat>T[j]), NULL, NULL, strat); // with debug output 

[585bbcb]  350  

 351  if (h>GetLmTailRing() == NULL) 

 352  { 

[a539ad]  353  if (h>lcm!=NULL) pLmDelete(h>lcm); 

[585bbcb]  354  #ifdef KDEBUG 

 355  h>lcm=NULL; 

 356  #endif 

[8d679fd]  357  h>Clear(); 

[585bbcb]  358  return 0; 

 359  } 

 360  h>SetShortExpVector(); 

 361  d = h>SetpFDeg(); 

 362  /* try to reduce the spolynomial */ 

 363  pass++; 

[228b631]  364  if (!TEST_OPT_REDTHROUGH && 

[585bbcb]  365  (strat>Ll >= 0) && ((d > reddeg)  (pass > strat>LazyPass))) 

 366  { 

 367  h>SetLmCurrRing(); 

[8d679fd]  368  if (strat>posInLDependsOnLength) 

 369  h>SetLength(strat>length_pLength); 

[585bbcb]  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 

[cea6f3]  376  enterL(&strat>L,&strat>Ll,&strat>Lmax,*h,at); // NOT RING CHECKED OLIVER 

[585bbcb]  377  h>Clear(); 

 378  return 1; 

 379  } 

 380  } 

[8d679fd]  381  if (d != reddeg) 

[585bbcb]  382  { 

[d5564f8]  383  if (d >= strat>tailRing>bitmask) 

[f7feb7]  384  { 

[8d679fd]  385  if (h>pTotalDeg() >= strat>tailRing>bitmask) 

 386  { 

 387  strat>overflow=TRUE; 

[d5564f8]  388  //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat>tailRing>bitmask); 

[8d679fd]  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(); 

[d5564f8]  393  return 1; 

 394  } 

[f7feb7]  395  } 

 396  else if ((TEST_OPT_PROT) && (strat>Ll < 0)) 

 397  { 

[dd8a7d]  398  Print(".%ld",d);mflush(); 

[f7feb7]  399  reddeg = d; 

 400  } 

[585bbcb]  401  } 

 402  } 

 403  } 

 404  #endif 

 405  

[35aab3]  406  /*2 

 407  * reduction procedure for the homogeneous case 

 408  * and the case of a degreeordering 

 409  */ 

 410  int redHomog (LObject* h,kStrategy strat) 

 411  { 

[bdde4f4]  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; 

[225d94]  417  int i,j,at,pass, ii; 

[bdde4f4]  418  unsigned long not_sev; 

[cd4f24]  419  // long reddeg,d; 

[bdde4f4]  420  

 421  pass = j = 0; 

[cd4f24]  422  // d = reddeg = h>GetpFDeg(); 

[bdde4f4]  423  h>SetShortExpVector(); 

 424  int li; 

 425  h_p = h>GetLmTailRing(); 

 426  not_sev = ~ h>sev; 

[35aab3]  427  loop 

 428  { 

 429  j = kFindDivisibleByInT(strat>T, strat>sevT, strat>tl, h); 

[bdde4f4]  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 

[8c36a9]  440  if (TEST_OPT_LENGTH) 

[bdde4f4]  441  loop 

[35aab3]  442  { 

[bdde4f4]  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  } 

[35aab3]  460  } 

[bdde4f4]  461  #endif 

[35aab3]  462  

[bdde4f4]  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); 

[f59aaa]  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 

[35aab3]  484  

 485  #ifdef KDEBUG 

 486  if (TEST_OPT_DEBUG) 

 487  { 

[bdde4f4]  488  PrintS("\nto "); 

[35aab3]  489  h>wrp(); 

 490  PrintLn(); 

 491  } 

 492  #endif 

[bdde4f4]  493  

 494  h_p = h>GetLmTailRing(); 

 495  if (h_p == NULL) 

[35aab3]  496  { 

 497  if (h>lcm!=NULL) pLmFree(h>lcm); 

 498  #ifdef KDEBUG 

 499  h>lcm=NULL; 

 500  #endif 

 501  return 0; 

 502  } 

[bdde4f4]  503  h>SetShortExpVector(); 

 504  not_sev = ~ h>sev; 

 505  /* 

 506  * try to reduce the spolynomial h 

 507  *test first whether h should go to the lazyset L 

 508  *if the degree jumps 

 509  *if the number of predefined reductions jumps 

 510  */ 

 511  pass++; 

[228b631]  512  if (!TEST_OPT_REDTHROUGH && (strat>Ll >= 0) && (pass > strat>LazyPass)) 

[0188fa]  513  { 

 514  h>SetLmCurrRing(); 

[bdde4f4]  515  at = strat>posInL(strat>L,strat>Ll,h,strat); 

[0188fa]  516  if (at <= strat>Ll) 

 517  { 

[bdde4f4]  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); 

[0188fa]  522  #ifdef KDEBUG 

[bdde4f4]  523  if (TEST_OPT_DEBUG) 

 524  Print(" lazy: > L%d\n",at); 

[0188fa]  525  #endif 

 526  h>Clear(); 

 527  return 1; 

 528  } 

 529  } 

[35aab3]  530  } 

 531  } 

 532  

[fbc7cb]  533  KINLINE 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  

[83be980]  559  /*2 

 560  * reduction procedure for signaturebased standard 

 561  * basis algorithms: 

 562  * all reductions have to be sigsafe! 

 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  */ 

 569  int 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; 

[cd4f24]  591  // long reddeg,d; 

[83be980]  592  

 593  pass = j = 0; 

[cd4f24]  594  // d = reddeg = h>GetpFDeg(); 

[83be980]  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); 

[f9d20d7]  666  #if SBA_PRINT_REDUCTION_STEPS 

[15b211]  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); 

[f9d20d7]  673  #endif 

[83be980]  674  // if reduction has taken place, i.e. the reduction was sigsafe 

 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 spolynomial h 

 707  *test first whether h should go to the lazyset L 

 708  *if the degree jumps 

 709  *if the number of predefined 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  

[fbc7cb]  736  // tail reduction for SBA 

 737  poly 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  

[35aab3]  844  /*2 

 845  * reduction procedure for the inhomogeneous case 

 846  * and not a degreeordering 

 847  */ 

 848  int redLazy (LObject* h,kStrategy strat) 

 849  { 

 850  if (strat>tl<0) return 1; 

[d5564f8]  851  int at,i,ii,li; 

[35aab3]  852  int j = 0; 

 853  int pass = 0; 

 854  assume(h>pFDeg() == h>FDeg); 

 855  long reddeg = h>GetpFDeg(); 

[d5564f8]  856  long d; 

[225d94]  857  unsigned long not_sev; 

[35aab3]  858  

 859  h>SetShortExpVector(); 

[225d94]  860  poly h_p = h>GetLmTailRing(); 

 861  not_sev = ~ h>sev; 

[35aab3]  862  loop 

 863  { 

 864  j = kFindDivisibleByInT(strat>T, strat>sevT, strat>tl, h); 

 865  if (j < 0) return 1; 

[533634]  866  

[225d94]  867  li = strat>T[j].pLength; 

[f0b6c9]  868  #if 0 

 869  if (li==0) 

 870  { 

 871  li=strat>T[j].pLength=pLength(strat>T[j].p); 

 872  } 

 873  #endif 

[225d94]  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 

[8c36a9]  882  if (TEST_OPT_LENGTH) 

[225d94]  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; 

[f0b6c9]  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 

[225d94]  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  */ 

[533634]  906  PrintS("+"); 

[225d94]  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  

[35aab3]  917  

 918  #ifdef KDEBUG 

 919  if (TEST_OPT_DEBUG) 

 920  { 

 921  PrintS("red:"); 

 922  h>wrp(); 

 923  PrintS(" with "); 

[225d94]  924  strat>T[ii].wrp(); 

[35aab3]  925  } 

 926  #endif 

 927  

[225d94]  928  ksReducePoly(h, &(strat>T[ii]), NULL, NULL, strat); 

[f59aaa]  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 

[35aab3]  935  

 936  #ifdef KDEBUG 

 937  if (TEST_OPT_DEBUG) 

 938  { 

 939  PrintS("\nto "); 

 940  h>wrp(); 

 941  PrintLn(); 

 942  } 

 943  #endif 

 944  

[225d94]  945  h_p=h>GetLmTailRing(); 

 946  

 947  if (h_p == NULL) 

[35aab3]  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(); 

[225d94]  956  not_sev = ~ h>sev; 

[35aab3]  957  d = h>SetpFDeg(); 

 958  /* try to reduce the spolynomial */ 

 959  pass++; 

[228b631]  960  if (//!TEST_OPT_REDTHROUGH && 

[35aab3]  961  (strat>Ll >= 0) && ((d > reddeg)  (pass > strat>LazyPass))) 

 962  { 

 963  h>SetLmCurrRing(); 

[0188fa]  964  at = strat>posInL(strat>L,strat>Ll,h,strat); 

[35aab3]  965  if (at <= strat>Ll) 

 966  { 

[e690a91]  967  #if 1 

 968  int dummy=strat>sl; 

 969  if (kFindDivisibleByInS(strat, &dummy, h) < 0) 

[35aab3]  970  return 1; 

[0188fa]  971  #endif 

[35aab3]  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  } 

[f7feb7]  980  else if (d != reddeg) 

[35aab3]  981  { 

[f7feb7]  982  if (d>=strat>tailRing>bitmask) 

 983  { 

[8d679fd]  984  if (h>pTotalDeg() >= strat>tailRing>bitmask) 

 985  { 

 986  strat>overflow=TRUE; 

[d5564f8]  987  //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat>tailRing>bitmask); 

[8d679fd]  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(); 

[d5564f8]  992  return 1; 

 993  } 

[f7feb7]  994  } 

 995  else if ((TEST_OPT_PROT) && (strat>Ll < 0)) 

 996  { 

[dd8a7d]  997  Print(".%ld",d);mflush(); 

[f7feb7]  998  reddeg = d; 

 999  } 

[35aab3]  1000  } 

 1001  } 

 1002  } 

 1003  /*2 

 1004  * reduction procedure for the sugarstrategy (honey) 

 1005  * reduces h with elements from T choosing first possible 

 1006  * element in T with respect to the given ecart 

 1007  */ 

 1008  int redHoney (LObject* h, kStrategy strat) 

 1009  { 

 1010  if (strat>tl<0) return 1; 

[c5f67b5]  1011  //if (h>GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED! 

[35aab3]  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(); 

[b2c236]  1021  int li; 

[35aab3]  1022  h_p = h>GetLmTailRing(); 

 1023  not_sev = ~ h>sev; 

[f53fdf]  1024  

 1025  h>PrepareRed(strat>use_buckets); 

[35aab3]  1026  loop 

 1027  { 

[f53fdf]  1028  j=kFindDivisibleByInT(strat>T, strat>sevT, strat>tl, h); 

[35aab3]  1029  if (j < 0) return 1; 

 1030  

 1031  ei = strat>T[j].ecart; 

[b2c236]  1032  li = strat>T[j].pLength; 

[35aab3]  1033  ii = j; 

 1034  /* 

 1035  * the polynomial to reduce with (up to the moment) is; 

 1036  * pi with ecart ei 

 1037  */ 

 1038  i = j; 

[8c36a9]  1039  if (TEST_OPT_LENGTH) 

[35aab3]  1040  loop 

 1041  { 

 1042  /* takes the first possible with respect to ecart */ 

 1043  i++; 

 1044  if (i > strat>tl) 

 1045  break; 

[f0b6c9]  1046  //if (ei < h>ecart) 

 1047  // break; 

[bdde4f4]  1048  if (li<=1) 

[35aab3]  1049  break; 

[f0b6c9]  1050  if ((((strat>T[i].ecart < ei) && (ei> h>ecart)) 

[b2c236]  1051   ((strat>T[i].ecart <= h>ecart) && (strat>T[i].pLength < li))) 

 1052  && 

[35aab3]  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; 

[b2c236]  1060  li = strat>T[i].pLength; 

[35aab3]  1061  ii = i; 

 1062  } 

 1063  } 

 1064  

 1065  /* 

 1066  * end of search: have to reduce with pi 

 1067  */ 

[228b631]  1068  if (!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h>ecart)) 

[35aab3]  1069  { 

[f53fdf]  1070  h>GetTP(); // clears bucket 

[35aab3]  1071  h>SetLmCurrRing(); 

 1072  /* 

 1073  * It is not possible to reduce h with smaller ecart; 

 1074  * if possible h goes to the lazyset 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  

[f53fdf]  1103  number coef; 

 1104  ksReducePoly(h,&(strat>T[ii]),strat>kNoetherTail(),&coef,strat); 

[f59aaa]  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 

[35aab3]  1111  #ifdef KDEBUG 

 1112  if (TEST_OPT_DEBUG) 

 1113  { 

[f53fdf]  1114  PrintS("\nto:"); 

[35aab3]  1115  h>wrp(); 

 1116  PrintLn(); 

 1117  } 

 1118  #endif 

[f53fdf]  1119  if(h>IsNull()) 

[35aab3]  1120  { 

[f53fdf]  1121  h>Clear(); 

[35aab3]  1122  if (h>lcm!=NULL) pLmFree(h>lcm); 

[f53fdf]  1123  #ifdef KDEBUG 

[35aab3]  1124  h>lcm=NULL; 

[f53fdf]  1125  #endif 

[35aab3]  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 = dh_d; 

[822aa3a]  1134  else 

[35aab3]  1135  h>ecart = dh_d+eih>ecart; 

[f53fdf]  1136  

[35aab3]  1137  /* 

 1138  * try to reduce the spolynomial h 

 1139  *test first whether h should go to the lazyset L 

 1140  *if the degree jumps 

 1141  *if the number of predefined reductions jumps 

 1142  */ 

 1143  pass++; 

 1144  d = h_d + h>ecart; 

[228b631]  1145  if (!TEST_OPT_REDTHROUGH && (strat>Ll >= 0) && ((d > reddeg)  (pass > strat>LazyPass))) 

[35aab3]  1146  { 

[f53fdf]  1147  h>GetTP(); // clear bucket 

[35aab3]  1148  h>SetLmCurrRing(); 

 1149  at = strat>posInL(strat>L,strat>Ll,h,strat); 

 1150  if (at <= strat>Ll) 

 1151  { 

[391323]  1152  int dummy=strat>sl; 

 1153  if (kFindDivisibleByInS(strat, &dummy, h) < 0) 

[35aab3]  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  } 

[f7feb7]  1164  else if (d > reddeg) 

[35aab3]  1165  { 

[f7feb7]  1166  if (d>=strat>tailRing>bitmask) 

 1167  { 

[8d679fd]  1168  if (h>pTotalDeg()+h>ecart >= strat>tailRing>bitmask) 

 1169  { 

 1170  strat>overflow=TRUE; 

[d5564f8]  1171  //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat>tailRing>bitmask); 

[8d679fd]  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(); 

[d5564f8]  1176  return 1; 

 1177  } 

[f7feb7]  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  } 

[35aab3]  1185  } 

 1186  } 

 1187  } 

[22579cf]  1188  

[35aab3]  1189  /*2 

 1190  * reduction procedure for the normal form 

 1191  */ 

 1192  

[ab1c36]  1193  poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat) 

[35aab3]  1194  { 

 1195  if (h==NULL) return NULL; 

 1196  int j; 

[391323]  1197  max_ind=strat>sl; 

[35aab3]  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)); 

[c5f67b5]  1207  kbTest(P.bucket); 

[40d3462]  1208  #ifdef HAVE_RINGS 

 1209  BOOLEAN is_ring = rField_is_Ring(currRing); 

 1210  #endif 

[9e8da7]  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  

[35aab3]  1223  loop 

 1224  { 

[d772c3]  1225  j=kFindDivisibleByInS(strat,&max_ind,&P); 

[35aab3]  1226  if (j>=0) 

 1227  { 

[40d3462]  1228  #ifdef HAVE_RINGS 

 1229  if (!is_ring) 

 1230  { 

 1231  #endif 

[ab1c36]  1232  int sl=pSize(strat>S[j]); 

 1233  int jj=j; 

 1234  loop 

[7ba059]  1235  { 

[ab1c36]  1236  int sll; 

 1237  jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P); 

 1238  if (jj<0) break; 

 1239  sll=pSize(strat>S[jj]); 

[08ab82]  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 

[a589e6]  1245  //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); } 

[19408c]  1246  j=jj; 

 1247  sl=sll; 

[08ab82]  1248  } 

[7ba059]  1249  } 

[1863d8]  1250  if ((nonorm==0) && (!nIsOne(pGetCoeff(strat>S[j])))) 

[ab1c36]  1251  { 

 1252  pNorm(strat>S[j]); 

 1253  //if (TEST_OPT_PROT) { PrintS("n"); mflush(); } 

 1254  } 

[40d3462]  1255  #ifdef HAVE_RINGS 

 1256  } 

 1257  #endif 

[35aab3]  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  { 

[c5f67b5]  1271  number coef; 

[19370c]  1272  nc_kBucketPolyRed(P.bucket,strat>S[j],&coef); 

[c5f67b5]  1273  nDelete(&coef); 

[35aab3]  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  } 

[cea6f3]  1282  h = kBucketGetLm(P.bucket); // FRAGE OLIVER 

[35aab3]  1283  if (h==NULL) 

 1284  { 

 1285  kBucketDestroy(&P.bucket); 

[9e8da7]  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 

[e91ba4]  1298  

[35aab3]  1299  return NULL; 

 1300  } 

[c5f67b5]  1301  kbTest(P.bucket); 

[35aab3]  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); 

[9e8da7]  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  

[35aab3]  1332  return P.p; 

 1333  } 

 1334  } 

 1335  } 

 1336  

 1337  #ifdef KDEBUG 

 1338  static int bba_count = 0; 

[645a19]  1339  #endif /* KDEBUG */ 

[79d3879]  1340  void kDebugPrint(kStrategy strat); 

[35aab3]  1341  

 1342  ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat) 

 1343  { 

 1344  #ifdef KDEBUG 

 1345  bba_count++; 

 1346  int loop_count = 0; 

[645a19]  1347  #endif /* KDEBUG */ 

[930ea8]  1348  int red_result = 1; 

[35aab3]  1349  int olddeg,reduc; 

 1350  int hilbeledeg=1,hilbcount=0,minimcnt=0; 

 1351  BOOLEAN withT = FALSE; 

[3772383]  1352  BITSET save; 

 1353  SI_SAVE_OPT1(save); 

[35aab3]  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); 

[930ea8]  1362  reduc = olddeg = 0; 

[35aab3]  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 

[228b631]  1370  if (!TEST_OPT_OLDSTD) 

[35aab3]  1371  withT = ! strat>homog; 

 1372  

 1373  // strat>posInT = posInT_pLength; 

[d101b1]  1374  assume(kTest_TS(strat)); 

[35aab3]  1375  

[645a19]  1376  #ifdef KDEBUG 

 1377  #if MYTEST 

[9982049]  1378  if (TEST_OPT_DEBUG) 

[8d679fd]  1379  { 

[9982049]  1380  PrintS("bba start GB: currRing: "); 

 1381  // rWrite(currRing);PrintLn(); 

 1382  rDebugPrint(currRing); 

 1383  PrintLn(); 

[645a19]  1384  } 

 1385  #endif /* MYTEST */ 

 1386  #endif /* KDEBUG */ 

 1387  

[35aab3]  1388  #ifdef HAVE_TAIL_RING 

[e533660]  1389  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] >to be fixed 

[645a19]  1390  kStratInitChangeTailRing(strat); 

[35aab3]  1391  #endif 

[d5564f8]  1392  if (BVERBOSE(23)) 

[57fad3a]  1393  { 

 1394  if (test_PosInT!=NULL) strat>posInT=test_PosInT; 

 1395  if (test_PosInL!=NULL) strat>posInL=test_PosInL; 

 1396  kDebugPrint(strat); 

 1397  } 

 1398  

[35aab3]  1399  

[8d679fd]  1400  #ifdef KDEBUG 

 1401  //kDebugPrint(strat); 

 1402  #endif 

[35aab3]  1403  /* compute */ 

 1404  while (strat>Ll >= 0) 

 1405  { 

[08ab82]  1406  #ifdef KDEBUG 

 1407  loop_count++; 

 1408  if (TEST_OPT_DEBUG) messageSets(strat); 

 1409  #endif 

[35aab3]  1410  if (strat>Ll== 0) strat>interpt=TRUE; 

 1411  if (TEST_OPT_DEGBOUND 

[e533660]  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)))) 

[35aab3]  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  */ 

[939847]  1420  while ((strat>Ll >= 0) 

[977f94]  1421  && (strat>L[strat>Ll].p1!=NULL) && (strat>L[strat>Ll].p2!=NULL) 

[e533660]  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))) 

[977f94]  1424  ) 

[019649]  1425  deleteInL(strat>L,&strat>Ll,strat>Ll,strat); 

 1426  if (strat>Ll<0) break; 

[3957e37]  1427  else strat>noClearS=TRUE; 

[35aab3]  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 

[a539ad]  1436  #ifdef HAVE_RINGS 

 1437  if (rField_is_Ring(currRing)) 

 1438  pLmDelete(strat>P.p); 

 1439  else 

 1440  #endif 

 1441  pLmFree(strat>P.p); 

[35aab3]  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 

[7ae94b]  1452  if (!kStratChangeTailRing(strat)) 

 1453  { 

[8d679fd]  1454  WerrorS("OVERFLOW..."); 

[7ae94b]  1455  break; 

 1456  } 

[35aab3]  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  

[977f94]  1470  if (strat>P.p == NULL && strat>P.t_p == NULL) 

 1471  { 

[cea6f3]  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); 

[35aab3]  1479  

[cea6f3]  1480  /* reduction of the element choosen from L */ 

 1481  red_result = strat>red(&strat>P,strat); 

[d5564f8]  1482  if (errorreported) break; 

 1483  } 

 1484  

 1485  if (strat>overflow) 

 1486  { 

 1487  if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;} 

[cea6f3]  1488  } 

[35aab3]  1489  

 1490  // reduction to nonzero 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); 

[3dc79f5]  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)); 

[35aab3]  1499  

[d5564f8]  1500  /* statistic */ 

 1501  if (TEST_OPT_PROT) PrintS("s"); 

 1502  

[35aab3]  1503  int pos=posInS(strat,strat>sl,strat>P.p,strat>P.ecart); 

 1504  

[645a19]  1505  #ifdef KDEBUG 

 1506  #if MYTEST 

[f29ab6]  1507  PrintS("New S: "); p_DebugPrint(strat>P.p, currRing); PrintLn(); 

[645a19]  1508  #endif /* MYTEST */ 

 1509  #endif /* KDEBUG */ 

 1510  

[35aab3]  1511  // reduce the tail and normalize poly 

[521349]  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))) 

[35aab3]  1515  { 

 1516  strat>P.pCleardenom(); 

 1517  if ((TEST_OPT_REDSB)(TEST_OPT_REDTAIL)) 

 1518  { 

 1519  strat>P.p = redtailBba(&(strat>P),pos1,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),pos1,strat, withT); 

 1528  } 

 1529  

 1530  #ifdef KDEBUG 

 1531  if (TEST_OPT_DEBUG){PrintS("new s:");strat>P.wrp();PrintLn();} 

[645a19]  1532  #if MYTEST 

[f29ab6]  1533  PrintS("New (reduced) S: "); p_DebugPrint(strat>P.p, currRing); PrintLn(); 

[645a19]  1534  #endif /* MYTEST */ 

 1535  #endif /* KDEBUG */ 

[35aab3]  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 

[b981502]  1559  //if ((!TEST_OPT_IDLIFT)  (pGetComp(strat>P.p) <= strat>syzComp)) 

[f0b6c9]  1560  enterT(strat>P, strat); 

[206e158]  1561  #ifdef HAVE_RINGS 

 1562  if (rField_is_Ring(currRing)) 

[f92547]  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); 

[35aab3]  1567  // posInS only depends on the leading term 

 1568  strat>enterS(strat>P, pos, strat, strat>tl); 

[f0b6c9]  1569  #if 0 

[b2c236]  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  } 

[f0b6c9]  1581  #endif 

[35aab3]  1582  if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat); 

 1583  // Print("[%d]",hilbeledeg); 

[1e36c5]  1584  if (strat>P.lcm!=NULL) 

 1585  #ifdef HAVE_RINGS 

 1586  pLmDelete(strat>P.lcm); 

 1587  #else 

 1588  pLmFree(strat>P.lcm); 

 1589  #endif 

[35aab3]  1590  } 

 1591  else if (strat>P.p1 == NULL && strat>minim > 0) 

 1592  { 

 1593  p_Delete(&strat>P.p2, currRing, strat>tailRing); 

 1594  } 

[a539ad]  1595  

[35aab3]  1596  #ifdef KDEBUG 

 1597  memset(&(strat>P), 0, sizeof(strat>P)); 

[645a19]  1598  #endif /* KDEBUG */ 

[d101b1]  1599  assume(kTest_TS(strat)); 

[35aab3]  1600  } 

 1601  #ifdef KDEBUG 

[645a19]  1602  #if MYTEST 

 1603  PrintS("bba finish GB: currRing: "); rWrite(currRing); 

 1604  #endif /* MYTEST */ 

[35aab3]  1605  if (TEST_OPT_DEBUG) messageSets(strat); 

[645a19]  1606  #endif /* KDEBUG */ 

 1607  

[07b1cf]  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  

[93f4bb]  1625  /* complete reduction of the standard basis */ 

[533634]  1626  if (TEST_OPT_REDSB) 

[b57694]  1627  { 

[533634]  1628  completeReduce(strat); 

[cbc616]  1629  #ifdef HAVE_TAIL_RING 

[b57694]  1630  if (strat>completeReduce_retry) 

 1631  { 

[533634]  1632  // completeReduce needed larger exponents, retry 

 1633  // to reduce with S (instead of T) 

 1634  // and in currRing (instead of strat>tailRing) 

[b57694]  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  } 

[cbc616]  1640  #endif 

[b57694]  1641  } 

[5accf0]  1642  else if (TEST_OPT_PROT) PrintLn(); 

[533634]  1643  

[35aab3]  1644  /* release temp data */ 

 1645  exitBuchMora(strat); 

[e533660]  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  // } 

[930ea8]  1655  if (TEST_OPT_PROT) messageStat(hilbcount,strat); 

[3772383]  1656  SI_RESTORE_OPT1(save); 

[35aab3]  1657  if (Q!=NULL) updateResult(strat>Shdl,Q,strat); 

[645a19]  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  

[35aab3]  1666  return (strat>Shdl); 

 1667  } 

[83be980]  1668  ideal 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) 

[601105]  1673  // 2. a (possibly nonincremental) computation w.r.t. the 

[83be980]  1674  // induced Schreyer order. 

 1675  // The corresponding orders are computed in sbaRing(), depending 

 1676  // on the flag strat>incremental 

[f59aaa]  1677  long zeroreductions = 0; 

 1678  long product_criterion = 0; 

 1679  long size_g = 0; 

 1680  long size_syz = 0; 

[f9d20d7]  1681  // global variable 

[f59aaa]  1682  sba_reduction_steps = 0; 

 1683  sba_operations = 0; 

 1684  sba_interreduction_steps = 0; 

 1685  sba_interreduction_operations = 0; 

[b3e94aa]  1686  

[83be980]  1687  ideal F = F0; 

 1688  ring sRing, currRingOld; 

[601105]  1689  currRingOld = currRing; 

[83be980]  1690  if (strat>incremental) 

 1691  { 

 1692  sRing = sbaRing(strat); 

 1693  if (sRing!=currRingOld) 

 1694  { 

 1695  rChangeCurrRing (sRing); 

[fee33e]  1696  F = idrMoveR (F0, currRingOld, currRing); 

[83be980]  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; 

[576f5b]  1712  BOOLEAN withT = TRUE; 

[83be980]  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 

[cd4f24]  1733  // if (!TEST_OPT_OLDSTD) 

 1734  // withT = ! strat>homog; 

[83be980]  1735  

 1736  // strat>posInT = posInT_pLength; 

[d101b1]  1737  assume(kTest_TS(strat)); 

[83be980]  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 

[fee33e]  1752  if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] >to be fixed 

[83be980]  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 

[fee33e]  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)))) 

[83be980]  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) 

[fee33e]  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))) 

[83be980]  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 

[601105]  1799  f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax, 

[83be980]  1800  lrmax, reduc, Q, w, hilb ); 

 1801  #endif 

[601105]  1802  // initialize new syzygy rules for the next iteration step 

[83be980]  1803  initSyzRules(strat); 

 1804  } 

 1805  /********************************************************************* 

 1806  * interrreduction step is done, we can go on with the next iteration 

 1807  * step of the signaturebased 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 SIGBASED 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 */ 

[b3e94aa]  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 { 

[83be980]  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 nonzero 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); 

[601105]  1912  

 1913  // sigsafe computations may lead to wrong FDeg computation, thus we need 

[83be980]  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 

[b085fba]  1938  #if SBA_TAIL_RED 

[83be980]  1939  if ((TEST_OPT_INTSTRATEGY)  (rField_is_Ring(currRing))) 

 1940  { 

 1941  strat>P.pCleardenom(); 

 1942  if ((TEST_OPT_REDSB)(TEST_OPT_REDTAIL)) 

 1943  { 

[b085fba]  1944  strat>P.p = redtailSba(&(strat>P),pos1,strat, withT); 

[83be980]  1945  strat>P.pCleardenom(); 

 1946  } 

 1947  } 

 1948  else 

 1949  { 

 1950  strat>P.pNorm(); 

 1951  if ((TEST_OPT_REDSB)(TEST_OPT_REDTAIL)) 

[b085fba]  1952  strat>P.p = redtailSba(&(strat>P),pos1,strat, withT); 

[83be980]  1953  } 

[b085fba]  1954  #endif 

[576f5b]  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  } 

[83be980]  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 

[601105]  2045  p_ExpVectorAdd (strat>syz[i],strat>S[ps],currRing); 

[83be980]  2046  // since p_Add_q() destroys all input 

[601105]  2047  // data we need to recreate help 

[83be980]  2048  // each time 

 2049  //  

[601105]  2050  // in the Schreyer order we always know that the multiplied 

[83be980]  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]); 

[601105]  2055  p_ExpVectorAdd (help,strat>P.p,currRing); 

[83be980]  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  } 

[601105]  2064  enterT(strat>P, strat); 

 2065  strat>T[strat>tl].is_sigsafe = FALSE; 

[83be980]  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); 

[576f5b]  2074  //#if 1 

 2075  #if DEBUGF50 

[83be980]  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 */ 

[d101b1]  2136  assume(kTest_TS(strat)); 

[83be980]  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  

[b3e94aa]  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  

[83be980]  2188  exitSba(strat); 

[fee33e]  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); 

[83be980]  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); 

[fee33e]  2219  F0 = idrMoveR (F, sRing, currRing); 

 2220  strat>Shdl = idrMoveR_NoSort (strat>Shdl, sRing, currRing); 

[83be980]  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 

[b3e94aa]  2235  #if SBA_PRINT_ZERO_REDUCTIONS 

[f59aaa]  2236  printf("\n"); 

 2237  printf("ZERO REDUCTIONS: %ld\n",zeroreductions); 

[b3e94aa]  2238  #endif 

[f9d20d7]  2239  #if SBA_PRINT_REDUCTION_STEPS 

[f59aaa]  2240  printf("\n"); 

 2241  printf("TOP SREDUCTIONS: %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); 

[f9d20d7]  2256  #endif 

[f59aaa]  2257  #if SBA_PRINT_INTERREDUCTION_OPERATIONS 

 2258  printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations); 

[15b211]  2259  #endif 

[b3e94aa]  2260  #if SBA_PRINT_SIZE_G 

[f59aaa]  2261  printf("\n"); 

 2262  printf("SIZE OF G: %ld\n",size_g); 

[b3e94aa]  2263  #endif 

 2264  #if SBA_PRINT_SIZE_SYZ 

[f59aaa]  2265  printf("SIZE OF SYZ: %ld\n",size_syz); 

 2266  printf("\n"); 

[b3e94aa]  2267  #endif 

 2268  #if SBA_PRINT_PRODUCT_CRITERION 

[f59aaa]  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; 

[83be980]  2279  return (strat>Shdl); 

 2280  } 

 2281  

 2282  poly 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 */ 

[d30a399]  2298  BITSET save1; 

 2299  SI_SAVE_OPT1(save1); 

 2300  si_opt_1=Sy_bit(OPT_REDTAIL); 

[83be980]  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  //} 

[d101b1]  2317  assume(kTest(strat)); 

[83be980]  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  { 

[d30a399]  2333  si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY); 

[83be980]  2334  p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0); 

 2335  } 

 2336  } 

 2337  /* release temp data */ 

[e14e025]  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); 

[83be980]  2345  omfree(strat>S_2_R); 

 2346  omfree(strat>fromQ); 

 2347  idDelete(&strat>Shdl); 

[d30a399]  2348  SI_RESTORE_OPT1(save1); 

[83be980]  2349  if (TEST_OPT_PROT) PrintLn(); 

 2350  return p; 

 2351  } 

 2352  

 2353  ideal 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 */ 

[d30a399]  2373  BITSET save1; 

 2374  SI_SAVE_OPT1(save1); 

 2375  si_opt_1=Sy_bit(OPT_REDTAIL); 

[83be980]  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)); 

[d30a399]  2388  si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY); 

[83be980]  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 */ 

[e14e025]  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); 

[83be980]  2422  omfree(strat>S_2_R); 

[35aab3]  2423  omfree(strat>fromQ); 

 2424  idDelete(&strat>Shdl); 

[d30a399]  2425  SI_RESTORE_OPT1(save1); 

[35aab3]  2426  if (TEST_OPT_PROT) PrintLn(); 

 2427  return res; 

 2428  } 

[dd2855]  2429  

[83be980]  2430  #if F5C 

 2431  /********************************************************************* 

 2432  * interrreduction step of the signaturebased 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  ********************************************************************/ 

[601105]  2438  void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg, 

[83be980]  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  { 

[fee33e]  2463  if (currRing>OrdSgn==1) 

[83be980]  2464  { 

[601105]  2465  cancelunit(&h); 

[83be980]  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 nonzero 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 

[15b211]  2601  BOOLEAN withT = TRUE; 

[83be980]  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),pos1,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),pos1,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; 

[601105]  2694  strat>T[cc].is_sigsafe = TRUE; 

[83be980]  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  

[cb0fbe]  2747  /* shiftgb stuff */ 

[037df4]  2748  #ifdef HAVE_SHIFTBBA 

[37a4c3]  2749  

[07625cb]  2750  

[cb0fbe]  2751  ideal 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 

[930ea8]  2757  int red_result = 1; 

[cb0fbe]  2758  int olddeg,reduc; 

 2759  int hilbeledeg=1,hilbcount=0,minimcnt=0; 

[4d43ff]  2760  BOOLEAN withT = TRUE; // very important for shifts 

[cb0fbe]  2761  

[37a4c3]  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 */ 

[cb0fbe]  2766  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/ 

[37a4c3]  2767  /*Shdl=*/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */ 

 2768  updateSShift(strat,uptodeg,lV); /* initializes T */ 

 2769  

[cb0fbe]  2770  if (strat>minim>0) strat>M=idInit(IDELEMS(F),F>rank); 

[930ea8]  2771  reduc = olddeg = 0; 

[bbf50e]  2772  strat>lV=lV; 

[cb0fbe]  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 

[228b631]  2780  // if (!TEST_OPT_OLDSTD) 

[37a4c3]  2781  // withT = ! strat>homog; 

[cb0fbe]  2782  

 2783  // strat>posInT = posInT_pLength; 

[d101b1]  2784  assume(kTest_TS(strat)); 

[cb0fbe]  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 

[e533660]  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)))) 

[cb0fbe]  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) 

[e533660]  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))) 

[cb0fbe]  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  

[ad1c3b]  2848  poly qq; 

 2849  

 2850  /* here in the nonhomog case we shrink the new spoly */ 

[eed827]  2851  

[ad1c3b]  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; 

[eed827]  2862  // strat>P.Delete(); /* deletes P.p and P.t_p */ //error 

[ad1c3b]  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 

[eed827]  2879  // strat>P.Delete(); // cause error 

 2880  strat>P.p = NULL; 

 2881  strat>P.t_p = NULL; 

[ad1c3b]  2882  // strat>P.p = NULL; // or delete strat>P.p ? 

 2883  } 

 2884  } 

 2885  /* end shrinking poly in the nonhomog case */ 

 2886  

[cb0fbe]  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 nonzero 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),pos1,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),pos1,strat, withT); 

 2927  } 

 2928  

[ad1c3b]  2929  // here we must shrink again! and optionally reduce again 

 2930  // or build shrink into redtailBba! 

 2931  

[cb0fbe]  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  

[ad1c3b]  2957  /* here in the nonhomog case we shrink the reduced poly AGAIN */ 

[eed827]  2958  

[ad1c3b]  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; 

[eed827]  2970  // strat>P.Delete(); /* deletes P.p and P.t_p */ //error 

[ad1c3b]  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 

[eed827]  2984  // strat>P.Delete(); // cause error 

 2985  strat>P.p = NULL; 

 2986  strat>P.t_p = NULL; 

[ad1c3b]  2987  // strat>P.p = NULL; // or delete strat>P.p ? 

[eed827]  2988  goto red_shrink2zero; 

[ad1c3b]  2989  } 

 2990  } 

 2991  /* end shrinking poly AGAIN in the nonhomog case */ 

 2992  

 2993  

[cb0fbe]  2994  // enter into S, L, and T 

 2995  //if ((!TEST_OPT_IDLIFT)  (pGetComp(strat>P.p) <= strat>syzComp)) 

[37a4c3]  2996  // enterT(strat>P, strat); // this was here before Shift stuff 

 2997  //enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax 

[4d2ab5c]  2998  // the default value for atT = 1 as in bba 

[eed827]  2999  /* strat>P.GetP(); */ 

[ad1c3b]  3000  // because shifts are counted with .p structure // done before, but ? 

[37a4c3]  3001  enterTShift(strat>P,strat,1,uptodeg, lV); 

 3002  enterpairsShift(strat>P.p,strat>sl,strat>P.ecart,pos,strat, strat>tl,uptodeg,lV); 

[4d2ab5c]  3003  // enterpairsShift(vw,strat>sl,strat>P.ecart,pos,strat, strat>tl,uptodeg,lV); 

[cb0fbe]  3004  // posInS only depends on the leading term 

[1c35568]  3005  strat>enterS(strat>P, pos, strat, strat>tl); 

[ad1c3b]  3006  

[cb0fbe]  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  } 

[eed827]  3011  else 

[cb0fbe]  3012  { 

[ad1c3b]  3013  red_shrink2zero: 

 3014  if (strat>P.p1 == NULL && strat>minim > 0) 

 3015  { 

[eed827]  3016  p_Delete(&strat>P.p2, currRing, strat>tailRing); 

[ad1c3b]  3017  } 

[cb0fbe]  3018  } 

 3019  #ifdef KDEBUG 

 3020  memset(&(strat>P), 0, sizeof(strat>P)); 

 3021  #endif 

[d101b1]  3022  assume(kTest_TS(strat)); 

[cb0fbe]  3023  } 

 3024  #ifdef KDEBUG 

 3025  if (TEST_OPT_DEBUG) messageSets(strat); 

 3026  #endif 

 3027  /* complete reduction of the standard basis */ 

[d5564f8]  3028  /* shift case: look for elt's in S such that they are divisible by elt in T */ 

[4c4979]  3029  // if (TEST_OPT_SB_1) 

 3030  if (TEST_OPT_REDSB) 

[cb0fbe]  3031  { 

[4c4979]  3032  int k=0; 

 3033  int j=1; 

[cb0fbe]  3034  while(k<=strat>sl) 

 3035  { 

[4c4979]  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 

[cb0fbe]  3047  { 

[4c4979]  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  } 

[cb0fbe]  3061  } 

 3062  } 

 3063  } 

 3064  

 3065  if (TEST_OPT_REDSB) 

[4c4979]  3066  { completeReduce(strat, TRUE); //shift: withT = TRUE 

[cb0fbe]  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; 

[4d43ff]  3075  completeReduce(strat, TRUE); 

[cb0fbe]  3076  } 

 3077  } 

[5accf0]  3078  else if (TEST_OPT_PROT) PrintLn(); 

[cb0fbe]  3079  

 3080  /* release temp data */ 

 3081  exitBuchMora(strat); 

[e533660]  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  // } 

[930ea8]  3091  if (TEST_OPT_PROT) messageStat(hilbcount,strat); 

[cb0fbe]  3092  if (Q!=NULL) updateResult(strat>Shdl,Q,strat); 

 3093  return (strat>Shdl); 

 3094  } 

 3095  

[1c473f]  3096  

[cb0fbe]  3097  ideal freegb(ideal I, int uptodeg, int lVblock) 

 3098  { 

 3099  /* todo main call */ 

 3100  

[37a4c3]  3101  /* assume: ring is prepared, ideal is copied into shifted ring */ 

 3102  /* uptodeg and lVblock are correct  test them! */ 

 3103  

[dabe365]  3104  /* check whether the ideal is in V */ 

[9f5fca]  3105  

[db0c264]  3106  // if (0) 

 3107  if (! ideal_isInV(I,lVblock) ) 

[dabe365]  3108  { 

[9f5fca]  3109  WerrorS("The input ideal contains incorrectly encoded elements! "); 

[dabe365]  3110  return(NULL); 

 3111  } 

 3112  

[1c473f]  3113  // kStrategy strat = new skStrategy; 

[cb0fbe]  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  */ 

[1c473f]  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); 

[4d2ab5c]  3123  idSkipZeroes(RS); 

[cb0fbe]  3124  return(RS); 

 3125  } 

[37a4c3]  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  */ 

 3131  int redFirstShift (LObject* h,kStrategy strat) 

 3132  { 

