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