source: git/kernel/GBEngine/kspoly.cc @ 486d31

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