My Project
kstd2.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT - Kernel: alg. of Buchberger
6*/
7
8// #define PDEBUG 2
9
10#include "kernel/mod2.h"
11
12#define GCD_SBA 1
13
14// define if no buckets should be used
15// #define NO_BUCKETS
16
17#ifdef HAVE_PLURAL
18#define PLURAL_INTERNAL_DECLARATIONS 1
19#endif
20
21#define STDZ_EXHANGE_DURING_REDUCTION 0
22
23/***********************************************
24 * SBA stuff -- start
25***********************************************/
26#define DEBUGF50 0
27#define DEBUGF51 0
28
29#ifdef DEBUGF5
30#undef DEBUGF5
31//#define DEBUGF5 1
32#endif
33
34#define F5C 1
35#if F5C
36 #define F5CTAILRED 1
37#endif
38
39#define SBA_INTERRED_START 0
40#define SBA_TAIL_RED 1
41#define SBA_PRODUCT_CRITERION 0
42#define SBA_PRINT_ZERO_REDUCTIONS 0
43#define SBA_PRINT_REDUCTION_STEPS 0
44#define SBA_PRINT_OPERATIONS 0
45#define SBA_PRINT_SIZE_G 0
46#define SBA_PRINT_SIZE_SYZ 0
47#define SBA_PRINT_PRODUCT_CRITERION 0
48
49// counts sba's reduction steps
50#if SBA_PRINT_REDUCTION_STEPS
51VAR long sba_reduction_steps;
52VAR long sba_interreduction_steps;
53#endif
54#if SBA_PRINT_OPERATIONS
55VAR long sba_operations;
56VAR long sba_interreduction_operations;
57#endif
58
59/***********************************************
60 * SBA stuff -- done
61***********************************************/
62
64#include "misc/options.h"
65#include "kernel/polys.h"
66#include "kernel/ideals.h"
69#include "polys/kbuckets.h"
70#include "polys/prCopy.h"
71#include "polys/weight.h"
72#include "misc/intvec.h"
73#ifdef HAVE_PLURAL
74#include "polys/nc/nc.h"
75#endif
76// #include "timer.h"
77
78#ifdef HAVE_SHIFTBBA
79#include "polys/shiftop.h"
80#endif
81
82 VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
83 VAR int (*test_PosInL)(const LSet set, const int length,
84 LObject* L,const kStrategy strat);
85
86int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start)
87{
88 unsigned long not_sev = ~L->sev;
89 int j = start;
90 int o = -1;
91
92 const TSet T=strat->T;
93 const unsigned long* sevT=strat->sevT;
94 number gcd, ogcd;
95 if (L->p!=NULL)
96 {
97 const ring r=currRing;
98 const poly p=L->p;
99 ogcd = pGetCoeff(p);
100
101 pAssume(~not_sev == p_GetShortExpVector(p, r));
102
103 loop
104 {
105 if (j > strat->tl) return o;
106 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
107 {
108 gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
109 if (o == -1
110 || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
111 {
112 ogcd = gcd;
113 o = j;
114 }
115 }
116 j++;
117 }
118 }
119 else
120 {
121 const ring r=strat->tailRing;
122 const poly p=L->t_p;
123 ogcd = pGetCoeff(p);
124 loop
125 {
126 if (j > strat->tl) return o;
127 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
128 {
129 gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
130 if (o == -1
131 || n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
132 {
133 ogcd = gcd;
134 o = j;
135 }
136 }
137 j++;
138 }
139 }
140}
141// return -1 if T[0] does not divide the leading monomial
142int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L)
143{
144 if (strat->tl < 1)
145 return -1;
146
147 unsigned long not_sev = ~L->sev;
148 const unsigned long sevT0 = strat->sevT[0];
149 number rest, orest, mult;
150 if (L->p!=NULL)
151 {
152 const poly T0p = strat->T[0].p;
153 const ring r = currRing;
154 const poly p = L->p;
155 orest = pGetCoeff(p);
156
157 pAssume(~not_sev == p_GetShortExpVector(p, r));
158
159#if defined(PDEBUG) || defined(PDIV_DEBUG)
160 if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
161 {
162 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
163 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
164 {
165 return 0;
166 }
167 }
168#else
169 if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
170 {
171 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
172 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
173 {
174 return 0;
175 }
176 }
177#endif
178 }
179 else
180 {
181 const poly T0p = strat->T[0].t_p;
182 const ring r = strat->tailRing;
183 const poly p = L->t_p;
184 orest = pGetCoeff(p);
185#if defined(PDEBUG) || defined(PDIV_DEBUG)
186 if (p_LmShortDivisibleBy(T0p, sevT0,
187 p, not_sev, r))
188 {
189 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
190 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
191 {
192 return 0;
193 }
194 }
195#else
196 if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
197 {
198 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
199 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
200 {
201 return 0;
202 }
203 }
204#endif
205 }
206 return -1;
207}
208
209int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start)
210{
211 unsigned long not_sev = ~L->sev;
212 int j = start;
213 int o = -1;
214
215 const TSet T=strat->T;
216 const unsigned long* sevT=strat->sevT;
217 number rest, orest, mult;
218 if (L->p!=NULL)
219 {
220 const ring r=currRing;
221 const poly p=L->p;
222 orest = pGetCoeff(p);
223
224 pAssume(~not_sev == p_GetShortExpVector(p, r));
225
226 loop
227 {
228 if (j > strat->tl) return o;
229#if defined(PDEBUG) || defined(PDIV_DEBUG)
230 if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
231 {
232 mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
233 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
234 {
235 o = j;
236 orest = rest;
237 }
238 }
239#else
240 if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
241 {
242 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
243 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
244 {
245 o = j;
246 orest = rest;
247 }
248 }
249#endif
250 j++;
251 }
252 }
253 else
254 {
255 const ring r=strat->tailRing;
256 const poly p=L->t_p;
257 orest = pGetCoeff(p);
258 loop
259 {
260 if (j > strat->tl) return o;
261#if defined(PDEBUG) || defined(PDIV_DEBUG)
262 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
263 p, not_sev, r))
264 {
265 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
266 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
267 {
268 o = j;
269 orest = rest;
270 }
271 }
272#else
273 if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
274 {
275 mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
276 if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
277 {
278 o = j;
279 orest = rest;
280 }
281 }
282#endif
283 j++;
284 }
285 }
286}
287
288// return -1 if no divisor is found
289// number of first divisor, otherwise
290int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
291{
292 unsigned long not_sev = ~L->sev;
293 int j = start;
294
295 const TSet T=strat->T;
296 const unsigned long* sevT=strat->sevT;
297 const ring r=currRing;
298 const BOOLEAN is_Ring=rField_is_Ring(r);
299 if (L->p!=NULL)
300 {
301 const poly p=L->p;
302
303 pAssume(~not_sev == p_GetShortExpVector(p, r));
304
305 if(is_Ring)
306 {
307 loop
308 {
309 if (j > strat->tl) return -1;
310#if defined(PDEBUG) || defined(PDIV_DEBUG)
311 if ((T[j].p!=NULL)
312 && p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
313 {
314 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
315 return j;
316 }
317#else
318 if (!(sevT[j] & not_sev)
319 && (T[j].p!=NULL)
320 && p_LmDivisibleBy(T[j].p, p, r))
321 {
322 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
323 return j;
324 }
325#endif
326 j++;
327 }
328 }
329 else
330 {
331 loop
332 {
333 if (j > strat->tl) return -1;
334#if defined(PDEBUG) || defined(PDIV_DEBUG)
335 if ((T[j].p!=NULL)
336 && p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
337 {
338 return j;
339 }
340#else
341 if (!(sevT[j] & not_sev)
342 && (T[j].p!=NULL)
343 && p_LmDivisibleBy(T[j].p, p, r))
344 {
345 return j;
346 }
347#endif
348 j++;
349 }
350 }
351 }
352 else
353 {
354 const poly p=L->t_p;
355 const ring r=strat->tailRing;
356 if(is_Ring)
357 {
358 loop
359 {
360 if (j > strat->tl) return -1;
361#if defined(PDEBUG) || defined(PDIV_DEBUG)
362 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
363 p, not_sev, r))
364 {
365 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
366 return j;
367 }
368#else
369 if (!(sevT[j] & not_sev) &&
370 p_LmDivisibleBy(T[j].t_p, p, r))
371 {
372 if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
373 return j;
374 }
375#endif
376 j++;
377 }
378 }
379 else
380 {
381 loop
382 {
383 if (j > strat->tl) return -1;
384#if defined(PDEBUG) || defined(PDIV_DEBUG)
385 if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
386 p, not_sev, r))
387 {
388 return j;
389 }
390#else
391 if (!(sevT[j] & not_sev) &&
392 p_LmDivisibleBy(T[j].t_p, p, r))
393 {
394 return j;
395 }
396#endif
397 j++;
398 }
399 }
400 }
401}
402
403// same as above, only with set S
404int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
405{
406 unsigned long not_sev = ~L->sev;
407 poly p = L->GetLmCurrRing();
408 int j = 0;
409
410 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
411
413#if 1
414 int ende;
415 if (is_Ring
416 || (strat->ak>0)
417 || currRing->pLexOrder)
418 ende=strat->sl;
419 else
420 {
421 ende=posInS(strat,*max_ind,p,0)+1;
422 if (ende>(*max_ind)) ende=(*max_ind);
423 }
424#else
425 int ende=strat->sl;
426#endif
427 if(is_Ring)
428 {
429 loop
430 {
431 if (j > ende) return -1;
432#if defined(PDEBUG) || defined(PDIV_DEBUG)
433 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
434 p, not_sev, currRing))
435 {
436 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
437 return j;
438 }
439#else
440 if ( !(strat->sevS[j] & not_sev) &&
441 p_LmDivisibleBy(strat->S[j], p, currRing))
442 {
443 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
444 return j;
445 }
446#endif
447 j++;
448 }
449 }
450 else
451 {
452 loop
453 {
454 if (j > ende) return -1;
455#if defined(PDEBUG) || defined(PDIV_DEBUG)
456 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
457 p, not_sev, currRing))
458 {
459 return j;
460 }
461#else
462 if ( !(strat->sevS[j] & not_sev) &&
463 p_LmDivisibleBy(strat->S[j], p, currRing))
464 {
465 return j;
466 }
467#endif
468 j++;
469 }
470 }
471}
472
473int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
474{
475 unsigned long not_sev = ~L->sev;
476 poly p = L->GetLmCurrRing();
477 int j = start;
478
479 pAssume(~not_sev == p_GetShortExpVector(p, currRing));
480#if 1
481 int ende=max_ind;
482#else
483 int ende=strat->sl;
484#endif
486 {
487 loop
488 {
489 if (j > ende) return -1;
490#if defined(PDEBUG) || defined(PDIV_DEBUG)
491 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
492 p, not_sev, currRing))
493 {
494 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
495 return j;
496 }
497#else
498 if ( !(strat->sevS[j] & not_sev) &&
499 p_LmDivisibleBy(strat->S[j], p, currRing))
500 {
501 if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
502 return j;
503 }
504#endif
505 j++;
506 }
507 }
508 else
509 {
510 loop
511 {
512 if (j > ende) return -1;
513#if defined(PDEBUG) || defined(PDIV_DEBUG)
514 if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
515 p, not_sev, currRing))
516 {
517 return j;
518 }
519#else
520 if ( !(strat->sevS[j] & not_sev) &&
521 p_LmDivisibleBy(strat->S[j], p, currRing))
522 {
523 return j;
524 }
525#endif
526 j++;
527 }
528 }
529}
530
531#ifdef HAVE_RINGS
532static long ind2(long arg)
533{
534 if (arg <= 0) return 0;
535 long ind = 0;
536 while (arg%2 == 0)
537 {
538 arg = arg / 2;
539 ind++;
540 }
541 return ind;
542}
543
544static long ind_fact_2(long arg)
545{
546 if (arg <= 0) return 0;
547 long ind = 0;
548 if (arg%2 == 1) { arg--; }
549 while (arg > 0)
550 {
551 ind += ind2(arg);
552 arg = arg - 2;
553 }
554 return ind;
555}
556#endif
557
558#ifdef HAVE_RINGS
559poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
560{
561 // m = currRing->ch
562
563 if (input_p == NULL) return NULL;
564
565 poly p = input_p;
566 poly zeroPoly = NULL;
567 unsigned long a = (unsigned long) pGetCoeff(p);
568
569 int k_ind2 = 0;
570 int a_ind2 = ind2(a);
571
572 // unsigned long k = 1;
573 // of interest is only k_ind2, special routine for improvement ... TODO OLIVER
574 for (int i = 1; i <= leadRing->N; i++)
575 {
576 k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
577 }
578
579 a = (unsigned long) pGetCoeff(p);
580
581 number tmp1;
582 poly tmp2, tmp3;
583 poly lead_mult = p_ISet(1, tailRing);
584 if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
585 {
586 int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
587 int s_exp;
588 zeroPoly = p_ISet(a, tailRing);
589 for (int i = 1; i <= leadRing->N; i++)
590 {
591 s_exp = p_GetExp(p, i,leadRing);
592 if (s_exp % 2 != 0)
593 {
594 s_exp = s_exp - 1;
595 }
596 while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
597 {
598 too_much = too_much - ind2(s_exp);
599 s_exp = s_exp - 2;
600 }
601 p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
602 for (int j = 1; j <= s_exp; j++)
603 {
604 tmp1 = nInit(j);
605 tmp2 = p_ISet(1, tailRing);
606 p_SetExp(tmp2, i, 1, tailRing);
607 p_Setm(tmp2, tailRing);
608 if (nIsZero(tmp1))
609 { // should nowbe obsolet, test ! TODO OLIVER
610 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
611 }
612 else
613 {
614 tmp3 = p_NSet(nCopy(tmp1), tailRing);
615 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
616 }
617 }
618 }
619 p_Setm(lead_mult, tailRing);
620 zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
621 tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
622 for (int i = 1; i <= leadRing->N; i++)
623 {
624 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
625 }
626 p_Setm(tmp2, leadRing);
627 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
628 pNext(tmp2) = zeroPoly;
629 return tmp2;
630 }
631/* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
632 if (1 == 0 && alpha_k <= a)
633 { // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
634 zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
635 for (int i = 1; i <= leadRing->N; i++)
636 {
637 for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
638 {
639 tmp1 = nInit(j);
640 tmp2 = p_ISet(1, tailRing);
641 p_SetExp(tmp2, i, 1, tailRing);
642 p_Setm(tmp2, tailRing);
643 if (nIsZero(tmp1))
644 {
645 zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
646 }
647 else
648 {
649 tmp3 = p_ISet((unsigned long) tmp1, tailRing);
650 zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
651 }
652 }
653 }
654 tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
655 for (int i = 1; i <= leadRing->N; i++)
656 {
657 pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
658 }
659 p_Setm(tmp2, leadRing);
660 zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
661 pNext(tmp2) = zeroPoly;
662 return tmp2;
663 } */
664 return NULL;
665}
666#endif
667
668
669#ifdef HAVE_RINGS
670/*2
671* reduction procedure for the ring Z/2^m
672*/
674{
675 if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
676 if (strat->tl<0) return 1;
677
678 int at;
679 long d;
680 int j = 0;
681 int pass = 0;
682
683// TODO warum SetpFDeg notwendig?
684 h->SetpFDeg();
685 assume(h->pFDeg() == h->FDeg);
686 long reddeg = h->GetpFDeg();
687
688 h->SetShortExpVector();
689 loop
690 {
691 /* check if a reducer of the lead term exists */
692 j = kFindDivisibleByInT(strat, h);
693 if (j < 0)
694 {
695#if STDZ_EXCHANGE_DURING_REDUCTION
696 /* check if a reducer with the same lead monomial exists */
697 j = kFindSameLMInT_Z(strat, h);
698 if (j < 0)
699 {
700#endif
701 /* check if a reducer of the lead monomial exists, by the above
702 * check this is a real divisor of the lead monomial */
703 j = kFindDivisibleByInT_Z(strat, h);
704 if (j < 0)
705 {
706 // over ZZ: cleanup coefficients by complete reduction with monomials
708 postReduceByMon(h, strat);
709 if(h->p == NULL)
710 {
711 if (h->lcm!=NULL) pLmDelete(h->lcm);
712 h->Clear();
713 return 0;
714 }
715 if(nIsZero(pGetCoeff(h->p))) return 2;
716 j = kFindDivisibleByInT(strat, h);
717 if(j < 0)
718 {
719 if(strat->tl >= 0)
720 h->i_r1 = strat->tl;
721 else
722 h->i_r1 = -1;
723 if (h->GetLmTailRing() == NULL)
724 {
725 if (h->lcm!=NULL) pLmDelete(h->lcm);
726 h->Clear();
727 return 0;
728 }
729 return 1;
730 }
731 }
732 else
733 {
734 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
735 * => we try to cut down the lead coefficient at least */
736 /* first copy T[j] in order to multiply it with a coefficient later on */
737 number mult, rest;
738 TObject tj = strat->T[j];
739 tj.Copy();
740 /* tj.max_exp = strat->T[j].max_exp; */
741 /* compute division with remainder of lc(h) and lc(T[j]) */
742 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
743 &rest, currRing->cf);
744 /* set corresponding new lead coefficient already. we do not
745 * remove the lead term in ksReducePolyLC, but only apply
746 * a lead coefficient reduction */
747 tj.Mult_nn(mult);
748 ksReducePolyLC(h, &tj, NULL, &rest, strat);
749 tj.Delete();
750 tj.Clear();
751 }
752#if STDZ_EXCHANGE_DURING_REDUCTION
753 }
754 else
755 {
756 /* same lead monomial but lead coefficients do not divide each other:
757 * change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
758 LObject h2 = *h;
759 h2.Copy();
760
761 ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
762 ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
764 {
765 redtailBbaAlsoLC_Z(&h2, j, strat);
766 }
767 /* replace h2 for tj in L (already generated pairs with tj), S and T */
768 replaceInLAndSAndT(h2, j, strat);
769 }
770#endif
771 }
772 else
773 {
774 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat);
775 }
776 /* printf("\nAfter small red: ");pWrite(h->p); */
777 if (h->GetLmTailRing() == NULL)
778 {
779 if (h->lcm!=NULL) pLmDelete(h->lcm);
780#ifdef KDEBUG
781 h->lcm=NULL;
782#endif
783 h->Clear();
784 return 0;
785 }
786 h->SetShortExpVector();
787 d = h->SetpFDeg();
788 /*- try to reduce the s-polynomial -*/
789 pass++;
790 if (!TEST_OPT_REDTHROUGH &&
791 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
792 {
793 h->SetLmCurrRing();
794 if (strat->posInLDependsOnLength)
795 h->SetLength(strat->length_pLength);
796 at = strat->posInL(strat->L,strat->Ll,h,strat);
797 if (at <= strat->Ll)
798 {
799#ifdef KDEBUG
800 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
801#endif
802 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
803 h->Clear();
804 return -1;
805 }
806 }
807 if (d != reddeg)
808 {
809 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
810 {
811 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
812 {
813 strat->overflow=TRUE;
814 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
815 h->GetP();
816 at = strat->posInL(strat->L,strat->Ll,h,strat);
817 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
818 h->Clear();
819 return -1;
820 }
821 }
822 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
823 {
824 Print(".%ld",d);mflush();
825 reddeg = d;
826 }
827 }
828 }
829}
830
832{
833 if (strat->tl<0) return 1;
834 if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
835
836 int at/*,i*/;
837 long d;
838 int j = 0;
839 int pass = 0;
840 // poly zeroPoly = NULL;
841
842// TODO warum SetpFDeg notwendig?
843 h->SetpFDeg();
844 assume(h->pFDeg() == h->FDeg);
845 long reddeg = h->GetpFDeg();
846
847 h->SetShortExpVector();
848 loop
849 {
850 j = kFindDivisibleByInT(strat, h);
851 if (j < 0)
852 {
853 // over ZZ: cleanup coefficients by complete reduction with monomials
854 postReduceByMon(h, strat);
855 if(h->p == NULL)
856 {
857 kDeleteLcm(h);
858 h->Clear();
859 return 0;
860 }
861 if(nIsZero(pGetCoeff(h->p))) return 2;
862 j = kFindDivisibleByInT(strat, h);
863 if(j < 0)
864 {
865 if(strat->tl >= 0)
866 h->i_r1 = strat->tl;
867 else
868 h->i_r1 = -1;
869 if (h->GetLmTailRing() == NULL)
870 {
871 kDeleteLcm(h);
872 h->Clear();
873 return 0;
874 }
875 return 1;
876 }
877 }
878 //printf("\nFound one: ");pWrite(strat->T[j].p);
879 //enterT(*h, strat);
880 ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
881 //printf("\nAfter small red: ");pWrite(h->p);
882 if (h->GetLmTailRing() == NULL)
883 {
884 kDeleteLcm(h);
885 h->Clear();
886 return 0;
887 }
888 h->SetShortExpVector();
889 d = h->SetpFDeg();
890 /*- try to reduce the s-polynomial -*/
891 pass++;
892 if (!TEST_OPT_REDTHROUGH &&
893 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
894 {
895 h->SetLmCurrRing();
896 if (strat->posInLDependsOnLength)
897 h->SetLength(strat->length_pLength);
898 at = strat->posInL(strat->L,strat->Ll,h,strat);
899 if (at <= strat->Ll)
900 {
901#ifdef KDEBUG
902 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
903#endif
904 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
905 h->Clear();
906 return -1;
907 }
908 }
909 if (d != reddeg)
910 {
911 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
912 {
913 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
914 {
915 strat->overflow=TRUE;
916 //Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
917 h->GetP();
918 at = strat->posInL(strat->L,strat->Ll,h,strat);
919 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
920 h->Clear();
921 return -1;
922 }
923 }
924 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
925 {
926 Print(".%ld",d);mflush();
927 reddeg = d;
928 }
929 }
930 }
931}
932#endif
933
934/*2
935* reduction procedure for the homogeneous case
936* and the case of a degree-ordering
937*/
939{
940 if (strat->tl<0) return 1;
941 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
942 assume(h->FDeg == h->pFDeg());
943
944 poly h_p;
945 int i,j,at,pass,cnt,ii;
946 // long reddeg,d;
947 int li;
948 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
949
950 pass = j = 0;
951 cnt = RED_CANONICALIZE;
952 // d = reddeg = h->GetpFDeg();
953 h->SetShortExpVector();
954 h_p = h->GetLmTailRing();
955 h->PrepareRed(strat->use_buckets);
956 loop
957 {
958 j = kFindDivisibleByInT(strat, h);
959 if (j < 0) return 1;
960
961 li = strat->T[j].pLength;
962 ii = j;
963 /*
964 * the polynomial to reduce with (up to the moment) is;
965 * pi with length li
966 */
967 i = j;
968#if 1
969 if (test_opt_length)
970 {
971 if (li<=0) li=strat->T[j].GetpLength();
972 if (li>2)
973 {
974 unsigned long not_sev = ~ h->sev;
975 loop
976 {
977 /*- search the shortest possible with respect to length -*/
978 i++;
979 if (i > strat->tl)
980 break;
981 if ((strat->T[i].pLength < li)
982 &&
983 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
984 h_p, not_sev, strat->tailRing))
985 {
986 /*
987 * the polynomial to reduce with is now;
988 */
989 li = strat->T[i].pLength;
990 if (li<=0) li=strat->T[i].GetpLength();
991 ii = i;
992 if (li<3) break;
993 }
994 }
995 }
996 }
997#endif
998
999 /*
1000 * end of search: have to reduce with pi
1001 */
1002#ifdef KDEBUG
1003 if (TEST_OPT_DEBUG)
1004 {
1005 PrintS("red:");
1006 h->wrp();
1007 PrintS(" with ");
1008 strat->T[ii].wrp();
1009 }
1010#endif
1011 assume(strat->fromT == FALSE);
1012
1013 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1014#if SBA_PRINT_REDUCTION_STEPS
1015 sba_interreduction_steps++;
1016#endif
1017#if SBA_PRINT_OPERATIONS
1018 sba_interreduction_operations += pLength(strat->T[ii].p);
1019#endif
1020
1021#ifdef KDEBUG
1022 if (TEST_OPT_DEBUG)
1023 {
1024 PrintS("\nto ");
1025 h->wrp();
1026 PrintLn();
1027 }
1028#endif
1029
1030 h_p = h->GetLmTailRing();
1031 if (h_p == NULL)
1032 {
1033 kDeleteLcm(h);
1034 return 0;
1035 }
1036 #if 0 // red is redLiftstd if OPT_IDLIFT
1038 {
1039 if (h->p!=NULL)
1040 {
1041 if(p_GetComp(h->p,currRing)>strat->syzComp)
1042 {
1043 h->Delete();
1044 return 0;
1045 }
1046 }
1047 else if (h->t_p!=NULL)
1048 {
1049 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1050 {
1051 h->Delete();
1052 return 0;
1053 }
1054 }
1055 }
1056 #endif
1057 #if 0
1058 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1059 {
1060 if (h->p!=NULL)
1061 {
1062 if(p_GetComp(h->p,currRing)>strat->syzComp)
1063 {
1064 return 1;
1065 }
1066 }
1067 else if (h->t_p!=NULL)
1068 {
1069 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1070 {
1071 return 1;
1072 }
1073 }
1074 }
1075 #endif
1076 h->SetShortExpVector();
1077 /*
1078 * try to reduce the s-polynomial h
1079 *test first whether h should go to the lazyset L
1080 *-if the degree jumps
1081 *-if the number of pre-defined reductions jumps
1082 */
1083 cnt--;
1084 pass++;
1085 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1086 {
1087 h->SetLmCurrRing();
1088 at = strat->posInL(strat->L,strat->Ll,h,strat);
1089 if (at <= strat->Ll)
1090 {
1091#ifdef HAVE_SHIFTBBA
1092 if (rIsLPRing(currRing))
1093 {
1094 if (kFindDivisibleByInT(strat, h) < 0)
1095 return 1;
1096 }
1097 else
1098#endif
1099 {
1100 int dummy=strat->sl;
1101 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1102 return 1;
1103 }
1104 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1105#ifdef KDEBUG
1106 if (TEST_OPT_DEBUG)
1107 Print(" lazy: -> L%d\n",at);
1108#endif
1109 h->Clear();
1110 return -1;
1111 }
1112 }
1113 else if (UNLIKELY(cnt==0))
1114 {
1115 h->CanonicalizeP();
1116 cnt=RED_CANONICALIZE;
1117 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1118 }
1119 }
1120}
1121
1123{
1124 BOOLEAN ret;
1125 number coef;
1126 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1128 Red->HeadNormalize();
1129 /*
1130 printf("------------------------\n");
1131 pWrite(Red->GetLmCurrRing());
1132 */
1134 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1135 else
1136 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1137 if (!ret)
1138 {
1139 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1140 {
1141 PR->Mult_nn(coef);
1142 // HANNES: mark for Normalize
1143 }
1144 n_Delete(&coef, currRing->cf);
1145 }
1146 return ret;
1147}
1148
1149/*2
1150* reduction procedure for signature-based standard
1151* basis algorithms:
1152* all reductions have to be sig-safe!
1153*
1154* 2 is returned if and only if the pair is rejected by the rewritten criterion
1155* at exactly this point of the computations. This is the last possible point
1156* such a check can be done => checks with the biggest set of available
1157* signatures
1158*/
1159
1161{
1162 if (strat->tl<0) return 1;
1163 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1164 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1165 assume(h->FDeg == h->pFDeg());
1166//#if 1
1167#ifdef DEBUGF5
1168 PrintS("------- IN REDSIG -------\n");
1169 Print("p: ");
1170 pWrite(pHead(h->p));
1171 PrintS("p1: ");
1172 pWrite(pHead(h->p1));
1173 PrintS("p2: ");
1174 pWrite(pHead(h->p2));
1175 PrintS("---------------------------\n");
1176#endif
1177 poly h_p;
1178 int i,j,at,pass, ii;
1179 int start=0;
1180 int sigSafe;
1181 unsigned long not_sev;
1182 // long reddeg,d;
1183 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1184 int li;
1185
1186 pass = j = 0;
1187 // d = reddeg = h->GetpFDeg();
1188 h->SetShortExpVector();
1189 h_p = h->GetLmTailRing();
1190 not_sev = ~ h->sev;
1191 loop
1192 {
1193 j = kFindDivisibleByInT(strat, h, start);
1194 if (j < 0)
1195 {
1196 return 1;
1197 }
1198
1199 li = strat->T[j].pLength;
1200 if (li<=0) li=strat->T[j].GetpLength();
1201 ii = j;
1202 /*
1203 * the polynomial to reduce with (up to the moment) is;
1204 * pi with length li
1205 */
1206 i = j;
1207#if 1
1208 if (test_opt_length)
1209 loop
1210 {
1211 /*- search the shortest possible with respect to length -*/
1212 i++;
1213 if (i > strat->tl)
1214 break;
1215 if (li==1)
1216 break;
1217 if ((strat->T[i].pLength < li)
1218 &&
1219 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1220 h_p, not_sev, strat->tailRing))
1221 {
1222 /*
1223 * the polynomial to reduce with is now;
1224 */
1225 li = strat->T[i].pLength;
1226 if (li<=0) li=strat->T[i].GetpLength();
1227 ii = i;
1228 }
1229 }
1230 start = ii+1;
1231#endif
1232
1233 /*
1234 * end of search: have to reduce with pi
1235 */
1236#ifdef KDEBUG
1237 if (TEST_OPT_DEBUG)
1238 {
1239 PrintS("red:");
1240 h->wrp();
1241 PrintS(" with ");
1242 strat->T[ii].wrp();
1243 }
1244#endif
1245 assume(strat->fromT == FALSE);
1246//#if 1
1247#ifdef DEBUGF5
1248 Print("BEFORE REDUCTION WITH %d:\n",ii);
1249 PrintS("--------------------------------\n");
1250 pWrite(h->sig);
1251 pWrite(strat->T[ii].sig);
1252 pWrite(h->GetLmCurrRing());
1253 pWrite(pHead(h->p1));
1254 pWrite(pHead(h->p2));
1255 pWrite(pHead(strat->T[ii].p));
1256 PrintS("--------------------------------\n");
1257 printf("INDEX OF REDUCER T: %d\n",ii);
1258#endif
1259 sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1260#if SBA_PRINT_REDUCTION_STEPS
1261 if (sigSafe != 3)
1262 sba_reduction_steps++;
1263#endif
1264#if SBA_PRINT_OPERATIONS
1265 if (sigSafe != 3)
1266 sba_operations += pLength(strat->T[ii].p);
1267#endif
1268 // if reduction has taken place, i.e. the reduction was sig-safe
1269 // otherwise start is already at the next position and the loop
1270 // searching reducers in T goes on from index start
1271//#if 1
1272#ifdef DEBUGF5
1273 Print("SigSAFE: %d\n",sigSafe);
1274#endif
1275 if (sigSafe != 3)
1276 {
1277 // start the next search for reducers in T from the beginning
1278 start = 0;
1279#ifdef KDEBUG
1280 if (TEST_OPT_DEBUG)
1281 {
1282 PrintS("\nto ");
1283 h->wrp();
1284 PrintLn();
1285 }
1286#endif
1287
1288 h_p = h->GetLmTailRing();
1289 if (h_p == NULL)
1290 {
1291 kDeleteLcm(h);
1292 return 0;
1293 }
1294 h->SetShortExpVector();
1295 not_sev = ~ h->sev;
1296 /*
1297 * try to reduce the s-polynomial h
1298 *test first whether h should go to the lazyset L
1299 *-if the degree jumps
1300 *-if the number of pre-defined reductions jumps
1301 */
1302 pass++;
1303 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1304 {
1305 h->SetLmCurrRing();
1306 at = strat->posInL(strat->L,strat->Ll,h,strat);
1307 if (at <= strat->Ll)
1308 {
1309 int dummy=strat->sl;
1310 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1311 {
1312 return 1;
1313 }
1314 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1315#ifdef KDEBUG
1316 if (TEST_OPT_DEBUG)
1317 Print(" lazy: -> L%d\n",at);
1318#endif
1319 h->Clear();
1320 return -1;
1321 }
1322 }
1323 }
1324 }
1325}
1326
1327
1329{
1330 //Since reduce is really bad for SBA we use the following idea:
1331 // We first check if we can build a gcd pair between h and S
1332 //where the sig remains the same and replace h by this gcd poly
1334 #if GCD_SBA
1335 while(sbaCheckGcdPair(h,strat))
1336 {
1337 h->sev = pGetShortExpVector(h->p);
1338 }
1339 #endif
1340 poly beforeredsig;
1341 beforeredsig = pCopy(h->sig);
1342
1343 if (strat->tl<0) return 1;
1344 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1345 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1346 assume(h->FDeg == h->pFDeg());
1347//#if 1
1348#ifdef DEBUGF5
1349 Print("------- IN REDSIG -------\n");
1350 Print("p: ");
1351 pWrite(pHead(h->p));
1352 Print("p1: ");
1353 pWrite(pHead(h->p1));
1354 Print("p2: ");
1355 pWrite(pHead(h->p2));
1356 Print("---------------------------\n");
1357#endif
1358 poly h_p;
1359 int i,j,at,pass, ii;
1360 int start=0;
1361 int sigSafe;
1362 unsigned long not_sev;
1363 // long reddeg,d;
1364 int li;
1365 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1366
1367 pass = j = 0;
1368 // d = reddeg = h->GetpFDeg();
1369 h->SetShortExpVector();
1370 h_p = h->GetLmTailRing();
1371 not_sev = ~ h->sev;
1372 loop
1373 {
1374 j = kFindDivisibleByInT(strat, h, start);
1375 if (j < 0)
1376 {
1377 #if GCD_SBA
1378 while(sbaCheckGcdPair(h,strat))
1379 {
1380 h->sev = pGetShortExpVector(h->p);
1381 h->is_redundant = FALSE;
1382 start = 0;
1383 }
1384 #endif
1385 // over ZZ: cleanup coefficients by complete reduction with monomials
1386 postReduceByMonSig(h, strat);
1387 if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
1388 j = kFindDivisibleByInT(strat, h,start);
1389 if(j < 0)
1390 {
1391 if(strat->tl >= 0)
1392 h->i_r1 = strat->tl;
1393 else
1394 h->i_r1 = -1;
1395 if (h->GetLmTailRing() == NULL)
1396 {
1397 kDeleteLcm(h);
1398 h->Clear();
1399 return 0;
1400 }
1401 //Check for sigdrop after reduction
1402 if(pLtCmp(beforeredsig,h->sig) == 1)
1403 {
1404 strat->sigdrop = TRUE;
1405 //Reduce it as much as you can
1406 int red_result = redRing(h,strat);
1407 if(red_result == 0)
1408 {
1409 //It reduced to 0, cancel the sigdrop
1410 strat->sigdrop = FALSE;
1411 p_Delete(&h->sig,currRing);h->sig = NULL;
1412 return 0;
1413 }
1414 else
1415 {
1416 //strat->enterS(*h, strat->sl+1, strat, strat->tl);
1417 return 0;
1418 }
1419 }
1420 p_Delete(&beforeredsig,currRing);
1421 return 1;
1422 }
1423 }
1424
1425 li = strat->T[j].pLength;
1426 if (li<=0) li=strat->T[j].GetpLength();
1427 ii = j;
1428 /*
1429 * the polynomial to reduce with (up to the moment) is;
1430 * pi with length li
1431 */
1432 i = j;
1433 if (test_opt_length)
1434 loop
1435 {
1436 /*- search the shortest possible with respect to length -*/
1437 i++;
1438 if (i > strat->tl)
1439 break;
1440 if (li==1)
1441 break;
1442 if ((strat->T[i].pLength < li)
1443 && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1444 && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1445 h_p, not_sev, strat->tailRing))
1446 {
1447 /*
1448 * the polynomial to reduce with is now;
1449 */
1450 li = strat->T[i].pLength;
1451 if (li<=0) li=strat->T[i].GetpLength();
1452 ii = i;
1453 }
1454 }
1455
1456 start = ii+1;
1457
1458 /*
1459 * end of search: have to reduce with pi
1460 */
1461#ifdef KDEBUG
1462 if (TEST_OPT_DEBUG)
1463 {
1464 PrintS("red:");
1465 h->wrp();
1466 PrintS(" with ");
1467 strat->T[ii].wrp();
1468 }
1469#endif
1470 assume(strat->fromT == FALSE);
1471//#if 1
1472#ifdef DEBUGF5
1473 Print("BEFORE REDUCTION WITH %d:\n",ii);
1474 Print("--------------------------------\n");
1475 pWrite(h->sig);
1476 pWrite(strat->T[ii].sig);
1477 pWrite(h->GetLmCurrRing());
1478 pWrite(pHead(h->p1));
1479 pWrite(pHead(h->p2));
1480 pWrite(pHead(strat->T[ii].p));
1481 Print("--------------------------------\n");
1482 printf("INDEX OF REDUCER T: %d\n",ii);
1483#endif
1484 sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1485 if(h->p == NULL && h->sig == NULL)
1486 {
1487 //Trivial case catch
1488 strat->sigdrop = FALSE;
1489 }
1490 #if 0
1491 //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1492 //In some cases this proves to be very bad
1493 if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1494 {
1495 int red_result = redRing(h,strat);
1496 if(red_result == 0)
1497 {
1498 pDelete(&h->sig);h->sig = NULL;
1499 return 0;
1500 }
1501 else
1502 {
1503 strat->sigdrop = TRUE;
1504 return 1;
1505 }
1506 }
1507 #endif
1508 if(strat->sigdrop)
1509 return 1;
1510#if SBA_PRINT_REDUCTION_STEPS
1511 if (sigSafe != 3)
1512 sba_reduction_steps++;
1513#endif
1514#if SBA_PRINT_OPERATIONS
1515 if (sigSafe != 3)
1516 sba_operations += pLength(strat->T[ii].p);
1517#endif
1518 // if reduction has taken place, i.e. the reduction was sig-safe
1519 // otherwise start is already at the next position and the loop
1520 // searching reducers in T goes on from index start
1521//#if 1
1522#ifdef DEBUGF5
1523 Print("SigSAFE: %d\n",sigSafe);
1524#endif
1525 if (sigSafe != 3)
1526 {
1527 // start the next search for reducers in T from the beginning
1528 start = 0;
1529#ifdef KDEBUG
1530 if (TEST_OPT_DEBUG)
1531 {
1532 PrintS("\nto ");
1533 h->wrp();
1534 PrintLn();
1535 }
1536#endif
1537
1538 h_p = h->GetLmTailRing();
1539 if (h_p == NULL)
1540 {
1541 kDeleteLcm(h);
1542 return 0;
1543 }
1544 h->SetShortExpVector();
1545 not_sev = ~ h->sev;
1546 /*
1547 * try to reduce the s-polynomial h
1548 *test first whether h should go to the lazyset L
1549 *-if the degree jumps
1550 *-if the number of pre-defined reductions jumps
1551 */
1552 pass++;
1553 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1554 {
1555 h->SetLmCurrRing();
1556 at = strat->posInL(strat->L,strat->Ll,h,strat);
1557 if (at <= strat->Ll)
1558 {
1559 int dummy=strat->sl;
1560 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1561 {
1562 return 1;
1563 }
1564 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1565#ifdef KDEBUG
1566 if (TEST_OPT_DEBUG)
1567 Print(" lazy: -> L%d\n",at);
1568#endif
1569 h->Clear();
1570 return -1;
1571 }
1572 }
1573 }
1574 }
1575}
1576
1577// tail reduction for SBA
1578poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
1579{
1580 strat->redTailChange=FALSE;
1581 if (strat->noTailReduction) return L->GetLmCurrRing();
1582 poly h, p;
1583 p = h = L->GetLmTailRing();
1584 if ((h==NULL) || (pNext(h)==NULL))
1585 return L->GetLmCurrRing();
1586
1587 TObject* With;
1588 // placeholder in case strat->tl < 0
1589 TObject With_s(strat->tailRing);
1590
1591 LObject Ln(pNext(h), strat->tailRing);
1592 Ln.sig = L->sig;
1593 Ln.sevSig = L->sevSig;
1594 Ln.pLength = L->GetpLength() - 1;
1595
1596 pNext(h) = NULL;
1597 if (L->p != NULL) pNext(L->p) = NULL;
1598 L->pLength = 1;
1599
1600 Ln.PrepareRed(strat->use_buckets);
1601
1602 int cnt=REDTAIL_CANONICALIZE;
1603 while(!Ln.IsNull())
1604 {
1605 loop
1606 {
1607 if(rField_is_Ring(currRing) && strat->sigdrop)
1608 break;
1609 Ln.SetShortExpVector();
1610 if (withT)
1611 {
1612 int j;
1613 j = kFindDivisibleByInT(strat, &Ln);
1614 if (j < 0) break;
1615 With = &(strat->T[j]);
1616 }
1617 else
1618 {
1619 With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1620 if (With == NULL) break;
1621 }
1622 cnt--;
1623 if (cnt==0)
1624 {
1626 /*poly tmp=*/Ln.CanonicalizeP();
1628 {
1629 Ln.Normalize();
1630 //pNormalize(tmp);
1631 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1632 }
1633 }
1635 {
1636 With->pNorm();
1637 }
1638 strat->redTailChange=TRUE;
1639 int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1641 L->sig = Ln.sig;
1642 //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1643 // I delete it an then set Ln.sig. Hence L->sig is lost
1644#if SBA_PRINT_REDUCTION_STEPS
1645 if (ret != 3)
1646 sba_reduction_steps++;
1647#endif
1648#if SBA_PRINT_OPERATIONS
1649 if (ret != 3)
1650 sba_operations += pLength(With->p);
1651#endif
1652 if (ret)
1653 {
1654 // reducing the tail would violate the exp bound
1655 // set a flag and hope for a retry (in bba)
1657 if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1658 do
1659 {
1660 pNext(h) = Ln.LmExtractAndIter();
1661 pIter(h);
1662 L->pLength++;
1663 } while (!Ln.IsNull());
1664 goto all_done;
1665 }
1666 if (Ln.IsNull()) goto all_done;
1667 if (! withT) With_s.Init(currRing);
1668 if(rField_is_Ring(currRing) && strat->sigdrop)
1669 {
1670 //Cannot break the loop here so easily
1671 break;
1672 }
1673 }
1674 pNext(h) = Ln.LmExtractAndIter();
1675 pIter(h);
1677 pNormalize(h);
1678 L->pLength++;
1679 }
1680 all_done:
1681 Ln.Delete();
1682 if (L->p != NULL) pNext(L->p) = pNext(p);
1683
1684 if (strat->redTailChange)
1685 {
1686 L->length = 0;
1687 }
1688 //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1689 //L->Normalize(); // HANNES: should have a test
1690 kTest_L(L,strat);
1691 return L->GetLmCurrRing();
1692}
1693
1694/*2
1695* reduction procedure for the inhomogeneous case
1696* and not a degree-ordering
1697*/
1699{
1700 if (strat->tl<0) return 1;
1701 int at,i,ii,li;
1702 int j = 0;
1703 int pass = 0;
1704 int cnt = RED_CANONICALIZE;
1705 assume(h->pFDeg() == h->FDeg);
1706 long reddeg = h->GetpFDeg();
1707 long d;
1708 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1709
1710 h->SetShortExpVector();
1711 poly h_p = h->GetLmTailRing();
1712 h->PrepareRed(strat->use_buckets);
1713 loop
1714 {
1715 j = kFindDivisibleByInT(strat, h);
1716 if (j < 0) return 1;
1717
1718 li = strat->T[j].pLength;
1719 ii = j;
1720 /*
1721 * the polynomial to reduce with (up to the moment) is;
1722 * pi with length li
1723 */
1724
1725 i = j;
1726#if 1
1727 if (test_opt_length)
1728 {
1729 if (li<=0) li=strat->T[j].GetpLength();
1730 if(li>2)
1731 {
1732 unsigned long not_sev = ~ h->sev;
1733 loop
1734 {
1735 /*- search the shortest possible with respect to length -*/
1736 i++;
1737 if (i > strat->tl)
1738 break;
1739 if ((strat->T[i].pLength < li)
1740 &&
1741 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1742 h_p, not_sev, strat->tailRing))
1743 {
1744 /*
1745 * the polynomial to reduce with is now;
1746 */
1747 li = strat->T[i].pLength;
1748 if (li<=0) li=strat->T[i].GetpLength();
1749 ii = i;
1750 if (li<3) break;
1751 }
1752 }
1753 }
1754 }
1755#endif
1756
1757 /*
1758 * end of search: have to reduce with pi
1759 */
1760
1761
1762#ifdef KDEBUG
1763 if (TEST_OPT_DEBUG)
1764 {
1765 PrintS("red:");
1766 h->wrp();
1767 PrintS(" with ");
1768 strat->T[ii].wrp();
1769 }
1770#endif
1771
1772 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1773#if SBA_PRINT_REDUCTION_STEPS
1774 sba_interreduction_steps++;
1775#endif
1776#if SBA_PRINT_OPERATIONS
1777 sba_interreduction_operations += pLength(strat->T[ii].p);
1778#endif
1779
1780#ifdef KDEBUG
1781 if (TEST_OPT_DEBUG)
1782 {
1783 PrintS("\nto ");
1784 h->wrp();
1785 PrintLn();
1786 }
1787#endif
1788
1789 h_p=h->GetLmTailRing();
1790
1791 if (h_p == NULL)
1792 {
1793 kDeleteLcm(h);
1794 return 0;
1795 }
1796 #if 0 // red id redLiftstd if OPT_IDLIFT
1798 {
1799 if (h->p!=NULL)
1800 {
1801 if(p_GetComp(h->p,currRing)>strat->syzComp)
1802 {
1803 h->Delete();
1804 return 0;
1805 }
1806 }
1807 else if (h->t_p!=NULL)
1808 {
1809 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1810 {
1811 h->Delete();
1812 return 0;
1813 }
1814 }
1815 }
1816 #endif
1817 #if 0
1818 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1819 {
1820 if (h->p!=NULL)
1821 {
1822 if(p_GetComp(h->p,currRing)>strat->syzComp)
1823 {
1824 return 1;
1825 }
1826 }
1827 else if (h->t_p!=NULL)
1828 {
1829 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1830 {
1831 return 1;
1832 }
1833 }
1834 }
1835 #endif
1836 h->SetShortExpVector();
1837 d = h->SetpFDeg();
1838 /*- try to reduce the s-polynomial -*/
1839 cnt--;
1840 pass++;
1841 if (//!TEST_OPT_REDTHROUGH &&
1842 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
1843 {
1844 h->SetLmCurrRing();
1845 at = strat->posInL(strat->L,strat->Ll,h,strat);
1846 if (at <= strat->Ll)
1847 {
1848#if 1
1849#ifdef HAVE_SHIFTBBA
1850 if (rIsLPRing(currRing))
1851 {
1852 if (kFindDivisibleByInT(strat, h) < 0)
1853 return 1;
1854 }
1855 else
1856#endif
1857 {
1858 int dummy=strat->sl;
1859 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1860 return 1;
1861 }
1862#endif
1863#ifdef KDEBUG
1864 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1865#endif
1866 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1867 h->Clear();
1868 return -1;
1869 }
1870 }
1871 else if (d != reddeg)
1872 {
1873 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
1874 {
1875 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1876 {
1877 strat->overflow=TRUE;
1878 //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1879 h->GetP();
1880 at = strat->posInL(strat->L,strat->Ll,h,strat);
1881 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1882 h->Clear();
1883 return -1;
1884 }
1885 }
1886 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1887 {
1888 Print(".%ld",d);mflush();
1889 reddeg = d;
1890 }
1891 }
1892 else if (UNLIKELY(cnt==0))
1893 {
1894 h->CanonicalizeP();
1895 cnt=RED_CANONICALIZE;
1896 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1897 }
1898 }
1899}
1900/*2
1901* reduction procedure for the sugar-strategy (honey)
1902* reduces h with elements from T choosing first possible
1903* element in T with respect to the given ecart
1904*/
1906{
1907 if (strat->tl<0) return 1;
1908 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1909 assume(h->FDeg == h->pFDeg());
1910 poly h_p;
1911 int i,j,at,pass,ei, ii, h_d;
1912 long reddeg,d;
1913 int li;
1914 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1915
1916 pass = j = 0;
1917 d = reddeg = h->GetpFDeg() + h->ecart;
1918 h->SetShortExpVector();
1919 h_p = h->GetLmTailRing();
1920
1921 h->PrepareRed(strat->use_buckets);
1922 loop
1923 {
1924 j=kFindDivisibleByInT(strat, h);
1925 if (j < 0) return 1;
1926
1927 ei = strat->T[j].ecart;
1928 li = strat->T[j].pLength;
1929 ii = j;
1930 /*
1931 * the polynomial to reduce with (up to the moment) is;
1932 * pi with ecart ei (T[ii])
1933 */
1934 i = j;
1935 if (test_opt_length)
1936 {
1937 if (li<=0) li=strat->T[j].GetpLength();
1938 if (li>2)
1939 {
1940 unsigned long not_sev = ~ h->sev;
1941 loop
1942 {
1943 /*- takes the first possible with respect to ecart -*/
1944 i++;
1945 if (i > strat->tl) break;
1946 if (ei <= h->ecart) break;
1947 if(p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1948 h_p, not_sev, strat->tailRing))
1949 {
1950 strat->T[i].GetpLength();
1951 if (((strat->T[i].ecart < ei) && (ei> h->ecart))
1952 || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1953 {
1954 /*
1955 * the polynomial to reduce with is now;
1956 */
1957 ei = strat->T[i].ecart;
1958 li = strat->T[i].pLength;
1959 ii = i;
1960 if (li==1) break;
1961 if (ei<=h->ecart) break;
1962 }
1963 }
1964 }
1965 }
1966 }
1967
1968 /*
1969 * end of search: have to reduce with pi
1970 */
1971 if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
1972 {
1973 h->GetTP(); // clears bucket
1974 h->SetLmCurrRing();
1975 /*
1976 * It is not possible to reduce h with smaller ecart;
1977 * if possible h goes to the lazy-set L,i.e
1978 * if its position in L would be not the last one
1979 */
1980 if (strat->Ll >= 0) /* L is not empty */
1981 {
1982 at = strat->posInL(strat->L,strat->Ll,h,strat);
1983 if(at <= strat->Ll)
1984 /*- h will not become the next element to reduce -*/
1985 {
1986 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1987#ifdef KDEBUG
1988 if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1989#endif
1990 h->Clear();
1991 return -1;
1992 }
1993 }
1994 }
1995#ifdef KDEBUG
1996 if (TEST_OPT_DEBUG)
1997 {
1998 PrintS("red:");
1999 h->wrp();
2000 Print("\nwith T[%d]:",ii);
2001 strat->T[ii].wrp();
2002 }
2003#endif
2004 assume(strat->fromT == FALSE);
2005
2006 ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
2007#if SBA_PRINT_REDUCTION_STEPS
2008 sba_interreduction_steps++;
2009#endif
2010#if SBA_PRINT_OPERATIONS
2011 sba_interreduction_operations += strat->T[ii].pLength;
2012#endif
2013#ifdef KDEBUG
2014 if (TEST_OPT_DEBUG)
2015 {
2016 PrintS("\nto:");
2017 h->wrp();
2018 PrintLn();
2019 }
2020#endif
2021 if(h->IsNull())
2022 {
2023 kDeleteLcm(h);
2024 h->Clear();
2025 return 0;
2026 }
2027 #if 0 // red is redLiftstd if OPT_IDLIFT
2029 {
2030 if (h->p!=NULL)
2031 {
2032 if(p_GetComp(h->p,currRing)>strat->syzComp)
2033 {
2034 h->Delete();
2035 return 0;
2036 }
2037 }
2038 else if (h->t_p!=NULL)
2039 {
2040 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2041 {
2042 h->Delete();
2043 return 0;
2044 }
2045 }
2046 }
2047 else
2048 #endif
2049 if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
2050 {
2051 if (h->p!=NULL)
2052 {
2053 if(p_GetComp(h->p,currRing)>strat->syzComp)
2054 {
2055 return 1;
2056 }
2057 }
2058 else if (h->t_p!=NULL)
2059 {
2060 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2061 {
2062 return 1;
2063 }
2064 }
2065 }
2066 h->SetShortExpVector();
2067 h_d = h->SetpFDeg();
2068 /* compute the ecart */
2069 if (ei <= h->ecart)
2070 h->ecart = d-h_d;
2071 else
2072 h->ecart = d-h_d+ei-h->ecart;
2073
2074 /*
2075 * try to reduce the s-polynomial h
2076 *test first whether h should go to the lazyset L
2077 *-if the degree jumps
2078 *-if the number of pre-defined reductions jumps
2079 */
2080 pass++;
2081 d = h_d + h->ecart;
2083 && (strat->Ll >= 0)
2084 && ((d > reddeg) || (pass > strat->LazyPass))))
2085 {
2086 h->GetTP(); // clear bucket
2087 h->SetLmCurrRing();
2088 at = strat->posInL(strat->L,strat->Ll,h,strat);
2089 if (at <= strat->Ll)
2090 {
2091#ifdef HAVE_SHIFTBBA
2092 if (rIsLPRing(currRing))
2093 {
2094 if (kFindDivisibleByInT(strat, h) < 0)
2095 return 1;
2096 }
2097 else
2098#endif
2099 {
2100 int dummy=strat->sl;
2101 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2102 return 1;
2103 }
2104 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2105#ifdef KDEBUG
2106 if (TEST_OPT_DEBUG)
2107 Print(" degree jumped: -> L%d\n",at);
2108#endif
2109 h->Clear();
2110 return -1;
2111 }
2112 }
2113 else if (d > reddeg)
2114 {
2115 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2116 {
2117 if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2118 {
2119 strat->overflow=TRUE;
2120 //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2121 h->GetP();
2122 at = strat->posInL(strat->L,strat->Ll,h,strat);
2123 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2124 h->Clear();
2125 return -1;
2126 }
2127 }
2128 else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
2129 {
2130 //h->wrp(); Print("<%d>\n",h->GetpLength());
2131 reddeg = d;
2132 Print(".%ld",d); mflush();
2133 }
2134 }
2135 }
2136}
2137
2138/*2
2139* reduction procedure for the normal form
2140*/
2141
2142poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
2143{
2144 if (h==NULL) return NULL;
2145 int j;
2146 int cnt=REDNF_CANONICALIZE;
2147 max_ind=strat->sl;
2148
2149 if (0 > strat->sl)
2150 {
2151 return h;
2152 }
2153 LObject P(h);
2154 P.SetShortExpVector();
2155 P.bucket = kBucketCreate(currRing);
2156 kBucketInit(P.bucket,P.p,pLength(P.p));
2157 kbTest(P.bucket);
2158#ifdef HAVE_RINGS
2159 BOOLEAN is_ring = rField_is_Ring(currRing);
2160#endif
2161#ifdef KDEBUG
2162// if (TEST_OPT_DEBUG)
2163// {
2164// PrintS("redNF: starting S:\n");
2165// for( j = 0; j <= max_ind; j++ )
2166// {
2167// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2168// pWrite(strat->S[j]);
2169// }
2170// };
2171#endif
2172
2173 loop
2174 {
2175 j=kFindDivisibleByInS(strat,&max_ind,&P);
2176 if (j>=0)
2177 {
2178#ifdef HAVE_RINGS
2179 if (!is_ring)
2180 {
2181#endif
2182 int sl=pSize(strat->S[j]);
2183 int jj=j;
2184 loop
2185 {
2186 int sll;
2187 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2188 if (jj<0) break;
2189 sll=pSize(strat->S[jj]);
2190 if (sll<sl)
2191 {
2192 #ifdef KDEBUG
2193 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2194 #endif
2195 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2196 j=jj;
2197 sl=sll;
2198 }
2199 }
2200 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2201 {
2202 pNorm(strat->S[j]);
2203 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2204 }
2205#ifdef HAVE_RINGS
2206 }
2207#endif
2208 nNormalize(pGetCoeff(P.p));
2209#ifdef KDEBUG
2210 if (TEST_OPT_DEBUG)
2211 {
2212 PrintS("red:");
2213 wrp(h);
2214 PrintS(" with ");
2215 wrp(strat->S[j]);
2216 }
2217#endif
2218#ifdef HAVE_PLURAL
2220 {
2221 number coef;
2222 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2223 nDelete(&coef);
2224 }
2225 else
2226#endif
2227 {
2228 number coef;
2229 coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2230 nDelete(&coef);
2231 }
2232 cnt--;
2233 if (cnt==0)
2234 {
2235 kBucketCanonicalize(P.bucket);
2237 }
2238 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2239 if (h==NULL)
2240 {
2241 kBucketDestroy(&P.bucket);
2242 return NULL;
2243 }
2244 kbTest(P.bucket);
2245 P.p=h;
2246 P.t_p=NULL;
2247 P.SetShortExpVector();
2248#ifdef KDEBUG
2249 if (TEST_OPT_DEBUG)
2250 {
2251 PrintS("\nto:");
2252 wrp(h);
2253 PrintLn();
2254 }
2255#endif
2256 }
2257 else
2258 {
2259 P.p=kBucketClear(P.bucket);
2260 kBucketDestroy(&P.bucket);
2261 pNormalize(P.p);
2262 return P.p;
2263 }
2264 }
2265}
2266
2267/*2
2268* reduction procedure from global case but with jet bound
2269*/
2270
2271poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
2272{
2273 h = pJet(h,bound);
2274 if (h==NULL) return NULL;
2275 int j;
2276 max_ind=strat->sl;
2277
2278 if (0 > strat->sl)
2279 {
2280 return h;
2281 }
2282 LObject P(h);
2283 P.SetShortExpVector();
2284 P.bucket = kBucketCreate(currRing);
2285 kBucketInit(P.bucket,P.p,pLength(P.p));
2286 kbTest(P.bucket);
2287#ifdef HAVE_RINGS
2288 BOOLEAN is_ring = rField_is_Ring(currRing);
2289#endif
2290
2291 loop
2292 {
2293 j=kFindDivisibleByInS(strat,&max_ind,&P);
2294 if (j>=0)
2295 {
2296#ifdef HAVE_RINGS
2297 if (!is_ring)
2298 {
2299#endif
2300 int sl=pSize(strat->S[j]);
2301 int jj=j;
2302 loop
2303 {
2304 int sll;
2305 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2306 if (jj<0) break;
2307 sll=pSize(strat->S[jj]);
2308 if (sll<sl)
2309 {
2310 #ifdef KDEBUG
2311 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2312 #endif
2313 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2314 j=jj;
2315 sl=sll;
2316 }
2317 }
2318 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2319 {
2320 pNorm(strat->S[j]);
2321 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2322 }
2323#ifdef HAVE_RINGS
2324 }
2325#endif
2326 nNormalize(pGetCoeff(P.p));
2327#ifdef KDEBUG
2328 if (TEST_OPT_DEBUG)
2329 {
2330 PrintS("red:");
2331 wrp(h);
2332 PrintS(" with ");
2333 wrp(strat->S[j]);
2334 }
2335#endif
2336#ifdef HAVE_PLURAL
2338 {
2339 number coef;
2340 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2341 nDelete(&coef);
2342 }
2343 else
2344#endif
2345 {
2346 number coef;
2347 coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2348 P.p = kBucketClear(P.bucket);
2349 P.p = pJet(P.p,bound);
2350 if(!P.IsNull())
2351 {
2352 kBucketDestroy(&P.bucket);
2353 P.SetShortExpVector();
2354 P.bucket = kBucketCreate(currRing);
2355 kBucketInit(P.bucket,P.p,pLength(P.p));
2356 }
2357 nDelete(&coef);
2358 }
2359 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2360 if (h==NULL)
2361 {
2362 kBucketDestroy(&P.bucket);
2363 return NULL;
2364 }
2365 kbTest(P.bucket);
2366 P.p=h;
2367 P.t_p=NULL;
2368 P.SetShortExpVector();
2369#ifdef KDEBUG
2370 if (TEST_OPT_DEBUG)
2371 {
2372 PrintS("\nto:");
2373 wrp(h);
2374 PrintLn();
2375 }
2376#endif
2377 }
2378 else
2379 {
2380 P.p=kBucketClear(P.bucket);
2381 kBucketDestroy(&P.bucket);
2382 pNormalize(P.p);
2383 return P.p;
2384 }
2385 }
2386}
2387
2388void kDebugPrint(kStrategy strat);
2389
2390ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2391{
2392 int red_result = 1;
2393 int olddeg,reduc;
2394 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2395 BOOLEAN withT = FALSE;
2396 BITSET save;
2397 SI_SAVE_OPT1(save);
2398
2399 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2401 initBuchMoraPosRing(strat);
2402 else
2403 initBuchMoraPos(strat);
2404 initHilbCrit(F,Q,&hilb,strat);
2405 initBba(strat);
2406 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2407 /*Shdl=*/initBuchMora(F, Q,strat);
2408 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2409 reduc = olddeg = 0;
2410
2411#ifndef NO_BUCKETS
2413 strat->use_buckets = 1;
2414#endif
2415 // redtailBBa against T for inhomogenous input
2416 if (!TEST_OPT_OLDSTD)
2417 withT = ! strat->homog;
2418
2419 // strat->posInT = posInT_pLength;
2420 kTest_TS(strat);
2421
2422#ifdef HAVE_TAIL_RING
2423 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2425#endif
2426 if (BVERBOSE(23))
2427 {
2428 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2429 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2430 kDebugPrint(strat);
2431 }
2432
2433
2434#ifdef KDEBUG
2435 //kDebugPrint(strat);
2436#endif
2437 /* compute------------------------------------------------------- */
2438 while (strat->Ll >= 0)
2439 {
2440 #ifdef KDEBUG
2441 if (TEST_OPT_DEBUG) messageSets(strat);
2442 #endif
2443 if (siCntrlc)
2444 {
2445 while (strat->Ll >= 0)
2446 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2447 strat->noClearS=TRUE;
2448 }
2450 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2451 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2452 {
2453 /*
2454 *stops computation if
2455 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2456 *a predefined number Kstd1_deg
2457 */
2458 while ((strat->Ll >= 0)
2459 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2460 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2461 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2462 )
2463 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2464 if (strat->Ll<0) break;
2465 else strat->noClearS=TRUE;
2466 }
2467 if (strat->Ll== 0) strat->interpt=TRUE;
2468 /* picks the last element from the lazyset L */
2469 strat->P = strat->L[strat->Ll];
2470 strat->Ll--;
2471
2472 if (pNext(strat->P.p) == strat->tail)
2473 {
2474 // deletes the short spoly
2476 pLmDelete(strat->P.p);
2477 else
2478 pLmFree(strat->P.p);
2479 strat->P.p = NULL;
2480 poly m1 = NULL, m2 = NULL;
2481
2482 // check that spoly creation is ok
2483 while (strat->tailRing != currRing &&
2484 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2485 {
2486 assume(m1 == NULL && m2 == NULL);
2487 // if not, change to a ring where exponents are at least
2488 // large enough
2489 if (!kStratChangeTailRing(strat))
2490 {
2491 WerrorS("OVERFLOW...");
2492 break;
2493 }
2494 }
2495 // create the real one
2496 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2497 strat->tailRing, m1, m2, strat->R);
2498 }
2499 else if (strat->P.p1 == NULL)
2500 {
2501 if (strat->minim > 0)
2502 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2503 // for input polys, prepare reduction
2504 strat->P.PrepareRed(strat->use_buckets);
2505 }
2506
2507 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2508 {
2509 red_result = 0;
2510 }
2511 else
2512 {
2513 if (TEST_OPT_PROT)
2514 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2515 &olddeg,&reduc,strat, red_result);
2516
2517 /* reduction of the element chosen from L */
2518 red_result = strat->red(&strat->P,strat);
2519 if (errorreported) break;
2520 }
2521
2522 if (strat->overflow)
2523 {
2524 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2525 }
2526
2527 // reduction to non-zero new poly
2528 if (red_result == 1)
2529 {
2530 // get the polynomial (canonicalize bucket, make sure P.p is set)
2531 strat->P.GetP(strat->lmBin);
2532 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2533 // but now, for entering S, T, we reset it
2534 // in the inhomogeneous case: FDeg == pFDeg
2535 if (strat->homog) strat->initEcart(&(strat->P));
2536
2537 /* statistic */
2538 if (TEST_OPT_PROT) PrintS("s");
2539
2540 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2541
2542 // reduce the tail and normalize poly
2543 // in the ring case we cannot expect LC(f) = 1,
2544 strat->redTailChange=FALSE;
2545
2546 /* if we are computing over Z we always want to try and cut down
2547 * the coefficients in the tail terms */
2549 {
2550 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2551 }
2552
2554 {
2555 strat->P.pCleardenom();
2557 {
2558 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2559 strat->P.pCleardenom();
2560 if (strat->redTailChange) { strat->P.t_p=NULL; }
2561 }
2562 }
2563 else
2564 {
2565 strat->P.pNorm();
2567 {
2568 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2569 if (strat->redTailChange) { strat->P.t_p=NULL; }
2570 }
2571 }
2572
2573#ifdef KDEBUG
2574 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2575#endif /* KDEBUG */
2576
2577 // min_std stuff
2578 if ((strat->P.p1==NULL) && (strat->minim>0))
2579 {
2580 if (strat->minim==1)
2581 {
2582 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2583 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2584 }
2585 else
2586 {
2587 strat->M->m[minimcnt]=strat->P.p2;
2588 strat->P.p2=NULL;
2589 }
2590 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2591 pNext(strat->M->m[minimcnt])
2592 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2593 strat->tailRing, currRing,
2594 currRing->PolyBin);
2595 minimcnt++;
2596 }
2597
2598 // enter into S, L, and T
2599 if (((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2600 && ((!TEST_OPT_IDELIM) || (p_Deg(strat->P.p,currRing) > 0)))
2601 {
2602 strat->P.SetShortExpVector();
2603 enterT(strat->P, strat);
2605 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2606 else
2607 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2608 // posInS only depends on the leading term
2609 strat->enterS(strat->P, pos, strat, strat->tl);
2610#if 0
2611 int pl=pLength(strat->P.p);
2612 if (pl==1)
2613 {
2614 //if (TEST_OPT_PROT)
2615 //PrintS("<1>");
2616 }
2617 else if (pl==2)
2618 {
2619 //if (TEST_OPT_PROT)
2620 //PrintS("<2>");
2621 }
2622#endif
2623 }
2624 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2625// Print("[%d]",hilbeledeg);
2626 kDeleteLcm(&strat->P);
2627 if (strat->s_poly!=NULL)
2628 {
2629 // the only valid entries are: strat->P.p,
2630 // strat->tailRing (read-only, keep it)
2631 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2632 if (strat->s_poly(strat))
2633 {
2634 // we are called AFTER enterS, i.e. if we change P
2635 // we have to add it also to S/T
2636 // and add pairs
2637 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2638 enterT(strat->P, strat);
2640 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2641 else
2642 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2643 strat->enterS(strat->P, pos, strat, strat->tl);
2644 }
2645 }
2646 }
2647 else if (strat->P.p1 == NULL && strat->minim > 0)
2648 {
2649 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2650 }
2651
2652#ifdef KDEBUG
2653 memset(&(strat->P), 0, sizeof(strat->P));
2654#endif /* KDEBUG */
2655 kTest_TS(strat);
2656 }
2657#ifdef KDEBUG
2658 if (TEST_OPT_DEBUG) messageSets(strat);
2659#endif /* KDEBUG */
2660
2661 if (TEST_OPT_SB_1)
2662 {
2664 {
2665 int k=1;
2666 int j;
2667 while(k<=strat->sl)
2668 {
2669 j=0;
2670 loop
2671 {
2672 if (j>=k) break;
2673 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2674 j++;
2675 }
2676 k++;
2677 }
2678 }
2679 }
2680 /* complete reduction of the standard basis--------- */
2681 if (TEST_OPT_REDSB)
2682 {
2683 completeReduce(strat);
2684 if (strat->completeReduce_retry)
2685 {
2686 // completeReduce needed larger exponents, retry
2687 // to reduce with S (instead of T)
2688 // and in currRing (instead of strat->tailRing)
2689#ifdef HAVE_TAIL_RING
2690 if(currRing->bitmask>strat->tailRing->bitmask)
2691 {
2693 cleanT(strat);strat->tailRing=currRing;
2694 int i;
2695 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2696 completeReduce(strat);
2697 }
2698 if (strat->completeReduce_retry)
2699#endif
2700 Werror("exponent bound is %ld",currRing->bitmask);
2701 }
2702 }
2703 else if (TEST_OPT_PROT) PrintLn();
2704 /* release temp data-------------------------------- */
2705 exitBuchMora(strat);
2706 /* postprocessing for GB over ZZ --------------------*/
2707 if (!errorreported)
2708 {
2710 {
2711 for(int i = 0;i<=strat->sl;i++)
2712 {
2713 if(!nGreaterZero(pGetCoeff(strat->S[i])))
2714 {
2715 strat->S[i] = pNeg(strat->S[i]);
2716 }
2717 }
2718 finalReduceByMon(strat);
2719 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2720 {
2721 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2722 {
2723 strat->S[i] = pNeg(strat->Shdl->m[i]);
2724 }
2725 }
2726 }
2727 //else if (rField_is_Ring(currRing))
2728 // finalReduceByMon(strat);
2729 }
2730// if (TEST_OPT_WEIGHTM)
2731// {
2732// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2733// if (ecartWeights)
2734// {
2735// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2736// ecartWeights=NULL;
2737// }
2738// }
2739 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2740 SI_RESTORE_OPT1(save);
2741 /* postprocessing for GB over Q-rings ------------------*/
2742 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2743
2744 idTest(strat->Shdl);
2745
2746 return (strat->Shdl);
2747}
2748
2749ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2750{
2751 // ring order stuff:
2752 // in sba we have (until now) two possibilities:
2753 // 1. an incremental computation w.r.t. (C,monomial order)
2754 // 2. a (possibly non-incremental) computation w.r.t. the
2755 // induced Schreyer order.
2756 // The corresponding orders are computed in sbaRing(), depending
2757 // on the flag strat->sbaOrder
2758#if SBA_PRINT_ZERO_REDUCTIONS
2759 long zeroreductions = 0;
2760#endif
2761#if SBA_PRINT_PRODUCT_CRITERION
2762 long product_criterion = 0;
2763#endif
2764#if SBA_PRINT_SIZE_G
2765 int size_g = 0;
2766 int size_g_non_red = 0;
2767#endif
2768#if SBA_PRINT_SIZE_SYZ
2769 long size_syz = 0;
2770#endif
2771 // global variable
2772#if SBA_PRINT_REDUCTION_STEPS
2773 sba_reduction_steps = 0;
2774 sba_interreduction_steps = 0;
2775#endif
2776#if SBA_PRINT_OPERATIONS
2777 sba_operations = 0;
2778 sba_interreduction_operations = 0;
2779#endif
2780
2781 ideal F1 = F0;
2782 ring sRing, currRingOld;
2783 currRingOld = currRing;
2784 if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
2785 {
2786 sRing = sbaRing(strat);
2787 if (sRing!=currRingOld)
2788 {
2789 rChangeCurrRing (sRing);
2790 F1 = idrMoveR (F0, currRingOld, currRing);
2791 }
2792 }
2793 ideal F;
2794 // sort ideal F
2795 //Put the SigDrop element on the correct position (think of sbaEnterS)
2796 //We also sort them
2797 if(rField_is_Ring(currRing) && strat->sigdrop)
2798 {
2799 #if 1
2800 F = idInit(IDELEMS(F1),F1->rank);
2801 for (int i=0; i<IDELEMS(F1);++i)
2802 F->m[i] = F1->m[i];
2803 if(strat->sbaEnterS >= 0)
2804 {
2805 poly dummy;
2806 dummy = pCopy(F->m[0]); //the sigdrop element
2807 for(int i = 0;i<strat->sbaEnterS;i++)
2808 F->m[i] = F->m[i+1];
2809 F->m[strat->sbaEnterS] = dummy;
2810 }
2811 #else
2812 F = idInit(1,F1->rank);
2813 //printf("\nBefore the initial block sorting:\n");idPrint(F1);
2814 F->m[0] = F1->m[0];
2815 int pos;
2816 if(strat->sbaEnterS >= 0)
2817 {
2818 for(int i=1;i<=strat->sbaEnterS;i++)
2819 {
2820 pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2821 idInsertPolyOnPos(F,F1->m[i],pos);
2822 }
2823 for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2824 {
2825 pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2826 idInsertPolyOnPos(F,F1->m[i],pos);
2827 }
2828 poly dummy;
2829 dummy = pCopy(F->m[0]); //the sigdrop element
2830 for(int i = 0;i<strat->sbaEnterS;i++)
2831 F->m[i] = F->m[i+1];
2832 F->m[strat->sbaEnterS] = dummy;
2833 }
2834 else
2835 {
2836 for(int i=1;i<IDELEMS(F1);i++)
2837 {
2838 pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2839 idInsertPolyOnPos(F,F1->m[i],pos);
2840 }
2841 }
2842 #endif
2843 //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2844 }
2845 else
2846 {
2847 F = idInit(IDELEMS(F1),F1->rank);
2848 intvec *sort = idSort(F1);
2849 for (int i=0; i<sort->length();++i)
2850 F->m[i] = F1->m[(*sort)[i]-1];
2852 {
2853 // put the monomials after the sbaEnterS polynomials
2854 //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2855 int nrmon = 0;
2856 for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2857 {
2858 //pWrite(F->m[i]);
2859 if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2860 {
2861 poly mon = F->m[i];
2862 for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2863 {
2864 F->m[j] = F->m[j-1];
2865 }
2866 F->m[j] = mon;
2867 nrmon++;
2868 }
2869 //idPrint(F);
2870 }
2871 }
2872 }
2873 //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2875 strat->sigdrop = FALSE;
2876 strat->nrsyzcrit = 0;
2877 strat->nrrewcrit = 0;
2878#if SBA_INTERRED_START
2879 F = kInterRed(F,NULL);
2880#endif
2881#if F5DEBUG
2882 printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2883 rWrite (currRing);
2884 printf("ordSgn = %d\n",currRing->OrdSgn);
2885 printf("\n");
2886#endif
2887 int srmax,lrmax, red_result = 1;
2888 int olddeg,reduc;
2889 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2890 LObject L;
2891 BOOLEAN withT = TRUE;
2892 strat->max_lower_index = 0;
2893 //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2894 initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
2895 initSbaPos(strat);
2896 initHilbCrit(F,Q,&hilb,strat);
2897 initSba(F,strat);
2898 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2899 /*Shdl=*/initSbaBuchMora(F, Q,strat);
2900 idTest(strat->Shdl);
2901 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2902 srmax = strat->sl;
2903 reduc = olddeg = lrmax = 0;
2904#ifndef NO_BUCKETS
2906 strat->use_buckets = 1;
2907#endif
2908
2909 // redtailBBa against T for inhomogenous input
2910 // if (!TEST_OPT_OLDSTD)
2911 // withT = ! strat->homog;
2912
2913 // strat->posInT = posInT_pLength;
2914 kTest_TS(strat);
2915
2916#ifdef HAVE_TAIL_RING
2917 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2919#endif
2920 if (BVERBOSE(23))
2921 {
2922 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2923 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2924 kDebugPrint(strat);
2925 }
2926 // We add the elements directly in S from the previous loop
2927 if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2928 {
2929 for(int i = 0;i<strat->sbaEnterS;i++)
2930 {
2931 //Update: now the element is at the corect place
2932 //i+1 because on the 0 position is the sigdrop element
2933 enterT(strat->L[strat->Ll-(i)],strat);
2934 strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2935 }
2936 strat->Ll = strat->Ll - strat->sbaEnterS;
2937 strat->sbaEnterS = -1;
2938 }
2939 kTest_TS(strat);
2940#ifdef KDEBUG
2941 //kDebugPrint(strat);
2942#endif
2943 /* compute------------------------------------------------------- */
2944 while (strat->Ll >= 0)
2945 {
2946 if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
2947 #ifdef KDEBUG
2948 if (TEST_OPT_DEBUG) messageSets(strat);
2949 #endif
2950 if (strat->Ll== 0) strat->interpt=TRUE;
2951 /*
2952 if (TEST_OPT_DEGBOUND
2953 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2954 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2955 {
2956
2957 //stops computation if
2958 // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2959 //a predefined number Kstd1_deg
2960 while ((strat->Ll >= 0)
2961 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2962 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2963 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2964 )
2965 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2966 if (strat->Ll<0) break;
2967 else strat->noClearS=TRUE;
2968 }
2969 */
2970 if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2971 {
2972 strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2973#if F5C
2974 // 1. interreduction of the current standard basis
2975 // 2. generation of new principal syzygy rules for syzCriterion
2976 f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2977 lrmax, reduc, Q, w, hilb );
2978#endif
2979 // initialize new syzygy rules for the next iteration step
2980 initSyzRules(strat);
2981 }
2982 /*********************************************************************
2983 * interrreduction step is done, we can go on with the next iteration
2984 * step of the signature-based algorithm
2985 ********************************************************************/
2986 /* picks the last element from the lazyset L */
2987 strat->P = strat->L[strat->Ll];
2988 strat->Ll--;
2989
2991 strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2992 /* reduction of the element chosen from L */
2993 if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2994 {
2995 //#if 1
2996#ifdef DEBUGF5
2997 PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2998 PrintS("-------------------------------------------------\n");
2999 pWrite(strat->P.sig);
3000 pWrite(pHead(strat->P.p));
3001 pWrite(pHead(strat->P.p1));
3002 pWrite(pHead(strat->P.p2));
3003 PrintS("-------------------------------------------------\n");
3004#endif
3005 if (pNext(strat->P.p) == strat->tail)
3006 {
3007 // deletes the short spoly
3008 /*
3009 if (rField_is_Ring(currRing))
3010 pLmDelete(strat->P.p);
3011 else
3012 pLmFree(strat->P.p);
3013*/
3014 // TODO: needs some masking
3015 // TODO: masking needs to vanish once the signature
3016 // sutff is completely implemented
3017 strat->P.p = NULL;
3018 poly m1 = NULL, m2 = NULL;
3019
3020 // check that spoly creation is ok
3021 while (strat->tailRing != currRing &&
3022 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3023 {
3024 assume(m1 == NULL && m2 == NULL);
3025 // if not, change to a ring where exponents are at least
3026 // large enough
3027 if (!kStratChangeTailRing(strat))
3028 {
3029 WerrorS("OVERFLOW...");
3030 break;
3031 }
3032 }
3033 // create the real one
3034 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3035 strat->tailRing, m1, m2, strat->R);
3036
3037 }
3038 else if (strat->P.p1 == NULL)
3039 {
3040 if (strat->minim > 0)
3041 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3042 // for input polys, prepare reduction
3044 strat->P.PrepareRed(strat->use_buckets);
3045 }
3046 if (strat->P.p == NULL && strat->P.t_p == NULL)
3047 {
3048 red_result = 0;
3049 }
3050 else
3051 {
3052 //#if 1
3053#ifdef DEBUGF5
3054 PrintS("Poly before red: ");
3055 pWrite(pHead(strat->P.p));
3056 pWrite(strat->P.sig);
3057#endif
3058#if SBA_PRODUCT_CRITERION
3059 if (strat->P.prod_crit)
3060 {
3061#if SBA_PRINT_PRODUCT_CRITERION
3062 product_criterion++;
3063#endif
3064 int pos = posInSyz(strat, strat->P.sig);
3065 enterSyz(strat->P, strat, pos);
3066 kDeleteLcm(&strat->P);
3067 red_result = 2;
3068 }
3069 else
3070 {
3071 red_result = strat->red(&strat->P,strat);
3072 }
3073#else
3074 red_result = strat->red(&strat->P,strat);
3075#endif
3076 }
3077 }
3078 else
3079 {
3080 /*
3081 if (strat->P.lcm != NULL)
3082 pLmFree(strat->P.lcm);
3083 */
3084 red_result = 2;
3085 }
3087 {
3088 if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3089 {
3090 strat->P.p = pNeg(strat->P.p);
3091 strat->P.sig = pNeg(strat->P.sig);
3092 }
3093 strat->P.pLength = pLength(strat->P.p);
3094 if(strat->P.sig != NULL)
3095 strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3096 if(strat->P.p != NULL)
3097 strat->P.sev = pGetShortExpVector(strat->P.p);
3098 }
3099 //sigdrop case
3100 if(rField_is_Ring(currRing) && strat->sigdrop)
3101 {
3102 //First reduce it as much as one can
3103 red_result = redRing(&strat->P,strat);
3104 if(red_result == 0)
3105 {
3106 strat->sigdrop = FALSE;
3107 pDelete(&strat->P.sig);
3108 strat->P.sig = NULL;
3109 }
3110 else
3111 {
3112 strat->enterS(strat->P, 0, strat, strat->tl);
3113 if (TEST_OPT_PROT)
3114 PrintS("-");
3115 break;
3116 }
3117 }
3118 if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3119 {
3120 strat->sigdrop = TRUE;
3121 break;
3122 }
3123
3124 if (errorreported) break;
3125
3126//#if 1
3127#ifdef DEBUGF5
3128 if (red_result != 0)
3129 {
3130 PrintS("Poly after red: ");
3131 pWrite(pHead(strat->P.p));
3132 pWrite(strat->P.GetLmCurrRing());
3133 pWrite(strat->P.sig);
3134 printf("%d\n",red_result);
3135 }
3136#endif
3137 if (TEST_OPT_PROT)
3138 {
3139 if(strat->P.p != NULL)
3140 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3141 &olddeg,&reduc,strat, red_result);
3142 else
3143 message((strat->honey ? strat->P.ecart : 0),
3144 &olddeg,&reduc,strat, red_result);
3145 }
3146
3147 if (strat->overflow)
3148 {
3149 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3150 }
3151 // reduction to non-zero new poly
3152 if (red_result == 1)
3153 {
3154 // get the polynomial (canonicalize bucket, make sure P.p is set)
3155 strat->P.GetP(strat->lmBin);
3156
3157 // sig-safe computations may lead to wrong FDeg computation, thus we need
3158 // to recompute it to make sure everything is alright
3159 (strat->P).FDeg = (strat->P).pFDeg();
3160 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3161 // but now, for entering S, T, we reset it
3162 // in the inhomogeneous case: FDeg == pFDeg
3163 if (strat->homog) strat->initEcart(&(strat->P));
3164
3165 /* statistic */
3166 if (TEST_OPT_PROT) PrintS("s");
3167
3168 //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3169 // in F5E we know that the last reduced element is already the
3170 // the one with highest signature
3171 int pos = strat->sl+1;
3172
3173 // reduce the tail and normalize poly
3174 // in the ring case we cannot expect LC(f) = 1,
3175 #ifdef HAVE_RINGS
3176 poly beforetailred;
3178 beforetailred = pCopy(strat->P.sig);
3179 #endif
3180#if SBA_TAIL_RED
3182 {
3184 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3185 }
3186 else
3187 {
3188 if (strat->sbaOrder != 2)
3189 {
3191 {
3192 strat->P.pCleardenom();
3194 {
3195 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3196 strat->P.pCleardenom();
3197 }
3198 }
3199 else
3200 {
3201 strat->P.pNorm();
3203 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3204 }
3205 }
3206 }
3207 // It may happen that we have lost the sig in redtailsba
3208 // It cannot reduce to 0 since here we are doing just tail reduction.
3209 // Best case scenerio: remains the leading term
3210 if(rField_is_Ring(currRing) && strat->sigdrop)
3211 {
3212 strat->enterS(strat->P, 0, strat, strat->tl);
3213 break;
3214 }
3215#endif
3217 {
3218 if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
3219 {
3220 strat->sigdrop = TRUE;
3221 //Reduce it as much as you can
3222 red_result = redRing(&strat->P,strat);
3223 if(red_result == 0)
3224 {
3225 //It reduced to 0, cancel the sigdrop
3226 strat->sigdrop = FALSE;
3227 p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3228 }
3229 else
3230 {
3231 strat->enterS(strat->P, 0, strat, strat->tl);
3232 break;
3233 }
3234 }
3235 p_Delete(&beforetailred,currRing);
3236 // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3237 if(strat->P.p == NULL)
3238 goto case_when_red_result_changed;
3239 }
3240 // remove sigsafe label since it is no longer valid for the next element to
3241 // be reduced
3242 if (strat->sbaOrder == 1)
3243 {
3244 for (int jj = 0; jj<strat->tl+1; jj++)
3245 {
3246 if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3247 {
3248 strat->T[jj].is_sigsafe = FALSE;
3249 }
3250 }
3251 }
3252 else
3253 {
3254 for (int jj = 0; jj<strat->tl+1; jj++)
3255 {
3256 strat->T[jj].is_sigsafe = FALSE;
3257 }
3258 }
3259#ifdef KDEBUG
3260 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3261#endif /* KDEBUG */
3262
3263 // min_std stuff
3264 if ((strat->P.p1==NULL) && (strat->minim>0))
3265 {
3266 if (strat->minim==1)
3267 {
3268 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3269 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3270 }
3271 else
3272 {
3273 strat->M->m[minimcnt]=strat->P.p2;
3274 strat->P.p2=NULL;
3275 }
3276 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3277 pNext(strat->M->m[minimcnt])
3278 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3279 strat->tailRing, currRing,
3280 currRing->PolyBin);
3281 minimcnt++;
3282 }
3283
3284 // enter into S, L, and T
3285 //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3286 enterT(strat->P, strat);
3287 strat->T[strat->tl].is_sigsafe = FALSE;
3288 /*
3289 printf("hier\n");
3290 pWrite(strat->P.GetLmCurrRing());
3291 pWrite(strat->P.sig);
3292 */
3294 superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3295 else
3296 enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3297 if(rField_is_Ring(currRing) && strat->sigdrop)
3298 break;
3300 strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3301 strat->enterS(strat->P, pos, strat, strat->tl);
3302 if(strat->sbaOrder != 1)
3303 {
3304 BOOLEAN overwrite = FALSE;
3305 for (int tk=0; tk<strat->sl+1; tk++)
3306 {
3307 if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3308 {
3309 //printf("TK %d / %d\n",tk,strat->sl);
3310 overwrite = FALSE;
3311 break;
3312 }
3313 }
3314 //printf("OVERWRITE %d\n",overwrite);
3315 if (overwrite)
3316 {
3317 int cmp = pGetComp(strat->P.sig);
3318 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3319 p_GetExpV (strat->P.p,vv,currRing);
3320 p_SetExpV (strat->P.sig, vv,currRing);
3321 p_SetComp (strat->P.sig,cmp,currRing);
3322
3323 strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3324 int i;
3325 LObject Q;
3326 for(int ps=0;ps<strat->sl+1;ps++)
3327 {
3328
3329 strat->newt = TRUE;
3330 if (strat->syzl == strat->syzmax)
3331 {
3332 pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3333 strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3334 (strat->syzmax)*sizeof(unsigned long),
3335 ((strat->syzmax)+setmaxTinc)
3336 *sizeof(unsigned long));
3337 strat->syzmax += setmaxTinc;
3338 }
3339 Q.sig = pCopy(strat->P.sig);
3340 // add LM(F->m[i]) to the signature to get a Schreyer order
3341 // without changing the underlying polynomial ring at all
3342 if (strat->sbaOrder == 0)
3343 p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3344 // since p_Add_q() destroys all input
3345 // data we need to recreate help
3346 // each time
3347 // ----------------------------------------------------------
3348 // in the Schreyer order we always know that the multiplied
3349 // module monomial strat->P.sig gives the leading monomial of
3350 // the corresponding principal syzygy
3351 // => we do not need to compute the "real" syzygy completely
3352 poly help = p_Copy(strat->sig[ps],currRing);
3353 p_ExpVectorAdd (help,strat->P.p,currRing);
3354 Q.sig = p_Add_q(Q.sig,help,currRing);
3355 //printf("%d. SYZ ",i+1);
3356 //pWrite(strat->syz[i]);
3357 Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3358 i = posInSyz(strat, Q.sig);
3359 enterSyz(Q, strat, i);
3360 }
3361 }
3362 }
3363 // deg - idx - lp/rp
3364 // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3365 if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3366 {
3367 int cmp = pGetComp(strat->P.sig);
3368 unsigned max_cmp = IDELEMS(F);
3369 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3370 p_GetExpV (strat->P.p,vv,currRing);
3371 LObject Q;
3372 int pos;
3373 int idx = __p_GetComp(strat->P.sig,currRing);
3374 //printf("++ -- adding syzygies -- ++\n");
3375 // if new element is the first one in this index
3376 if (strat->currIdx < idx)
3377 {
3378 for (int i=0; i<strat->sl; ++i)
3379 {
3380 Q.sig = p_Copy(strat->P.sig,currRing);
3381 p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3382 poly help = p_Copy(strat->sig[i],currRing);
3383 p_ExpVectorAdd(help,strat->P.p,currRing);
3384 Q.sig = p_Add_q(Q.sig,help,currRing);
3385 //pWrite(Q.sig);
3386 pos = posInSyz(strat, Q.sig);
3387 enterSyz(Q, strat, pos);
3388 }
3389 strat->currIdx = idx;
3390 }
3391 else
3392 {
3393 // if the element is not the first one in the given index we build all
3394 // possible syzygies with elements of higher index
3395 for (unsigned i=cmp+1; i<=max_cmp; ++i)
3396 {
3397 pos = -1;
3398 for (int j=0; j<strat->sl; ++j)
3399 {
3400 if (__p_GetComp(strat->sig[j],currRing) == i)
3401 {
3402 pos = j;
3403 break;
3404 }
3405 }
3406 if (pos != -1)
3407 {
3408 Q.sig = p_One(currRing);
3409 p_SetExpV(Q.sig, vv, currRing);
3410 // F->m[i-1] corresponds to index i
3411 p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3412 p_SetComp(Q.sig, i, currRing);
3413 poly help = p_Copy(strat->P.sig,currRing);
3414 p_ExpVectorAdd(help,strat->S[pos],currRing);
3415 Q.sig = p_Add_q(Q.sig,help,currRing);
3416 if (strat->sbaOrder == 0)
3417 {
3418 if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3419 {
3420 pos = posInSyz(strat, Q.sig);
3421 enterSyz(Q, strat, pos);
3422 }
3423 }
3424 else
3425 {
3426 pos = posInSyz(strat, Q.sig);
3427 enterSyz(Q, strat, pos);
3428 }
3429 }
3430 }
3431 //printf("++ -- done adding syzygies -- ++\n");
3432 }
3433 }
3434//#if 1
3435#if DEBUGF50
3436 printf("---------------------------\n");
3437 Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3438 PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3439 PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3440#endif
3441 /*
3442 if (newrules)
3443 {
3444 newrules = FALSE;
3445 }
3446 */
3447#if 0
3448 int pl=pLength(strat->P.p);
3449 if (pl==1)
3450 {
3451 //if (TEST_OPT_PROT)
3452 //PrintS("<1>");
3453 }
3454 else if (pl==2)
3455 {
3456 //if (TEST_OPT_PROT)
3457 //PrintS("<2>");
3458 }
3459#endif
3460 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3461// Print("[%d]",hilbeledeg);
3462 kDeleteLcm(&strat->P);
3463 if (strat->sl>srmax) srmax = strat->sl;
3464 }
3465 else
3466 {
3467 case_when_red_result_changed:
3468 // adds signature of the zero reduction to
3469 // strat->syz. This is the leading term of
3470 // syzygy and can be used in syzCriterion()
3471 // the signature is added if and only if the
3472 // pair was not detected by the rewritten criterion in strat->red = redSig
3473 if (red_result!=2)
3474 {
3475#if SBA_PRINT_ZERO_REDUCTIONS
3476 zeroreductions++;
3477#endif
3478 if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3479 {
3480 //Catch the case when p = 0, sig = 0
3481 }
3482 else
3483 {
3484 int pos = posInSyz(strat, strat->P.sig);
3485 enterSyz(strat->P, strat, pos);
3486 //#if 1
3487 #ifdef DEBUGF5
3488 Print("ADDING STUFF TO SYZ : ");
3489 //pWrite(strat->P.p);
3490 pWrite(strat->P.sig);
3491 #endif
3492 }
3493 }
3494 if (strat->P.p1 == NULL && strat->minim > 0)
3495 {
3496 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3497 }
3498 }
3499
3500#ifdef KDEBUG
3501 memset(&(strat->P), 0, sizeof(strat->P));
3502#endif /* KDEBUG */
3503 kTest_TS(strat);
3504 }
3505 #if 0
3506 if(strat->sigdrop)
3507 printf("\nSigDrop!\n");
3508 else
3509 printf("\nEnded with no SigDrop\n");
3510 #endif
3511// Clean strat->P for the next sba call
3512 if(rField_is_Ring(currRing) && strat->sigdrop)
3513 {
3514 //This is used to know how many elements can we directly add to S in the next run
3515 if(strat->P.sig != NULL)
3516 strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3517 //else we already set it at the beggining of the loop
3518 #ifdef KDEBUG
3519 memset(&(strat->P), 0, sizeof(strat->P));
3520 #endif /* KDEBUG */
3521 }
3522#ifdef KDEBUG
3523 if (TEST_OPT_DEBUG) messageSets(strat);
3524#endif /* KDEBUG */
3525
3526 if (TEST_OPT_SB_1)
3527 {
3529 {
3530 int k=1;
3531 int j;
3532 while(k<=strat->sl)
3533 {
3534 j=0;
3535 loop
3536 {
3537 if (j>=k) break;
3538 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3539 j++;
3540 }
3541 k++;
3542 }
3543 }
3544 }
3545 /* complete reduction of the standard basis--------- */
3546 if (TEST_OPT_REDSB)
3547 {
3548 completeReduce(strat);
3549 if (strat->completeReduce_retry)
3550 {
3551 // completeReduce needed larger exponents, retry
3552 // to reduce with S (instead of T)
3553 // and in currRing (instead of strat->tailRing)
3554#ifdef HAVE_TAIL_RING
3555 if(currRing->bitmask>strat->tailRing->bitmask)
3556 {
3558 cleanT(strat);strat->tailRing=currRing;
3559 int i;
3560 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3561 completeReduce(strat);
3562 }
3563 if (strat->completeReduce_retry)
3564#endif
3565 Werror("exponent bound is %ld",currRing->bitmask);
3566 }
3567 }
3568 else if (TEST_OPT_PROT) PrintLn();
3569
3570#if SBA_PRINT_SIZE_SYZ
3571 // that is correct, syzl is counting one too far
3572 size_syz = strat->syzl;
3573#endif
3574// if (TEST_OPT_WEIGHTM)
3575// {
3576// pRestoreDegProcs(pFDegOld, pLDegOld);
3577// if (ecartWeights)
3578// {
3579// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3580// ecartWeights=NULL;
3581// }
3582// }
3583 if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3584 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3585#if SBA_PRINT_SIZE_G
3586 size_g_non_red = IDELEMS(strat->Shdl);
3587#endif
3589 exitSba(strat);
3590 // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3591 #ifdef HAVE_RINGS
3592 int k;
3594 {
3595 //for(k = strat->sl;k>=0;k--)
3596 // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3597 k = strat->Ll;
3598 #if 1
3599 // 1 - adds just the unused ones, 0 - adds everthing
3600 for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3601 {
3602 //printf("\nDeleted k = %i, %p\n",k,strat->L[k].p);pWrite(strat->L[k].p);pWrite(strat->L[k].p1);pWrite(strat->L[k].p2);
3603 deleteInL(strat->L,&strat->Ll,k,strat);
3604 }
3605 #endif
3606 //for(int kk = strat->sl;kk>=0;kk--)
3607 // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3608 //idPrint(strat->Shdl);
3609 //printf("\nk = %i\n",k);
3610 for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3611 {
3612 //printf("\nAdded k = %i\n",k);
3613 strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3614 //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3615 }
3616 }
3617 // Find the "sigdrop element" and put the same signature as the previous one - do we really need this?? - now i put it on the 0 position - no more comparing needed
3618 #if 0
3619 if(strat->sigdrop && rField_is_Ring(currRing))
3620 {
3621 for(k=strat->sl;k>=0;k--)
3622 {
3623 printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3624 if(strat->sig[k] == NULL)
3625 strat->sig[k] = pCopy(strat->sig[k-1]);
3626 }
3627 }
3628 #endif
3629 #endif
3630 //Never do this - you will damage S
3631 //idSkipZeroes(strat->Shdl);
3632 //idPrint(strat->Shdl);
3633
3634 if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3635 {
3636 rChangeCurrRing (currRingOld);
3637 F0 = idrMoveR (F1, sRing, currRing);
3638 strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3639 rChangeCurrRing (sRing);
3641 exitSba(strat);
3642 rChangeCurrRing (currRingOld);
3643 if(strat->tailRing == sRing)
3644 strat->tailRing = currRing;
3645 rDelete (sRing);
3646 }
3647 if(rField_is_Ring(currRing) && !strat->sigdrop)
3648 id_DelDiv(strat->Shdl, currRing);
3650 id_DelDiv(strat->Shdl, currRing);
3651 idSkipZeroes(strat->Shdl);
3652 idTest(strat->Shdl);
3653
3654#if SBA_PRINT_SIZE_G
3655 size_g = IDELEMS(strat->Shdl);
3656#endif
3657#ifdef DEBUGF5
3658 printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3659 int oo = 0;
3660 while (oo<IDELEMS(strat->Shdl))
3661 {
3662 printf(" %d. ",oo+1);
3663 pWrite(pHead(strat->Shdl->m[oo]));
3664 oo++;
3665 }
3666#endif
3667#if SBA_PRINT_ZERO_REDUCTIONS
3668 printf("----------------------------------------------------------\n");
3669 printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3670 zeroreductions = 0;
3671#endif
3672#if SBA_PRINT_REDUCTION_STEPS
3673 printf("----------------------------------------------------------\n");
3674 printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3675#endif
3676#if SBA_PRINT_OPERATIONS
3677 printf("OPERATIONS: %ld\n",sba_operations);
3678#endif
3679#if SBA_PRINT_REDUCTION_STEPS
3680 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3681 printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3682#endif
3683#if SBA_PRINT_OPERATIONS
3684 printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3685#endif
3686#if SBA_PRINT_REDUCTION_STEPS
3687 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3688 printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3689 sba_interreduction_steps = 0;
3690 sba_reduction_steps = 0;
3691#endif
3692#if SBA_PRINT_OPERATIONS
3693 printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3694 sba_interreduction_operations = 0;
3695 sba_operations = 0;
3696#endif
3697#if SBA_PRINT_SIZE_G
3698 printf("----------------------------------------------------------\n");
3699 printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3700 size_g = 0;
3701 size_g_non_red = 0;
3702#endif
3703#if SBA_PRINT_SIZE_SYZ
3704 printf("SIZE OF SYZ: %ld\n",size_syz);
3705 printf("----------------------------------------------------------\n");
3706 size_syz = 0;
3707#endif
3708#if SBA_PRINT_PRODUCT_CRITERION
3709 printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3710 product_criterion = 0;
3711#endif
3712 return (strat->Shdl);
3713}
3714
3715poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3716{
3717 assume(q!=NULL);
3718 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3719
3720// lazy_reduce flags: can be combined by |
3721//#define KSTD_NF_LAZY 1
3722 // do only a reduction of the leading term
3723//#define KSTD_NF_NONORM 4
3724 // only global: avoid normalization, return a multiply of NF
3725 poly p;
3726
3727 //if ((idIs0(F))&&(Q==NULL))
3728 // return pCopy(q); /*F=0*/
3729 //strat->ak = idRankFreeModule(F);
3730 /*- creating temp data structures------------------- -*/
3731 BITSET save1;
3732 SI_SAVE_OPT1(save1);
3734 initBuchMoraCrit(strat);
3735 strat->initEcart = initEcartBBA;
3736#ifdef HAVE_SHIFTBBA
3737 if (rIsLPRing(currRing))
3738 {
3739 strat->enterS = enterSBbaShift;
3740 }
3741 else
3742#endif
3743 {
3744 strat->enterS = enterSBba;
3745 }
3746#ifndef NO_BUCKETS
3748#endif
3749 /*- set S -*/
3750 strat->sl = -1;
3751 /*- init local data struct.---------------------------------------- -*/
3752 /*Shdl=*/initS(F,Q,strat);
3753 /*- compute------------------------------------------------------- -*/
3754 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3755 //{
3756 // for (i=strat->sl;i>=0;i--)
3757 // pNorm(strat->S[i]);
3758 //}
3759 kTest(strat);
3760 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3761 if (BVERBOSE(23)) kDebugPrint(strat);
3762 int max_ind;
3763 p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3764 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3765 {
3766 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3768 {
3769 p = redtailBba_Z(p,max_ind,strat);
3770 }
3771 else if (rField_is_Ring(currRing))
3772 {
3773 p = redtailBba_Ring(p,max_ind,strat);
3774 }
3775 else
3776 {
3777 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3778 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3779 }
3780 }
3781 /*- release temp data------------------------------- -*/
3782 assume(strat->L==NULL); /* strat->L unused */
3783 assume(strat->B==NULL); /* strat->B unused */
3784 omFree(strat->sevS);
3785 omFree(strat->ecartS);
3786 assume(strat->T==NULL);//omfree(strat->T);
3787 assume(strat->sevT==NULL);//omfree(strat->sevT);
3788 assume(strat->R==NULL);//omfree(strat->R);
3789 omfree(strat->S_2_R);
3790 omfree(strat->fromQ);
3791 idDelete(&strat->Shdl);
3792 SI_RESTORE_OPT1(save1);
3793 if (TEST_OPT_PROT) PrintLn();
3794 return p;
3795}
3796
3797poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3798{
3799 assume(q!=NULL);
3800 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3801
3802// lazy_reduce flags: can be combined by |
3803//#define KSTD_NF_LAZY 1
3804 // do only a reduction of the leading term
3805//#define KSTD_NF_NONORM 4
3806 // only global: avoid normalization, return a multiply of NF
3807 poly p;
3808
3809 //if ((idIs0(F))&&(Q==NULL))
3810 // return pCopy(q); /*F=0*/
3811 //strat->ak = idRankFreeModule(F);
3812 /*- creating temp data structures------------------- -*/
3813 BITSET save1;
3814 SI_SAVE_OPT1(save1);
3816 initBuchMoraCrit(strat);
3817 strat->initEcart = initEcartBBA;
3818 strat->enterS = enterSBba;
3819#ifndef NO_BUCKETS
3821#endif
3822 /*- set S -*/
3823 strat->sl = -1;
3824 /*- init local data struct.---------------------------------------- -*/
3825 /*Shdl=*/initS(F,Q,strat);
3826 /*- compute------------------------------------------------------- -*/
3827 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3828 //{
3829 // for (i=strat->sl;i>=0;i--)
3830 // pNorm(strat->S[i]);
3831 //}
3832 kTest(strat);
3833 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3834 if (BVERBOSE(23)) kDebugPrint(strat);
3835 int max_ind;
3836 p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3837 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3838 {
3839 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3841 {
3842 p = redtailBba_Z(p,max_ind,strat);
3843 }
3844 else if (rField_is_Ring(currRing))
3845 {
3846 p = redtailBba_Ring(p,max_ind,strat);
3847 }
3848 else
3849 {
3850 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3851 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3852 //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3853 }
3854 }
3855 /*- release temp data------------------------------- -*/
3856 assume(strat->L==NULL); /* strat->L unused */
3857 assume(strat->B==NULL); /* strat->B unused */
3858 omFree(strat->sevS);
3859 omFree(strat->ecartS);
3860 assume(strat->T==NULL);//omfree(strat->T);
3861 assume(strat->sevT==NULL);//omfree(strat->sevT);
3862 assume(strat->R==NULL);//omfree(strat->R);
3863 omfree(strat->S_2_R);
3864 omfree(strat->fromQ);
3865 idDelete(&strat->Shdl);
3866 SI_RESTORE_OPT1(save1);
3867 if (TEST_OPT_PROT) PrintLn();
3868 return p;
3869}
3870
3871ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3872{
3873 assume(!idIs0(q));
3874 assume(!(idIs0(F)&&(Q==NULL)));
3875// lazy_reduce flags: can be combined by |
3876//#define KSTD_NF_LAZY 1
3877 // do only a reduction of the leading term
3878//#define KSTD_NF_NONORM 4
3879 // only global: avoid normalization, return a multiply of NF
3880 poly p;
3881 int i;
3882 ideal res;
3883 int max_ind;
3884
3885 //if (idIs0(q))
3886 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3887 //if ((idIs0(F))&&(Q==NULL))
3888 // return idCopy(q); /*F=0*/
3889 //strat->ak = idRankFreeModule(F);
3890 /*- creating temp data structures------------------- -*/
3891 BITSET save1;
3892 SI_SAVE_OPT1(save1);
3894 initBuchMoraCrit(strat);
3895 strat->initEcart = initEcartBBA;
3896#ifdef HAVE_SHIFTBBA
3897 if (rIsLPRing(currRing))
3898 {
3899 strat->enterS = enterSBbaShift;
3900 }
3901 else
3902#endif
3903 {
3904 strat->enterS = enterSBba;
3905 }
3906 /*- set S -*/
3907 strat->sl = -1;
3908#ifndef NO_BUCKETS
3910#endif
3911 /*- init local data struct.---------------------------------------- -*/
3912 /*Shdl=*/initS(F,Q,strat);
3913 /*- compute------------------------------------------------------- -*/
3914 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3915 for (i=IDELEMS(q)-1; i>=0; i--)
3916 {
3917 if (q->m[i]!=NULL)
3918 {
3919 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3920 p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3921 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3922 {
3923 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3925 {
3926 p = redtailBba_Z(p,max_ind,strat);
3927 }
3928 else if (rField_is_Ring(currRing))
3929 {
3930 p = redtailBba_Ring(p,max_ind,strat);
3931 }
3932 else
3933 {
3934 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3935 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3936 }
3937 }
3938 res->m[i]=p;
3939 }
3940 //else
3941 // res->m[i]=NULL;
3942 }
3943 /*- release temp data------------------------------- -*/
3944 assume(strat->L==NULL); /* strat->L unused */
3945 assume(strat->B==NULL); /* strat->B unused */
3946 omFree(strat->sevS);
3947 omFree(strat->ecartS);
3948 assume(strat->T==NULL);//omfree(strat->T);
3949 assume(strat->sevT==NULL);//omfree(strat->sevT);
3950 assume(strat->R==NULL);//omfree(strat->R);
3951 omfree(strat->S_2_R);
3952 omfree(strat->fromQ);
3953 idDelete(&strat->Shdl);
3954 SI_RESTORE_OPT1(save1);
3955 if (TEST_OPT_PROT) PrintLn();
3956 return res;
3957}
3958
3959ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3960{
3961 assume(!idIs0(q));
3962 assume(!(idIs0(F)&&(Q==NULL)));
3963// lazy_reduce flags: can be combined by |
3964//#define KSTD_NF_LAZY 1
3965 // do only a reduction of the leading term
3966//#define KSTD_NF_NONORM 4
3967 // only global: avoid normalization, return a multiply of NF
3968 poly p;
3969 int i;
3970 ideal res;
3971 int max_ind;
3972
3973 //if (idIs0(q))
3974 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3975 //if ((idIs0(F))&&(Q==NULL))
3976 // return idCopy(q); /*F=0*/
3977 //strat->ak = idRankFreeModule(F);
3978 /*- creating temp data structures------------------- -*/
3979 BITSET save1;
3980 SI_SAVE_OPT1(save1);
3982 initBuchMoraCrit(strat);
3983 strat->initEcart = initEcartBBA;
3984 strat->enterS = enterSBba;
3985 /*- set S -*/
3986 strat->sl = -1;
3987#ifndef NO_BUCKETS
3989#endif
3990 /*- init local data struct.---------------------------------------- -*/
3991 /*Shdl=*/initS(F,Q,strat);
3992 /*- compute------------------------------------------------------- -*/
3993 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3994 for (i=IDELEMS(q)-1; i>=0; i--)
3995 {
3996 if (q->m[i]!=NULL)
3997 {
3998 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3999 p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
4000 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4001 {
4002 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4004 {
4005 p = redtailBba_Z(p,max_ind,strat);
4006 }
4007 else if (rField_is_Ring(currRing))
4008 {
4009 p = redtailBba_Ring(p,max_ind,strat);
4010 }
4011 else
4012 {
4013 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4014 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4015 }
4016 }
4017 res->m[i]=p;
4018 }
4019 //else
4020 // res->m[i]=NULL;
4021 }
4022 /*- release temp data------------------------------- -*/
4023 assume(strat->L==NULL); /* strat->L unused */
4024 assume(strat->B==NULL); /* strat->B unused */
4025 omFree(strat->sevS);
4026 omFree(strat->ecartS);
4027 assume(strat->T==NULL);//omfree(strat->T);
4028 assume(strat->sevT==NULL);//omfree(strat->sevT);
4029 assume(strat->R==NULL);//omfree(strat->R);
4030 omfree(strat->S_2_R);
4031 omfree(strat->fromQ);
4032 idDelete(&strat->Shdl);
4033 SI_RESTORE_OPT1(save1);
4034 if (TEST_OPT_PROT) PrintLn();
4035 return res;
4036}
4037
4038#if F5C
4039/*********************************************************************
4040* interrreduction step of the signature-based algorithm:
4041* 1. all strat->S are interpreted as new critical pairs
4042* 2. those pairs need to be completely reduced by the usual (non sig-
4043* safe) reduction process (including tail reductions)
4044* 3. strat->S and strat->T are completely new computed in these steps
4045********************************************************************/
4046void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
4047 int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
4048 intvec *w,intvec *hilb )
4049{
4050 int Ll_old, red_result = 1;
4051 int pos = 0;
4052 hilbeledeg=1;
4053 hilbcount=0;
4054 minimcnt=0;
4055 srmax = 0; // strat->sl is 0 at this point
4056 reduc = olddeg = lrmax = 0;
4057 // we cannot use strat->T anymore
4058 //cleanT(strat);
4059 //strat->tl = -1;
4060 Ll_old = strat->Ll;
4061 while (strat->tl >= 0)
4062 {
4063 if(!strat->T[strat->tl].is_redundant)
4064 {
4065 LObject h;
4066 h.p = strat->T[strat->tl].p;
4067 h.tailRing = strat->T[strat->tl].tailRing;
4068 h.t_p = strat->T[strat->tl].t_p;
4069 if (h.p!=NULL)
4070 {
4071 if (currRing->OrdSgn==-1)
4072 {
4073 cancelunit(&h);
4074 deleteHC(&h, strat);
4075 }
4076 if (h.p!=NULL)
4077 {
4079 {
4080 h.pCleardenom(); // also does remove Content
4081 }
4082 else
4083 {
4084 h.pNorm();
4085 }
4086 strat->initEcart(&h);
4088 pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4089 else
4090 pos = strat->Ll+1;
4091 h.sev = pGetShortExpVector(h.p);
4092 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4093 }
4094 }
4095 }
4096 strat->tl--;
4097 }
4098 strat->sl = -1;
4099#if 0
4100//#ifdef HAVE_TAIL_RING
4101 if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4103#endif
4104 //enterpairs(pOne(),0,0,-1,strat,strat->tl);
4105 //strat->sl = -1;
4106 /* picks the last element from the lazyset L */
4107 while (strat->Ll>Ll_old)
4108 {
4109 strat->P = strat->L[strat->Ll];
4110 strat->Ll--;
4111//#if 1
4112#ifdef DEBUGF5
4113 PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4114 PrintS("-------------------------------------------------\n");
4115 pWrite(pHead(strat->P.p));
4116 pWrite(pHead(strat->P.p1));
4117 pWrite(pHead(strat->P.p2));
4118 printf("%d\n",strat->tl);
4119 PrintS("-------------------------------------------------\n");
4120#endif
4121 if (pNext(strat->P.p) == strat->tail)
4122 {
4123 // deletes the short spoly
4125 pLmDelete(strat->P.p);
4126 else
4127 pLmFree(strat->P.p);
4128
4129 // TODO: needs some masking
4130 // TODO: masking needs to vanish once the signature
4131 // sutff is completely implemented
4132 strat->P.p = NULL;
4133 poly m1 = NULL, m2 = NULL;
4134
4135 // check that spoly creation is ok
4136 while (strat->tailRing != currRing &&
4137 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4138 {
4139 assume(m1 == NULL && m2 == NULL);
4140 // if not, change to a ring where exponents are at least
4141 // large enough
4142 if (!kStratChangeTailRing(strat))
4143 {
4144 WerrorS("OVERFLOW...");
4145 break;
4146 }
4147 }
4148 // create the real one
4149 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4150 strat->tailRing, m1, m2, strat->R);
4151 }
4152 else if (strat->P.p1 == NULL)
4153 {
4154 if (strat->minim > 0)
4155 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4156 // for input polys, prepare reduction
4158 strat->P.PrepareRed(strat->use_buckets);
4159 }
4160
4161 if (strat->P.p == NULL && strat->P.t_p == NULL)
4162 {
4163 red_result = 0;
4164 }
4165 else
4166 {
4167 if (TEST_OPT_PROT)
4168 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4169 &olddeg,&reduc,strat, red_result);
4170
4171#ifdef DEBUGF5
4172 PrintS("Poly before red: ");
4173 pWrite(strat->P.p);
4174#endif
4175 /* complete reduction of the element chosen from L */
4176 red_result = strat->red2(&strat->P,strat);
4177 if (errorreported) break;
4178 }
4179
4180 if (strat->overflow)
4181 {
4182 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4183 }
4184
4185 // reduction to non-zero new poly
4186 if (red_result == 1)
4187 {
4188 // get the polynomial (canonicalize bucket, make sure P.p is set)
4189 strat->P.GetP(strat->lmBin);
4190 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4191 // but now, for entering S, T, we reset it
4192 // in the inhomogeneous case: FDeg == pFDeg
4193 if (strat->homog) strat->initEcart(&(strat->P));
4194
4195 /* statistic */
4196 if (TEST_OPT_PROT) PrintS("s");
4197 int pos;
4198 #if 1
4200 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4201 else
4202 pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4203 #else
4204 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4205 #endif
4206 // reduce the tail and normalize poly
4207 // in the ring case we cannot expect LC(f) = 1,
4208#if F5CTAILRED
4209 BOOLEAN withT = TRUE;
4211 {
4212 strat->P.pCleardenom();
4214 {
4215 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4216 strat->P.pCleardenom();
4217 }
4218 }
4219 else
4220 {
4221 strat->P.pNorm();
4223 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4224 }
4225#endif
4226#ifdef KDEBUG
4227 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4228#endif /* KDEBUG */
4229
4230 // min_std stuff
4231 if ((strat->P.p1==NULL) && (strat->minim>0))
4232 {
4233 if (strat->minim==1)
4234 {
4235 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4236 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4237 }
4238 else
4239 {
4240 strat->M->m[minimcnt]=strat->P.p2;
4241 strat->P.p2=NULL;
4242 }
4243 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4244 pNext(strat->M->m[minimcnt])
4245 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4246 strat->tailRing, currRing,
4247 currRing->PolyBin);
4248 minimcnt++;
4249 }
4250
4251 // enter into S, L, and T
4252 // here we need to recompute new signatures, but those are trivial ones
4253 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4254 {
4255 enterT(strat->P, strat);
4256 // posInS only depends on the leading term
4257 strat->enterS(strat->P, pos, strat, strat->tl);
4258//#if 1
4259#ifdef DEBUGF5
4260 PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4261 pWrite(pHead(strat->S[strat->sl]));
4262 pWrite(strat->sig[strat->sl]);
4263#endif
4264 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4265 }
4266 // Print("[%d]",hilbeledeg);
4267 kDeleteLcm(&strat->P);
4268 if (strat->sl>srmax) srmax = strat->sl;
4269 }
4270 else
4271 {
4272 // adds signature of the zero reduction to
4273 // strat->syz. This is the leading term of
4274 // syzygy and can be used in syzCriterion()
4275 // the signature is added if and only if the
4276 // pair was not detected by the rewritten criterion in strat->red = redSig
4277 if (strat->P.p1 == NULL && strat->minim > 0)
4278 {
4279 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4280 }
4281 }
4282
4283#ifdef KDEBUG
4284 memset(&(strat->P), 0, sizeof(strat->P));
4285#endif /* KDEBUG */
4286 }
4287 int cc = 0;
4288 while (cc<strat->tl+1)
4289 {
4290 strat->T[cc].sig = pOne();
4291 p_SetComp(strat->T[cc].sig,cc+1,currRing);
4292 strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4293 strat->sig[cc] = strat->T[cc].sig;
4294 strat->sevSig[cc] = strat->T[cc].sevSig;
4295 strat->T[cc].is_sigsafe = TRUE;
4296 cc++;
4297 }
4298 strat->max_lower_index = strat->tl;
4299 // set current signature index of upcoming iteration step
4300 // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4301 // the corresponding syzygy rules correctly
4302 strat->currIdx = cc+1;
4303 for (int cd=strat->Ll; cd>=0; cd--)
4304 {
4305 p_SetComp(strat->L[cd].sig,cc+1,currRing);
4306 cc++;
4307 }
4308 for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4309 strat->Shdl->m[cc] = NULL;
4310 #if 0
4311 printf("\nAfter f5c sorting\n");
4312 for(int i=0;i<=strat->sl;i++)
4313 pWrite(pHead(strat->S[i]));
4314 getchar();
4315 #endif
4316//#if 1
4317#if DEBUGF5
4318 PrintS("------------------- STRAT S ---------------------\n");
4319 cc = 0;
4320 while (cc<strat->tl+1)
4321 {
4322 pWrite(pHead(strat->S[cc]));
4323 pWrite(strat->sig[cc]);
4324 printf("- - - - - -\n");
4325 cc++;
4326 }
4327 PrintS("-------------------------------------------------\n");
4328 PrintS("------------------- STRAT T ---------------------\n");
4329 cc = 0;
4330 while (cc<strat->tl+1)
4331 {
4332 pWrite(pHead(strat->T[cc].p));
4333 pWrite(strat->T[cc].sig);
4334 printf("- - - - - -\n");
4335 cc++;
4336 }
4337 PrintS("-------------------------------------------------\n");
4338 PrintS("------------------- STRAT L ---------------------\n");
4339 cc = 0;
4340 while (cc<strat->Ll+1)
4341 {
4342 pWrite(pHead(strat->L[cc].p));
4343 pWrite(pHead(strat->L[cc].p1));
4344 pWrite(pHead(strat->L[cc].p2));
4345 pWrite(strat->L[cc].sig);
4346 printf("- - - - - -\n");
4347 cc++;
4348 }
4349 PrintS("-------------------------------------------------\n");
4350 printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4351#endif
4352
4353}
4354#endif
4355
4356/* shiftgb stuff */
4357#ifdef HAVE_SHIFTBBA
4358ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
4359{
4360 int red_result = 1;
4361 int olddeg,reduc;
4362 int hilbeledeg=1,hilbcount=0,minimcnt=0;
4363 BOOLEAN withT = TRUE; // currently only T contains the shifts
4364 BITSET save;
4365 SI_SAVE_OPT1(save);
4366
4367 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4369 initBuchMoraPosRing(strat);
4370 else
4371 initBuchMoraPos(strat);
4372 initHilbCrit(F,Q,&hilb,strat);
4373 initBba(strat);
4374 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4375 /*Shdl=*/initBuchMora(F, Q,strat);
4376 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4377 reduc = olddeg = 0;
4378
4379#ifndef NO_BUCKETS
4381 strat->use_buckets = 1;
4382#endif
4383 // redtailBBa against T for inhomogenous input
4384 // if (!TEST_OPT_OLDSTD)
4385 // withT = ! strat->homog;
4386
4387 // strat->posInT = posInT_pLength;
4388 kTest_TS(strat);
4389
4390#ifdef HAVE_TAIL_RING
4391 // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4392 // kStratInitChangeTailRing(strat);
4393 strat->tailRing=currRing;
4394#endif
4395 if (BVERBOSE(23))
4396 {
4397 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4398 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4399 kDebugPrint(strat);
4400 }
4401
4402#ifdef KDEBUG
4403 //kDebugPrint(strat);
4404#endif
4405 /* compute------------------------------------------------------- */
4406 while (strat->Ll >= 0)
4407 {
4408 #ifdef KDEBUG
4409 if (TEST_OPT_DEBUG) messageSets(strat);
4410 #endif
4411 if (siCntrlc)
4412 {
4413 while (strat->Ll >= 0)
4414 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4415 strat->noClearS=TRUE;
4416 }
4418 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4419 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4420 {
4421 /*
4422 *stops computation if
4423 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4424 *a predefined number Kstd1_deg
4425 */
4426 while ((strat->Ll >= 0)
4427 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4428 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4429 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4430 )
4431 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4432 if (strat->Ll<0) break;
4433 else strat->noClearS=TRUE;
4434 }
4435 if (strat->Ll== 0) strat->interpt=TRUE;
4436 /* picks the last element from the lazyset L */
4437 strat->P = strat->L[strat->Ll];
4438 strat->Ll--;
4439
4440 if (pNext(strat->P.p) == strat->tail)
4441 {
4442 // deletes the short spoly
4444 pLmDelete(strat->P.p);
4445 else
4446 pLmFree(strat->P.p);
4447 strat->P.p = NULL;
4448 poly m1 = NULL, m2 = NULL;
4449
4450 // check that spoly creation is ok
4451 while (strat->tailRing != currRing &&
4452 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4453 {
4454 assume(m1 == NULL && m2 == NULL);
4455 // if not, change to a ring where exponents are at least
4456 // large enough
4457 if (!kStratChangeTailRing(strat))
4458 {
4459 WerrorS("OVERFLOW...");
4460 break;
4461 }
4462 }
4463 // create the real one
4464 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4465 strat->tailRing, m1, m2, strat->R);
4466 }
4467 else if (strat->P.p1 == NULL)
4468 {
4469 if (strat->minim > 0)
4470 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4471 // for input polys, prepare reduction
4472 strat->P.PrepareRed(strat->use_buckets);
4473 }
4474
4475 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4476 {
4477 red_result = 0;
4478 }
4479 else
4480 {
4481 if (TEST_OPT_PROT)
4482 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4483 &olddeg,&reduc,strat, red_result);
4484
4485 /* reduction of the element chosen from L */
4486 red_result = strat->red(&strat->P,strat);
4487 if (errorreported) break;
4488 }
4489
4490 if (strat->overflow)
4491 {
4492 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4493 }
4494
4495 // reduction to non-zero new poly
4496 if (red_result == 1)
4497 {
4498 // get the polynomial (canonicalize bucket, make sure P.p is set)
4499 strat->P.GetP(strat->lmBin);
4500 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4501 // but now, for entering S, T, we reset it
4502 // in the inhomogeneous case: FDeg == pFDeg
4503 if (strat->homog) strat->initEcart(&(strat->P));
4504
4505 /* statistic */
4506 if (TEST_OPT_PROT) PrintS("s");
4507
4508 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4509
4510 // reduce the tail and normalize poly
4511 // in the ring case we cannot expect LC(f) = 1,
4512 strat->redTailChange=FALSE;
4513
4514 /* if we are computing over Z we always want to try and cut down
4515 * the coefficients in the tail terms */
4517 {
4518 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4519 }
4520
4522 {
4523 strat->P.pCleardenom();
4525 {
4526 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4527 strat->P.pCleardenom();
4528 if (strat->redTailChange)
4529 {
4530 strat->P.t_p=NULL;
4531 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4532 }
4533 }
4534 }
4535 else
4536 {
4537 strat->P.pNorm();
4539 {
4540 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4541 if (strat->redTailChange)
4542 {
4543 strat->P.t_p=NULL;
4544 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4545 }
4546 }
4547 }
4548
4549#ifdef KDEBUG
4550 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4551#endif /* KDEBUG */
4552
4553 // min_std stuff
4554 if ((strat->P.p1==NULL) && (strat->minim>0))
4555 {
4556 if (strat->minim==1)
4557 {
4558 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4559 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4560 }
4561 else
4562 {
4563 strat->M->m[minimcnt]=strat->P.p2;
4564 strat->P.p2=NULL;
4565 }
4566 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4567 pNext(strat->M->m[minimcnt])
4568 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4569 strat->tailRing, currRing,
4570 currRing->PolyBin);
4571 minimcnt++;
4572 }
4573
4574
4575 // enter into S, L, and T
4576 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4577 {
4578 enterT(strat->P, strat);
4579 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4580 // posInS only depends on the leading term
4581 strat->enterS(strat->P, pos, strat, strat->tl);
4582 if (!strat->rightGB)
4583 enterTShift(strat->P, strat);
4584 }
4585
4586 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4587// Print("[%d]",hilbeledeg);
4588 kDeleteLcm(&strat->P);
4589 if (strat->s_poly!=NULL)
4590 {
4591 // the only valid entries are: strat->P.p,
4592 // strat->tailRing (read-only, keep it)
4593 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4594 if (strat->s_poly(strat))
4595 {
4596 // we are called AFTER enterS, i.e. if we change P
4597 // we have to add it also to S/T
4598 // and add pairs
4599 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4600 enterT(strat->P, strat);
4601 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4602 strat->enterS(strat->P, pos, strat, strat->tl);
4603 if (!strat->rightGB)
4604 enterTShift(strat->P,strat);
4605 }
4606 }
4607 }
4608 else if (strat->P.p1 == NULL && strat->minim > 0)
4609 {
4610 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4611 }
4612#ifdef KDEBUG
4613 memset(&(strat->P), 0, sizeof(strat->P));
4614#endif /* KDEBUG */
4615 kTest_TS(strat);
4616 }
4617#ifdef KDEBUG
4618 if (TEST_OPT_DEBUG) messageSets(strat);
4619#endif /* KDEBUG */
4620 /* shift case: look for elt's in S such that they are divisible by elt in T */
4621 if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4622 {
4624 {
4625 for (int k = 0; k <= strat->sl; ++k)
4626 {
4627 if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4628 for (int j = 0; j<=strat->tl; ++j)
4629 {
4630 if (strat->T[j].p!=NULL)
4631 {
4632 // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4633 assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4634 assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4635 if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4636 {
4637 if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4638 { // check whether LM is different
4639 deleteInS(k, strat);
4640 --k;
4641 break;
4642 }
4643 }
4644 }
4645 }
4646 }
4647 }
4648 }
4649 /* complete reduction of the standard basis--------- */
4650 if (TEST_OPT_REDSB)
4651 {
4652 completeReduce(strat, TRUE); //shift: withT = TRUE
4653 if (strat->completeReduce_retry)
4654 {
4655 // completeReduce needed larger exponents, retry
4656 // to reduce with S (instead of T)
4657 // and in currRing (instead of strat->tailRing)
4658#ifdef HAVE_TAIL_RING
4659 if(currRing->bitmask>strat->tailRing->bitmask)
4660 {
4662 cleanT(strat);strat->tailRing=currRing;
4663 int i;
4664 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4665 WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4666 completeReduce(strat);
4667 }
4668 if (strat->completeReduce_retry)
4669#endif
4670 Werror("exponent bound is %ld",currRing->bitmask);
4671 }
4672 }
4673 else if (TEST_OPT_PROT) PrintLn();
4674
4675 /* release temp data-------------------------------- */
4676 exitBuchMora(strat);
4677 /* postprocessing for GB over ZZ --------------------*/
4678 if (!errorreported)
4679 {
4681 {
4682 for(int i = 0;i<=strat->sl;i++)
4683 {
4684 if(!nGreaterZero(pGetCoeff(strat->S[i])))
4685 {
4686 strat->S[i] = pNeg(strat->S[i]);
4687 }
4688 }
4689 finalReduceByMon(strat);
4690 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4691 {
4692 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4693 {
4694 strat->S[i] = pNeg(strat->Shdl->m[i]);
4695 }
4696 }
4697 }
4698 //else if (rField_is_Ring(currRing))
4699 // finalReduceByMon(strat);
4700 }
4701// if (TEST_OPT_WEIGHTM)
4702// {
4703// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4704// if (ecartWeights)
4705// {
4706// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4707// ecartWeights=NULL;
4708// }
4709// }
4710 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4711 SI_RESTORE_OPT1(save);
4712 /* postprocessing for GB over Q-rings ------------------*/
4713 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4714
4715 idTest(strat->Shdl);
4716
4717 return (strat->Shdl);
4718}
4719#endif
4720
4721#ifdef HAVE_SHIFTBBA
4722ideal rightgb(ideal F, ideal Q)
4723{
4725 assume(idIsInV(F));
4726 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4727 idSkipZeroes(RS); // is this even necessary?
4728 assume(idIsInV(RS));
4729 return(RS);
4730}
4731#endif
4732
4733/*2
4734*reduces h with elements from T choosing the first possible
4735* element in t with respect to the given pDivisibleBy
4736*/
4737#ifdef HAVE_SHIFTBBA
4739{
4740 if (h->IsNull()) return 0;
4741
4742 int at, reddeg,d;
4743 int pass = 0;
4744 int j = 0;
4745
4746 if (! strat->homog)
4747 {
4748 d = h->GetpFDeg() + h->ecart;
4749 reddeg = strat->LazyDegree+d;
4750 }
4751 h->SetShortExpVector();
4752 loop
4753 {
4754 j = kFindDivisibleByInT(strat, h);
4755 if (j < 0)
4756 {
4757 h->SetDegStuffReturnLDeg(strat->LDegLast);
4758 return 1;
4759 }
4760
4762 strat->T[j].pNorm();
4763#ifdef KDEBUG
4764 if (TEST_OPT_DEBUG)
4765 {
4766 PrintS("reduce ");
4767 h->wrp();
4768 PrintS(" with ");
4769 strat->T[j].wrp();
4770 }
4771#endif
4772 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
4773
4774#ifdef KDEBUG
4775 if (TEST_OPT_DEBUG)
4776 {
4777 PrintS("\nto ");
4778 wrp(h->p);
4779 PrintLn();
4780 }
4781#endif
4782 if (h->IsNull())
4783 {
4784 kDeleteLcm(h);
4785 h->Clear();
4786 return 0;
4787 }
4788 h->SetShortExpVector();
4789
4790#if 0
4791 if ((strat->syzComp!=0) && !strat->honey)
4792 {
4793 if ((strat->syzComp>0) &&
4794 (h->Comp() > strat->syzComp))
4795 {
4796 assume(h->MinComp() > strat->syzComp);
4797#ifdef KDEBUG
4798 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4799#endif
4800 if (strat->homog)
4801 h->SetDegStuffReturnLDeg(strat->LDegLast);
4802 return -2;
4803 }
4804 }
4805#endif
4806 if (!strat->homog)
4807 {
4808 if (!TEST_OPT_OLDSTD && strat->honey)
4809 {
4810 h->SetpFDeg();
4811 if (strat->T[j].ecart <= h->ecart)
4812 h->ecart = d - h->GetpFDeg();
4813 else
4814 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4815
4816 d = h->GetpFDeg() + h->ecart;
4817 }
4818 else
4819 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4820 /*- try to reduce the s-polynomial -*/
4821 pass++;
4822 /*
4823 *test whether the polynomial should go to the lazyset L
4824 *-if the degree jumps
4825 *-if the number of pre-defined reductions jumps
4826 */
4827 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4828 && ((d >= reddeg) || (pass > strat->LazyPass)))
4829 {
4830 h->SetLmCurrRing();
4831 if (strat->posInLDependsOnLength)
4832 h->SetLength(strat->length_pLength);
4833 at = strat->posInL(strat->L,strat->Ll,h,strat);
4834 if (at <= strat->Ll)
4835 {
4836 //int dummy=strat->sl;
4837 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4838 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4839 if (kFindDivisibleByInT(strat, h) < 0)
4840 return 1;
4841 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4842#ifdef KDEBUG
4843 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4844#endif
4845 h->Clear();
4846 return -1;
4847 }
4848 }
4849 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4850 {
4851 reddeg = d+1;
4852 Print(".%d",d);mflush();
4853 }
4854 }
4855 }
4856}
4857#endif
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
#define UNLIKELY(X)
Definition: auxiliary.h:404
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
Definition: intvec.h:23
KINLINE poly kNoetherTail()
Definition: kInline.h:66
unsigned long * sevSyz
Definition: kutil.h:323
bool sigdrop
Definition: kutil.h:359
int syzComp
Definition: kutil.h:354
int * S_2_R
Definition: kutil.h:342
ring tailRing
Definition: kutil.h:343
char noTailReduction
Definition: kutil.h:378
int currIdx
Definition: kutil.h:317
int nrsyzcrit
Definition: kutil.h:360
int nrrewcrit
Definition: kutil.h:361
int Ll
Definition: kutil.h:351
TSet T
Definition: kutil.h:326
omBin lmBin
Definition: kutil.h:344
int syzmax
Definition: kutil.h:349
intset ecartS
Definition: kutil.h:309
char honey
Definition: kutil.h:377
char rightGB
Definition: kutil.h:369
polyset S
Definition: kutil.h:306
int minim
Definition: kutil.h:357
poly kNoether
Definition: kutil.h:329
LSet B
Definition: kutil.h:328
int ak
Definition: kutil.h:353
TObject ** R
Definition: kutil.h:340
ideal M
Definition: kutil.h:305
int tl
Definition: kutil.h:350
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:279
unsigned long * sevT
Definition: kutil.h:325
unsigned long * sevSig
Definition: kutil.h:324
int max_lower_index
Definition: kutil.h:318
poly tail
Definition: kutil.h:334
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:284
int blockred
Definition: kutil.h:364
ideal Shdl
Definition: kutil.h:303
int syzl
Definition: kutil.h:349
unsigned sbaOrder
Definition: kutil.h:316
int blockredmax
Definition: kutil.h:365
polyset sig
Definition: kutil.h:308
polyset syz
Definition: kutil.h:307
char LDegLast
Definition: kutil.h:385
pShallowCopyDeleteProc p_shallow_copy_delete
Definition: kutil.h:338
intset fromQ
Definition: kutil.h:321
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:286
char newt
Definition: kutil.h:401
char use_buckets
Definition: kutil.h:383
char interpt
Definition: kutil.h:371
char redTailChange
Definition: kutil.h:399
char fromT
Definition: kutil.h:379
char completeReduce_retry
Definition: kutil.h:403
void(* initEcart)(TObject *L)
Definition: kutil.h:280
LObject P
Definition: kutil.h:302
char noClearS
Definition: kutil.h:402
int Lmax
Definition: kutil.h:351
int LazyPass
Definition: kutil.h:353
char overflow
Definition: kutil.h:404
LSet L
Definition: kutil.h:327
char length_pLength
Definition: kutil.h:387
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:281
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:278
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:294
int sl
Definition: kutil.h:348
int sbaEnterS
Definition: kutil.h:362
int LazyDegree
Definition: kutil.h:353
char posInLDependsOnLength
Definition: kutil.h:389
unsigned long * sevS
Definition: kutil.h:322
char homog
Definition: kutil.h:372
s_poly_proc_t s_poly
Definition: kutil.h:300
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
Definition: coeffs.h:664
static FORCE_INLINE number n_EucNorm(number a, const coeffs r)
Definition: coeffs.h:675
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition: coeffs.h:681
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:511
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition: coeffs.h:444
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition: coeffs.h:753
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
#define Print
Definition: emacs.cc:80
#define WarnS
Definition: emacs.cc:78
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
CFList tmp1
Definition: facFqBivar.cc:72
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
void sort(CFArray &A, int l=0)
quick sort A
VAR short errorreported
Definition: feFopen.cc:23
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define VAR
Definition: globaldefs.h:5
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
#define idTest(id)
Definition: ideals.h:47
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:184
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR jList * T
Definition: janet.cc:30
STATIC_VAR Poly * h
Definition: janet.cc:971
STATIC_VAR jList * Q
Definition: janet.cc:30
KINLINE poly redtailBba_Ring(poly p, int pos, kStrategy strat)
Definition: kInline.h:1236
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1223
KINLINE poly redtailBbaBound(poly p, int pos, kStrategy strat, int bound, BOOLEAN normalize)
Definition: kInline.h:1229
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition: kInline.h:1248
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
Definition: kInline.h:1241
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition: kbuckets.cc:197
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1085
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:506
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
Definition: khstd.cc:28
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:458
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:1185
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat)
Definition: kspoly.cc:187
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:719
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:925
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:44
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:325
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2911
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3743
void initBba(kStrategy strat)
Definition: kstd1.cc:1676
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1734
#define KSTD_NF_LAZY
Definition: kstd1.h:17
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
#define KSTD_NF_NONORM
Definition: kstd1.h:21
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:673
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:559
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4738
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start)
Definition: kstd2.cc:86
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start)
Definition: kstd2.cc:209
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition: kstd2.cc:404
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject *L)
tests if T[0] divides the leading monomial of L, returns -1 if not
Definition: kstd2.cc:142
poly redNFBound(poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
Definition: kstd2.cc:2271
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3715
VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd2.cc:83
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1905
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:473
static long ind_fact_2(long arg)
Definition: kstd2.cc:544
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:938
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2749
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2390
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1698
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1328
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kstd2.cc:1578
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition: kstd2.cc:1122
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2142
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1160
static long ind2(long arg)
Definition: kstd2.cc:532
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11833
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, intvec *hilb)
Definition: kstd2.cc:4046
VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kstd2.cc:82
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3797
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:831
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:290
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4358
ideal rightgb(ideal F, ideal Q)
Definition: kstd2.cc:4722
void initSbaPos(kStrategy strat)
Definition: kutil.cc:10184
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7784
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10073
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9652
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9450
void enterTShift(LObject p, kStrategy strat, int atT)
Definition: kutil.cc:13450
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1036
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition: kutil.cc:7005
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1097
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4613
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1360
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4587
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7452
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9730
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition: kutil.cc:4864
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4569
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9900
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7907
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11294
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
Definition: kutil.cc:11415
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:11036
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13420
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition: kutil.cc:950
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10158
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:7838
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4763
void initSyzRules(kStrategy strat)
Definition: kutil.cc:8248
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10286
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10807
void cleanT(kStrategy strat)
Definition: kutil.cc:569
int posInSyz(const kStrategy strat, poly sig)
Definition: kutil.cc:6018
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition: kutil.cc:9359
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:294
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10401
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4556
void exitSba(kStrategy strat)
Definition: kutil.cc:10361
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1295
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11387
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9748
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10613
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9986
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:11112
void messageSets(kStrategy strat)
Definition: kutil.cc:7857
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1163
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition: kutil.cc:1780
int posInLF5CRing(const LSet set, int start, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:6136
void initEcartBBA(TObject *h)
Definition: kutil.cc:1392
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9201
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7825
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
Definition: kutil.cc:4941
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11201
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9101
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9813
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:373
TObject * TSet
Definition: kutil.h:59
#define setmaxTinc
Definition: kutil.h:34
#define REDNF_CANONICALIZE
Definition: kutil.h:37
LObject * LSet
Definition: kutil.h:60
static void kDeleteLcm(LObject *P)
Definition: kutil.h:886
#define KINLINE
Definition: kutil.h:49
#define RED_CANONICALIZE
Definition: kutil.h:36
class sTObject TObject
Definition: kutil.h:57
#define REDTAIL_CANONICALIZE
Definition: kutil.h:38
class sLObject LObject
Definition: kutil.h:58
#define help
Definition: libparse.cc:1230
static void nc_kBucketPolyRed_NF(kBucket_pt b, poly p, number *c)
Definition: nc.h:275
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
#define assume(x)
Definition: mod2.h:389
#define p_GetComp(p, r)
Definition: monomials.h:64
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
#define __p_GetComp(p, r)
Definition: monomials.h:63
#define pAssume(cond)
Definition: monomials.h:90
#define nDelete(n)
Definition: numbers.h:16
#define nIsZero(n)
Definition: numbers.h:19
#define nCopy(n)
Definition: numbers.h:15
#define nGreaterZero(n)
Definition: numbers.h:27
#define nIsOne(n)
Definition: numbers.h:25
#define nNormalize(n)
Definition: numbers.h:30
#define nInit(i)
Definition: numbers.h:24
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omRealloc0Size(addr, o_size, size)
Definition: omAllocDecl.h:221
#define NULL
Definition: omList.c:12
VAR BOOLEAN siCntrlc
Definition: options.c:14
VAR unsigned si_opt_1
Definition: options.c:5
#define OPT_INTSTRATEGY
Definition: options.h:93
#define TEST_OPT_IDLIFT
Definition: options.h:130
#define TEST_OPT_INTSTRATEGY
Definition: options.h:111
#define BVERBOSE(a)
Definition: options.h:35
#define TEST_OPT_REDTAIL
Definition: options.h:117
#define OPT_REDTAIL
Definition: options.h:92
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define TEST_OPT_OLDSTD
Definition: options.h:124
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:105
#define TEST_OPT_DEGBOUND
Definition: options.h:114
#define TEST_OPT_SB_1
Definition: options.h:120
#define TEST_OPT_LENGTH
Definition: options.h:132
#define TEST_OPT_PROT
Definition: options.h:104
#define TEST_OPT_REDTHROUGH
Definition: options.h:123
#define TEST_OPT_IDELIM
Definition: options.h:131
#define TEST_OPT_DEBUG
Definition: options.h:109
#define TEST_OPT_REDTAIL_SYZ
Definition: options.h:118
#define TEST_OPT_CONTENTSB
Definition: options.h:128
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:106
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1297
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4897
poly p_One(const ring r)
Definition: p_polys.cc:1313
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1469
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3812
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:938
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1116
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1413
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1725
static void p_SetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1546
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:490
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:249
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:235
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1582
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1931
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:471
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1897
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:903
static unsigned pLength(poly a)
Definition: p_polys.h:191
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1522
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1053
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:757
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:848
void rChangeCurrRing(ring r)
Definition: polys.cc:15
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatiblity layer for legacy polynomial operations (over currRing)
#define pLtCmp(p, q)
Definition: polys.h:123
#define pDelete(p_ptr)
Definition: polys.h:186
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pNeg(p)
Definition: polys.h:198
#define pGetComp(p)
Component.
Definition: polys.h:37
void pNorm(poly p)
Definition: polys.h:363
#define pJet(p, m)
Definition: polys.h:368
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition: polys.h:146
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
void wrp(poly p)
Definition: polys.h:310
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition: polys.h:70
void pWrite(poly p)
Definition: polys.h:308
#define pNormalize(p)
Definition: polys.h:317
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
#define pSize(p)
Definition: polys.h:318
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define pOne()
Definition: polys.h:315
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:248
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:261
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
void Werror(const char *fmt,...)
Definition: reporter.cc:189
#define mflush()
Definition: reporter.h:58
void rWrite(ring r, BOOLEAN details)
Definition: ring.cc:226
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:510
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static BOOLEAN rField_is_Zn(const ring r)
Definition: ring.h:513
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:761
#define rField_is_Ring(R)
Definition: ring.h:486
#define idIsInV(I)
Definition: shiftop.h:49
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23
@ testHomog
Definition: structs.h:38
#define BITSET
Definition: structs.h:16
#define loop
Definition: structs.h:75
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
int gcd(int a, int b)
Definition: walkSupport.cc:836