My Project
Loading...
Searching...
No Matches
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 }
1219 #if 0 // red is redLiftstd if OPT_IDLIFT
1221 {
1222 if (h->p!=NULL)
1223 {
1224 if(p_GetComp(h->p,currRing)>strat->syzComp)
1225 {
1226 h->Delete();
1227 return 0;
1228 }
1229 }
1230 else if (h->t_p!=NULL)
1231 {
1232 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1233 {
1234 h->Delete();
1235 return 0;
1236 }
1237 }
1238 }
1239 #endif
1240 #if 0
1241 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1242 {
1243 if (h->p!=NULL)
1244 {
1245 if(p_GetComp(h->p,currRing)>strat->syzComp)
1246 {
1247 return 1;
1248 }
1249 }
1250 else if (h->t_p!=NULL)
1251 {
1252 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1253 {
1254 return 1;
1255 }
1256 }
1257 }
1258 #endif
1259 h->SetShortExpVector();
1260 /*
1261 * try to reduce the s-polynomial h
1262 *test first whether h should go to the lazyset L
1263 *-if the degree jumps
1264 *-if the number of pre-defined reductions jumps
1265 */
1266 cnt--;
1267 pass++;
1268 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1269 {
1270 h->SetLmCurrRing();
1271 at = strat->posInL(strat->L,strat->Ll,h,strat);
1272 if (at <= strat->Ll)
1273 {
1274#ifdef HAVE_SHIFTBBA
1275 if (rIsLPRing(currRing))
1276 {
1277 if (kFindDivisibleByInT(strat, h) < 0)
1278 return 1;
1279 }
1280 else
1281#endif
1282 {
1283 int dummy=strat->sl;
1284 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1285 return 1;
1286 }
1287 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1288#ifdef KDEBUG
1289 if (TEST_OPT_DEBUG)
1290 Print(" lazy: -> L%d\n",at);
1291#endif
1292 h->Clear();
1293 return -1;
1294 }
1295 }
1296 else if (UNLIKELY(cnt==0))
1297 {
1298 h->CanonicalizeP();
1299 cnt=RED_CANONICALIZE;
1300 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
1301 }
1302 }
1303}
1304
1306{
1307 BOOLEAN ret;
1308 number coef;
1309 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1311 Red->HeadNormalize();
1312 /*
1313 printf("------------------------\n");
1314 pWrite(Red->GetLmCurrRing());
1315 */
1317 ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1318 else
1319 ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1320 if (!ret)
1321 {
1322 if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1323 {
1324 PR->Mult_nn(coef);
1325 // HANNES: mark for Normalize
1326 }
1327 n_Delete(&coef, currRing->cf);
1328 }
1329 return ret;
1330}
1331
1332/*2
1333* reduction procedure for signature-based standard
1334* basis algorithms:
1335* all reductions have to be sig-safe!
1336*
1337* 2 is returned if and only if the pair is rejected by the rewritten criterion
1338* at exactly this point of the computations. This is the last possible point
1339* such a check can be done => checks with the biggest set of available
1340* signatures
1341*/
1342
1344{
1345 if (strat->tl<0) return 1;
1346 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1347 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1348 assume(h->FDeg == h->pFDeg());
1349//#if 1
1350#ifdef DEBUGF5
1351 PrintS("------- IN REDSIG -------\n");
1352 Print("p: ");
1353 pWrite(pHead(h->p));
1354 PrintS("p1: ");
1355 pWrite(pHead(h->p1));
1356 PrintS("p2: ");
1357 pWrite(pHead(h->p2));
1358 PrintS("---------------------------\n");
1359#endif
1360 poly h_p;
1361 int i,j,at,pass, ii;
1362 int start=0;
1363 int sigSafe;
1364 unsigned long not_sev;
1365 // long reddeg,d;
1366 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1367 int li;
1368
1369 pass = j = 0;
1370 // d = reddeg = h->GetpFDeg();
1371 h->SetShortExpVector();
1372 h_p = h->GetLmTailRing();
1373 not_sev = ~ h->sev;
1374 loop
1375 {
1376 j = kFindDivisibleByInT(strat, h, start);
1377 if (j < 0)
1378 {
1379 return 1;
1380 }
1381
1382 li = strat->T[j].pLength;
1383 if (li<=0) li=strat->T[j].GetpLength();
1384 ii = j;
1385 /*
1386 * the polynomial to reduce with (up to the moment) is;
1387 * pi with length li
1388 */
1389 i = j;
1390#if 1
1391 if (test_opt_length)
1392 loop
1393 {
1394 /*- search the shortest possible with respect to length -*/
1395 i++;
1396 if (i > strat->tl)
1397 break;
1398 if (li==1)
1399 break;
1400 if ((strat->T[i].pLength < li)
1401 &&
1402 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1403 h_p, not_sev, strat->tailRing))
1404 {
1405 /*
1406 * the polynomial to reduce with is now;
1407 */
1408 li = strat->T[i].pLength;
1409 if (li<=0) li=strat->T[i].GetpLength();
1410 ii = i;
1411 }
1412 }
1413 start = ii+1;
1414#endif
1415
1416 /*
1417 * end of search: have to reduce with pi
1418 */
1419#ifdef KDEBUG
1420 if (TEST_OPT_DEBUG)
1421 {
1422 PrintS("red:");
1423 h->wrp();
1424 PrintS(" with ");
1425 strat->T[ii].wrp();
1426 }
1427#endif
1428 assume(strat->fromT == FALSE);
1429//#if 1
1430#ifdef DEBUGF5
1431 Print("BEFORE REDUCTION WITH %d:\n",ii);
1432 PrintS("--------------------------------\n");
1433 pWrite(h->sig);
1434 pWrite(strat->T[ii].sig);
1435 pWrite(h->GetLmCurrRing());
1436 pWrite(pHead(h->p1));
1437 pWrite(pHead(h->p2));
1438 pWrite(pHead(strat->T[ii].p));
1439 PrintS("--------------------------------\n");
1440 printf("INDEX OF REDUCER T: %d\n",ii);
1441#endif
1442 sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1443#if SBA_PRINT_REDUCTION_STEPS
1444 if (sigSafe != 3)
1445 sba_reduction_steps++;
1446#endif
1447#if SBA_PRINT_OPERATIONS
1448 if (sigSafe != 3)
1449 sba_operations += pLength(strat->T[ii].p);
1450#endif
1451 // if reduction has taken place, i.e. the reduction was sig-safe
1452 // otherwise start is already at the next position and the loop
1453 // searching reducers in T goes on from index start
1454//#if 1
1455#ifdef DEBUGF5
1456 Print("SigSAFE: %d\n",sigSafe);
1457#endif
1458 if (sigSafe != 3)
1459 {
1460 // start the next search for reducers in T from the beginning
1461 start = 0;
1462#ifdef KDEBUG
1463 if (TEST_OPT_DEBUG)
1464 {
1465 PrintS("\nto ");
1466 h->wrp();
1467 PrintLn();
1468 }
1469#endif
1470
1471 h_p = h->GetLmTailRing();
1472 if (h_p == NULL)
1473 {
1474 kDeleteLcm(h);
1475 return 0;
1476 }
1477 h->SetShortExpVector();
1478 not_sev = ~ h->sev;
1479 /*
1480 * try to reduce the s-polynomial h
1481 *test first whether h should go to the lazyset L
1482 *-if the degree jumps
1483 *-if the number of pre-defined reductions jumps
1484 */
1485 pass++;
1486 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1487 {
1488 h->SetLmCurrRing();
1489 at = strat->posInL(strat->L,strat->Ll,h,strat);
1490 if (at <= strat->Ll)
1491 {
1492 int dummy=strat->sl;
1493 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1494 {
1495 return 1;
1496 }
1497 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1498#ifdef KDEBUG
1499 if (TEST_OPT_DEBUG)
1500 Print(" lazy: -> L%d\n",at);
1501#endif
1502 h->Clear();
1503 return -1;
1504 }
1505 }
1506 }
1507 }
1508}
1509
1510
1512{
1513 //Since reduce is really bad for SBA we use the following idea:
1514 // We first check if we can build a gcd pair between h and S
1515 //where the sig remains the same and replace h by this gcd poly
1517 #if GCD_SBA
1518 while(sbaCheckGcdPair(h,strat))
1519 {
1520 h->sev = pGetShortExpVector(h->p);
1521 }
1522 #endif
1523 poly beforeredsig;
1524 beforeredsig = pCopy(h->sig);
1525
1526 if (strat->tl<0) return 1;
1527 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1528 //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1529 assume(h->FDeg == h->pFDeg());
1530//#if 1
1531#ifdef DEBUGF5
1532 Print("------- IN REDSIG -------\n");
1533 Print("p: ");
1534 pWrite(pHead(h->p));
1535 Print("p1: ");
1536 pWrite(pHead(h->p1));
1537 Print("p2: ");
1538 pWrite(pHead(h->p2));
1539 Print("---------------------------\n");
1540#endif
1541 poly h_p;
1542 int i,j,at,pass, ii;
1543 int start=0;
1544 int sigSafe;
1545 unsigned long not_sev;
1546 // long reddeg,d;
1547 int li;
1548 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1549
1550 pass = j = 0;
1551 // d = reddeg = h->GetpFDeg();
1552 h->SetShortExpVector();
1553 h_p = h->GetLmTailRing();
1554 not_sev = ~ h->sev;
1555 loop
1556 {
1557 j = kFindDivisibleByInT(strat, h, start);
1558 if (j < 0)
1559 {
1560 #if GCD_SBA
1561 while(sbaCheckGcdPair(h,strat))
1562 {
1563 h->sev = pGetShortExpVector(h->p);
1564 h->is_redundant = FALSE;
1565 start = 0;
1566 }
1567 #endif
1568 // over ZZ: cleanup coefficients by complete reduction with monomials
1569 postReduceByMonSig(h, strat);
1570 if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
1571 j = kFindDivisibleByInT(strat, h,start);
1572 if(j < 0)
1573 {
1574 if(strat->tl >= 0)
1575 h->i_r1 = strat->tl;
1576 else
1577 h->i_r1 = -1;
1578 if (h->GetLmTailRing() == NULL)
1579 {
1580 kDeleteLcm(h);
1581 h->Clear();
1582 return 0;
1583 }
1584 //Check for sigdrop after reduction
1585 if(pLtCmp(beforeredsig,h->sig) == 1)
1586 {
1587 strat->sigdrop = TRUE;
1588 //Reduce it as much as you can
1589 int red_result = redRing(h,strat);
1590 if(red_result == 0)
1591 {
1592 //It reduced to 0, cancel the sigdrop
1593 strat->sigdrop = FALSE;
1594 p_Delete(&h->sig,currRing);h->sig = NULL;
1595 return 0;
1596 }
1597 else
1598 {
1599 //strat->enterS(*h, strat->sl+1, strat, strat->tl);
1600 return 0;
1601 }
1602 }
1603 p_Delete(&beforeredsig,currRing);
1604 return 1;
1605 }
1606 }
1607
1608 li = strat->T[j].pLength;
1609 if (li<=0) li=strat->T[j].GetpLength();
1610 ii = j;
1611 /*
1612 * the polynomial to reduce with (up to the moment) is;
1613 * pi with length li
1614 */
1615 i = j;
1616 if (test_opt_length)
1617 loop
1618 {
1619 /*- search the shortest possible with respect to length -*/
1620 i++;
1621 if (i > strat->tl)
1622 break;
1623 if (li==1)
1624 break;
1625 if ((strat->T[i].pLength < li)
1626 && n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1627 && p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1628 h_p, not_sev, strat->tailRing))
1629 {
1630 /*
1631 * the polynomial to reduce with is now;
1632 */
1633 li = strat->T[i].pLength;
1634 if (li<=0) li=strat->T[i].GetpLength();
1635 ii = i;
1636 }
1637 }
1638
1639 start = ii+1;
1640
1641 /*
1642 * end of search: have to reduce with pi
1643 */
1644#ifdef KDEBUG
1645 if (TEST_OPT_DEBUG)
1646 {
1647 PrintS("red:");
1648 h->wrp();
1649 PrintS(" with ");
1650 strat->T[ii].wrp();
1651 }
1652#endif
1653 assume(strat->fromT == FALSE);
1654//#if 1
1655#ifdef DEBUGF5
1656 Print("BEFORE REDUCTION WITH %d:\n",ii);
1657 Print("--------------------------------\n");
1658 pWrite(h->sig);
1659 pWrite(strat->T[ii].sig);
1660 pWrite(h->GetLmCurrRing());
1661 pWrite(pHead(h->p1));
1662 pWrite(pHead(h->p2));
1663 pWrite(pHead(strat->T[ii].p));
1664 Print("--------------------------------\n");
1665 printf("INDEX OF REDUCER T: %d\n",ii);
1666#endif
1667 sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1668 if(h->p == NULL && h->sig == NULL)
1669 {
1670 //Trivial case catch
1671 strat->sigdrop = FALSE;
1672 }
1673 #if 0
1674 //If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1675 //In some cases this proves to be very bad
1676 if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1677 {
1678 int red_result = redRing(h,strat);
1679 if(red_result == 0)
1680 {
1681 pDelete(&h->sig);h->sig = NULL;
1682 return 0;
1683 }
1684 else
1685 {
1686 strat->sigdrop = TRUE;
1687 return 1;
1688 }
1689 }
1690 #endif
1691 if(strat->sigdrop)
1692 return 1;
1693#if SBA_PRINT_REDUCTION_STEPS
1694 if (sigSafe != 3)
1695 sba_reduction_steps++;
1696#endif
1697#if SBA_PRINT_OPERATIONS
1698 if (sigSafe != 3)
1699 sba_operations += pLength(strat->T[ii].p);
1700#endif
1701 // if reduction has taken place, i.e. the reduction was sig-safe
1702 // otherwise start is already at the next position and the loop
1703 // searching reducers in T goes on from index start
1704//#if 1
1705#ifdef DEBUGF5
1706 Print("SigSAFE: %d\n",sigSafe);
1707#endif
1708 if (sigSafe != 3)
1709 {
1710 // start the next search for reducers in T from the beginning
1711 start = 0;
1712#ifdef KDEBUG
1713 if (TEST_OPT_DEBUG)
1714 {
1715 PrintS("\nto ");
1716 h->wrp();
1717 PrintLn();
1718 }
1719#endif
1720
1721 h_p = h->GetLmTailRing();
1722 if (h_p == NULL)
1723 {
1724 kDeleteLcm(h);
1725 return 0;
1726 }
1727 h->SetShortExpVector();
1728 not_sev = ~ h->sev;
1729 /*
1730 * try to reduce the s-polynomial h
1731 *test first whether h should go to the lazyset L
1732 *-if the degree jumps
1733 *-if the number of pre-defined reductions jumps
1734 */
1735 pass++;
1736 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1737 {
1738 h->SetLmCurrRing();
1739 at = strat->posInL(strat->L,strat->Ll,h,strat);
1740 if (at <= strat->Ll)
1741 {
1742 int dummy=strat->sl;
1743 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1744 {
1745 return 1;
1746 }
1747 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1748#ifdef KDEBUG
1749 if (TEST_OPT_DEBUG)
1750 Print(" lazy: -> L%d\n",at);
1751#endif
1752 h->Clear();
1753 return -1;
1754 }
1755 }
1756 }
1757 }
1758}
1759
1760// tail reduction for SBA
1761poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
1762{
1763 strat->redTailChange=FALSE;
1764 if (strat->noTailReduction) return L->GetLmCurrRing();
1765 poly h, p;
1766 p = h = L->GetLmTailRing();
1767 if ((h==NULL) || (pNext(h)==NULL))
1768 return L->GetLmCurrRing();
1769
1770 TObject* With;
1771 // placeholder in case strat->tl < 0
1772 TObject With_s(strat->tailRing);
1773
1774 LObject Ln(pNext(h), strat->tailRing);
1775 Ln.sig = L->sig;
1776 Ln.sevSig = L->sevSig;
1777 Ln.pLength = L->GetpLength() - 1;
1778
1779 pNext(h) = NULL;
1780 if (L->p != NULL) pNext(L->p) = NULL;
1781 L->pLength = 1;
1782
1783 Ln.PrepareRed(strat->use_buckets);
1784
1785 int cnt=REDTAIL_CANONICALIZE;
1786 while(!Ln.IsNull())
1787 {
1788 loop
1789 {
1790 if(rField_is_Ring(currRing) && strat->sigdrop)
1791 break;
1792 Ln.SetShortExpVector();
1793 if (withT)
1794 {
1795 int j;
1796 j = kFindDivisibleByInT(strat, &Ln);
1797 if (j < 0) break;
1798 With = &(strat->T[j]);
1799 }
1800 else
1801 {
1802 With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1803 if (With == NULL) break;
1804 }
1805 cnt--;
1806 if (cnt==0)
1807 {
1809 /*poly tmp=*/Ln.CanonicalizeP();
1811 {
1812 Ln.Normalize();
1813 //pNormalize(tmp);
1814 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1815 }
1816 }
1818 {
1819 With->pNorm();
1820 }
1821 strat->redTailChange=TRUE;
1822 int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1824 L->sig = Ln.sig;
1825 //Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1826 // I delete it an then set Ln.sig. Hence L->sig is lost
1827#if SBA_PRINT_REDUCTION_STEPS
1828 if (ret != 3)
1829 sba_reduction_steps++;
1830#endif
1831#if SBA_PRINT_OPERATIONS
1832 if (ret != 3)
1833 sba_operations += pLength(With->p);
1834#endif
1835 if (ret)
1836 {
1837 // reducing the tail would violate the exp bound
1838 // set a flag and hope for a retry (in bba)
1840 if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1841 do
1842 {
1843 pNext(h) = Ln.LmExtractAndIter();
1844 pIter(h);
1845 L->pLength++;
1846 } while (!Ln.IsNull());
1847 goto all_done;
1848 }
1849 if (Ln.IsNull()) goto all_done;
1850 if (! withT) With_s.Init(currRing);
1851 if(rField_is_Ring(currRing) && strat->sigdrop)
1852 {
1853 //Cannot break the loop here so easily
1854 break;
1855 }
1856 }
1857 pNext(h) = Ln.LmExtractAndIter();
1858 pIter(h);
1860 pNormalize(h);
1861 L->pLength++;
1862 }
1863 all_done:
1864 Ln.Delete();
1865 if (L->p != NULL) pNext(L->p) = pNext(p);
1866
1867 if (strat->redTailChange)
1868 {
1869 L->length = 0;
1870 }
1871 //if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1872 //L->Normalize(); // HANNES: should have a test
1873 kTest_L(L,strat);
1874 return L->GetLmCurrRing();
1875}
1876
1877/*2
1878* reduction procedure for the inhomogeneous case
1879* and not a degree-ordering
1880*/
1882{
1883 if (strat->tl<0) return 1;
1884 int at,i,ii,li;
1885 int j = 0;
1886 int pass = 0;
1887 int cnt = RED_CANONICALIZE;
1888 assume(h->pFDeg() == h->FDeg);
1889 long reddeg = h->GetpFDeg();
1890 long d;
1891 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
1892
1893 h->SetShortExpVector();
1894 poly h_p = h->GetLmTailRing();
1895 h->PrepareRed(strat->use_buckets);
1896 loop
1897 {
1898 j = kFindDivisibleByInT(strat, h);
1899 if (j < 0) return 1;
1900
1901 li = strat->T[j].pLength;
1902 ii = j;
1903 /*
1904 * the polynomial to reduce with (up to the moment) is;
1905 * pi with length li
1906 */
1907
1908 i = j;
1909#if 1
1910 if (test_opt_length)
1911 {
1912 if (li<=0) li=strat->T[j].GetpLength();
1913 if(li>2)
1914 {
1915 unsigned long not_sev = ~ h->sev;
1916 loop
1917 {
1918 /*- search the shortest possible with respect to length -*/
1919 i++;
1920 if (i > strat->tl)
1921 break;
1922 if ((strat->T[i].pLength < li)
1923 &&
1924 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1925 h_p, not_sev, strat->tailRing))
1926 {
1927 /*
1928 * the polynomial to reduce with is now;
1929 */
1930 li = strat->T[i].pLength;
1931 if (li<=0) li=strat->T[i].GetpLength();
1932 ii = i;
1933 if (li<3) break;
1934 }
1935 }
1936 }
1937 }
1938#endif
1939
1940 /*
1941 * end of search: have to reduce with pi
1942 */
1943
1944
1945#ifdef KDEBUG
1946 if (TEST_OPT_DEBUG)
1947 {
1948 PrintS("red:");
1949 h->wrp();
1950 PrintS(" with ");
1951 strat->T[ii].wrp();
1952 }
1953#endif
1954
1955 ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
1956#if SBA_PRINT_REDUCTION_STEPS
1957 sba_interreduction_steps++;
1958#endif
1959#if SBA_PRINT_OPERATIONS
1960 sba_interreduction_operations += pLength(strat->T[ii].p);
1961#endif
1962
1963#ifdef KDEBUG
1964 if (TEST_OPT_DEBUG)
1965 {
1966 PrintS("\nto ");
1967 h->wrp();
1968 PrintLn();
1969 }
1970#endif
1971
1972 h_p=h->GetLmTailRing();
1973
1974 if (h_p == NULL)
1975 {
1976 kDeleteLcm(h);
1977 return 0;
1978 }
1979 #if 0 // red id redLiftstd if OPT_IDLIFT
1981 {
1982 if (h->p!=NULL)
1983 {
1984 if(p_GetComp(h->p,currRing)>strat->syzComp)
1985 {
1986 h->Delete();
1987 return 0;
1988 }
1989 }
1990 else if (h->t_p!=NULL)
1991 {
1992 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1993 {
1994 h->Delete();
1995 return 0;
1996 }
1997 }
1998 }
1999 #endif
2000 #if 0
2001 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
2002 {
2003 if (h->p!=NULL)
2004 {
2005 if(p_GetComp(h->p,currRing)>strat->syzComp)
2006 {
2007 return 1;
2008 }
2009 }
2010 else if (h->t_p!=NULL)
2011 {
2012 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2013 {
2014 return 1;
2015 }
2016 }
2017 }
2018 #endif
2019 h->SetShortExpVector();
2020 d = h->SetpFDeg();
2021 /*- try to reduce the s-polynomial -*/
2022 cnt--;
2023 pass++;
2024 if (//!TEST_OPT_REDTHROUGH &&
2025 (strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
2026 {
2027 h->SetLmCurrRing();
2028 at = strat->posInL(strat->L,strat->Ll,h,strat);
2029 if (at <= strat->Ll)
2030 {
2031#if 1
2032#ifdef HAVE_SHIFTBBA
2033 if (rIsLPRing(currRing))
2034 {
2035 if (kFindDivisibleByInT(strat, h) < 0)
2036 return 1;
2037 }
2038 else
2039#endif
2040 {
2041 int dummy=strat->sl;
2042 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2043 return 1;
2044 }
2045#endif
2046#ifdef KDEBUG
2047 if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
2048#endif
2049 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2050 h->Clear();
2051 return -1;
2052 }
2053 }
2054 else if (d != reddeg)
2055 {
2056 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2057 {
2058 if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
2059 {
2060 strat->overflow=TRUE;
2061 //Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2062 h->GetP();
2063 at = strat->posInL(strat->L,strat->Ll,h,strat);
2064 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2065 h->Clear();
2066 return -1;
2067 }
2068 }
2069 else if ((TEST_OPT_PROT) && (strat->Ll < 0))
2070 {
2071 Print(".%ld",d);mflush();
2072 reddeg = d;
2073 }
2074 }
2075 else if (UNLIKELY(cnt==0))
2076 {
2077 h->CanonicalizeP();
2078 cnt=RED_CANONICALIZE;
2079 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
2080 }
2081 }
2082}
2083/*2
2084* reduction procedure for the sugar-strategy (honey)
2085* reduces h with elements from T choosing first possible
2086* element in T with respect to the given ecart
2087*/
2089{
2090 if (strat->tl<0) return 1;
2091 //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
2092 assume(h->FDeg == h->pFDeg());
2093 poly h_p;
2094 int i,j,at,pass,ei, ii, h_d;
2095 long reddeg,d;
2096 int li;
2097 BOOLEAN test_opt_length=TEST_OPT_LENGTH;
2098
2099 pass = j = 0;
2100 d = reddeg = h->GetpFDeg() + h->ecart;
2101 h->SetShortExpVector();
2102 h_p = h->GetLmTailRing();
2103
2104 h->PrepareRed(strat->use_buckets);
2105 loop
2106 {
2107 j=kFindDivisibleByInT(strat, h);
2108 if (j < 0) return 1;
2109
2110 ei = strat->T[j].ecart;
2111 li = strat->T[j].pLength;
2112 ii = j;
2113 /*
2114 * the polynomial to reduce with (up to the moment) is;
2115 * pi with ecart ei (T[ii])
2116 */
2117 i = j;
2118 if (test_opt_length)
2119 {
2120 if (li<=0) li=strat->T[j].GetpLength();
2121 if (li>2)
2122 {
2123 unsigned long not_sev = ~ h->sev;
2124 loop
2125 {
2126 /*- takes the first possible with respect to ecart -*/
2127 i++;
2128 if (i > strat->tl) break;
2129 if (ei <= h->ecart) break;
2130 if(p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
2131 h_p, not_sev, strat->tailRing))
2132 {
2133 strat->T[i].GetpLength();
2134 if (((strat->T[i].ecart < ei) && (ei> h->ecart))
2135 || ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
2136 {
2137 /*
2138 * the polynomial to reduce with is now;
2139 */
2140 ei = strat->T[i].ecart;
2141 li = strat->T[i].pLength;
2142 ii = i;
2143 if (li==1) break;
2144 if (ei<=h->ecart) break;
2145 }
2146 }
2147 }
2148 }
2149 }
2150
2151 /*
2152 * end of search: have to reduce with pi
2153 */
2154 if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
2155 {
2156 h->GetTP(); // clears bucket
2157 h->SetLmCurrRing();
2158 /*
2159 * It is not possible to reduce h with smaller ecart;
2160 * if possible h goes to the lazy-set L,i.e
2161 * if its position in L would be not the last one
2162 */
2163 if (strat->Ll >= 0) /* L is not empty */
2164 {
2165 at = strat->posInL(strat->L,strat->Ll,h,strat);
2166 if(at <= strat->Ll)
2167 /*- h will not become the next element to reduce -*/
2168 {
2169 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2170#ifdef KDEBUG
2171 if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
2172#endif
2173 h->Clear();
2174 return -1;
2175 }
2176 }
2177 }
2178#ifdef KDEBUG
2179 if (TEST_OPT_DEBUG)
2180 {
2181 PrintS("red:");
2182 h->wrp();
2183 Print("\nwith T[%d]:",ii);
2184 strat->T[ii].wrp();
2185 }
2186#endif
2187 assume(strat->fromT == FALSE);
2188
2189 ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
2190#if SBA_PRINT_REDUCTION_STEPS
2191 sba_interreduction_steps++;
2192#endif
2193#if SBA_PRINT_OPERATIONS
2194 sba_interreduction_operations += strat->T[ii].pLength;
2195#endif
2196#ifdef KDEBUG
2197 if (TEST_OPT_DEBUG)
2198 {
2199 PrintS("\nto:");
2200 h->wrp();
2201 PrintLn();
2202 }
2203#endif
2204 if(h->IsNull())
2205 {
2206 kDeleteLcm(h);
2207 h->Clear();
2208 return 0;
2209 }
2210 #if 0 // red is redLiftstd if OPT_IDLIFT
2212 {
2213 if (h->p!=NULL)
2214 {
2215 if(p_GetComp(h->p,currRing)>strat->syzComp)
2216 {
2217 h->Delete();
2218 return 0;
2219 }
2220 }
2221 else if (h->t_p!=NULL)
2222 {
2223 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2224 {
2225 h->Delete();
2226 return 0;
2227 }
2228 }
2229 }
2230 else
2231 #endif
2232 if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
2233 {
2234 if (h->p!=NULL)
2235 {
2236 if(p_GetComp(h->p,currRing)>strat->syzComp)
2237 {
2238 return 1;
2239 }
2240 }
2241 else if (h->t_p!=NULL)
2242 {
2243 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
2244 {
2245 return 1;
2246 }
2247 }
2248 }
2249 h->SetShortExpVector();
2250 h_d = h->SetpFDeg();
2251 /* compute the ecart */
2252 if (ei <= h->ecart)
2253 h->ecart = d-h_d;
2254 else
2255 h->ecart = d-h_d+ei-h->ecart;
2256
2257 /*
2258 * try to reduce the s-polynomial h
2259 *test first whether h should go to the lazyset L
2260 *-if the degree jumps
2261 *-if the number of pre-defined reductions jumps
2262 */
2263 pass++;
2264 d = h_d + h->ecart;
2266 && (strat->Ll >= 0)
2267 && ((d > reddeg) || (pass > strat->LazyPass))))
2268 {
2269 h->GetTP(); // clear bucket
2270 h->SetLmCurrRing();
2271 at = strat->posInL(strat->L,strat->Ll,h,strat);
2272 if (at <= strat->Ll)
2273 {
2274#ifdef HAVE_SHIFTBBA
2275 if (rIsLPRing(currRing))
2276 {
2277 if (kFindDivisibleByInT(strat, h) < 0)
2278 return 1;
2279 }
2280 else
2281#endif
2282 {
2283 int dummy=strat->sl;
2284 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2285 return 1;
2286 }
2287 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2288#ifdef KDEBUG
2289 if (TEST_OPT_DEBUG)
2290 Print(" degree jumped: -> L%d\n",at);
2291#endif
2292 h->Clear();
2293 return -1;
2294 }
2295 }
2296 else if (d > reddeg)
2297 {
2298 if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
2299 {
2300 if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2301 {
2302 strat->overflow=TRUE;
2303 //Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2304 h->GetP();
2305 at = strat->posInL(strat->L,strat->Ll,h,strat);
2306 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2307 h->Clear();
2308 return -1;
2309 }
2310 }
2311 else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
2312 {
2313 //h->wrp(); Print("<%d>\n",h->GetpLength());
2314 reddeg = d;
2315 Print(".%ld",d); mflush();
2316 }
2317 }
2318 }
2319}
2320
2321/*2
2322* reduction procedure for the normal form
2323*/
2324
2325poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
2326{
2327 if (h==NULL) return NULL;
2328 int j,j_ring;
2329 int cnt=REDNF_CANONICALIZE;
2330 max_ind=strat->sl;
2331
2332 if (0 > strat->sl)
2333 {
2334 return h;
2335 }
2336 LObject P(h);
2337 P.SetShortExpVector();
2338 P.t_p=NULL;
2339#ifdef HAVE_RINGS
2340 BOOLEAN is_ring = rField_is_Ring(currRing);
2341 if(is_ring) nonorm=TRUE;
2342#endif
2343#ifdef KDEBUG
2344// if (TEST_OPT_DEBUG)
2345// {
2346// PrintS("redNF: starting S:\n");
2347// for( j = 0; j <= max_ind; j++ )
2348// {
2349// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2350// pWrite(strat->S[j]);
2351// }
2352// };
2353#endif
2354 if (rField_is_Z(currRing))
2355 {
2356 redRing_Z_S(&P,strat);
2357 if (P.bucket!=NULL)
2358 {
2359 P.p=kBucketClear(P.bucket);
2360 kBucketDestroy(&P.bucket);
2361 }
2362 return P.p;
2363 }
2364 else if (rField_is_Ring(currRing))
2365 {
2366 redRing_S(&P,strat);
2367 if (P.bucket!=NULL)
2368 {
2369 P.p=kBucketClear(P.bucket);
2370 kBucketDestroy(&P.bucket);
2371 }
2372 return P.p;
2373 }
2374
2375 P.bucket = kBucketCreate(currRing);
2376 kBucketInit(P.bucket,P.p,pLength(P.p));
2377 kbTest(P.bucket);
2378 P.p=kBucketGetLm(P.bucket);
2379 loop
2380 {
2381 j_ring=j=kFindDivisibleByInS_noCF(strat,&max_ind,&P);
2382 while ((j>=0)
2383 && (nonorm)
2384 && (!n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[j]),currRing->cf)))
2385 j=kFindNextDivisibleByInS(strat,j+1,max_ind,&P);
2386 if (j>=0)
2387 {
2388 int sl=pSize(strat->S[j]);
2389 int jj=j;
2390 loop
2391 {
2392 int sll;
2393 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2394 if (jj<0) break;
2395 if ((!nonorm)
2396 || (n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[jj]),currRing->cf)))
2397 {
2398 sll=pSize(strat->S[jj]);
2399 if (sll<sl)
2400 {
2401 #ifdef KDEBUG
2402 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2403 #endif
2404 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2405 j=jj;
2406 sl=sll;
2407 }
2408 }
2409 }
2410 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2411 {
2412 pNorm(strat->S[j]);
2413 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2414 }
2415 nNormalize(pGetCoeff(P.p));
2416#ifdef KDEBUG
2417 if (TEST_OPT_DEBUG)
2418 {
2419 PrintS("red:");
2420 wrp(P.p);
2421 PrintS(" with ");
2422 wrp(strat->S[j]);
2423 }
2424#endif
2425#ifdef HAVE_PLURAL
2427 {
2428 number coef;
2429 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
2430 nDelete(&coef);
2431 }
2432 else
2433#endif
2434 {
2435 kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),
2436 strat->kNoether);
2437 }
2438 cnt--;
2439 if (cnt==0)
2440 {
2441 kBucketCanonicalize(P.bucket);
2443 }
2444 P.p=kBucketGetLm(P.bucket);
2445 //P.t_p=NULL;
2446#ifdef KDEBUG
2447 if (TEST_OPT_DEBUG)
2448 {
2449 PrintS("\nto:");
2450 wrp(P.p);
2451 PrintLn();
2452 }
2453#endif
2454 if (P.p==NULL)
2455 {
2456 kBucketDestroy(&P.bucket);
2457 return NULL;
2458 }
2459 kbTest(P.bucket);
2460 P.SetShortExpVector();
2461 }
2462#ifdef HAVE_RINGS
2463 else if (is_ring && (j_ring>=0) && (currRing->cf->cfQuotRem!=ndQuotRem))
2464 {
2465 number r;
2466 number n=n_QuotRem(pGetCoeff(P.p),pGetCoeff(strat->S[j_ring]),&r,currRing->cf);
2467 if(!n_IsZero(n,currRing->cf))
2468 {
2469 poly lm=kBucketGetLm(P.bucket);
2470 poly m=p_Head(lm,currRing);
2471 p_ExpVectorSub(m,strat->S[j_ring],currRing);
2472 if (p_GetComp(strat->S[j_ring], currRing) != p_GetComp(lm, currRing))
2473 {
2475 }
2477 p_Setm(m,currRing);
2478#ifdef KDEBUG
2479 if (TEST_OPT_DEBUG)
2480 {
2481 PrintS("redi (coeff):");
2482 wrp(P.p);
2483 PrintS(" with ");
2484 wrp(strat->S[j]);
2485 }
2486#endif
2487 int l=-1;
2488 kBucket_Minus_m_Mult_p(P.bucket,m,strat->S[j_ring],&l);
2489 P.p=kBucketGetLm(P.bucket);
2491#ifdef KDEBUG
2492 if (TEST_OPT_DEBUG)
2493 {
2494 PrintS("\nto:");
2495 wrp(P.p);
2496 PrintLn();
2497 }
2498#endif
2499 }
2500 else
2501 {
2502 n_Delete(&n,currRing->cf);
2503 }
2504 n_Delete(&r,currRing->cf);
2505 P.p=kBucketClear(P.bucket);
2506 kBucketDestroy(&P.bucket);
2507 pNormalize(P.p);
2508 return P.p;
2509 }
2510#endif
2511 else
2512 {
2513 P.p=kBucketClear(P.bucket);
2514 kBucketDestroy(&P.bucket);
2515 pNormalize(P.p);
2516 return P.p;
2517 }
2518 }
2519}
2520
2521/*2
2522* reduction procedure from global case but with jet bound
2523*/
2524
2525poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
2526{
2527 h = pJet(h,bound);
2528 if (h==NULL) return NULL;
2529 int j;
2530 max_ind=strat->sl;
2531
2532 if (0 > strat->sl)
2533 {
2534 return h;
2535 }
2536 LObject P(h);
2537 P.SetShortExpVector();
2538 P.bucket = kBucketCreate(currRing);
2539 kBucketInit(P.bucket,P.p,pLength(P.p));
2540 kbTest(P.bucket);
2541#ifdef HAVE_RINGS
2542 BOOLEAN is_ring = rField_is_Ring(currRing);
2543#endif
2544
2545 loop
2546 {
2547 j=kFindDivisibleByInS(strat,&max_ind,&P);
2548 if (j>=0)
2549 {
2550#ifdef HAVE_RINGS
2551 if (!is_ring)
2552 {
2553#endif
2554 int sl=pSize(strat->S[j]);
2555 int jj=j;
2556 loop
2557 {
2558 int sll;
2559 jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2560 if (jj<0) break;
2561 sll=pSize(strat->S[jj]);
2562 if (sll<sl)
2563 {
2564 #ifdef KDEBUG
2565 if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2566 #endif
2567 //else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2568 j=jj;
2569 sl=sll;
2570 }
2571 }
2572 if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2573 {
2574 pNorm(strat->S[j]);
2575 //if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2576 }
2577#ifdef HAVE_RINGS
2578 }
2579#endif
2580 nNormalize(pGetCoeff(P.p));
2581#ifdef KDEBUG
2582 if (TEST_OPT_DEBUG)
2583 {
2584 PrintS("red:");
2585 wrp(h);
2586 PrintS(" with ");
2587 wrp(strat->S[j]);
2588 }
2589#endif
2590#ifdef HAVE_PLURAL
2592 {
2593 number coef;
2594 nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
2595 nDelete(&coef);
2596 }
2597 else
2598#endif
2599 {
2600 kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2601 P.p = kBucketClear(P.bucket);
2602 P.p = pJet(P.p,bound);
2603 if(!P.IsNull())
2604 {
2605 kBucketDestroy(&P.bucket);
2606 P.SetShortExpVector();
2607 P.bucket = kBucketCreate(currRing);
2608 kBucketInit(P.bucket,P.p,pLength(P.p));
2609 }
2610 }
2611 h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2612 if (h==NULL)
2613 {
2614 kBucketDestroy(&P.bucket);
2615 return NULL;
2616 }
2617 kbTest(P.bucket);
2618 P.p=h;
2619 P.t_p=NULL;
2620 P.SetShortExpVector();
2621#ifdef KDEBUG
2622 if (TEST_OPT_DEBUG)
2623 {
2624 PrintS("\nto:");
2625 wrp(h);
2626 PrintLn();
2627 }
2628#endif
2629 }
2630 else
2631 {
2632 P.p=kBucketClear(P.bucket);
2633 kBucketDestroy(&P.bucket);
2634 pNormalize(P.p);
2635 return P.p;
2636 }
2637 }
2638}
2639
2640void kDebugPrint(kStrategy strat);
2641
2642ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
2643{
2644 int red_result = 1;
2645 int olddeg,reduc;
2646 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2647 BOOLEAN withT = FALSE;
2648 BITSET save;
2649 SI_SAVE_OPT1(save);
2650
2651 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
2653 initBuchMoraPosRing(strat);
2654 else
2655 initBuchMoraPos(strat);
2656 initHilbCrit(F,Q,&hilb,strat);
2657 initBba(strat);
2658 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
2659 /*Shdl=*/initBuchMora(F, Q,strat);
2660 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2661 reduc = olddeg = 0;
2662
2663#ifndef NO_BUCKETS
2665 strat->use_buckets = 1;
2666#endif
2667 // redtailBBa against T for inhomogeneous input
2668 if (!TEST_OPT_OLDSTD)
2669 withT = ! strat->homog;
2670
2671 // strat->posInT = posInT_pLength;
2672 kTest_TS(strat);
2673
2674#ifdef HAVE_TAIL_RING
2675 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2677#endif
2678 if (BVERBOSE(23))
2679 {
2680 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2681 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2682 kDebugPrint(strat);
2683 }
2684
2685
2686#ifdef KDEBUG
2687 //kDebugPrint(strat);
2688#endif
2689 /* compute------------------------------------------------------- */
2690 while (strat->Ll >= 0)
2691 {
2692 #ifdef KDEBUG
2693 if (TEST_OPT_DEBUG) messageSets(strat);
2694 #endif
2695 if (siCntrlc)
2696 {
2697 while (strat->Ll >= 0)
2698 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2699 strat->noClearS=TRUE;
2700 }
2702 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2703 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2704 {
2705 /*
2706 *stops computation if
2707 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2708 *a predefined number Kstd1_deg
2709 */
2710 while ((strat->Ll >= 0)
2711 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2712 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2713 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2714 )
2715 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2716 if (strat->Ll<0) break;
2717 else strat->noClearS=TRUE;
2718 }
2719 if (strat->Ll== 0) strat->interpt=TRUE;
2720 /* picks the last element from the lazyset L */
2721 strat->P = strat->L[strat->Ll];
2722 strat->Ll--;
2723
2724 if (pNext(strat->P.p) == strat->tail)
2725 {
2726 // deletes the short spoly
2728 pLmDelete(strat->P.p);
2729 else
2730 pLmFree(strat->P.p);
2731 strat->P.p = NULL;
2732 poly m1 = NULL, m2 = NULL;
2733
2734 // check that spoly creation is ok
2735 while (strat->tailRing != currRing &&
2736 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2737 {
2738 assume(m1 == NULL && m2 == NULL);
2739 // if not, change to a ring where exponents are at least
2740 // large enough
2741 if (!kStratChangeTailRing(strat))
2742 {
2743 WerrorS("OVERFLOW...");
2744 break;
2745 }
2746 }
2747 // create the real one
2748 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2749 strat->tailRing, m1, m2, strat->R);
2750 }
2751 else if (strat->P.p1 == NULL)
2752 {
2753 if (strat->minim > 0)
2754 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2755 // for input polys, prepare reduction
2756 strat->P.PrepareRed(strat->use_buckets);
2757 }
2758
2759 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2760 {
2761 red_result = 0;
2762 }
2763 else
2764 {
2765 if (TEST_OPT_PROT)
2766 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2767 &olddeg,&reduc,strat, red_result);
2768
2769 /* reduction of the element chosen from L */
2770 red_result = strat->red(&strat->P,strat);
2771 if (errorreported) break;
2772 }
2773
2774 if (strat->overflow)
2775 {
2776 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2777 }
2778
2779 // reduction to non-zero new poly
2780 if (red_result == 1)
2781 {
2782 // get the polynomial (canonicalize bucket, make sure P.p is set)
2783 strat->P.GetP(strat->lmBin);
2784 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
2785 // but now, for entering S, T, we reset it
2786 // in the inhomogeneous case: FDeg == pFDeg
2787 if (strat->homog) strat->initEcart(&(strat->P));
2788
2789 /* statistic */
2790 if (TEST_OPT_PROT) PrintS("s");
2791
2792 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2793
2794 // reduce the tail and normalize poly
2795 // in the ring case we cannot expect LC(f) = 1,
2796 strat->redTailChange=FALSE;
2797
2798 /* if we are computing over Z we always want to try and cut down
2799 * the coefficients in the tail terms */
2801 {
2802 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2803 }
2804
2806 {
2807 strat->P.pCleardenom();
2809 {
2810 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2811 strat->P.pCleardenom();
2812 if (strat->redTailChange) { strat->P.t_p=NULL; }
2813 }
2814 }
2815 else
2816 {
2817 strat->P.pNorm();
2819 {
2820 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2821 if (strat->redTailChange) { strat->P.t_p=NULL; }
2822 }
2823 }
2824
2825#ifdef KDEBUG
2826 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2827#endif /* KDEBUG */
2828
2829 // min_std stuff
2830 if ((strat->P.p1==NULL) && (strat->minim>0))
2831 {
2832 if (strat->minim==1)
2833 {
2834 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2835 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2836 }
2837 else
2838 {
2839 strat->M->m[minimcnt]=strat->P.p2;
2840 strat->P.p2=NULL;
2841 }
2842 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2843 pNext(strat->M->m[minimcnt])
2844 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2845 strat->tailRing, currRing,
2846 currRing->PolyBin);
2847 minimcnt++;
2848 }
2849
2850 // enter into S, L, and T
2851 if (((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
2852 && ((!TEST_OPT_IDELIM) || (p_Deg(strat->P.p,currRing) > 0)))
2853 {
2854 strat->P.SetShortExpVector();
2855 enterT(strat->P, strat);
2857 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2858 else
2859 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2860 // posInS only depends on the leading term
2861 strat->enterS(strat->P, pos, strat, strat->tl);
2862#if 0
2863 int pl=pLength(strat->P.p);
2864 if (pl==1)
2865 {
2866 //if (TEST_OPT_PROT)
2867 //PrintS("<1>");
2868 }
2869 else if (pl==2)
2870 {
2871 //if (TEST_OPT_PROT)
2872 //PrintS("<2>");
2873 }
2874#endif
2875 }
2876 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2877// Print("[%d]",hilbeledeg);
2878 kDeleteLcm(&strat->P);
2879 if (strat->s_poly!=NULL)
2880 {
2881 // the only valid entries are: strat->P.p,
2882 // strat->tailRing (read-only, keep it)
2883 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2884 if (strat->s_poly(strat))
2885 {
2886 // we are called AFTER enterS, i.e. if we change P
2887 // we have to add it also to S/T
2888 // and add pairs
2889 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2890 enterT(strat->P, strat);
2892 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2893 else
2894 enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2895 strat->enterS(strat->P, pos, strat, strat->tl);
2896 }
2897 }
2898 }
2899 else if (strat->P.p1 == NULL && strat->minim > 0)
2900 {
2901 p_Delete(&strat->P.p2, currRing, strat->tailRing);
2902 }
2903
2904#ifdef KDEBUG
2905 memset(&(strat->P), 0, sizeof(strat->P));
2906#endif /* KDEBUG */
2907 kTest_TS(strat);
2908 }
2909#ifdef KDEBUG
2910 if (TEST_OPT_DEBUG) messageSets(strat);
2911#endif /* KDEBUG */
2912
2913 if (TEST_OPT_SB_1)
2914 {
2916 {
2917 int k=1;
2918 int j;
2919 while(k<=strat->sl)
2920 {
2921 j=0;
2922 loop
2923 {
2924 if (j>=k) break;
2925 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2926 j++;
2927 }
2928 k++;
2929 }
2930 }
2931 }
2932 /* complete reduction of the standard basis--------- */
2933 if (TEST_OPT_REDSB)
2934 {
2935 completeReduce(strat);
2936 if (strat->completeReduce_retry)
2937 {
2938 // completeReduce needed larger exponents, retry
2939 // to reduce with S (instead of T)
2940 // and in currRing (instead of strat->tailRing)
2941#ifdef HAVE_TAIL_RING
2942 if(currRing->bitmask>strat->tailRing->bitmask)
2943 {
2945 cleanT(strat);strat->tailRing=currRing;
2946 int i;
2947 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2948 completeReduce(strat);
2949 }
2950 if (strat->completeReduce_retry)
2951#endif
2952 Werror("exponent bound is %ld",currRing->bitmask);
2953 }
2954 }
2955 else if (TEST_OPT_PROT) PrintLn();
2956 /* release temp data-------------------------------- */
2957 exitBuchMora(strat);
2958 /* postprocessing for GB over ZZ --------------------*/
2959 if (!errorreported)
2960 {
2962 {
2963 for(int i = 0;i<=strat->sl;i++)
2964 {
2965 if(!nGreaterZero(pGetCoeff(strat->S[i])))
2966 {
2967 strat->S[i] = pNeg(strat->S[i]);
2968 }
2969 }
2970 finalReduceByMon(strat);
2971 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2972 {
2973 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2974 {
2975 strat->S[i] = pNeg(strat->Shdl->m[i]);
2976 }
2977 }
2978 }
2979 //else if (rField_is_Ring(currRing))
2980 // finalReduceByMon(strat);
2981 }
2982// if (TEST_OPT_WEIGHTM)
2983// {
2984// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2985// if (ecartWeights)
2986// {
2987// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2988// ecartWeights=NULL;
2989// }
2990// }
2991 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2992 SI_RESTORE_OPT1(save);
2993 /* postprocessing for GB over Q-rings ------------------*/
2994 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2995
2996 idTest(strat->Shdl);
2997
2998 return (strat->Shdl);
2999}
3000
3001ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
3002{
3003 // ring order stuff:
3004 // in sba we have (until now) two possibilities:
3005 // 1. an incremental computation w.r.t. (C,monomial order)
3006 // 2. a (possibly non-incremental) computation w.r.t. the
3007 // induced Schreyer order.
3008 // The corresponding orders are computed in sbaRing(), depending
3009 // on the flag strat->sbaOrder
3010#if SBA_PRINT_ZERO_REDUCTIONS
3011 long zeroreductions = 0;
3012#endif
3013#if SBA_PRINT_PRODUCT_CRITERION
3014 long product_criterion = 0;
3015#endif
3016#if SBA_PRINT_SIZE_G
3017 int size_g = 0;
3018 int size_g_non_red = 0;
3019#endif
3020#if SBA_PRINT_SIZE_SYZ
3021 long size_syz = 0;
3022#endif
3023 // global variable
3024#if SBA_PRINT_REDUCTION_STEPS
3025 sba_reduction_steps = 0;
3026 sba_interreduction_steps = 0;
3027#endif
3028#if SBA_PRINT_OPERATIONS
3029 sba_operations = 0;
3030 sba_interreduction_operations = 0;
3031#endif
3032
3033 ideal F1 = F0;
3034 ring sRing, currRingOld;
3035 currRingOld = currRing;
3036 if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
3037 {
3038 sRing = sbaRing(strat);
3039 if (sRing!=currRingOld)
3040 {
3041 rChangeCurrRing (sRing);
3042 F1 = idrMoveR (F0, currRingOld, currRing);
3043 }
3044 }
3045 ideal F;
3046 // sort ideal F
3047 //Put the SigDrop element on the correct position (think of sbaEnterS)
3048 //We also sort them
3049 if(rField_is_Ring(currRing) && strat->sigdrop)
3050 {
3051 #if 1
3052 F = idInit(IDELEMS(F1),F1->rank);
3053 for (int i=0; i<IDELEMS(F1);++i)
3054 F->m[i] = F1->m[i];
3055 if(strat->sbaEnterS >= 0)
3056 {
3057 poly dummy;
3058 dummy = pCopy(F->m[0]); //the sigdrop element
3059 for(int i = 0;i<strat->sbaEnterS;i++)
3060 F->m[i] = F->m[i+1];
3061 F->m[strat->sbaEnterS] = dummy;
3062 }
3063 #else
3064 F = idInit(1,F1->rank);
3065 //printf("\nBefore the initial block sorting:\n");idPrint(F1);
3066 F->m[0] = F1->m[0];
3067 int pos;
3068 if(strat->sbaEnterS >= 0)
3069 {
3070 for(int i=1;i<=strat->sbaEnterS;i++)
3071 {
3072 pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
3073 idInsertPolyOnPos(F,F1->m[i],pos);
3074 }
3075 for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
3076 {
3077 pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
3078 idInsertPolyOnPos(F,F1->m[i],pos);
3079 }
3080 poly dummy;
3081 dummy = pCopy(F->m[0]); //the sigdrop element
3082 for(int i = 0;i<strat->sbaEnterS;i++)
3083 F->m[i] = F->m[i+1];
3084 F->m[strat->sbaEnterS] = dummy;
3085 }
3086 else
3087 {
3088 for(int i=1;i<IDELEMS(F1);i++)
3089 {
3090 pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
3091 idInsertPolyOnPos(F,F1->m[i],pos);
3092 }
3093 }
3094 #endif
3095 //printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
3096 }
3097 else
3098 {
3099 F = idInit(IDELEMS(F1),F1->rank);
3100 intvec *sort = idSort(F1);
3101 for (int i=0; i<sort->length();++i)
3102 F->m[i] = F1->m[(*sort)[i]-1];
3104 {
3105 // put the monomials after the sbaEnterS polynomials
3106 //printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
3107 int nrmon = 0;
3108 for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
3109 {
3110 //pWrite(F->m[i]);
3111 if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
3112 {
3113 poly mon = F->m[i];
3114 for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
3115 {
3116 F->m[j] = F->m[j-1];
3117 }
3118 F->m[j] = mon;
3119 nrmon++;
3120 }
3121 //idPrint(F);
3122 }
3123 }
3124 }
3125 //printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
3127 strat->sigdrop = FALSE;
3128 strat->nrsyzcrit = 0;
3129 strat->nrrewcrit = 0;
3130#if SBA_INTERRED_START
3131 F = kInterRed(F,NULL);
3132#endif
3133#if F5DEBUG
3134 printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
3135 rWrite (currRing);
3136 printf("ordSgn = %d\n",currRing->OrdSgn);
3137 printf("\n");
3138#endif
3139 int srmax,lrmax, red_result = 1;
3140 int olddeg,reduc;
3141 int hilbeledeg=1,hilbcount=0,minimcnt=0;
3142 LObject L;
3143 BOOLEAN withT = TRUE;
3144 strat->max_lower_index = 0;
3145 //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3146 initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
3147 initSbaPos(strat);
3148 initHilbCrit(F,Q,&hilb,strat);
3149 initSba(F,strat);
3150 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3151 /*Shdl=*/initSbaBuchMora(F, Q,strat);
3152 idTest(strat->Shdl);
3153 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
3154 srmax = strat->sl;
3155 reduc = olddeg = lrmax = 0;
3156#ifndef NO_BUCKETS
3158 strat->use_buckets = 1;
3159#endif
3160
3161 // redtailBBa against T for inhomogeneous input
3162 // if (!TEST_OPT_OLDSTD)
3163 // withT = ! strat->homog;
3164
3165 // strat->posInT = posInT_pLength;
3166 kTest_TS(strat);
3167
3168#ifdef HAVE_TAIL_RING
3169 if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
3171#endif
3172 if (BVERBOSE(23))
3173 {
3174 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
3175 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
3176 kDebugPrint(strat);
3177 }
3178 // We add the elements directly in S from the previous loop
3179 if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
3180 {
3181 for(int i = 0;i<strat->sbaEnterS;i++)
3182 {
3183 //Update: now the element is at the correct place
3184 //i+1 because on the 0 position is the sigdrop element
3185 enterT(strat->L[strat->Ll-(i)],strat);
3186 strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
3187 }
3188 strat->Ll = strat->Ll - strat->sbaEnterS;
3189 strat->sbaEnterS = -1;
3190 }
3191 kTest_TS(strat);
3192#ifdef KDEBUG
3193 //kDebugPrint(strat);
3194#endif
3195 /* compute------------------------------------------------------- */
3196 while (strat->Ll >= 0)
3197 {
3198 if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
3199 #ifdef KDEBUG
3200 if (TEST_OPT_DEBUG) messageSets(strat);
3201 #endif
3202 if (strat->Ll== 0) strat->interpt=TRUE;
3203 /*
3204 if (TEST_OPT_DEGBOUND
3205 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3206 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
3207 {
3208
3209 //stops computation if
3210 // 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
3211 //a predefined number Kstd1_deg
3212 while ((strat->Ll >= 0)
3213 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
3214 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3215 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
3216 )
3217 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
3218 if (strat->Ll<0) break;
3219 else strat->noClearS=TRUE;
3220 }
3221 */
3222 if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
3223 {
3224 strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
3225#if F5C
3226 // 1. interreduction of the current standard basis
3227 // 2. generation of new principal syzygy rules for syzCriterion
3228 f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
3229 lrmax, reduc, Q, w, hilb );
3230#endif
3231 // initialize new syzygy rules for the next iteration step
3232 initSyzRules(strat);
3233 }
3234 /*********************************************************************
3235 * interrreduction step is done, we can go on with the next iteration
3236 * step of the signature-based algorithm
3237 ********************************************************************/
3238 /* picks the last element from the lazyset L */
3239 strat->P = strat->L[strat->Ll];
3240 strat->Ll--;
3241
3243 strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
3244 /* reduction of the element chosen from L */
3245 if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
3246 {
3247 //#if 1
3248#ifdef DEBUGF5
3249 PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
3250 PrintS("-------------------------------------------------\n");
3251 pWrite(strat->P.sig);
3252 pWrite(pHead(strat->P.p));
3253 pWrite(pHead(strat->P.p1));
3254 pWrite(pHead(strat->P.p2));
3255 PrintS("-------------------------------------------------\n");
3256#endif
3257 if (pNext(strat->P.p) == strat->tail)
3258 {
3259 // deletes the short spoly
3260 /*
3261 if (rField_is_Ring(currRing))
3262 pLmDelete(strat->P.p);
3263 else
3264 pLmFree(strat->P.p);
3265*/
3266 // TODO: needs some masking
3267 // TODO: masking needs to vanish once the signature
3268 // sutff is completely implemented
3269 strat->P.p = NULL;
3270 poly m1 = NULL, m2 = NULL;
3271
3272 // check that spoly creation is ok
3273 while (strat->tailRing != currRing &&
3274 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3275 {
3276 assume(m1 == NULL && m2 == NULL);
3277 // if not, change to a ring where exponents are at least
3278 // large enough
3279 if (!kStratChangeTailRing(strat))
3280 {
3281 WerrorS("OVERFLOW...");
3282 break;
3283 }
3284 }
3285 // create the real one
3286 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3287 strat->tailRing, m1, m2, strat->R);
3288
3289 }
3290 else if (strat->P.p1 == NULL)
3291 {
3292 if (strat->minim > 0)
3293 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3294 // for input polys, prepare reduction
3296 strat->P.PrepareRed(strat->use_buckets);
3297 }
3298 if (strat->P.p == NULL && strat->P.t_p == NULL)
3299 {
3300 red_result = 0;
3301 }
3302 else
3303 {
3304 //#if 1
3305#ifdef DEBUGF5
3306 PrintS("Poly before red: ");
3307 pWrite(pHead(strat->P.p));
3308 pWrite(strat->P.sig);
3309#endif
3310#if SBA_PRODUCT_CRITERION
3311 if (strat->P.prod_crit)
3312 {
3313#if SBA_PRINT_PRODUCT_CRITERION
3314 product_criterion++;
3315#endif
3316 int pos = posInSyz(strat, strat->P.sig);
3317 enterSyz(strat->P, strat, pos);
3318 kDeleteLcm(&strat->P);
3319 red_result = 2;
3320 }
3321 else
3322 {
3323 red_result = strat->red(&strat->P,strat);
3324 }
3325#else
3326 red_result = strat->red(&strat->P,strat);
3327#endif
3328 }
3329 }
3330 else
3331 {
3332 /*
3333 if (strat->P.lcm != NULL)
3334 pLmFree(strat->P.lcm);
3335 */
3336 red_result = 2;
3337 }
3339 {
3340 if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3341 {
3342 strat->P.p = pNeg(strat->P.p);
3343 strat->P.sig = pNeg(strat->P.sig);
3344 }
3345 strat->P.pLength = pLength(strat->P.p);
3346 if(strat->P.sig != NULL)
3347 strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3348 if(strat->P.p != NULL)
3349 strat->P.sev = pGetShortExpVector(strat->P.p);
3350 }
3351 //sigdrop case
3352 if(rField_is_Ring(currRing) && strat->sigdrop)
3353 {
3354 //First reduce it as much as one can
3355 red_result = redRing(&strat->P,strat);
3356 if(red_result == 0)
3357 {
3358 strat->sigdrop = FALSE;
3359 pDelete(&strat->P.sig);
3360 strat->P.sig = NULL;
3361 }
3362 else
3363 {
3364 strat->enterS(strat->P, 0, strat, strat->tl);
3365 if (TEST_OPT_PROT)
3366 PrintS("-");
3367 break;
3368 }
3369 }
3370 if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3371 {
3372 strat->sigdrop = TRUE;
3373 break;
3374 }
3375
3376 if (errorreported) break;
3377
3378//#if 1
3379#ifdef DEBUGF5
3380 if (red_result != 0)
3381 {
3382 PrintS("Poly after red: ");
3383 pWrite(pHead(strat->P.p));
3384 pWrite(strat->P.GetLmCurrRing());
3385 pWrite(strat->P.sig);
3386 printf("%d\n",red_result);
3387 }
3388#endif
3389 if (TEST_OPT_PROT)
3390 {
3391 if(strat->P.p != NULL)
3392 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3393 &olddeg,&reduc,strat, red_result);
3394 else
3395 message((strat->honey ? strat->P.ecart : 0),
3396 &olddeg,&reduc,strat, red_result);
3397 }
3398
3399 if (strat->overflow)
3400 {
3401 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3402 }
3403 // reduction to non-zero new poly
3404 if (red_result == 1)
3405 {
3406 // get the polynomial (canonicalize bucket, make sure P.p is set)
3407 strat->P.GetP(strat->lmBin);
3408
3409 // sig-safe computations may lead to wrong FDeg computation, thus we need
3410 // to recompute it to make sure everything is alright
3411 (strat->P).FDeg = (strat->P).pFDeg();
3412 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
3413 // but now, for entering S, T, we reset it
3414 // in the inhomogeneous case: FDeg == pFDeg
3415 if (strat->homog) strat->initEcart(&(strat->P));
3416
3417 /* statistic */
3418 if (TEST_OPT_PROT) PrintS("s");
3419
3420 //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3421 // in F5E we know that the last reduced element is already the
3422 // the one with highest signature
3423 int pos = strat->sl+1;
3424
3425 // reduce the tail and normalize poly
3426 // in the ring case we cannot expect LC(f) = 1,
3427 #ifdef HAVE_RINGS
3428 poly beforetailred;
3430 beforetailred = pCopy(strat->P.sig);
3431 #endif
3432#if SBA_TAIL_RED
3434 {
3436 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3437 }
3438 else
3439 {
3440 if (strat->sbaOrder != 2)
3441 {
3443 {
3444 strat->P.pCleardenom();
3446 {
3447 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3448 strat->P.pCleardenom();
3449 }
3450 }
3451 else
3452 {
3453 strat->P.pNorm();
3455 strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3456 }
3457 }
3458 }
3459 // It may happen that we have lost the sig in redtailsba
3460 // It cannot reduce to 0 since here we are doing just tail reduction.
3461 // Best case scenerio: remains the leading term
3462 if(rField_is_Ring(currRing) && strat->sigdrop)
3463 {
3464 strat->enterS(strat->P, 0, strat, strat->tl);
3465 break;
3466 }
3467#endif
3469 {
3470 if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
3471 {
3472 strat->sigdrop = TRUE;
3473 //Reduce it as much as you can
3474 red_result = redRing(&strat->P,strat);
3475 if(red_result == 0)
3476 {
3477 //It reduced to 0, cancel the sigdrop
3478 strat->sigdrop = FALSE;
3479 p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3480 }
3481 else
3482 {
3483 strat->enterS(strat->P, 0, strat, strat->tl);
3484 break;
3485 }
3486 }
3487 p_Delete(&beforetailred,currRing);
3488 // strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3489 if(strat->P.p == NULL)
3490 goto case_when_red_result_changed;
3491 }
3492 // remove sigsafe label since it is no longer valid for the next element to
3493 // be reduced
3494 if (strat->sbaOrder == 1)
3495 {
3496 for (int jj = 0; jj<strat->tl+1; jj++)
3497 {
3498 if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3499 {
3500 strat->T[jj].is_sigsafe = FALSE;
3501 }
3502 }
3503 }
3504 else
3505 {
3506 for (int jj = 0; jj<strat->tl+1; jj++)
3507 {
3508 strat->T[jj].is_sigsafe = FALSE;
3509 }
3510 }
3511#ifdef KDEBUG
3512 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3513#endif /* KDEBUG */
3514
3515 // min_std stuff
3516 if ((strat->P.p1==NULL) && (strat->minim>0))
3517 {
3518 if (strat->minim==1)
3519 {
3520 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3521 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3522 }
3523 else
3524 {
3525 strat->M->m[minimcnt]=strat->P.p2;
3526 strat->P.p2=NULL;
3527 }
3528 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3529 pNext(strat->M->m[minimcnt])
3530 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3531 strat->tailRing, currRing,
3532 currRing->PolyBin);
3533 minimcnt++;
3534 }
3535
3536 // enter into S, L, and T
3537 //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3538 enterT(strat->P, strat);
3539 strat->T[strat->tl].is_sigsafe = FALSE;
3540 /*
3541 printf("hier\n");
3542 pWrite(strat->P.GetLmCurrRing());
3543 pWrite(strat->P.sig);
3544 */
3546 superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3547 else
3548 enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3549 if(rField_is_Ring(currRing) && strat->sigdrop)
3550 break;
3552 strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3553 strat->enterS(strat->P, pos, strat, strat->tl);
3554 if(strat->sbaOrder != 1)
3555 {
3556 BOOLEAN overwrite = FALSE;
3557 for (int tk=0; tk<strat->sl+1; tk++)
3558 {
3559 if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3560 {
3561 //printf("TK %d / %d\n",tk,strat->sl);
3562 overwrite = FALSE;
3563 break;
3564 }
3565 }
3566 //printf("OVERWRITE %d\n",overwrite);
3567 if (overwrite)
3568 {
3569 int cmp = pGetComp(strat->P.sig);
3570 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3571 p_GetExpV (strat->P.p,vv,currRing);
3572 p_SetExpV (strat->P.sig, vv,currRing);
3573 p_SetComp (strat->P.sig,cmp,currRing);
3574
3575 strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3576 int i;
3577 LObject Q;
3578 for(int ps=0;ps<strat->sl+1;ps++)
3579 {
3580
3581 strat->newt = TRUE;
3582 if (strat->syzl == strat->syzmax)
3583 {
3584 pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3585 strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3586 (strat->syzmax)*sizeof(unsigned long),
3587 ((strat->syzmax)+setmaxTinc)
3588 *sizeof(unsigned long));
3589 strat->syzmax += setmaxTinc;
3590 }
3591 Q.sig = pCopy(strat->P.sig);
3592 // add LM(F->m[i]) to the signature to get a Schreyer order
3593 // without changing the underlying polynomial ring at all
3594 if (strat->sbaOrder == 0)
3595 p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3596 // since p_Add_q() destroys all input
3597 // data we need to recreate help
3598 // each time
3599 // ----------------------------------------------------------
3600 // in the Schreyer order we always know that the multiplied
3601 // module monomial strat->P.sig gives the leading monomial of
3602 // the corresponding principal syzygy
3603 // => we do not need to compute the "real" syzygy completely
3604 poly help = p_Copy(strat->sig[ps],currRing);
3605 p_ExpVectorAdd (help,strat->P.p,currRing);
3606 Q.sig = p_Add_q(Q.sig,help,currRing);
3607 //printf("%d. SYZ ",i+1);
3608 //pWrite(strat->syz[i]);
3609 Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3610 i = posInSyz(strat, Q.sig);
3611 enterSyz(Q, strat, i);
3612 }
3613 }
3614 }
3615 // deg - idx - lp/rp
3616 // => we need to add syzygies with indices > pGetComp(strat->P.sig)
3617 if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
3618 {
3619 int cmp = pGetComp(strat->P.sig);
3620 unsigned max_cmp = IDELEMS(F);
3621 int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
3622 p_GetExpV (strat->P.p,vv,currRing);
3623 LObject Q;
3624 int pos;
3625 int idx = __p_GetComp(strat->P.sig,currRing);
3626 //printf("++ -- adding syzygies -- ++\n");
3627 // if new element is the first one in this index
3628 if (strat->currIdx < idx)
3629 {
3630 for (int i=0; i<strat->sl; ++i)
3631 {
3632 Q.sig = p_Copy(strat->P.sig,currRing);
3633 p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3634 poly help = p_Copy(strat->sig[i],currRing);
3635 p_ExpVectorAdd(help,strat->P.p,currRing);
3636 Q.sig = p_Add_q(Q.sig,help,currRing);
3637 //pWrite(Q.sig);
3638 pos = posInSyz(strat, Q.sig);
3639 enterSyz(Q, strat, pos);
3640 }
3641 strat->currIdx = idx;
3642 }
3643 else
3644 {
3645 // if the element is not the first one in the given index we build all
3646 // possible syzygies with elements of higher index
3647 for (unsigned i=cmp+1; i<=max_cmp; ++i)
3648 {
3649 pos = -1;
3650 for (int j=0; j<strat->sl; ++j)
3651 {
3652 if (__p_GetComp(strat->sig[j],currRing) == i)
3653 {
3654 pos = j;
3655 break;
3656 }
3657 }
3658 if (pos != -1)
3659 {
3660 Q.sig = p_One(currRing);
3661 p_SetExpV(Q.sig, vv, currRing);
3662 // F->m[i-1] corresponds to index i
3663 p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3664 p_SetComp(Q.sig, i, currRing);
3665 poly help = p_Copy(strat->P.sig,currRing);
3666 p_ExpVectorAdd(help,strat->S[pos],currRing);
3667 Q.sig = p_Add_q(Q.sig,help,currRing);
3668 if (strat->sbaOrder == 0)
3669 {
3670 if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3671 {
3672 pos = posInSyz(strat, Q.sig);
3673 enterSyz(Q, strat, pos);
3674 }
3675 }
3676 else
3677 {
3678 pos = posInSyz(strat, Q.sig);
3679 enterSyz(Q, strat, pos);
3680 }
3681 }
3682 }
3683 //printf("++ -- done adding syzygies -- ++\n");
3684 }
3685 }
3686//#if 1
3687#if DEBUGF50
3688 printf("---------------------------\n");
3689 Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3690 PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3691 PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3692#endif
3693 /*
3694 if (newrules)
3695 {
3696 newrules = FALSE;
3697 }
3698 */
3699#if 0
3700 int pl=pLength(strat->P.p);
3701 if (pl==1)
3702 {
3703 //if (TEST_OPT_PROT)
3704 //PrintS("<1>");
3705 }
3706 else if (pl==2)
3707 {
3708 //if (TEST_OPT_PROT)
3709 //PrintS("<2>");
3710 }
3711#endif
3712 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3713// Print("[%d]",hilbeledeg);
3714 kDeleteLcm(&strat->P);
3715 if (strat->sl>srmax) srmax = strat->sl;
3716 }
3717 else
3718 {
3719 case_when_red_result_changed:
3720 // adds signature of the zero reduction to
3721 // strat->syz. This is the leading term of
3722 // syzygy and can be used in syzCriterion()
3723 // the signature is added if and only if the
3724 // pair was not detected by the rewritten criterion in strat->red = redSig
3725 if (red_result!=2)
3726 {
3727#if SBA_PRINT_ZERO_REDUCTIONS
3728 zeroreductions++;
3729#endif
3730 if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3731 {
3732 //Catch the case when p = 0, sig = 0
3733 }
3734 else
3735 {
3736 int pos = posInSyz(strat, strat->P.sig);
3737 enterSyz(strat->P, strat, pos);
3738 //#if 1
3739 #ifdef DEBUGF5
3740 Print("ADDING STUFF TO SYZ : ");
3741 //pWrite(strat->P.p);
3742 pWrite(strat->P.sig);
3743 #endif
3744 }
3745 }
3746 if (strat->P.p1 == NULL && strat->minim > 0)
3747 {
3748 p_Delete(&strat->P.p2, currRing, strat->tailRing);
3749 }
3750 }
3751
3752#ifdef KDEBUG
3753 memset(&(strat->P), 0, sizeof(strat->P));
3754#endif /* KDEBUG */
3755 kTest_TS(strat);
3756 }
3757 #if 0
3758 if(strat->sigdrop)
3759 printf("\nSigDrop!\n");
3760 else
3761 printf("\nEnded with no SigDrop\n");
3762 #endif
3763// Clean strat->P for the next sba call
3764 if(rField_is_Ring(currRing) && strat->sigdrop)
3765 {
3766 //This is used to know how many elements can we directly add to S in the next run
3767 if(strat->P.sig != NULL)
3768 strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3769 //else we already set it at the beginning of the loop
3770 #ifdef KDEBUG
3771 memset(&(strat->P), 0, sizeof(strat->P));
3772 #endif /* KDEBUG */
3773 }
3774#ifdef KDEBUG
3775 if (TEST_OPT_DEBUG) messageSets(strat);
3776#endif /* KDEBUG */
3777
3778 if (TEST_OPT_SB_1)
3779 {
3781 {
3782 int k=1;
3783 int j;
3784 while(k<=strat->sl)
3785 {
3786 j=0;
3787 loop
3788 {
3789 if (j>=k) break;
3790 clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3791 j++;
3792 }
3793 k++;
3794 }
3795 }
3796 }
3797 /* complete reduction of the standard basis--------- */
3798 if (TEST_OPT_REDSB)
3799 {
3800 completeReduce(strat);
3801 if (strat->completeReduce_retry)
3802 {
3803 // completeReduce needed larger exponents, retry
3804 // to reduce with S (instead of T)
3805 // and in currRing (instead of strat->tailRing)
3806#ifdef HAVE_TAIL_RING
3807 if(currRing->bitmask>strat->tailRing->bitmask)
3808 {
3810 cleanT(strat);strat->tailRing=currRing;
3811 int i;
3812 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3813 completeReduce(strat);
3814 }
3815 if (strat->completeReduce_retry)
3816#endif
3817 Werror("exponent bound is %ld",currRing->bitmask);
3818 }
3819 }
3820 else if (TEST_OPT_PROT) PrintLn();
3821
3822#if SBA_PRINT_SIZE_SYZ
3823 // that is correct, syzl is counting one too far
3824 size_syz = strat->syzl;
3825#endif
3826// if (TEST_OPT_WEIGHTM)
3827// {
3828// pRestoreDegProcs(pFDegOld, pLDegOld);
3829// if (ecartWeights)
3830// {
3831// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3832// ecartWeights=NULL;
3833// }
3834// }
3835 if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3836 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3837#if SBA_PRINT_SIZE_G
3838 size_g_non_red = IDELEMS(strat->Shdl);
3839#endif
3841 exitSba(strat);
3842 // I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3843 #ifdef HAVE_RINGS
3844 int k;
3846 {
3847 //for(k = strat->sl;k>=0;k--)
3848 // {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3849 k = strat->Ll;
3850 #if 1
3851 // 1 - adds just the unused ones, 0 - adds everything
3852 for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
3853 {
3854 //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);
3855 deleteInL(strat->L,&strat->Ll,k,strat);
3856 }
3857 #endif
3858 //for(int kk = strat->sl;kk>=0;kk--)
3859 // {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3860 //idPrint(strat->Shdl);
3861 //printf("\nk = %i\n",k);
3862 for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3863 {
3864 //printf("\nAdded k = %i\n",k);
3865 strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3866 //printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3867 }
3868 }
3869 // 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
3870 #if 0
3871 if(strat->sigdrop && rField_is_Ring(currRing))
3872 {
3873 for(k=strat->sl;k>=0;k--)
3874 {
3875 printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3876 if(strat->sig[k] == NULL)
3877 strat->sig[k] = pCopy(strat->sig[k-1]);
3878 }
3879 }
3880 #endif
3881 #endif
3882 //Never do this - you will damage S
3883 //idSkipZeroes(strat->Shdl);
3884 //idPrint(strat->Shdl);
3885
3886 if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
3887 {
3888 rChangeCurrRing (currRingOld);
3889 F0 = idrMoveR (F1, sRing, currRing);
3890 strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3891 rChangeCurrRing (sRing);
3893 exitSba(strat);
3894 rChangeCurrRing (currRingOld);
3895 if(strat->tailRing == sRing)
3896 strat->tailRing = currRing;
3897 rDelete (sRing);
3898 }
3899 if(rField_is_Ring(currRing) && !strat->sigdrop)
3900 id_DelDiv(strat->Shdl, currRing);
3902 id_DelDiv(strat->Shdl, currRing);
3903 idSkipZeroes(strat->Shdl);
3904 idTest(strat->Shdl);
3905
3906#if SBA_PRINT_SIZE_G
3907 size_g = IDELEMS(strat->Shdl);
3908#endif
3909#ifdef DEBUGF5
3910 printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3911 int oo = 0;
3912 while (oo<IDELEMS(strat->Shdl))
3913 {
3914 printf(" %d. ",oo+1);
3915 pWrite(pHead(strat->Shdl->m[oo]));
3916 oo++;
3917 }
3918#endif
3919#if SBA_PRINT_ZERO_REDUCTIONS
3920 printf("----------------------------------------------------------\n");
3921 printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3922 zeroreductions = 0;
3923#endif
3924#if SBA_PRINT_REDUCTION_STEPS
3925 printf("----------------------------------------------------------\n");
3926 printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3927#endif
3928#if SBA_PRINT_OPERATIONS
3929 printf("OPERATIONS: %ld\n",sba_operations);
3930#endif
3931#if SBA_PRINT_REDUCTION_STEPS
3932 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3933 printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3934#endif
3935#if SBA_PRINT_OPERATIONS
3936 printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3937#endif
3938#if SBA_PRINT_REDUCTION_STEPS
3939 printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3940 printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3941 sba_interreduction_steps = 0;
3942 sba_reduction_steps = 0;
3943#endif
3944#if SBA_PRINT_OPERATIONS
3945 printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3946 sba_interreduction_operations = 0;
3947 sba_operations = 0;
3948#endif
3949#if SBA_PRINT_SIZE_G
3950 printf("----------------------------------------------------------\n");
3951 printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3952 size_g = 0;
3953 size_g_non_red = 0;
3954#endif
3955#if SBA_PRINT_SIZE_SYZ
3956 printf("SIZE OF SYZ: %ld\n",size_syz);
3957 printf("----------------------------------------------------------\n");
3958 size_syz = 0;
3959#endif
3960#if SBA_PRINT_PRODUCT_CRITERION
3961 printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3962 product_criterion = 0;
3963#endif
3964 return (strat->Shdl);
3965}
3966
3967poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3968{
3969 assume(q!=NULL);
3970 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3971
3972// lazy_reduce flags: can be combined by |
3973//#define KSTD_NF_LAZY 1
3974 // do only a reduction of the leading term
3975//#define KSTD_NF_NONORM 4
3976 // only global: avoid normalization, return a multiply of NF
3977 poly p;
3978
3979 //if ((idIs0(F))&&(Q==NULL))
3980 // return pCopy(q); /*F=0*/
3981 //strat->ak = idRankFreeModule(F);
3982 /*- creating temp data structures------------------- -*/
3983 BITSET save1;
3984 SI_SAVE_OPT1(save1);
3986 initBuchMoraCrit(strat);
3987 strat->initEcart = initEcartBBA;
3988#ifdef HAVE_SHIFTBBA
3989 if (rIsLPRing(currRing))
3990 {
3991 strat->enterS = enterSBbaShift;
3992 }
3993 else
3994#endif
3995 {
3996 strat->enterS = enterSBba;
3997 }
3998#ifndef NO_BUCKETS
4000#endif
4001 /*- set S -*/
4002 strat->sl = -1;
4003 /*- init local data struct.---------------------------------------- -*/
4004 /*Shdl=*/initS(F,Q,strat);
4005 /*- compute------------------------------------------------------- -*/
4006 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
4007 //{
4008 // for (i=strat->sl;i>=0;i--)
4009 // pNorm(strat->S[i]);
4010 //}
4011 kTest(strat);
4012 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
4013 if (BVERBOSE(23)) kDebugPrint(strat);
4014 int max_ind;
4015 p = redNF(pCopy(q),max_ind,(lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4016 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4017 {
4018 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4020 {
4021 p = redtailBba_NF(p,strat);
4022 }
4023 else if (rField_is_Ring(currRing))
4024 {
4025 p = redtailBba_Ring(p,max_ind,strat);
4026 }
4027 else
4028 {
4029 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4030 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4031 }
4032 }
4033 /*- release temp data------------------------------- -*/
4034 assume(strat->L==NULL); /* strat->L unused */
4035 assume(strat->B==NULL); /* strat->B unused */
4036 omFree(strat->sevS);
4037 omFree(strat->ecartS);
4038 assume(strat->T==NULL);//omfree(strat->T);
4039 assume(strat->sevT==NULL);//omfree(strat->sevT);
4040 assume(strat->R==NULL);//omfree(strat->R);
4041 omfree(strat->S_2_R);
4042 omfree(strat->fromQ);
4043 idDelete(&strat->Shdl);
4044 SI_RESTORE_OPT1(save1);
4045 if (TEST_OPT_PROT) PrintLn();
4046 return p;
4047}
4048
4049poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
4050{
4051 assume(q!=NULL);
4052 assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
4053
4054// lazy_reduce flags: can be combined by |
4055//#define KSTD_NF_LAZY 1
4056 // do only a reduction of the leading term
4057//#define KSTD_NF_NONORM 4
4058 // only global: avoid normalization, return a multiply of NF
4059 poly p;
4060
4061 //if ((idIs0(F))&&(Q==NULL))
4062 // return pCopy(q); /*F=0*/
4063 //strat->ak = idRankFreeModule(F);
4064 /*- creating temp data structures------------------- -*/
4065 BITSET save1;
4066 SI_SAVE_OPT1(save1);
4068 initBuchMoraCrit(strat);
4069 strat->initEcart = initEcartBBA;
4070 strat->enterS = enterSBba;
4071#ifndef NO_BUCKETS
4073#endif
4074 /*- set S -*/
4075 strat->sl = -1;
4076 /*- init local data struct.---------------------------------------- -*/
4077 /*Shdl=*/initS(F,Q,strat);
4078 /*- compute------------------------------------------------------- -*/
4079 //if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
4080 //{
4081 // for (i=strat->sl;i>=0;i--)
4082 // pNorm(strat->S[i]);
4083 //}
4084 kTest(strat);
4085 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
4086 if (BVERBOSE(23)) kDebugPrint(strat);
4087 int max_ind;
4088 p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
4089 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4090 {
4091 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4093 {
4094 p = redtailBba_Z(p,max_ind,strat);
4095 }
4096 else if (rField_is_Ring(currRing))
4097 {
4098 p = redtailBba_Ring(p,max_ind,strat);
4099 }
4100 else
4101 {
4102 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4103 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4104 //p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4105 }
4106 }
4107 /*- release temp data------------------------------- -*/
4108 assume(strat->L==NULL); /* strat->L unused */
4109 assume(strat->B==NULL); /* strat->B unused */
4110 omFree(strat->sevS);
4111 omFree(strat->ecartS);
4112 assume(strat->T==NULL);//omfree(strat->T);
4113 assume(strat->sevT==NULL);//omfree(strat->sevT);
4114 assume(strat->R==NULL);//omfree(strat->R);
4115 omfree(strat->S_2_R);
4116 omfree(strat->fromQ);
4117 idDelete(&strat->Shdl);
4118 SI_RESTORE_OPT1(save1);
4119 if (TEST_OPT_PROT) PrintLn();
4120 return p;
4121}
4122
4123ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
4124{
4125 assume(!idIs0(q));
4126 assume(!(idIs0(F)&&(Q==NULL)));
4127// lazy_reduce flags: can be combined by |
4128//#define KSTD_NF_LAZY 1
4129 // do only a reduction of the leading term
4130//#define KSTD_NF_NONORM 4
4131 // only global: avoid normalization, return a multiply of NF
4132 poly p;
4133 int i;
4134 ideal res;
4135 int max_ind;
4136
4137 //if (idIs0(q))
4138 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4139 //if ((idIs0(F))&&(Q==NULL))
4140 // return idCopy(q); /*F=0*/
4141 //strat->ak = idRankFreeModule(F);
4142 /*- creating temp data structures------------------- -*/
4143 BITSET save1;
4144 SI_SAVE_OPT1(save1);
4146 initBuchMoraCrit(strat);
4147 strat->initEcart = initEcartBBA;
4148#ifdef HAVE_SHIFTBBA
4149 if (rIsLPRing(currRing))
4150 {
4151 strat->enterS = enterSBbaShift;
4152 }
4153 else
4154#endif
4155 {
4156 strat->enterS = enterSBba;
4157 }
4158 /*- set S -*/
4159 strat->sl = -1;
4160#ifndef NO_BUCKETS
4162#endif
4163 /*- init local data struct.---------------------------------------- -*/
4164 /*Shdl=*/initS(F,Q,strat);
4165 /*- compute------------------------------------------------------- -*/
4166 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4167 for (i=IDELEMS(q)-1; i>=0; i--)
4168 {
4169 if (q->m[i]!=NULL)
4170 {
4171 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4172 p = redNF(pCopy(q->m[i]),max_ind,
4173 (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
4174 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4175 {
4176 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4178 {
4179 p = redtailBba_NF(p,strat);
4180 }
4181 else
4182 {
4183 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4184 p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
4185 }
4186 }
4187 res->m[i]=p;
4188 }
4189 //else
4190 // res->m[i]=NULL;
4191 }
4192 /*- release temp data------------------------------- -*/
4193 assume(strat->L==NULL); /* strat->L unused */
4194 assume(strat->B==NULL); /* strat->B unused */
4195 omFree(strat->sevS);
4196 omFree(strat->ecartS);
4197 assume(strat->T==NULL);//omfree(strat->T);
4198 assume(strat->sevT==NULL);//omfree(strat->sevT);
4199 assume(strat->R==NULL);//omfree(strat->R);
4200 omfree(strat->S_2_R);
4201 omfree(strat->fromQ);
4202 idDelete(&strat->Shdl);
4203 SI_RESTORE_OPT1(save1);
4204 if (TEST_OPT_PROT) PrintLn();
4205 return res;
4206}
4207
4208ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
4209{
4210 assume(!idIs0(q));
4211 assume(!(idIs0(F)&&(Q==NULL)));
4212// lazy_reduce flags: can be combined by |
4213//#define KSTD_NF_LAZY 1
4214 // do only a reduction of the leading term
4215//#define KSTD_NF_NONORM 4
4216 // only global: avoid normalization, return a multiply of NF
4217 poly p;
4218 int i;
4219 ideal res;
4220 int max_ind;
4221
4222 //if (idIs0(q))
4223 // return idInit(IDELEMS(q),si_max(q->rank,F->rank));
4224 //if ((idIs0(F))&&(Q==NULL))
4225 // return idCopy(q); /*F=0*/
4226 //strat->ak = idRankFreeModule(F);
4227 /*- creating temp data structures------------------- -*/
4228 BITSET save1;
4229 SI_SAVE_OPT1(save1);
4231 initBuchMoraCrit(strat);
4232 strat->initEcart = initEcartBBA;
4233 strat->enterS = enterSBba;
4234 /*- set S -*/
4235 strat->sl = -1;
4236#ifndef NO_BUCKETS
4238#endif
4239 /*- init local data struct.---------------------------------------- -*/
4240 /*Shdl=*/initS(F,Q,strat);
4241 /*- compute------------------------------------------------------- -*/
4242 res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
4243 for (i=IDELEMS(q)-1; i>=0; i--)
4244 {
4245 if (q->m[i]!=NULL)
4246 {
4247 if (TEST_OPT_PROT) { PrintS("r");mflush(); }
4248 p = redNFBound(pCopy(q->m[i]),max_ind,
4249 (lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat,bound);
4250 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
4251 {
4252 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4254 {
4255 p = redtailBba_Z(p,max_ind,strat);
4256 }
4257 else if (rField_is_Ring(currRing))
4258 {
4259 p = redtailBba_Ring(p,max_ind,strat);
4260 }
4261 else
4262 {
4263 si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
4264 p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4265 }
4266 }
4267 res->m[i]=p;
4268 }
4269 //else
4270 // res->m[i]=NULL;
4271 }
4272 /*- release temp data------------------------------- -*/
4273 assume(strat->L==NULL); /* strat->L unused */
4274 assume(strat->B==NULL); /* strat->B unused */
4275 omFree(strat->sevS);
4276 omFree(strat->ecartS);
4277 assume(strat->T==NULL);//omfree(strat->T);
4278 assume(strat->sevT==NULL);//omfree(strat->sevT);
4279 assume(strat->R==NULL);//omfree(strat->R);
4280 omfree(strat->S_2_R);
4281 omfree(strat->fromQ);
4282 idDelete(&strat->Shdl);
4283 SI_RESTORE_OPT1(save1);
4284 if (TEST_OPT_PROT) PrintLn();
4285 return res;
4286}
4287
4288#if F5C
4289/*********************************************************************
4290* interrreduction step of the signature-based algorithm:
4291* 1. all strat->S are interpreted as new critical pairs
4292* 2. those pairs need to be completely reduced by the usual (non sig-
4293* safe) reduction process (including tail reductions)
4294* 3. strat->S and strat->T are completely new computed in these steps
4295********************************************************************/
4296void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
4297 int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
4298 intvec *w,intvec *hilb )
4299{
4300 int Ll_old, red_result = 1;
4301 int pos = 0;
4302 hilbeledeg=1;
4303 hilbcount=0;
4304 minimcnt=0;
4305 srmax = 0; // strat->sl is 0 at this point
4306 reduc = olddeg = lrmax = 0;
4307 // we cannot use strat->T anymore
4308 //cleanT(strat);
4309 //strat->tl = -1;
4310 Ll_old = strat->Ll;
4311 while (strat->tl >= 0)
4312 {
4313 if(!strat->T[strat->tl].is_redundant)
4314 {
4315 LObject h;
4316 h.p = strat->T[strat->tl].p;
4317 h.tailRing = strat->T[strat->tl].tailRing;
4318 h.t_p = strat->T[strat->tl].t_p;
4319 if (h.p!=NULL)
4320 {
4321 if (currRing->OrdSgn==-1)
4322 {
4323 cancelunit(&h);
4324 deleteHC(&h, strat);
4325 }
4326 if (h.p!=NULL)
4327 {
4329 {
4330 h.pCleardenom(); // also does remove Content
4331 }
4332 else
4333 {
4334 h.pNorm();
4335 }
4336 strat->initEcart(&h);
4338 pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4339 else
4340 pos = strat->Ll+1;
4341 h.sev = pGetShortExpVector(h.p);
4342 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4343 }
4344 }
4345 }
4346 strat->tl--;
4347 }
4348 strat->sl = -1;
4349#if 0
4350//#ifdef HAVE_TAIL_RING
4351 if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4353#endif
4354 //enterpairs(pOne(),0,0,-1,strat,strat->tl);
4355 //strat->sl = -1;
4356 /* picks the last element from the lazyset L */
4357 while (strat->Ll>Ll_old)
4358 {
4359 strat->P = strat->L[strat->Ll];
4360 strat->Ll--;
4361//#if 1
4362#ifdef DEBUGF5
4363 PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4364 PrintS("-------------------------------------------------\n");
4365 pWrite(pHead(strat->P.p));
4366 pWrite(pHead(strat->P.p1));
4367 pWrite(pHead(strat->P.p2));
4368 printf("%d\n",strat->tl);
4369 PrintS("-------------------------------------------------\n");
4370#endif
4371 if (pNext(strat->P.p) == strat->tail)
4372 {
4373 // deletes the short spoly
4375 pLmDelete(strat->P.p);
4376 else
4377 pLmFree(strat->P.p);
4378
4379 // TODO: needs some masking
4380 // TODO: masking needs to vanish once the signature
4381 // sutff is completely implemented
4382 strat->P.p = NULL;
4383 poly m1 = NULL, m2 = NULL;
4384
4385 // check that spoly creation is ok
4386 while (strat->tailRing != currRing &&
4387 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4388 {
4389 assume(m1 == NULL && m2 == NULL);
4390 // if not, change to a ring where exponents are at least
4391 // large enough
4392 if (!kStratChangeTailRing(strat))
4393 {
4394 WerrorS("OVERFLOW...");
4395 break;
4396 }
4397 }
4398 // create the real one
4399 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4400 strat->tailRing, m1, m2, strat->R);
4401 }
4402 else if (strat->P.p1 == NULL)
4403 {
4404 if (strat->minim > 0)
4405 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4406 // for input polys, prepare reduction
4408 strat->P.PrepareRed(strat->use_buckets);
4409 }
4410
4411 if (strat->P.p == NULL && strat->P.t_p == NULL)
4412 {
4413 red_result = 0;
4414 }
4415 else
4416 {
4417 if (TEST_OPT_PROT)
4418 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4419 &olddeg,&reduc,strat, red_result);
4420
4421#ifdef DEBUGF5
4422 PrintS("Poly before red: ");
4423 pWrite(strat->P.p);
4424#endif
4425 /* complete reduction of the element chosen from L */
4426 red_result = strat->red2(&strat->P,strat);
4427 if (errorreported) break;
4428 }
4429
4430 if (strat->overflow)
4431 {
4432 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4433 }
4434
4435 // reduction to non-zero new poly
4436 if (red_result == 1)
4437 {
4438 // get the polynomial (canonicalize bucket, make sure P.p is set)
4439 strat->P.GetP(strat->lmBin);
4440 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4441 // but now, for entering S, T, we reset it
4442 // in the inhomogeneous case: FDeg == pFDeg
4443 if (strat->homog) strat->initEcart(&(strat->P));
4444
4445 /* statistic */
4446 if (TEST_OPT_PROT) PrintS("s");
4447 int pos;
4448 #if 1
4450 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4451 else
4452 pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4453 #else
4454 pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4455 #endif
4456 // reduce the tail and normalize poly
4457 // in the ring case we cannot expect LC(f) = 1,
4458#if F5CTAILRED
4459 BOOLEAN withT = TRUE;
4461 {
4462 strat->P.pCleardenom();
4464 {
4465 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4466 strat->P.pCleardenom();
4467 }
4468 }
4469 else
4470 {
4471 strat->P.pNorm();
4473 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4474 }
4475#endif
4476#ifdef KDEBUG
4477 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4478#endif /* KDEBUG */
4479
4480 // min_std stuff
4481 if ((strat->P.p1==NULL) && (strat->minim>0))
4482 {
4483 if (strat->minim==1)
4484 {
4485 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4486 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4487 }
4488 else
4489 {
4490 strat->M->m[minimcnt]=strat->P.p2;
4491 strat->P.p2=NULL;
4492 }
4493 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4494 pNext(strat->M->m[minimcnt])
4495 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4496 strat->tailRing, currRing,
4497 currRing->PolyBin);
4498 minimcnt++;
4499 }
4500
4501 // enter into S, L, and T
4502 // here we need to recompute new signatures, but those are trivial ones
4503 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4504 {
4505 enterT(strat->P, strat);
4506 // posInS only depends on the leading term
4507 strat->enterS(strat->P, pos, strat, strat->tl);
4508//#if 1
4509#ifdef DEBUGF5
4510 PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4511 pWrite(pHead(strat->S[strat->sl]));
4512 pWrite(strat->sig[strat->sl]);
4513#endif
4514 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4515 }
4516 // Print("[%d]",hilbeledeg);
4517 kDeleteLcm(&strat->P);
4518 if (strat->sl>srmax) srmax = strat->sl;
4519 }
4520 else
4521 {
4522 // adds signature of the zero reduction to
4523 // strat->syz. This is the leading term of
4524 // syzygy and can be used in syzCriterion()
4525 // the signature is added if and only if the
4526 // pair was not detected by the rewritten criterion in strat->red = redSig
4527 if (strat->P.p1 == NULL && strat->minim > 0)
4528 {
4529 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4530 }
4531 }
4532
4533#ifdef KDEBUG
4534 memset(&(strat->P), 0, sizeof(strat->P));
4535#endif /* KDEBUG */
4536 }
4537 int cc = 0;
4538 while (cc<strat->tl+1)
4539 {
4540 strat->T[cc].sig = pOne();
4541 p_SetComp(strat->T[cc].sig,cc+1,currRing);
4542 strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4543 strat->sig[cc] = strat->T[cc].sig;
4544 strat->sevSig[cc] = strat->T[cc].sevSig;
4545 strat->T[cc].is_sigsafe = TRUE;
4546 cc++;
4547 }
4548 strat->max_lower_index = strat->tl;
4549 // set current signature index of upcoming iteration step
4550 // NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4551 // the corresponding syzygy rules correctly
4552 strat->currIdx = cc+1;
4553 for (int cd=strat->Ll; cd>=0; cd--)
4554 {
4555 p_SetComp(strat->L[cd].sig,cc+1,currRing);
4556 cc++;
4557 }
4558 for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4559 strat->Shdl->m[cc] = NULL;
4560 #if 0
4561 printf("\nAfter f5c sorting\n");
4562 for(int i=0;i<=strat->sl;i++)
4563 pWrite(pHead(strat->S[i]));
4564 getchar();
4565 #endif
4566//#if 1
4567#if DEBUGF5
4568 PrintS("------------------- STRAT S ---------------------\n");
4569 cc = 0;
4570 while (cc<strat->tl+1)
4571 {
4572 pWrite(pHead(strat->S[cc]));
4573 pWrite(strat->sig[cc]);
4574 printf("- - - - - -\n");
4575 cc++;
4576 }
4577 PrintS("-------------------------------------------------\n");
4578 PrintS("------------------- STRAT T ---------------------\n");
4579 cc = 0;
4580 while (cc<strat->tl+1)
4581 {
4582 pWrite(pHead(strat->T[cc].p));
4583 pWrite(strat->T[cc].sig);
4584 printf("- - - - - -\n");
4585 cc++;
4586 }
4587 PrintS("-------------------------------------------------\n");
4588 PrintS("------------------- STRAT L ---------------------\n");
4589 cc = 0;
4590 while (cc<strat->Ll+1)
4591 {
4592 pWrite(pHead(strat->L[cc].p));
4593 pWrite(pHead(strat->L[cc].p1));
4594 pWrite(pHead(strat->L[cc].p2));
4595 pWrite(strat->L[cc].sig);
4596 printf("- - - - - -\n");
4597 cc++;
4598 }
4599 PrintS("-------------------------------------------------\n");
4600 printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4601#endif
4602
4603}
4604#endif
4605
4606/* shiftgb stuff */
4607#ifdef HAVE_SHIFTBBA
4608ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
4609{
4610 int red_result = 1;
4611 int olddeg,reduc;
4612 int hilbeledeg=1,hilbcount=0,minimcnt=0;
4613 BOOLEAN withT = TRUE; // currently only T contains the shifts
4614 BITSET save;
4615 SI_SAVE_OPT1(save);
4616
4617 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
4619 initBuchMoraPosRing(strat);
4620 else
4621 initBuchMoraPos(strat);
4622 initHilbCrit(F,Q,&hilb,strat);
4623 initBba(strat);
4624 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
4625 /*Shdl=*/initBuchMora(F, Q,strat);
4626 if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4627 reduc = olddeg = 0;
4628
4629#ifndef NO_BUCKETS
4631 strat->use_buckets = 1;
4632#endif
4633 // redtailBBa against T for inhomogeneous input
4634 // if (!TEST_OPT_OLDSTD)
4635 // withT = ! strat->homog;
4636
4637 // strat->posInT = posInT_pLength;
4638 kTest_TS(strat);
4639
4640#ifdef HAVE_TAIL_RING
4641 // if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4642 // kStratInitChangeTailRing(strat);
4643 strat->tailRing=currRing;
4644#endif
4645 if (BVERBOSE(23))
4646 {
4647 if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4648 if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4649 kDebugPrint(strat);
4650 }
4651
4652#ifdef KDEBUG
4653 //kDebugPrint(strat);
4654#endif
4655 /* compute------------------------------------------------------- */
4656 while (strat->Ll >= 0)
4657 {
4658 #ifdef KDEBUG
4659 if (TEST_OPT_DEBUG) messageSets(strat);
4660 #endif
4661 if (siCntrlc)
4662 {
4663 while (strat->Ll >= 0)
4664 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4665 strat->noClearS=TRUE;
4666 }
4668 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4669 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4670 {
4671 /*
4672 *stops computation if
4673 * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4674 *a predefined number Kstd1_deg
4675 */
4676 while ((strat->Ll >= 0)
4677 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4678 && ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4679 || ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4680 )
4681 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4682 if (strat->Ll<0) break;
4683 else strat->noClearS=TRUE;
4684 }
4685 if (strat->Ll== 0) strat->interpt=TRUE;
4686 /* picks the last element from the lazyset L */
4687 strat->P = strat->L[strat->Ll];
4688 strat->Ll--;
4689
4690 if (pNext(strat->P.p) == strat->tail)
4691 {
4692 // deletes the short spoly
4694 pLmDelete(strat->P.p);
4695 else
4696 pLmFree(strat->P.p);
4697 strat->P.p = NULL;
4698 poly m1 = NULL, m2 = NULL;
4699
4700 // check that spoly creation is ok
4701 while (strat->tailRing != currRing &&
4702 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4703 {
4704 assume(m1 == NULL && m2 == NULL);
4705 // if not, change to a ring where exponents are at least
4706 // large enough
4707 if (!kStratChangeTailRing(strat))
4708 {
4709 WerrorS("OVERFLOW...");
4710 break;
4711 }
4712 }
4713 // create the real one
4714 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4715 strat->tailRing, m1, m2, strat->R);
4716 }
4717 else if (strat->P.p1 == NULL)
4718 {
4719 if (strat->minim > 0)
4720 strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4721 // for input polys, prepare reduction
4722 strat->P.PrepareRed(strat->use_buckets);
4723 }
4724
4725 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4726 {
4727 red_result = 0;
4728 }
4729 else
4730 {
4731 if (TEST_OPT_PROT)
4732 message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4733 &olddeg,&reduc,strat, red_result);
4734
4735 /* reduction of the element chosen from L */
4736 red_result = strat->red(&strat->P,strat);
4737 if (errorreported) break;
4738 }
4739
4740 if (strat->overflow)
4741 {
4742 if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4743 }
4744
4745 // reduction to non-zero new poly
4746 if (red_result == 1)
4747 {
4748 // get the polynomial (canonicalize bucket, make sure P.p is set)
4749 strat->P.GetP(strat->lmBin);
4750 // in the homogeneous case FDeg >= pFDeg (sugar/honey)
4751 // but now, for entering S, T, we reset it
4752 // in the inhomogeneous case: FDeg == pFDeg
4753 if (strat->homog) strat->initEcart(&(strat->P));
4754
4755 /* statistic */
4756 if (TEST_OPT_PROT) PrintS("s");
4757
4758 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4759
4760 // reduce the tail and normalize poly
4761 // in the ring case we cannot expect LC(f) = 1,
4762 strat->redTailChange=FALSE;
4763
4764 /* if we are computing over Z we always want to try and cut down
4765 * the coefficients in the tail terms */
4767 {
4768 redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4769 }
4770
4772 {
4773 strat->P.pCleardenom();
4775 {
4776 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4777 strat->P.pCleardenom();
4778 if (strat->redTailChange)
4779 {
4780 strat->P.t_p=NULL;
4781 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4782 }
4783 }
4784 }
4785 else
4786 {
4787 strat->P.pNorm();
4789 {
4790 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4791 if (strat->redTailChange)
4792 {
4793 strat->P.t_p=NULL;
4794 strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4795 }
4796 }
4797 }
4798
4799#ifdef KDEBUG
4800 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4801#endif /* KDEBUG */
4802
4803 // min_std stuff
4804 if ((strat->P.p1==NULL) && (strat->minim>0))
4805 {
4806 if (strat->minim==1)
4807 {
4808 strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4809 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4810 }
4811 else
4812 {
4813 strat->M->m[minimcnt]=strat->P.p2;
4814 strat->P.p2=NULL;
4815 }
4816 if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4817 pNext(strat->M->m[minimcnt])
4818 = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4819 strat->tailRing, currRing,
4820 currRing->PolyBin);
4821 minimcnt++;
4822 }
4823
4824
4825 // enter into S, L, and T
4826 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
4827 {
4828 enterT(strat->P, strat);
4829 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4830 // posInS only depends on the leading term
4831 strat->enterS(strat->P, pos, strat, strat->tl);
4832 if (!strat->rightGB)
4833 enterTShift(strat->P, strat);
4834 }
4835
4836 if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4837// Print("[%d]",hilbeledeg);
4838 kDeleteLcm(&strat->P);
4839 if (strat->s_poly!=NULL)
4840 {
4841 // the only valid entries are: strat->P.p,
4842 // strat->tailRing (read-only, keep it)
4843 // (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4844 if (strat->s_poly(strat))
4845 {
4846 // we are called AFTER enterS, i.e. if we change P
4847 // we have to add it also to S/T
4848 // and add pairs
4849 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4850 enterT(strat->P, strat);
4851 enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4852 strat->enterS(strat->P, pos, strat, strat->tl);
4853 if (!strat->rightGB)
4854 enterTShift(strat->P,strat);
4855 }
4856 }
4857 }
4858 else if (strat->P.p1 == NULL && strat->minim > 0)
4859 {
4860 p_Delete(&strat->P.p2, currRing, strat->tailRing);
4861 }
4862#ifdef KDEBUG
4863 memset(&(strat->P), 0, sizeof(strat->P));
4864#endif /* KDEBUG */
4865 kTest_TS(strat);
4866 }
4867#ifdef KDEBUG
4868 if (TEST_OPT_DEBUG) messageSets(strat);
4869#endif /* KDEBUG */
4870 /* shift case: look for elt's in S such that they are divisible by elt in T */
4871 if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4872 {
4874 {
4875 for (int k = 0; k <= strat->sl; ++k)
4876 {
4877 if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4878 for (int j = 0; j<=strat->tl; ++j)
4879 {
4880 if (strat->T[j].p!=NULL)
4881 {
4882 // this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4883 assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4884 assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4885 if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4886 {
4887 if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4888 { // check whether LM is different
4889 deleteInS(k, strat);
4890 --k;
4891 break;
4892 }
4893 }
4894 }
4895 }
4896 }
4897 }
4898 }
4899 /* complete reduction of the standard basis--------- */
4900 if (TEST_OPT_REDSB)
4901 {
4902 completeReduce(strat, TRUE); //shift: withT = TRUE
4903 if (strat->completeReduce_retry)
4904 {
4905 // completeReduce needed larger exponents, retry
4906 // to reduce with S (instead of T)
4907 // and in currRing (instead of strat->tailRing)
4908#ifdef HAVE_TAIL_RING
4909 if(currRing->bitmask>strat->tailRing->bitmask)
4910 {
4912 cleanT(strat);strat->tailRing=currRing;
4913 int i;
4914 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4915 WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4916 completeReduce(strat);
4917 }
4918 if (strat->completeReduce_retry)
4919#endif
4920 Werror("exponent bound is %ld",currRing->bitmask);
4921 }
4922 }
4923 else if (TEST_OPT_PROT) PrintLn();
4924
4925 /* release temp data-------------------------------- */
4926 exitBuchMora(strat);
4927 /* postprocessing for GB over ZZ --------------------*/
4928 if (!errorreported)
4929 {
4931 {
4932 for(int i = 0;i<=strat->sl;i++)
4933 {
4934 if(!nGreaterZero(pGetCoeff(strat->S[i])))
4935 {
4936 strat->S[i] = pNeg(strat->S[i]);
4937 }
4938 }
4939 finalReduceByMon(strat);
4940 for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4941 {
4942 if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4943 {
4944 strat->S[i] = pNeg(strat->Shdl->m[i]);
4945 }
4946 }
4947 }
4948 //else if (rField_is_Ring(currRing))
4949 // finalReduceByMon(strat);
4950 }
4951// if (TEST_OPT_WEIGHTM)
4952// {
4953// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4954// if (ecartWeights)
4955// {
4956// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4957// ecartWeights=NULL;
4958// }
4959// }
4960 if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4961 SI_RESTORE_OPT1(save);
4962 /* postprocessing for GB over Q-rings ------------------*/
4963 if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4964
4965 idTest(strat->Shdl);
4966
4967 return (strat->Shdl);
4968}
4969#endif
4970
4971#ifdef HAVE_SHIFTBBA
4972ideal rightgb(ideal F, ideal Q)
4973{
4975 assume(idIsInV(F));
4976 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4977 idSkipZeroes(RS); // is this even necessary?
4978 assume(idIsInV(RS));
4979 return(RS);
4980}
4981#endif
4982
4983/*2
4984*reduces h with elements from T choosing the first possible
4985* element in t with respect to the given pDivisibleBy
4986*/
4987#ifdef HAVE_SHIFTBBA
4989{
4990 if (h->IsNull()) return 0;
4991
4992 int at, reddeg,d;
4993 int pass = 0;
4994 int j = 0;
4995
4996 if (! strat->homog)
4997 {
4998 d = h->GetpFDeg() + h->ecart;
4999 reddeg = strat->LazyDegree+d;
5000 }
5001 h->SetShortExpVector();
5002 loop
5003 {
5004 j = kFindDivisibleByInT(strat, h);
5005 if (j < 0)
5006 {
5007 h->SetDegStuffReturnLDeg(strat->LDegLast);
5008 return 1;
5009 }
5010
5012 strat->T[j].pNorm();
5013#ifdef KDEBUG
5014 if (TEST_OPT_DEBUG)
5015 {
5016 PrintS("reduce ");
5017 h->wrp();
5018 PrintS(" with ");
5019 strat->T[j].wrp();
5020 }
5021#endif
5022 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
5023
5024#ifdef KDEBUG
5025 if (TEST_OPT_DEBUG)
5026 {
5027 PrintS("\nto ");
5028 wrp(h->p);
5029 PrintLn();
5030 }
5031#endif
5032 if (h->IsNull())
5033 {
5034 kDeleteLcm(h);
5035 h->Clear();
5036 return 0;
5037 }
5038 h->SetShortExpVector();
5039
5040#if 0
5041 if ((strat->syzComp!=0) && !strat->honey)
5042 {
5043 if ((strat->syzComp>0) &&
5044 (h->Comp() > strat->syzComp))
5045 {
5046 assume(h->MinComp() > strat->syzComp);
5047#ifdef KDEBUG
5048 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
5049#endif
5050 if (strat->homog)
5051 h->SetDegStuffReturnLDeg(strat->LDegLast);
5052 return -2;
5053 }
5054 }
5055#endif
5056 if (!strat->homog)
5057 {
5058 if (!TEST_OPT_OLDSTD && strat->honey)
5059 {
5060 h->SetpFDeg();
5061 if (strat->T[j].ecart <= h->ecart)
5062 h->ecart = d - h->GetpFDeg();
5063 else
5064 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
5065
5066 d = h->GetpFDeg() + h->ecart;
5067 }
5068 else
5069 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
5070 /*- try to reduce the s-polynomial -*/
5071 pass++;
5072 /*
5073 *test whether the polynomial should go to the lazyset L
5074 *-if the degree jumps
5075 *-if the number of pre-defined reductions jumps
5076 */
5077 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
5078 && ((d >= reddeg) || (pass > strat->LazyPass)))
5079 {
5080 h->SetLmCurrRing();
5081 if (strat->posInLDependsOnLength)
5082 h->SetLength(strat->length_pLength);
5083 at = strat->posInL(strat->L,strat->Ll,h,strat);
5084 if (at <= strat->Ll)
5085 {
5086 //int dummy=strat->sl;
5087 /* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
5088 //if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
5089 if (kFindDivisibleByInT(strat, h) < 0)
5090 return 1;
5091 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
5092#ifdef KDEBUG
5093 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
5094#endif
5095 h->Clear();
5096 return -1;
5097 }
5098 }
5099 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
5100 {
5101 reddeg = d+1;
5102 Print(".%d",d);mflush();
5103 }
5104 }
5105 }
5106}
5107#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 void sort(int **points, int sizePoints)
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:72
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
VAR short errorreported
Definition: feFopen.cc:23
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define VAR
Definition: globaldefs.h:5
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
#define idTest(id)
Definition: ideals.h:47
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition: ideals.h:184
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR jList * T
Definition: janet.cc:30
STATIC_VAR Poly * h
Definition: janet.cc:971
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:2926
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3761
void initBba(kStrategy strat)
Definition: kstd1.cc:1689
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1747
#define KSTD_NF_LAZY
Definition: kstd1.h:17
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
#define KSTD_NF_NONORM
Definition: kstd1.h:21
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:683
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:569
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4988
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:2525
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3967
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:2088
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:3001
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2642
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1881
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1511
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:1761
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition: kstd2.cc:1305
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2325
static int redRing_S(LObject *h, kStrategy strat)
Definition: kstd2.cc:1056
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1343
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:4296
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:4049
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:4608
static int redRing_Z_S(LObject *h, kStrategy strat)
Definition: kstd2.cc:841
ideal rightgb(ideal F, ideal Q)
Definition: kstd2.cc:4972
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:357
#define nDelete(n)
Definition: numbers.h:16
#define nIsZero(n)
Definition: numbers.h:19
#define nCopy(n)
Definition: numbers.h:15
#define nGreaterZero(n)
Definition: numbers.h:27
#define nIsOne(n)
Definition: numbers.h:25
#define nNormalize(n)
Definition: numbers.h:30
#define nInit(i)
Definition: numbers.h:24
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omRealloc0Size(addr, o_size, size)
Definition: omAllocDecl.h:221
#define NULL
Definition: omList.c:12
VAR BOOLEAN siCntrlc
Definition: options.c:14
VAR unsigned si_opt_1
Definition: options.c:5
#define OPT_INTSTRATEGY
Definition: options.h:93
#define TEST_OPT_IDLIFT
Definition: options.h:130
#define TEST_OPT_INTSTRATEGY
Definition: options.h:111
#define BVERBOSE(a)
Definition: options.h:35
#define TEST_OPT_REDTAIL
Definition: options.h:117
#define OPT_REDTAIL
Definition: options.h:92
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define TEST_OPT_OLDSTD
Definition: options.h:124
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:105
#define TEST_OPT_DEGBOUND
Definition: options.h:114
#define TEST_OPT_SB_1
Definition: options.h:120
#define TEST_OPT_LENGTH
Definition: options.h:132
#define TEST_OPT_PROT
Definition: options.h:104
#define TEST_OPT_REDTHROUGH
Definition: options.h:123
#define TEST_OPT_IDELIM
Definition: options.h:131
#define TEST_OPT_DEBUG
Definition: options.h:109
#define TEST_OPT_REDTAIL_SYZ
Definition: options.h:118
#define TEST_OPT_CONTENTSB
Definition: options.h:128
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:106
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1297
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc: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
long p_Deg(poly a, const ring r)
Definition: p_polys.cc:587
static int pLength(poly a)
Definition: p_polys.h:188
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1112
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1409
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1721
static void p_SetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1542
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:486
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:245
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition: p_polys.h:1438
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:410
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition: p_polys.h:858
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1578
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1908
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:467
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1889
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static void p_GetExpV(poly p, int *ev, const ring r)
Definition: p_polys.h:1518
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:1049
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:753
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844
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:760
#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
#define Q
Definition: sirandom.c:26
@ 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 F1(int a1, int &r1)
F1.
int gcd(int a, int b)
Definition: walkSupport.cc:836