kspoly.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT - Routines for Spoly creation and reductions
6 */
7 
8 // #define PDEBUG 2
9 
10 
11 
12 #include "kernel/mod2.h"
13 #include "misc/options.h"
14 #include "kernel/GBEngine/kutil.h"
15 #include "coeffs/numbers.h"
18 #include "polys/nc/nc.h"
19 #ifdef HAVE_RINGS
20 #include "kernel/polys.h"
21 #endif
22 #ifdef HAVE_SHIFTBBA
23 #include "polys/shiftop.h"
24 #endif
25 
26 #ifdef KDEBUG
27 int red_count = 0;
28 int create_count = 0;
29 // define this if reductions are reported on TEST_OPT_DEBUG
30 #define TEST_OPT_DEBUG_RED
31 #endif
32 
33 /***************************************************************
34  *
35  * Reduces PR with PW
36  * Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
37  *
38  * returns 0: okay
39  * 1: tailRing changed
40  * -1: cannot change tailRing
41  * 2: cannot change tailRing: strat==NULL
42  *
43  ***************************************************************/
45  TObject* PW,
46  poly spNoether,
47  number *coef,
48  kStrategy strat)
49 {
50 #ifdef KDEBUG
51  red_count++;
52 #ifdef TEST_OPT_DEBUG_RED
53 // if (TEST_OPT_DEBUG)
54 // {
55 // Print("Red %d:", red_count); PR->wrp(); Print(" with:");
56 // PW->wrp();
57 // //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
58 // //pWrite(PR->p);
59 // }
60 #endif
61 #endif
62  int ret = 0;
63  ring tailRing = PR->tailRing;
64  kTest_L(PR,tailRing);
65  kTest_T(PW);
66 
67  poly p1 = PR->GetLmTailRing(); // p2 | p1
68  poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
69  poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
70  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
71  p_CheckPolyRing(p1, tailRing);
72  p_CheckPolyRing(p2, tailRing);
73 
74  pAssume1(p2 != NULL && p1 != NULL &&
75  p_DivisibleBy(p2, p1, tailRing));
76 
77  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
78  (p_GetComp(p2, tailRing) == 0 &&
79  p_MaxComp(pNext(p2),tailRing) == 0));
80 
81 #ifdef HAVE_PLURAL
83  {
84  // for the time being: we know currRing==strat->tailRing
85  // no exp-bound checking needed
86  // (only needed if exp-bound(tailring)<exp-b(currRing))
87  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
88  else
89  {
90  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
91  assume(_p != NULL);
92  nc_PolyPolyRed(_p, p2,coef, currRing);
93  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
94  PR->pLength=0; // usually not used, GetpLength re-computes it if needed
95  }
96  return 0;
97  }
98 #endif
99 
100  if (t2==NULL) // Divisor is just one term, therefore it will
101  { // just cancel the leading term
102  // adjust lead coefficient if needed
103  if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
104  {
105  number bn = pGetCoeff(lm);
106  number an = pGetCoeff(p2);
107  int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
108  p_SetCoeff(lm, bn, tailRing);
109  if ((ct == 0) || (ct == 2))
110  PR->Tail_Mult_nn(an);
111  if (coef != NULL) *coef = an;
112  else n_Delete(&an, tailRing->cf);
113  }
114  PR->LmDeleteAndIter();
115  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
116  return 0;
117  }
118 
119  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
120 
121  //if (tailRing != currRing)
122  {
123  // check that reduction does not violate exp bound
124  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
125  {
126  // undo changes of lm
127  p_ExpVectorAdd(lm, p2, tailRing);
128  if (strat == NULL) return 2;
129  if (! kStratChangeTailRing(strat, PR, PW)) return -1;
130  tailRing = strat->tailRing;
131  p1 = PR->GetLmTailRing();
132  p2 = PW->GetLmTailRing();
133  t2 = pNext(p2);
134  lm = p1;
135  p_ExpVectorSub(lm, p2, tailRing);
136  ret = 1;
137  }
138  }
139 
140 #ifdef HAVE_SHIFTBBA
141  poly lmRight;
142  if (tailRing->isLPring) {
143  k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
144  }
145 #endif
146 
147  // take care of coef buisness
148  if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
149  {
150  number bn = pGetCoeff(lm);
151  number an = pGetCoeff(p2);
152  int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
153  p_SetCoeff(lm, bn, tailRing);
154 #ifdef HAVE_SHIFTBBA
155  if (tailRing->isLPring) pSetCoeff0(p1, bn); // lm doesn't point to p1 anymore, if the coef was a pointer, it has been deleted
156 #endif
157  if ((ct == 0) || (ct == 2))
158  PR->Tail_Mult_nn(an);
159  if (coef != NULL) *coef = an;
160  else n_Delete(&an, tailRing->cf);
161  }
162  else
163  {
164  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
165  }
166 
167 
168  // and finally,
169 #ifdef HAVE_SHIFTBBA
170  if (tailRing->isLPring)
171  {
172  PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
173  }
174  else
175 #endif
176  {
177  PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
178  }
179  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
180  PR->LmDeleteAndIter();
181 
182  return ret;
183 }
184 
186  TObject* PW,
187  poly spNoether,
188  number *coef,
189  kStrategy strat)
190 {
191 #ifdef KDEBUG
192  red_count++;
193 #ifdef TEST_OPT_DEBUG_RED
194 // if (TEST_OPT_DEBUG)
195 // {
196 // Print("Red %d:", red_count); PR->wrp(); Print(" with:");
197 // PW->wrp();
198 // //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
199 // //pWrite(PR->p);
200 // }
201 #endif
202 #endif
203  int ret = 0;
204  ring tailRing = PR->tailRing;
205  kTest_L(PR,tailRing);
206  kTest_T(PW);
207 
208  poly p1 = PR->GetLmTailRing(); // p2 | p1
209  poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
210  poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
211  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
212  p_CheckPolyRing(p1, tailRing);
213  p_CheckPolyRing(p2, tailRing);
214 
215  pAssume1(p2 != NULL && p1 != NULL &&
216  p_DivisibleBy(p2, p1, tailRing));
217 
218  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
219  (p_GetComp(p2, tailRing) == 0 &&
220  p_MaxComp(pNext(p2),tailRing) == 0));
221 
222 #ifdef HAVE_PLURAL
223  if (rIsPluralRing(currRing))
224  {
225  // for the time being: we know currRing==strat->tailRing
226  // no exp-bound checking needed
227  // (only needed if exp-bound(tailring)<exp-b(currRing))
228  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
229  else
230  {
231  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
232  assume(_p != NULL);
233  nc_PolyPolyRed(_p, p2,coef, currRing);
234  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
235  PR->pLength=0; // usually not used, GetpLength re-computes it if needed
236  }
237  return 0;
238  }
239 #endif
240 
241  if (t2==NULL) // Divisor is just one term, therefore it will
242  { // just cancel the leading term
243  PR->LmDeleteAndIter();
244  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
245  return 0;
246  }
247 
248  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
249 
250  //if (tailRing != currRing)
251  {
252  // check that reduction does not violate exp bound
253  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
254  {
255  // undo changes of lm
256  p_ExpVectorAdd(lm, p2, tailRing);
257  if (strat == NULL) return 2;
258  if (! kStratChangeTailRing(strat, PR, PW)) return -1;
259  tailRing = strat->tailRing;
260  p1 = PR->GetLmTailRing();
261  p2 = PW->GetLmTailRing();
262  t2 = pNext(p2);
263  lm = p1;
264  p_ExpVectorSub(lm, p2, tailRing);
265  ret = 1;
266  }
267  }
268 
269 #ifdef HAVE_SHIFTBBA
270  poly lmRight;
271  if (tailRing->isLPring)
272  {
273  k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
274  }
275 #endif
276 
277  // take care of coef buisness
278  if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
279  {
280  number bn = pGetCoeff(lm);
281  number an = pGetCoeff(p2);
282  int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
283  p_SetCoeff(lm, bn, tailRing);
284 #ifdef HAVE_SHIFTBBA
285  if (tailRing->isLPring) pSetCoeff0(p1, bn); // lm doesn't point to p1 anymore, if the coef was a pointer, it has been deleted
286 #endif
287  if ((ct == 0) || (ct == 2))
288  PR->Tail_Mult_nn(an);
289  if (coef != NULL) *coef = an;
290  else n_Delete(&an, tailRing->cf);
291  }
292  else
293  {
294  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
295  }
296 
297 
298  // and finally,
299 #ifdef HAVE_SHIFTBBA
300  if (tailRing->isLPring)
301  {
302  PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
303  }
304  else
305 #endif
306  {
307  PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
308  }
309  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
310  PR->LmDeleteAndIter();
311 
312  return ret;
313 }
314 
316  TObject* PW,
317  poly spNoether,
318  number *coef,
319  kStrategy strat)
320 {
321 #ifdef KDEBUG
322  red_count++;
323 #ifdef TEST_OPT_DEBUG_RED
324 // if (TEST_OPT_DEBUG)
325 // {
326 // Print("Red %d:", red_count); PR->wrp(); Print(" with:");
327 // PW->wrp();
328 // //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
329 // //pWrite(PR->p);
330 // }
331 #endif
332 #endif
333  int ret = 0;
334  ring tailRing = PR->tailRing;
335  kTest_L(PR, tailRing);
336  kTest_T(PW);
337 
338  poly p1 = PR->GetLmTailRing();
339  poly p2 = PW->GetLmTailRing();
340  poly t2 = pNext(p2), lm = pOne();
341  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
342  p_CheckPolyRing(p1, tailRing);
343  p_CheckPolyRing(p2, tailRing);
344 
345  pAssume1(p2 != NULL && p1 != NULL &&
346  p_DivisibleBy(p2, p1, tailRing));
347 
348  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
349  (p_GetComp(p2, tailRing) == 0 &&
350  p_MaxComp(pNext(p2),tailRing) == 0));
351 
352 #ifdef HAVE_PLURAL
353  if (rIsPluralRing(currRing))
354  {
355  // for the time being: we know currRing==strat->tailRing
356  // no exp-bound checking needed
357  // (only needed if exp-bound(tailring)<exp-b(currRing))
358  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
359  else
360  {
361  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
362  assume(_p != NULL);
363  nc_PolyPolyRed(_p, p2,coef, currRing);
364  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
365  PR->pLength=0; // usually not used, GetpLength re-computes it if needed
366  }
367  return 0;
368  }
369 #endif
370  // check that reduction does not violate exp bound
371  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
372  {
373  // undo changes of lm
374  p_ExpVectorAdd(lm, p2, tailRing);
375  if (strat == NULL) return 2;
376  if (! kStratChangeTailRing(strat, PR, PW)) return -1;
377  tailRing = strat->tailRing;
378  p1 = PR->GetLmTailRing();
379  p2 = PW->GetLmTailRing();
380  t2 = pNext(p2);
381  lm = p1;
382  p_ExpVectorSub(lm, p2, tailRing);
383  ret = 1;
384  }
385 
386  number ct, an, bn;
387  // take care of coef buisness
388  if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
389  {
390  ct = n_ExtGcd(pGetCoeff(p1), pGetCoeff(p2), &an, &bn, tailRing->cf); // Calculate GCD
391  /* negate bn since we subtract in Tail_Minus_mm_Mult_qq */
392  bn = n_InpNeg(bn, tailRing->cf);
393  p_SetCoeff(lm, bn, tailRing);
394  PR->Tail_Mult_nn(an);
395  }
396  else
397  {
398  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
399  }
400 
401 
402  // and finally,
403  PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
404  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
405  pSetCoeff(PR->p, ct);
406 
407  // the following is commented out: shrinking
408 #ifdef HAVE_SHIFTBBA_NONEXISTENT
409  if ( (currRing->isLPring) && (!strat->homog) )
410  {
411  // assume? h->p in currRing
412  PR->GetP();
413  poly qq = p_Shrink(PR->p, currRing->isLPring, currRing);
414  PR->Clear(); // does the right things
415  PR->p = qq;
416  PR->t_p = NULL;
417  PR->SetShortExpVector();
418  }
419 #endif
420 
421  return ret;
422 }
423 
424 /* Computes a reduction of the lead coefficient only. We have already tested
425  * that lm(PW) divides lm(PR), but lc(PW) does not divide lc(PR). We have
426  * computed division with remainder on the lead coefficients, parameter
427  * coef is the corresponding multiple for PW we need. The new lead
428  * coefficient, i.e. the remainder of lc division has already been
429  * set before calling this function. We do not drop the lead term at
430  * the end, but keep the adjusted, correct lead term. */
432  TObject* PW,
433  poly spNoether,
434  number *coef,
435  kStrategy strat)
436 {
437 #ifdef KDEBUG
438  red_count++;
439 #ifdef TEST_OPT_DEBUG_RED
440 // if (TEST_OPT_DEBUG)
441 // {
442 // Print("Red %d:", red_count); PR->wrp(); Print(" with:");
443 // PW->wrp();
444 // //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
445 // //pWrite(PR->p);
446 // }
447 #endif
448 #endif
449  /* printf("PR->P: ");
450  * p_Write(PR->p, currRing, PR->tailRing); */
451  int ret = 0;
452  ring tailRing = PR->tailRing;
453  kTest_L(PR,tailRing);
454  kTest_T(PW);
455 
456  poly p1 = PR->GetLmTailRing(); // p2 | p1
457  poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
458  poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
459  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
460  p_CheckPolyRing(p1, tailRing);
461  p_CheckPolyRing(p2, tailRing);
462 
463  pAssume1(p2 != NULL && p1 != NULL &&
464  p_DivisibleBy(p2, p1, tailRing));
465 
466  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
467  (p_GetComp(p2, tailRing) == 0 &&
468  p_MaxComp(pNext(p2),tailRing) == 0));
469 
470 #ifdef HAVE_PLURAL
471  if (rIsPluralRing(currRing))
472  {
473  // for the time being: we know currRing==strat->tailRing
474  // no exp-bound checking needed
475  // (only needed if exp-bound(tailring)<exp-b(currRing))
476  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
477  else
478  {
479  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
480  assume(_p != NULL);
481  nc_PolyPolyRed(_p, p2,coef, currRing);
482  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
483  PR->pLength=0; // usually not used, GetpLength re-computes it if needed
484  }
485  return 0;
486  }
487 #endif
488 
489  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
490  p_SetCoeff(lm, n_Init(1, tailRing), tailRing);
491  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
492  {
493  // undo changes of lm
494  p_ExpVectorAdd(lm, p2, tailRing);
495  if (strat == NULL) return 2;
496  /* if (! kStratChangeTailRing(strat, PR, PW)) return -1; */
497  tailRing = strat->tailRing;
498  p1 = PR->GetLmTailRing();
499  p2 = PW->GetLmTailRing();
500  t2 = pNext(p2);
501  lm = p1;
502  p_ExpVectorSub(lm, p2, tailRing);
503  ret = 1;
504  }
505 
506  // and finally,
507  PR->Tail_Minus_mm_Mult_qq(lm, p2, pLength(p2) /*PW->GetpLength() - 1*/, spNoether);
508  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
509 
510  PR->LmDeleteAndIter();
511  p_SetCoeff(PR->p, *coef, currRing);
512 
513 
514  // the following is commented out: shrinking
515 #ifdef HAVE_SHIFTBBA_NONEXISTENT
516  if ( (currRing->isLPring) && (!strat->homog) )
517  {
518  // assume? h->p in currRing
519  PR->GetP();
520  poly qq = p_Shrink(PR->p, currRing->isLPring, currRing);
521  PR->Clear(); // does the right things
522  PR->p = qq;
523  PR->t_p = NULL;
524  PR->SetShortExpVector();
525  }
526 #endif
527 
528 #if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
529  if (TEST_OPT_DEBUG)
530  {
531  Print(" to: "); PR->wrp(); Print("\n");
532  //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
533  }
534 #endif
535  return ret;
536 }
537 
539  TObject* PW,
540  int bound,
541  poly spNoether,
542  number *coef,
543  kStrategy strat)
544 {
545 #ifdef KDEBUG
546  red_count++;
547 #ifdef TEST_OPT_DEBUG_RED
548  if (TEST_OPT_DEBUG)
549  {
550  Print("Red %d:", red_count); PR->wrp(); Print(" with:");
551  PW->wrp();
552  //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
553  //pWrite(PR->p);
554  }
555 #endif
556 #endif
557  int ret = 0;
558  ring tailRing = PR->tailRing;
559  kTest_L(PR,tailRing);
560  kTest_T(PW);
561 
562  poly p1 = PR->GetLmTailRing(); // p2 | p1
563  poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
564  poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
565  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
566  p_CheckPolyRing(p1, tailRing);
567  p_CheckPolyRing(p2, tailRing);
568 
569  pAssume1(p2 != NULL && p1 != NULL &&
570  p_DivisibleBy(p2, p1, tailRing));
571 
572  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
573  (p_GetComp(p2, tailRing) == 0 &&
574  p_MaxComp(pNext(p2),tailRing) == 0));
575 
576 #ifdef HAVE_PLURAL
577  if (rIsPluralRing(currRing))
578  {
579  // for the time being: we know currRing==strat->tailRing
580  // no exp-bound checking needed
581  // (only needed if exp-bound(tailring)<exp-b(currRing))
582  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
583  else
584  {
585  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
586  assume(_p != NULL);
587  nc_PolyPolyRed(_p, p2,coef, currRing);
588  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
589  PR->pLength=0; // usually not used, GetpLength re-computes it if needed
590  }
591  return 0;
592  }
593 #endif
594 
595  if (t2==NULL) // Divisor is just one term, therefore it will
596  { // just cancel the leading term
597  PR->LmDeleteAndIter();
598  if (coef != NULL) *coef = n_Init(1, tailRing);
599  return 0;
600  }
601 
602  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
603 
604  if (tailRing != currRing)
605  {
606  // check that reduction does not violate exp bound
607  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
608  {
609  // undo changes of lm
610  p_ExpVectorAdd(lm, p2, tailRing);
611  if (strat == NULL) return 2;
612  if (! kStratChangeTailRing(strat, PR, PW)) return -1;
613  tailRing = strat->tailRing;
614  p1 = PR->GetLmTailRing();
615  p2 = PW->GetLmTailRing();
616  t2 = pNext(p2);
617  lm = p1;
618  p_ExpVectorSub(lm, p2, tailRing);
619  ret = 1;
620  }
621  }
622 
623 #ifdef HAVE_SHIFTBBA
624  poly lmRight;
625  if (tailRing->isLPring) {
626  k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
627  }
628 #endif
629 
630  // take care of coef buisness
631  if (! n_IsOne(pGetCoeff(p2), tailRing))
632  {
633  number bn = pGetCoeff(lm);
634  number an = pGetCoeff(p2);
635  int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
636  p_SetCoeff(lm, bn, tailRing);
637 #ifdef HAVE_SHIFTBBA
638  if (tailRing->isLPring) pSetCoeff0(p1, bn); // lm doesn't point to p1 anymore, if the coef was a pointer, it has been deleted
639 #endif
640  if ((ct == 0) || (ct == 2))
641  PR->Tail_Mult_nn(an);
642  if (coef != NULL) *coef = an;
643  else n_Delete(&an, tailRing);
644  }
645  else
646  {
647  if (coef != NULL) *coef = n_Init(1, tailRing);
648  }
649 
650 
651  // and finally,
652 #ifdef HAVE_SHIFTBBA
653  if (tailRing->isLPring)
654  {
655  PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
656  }
657  else
658 #endif
659  {
660  PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
661  }
662  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
663  PR->LmDeleteAndIter();
664 
665 #if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
666  if (TEST_OPT_DEBUG)
667  {
668  Print(" to: "); PR->wrp(); Print("\n");
669  //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
670  }
671 #endif
672  return ret;
673 }
674 
675 /***************************************************************
676  *
677  * Reduces PR with PW
678  * Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
679  *
680  ***************************************************************/
681 
683  TObject* PW,
684  long /*idx*/,
685  poly spNoether,
686  number *coef,
687  kStrategy strat)
688 {
689 #ifdef KDEBUG
690  red_count++;
691 #ifdef TEST_OPT_DEBUG_RED
692  if (TEST_OPT_DEBUG)
693  {
694  Print("Red %d:", red_count); PR->wrp(); Print(" with:");
695  PW->wrp();
696  }
697 #endif
698 #endif
699  int ret = 0;
700  ring tailRing = PR->tailRing;
701  kTest_L(PR,tailRing);
702  kTest_T(PW);
703 
704  // signature-based stuff:
705  // checking for sig-safeness first
706  // NOTE: This has to be done in the current ring
707  //
708  /**********************************************
709  *
710  * TODO:
711  * --------------------------------------------
712  * if strat->sbaOrder == 1
713  * Since we are subdividing lower index and
714  * current index reductions it is enough to
715  * look at the polynomial part of the signature
716  * for a check. This should speed-up checking
717  * a lot!
718  * if !strat->sbaOrder == 0
719  * We are not subdividing lower and current index
720  * due to the fact that we are using the induced
721  * Schreyer order
722  *
723  * nevertheless, this different behaviour is
724  * taken care of by is_sigsafe
725  * => one reduction procedure can be used for
726  * both, the incremental and the non-incremental
727  * attempt!
728  * --------------------------------------------
729  *
730  *********************************************/
731  //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
732  if (!PW->is_sigsafe)
733  {
734  poly sigMult = pCopy(PW->sig); // copy signature of reducer
735 //#if 1
736 #ifdef DEBUGF5
737  printf("IN KSREDUCEPOLYSIG: \n");
738  pWrite(pHead(f1));
739  pWrite(pHead(f2));
740  pWrite(sigMult);
741  printf("--------------\n");
742 #endif
743  p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
744 //#if 1
745 #ifdef DEBUGF5
746  printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
747  pWrite(pHead(f1));
748  pWrite(pHead(f2));
749  pWrite(sigMult);
750  pWrite(PR->sig);
751  printf("--------------\n");
752 #endif
753  int sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
754  // now we can delete the copied polynomial data used for checking for
755  // sig-safeness of the reduction step
756 //#if 1
757 #ifdef DEBUGF5
758  printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
759 
760 #endif
761  //pDelete(&f1);
762  pDelete(&sigMult);
763  // go on with the computations only if the signature of p2 is greater than the
764  // signature of fm*p1
765  if(sigSafe != 1)
766  {
767  PR->is_redundant = TRUE;
768  return 3;
769  }
770  //PW->is_sigsafe = TRUE;
771  }
772  PR->is_redundant = FALSE;
773  poly p1 = PR->GetLmTailRing(); // p2 | p1
774  poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
775  poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
776  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
777  p_CheckPolyRing(p1, tailRing);
778  p_CheckPolyRing(p2, tailRing);
779 
780  pAssume1(p2 != NULL && p1 != NULL &&
781  p_DivisibleBy(p2, p1, tailRing));
782 
783  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
784  (p_GetComp(p2, tailRing) == 0 &&
785  p_MaxComp(pNext(p2),tailRing) == 0));
786 
787 #ifdef HAVE_PLURAL
788  if (rIsPluralRing(currRing))
789  {
790  // for the time being: we know currRing==strat->tailRing
791  // no exp-bound checking needed
792  // (only needed if exp-bound(tailring)<exp-b(currRing))
793  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
794  else
795  {
796  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
797  assume(_p != NULL);
798  nc_PolyPolyRed(_p, p2, coef, currRing);
799  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
800  PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
801  }
802  return 0;
803  }
804 #endif
805 
806  if (t2==NULL) // Divisor is just one term, therefore it will
807  { // just cancel the leading term
808  PR->LmDeleteAndIter();
809  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
810  return 0;
811  }
812 
813  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
814 
815  if (tailRing != currRing)
816  {
817  // check that reduction does not violate exp bound
818  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
819  {
820  // undo changes of lm
821  p_ExpVectorAdd(lm, p2, tailRing);
822  if (strat == NULL) return 2;
823  if (! kStratChangeTailRing(strat, PR, PW)) return -1;
824  tailRing = strat->tailRing;
825  p1 = PR->GetLmTailRing();
826  p2 = PW->GetLmTailRing();
827  t2 = pNext(p2);
828  lm = p1;
829  p_ExpVectorSub(lm, p2, tailRing);
830  ret = 1;
831  }
832  }
833 
834 #ifdef HAVE_SHIFTBBA
835  poly lmRight;
836  if (tailRing->isLPring) {
837  k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
838  }
839 #endif
840 
841  // take care of coef buisness
842  if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
843  {
844  number bn = pGetCoeff(lm);
845  number an = pGetCoeff(p2);
846  int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
847  p_SetCoeff(lm, bn, tailRing);
848 #ifdef HAVE_SHIFTBBA
849  if (tailRing->isLPring) pSetCoeff0(p1, bn); // lm doesn't point to p1 anymore, if the coef was a pointer, it has been deleted
850 #endif
851  if ((ct == 0) || (ct == 2))
852  PR->Tail_Mult_nn(an);
853  if (coef != NULL) *coef = an;
854  else n_Delete(&an, tailRing->cf);
855  }
856  else
857  {
858  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
859  }
860 
861 
862  // and finally,
863 #ifdef HAVE_SHIFTBBA
864  if (tailRing->isLPring)
865  {
866  PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
867  }
868  else
869 #endif
870  {
871  PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
872  }
873  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
874  PR->LmDeleteAndIter();
875 
876 #if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
877  if (TEST_OPT_DEBUG)
878  {
879  Print(" to: "); PR->wrp(); Print("\n");
880  }
881 #endif
882  return ret;
883 }
884 
886  TObject* PW,
887  long /*idx*/,
888  poly spNoether,
889  number *coef,
890  kStrategy strat)
891 {
892 #ifdef KDEBUG
893  red_count++;
894 #ifdef TEST_OPT_DEBUG_RED
895  if (TEST_OPT_DEBUG)
896  {
897  Print("Red %d:", red_count); PR->wrp(); Print(" with:");
898  PW->wrp();
899  }
900 #endif
901 #endif
902  int ret = 0;
903  ring tailRing = PR->tailRing;
904  kTest_L(PR,tailRing);
905  kTest_T(PW);
906 
907  // signature-based stuff:
908  // checking for sig-safeness first
909  // NOTE: This has to be done in the current ring
910  //
911  /**********************************************
912  *
913  * TODO:
914  * --------------------------------------------
915  * if strat->sbaOrder == 1
916  * Since we are subdividing lower index and
917  * current index reductions it is enough to
918  * look at the polynomial part of the signature
919  * for a check. This should speed-up checking
920  * a lot!
921  * if !strat->sbaOrder == 0
922  * We are not subdividing lower and current index
923  * due to the fact that we are using the induced
924  * Schreyer order
925  *
926  * nevertheless, this different behaviour is
927  * taken care of by is_sigsafe
928  * => one reduction procedure can be used for
929  * both, the incremental and the non-incremental
930  * attempt!
931  * --------------------------------------------
932  *
933  *********************************************/
934  //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
935  if (!PW->is_sigsafe)
936  {
937  poly sigMult = pCopy(PW->sig); // copy signature of reducer
938 //#if 1
939 #ifdef DEBUGF5
940  printf("IN KSREDUCEPOLYSIG: \n");
941  pWrite(pHead(f1));
942  pWrite(pHead(f2));
943  pWrite(sigMult);
944  printf("--------------\n");
945 #endif
946  p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
947  //I have also to set the leading coeficient for sigMult (in the case of rings)
949  {
950  pSetCoeff(sigMult,nMult(nDiv(pGetCoeff(PR->p),pGetCoeff(PW->p)), pGetCoeff(sigMult)));
951  if(nIsZero(pGetCoeff(sigMult)))
952  {
953  sigMult = NULL;
954  }
955  }
956 //#if 1
957 #ifdef DEBUGF5
958  printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
959  pWrite(pHead(f1));
960  pWrite(pHead(f2));
961  pWrite(sigMult);
962  pWrite(PR->sig);
963  printf("--------------\n");
964 #endif
965  int sigSafe;
967  sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
968  // now we can delete the copied polynomial data used for checking for
969  // sig-safeness of the reduction step
970 //#if 1
971 #ifdef DEBUGF5
972  printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
973 
974 #endif
976  {
977  // Set the sig
978  poly origsig = pCopy(PR->sig);
979  if(sigMult != NULL)
980  PR->sig = pHead(pSub(PR->sig, sigMult));
981  //The sigs have the same lm, have to substract
982  //It may happen that now the signature is 0 (drop)
983  if(PR->sig == NULL)
984  {
985  strat->sigdrop=TRUE;
986  }
987  else
988  {
989  if(pLtCmp(PR->sig,origsig) == 1)
990  {
991  // do not allow this reduction - it will increase it's signature
992  // and the partially standard basis is just till the old sig, not the new one
993  PR->is_redundant = TRUE;
994  pDelete(&PR->sig);
995  PR->sig = origsig;
996  strat->blockred++;
997  return 3;
998  }
999  if(pLtCmp(PR->sig,origsig) == -1)
1000  {
1001  strat->sigdrop=TRUE;
1002  }
1003  }
1004  pDelete(&origsig);
1005  }
1006  //pDelete(&f1);
1007  // go on with the computations only if the signature of p2 is greater than the
1008  // signature of fm*p1
1009  if(sigSafe != 1 && !rField_is_Ring(currRing))
1010  {
1011  PR->is_redundant = TRUE;
1012  return 3;
1013  }
1014  //PW->is_sigsafe = TRUE;
1015  }
1016  PR->is_redundant = FALSE;
1017  poly p1 = PR->GetLmTailRing(); // p2 | p1
1018  poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
1019  poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
1020  assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
1021  p_CheckPolyRing(p1, tailRing);
1022  p_CheckPolyRing(p2, tailRing);
1023 
1024  pAssume1(p2 != NULL && p1 != NULL &&
1025  p_DivisibleBy(p2, p1, tailRing));
1026 
1027  pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
1028  (p_GetComp(p2, tailRing) == 0 &&
1029  p_MaxComp(pNext(p2),tailRing) == 0));
1030 
1031 #ifdef HAVE_PLURAL
1032  if (rIsPluralRing(currRing))
1033  {
1034  // for the time being: we know currRing==strat->tailRing
1035  // no exp-bound checking needed
1036  // (only needed if exp-bound(tailring)<exp-b(currRing))
1037  if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef);
1038  else
1039  {
1040  poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
1041  assume(_p != NULL);
1042  nc_PolyPolyRed(_p, p2, coef, currRing);
1043  if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
1044  PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
1045  }
1046  return 0;
1047  }
1048 #endif
1049 
1050  if (t2==NULL) // Divisor is just one term, therefore it will
1051  { // just cancel the leading term
1052  PR->LmDeleteAndIter();
1053  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1054  return 0;
1055  }
1056 
1057  p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
1058 
1059  if (tailRing != currRing)
1060  {
1061  // check that reduction does not violate exp bound
1062  while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
1063  {
1064  // undo changes of lm
1065  p_ExpVectorAdd(lm, p2, tailRing);
1066  if (strat == NULL) return 2;
1067  if (! kStratChangeTailRing(strat, PR, PW)) return -1;
1068  tailRing = strat->tailRing;
1069  p1 = PR->GetLmTailRing();
1070  p2 = PW->GetLmTailRing();
1071  t2 = pNext(p2);
1072  lm = p1;
1073  p_ExpVectorSub(lm, p2, tailRing);
1074  ret = 1;
1075  }
1076  }
1077 
1078 #ifdef HAVE_SHIFTBBA
1079  poly lmRight;
1080  if (tailRing->isLPring) {
1081  k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
1082  }
1083 #endif
1084 
1085  // take care of coef buisness
1087  {
1088  p_SetCoeff(lm, nDiv(pGetCoeff(lm),pGetCoeff(p2)), tailRing);
1089 #ifdef HAVE_SHIFTBBA
1090  if (tailRing->isLPring) pSetCoeff0(p1, pGetCoeff(lm)); // lm doesn't point to p1 anymore, if the coef was a pointer, it has been deleted
1091 #endif
1092  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1093  }
1094  else
1095  {
1096  if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
1097  {
1098  number bn = pGetCoeff(lm);
1099  number an = pGetCoeff(p2);
1100  int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
1101  p_SetCoeff(lm, bn, tailRing);
1102 #ifdef HAVE_SHIFTBBA
1103  if (tailRing->isLPring) pSetCoeff0(p1, bn); // lm doesn't point to p1 anymore, if the coef was a pointer, it has been deleted
1104 #endif
1105  if (((ct == 0) || (ct == 2)))
1106  PR->Tail_Mult_nn(an);
1107  if (coef != NULL) *coef = an;
1108  else n_Delete(&an, tailRing->cf);
1109  }
1110  else
1111  {
1112  if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1113  }
1114  }
1115 
1116  // and finally,
1117 #ifdef HAVE_SHIFTBBA
1118  if (tailRing->isLPring)
1119  {
1120  PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
1121  }
1122  else
1123 #endif
1124  {
1125  PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
1126  }
1127  assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
1128  PR->LmDeleteAndIter();
1129 
1130 #if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
1131  if (TEST_OPT_DEBUG)
1132  {
1133  Print(" to: "); PR->wrp(); Print("\n");
1134  }
1135 #endif
1136  return ret;
1137 }
1138 
1139 /***************************************************************
1140  *
1141  * Creates S-Poly of p1 and p2
1142  *
1143  *
1144  ***************************************************************/
1145 void ksCreateSpoly(LObject* Pair, poly spNoether,
1146  int use_buckets, ring tailRing,
1147  poly m1, poly m2, TObject** R)
1148 {
1149 #ifdef KDEBUG
1150  create_count++;
1151 #endif
1152  kTest_L(Pair,tailRing);
1153  poly p1 = Pair->p1;
1154  poly p2 = Pair->p2;
1155  Pair->tailRing = tailRing;
1156 
1157  assume(p1 != NULL);
1158  assume(p2 != NULL);
1159  assume(tailRing != NULL);
1160 
1161  poly a1 = pNext(p1), a2 = pNext(p2);
1162  number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1163  int co=0/*, ct = ksCheckCoeff(&lc1, &lc2, currRing->cf)*/; // gcd and zero divisors
1164  (void) ksCheckCoeff(&lc1, &lc2, currRing->cf);
1165 
1166  int l1=0, l2=0;
1167 
1168  if (currRing->pCompIndex >= 0)
1169  {
1170  if (__p_GetComp(p1, currRing)!=__p_GetComp(p2, currRing))
1171  {
1172  if (__p_GetComp(p1, currRing)==0)
1173  {
1174  co=1;
1175  p_SetCompP(p1,__p_GetComp(p2, currRing), currRing, tailRing);
1176  }
1177  else
1178  {
1179  co=2;
1180  p_SetCompP(p2, __p_GetComp(p1, currRing), currRing, tailRing);
1181  }
1182  }
1183  }
1184 
1185  // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
1186  // m2 = LCM(LM(p1), LM(p2))/LM(p2)
1187  if (m1 == NULL)
1188  k_GetLeadTerms(p1, p2, currRing, m1, m2, tailRing);
1189 
1190 #ifdef HAVE_SHIFTBBA
1191  poly m12, m22;
1192  if (tailRing->isLPring)
1193  {
1194  // note: because of the crits, p2 is never shifted
1195  int split = p_mFirstVblock(p1, tailRing);
1196  k_SplitFrame(m1, m12, split, tailRing);
1197  k_SplitFrame(m2, m22, split, tailRing);
1198  // manually free the coeffs, because pSetCoeff0 is used in the next step
1199  n_Delete(&(m1->coef), tailRing->cf);
1200  n_Delete(&(m2->coef), tailRing->cf);
1201  }
1202 #endif
1203 
1204  pSetCoeff0(m1, lc2);
1205  pSetCoeff0(m2, lc1); // and now, m1 * LT(p1) == m2 * LT(p2)
1206 
1207  if (R != NULL)
1208  {
1209  if (Pair->i_r1 == -1)
1210  {
1211  l1 = pLength(p1) - 1;
1212  }
1213  else
1214  {
1215  l1 = (R[Pair->i_r1])->GetpLength() - 1;
1216  }
1217  if ((Pair->i_r2 == -1)||(R[Pair->i_r2]==NULL))
1218  {
1219  l2 = pLength(p2) - 1;
1220  }
1221  else
1222  {
1223  l2 = (R[Pair->i_r2])->GetpLength() - 1;
1224  }
1225  }
1226 
1227  // get m2 * a2
1228  if (spNoether != NULL)
1229  {
1230  l2 = -1;
1231  a2 = tailRing->p_Procs->pp_Mult_mm_Noether(a2, m2, spNoether, l2, tailRing);
1232  assume(l2 == pLength(a2));
1233  }
1234  else
1235 #ifdef HAVE_SHIFTBBA
1236  if (tailRing->isLPring)
1237  {
1238  // m2*a2*m22
1239  a2 = tailRing->p_Procs->pp_Mult_mm(tailRing->p_Procs->pp_mm_Mult(a2, m2, tailRing), m22, tailRing);
1240  }
1241  else
1242 #endif
1243  {
1244  a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, tailRing);
1245  }
1246 #ifdef HAVE_RINGS
1247  if (!(rField_is_Domain(currRing))) l2 = pLength(a2);
1248 #endif
1249 
1250  Pair->SetLmTail(m2, a2, l2, use_buckets, tailRing);
1251 
1252 #ifdef HAVE_SHIFTBBA
1253  if (tailRing->isLPring)
1254  {
1255  // get m2*a2*m22 - m1*a1*m12
1256  Pair->Tail_Minus_mm_Mult_qq(m1, tailRing->p_Procs->pp_Mult_mm(a1, m12, tailRing), l1, spNoether);
1257  }
1258  else
1259 #endif
1260  {
1261  // get m2*a2 - m1*a1
1262  Pair->Tail_Minus_mm_Mult_qq(m1, a1, l1, spNoether);
1263  }
1264 
1265  // Clean-up time
1266  Pair->LmDeleteAndIter();
1267  p_LmDelete(m1, tailRing);
1268 #ifdef HAVE_SHIFTBBA
1269  if (tailRing->isLPring)
1270  {
1271  p_LmDelete(m12, tailRing);
1272  p_LmDelete(m22, tailRing);
1273  // m2 is already deleted
1274  }
1275 #endif
1276 
1277  if (co != 0)
1278  {
1279  if (co==1)
1280  {
1281  p_SetCompP(p1,0, currRing, tailRing);
1282  }
1283  else
1284  {
1285  p_SetCompP(p2,0, currRing, tailRing);
1286  }
1287  }
1288 }
1289 
1290 int ksReducePolyTail(LObject* PR, TObject* PW, poly Current, poly spNoether)
1291 {
1292  BOOLEAN ret;
1293  number coef;
1294  poly Lp = PR->GetLmCurrRing();
1295  poly Save = PW->GetLmCurrRing();
1296 
1297  kTest_L(PR,PR->tailRing);
1298  kTest_T(PW);
1299  pAssume(pIsMonomOf(Lp, Current));
1300 
1301  assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1302  assume(PR->bucket == NULL);
1303 
1304  LObject Red(pNext(Current), PR->tailRing);
1305  TObject With(PW, Lp == Save);
1306 
1307  pAssume(!pHaveCommonMonoms(Red.p, With.p));
1308  ret = ksReducePoly(&Red, &With, spNoether, &coef);
1309 
1310  if (!ret)
1311  {
1312  if (! n_IsOne(coef, currRing->cf))
1313  {
1314  pNext(Current) = NULL;
1315  if (Current == PR->p && PR->t_p != NULL)
1316  pNext(PR->t_p) = NULL;
1317  PR->Mult_nn(coef);
1318  }
1319 
1320  n_Delete(&coef, currRing->cf);
1321  pNext(Current) = Red.GetLmTailRing();
1322  if (Current == PR->p && PR->t_p != NULL)
1323  pNext(PR->t_p) = pNext(Current);
1324  }
1325 
1326  if (Lp == Save)
1327  With.Delete();
1328 
1329  return ret;
1330 }
1331 
1332 int ksReducePolyTailBound(LObject* PR, TObject* PW, int bound, poly Current, poly spNoether)
1333 {
1334  BOOLEAN ret;
1335  number coef;
1336  poly Lp = PR->GetLmCurrRing();
1337  poly Save = PW->GetLmCurrRing();
1338 
1339  kTest_L(PR,PR->tailRing);
1340  kTest_T(PW);
1341  pAssume(pIsMonomOf(Lp, Current));
1342 
1343  assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1344  assume(PR->bucket == NULL);
1345 
1346  LObject Red(pNext(Current), PR->tailRing);
1347  TObject With(PW, Lp == Save);
1348 
1349  pAssume(!pHaveCommonMonoms(Red.p, With.p));
1350  ret = ksReducePolyBound(&Red, &With,bound, spNoether, &coef);
1351 
1352  if (!ret)
1353  {
1354  if (! n_IsOne(coef, currRing))
1355  {
1356  pNext(Current) = NULL;
1357  if (Current == PR->p && PR->t_p != NULL)
1358  pNext(PR->t_p) = NULL;
1359  PR->Mult_nn(coef);
1360  }
1361 
1362  n_Delete(&coef, currRing);
1363  pNext(Current) = Red.GetLmTailRing();
1364  if (Current == PR->p && PR->t_p != NULL)
1365  pNext(PR->t_p) = pNext(Current);
1366  }
1367 
1368  if (Lp == Save)
1369  With.Delete();
1370 
1371  return ret;
1372 }
1373 
1374 /***************************************************************
1375  *
1376  * Auxillary Routines
1377  *
1378  *
1379  ***************************************************************/
1380 
1381 /*2
1382 * creates the leading term of the S-polynomial of p1 and p2
1383 * do not destroy p1 and p2
1384 * remarks:
1385 * 1. the coefficient is 0 (p_Init)
1386 * 1. a) in the case of coefficient ring, the coefficient is calculated
1387 * 2. pNext is undefined
1388 */
1389 //static void bbb() { int i=0; }
1390 poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
1391 {
1392  poly a1 = pNext(p1), a2 = pNext(p2);
1393 #ifdef HAVE_SHIFTBBA
1394  int shift1, shift2;
1395  if (tailRing->isLPring) {
1396  // assume: LM is shifted, tail unshifted
1397  assume(p_FirstVblock(a1, tailRing) <= 1);
1398  assume(p_FirstVblock(a2, tailRing) <= 1);
1399  // save the shift of the LM so we can shift the other monomials on demand
1400  shift1 = p_mFirstVblock(p1, tailRing) - 1;
1401  shift2 = p_mFirstVblock(p2, tailRing) - 1;
1402  }
1403 #endif
1404  long c1=p_GetComp(p1, currRing),c2=p_GetComp(p2, currRing);
1405  long c;
1406  poly m1,m2;
1407  number t1 = NULL,t2 = NULL;
1408  int cm,i;
1409  BOOLEAN equal;
1410 
1411 #ifdef HAVE_RINGS
1412  BOOLEAN is_Ring=rField_is_Ring(currRing);
1413  number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1414  if (is_Ring)
1415  {
1416  ksCheckCoeff(&lc1, &lc2, currRing->cf); // gcd and zero divisors
1417  if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
1418  if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
1419  while (a1 != NULL && nIsZero(t2))
1420  {
1421  pIter(a1);
1422  nDelete(&t2);
1423  if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
1424  }
1425  while (a2 != NULL && nIsZero(t1))
1426  {
1427  pIter(a2);
1428  nDelete(&t1);
1429  if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
1430  }
1431  }
1432 #endif
1433 
1434 #ifdef HAVE_SHIFTBBA
1435  // shift the next monomial on demand
1436  if (tailRing->isLPring)
1437  {
1438  a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
1439  a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
1440  }
1441 #endif
1442  if (a1==NULL)
1443  {
1444  if(a2!=NULL)
1445  {
1446  m2=p_Init(currRing);
1447 x2:
1448  for (i = (currRing->N); i; i--)
1449  {
1450  c = p_GetExpDiff(p1, p2,i, currRing);
1451  if (c>0)
1452  {
1453  p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)),currRing);
1454  }
1455  else
1456  {
1457  p_SetExp(m2,i,p_GetExp(a2,i,tailRing),currRing);
1458  }
1459  }
1460  if ((c1==c2)||(c2!=0))
1461  {
1462  p_SetComp(m2,p_GetComp(a2,tailRing), currRing);
1463  }
1464  else
1465  {
1466  p_SetComp(m2,c1,currRing);
1467  }
1468  p_Setm(m2, currRing);
1469 #ifdef HAVE_RINGS
1470  if (is_Ring)
1471  {
1472  nDelete(&lc1);
1473  nDelete(&lc2);
1474  nDelete(&t2);
1475  pSetCoeff0(m2, t1);
1476  }
1477 #endif
1478  return m2;
1479  }
1480  else
1481  {
1482 #ifdef HAVE_RINGS
1483  if (is_Ring)
1484  {
1485  nDelete(&lc1);
1486  nDelete(&lc2);
1487  nDelete(&t1);
1488  nDelete(&t2);
1489  }
1490 #endif
1491  return NULL;
1492  }
1493  }
1494  if (a2==NULL)
1495  {
1496  m1=p_Init(currRing);
1497 x1:
1498  for (i = (currRing->N); i; i--)
1499  {
1500  c = p_GetExpDiff(p2, p1,i,currRing);
1501  if (c>0)
1502  {
1503  p_SetExp(m1,i,(c+p_GetExp(a1,i, tailRing)),currRing);
1504  }
1505  else
1506  {
1507  p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
1508  }
1509  }
1510  if ((c1==c2)||(c1!=0))
1511  {
1512  p_SetComp(m1,p_GetComp(a1,tailRing),currRing);
1513  }
1514  else
1515  {
1516  p_SetComp(m1,c2,currRing);
1517  }
1518  p_Setm(m1, currRing);
1519 #ifdef HAVE_RINGS
1520  if (is_Ring)
1521  {
1522  pSetCoeff0(m1, t2);
1523  nDelete(&lc1);
1524  nDelete(&lc2);
1525  nDelete(&t1);
1526  }
1527 #endif
1528  return m1;
1529  }
1530  m1 = p_Init(currRing);
1531  m2 = p_Init(currRing);
1532  loop
1533  {
1534  for (i = (currRing->N); i; i--)
1535  {
1536  c = p_GetExpDiff(p1, p2,i,currRing);
1537  if (c > 0)
1538  {
1539  p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)), currRing);
1540  p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
1541  }
1542  else
1543  {
1544  p_SetExp(m1,i,(p_GetExp(a1,i,tailRing)-c), currRing);
1545  p_SetExp(m2,i,p_GetExp(a2,i, tailRing), currRing);
1546  }
1547  }
1548  if(c1==c2)
1549  {
1550  p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
1551  p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
1552  }
1553  else
1554  {
1555  if(c1!=0)
1556  {
1557  p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
1558  p_SetComp(m2,c1, currRing);
1559  }
1560  else
1561  {
1562  p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
1563  p_SetComp(m1,c2, currRing);
1564  }
1565  }
1566  p_Setm(m1,currRing);
1567  p_Setm(m2,currRing);
1568  cm = p_LmCmp(m1, m2,currRing);
1569  if (cm!=0)
1570  {
1571  if(cm==1)
1572  {
1573  p_LmFree(m2,currRing);
1574 #ifdef HAVE_RINGS
1575  if (is_Ring)
1576  {
1577  pSetCoeff0(m1, t2);
1578  nDelete(&lc1);
1579  nDelete(&lc2);
1580  nDelete(&t1);
1581  }
1582 #endif
1583  return m1;
1584  }
1585  else
1586  {
1587  p_LmFree(m1,currRing);
1588 #ifdef HAVE_RINGS
1589  if (is_Ring)
1590  {
1591  pSetCoeff0(m2, t1);
1592  nDelete(&lc1);
1593  nDelete(&lc2);
1594  nDelete(&t2);
1595  }
1596 #endif
1597  return m2;
1598  }
1599  }
1600 #ifdef HAVE_RINGS
1601  if (is_Ring)
1602  {
1603  equal = nEqual(t1,t2);
1604  }
1605  else
1606 #endif
1607  {
1608  t1 = nMult(pGetCoeff(a2),pGetCoeff(p1));
1609  t2 = nMult(pGetCoeff(a1),pGetCoeff(p2));
1610  equal = nEqual(t1,t2);
1611  nDelete(&t2);
1612  nDelete(&t1);
1613  }
1614  if (!equal)
1615  {
1616  p_LmFree(m2,currRing);
1617 #ifdef HAVE_RINGS
1618  if (is_Ring)
1619  {
1620  pSetCoeff0(m1, nSub(t1, t2));
1621  nDelete(&lc1);
1622  nDelete(&lc2);
1623  nDelete(&t1);
1624  nDelete(&t2);
1625  }
1626 #endif
1627  return m1;
1628  }
1629  pIter(a1);
1630  pIter(a2);
1631 #ifdef HAVE_RINGS
1632  if (is_Ring)
1633  {
1634  if (a2 != NULL)
1635  {
1636  nDelete(&t1);
1637  t1 = nMult(pGetCoeff(a2),lc1);
1638  }
1639  if (a1 != NULL)
1640  {
1641  nDelete(&t2);
1642  t2 = nMult(pGetCoeff(a1),lc2);
1643  }
1644  while ((a1 != NULL) && nIsZero(t2))
1645  {
1646  pIter(a1);
1647  if (a1 != NULL)
1648  {
1649  nDelete(&t2);
1650  t2 = nMult(pGetCoeff(a1),lc2);
1651  }
1652  }
1653  while ((a2 != NULL) && nIsZero(t1))
1654  {
1655  pIter(a2);
1656  if (a2 != NULL)
1657  {
1658  nDelete(&t1);
1659  t1 = nMult(pGetCoeff(a2),lc1);
1660  }
1661  }
1662  }
1663 #endif
1664 #ifdef HAVE_SHIFTBBA
1665  if (tailRing->isLPring)
1666  {
1667  a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
1668  a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
1669  }
1670 #endif
1671  if (a2==NULL)
1672  {
1673  p_LmFree(m2,currRing);
1674  if (a1==NULL)
1675  {
1676 #ifdef HAVE_RINGS
1677  if (is_Ring)
1678  {
1679  nDelete(&lc1);
1680  nDelete(&lc2);
1681  nDelete(&t1);
1682  nDelete(&t2);
1683  }
1684 #endif
1685  p_LmFree(m1,currRing);
1686  return NULL;
1687  }
1688  goto x1;
1689  }
1690  if (a1==NULL)
1691  {
1692  p_LmFree(m1,currRing);
1693  goto x2;
1694  }
1695  }
1696 }
#define __p_GetComp(p, r)
Definition: monomials.h:63
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:431
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition: kInline.h:964
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
#define Print
Definition: emacs.cc:80
void nc_PolyPolyRed(poly &b, poly p, number *c, const ring r)
Definition: old.gring.cc:2230
class sLObject LObject
Definition: kutil.h:54
bool sigdrop
Definition: kutil.h:358
#define FALSE
Definition: auxiliary.h:94
Compatiblity layer for legacy polynomial operations (over currRing)
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:468
#define pAssume(cond)
Definition: monomials.h:90
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:246
#define p_GetComp(p, r)
Definition: monomials.h:64
static BOOLEAN p_LmExpVectorAddIsOk(const poly p1, const poly p2, const ring r)
Definition: p_polys.h:1962
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:538
int ksCheckCoeff(number *a, number *b)
int ksReducePolyTailBound(LObject *PR, TObject *PW, int bound, poly Current, poly spNoether)
Definition: kspoly.cc:1332
int p_mFirstVblock(poly p, const ring ri)
Definition: shiftop.cc:469
#define pLtCmp(p, q)
Definition: polys.h:123
#define TRUE
Definition: auxiliary.h:98
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:185
static BOOLEAN rField_is_Domain(const ring r)
Definition: ring.h:482
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:44
void pWrite(poly p)
Definition: polys.h:303
#define TEST_OPT_DEBUG
Definition: options.h:107
#define nEqual(n1, n2)
Definition: numbers.h:20
#define loop
Definition: structs.h:80
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
Definition: monomials.h:44
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition: kspoly.cc:1390
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition: pDebug.cc:173
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:411
static void p_LmFree(poly p, ring)
Definition: p_polys.h:682
BOOLEAN pIsMonomOf(poly p, poly m)
Definition: pDebug.cc:163
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:682
#define pIter(p)
Definition: monomials.h:37
BOOLEAN p_CheckPolyRing(poly p, ring r)
Definition: pDebug.cc:110
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition: p_polys.h:634
bool equal
Definition: cfModGcd.cc:4067
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:253
#define pSub(a, b)
Definition: polys.h:282
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:468
#define assume(x)
Definition: mod2.h:390
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:397
#define kTest_L(T, R)
Definition: kutil.h:657
#define nMult(n1, n2)
Definition: numbers.h:17
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:1145
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:315
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1828
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1496
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11377
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:557
#define nSub(n1, n2)
Definition: numbers.h:22
int red_count
Definition: kspoly.cc:27
int i
Definition: cfEzgcd.cc:125
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1375
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1346
#define pOne()
Definition: polys.h:310
static unsigned pLength(poly a)
Definition: p_polys.h:191
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
#define nDelete(n)
Definition: numbers.h:16
static void nc_kBucketPolyRed_Z(kBucket_pt b, poly p, number *c)
Definition: nc.h:286
static FORCE_INLINE number n_ExtGcd(number a, number b, number *s, number *t, const coeffs r)
beware that ExtGCD is only relevant for a few chosen coeff. domains and may perform something unexpec...
Definition: coeffs.h:693
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
int ksReducePolyBound(LObject *PR, TObject *PW, int bound, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:538
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:487
#define nDiv(a, b)
Definition: numbers.h:32
char homog
Definition: kutil.h:370
#define nIsZero(n)
Definition: numbers.h:19
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:479
#define NULL
Definition: omList.c:12
int create_count
Definition: kspoly.cc:28
ring tailRing
Definition: kutil.h:341
#define R
Definition: sirandom.c:26
int blockred
Definition: kutil.h:363
poly p_LPCopyAndShiftLM(poly p, int sh, const ring r)
Definition: shiftgb.cc:35
#define pDelete(p_ptr)
Definition: polys.h:181
int p_FirstVblock(poly p, const ring r)
Definition: shiftop.cc:447
#define pNext(p)
Definition: monomials.h:36
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:232
#define pSetCoeff0(p, n)
Definition: monomials.h:59
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:710
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:455
#define kTest_T(T)
Definition: kutil.h:655
static void p_ExpVectorAddSub(poly p1, poly p2, poly p3, const ring r)
Definition: p_polys.h:1391
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether)
Definition: kspoly.cc:1290
int BOOLEAN
Definition: auxiliary.h:85
#define pAssume1(cond)
Definition: monomials.h:171
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1255
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition: polys.h:31
class sTObject TObject
Definition: kutil.h:53
void k_SplitFrame(poly &m1, poly &m2, int at, const ring r)
Definition: shiftop.cc:585
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:291
#define pCopy(p)
return a copy of the poly
Definition: polys.h:180
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:885