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