source: git/kernel/GBEngine/kspoly.cc

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