My Project
Loading...
Searching...
No Matches
kspoly.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT - Routines for Spoly creation and reductions
6*/
7
8// #define PDEBUG 2
9
10
11
12#include "kernel/mod2.h"
13#include "misc/options.h"
14#include "kernel/GBEngine/kutil.h"
15#include "coeffs/numbers.h"
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 lm = p1; // 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 lm = p1;
550 p_ExpVectorSub(lm, p2, tailRing);
551 ret = 1;
552 }
553
554#ifdef HAVE_SHIFTBBA
555 poly lmRight;
556 if (tailRing->isLPring)
557 {
558 assume(PR->shift == 0);
559 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
560 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
561 }
562#endif
563
564 // and finally,
565#ifdef HAVE_SHIFTBBA
566 if (tailRing->isLPring)
567 {
568 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(p2, lmRight, tailRing), pLength(p2), spNoether);
569 }
570 else
571#endif
572 {
573 PR->Tail_Minus_mm_Mult_qq(lm, p2, pLength(p2) /*PW->GetpLength() - 1*/, spNoether);
574 }
575 assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
576
577 PR->LmDeleteAndIter();
578 p_SetCoeff(PR->p, *coef, currRing);
579
580#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
581 if (TEST_OPT_DEBUG)
582 {
583 Print(" to: "); PR->wrp(); Print("\n");
584 //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
585 }
586#endif
587 return ret;
588}
589
590int ksReducePolyBound(LObject* PR,
591 TObject* PW,
592 int /*bound*/,
593 poly spNoether,
594 number *coef,
595 kStrategy strat)
596{
597#ifdef KDEBUG
598 red_count++;
599#ifdef TEST_OPT_DEBUG_RED
600 if (TEST_OPT_DEBUG)
601 {
602 Print("Red %d:", red_count); PR->wrp(); Print(" with:");
603 PW->wrp();
604 //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
605 //pWrite(PR->p);
606 }
607#endif
608#endif
609 int ret = 0;
610 ring tailRing = PR->tailRing;
611 if (strat!=NULL)
612 {
613 kTest_L(PR,strat);
614 kTest_T(PW,strat);
615 }
616
617 poly p1 = PR->GetLmTailRing(); // p2 | p1
618 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
619 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
620 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
621 p_CheckPolyRing(p1, tailRing);
622 p_CheckPolyRing(p2, tailRing);
623
624 pAssume1(p2 != NULL && p1 != NULL &&
625 p_DivisibleBy(p2, p1, tailRing));
626
627 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
628 (p_GetComp(p2, tailRing) == 0 &&
629 p_MaxComp(pNext(p2),tailRing) == 0));
630
631#ifdef HAVE_PLURAL
632 if (rIsPluralRing(currRing))
633 {
634 // for the time being: we know currRing==strat->tailRing
635 // no exp-bound checking needed
636 // (only needed if exp-bound(tailring)<exp-b(currRing))
637 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
638 else
639 {
640 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
641 assume(_p != NULL);
642 nc_PolyPolyRed(_p, p2,coef, currRing);
643 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
644 PR->pLength=0; // usually not used, GetpLength re-computes it if needed
645 }
646 return 0;
647 }
648#endif
649
650 if (t2==NULL) // Divisor is just one term, therefore it will
651 { // just cancel the leading term
652 PR->LmDeleteAndIter();
653 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
654 return 0;
655 }
656
657 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
658
659 if (tailRing != currRing)
660 {
661 // check that reduction does not violate exp bound
662 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
663 {
664 // undo changes of lm
665 p_ExpVectorAdd(lm, p2, tailRing);
666 if (strat == NULL) return 2;
667 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
668 tailRing = strat->tailRing;
669 p1 = PR->GetLmTailRing();
670 p2 = PW->GetLmTailRing();
671 t2 = pNext(p2);
672 lm = p1;
673 p_ExpVectorSub(lm, p2, tailRing);
674 ret = 1;
675 }
676 }
677
678#ifdef HAVE_SHIFTBBA
679 poly lmRight;
680 if (tailRing->isLPring)
681 {
682 assume(PR->shift == 0);
683 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
684 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
685 }
686#endif
687
688 // take care of coef business
689 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
690 {
691 number bn = pGetCoeff(lm);
692 number an = pGetCoeff(p2);
693 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
694 p_SetCoeff(lm, bn, tailRing);
695 if ((ct == 0) || (ct == 2))
696 PR->Tail_Mult_nn(an);
697 if (coef != NULL) *coef = an;
698 else n_Delete(&an, tailRing->cf);
699 }
700 else
701 {
702 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
703 }
704
705
706 // and finally,
707#ifdef HAVE_SHIFTBBA
708 if (tailRing->isLPring)
709 {
710 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
711 }
712 else
713#endif
714 {
715 PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
716 }
717 assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
718 PR->LmDeleteAndIter();
719
720#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
721 if (TEST_OPT_DEBUG)
722 {
723 Print(" to: "); PR->wrp(); Print("\n");
724 //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
725 }
726#endif
727 return ret;
728}
729
730/***************************************************************
731 *
732 * Reduces PR with PW
733 * Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
734 *
735 ***************************************************************/
736
737int ksReducePolySig(LObject* PR,
738 TObject* PW,
739 long /*idx*/,
740 poly spNoether,
741 number *coef,
742 kStrategy strat)
743{
744#ifdef KDEBUG
745 red_count++;
746#ifdef TEST_OPT_DEBUG_RED
747 if (TEST_OPT_DEBUG)
748 {
749 Print("Red %d:", red_count); PR->wrp(); Print(" with:");
750 PW->wrp();
751 }
752#endif
753#endif
754 int ret = 0;
755 ring tailRing = PR->tailRing;
756 if (strat!=NULL)
757 {
758 kTest_L(PR,strat);
759 kTest_T(PW,strat);
760 }
761
762 // signature-based stuff:
763 // checking for sig-safeness first
764 // NOTE: This has to be done in the current ring
765 //
766 /**********************************************
767 *
768 * TODO:
769 * --------------------------------------------
770 * if strat->sbaOrder == 1
771 * Since we are subdividing lower index and
772 * current index reductions it is enough to
773 * look at the polynomial part of the signature
774 * for a check. This should speed-up checking
775 * a lot!
776 * if !strat->sbaOrder == 0
777 * We are not subdividing lower and current index
778 * due to the fact that we are using the induced
779 * Schreyer order
780 *
781 * nevertheless, this different behaviour is
782 * taken care of by is_sigsafe
783 * => one reduction procedure can be used for
784 * both, the incremental and the non-incremental
785 * attempt!
786 * --------------------------------------------
787 *
788 *********************************************/
789 //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
790 if (!PW->is_sigsafe)
791 {
792 poly sigMult = pCopy(PW->sig); // copy signature of reducer
793//#if 1
794#ifdef DEBUGF5
795 printf("IN KSREDUCEPOLYSIG: \n");
796 pWrite(pHead(f1));
797 pWrite(pHead(f2));
798 pWrite(sigMult);
799 printf("--------------\n");
800#endif
801 p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
802//#if 1
803#ifdef DEBUGF5
804 printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
805 pWrite(pHead(f1));
806 pWrite(pHead(f2));
807 pWrite(sigMult);
808 pWrite(PR->sig);
809 printf("--------------\n");
810#endif
811 int sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
812 // now we can delete the copied polynomial data used for checking for
813 // sig-safeness of the reduction step
814//#if 1
815#ifdef DEBUGF5
816 printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
817
818#endif
819 //pDelete(&f1);
820 pDelete(&sigMult);
821 // go on with the computations only if the signature of p2 is greater than the
822 // signature of fm*p1
823 if(sigSafe != 1)
824 {
825 PR->is_redundant = TRUE;
826 return 3;
827 }
828 //PW->is_sigsafe = TRUE;
829 }
830 PR->is_redundant = FALSE;
831 poly p1 = PR->GetLmTailRing(); // p2 | p1
832 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
833 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
834 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
835 p_CheckPolyRing(p1, tailRing);
836 p_CheckPolyRing(p2, tailRing);
837
838 pAssume1(p2 != NULL && p1 != NULL &&
839 p_DivisibleBy(p2, p1, tailRing));
840
841 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
842 (p_GetComp(p2, tailRing) == 0 &&
843 p_MaxComp(pNext(p2),tailRing) == 0));
844
845#ifdef HAVE_PLURAL
846 if (rIsPluralRing(currRing))
847 {
848 // for the time being: we know currRing==strat->tailRing
849 // no exp-bound checking needed
850 // (only needed if exp-bound(tailring)<exp-b(currRing))
851 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
852 else
853 {
854 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
855 assume(_p != NULL);
856 nc_PolyPolyRed(_p, p2, coef, currRing);
857 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
858 PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
859 }
860 return 0;
861 }
862#endif
863
864 if (t2==NULL) // Divisor is just one term, therefore it will
865 { // just cancel the leading term
866 PR->LmDeleteAndIter();
867 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
868 return 0;
869 }
870
871 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
872
873 if (tailRing != currRing)
874 {
875 // check that reduction does not violate exp bound
876 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
877 {
878 // undo changes of lm
879 p_ExpVectorAdd(lm, p2, tailRing);
880 if (strat == NULL) return 2;
881 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
882 tailRing = strat->tailRing;
883 p1 = PR->GetLmTailRing();
884 p2 = PW->GetLmTailRing();
885 t2 = pNext(p2);
886 lm = p1;
887 p_ExpVectorSub(lm, p2, tailRing);
888 ret = 1;
889 }
890 }
891
892#ifdef HAVE_SHIFTBBA
893 poly lmRight;
894 if (tailRing->isLPring)
895 {
896 assume(PR->shift == 0);
897 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
898 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
899 }
900#endif
901
902 // take care of coef business
903 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
904 {
905 number bn = pGetCoeff(lm);
906 number an = pGetCoeff(p2);
907 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
908 p_SetCoeff(lm, bn, tailRing);
909 if ((ct == 0) || (ct == 2))
910 PR->Tail_Mult_nn(an);
911 if (coef != NULL) *coef = an;
912 else n_Delete(&an, tailRing->cf);
913 }
914 else
915 {
916 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
917 }
918
919
920 // and finally,
921#ifdef HAVE_SHIFTBBA
922 if (tailRing->isLPring)
923 {
924 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
925 }
926 else
927#endif
928 {
929 PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
930 }
931 assume(PW->GetpLength() == (int)pLength(PW->p != NULL ? PW->p : PW->t_p));
932 PR->LmDeleteAndIter();
933
934#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
935 if (TEST_OPT_DEBUG)
936 {
937 Print(" to: "); PR->wrp(); Print("\n");
938 }
939#endif
940 return ret;
941}
942
943int ksReducePolySigRing(LObject* PR,
944 TObject* PW,
945 long /*idx*/,
946 poly spNoether,
947 number *coef,
948 kStrategy strat)
949{
950#ifdef KDEBUG
951 red_count++;
952#ifdef TEST_OPT_DEBUG_RED
953 if (TEST_OPT_DEBUG)
954 {
955 Print("Red %d:", red_count); PR->wrp(); Print(" with:");
956 PW->wrp();
957 }
958#endif
959#endif
960 int ret = 0;
961 ring tailRing = PR->tailRing;
962 if (strat!=NULL)
963 {
964 kTest_L(PR,strat);
965 kTest_T(PW,strat);
966 }
967
968 // signature-based stuff:
969 // checking for sig-safeness first
970 // NOTE: This has to be done in the current ring
971 //
972 /**********************************************
973 *
974 * TODO:
975 * --------------------------------------------
976 * if strat->sbaOrder == 1
977 * Since we are subdividing lower index and
978 * current index reductions it is enough to
979 * look at the polynomial part of the signature
980 * for a check. This should speed-up checking
981 * a lot!
982 * if !strat->sbaOrder == 0
983 * We are not subdividing lower and current index
984 * due to the fact that we are using the induced
985 * Schreyer order
986 *
987 * nevertheless, this different behaviour is
988 * taken care of by is_sigsafe
989 * => one reduction procedure can be used for
990 * both, the incremental and the non-incremental
991 * attempt!
992 * --------------------------------------------
993 *
994 *********************************************/
995 //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
996 if (!PW->is_sigsafe)
997 {
998 poly sigMult = pCopy(PW->sig); // copy signature of reducer
999//#if 1
1000#ifdef DEBUGF5
1001 printf("IN KSREDUCEPOLYSIG: \n");
1002 pWrite(pHead(f1));
1003 pWrite(pHead(f2));
1004 pWrite(sigMult);
1005 printf("--------------\n");
1006#endif
1007 p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
1008 //I have also to set the leading coefficient for sigMult (in the case of rings)
1009 if(rField_is_Ring(currRing))
1010 {
1011 pSetCoeff(sigMult,nMult(nDiv(pGetCoeff(PR->p),pGetCoeff(PW->p)), pGetCoeff(sigMult)));
1012 if(nIsZero(pGetCoeff(sigMult)))
1013 {
1014 sigMult = NULL;
1015 }
1016 }
1017//#if 1
1018#ifdef DEBUGF5
1019 printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
1020 pWrite(pHead(f1));
1021 pWrite(pHead(f2));
1022 pWrite(sigMult);
1023 pWrite(PR->sig);
1024 printf("--------------\n");
1025#endif
1026 int sigSafe;
1027 if(!rField_is_Ring(currRing))
1028 sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
1029 // now we can delete the copied polynomial data used for checking for
1030 // sig-safeness of the reduction step
1031//#if 1
1032#ifdef DEBUGF5
1033 printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
1034
1035#endif
1036 if(rField_is_Ring(currRing))
1037 {
1038 // Set the sig
1039 poly origsig = pCopy(PR->sig);
1040 if(sigMult != NULL)
1041 PR->sig = pHead(pSub(PR->sig, sigMult));
1042 //The sigs have the same lm, have to subtract
1043 //It may happen that now the signature is 0 (drop)
1044 if(PR->sig == NULL)
1045 {
1046 strat->sigdrop=TRUE;
1047 }
1048 else
1049 {
1050 if(pLtCmp(PR->sig,origsig) == 1)
1051 {
1052 // do not allow this reduction - it will increase it's signature
1053 // and the partially standard basis is just till the old sig, not the new one
1054 PR->is_redundant = TRUE;
1055 pDelete(&PR->sig);
1056 PR->sig = origsig;
1057 strat->blockred++;
1058 return 3;
1059 }
1060 if(pLtCmp(PR->sig,origsig) == -1)
1061 {
1062 strat->sigdrop=TRUE;
1063 }
1064 }
1065 pDelete(&origsig);
1066 }
1067 //pDelete(&f1);
1068 // go on with the computations only if the signature of p2 is greater than the
1069 // signature of fm*p1
1070 if(sigSafe != 1 && !rField_is_Ring(currRing))
1071 {
1072 PR->is_redundant = TRUE;
1073 return 3;
1074 }
1075 //PW->is_sigsafe = TRUE;
1076 }
1077 PR->is_redundant = FALSE;
1078 poly p1 = PR->GetLmTailRing(); // p2 | p1
1079 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
1080 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
1081 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
1082 p_CheckPolyRing(p1, tailRing);
1083 p_CheckPolyRing(p2, tailRing);
1084
1085 pAssume1(p2 != NULL && p1 != NULL &&
1086 p_DivisibleBy(p2, p1, tailRing));
1087
1088 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
1089 (p_GetComp(p2, tailRing) == 0 &&
1090 p_MaxComp(pNext(p2),tailRing) == 0));
1091
1092#ifdef HAVE_PLURAL
1093 if (rIsPluralRing(currRing))
1094 {
1095 // for the time being: we know currRing==strat->tailRing
1096 // no exp-bound checking needed
1097 // (only needed if exp-bound(tailring)<exp-b(currRing))
1098 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
1099 else
1100 {
1101 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
1102 assume(_p != NULL);
1103 nc_PolyPolyRed(_p, p2, coef, currRing);
1104 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
1105 PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
1106 }
1107 return 0;
1108 }
1109#endif
1110
1111 if (t2==NULL) // Divisor is just one term, therefore it will
1112 { // just cancel the leading term
1113 PR->LmDeleteAndIter();
1114 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1115 return 0;
1116 }
1117
1118 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
1119
1120 if (tailRing != currRing)
1121 {
1122 // check that reduction does not violate exp bound
1123 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
1124 {
1125 // undo changes of lm
1126 p_ExpVectorAdd(lm, p2, tailRing);
1127 if (strat == NULL) return 2;
1128 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
1129 tailRing = strat->tailRing;
1130 p1 = PR->GetLmTailRing();
1131 p2 = PW->GetLmTailRing();
1132 t2 = pNext(p2);
1133 lm = p1;
1134 p_ExpVectorSub(lm, p2, tailRing);
1135 ret = 1;
1136 }
1137 }
1138
1139#ifdef HAVE_SHIFTBBA
1140 poly lmRight;
1141 if (tailRing->isLPring)
1142 {
1143 assume(PR->shift == 0);
1144 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
1145 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
1146 }
1147#endif
1148
1149 // take care of coef business
1150 if(rField_is_Ring(currRing))
1151 {
1152 p_SetCoeff(lm, nDiv(pGetCoeff(lm),pGetCoeff(p2)), tailRing);
1153 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1154 }
1155 else
1156 {
1157 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
1158 {
1159 number bn = pGetCoeff(lm);
1160 number an = pGetCoeff(p2);
1161 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
1162 p_SetCoeff(lm, bn, tailRing);
1163 if (((ct == 0) || (ct == 2)))
1164 PR->Tail_Mult_nn(an);
1165 if (coef != NULL) *coef = an;
1166 else n_Delete(&an, tailRing->cf);
1167 }
1168 else
1169 {
1170 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1171 }
1172 }
1173
1174 // and finally,
1175#ifdef HAVE_SHIFTBBA
1176 if (tailRing->isLPring)
1177 {
1178 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
1179 }
1180 else
1181#endif
1182 {
1183 PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
1184 }
1185 assume(PW->GetpLength() == (int)pLength(PW->p != NULL ? PW->p : PW->t_p));
1186 PR->LmDeleteAndIter();
1187
1188#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
1189 if (TEST_OPT_DEBUG)
1190 {
1191 Print(" to: "); PR->wrp(); Print("\n");
1192 }
1193#endif
1194 return ret;
1195}
1196
1197/***************************************************************
1198 *
1199 * Creates S-Poly of p1 and p2
1200 *
1201 *
1202 ***************************************************************/
1203void ksCreateSpoly(LObject* Pair, poly spNoether,
1204 int use_buckets, ring tailRing,
1205 poly m1, poly m2, TObject** R)
1206{
1207#ifdef KDEBUG
1208 create_count++;
1209#endif
1210 poly p1 = Pair->p1;
1211 poly p2 = Pair->p2;
1212 Pair->tailRing = tailRing;
1213
1214 assume(p1 != NULL);
1215 assume(p2 != NULL);
1216 assume(tailRing != NULL);
1217
1218 poly a1 = pNext(p1), a2 = pNext(p2);
1219 number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1220 int co=0/*, ct = ksCheckCoeff(&lc1, &lc2, currRing->cf)*/; // gcd and zero divisors
1221 (void) ksCheckCoeff(&lc1, &lc2, currRing->cf);
1222
1223 int l1=0, l2=0;
1224
1225 if (currRing->pCompIndex >= 0)
1226 {
1227 if (__p_GetComp(p1, currRing)!=__p_GetComp(p2, currRing))
1228 {
1229 if (__p_GetComp(p1, currRing)==0)
1230 {
1231 co=1;
1232 p_SetCompP(p1,__p_GetComp(p2, currRing), currRing, tailRing);
1233 }
1234 else
1235 {
1236 co=2;
1237 p_SetCompP(p2, __p_GetComp(p1, currRing), currRing, tailRing);
1238 }
1239 }
1240 }
1241
1242 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
1243 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
1244 if (m1 == NULL)
1245 k_GetLeadTerms(p1, p2, currRing, m1, m2, tailRing);
1246
1247#ifdef HAVE_SHIFTBBA
1248 poly m12, m22;
1249 if (tailRing->isLPring)
1250 {
1251 assume(p_mFirstVblock(p1, tailRing) <= 1 || p_mFirstVblock(p2, tailRing) <= 1);
1252 k_SplitFrame(m1, m12, si_max(p_mFirstVblock(p1, tailRing), 1), tailRing);
1253 k_SplitFrame(m2, m22, si_max(p_mFirstVblock(p2, tailRing), 1), tailRing);
1254 // coeffs of m1,m2 are NULL here
1255 }
1256#endif
1257
1258 pSetCoeff0(m1, lc2);
1259 pSetCoeff0(m2, lc1); // and now, m1 * LT(p1) == m2 * LT(p2)
1260
1261 if (R != NULL)
1262 {
1263 if (Pair->i_r1 == -1)
1264 {
1265 l1 = pLength(p1) - 1;
1266 }
1267 else
1268 {
1269 l1 = (R[Pair->i_r1])->GetpLength() - 1;
1270 }
1271 if ((Pair->i_r2 == -1)||(R[Pair->i_r2]==NULL))
1272 {
1273 l2 = pLength(p2) - 1;
1274 }
1275 else
1276 {
1277 l2 = (R[Pair->i_r2])->GetpLength() - 1;
1278 }
1279 }
1280
1281 // get m2 * a2
1282#ifdef HAVE_SHIFTBBA
1283 if (tailRing->isLPring)
1284 {
1285 // m2*a2*m22
1286 poly tmp= tailRing->p_Procs->pp_mm_Mult(a2, m2, tailRing);
1287 a2 = tailRing->p_Procs->pp_Mult_mm(tmp, m22, tailRing);
1288 p_Delete(&tmp,tailRing);
1289 }
1290 else
1291#endif
1292 if (spNoether != NULL)
1293 {
1294 l2 = -1;
1295 a2 = tailRing->p_Procs->pp_Mult_mm_Noether(a2, m2, spNoether, l2, tailRing);
1296 assume(l2 == (int)pLength(a2));
1297 }
1298 else
1299 {
1300 a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, tailRing);
1301 }
1302 if (!(rField_is_Domain(currRing))) l2 = pLength(a2);
1303
1304 Pair->SetLmTail(m2, a2, l2, use_buckets, tailRing);
1305
1306#ifdef HAVE_SHIFTBBA
1307 if (tailRing->isLPring)
1308 {
1309 // get m2*a2*m22 - m1*a1*m12
1310 poly tmp=tailRing->p_Procs->pp_Mult_mm(a1, m12, tailRing);
1311 Pair->Tail_Minus_mm_Mult_qq(m1, tmp, l1, spNoether);
1312 p_Delete(&tmp,tailRing);
1313 }
1314 else
1315#endif
1316 {
1317 // get m2*a2 - m1*a1
1318 Pair->Tail_Minus_mm_Mult_qq(m1, a1, l1, spNoether);
1319 }
1320
1321 // Clean-up time
1322 Pair->LmDeleteAndIter();
1323 p_LmDelete(m1, tailRing);
1324#ifdef HAVE_SHIFTBBA
1325 if (tailRing->isLPring)
1326 {
1327 // just to be sure, check that the shift is correct
1328 assume(Pair->shift == 0);
1329 assume(si_max(p_mFirstVblock(Pair->p, tailRing) - 1, 0) == Pair->shift); // == 0
1330
1331 p_LmDelete(m12, tailRing);
1332 p_LmDelete(m22, tailRing);
1333 // m2 is already deleted
1334 }
1335#endif
1336
1337 if (co != 0)
1338 {
1339 if (co==1)
1340 {
1341 p_SetCompP(p1,0, currRing, tailRing);
1342 }
1343 else
1344 {
1345 p_SetCompP(p2,0, currRing, tailRing);
1346 }
1347 }
1348}
1349
1350int ksReducePolyTail(LObject* PR, TObject* PW, poly Current, poly spNoether)
1351{
1352 BOOLEAN ret;
1353 number coef;
1354 poly Lp = PR->GetLmCurrRing();
1355 poly Save = PW->GetLmCurrRing();
1356
1357 pAssume(pIsMonomOf(Lp, Current));
1358
1359 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1360 assume(PR->bucket == NULL);
1361
1362 LObject Red(pNext(Current), PR->tailRing);
1363 TObject With(PW, Lp == Save);
1364
1365 pAssume(!pHaveCommonMonoms(Red.p, With.p));
1366 ret = ksReducePoly(&Red, &With, spNoether, &coef);
1367
1368 if (!ret)
1369 {
1370 if (! n_IsOne(coef, currRing->cf))
1371 {
1372 pNext(Current) = NULL;
1373 if (Current == PR->p && PR->t_p != NULL)
1374 pNext(PR->t_p) = NULL;
1375 PR->Mult_nn(coef);
1376 }
1377
1378 n_Delete(&coef, currRing->cf);
1379 pNext(Current) = Red.GetLmTailRing();
1380 if (Current == PR->p && PR->t_p != NULL)
1381 pNext(PR->t_p) = pNext(Current);
1382 }
1383
1384 if (Lp == Save)
1385 With.Delete();
1386
1387 return ret;
1388}
1389
1390int ksReducePolyTailBound(LObject* PR, TObject* PW, int bound, poly Current, poly spNoether)
1391{
1392 BOOLEAN ret;
1393 number coef;
1394 poly Lp = PR->GetLmCurrRing();
1395 poly Save = PW->GetLmCurrRing();
1396
1397 pAssume(pIsMonomOf(Lp, Current));
1398
1399 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1400 assume(PR->bucket == NULL);
1401
1402 LObject Red(pNext(Current), PR->tailRing);
1403 TObject With(PW, Lp == Save);
1404
1405 pAssume(!pHaveCommonMonoms(Red.p, With.p));
1406 ret = ksReducePolyBound(&Red, &With,bound, spNoether, &coef);
1407
1408 if (!ret)
1409 {
1410 if (! n_IsOne(coef, currRing->cf))
1411 {
1412 pNext(Current) = NULL;
1413 if (Current == PR->p && PR->t_p != NULL)
1414 pNext(PR->t_p) = NULL;
1415 PR->Mult_nn(coef);
1416 }
1417
1418 n_Delete(&coef, currRing->cf);
1419 pNext(Current) = Red.GetLmTailRing();
1420 if (Current == PR->p && PR->t_p != NULL)
1421 pNext(PR->t_p) = pNext(Current);
1422 }
1423
1424 if (Lp == Save)
1425 With.Delete();
1426
1427 return ret;
1428}
1429
1430/***************************************************************
1431 *
1432 * Auxiliary Routines
1433 *
1434 *
1435 ***************************************************************/
1436
1437/*2
1438* creates the leading term of the S-polynomial of p1 and p2
1439* do not destroy p1 and p2
1440* remarks:
1441* 1. the coefficient is 0 (p_Init)
1442* 1. a) in the case of coefficient ring, the coefficient is calculated
1443* 2. pNext is undefined
1444*/
1445//static void bbb() { int i=0; }
1446poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
1447{
1448 poly a1 = pNext(p1), a2 = pNext(p2);
1449#ifdef HAVE_SHIFTBBA
1450 int shift1, shift2;
1451 if (tailRing->isLPring)
1452 {
1453 // assume: LM is shifted, tail unshifted
1454 assume(p_FirstVblock(a1, tailRing) <= 1);
1455 assume(p_FirstVblock(a2, tailRing) <= 1);
1456 // save the shift of the LM so we can shift the other monomials on demand
1457 shift1 = p_mFirstVblock(p1, tailRing) - 1;
1458 shift2 = p_mFirstVblock(p2, tailRing) - 1;
1459 }
1460#endif
1461 long c1=p_GetComp(p1, currRing),c2=p_GetComp(p2, currRing);
1462 long c;
1463 poly m1,m2;
1464 number t1 = NULL,t2 = NULL;
1465 int cm,i;
1466 BOOLEAN equal;
1467
1468 BOOLEAN is_Ring=rField_is_Ring(currRing);
1469 number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1470 if (is_Ring)
1471 {
1472 ksCheckCoeff(&lc1, &lc2, currRing->cf); // gcd and zero divisors
1473 if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
1474 if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
1475 while (a1 != NULL && nIsZero(t2))
1476 {
1477 pIter(a1);
1478 nDelete(&t2);
1479 if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
1480 }
1481 while (a2 != NULL && nIsZero(t1))
1482 {
1483 pIter(a2);
1484 nDelete(&t1);
1485 if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
1486 }
1487 }
1488
1489#ifdef HAVE_SHIFTBBA
1490 // shift the next monomial on demand
1491 if (tailRing->isLPring)
1492 {
1493 a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
1494 a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
1495 }
1496#endif
1497 if (a1==NULL)
1498 {
1499 if(a2!=NULL)
1500 {
1501 m2=p_Init(currRing);
1502x2:
1503 for (i = (currRing->N); i; i--)
1504 {
1505 c = p_GetExpDiff(p1, p2,i, currRing);
1506 if (c>0)
1507 {
1508 p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)),currRing);
1509 }
1510 else
1511 {
1512 p_SetExp(m2,i,p_GetExp(a2,i,tailRing),currRing);
1513 }
1514 }
1515 if ((c1==c2)||(c2!=0))
1516 {
1517 p_SetComp(m2,p_GetComp(a2,tailRing), currRing);
1518 }
1519 else
1520 {
1521 p_SetComp(m2,c1,currRing);
1522 }
1523 p_Setm(m2, currRing);
1524 if (is_Ring)
1525 {
1526 nDelete(&lc1);
1527 nDelete(&lc2);
1528 nDelete(&t2);
1529 pSetCoeff0(m2, t1);
1530 }
1531#ifdef HAVE_SHIFTBBA
1532 if (tailRing->isLPring && (shift2!=0)) /*a1==NULL*/
1533 {
1534 p_LmDelete(a2, tailRing);
1535 }
1536#endif
1537 return m2;
1538 }
1539 else
1540 {
1541 if (is_Ring)
1542 {
1543 nDelete(&lc1);
1544 nDelete(&lc2);
1545 nDelete(&t1);
1546 nDelete(&t2);
1547 }
1548 return NULL;
1549 }
1550 }
1551 if (a2==NULL)
1552 {
1553 m1=p_Init(currRing);
1554x1:
1555 for (i = (currRing->N); i; i--)
1556 {
1557 c = p_GetExpDiff(p2, p1,i,currRing);
1558 if (c>0)
1559 {
1560 p_SetExp(m1,i,(c+p_GetExp(a1,i, tailRing)),currRing);
1561 }
1562 else
1563 {
1564 p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
1565 }
1566 }
1567 if ((c1==c2)||(c1!=0))
1568 {
1569 p_SetComp(m1,p_GetComp(a1,tailRing),currRing);
1570 }
1571 else
1572 {
1573 p_SetComp(m1,c2,currRing);
1574 }
1575 p_Setm(m1, currRing);
1576 if (is_Ring)
1577 {
1578 pSetCoeff0(m1, t2);
1579 nDelete(&lc1);
1580 nDelete(&lc2);
1581 nDelete(&t1);
1582 }
1583#ifdef HAVE_SHIFTBBA
1584 if (tailRing->isLPring && (shift1!=0)) /*a2==NULL*/
1585 {
1586 p_LmDelete(a1, tailRing);
1587 }
1588#endif
1589 return m1;
1590 }
1591 m1 = p_Init(currRing);
1592 m2 = p_Init(currRing);
1593 loop
1594 {
1595 for (i = (currRing->N); i; i--)
1596 {
1597 c = p_GetExpDiff(p1, p2,i,currRing);
1598 if (c > 0)
1599 {
1600 p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)), currRing);
1601 p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
1602 }
1603 else
1604 {
1605 p_SetExp(m1,i,(p_GetExp(a1,i,tailRing)-c), currRing);
1606 p_SetExp(m2,i,p_GetExp(a2,i, tailRing), currRing);
1607 }
1608 }
1609 if(c1==c2)
1610 {
1611 p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
1612 p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
1613 }
1614 else
1615 {
1616 if(c1!=0)
1617 {
1618 p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
1619 p_SetComp(m2,c1, currRing);
1620 }
1621 else
1622 {
1623 p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
1624 p_SetComp(m1,c2, currRing);
1625 }
1626 }
1627 p_Setm(m1,currRing);
1628 p_Setm(m2,currRing);
1629 cm = p_LmCmp(m1, m2,currRing);
1630 if (cm!=0)
1631 {
1632 if(cm==1)
1633 {
1634 p_LmFree(m2,currRing);
1635 if (is_Ring)
1636 {
1637 pSetCoeff0(m1, t2);
1638 nDelete(&lc1);
1639 nDelete(&lc2);
1640 nDelete(&t1);
1641 }
1642#ifdef HAVE_SHIFTBBA
1643 if (tailRing->isLPring)
1644 {
1645 if (shift1!=0) p_LmDelete(a1, tailRing);
1646 if (shift2!=0) p_LmDelete(a2, tailRing);
1647 }
1648#endif
1649 return m1;
1650 }
1651 else
1652 {
1653 p_LmFree(m1,currRing);
1654 if (is_Ring)
1655 {
1656 pSetCoeff0(m2, t1);
1657 nDelete(&lc1);
1658 nDelete(&lc2);
1659 nDelete(&t2);
1660 }
1661#ifdef HAVE_SHIFTBBA
1662 if (tailRing->isLPring)
1663 {
1664 if (shift1!=0) p_LmDelete(a1, tailRing);
1665 if (shift2!=0) p_LmDelete(a2, tailRing);
1666 }
1667#endif
1668 return m2;
1669 }
1670 }
1671 if (is_Ring)
1672 {
1673 equal = nEqual(t1,t2);
1674 }
1675 else
1676 {
1677 t1 = nMult(pGetCoeff(a2),pGetCoeff(p1));
1678 t2 = nMult(pGetCoeff(a1),pGetCoeff(p2));
1679 equal = nEqual(t1,t2);
1680 nDelete(&t2);
1681 nDelete(&t1);
1682 }
1683 if (!equal)
1684 {
1685 p_LmFree(m2,currRing);
1686 if (is_Ring)
1687 {
1688 pSetCoeff0(m1, nSub(t1, t2));
1689 nDelete(&lc1);
1690 nDelete(&lc2);
1691 nDelete(&t1);
1692 nDelete(&t2);
1693 }
1694#ifdef HAVE_SHIFTBBA
1695 if (tailRing->isLPring)
1696 {
1697 if (shift1!=0) p_LmDelete(a1, tailRing);
1698 if (shift2!=0) p_LmDelete(a2, tailRing);
1699 }
1700#endif
1701 return m1;
1702 }
1703 pIter(a1);
1704 pIter(a2);
1705 if (is_Ring)
1706 {
1707 if (a2 != NULL)
1708 {
1709 nDelete(&t1);
1710 t1 = nMult(pGetCoeff(a2),lc1);
1711 }
1712 if (a1 != NULL)
1713 {
1714 nDelete(&t2);
1715 t2 = nMult(pGetCoeff(a1),lc2);
1716 }
1717 while ((a1 != NULL) && nIsZero(t2))
1718 {
1719 pIter(a1);
1720 if (a1 != NULL)
1721 {
1722 nDelete(&t2);
1723 t2 = nMult(pGetCoeff(a1),lc2);
1724 }
1725 }
1726 while ((a2 != NULL) && nIsZero(t1))
1727 {
1728 pIter(a2);
1729 if (a2 != NULL)
1730 {
1731 nDelete(&t1);
1732 t1 = nMult(pGetCoeff(a2),lc1);
1733 }
1734 }
1735 }
1736#ifdef HAVE_SHIFTBBA
1737 if (tailRing->isLPring)
1738 {
1739 a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
1740 a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
1741 }
1742#endif
1743 if (a2==NULL)
1744 {
1745 p_LmFree(m2,currRing);
1746 if (a1==NULL)
1747 {
1748 if (is_Ring)
1749 {
1750 nDelete(&lc1);
1751 nDelete(&lc2);
1752 nDelete(&t1);
1753 nDelete(&t2);
1754 }
1755 p_LmFree(m1,currRing);
1756 return NULL;
1757 }
1758 goto x1;
1759 }
1760 if (a1==NULL)
1761 {
1762 p_LmFree(m1,currRing);
1763 goto x2;
1764 }
1765 }
1766}
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
reduce
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition cf_ops.cc:660
i
int i
Definition cfEzgcd.cc:132
equal
bool equal
Definition cfModGcd.cc:4134
skStrategy::sigdrop
bool sigdrop
Definition kutil.h:357
skStrategy::tailRing
ring tailRing
Definition kutil.h:342
skStrategy::blockred
int blockred
Definition kutil.h:362
Print
#define Print
Definition emacs.cc:80
VAR
#define VAR
Definition globaldefs.h:5
ksReducePolyTail
KINLINE int ksReducePolyTail(LObject *PR, TObject *PW, LObject *Red)
Definition kInline.h:1147
k_GetLeadTerms
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition kInline.h:1018
ksCheckCoeff
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition kbuckets.cc:1504
ksReducePolyLC
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
red_count
VAR int red_count
Definition kspoly.cc:25
ksCreateSpoly
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition kspoly.cc:1203
ksReducePolyTailBound
int ksReducePolyTailBound(LObject *PR, TObject *PW, int bound, poly Current, poly spNoether)
Definition kspoly.cc:1390
ksReducePoly
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition kspoly.cc:187
ksReducePolySig
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:737
ksReducePolyBound
int ksReducePolyBound(LObject *PR, TObject *PW, int, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:590
ksReducePolySigRing
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:943
ksCreateShortSpoly
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition kspoly.cc:1446
create_count
VAR int create_count
Definition kspoly.cc:26
kStratChangeTailRing
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10939
kTest_L
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:916
kTest_T
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:789
ksReducePolyGCD
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
TObject
class sTObject TObject
Definition kutil.h:58
ksReducePolyZ
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
LObject
class sLObject LObject
Definition kutil.h:59
nc_PolyPolyRed
void nc_PolyPolyRed(poly &b, poly p, number *c, const ring r)
Definition old.gring.cc:2238
assume
#define assume(x)
Definition mod2.h:389
p_GetComp
#define p_GetComp(p, r)
Definition monomials.h:64
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
pAssume1
#define pAssume1(cond)
Definition monomials.h:171
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
__p_GetComp
#define __p_GetComp(p, r)
Definition monomials.h:63
pAssume
#define pAssume(cond)
Definition monomials.h:90
nDiv
#define nDiv(a, b)
Definition numbers.h:32
nDelete
#define nDelete(n)
Definition numbers.h:16
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nEqual
#define nEqual(n1, n2)
Definition numbers.h:20
nSub
#define nSub(n1, n2)
Definition numbers.h:22
nMult
#define nMult(n1, n2)
Definition numbers.h:17
NULL
#define NULL
Definition omList.c:12
TEST_OPT_DEBUG
#define TEST_OPT_DEBUG
Definition options.h:110
p_Procs.h
p_polys.h
pIsMonomOf
BOOLEAN pIsMonomOf(poly p, poly m)
Definition pDebug.cc:164
p_CheckPolyRing
BOOLEAN p_CheckPolyRing(poly p, ring r)
Definition pDebug.cc:115
pHaveCommonMonoms
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition pDebug.cc:174
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
polys.h
Compatibility layer for legacy polynomial operations (over currRing).
pLtCmp
#define pLtCmp(p, q)
Definition polys.h:124
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition polys.h:32
pSub
#define pSub(a, b)
Definition polys.h:288
pWrite
void pWrite(poly p)
Definition polys.h:309
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
pOne
#define pOne()
Definition polys.h:316
StringSetS
void StringSetS(const char *st)
Definition reporter.cc:128
StringAppendS
void StringAppendS(const char *st)
Definition reporter.cc:107
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
StringEndS
char * StringEndS()
Definition reporter.cc:151
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491
p_LPCopyAndShiftLM
poly p_LPCopyAndShiftLM(poly p, int sh, const ring r)
Definition shiftgb.cc:35
p_mFirstVblock
int p_mFirstVblock(poly p, const ring ri)
Definition shiftop.cc:478
p_FirstVblock
int p_FirstVblock(poly p, const ring r)
Definition shiftop.cc:456
k_SplitFrame
void k_SplitFrame(poly &m1, poly &m2, int at, const ring r)
Definition shiftop.cc:600
R
#define R
Definition sirandom.c:27
kStrategy
skStrategy * kStrategy
Definition structs.h:54
loop
#define loop
Definition structs.h:71
Generated on for My Project by   doxygen 1.18.0 for Singular