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