My Project
Loading...
Searching...
No Matches
kstd1.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT:
6*/
7
8// TODO: why the following is here instead of mod2.h???
9
10
11// define if buckets should be used
12#define MORA_USE_BUCKETS
13
14#define PRE_INTEGER_CHECK 0
15
16#include "kernel/mod2.h"
17
18#include "misc/options.h"
19#include "misc/intvec.h"
20
21#include "polys/weight.h"
22#include "kernel/polys.h"
23
28#include "kernel/ideals.h"
29
30//#include "ipprint.h"
31
32#ifdef HAVE_PLURAL
33#include "polys/nc/nc.h"
34#include "polys/nc/sca.h"
35#include "kernel/GBEngine/nc.h"
36#endif
37
39
40#ifdef HAVE_SHIFTBBA
41#include "polys/shiftop.h"
42#endif
43
44/* the list of all options which give a warning by test */
46 |Sy_bit(OPT_REDSB) /* 1 */
47 |Sy_bit(OPT_NOT_SUGAR) /* 3 */
48 |Sy_bit(OPT_INTERRUPT) /* 4 */
49 |Sy_bit(OPT_SUGARCRIT) /* 5 */
52 |Sy_bit(OPT_FASTHC) /* 10 */
53 |Sy_bit(OPT_INTSTRATEGY) /* 26 */
54 |Sy_bit(OPT_INFREDTAIL) /* 28 */
55 |Sy_bit(OPT_NOTREGULARITY) /* 30 */
56 |Sy_bit(OPT_WEIGHTM); /* 31 */
57
58/* the list of all options which may be used by option and test */
59/* definition of ALL options: libpolys/misc/options.h */
61 |Sy_bit(1)
62 |Sy_bit(2) // obachman 10/00: replaced by notBucket
63 |Sy_bit(3)
64 |Sy_bit(4)
65 |Sy_bit(5)
66 |Sy_bit(6)
67// |Sy_bit(7) obachman 11/00 tossed: 12/00 used for redThrough
68 |Sy_bit(7) // OPT_REDTHROUGH
69 |Sy_bit(8) // obachman 11/00 tossed -> motsak 2011 experimental: OPT_NO_SYZ_MINIM
70 |Sy_bit(9)
71 |Sy_bit(10)
72 |Sy_bit(11)
73 |Sy_bit(12)
74 |Sy_bit(13)
75 |Sy_bit(14)
76 |Sy_bit(15)
77 |Sy_bit(16)
78 |Sy_bit(17)
79 |Sy_bit(18)
80 |Sy_bit(19)
81// |Sy_bit(20) obachman 11/00 tossed: 12/00 used for redOldStd
83 |Sy_bit(21)
84 |Sy_bit(22)
85 /*|Sy_bit(23)*/
86 /*|Sy_bit(24)*/
89 |Sy_bit(27)
90 |Sy_bit(28)
91 |Sy_bit(29)
92 |Sy_bit(30)
93 |Sy_bit(31);
94
95//static BOOLEAN posInLOldFlag;
96 /*FALSE, if posInL == posInL10*/
97// returns TRUE if mora should use buckets, false otherwise
98static BOOLEAN kMoraUseBucket(kStrategy strat);
99
100static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
101{
102// if (strat->ak == 0 && !rIsSyzIndexRing(currRing))
103 strat->length_pLength = TRUE;
104// else
105// strat->length_pLength = FALSE;
106
107 if ((ldeg == pLDeg0c /*&& !rIsSyzIndexRing(currRing)*/) ||
108 (ldeg == pLDeg0 && strat->ak == 0))
109 {
110 strat->LDegLast = TRUE;
111 }
112 else
113 {
114 strat->LDegLast = FALSE;
115 }
116}
117
118static int doRed (LObject* h, TObject* with,BOOLEAN intoT,kStrategy strat, bool redMoraNF)
119{
120 int ret;
121#if KDEBUG > 0
122 kTest_L(h);
123 kTest_T(with);
124#endif
125 // Hmmm ... why do we do this -- polys from T should already be normalized
127 with->pNorm();
128#ifdef KDEBUG
129 if (TEST_OPT_DEBUG)
130 {
131 PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
132 }
133#endif
134 if (intoT)
135 {
136 // need to do it exactly like this: otherwise
137 // we might get errors
138 LObject L= *h;
139 L.Copy();
140 h->GetP();
141 h->length=h->pLength=pLength(h->p);
142 ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, NULL, strat);
143 if (ret)
144 {
145 if (ret < 0) return ret;
146 if (h->tailRing != strat->tailRing)
147 h->ShallowCopyDelete(strat->tailRing,
149 strat->tailRing));
150 }
152 enterT_strong(*h,strat);
153 else
154 enterT(*h,strat);
155 *h = L;
156 }
157 else
158 ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, NULL, strat);
159#ifdef KDEBUG
160 if (TEST_OPT_DEBUG)
161 {
162 PrintS("to ");h->wrp();PrintLn();
163 }
164#endif
165 return ret;
166}
167
169{
170 int i,at,ei,li,ii;
171 int j = 0;
172 int pass = 0;
173 long d,reddeg;
174
175 d = h->GetpFDeg()+ h->ecart;
176 reddeg = strat->LazyDegree+d;
177 h->SetShortExpVector();
178 loop
179 {
180 j = kFindDivisibleByInT(strat, h);
181 if (j < 0)
182 {
183 if (strat->honey) h->SetLength(strat->length_pLength);
184 return 1;
185 }
186
187 ei = strat->T[j].ecart;
188 ii = j;
189
190 if (ei > h->ecart)
191 {
192 unsigned long not_sev=~h->sev;
193 poly h_t= h->GetLmTailRing();
194 li = strat->T[j].length;
195 if (li<=0) li=strat->T[j].GetpLength();
196 // the polynomial to reduce with (up to the moment) is;
197 // pi with ecart ei and length li
198 // look for one with smaller ecart
199 i = j;
200 loop
201 {
202 /*- takes the first possible with respect to ecart -*/
203 i++;
204 if (i > strat->tl) break;
205#if 1
206 if (strat->T[i].length<=0) strat->T[i].GetpLength();
207 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
208 strat->T[i].length < li))
209 &&
210 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h_t, not_sev, strat->tailRing))
211#else
212 j = kFindDivisibleByInT(strat, h, i);
213 if (j < 0) break;
214 i = j;
215 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
216 strat->T[i].length < li))
217#endif
218 {
219 // the polynomial to reduce with is now
220 ii = i;
221 ei = strat->T[i].ecart;
222 if (ei <= h->ecart) break;
223 li = strat->T[i].length;
224 }
225 }
226 }
227
228 // end of search: have to reduce with pi
229 if ((ei > h->ecart)&&(strat->kNoether==NULL))
230 {
231 // It is not possible to reduce h with smaller ecart;
232 // if possible h goes to the lazy-set L,i.e
233 // if its position in L would be not the last one
234 strat->fromT = TRUE;
235 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
236 {
237 h->SetLmCurrRing();
238 if (strat->honey && strat->posInLDependsOnLength)
239 h->SetLength(strat->length_pLength);
240 assume(h->FDeg == h->pFDeg());
241 at = strat->posInL(strat->L,strat->Ll,h,strat);
242 if (at <= strat->Ll)
243 {
244 /*- h will not become the next element to reduce -*/
245 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
246#ifdef KDEBUG
247 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
248#endif
249 h->Clear();
250 strat->fromT = FALSE;
251 return -1;
252 }
253 }
254 }
255
256 // now we finally can reduce
257 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
258 strat->fromT=FALSE;
259
260 // are we done ???
261 if (h->IsNull())
262 {
264 kDeleteLcm(h);
265 h->Clear();
266 return 0;
267 }
268 if (TEST_OPT_IDLIFT)
269 {
270 if (h->p!=NULL)
271 {
272 if(p_GetComp(h->p,currRing)>strat->syzComp)
273 {
274 h->Delete();
275 return 0;
276 }
277 }
278 else if (h->t_p!=NULL)
279 {
280 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
281 {
282 h->Delete();
283 return 0;
284 }
285 }
286 }
287 #if 0
288 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
289 {
290 if (h->p!=NULL)
291 {
292 if(p_GetComp(h->p,currRing)>strat->syzComp)
293 {
294 return 1;
295 }
296 }
297 else if (h->t_p!=NULL)
298 {
299 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
300 {
301 return 1;
302 }
303 }
304 }
305 #endif
306
307 // done ? NO!
308 h->SetShortExpVector();
309 h->SetpFDeg();
310 if (strat->honey)
311 {
312 if (ei <= h->ecart)
313 h->ecart = d-h->GetpFDeg();
314 else
315 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
316 }
317 else
318 // this has the side effect of setting h->length
319 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
320#if 0
321 if (strat->syzComp!=0)
322 {
323 if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
324 {
325 assume(h->MinComp() > strat->syzComp);
326 if (strat->honey) h->SetLength();
327#ifdef KDEBUG
328 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
329#endif
330 return -2;
331 }
332 }
333#endif
334 /*- try to reduce the s-polynomial -*/
335 pass++;
336 d = h->GetpFDeg()+h->ecart;
337 /*
338 *test whether the polynomial should go to the lazyset L
339 *-if the degree jumps
340 *-if the number of pre-defined reductions jumps
341 */
342 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
343 && ((d >= reddeg) || (pass > strat->LazyPass)))
344 {
345 h->SetLmCurrRing();
346 if (strat->honey && strat->posInLDependsOnLength)
347 h->SetLength(strat->length_pLength);
348 assume(h->FDeg == h->pFDeg());
349 at = strat->posInL(strat->L,strat->Ll,h,strat);
350 if (at <= strat->Ll)
351 {
352 int dummy=strat->sl;
353 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
354 {
355 if (strat->honey && !strat->posInLDependsOnLength)
356 h->SetLength(strat->length_pLength);
357 return 1;
358 }
359 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
360#ifdef KDEBUG
361 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
362#endif
363 h->Clear();
364 return -1;
365 }
366 }
367 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
368 {
369 Print(".%ld",d);mflush();
370 reddeg = d+1;
371 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
372 {
373 strat->overflow=TRUE;
374 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
375 h->GetP();
376 at = strat->posInL(strat->L,strat->Ll,h,strat);
377 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
378 h->Clear();
379 return -1;
380 }
381 }
382 }
383}
384
386{
387 int i,at,ei,li,ii;
388 int j = 0;
389 int pass = 0;
390 long d,reddeg;
391
392 d = h->GetpFDeg()+ h->ecart;
393 reddeg = strat->LazyDegree+d;
394 h->SetShortExpVector();
395 loop
396 {
397 j = kFindDivisibleByInT(strat, h);
398 if (j < 0)
399 {
400 // over ZZ: cleanup coefficients by complete reduction with monomials
401 postReduceByMon(h, strat);
402 if(h->p == NULL)
403 {
404 kDeleteLcm(h);
405 h->Clear();
406 return 0;
407 }
408 if (strat->honey) h->SetLength(strat->length_pLength);
409 if(strat->tl >= 0)
410 h->i_r1 = strat->tl;
411 else
412 h->i_r1 = -1;
413 if (h->GetLmTailRing() == NULL)
414 {
415 kDeleteLcm(h);
416 h->Clear();
417 return 0;
418 }
419 return 1;
420 }
421
422 ei = strat->T[j].ecart;
423 ii = j;
424 if (ei > h->ecart && ii < strat->tl)
425 {
426 li = strat->T[j].length;
427 // the polynomial to reduce with (up to the moment) is;
428 // pi with ecart ei and length li
429 // look for one with smaller ecart
430 i = j;
431 loop
432 {
433 /*- takes the first possible with respect to ecart -*/
434 i++;
435#if 1
436 if (i > strat->tl) break;
437 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
438 strat->T[i].length < li))
439 &&
440 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
441 &&
442 n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
443#else
444 j = kFindDivisibleByInT(strat, h, i);
445 if (j < 0) break;
446 i = j;
447 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
448 strat->T[i].length < li))
449#endif
450 {
451 // the polynomial to reduce with is now
452 ii = i;
453 ei = strat->T[i].ecart;
454 if (ei <= h->ecart) break;
455 li = strat->T[i].length;
456 }
457 }
458 }
459
460 // end of search: have to reduce with pi
461 if (ei > h->ecart)
462 {
463 // It is not possible to reduce h with smaller ecart;
464 // if possible h goes to the lazy-set L,i.e
465 // if its position in L would be not the last one
466 strat->fromT = TRUE;
467 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
468 {
469 h->SetLmCurrRing();
470 if (strat->honey && strat->posInLDependsOnLength)
471 h->SetLength(strat->length_pLength);
472 assume(h->FDeg == h->pFDeg());
473 at = strat->posInL(strat->L,strat->Ll,h,strat);
474 if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
475 {
476 /*- h will not become the next element to reduce -*/
477 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
478 #ifdef KDEBUG
479 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
480 #endif
481 h->Clear();
482 strat->fromT = FALSE;
483 return -1;
484 }
485 }
486 doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
487 }
488 else
489 {
490 // now we finally can reduce
491 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
492 }
493 strat->fromT=FALSE;
494 // are we done ???
495 if (h->IsNull())
496 {
497 kDeleteLcm(h);
498 h->Clear();
499 return 0;
500 }
501
502 // NO!
503 h->SetShortExpVector();
504 h->SetpFDeg();
505 if (strat->honey)
506 {
507 if (ei <= h->ecart)
508 h->ecart = d-h->GetpFDeg();
509 else
510 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
511 }
512 else
513 // this has the side effect of setting h->length
514 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
515 /*- try to reduce the s-polynomial -*/
516 pass++;
517 d = h->GetpFDeg()+h->ecart;
518 /*
519 *test whether the polynomial should go to the lazyset L
520 *-if the degree jumps
521 *-if the number of pre-defined reductions jumps
522 */
523 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
524 && ((d >= reddeg) || (pass > strat->LazyPass)))
525 {
526 h->SetLmCurrRing();
527 if (strat->honey && strat->posInLDependsOnLength)
528 h->SetLength(strat->length_pLength);
529 assume(h->FDeg == h->pFDeg());
530 at = strat->posInL(strat->L,strat->Ll,h,strat);
531 if (at <= strat->Ll)
532 {
533 int dummy=strat->sl;
534 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
535 {
536 if (strat->honey && !strat->posInLDependsOnLength)
537 h->SetLength(strat->length_pLength);
538 return 1;
539 }
540 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
541#ifdef KDEBUG
542 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
543#endif
544 h->Clear();
545 return -1;
546 }
547 }
548 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
549 {
550 Print(".%ld",d);mflush();
551 reddeg = d+1;
552 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
553 {
554 strat->overflow=TRUE;
555 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
556 h->GetP();
557 at = strat->posInL(strat->L,strat->Ll,h,strat);
558 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
559 h->Clear();
560 return -1;
561 }
562 }
563 }
564}
565
567{
568 int i,at,ei,li,ii;
569 int j = 0;
570 int pass = 0;
571 long d,reddeg;
572 int docoeffred = 0;
573 poly T0p = strat->T[0].p;
574 int T0ecart = strat->T[0].ecart;
575
576
577 d = h->GetpFDeg()+ h->ecart;
578 reddeg = strat->LazyDegree+d;
579 h->SetShortExpVector();
580 if ((strat->tl>=0)
581 &&strat->T[0].GetpFDeg() == 0
582 && strat->T[0].length <= 2)
583 {
584 docoeffred = 1;
585 }
586 loop
587 {
588 /* cut down the lead coefficients, only possible if the degree of
589 * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
590 * we ask for the length of T[0] to be <= 2 */
591 if (docoeffred)
592 {
593 j = kTestDivisibleByT0_Z(strat, h);
594 if (j == 0 && n_DivBy(pGetCoeff(h->p), pGetCoeff(T0p), currRing->cf) == FALSE
595 && T0ecart <= h->ecart)
596 {
597 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
598 * => we try to cut down the lead coefficient at least */
599 /* first copy T[j] in order to multiply it with a coefficient later on */
600 number mult, rest;
601 TObject tj = strat->T[0];
602 tj.Copy();
603 /* compute division with remainder of lc(h) and lc(T[j]) */
604 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(T0p),
605 &rest, currRing->cf);
606 /* set corresponding new lead coefficient already. we do not
607 * remove the lead term in ksReducePolyLC, but only apply
608 * a lead coefficient reduction */
609 tj.Mult_nn(mult);
610 ksReducePolyLC(h, &tj, NULL, &rest, strat);
611 tj.Delete();
612 tj.Clear();
613 if (n_IsZero(pGetCoeff(h->GetP()),currRing->cf))
614 {
615 h->LmDeleteAndIter();
616 }
617 }
618 }
619 j = kFindDivisibleByInT(strat, h);
620 if (j < 0)
621 {
622 // over ZZ: cleanup coefficients by complete reduction with monomials
623 postReduceByMon(h, strat);
624 if(h->p == NULL)
625 {
626 kDeleteLcm(h);
627 h->Clear();
628 return 0;
629 }
630 if (strat->honey) h->SetLength(strat->length_pLength);
631 if(strat->tl >= 0)
632 h->i_r1 = strat->tl;
633 else
634 h->i_r1 = -1;
635 if (h->GetLmTailRing() == NULL)
636 {
637 kDeleteLcm(h);
638 h->Clear();
639 return 0;
640 }
641 return 1;
642 }
643
644 ei = strat->T[j].ecart;
645 ii = j;
646#if 1
647 if (ei > h->ecart && ii < strat->tl)
648 {
649 li = strat->T[j].length;
650 // the polynomial to reduce with (up to the moment) is;
651 // pi with ecart ei and length li
652 // look for one with smaller ecart
653 i = j;
654 loop
655 {
656 /*- takes the first possible with respect to ecart -*/
657 i++;
658#if 1
659 if (i > strat->tl) break;
660 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
661 strat->T[i].length < li))
662 &&
663 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
664 &&
665 n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
666#else
667 j = kFindDivisibleByInT(strat, h, i);
668 if (j < 0) break;
669 i = j;
670 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
671 strat->T[i].length < li))
672#endif
673 {
674 // the polynomial to reduce with is now
675 ii = i;
676 ei = strat->T[i].ecart;
677 if (ei <= h->ecart) break;
678 li = strat->T[i].length;
679 }
680 }
681 }
682#endif
683
684 // end of search: have to reduce with pi
685 if (ei > h->ecart)
686 {
687 // It is not possible to reduce h with smaller ecart;
688 // if possible h goes to the lazy-set L,i.e
689 // if its position in L would be not the last one
690 strat->fromT = TRUE;
691 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
692 {
693 h->SetLmCurrRing();
694 if (strat->honey && strat->posInLDependsOnLength)
695 h->SetLength(strat->length_pLength);
696 assume(h->FDeg == h->pFDeg());
697 at = strat->posInL(strat->L,strat->Ll,h,strat);
698 if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
699 {
700 /*- h will not become the next element to reduce -*/
701 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
702#ifdef KDEBUG
703 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
704#endif
705 h->Clear();
706 strat->fromT = FALSE;
707 return -1;
708 }
709 }
710 doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
711 }
712 else
713 {
714 // now we finally can reduce
715 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
716 }
717 strat->fromT=FALSE;
718 // are we done ???
719 if (h->IsNull())
720 {
721 kDeleteLcm(h);
722 h->Clear();
723 return 0;
724 }
725
726 // NO!
727 h->SetShortExpVector();
728 h->SetpFDeg();
729 if (strat->honey)
730 {
731 if (ei <= h->ecart)
732 h->ecart = d-h->GetpFDeg();
733 else
734 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
735 }
736 else
737 // this has the side effect of setting h->length
738 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
739 /*- try to reduce the s-polynomial -*/
740 pass++;
741 d = h->GetpFDeg()+h->ecart;
742 /*
743 *test whether the polynomial should go to the lazyset L
744 *-if the degree jumps
745 *-if the number of pre-defined reductions jumps
746 */
747 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
748 && ((d >= reddeg) || (pass > strat->LazyPass)))
749 {
750 h->SetLmCurrRing();
751 if (strat->honey && strat->posInLDependsOnLength)
752 h->SetLength(strat->length_pLength);
753 assume(h->FDeg == h->pFDeg());
754 at = strat->posInL(strat->L,strat->Ll,h,strat);
755 if (at <= strat->Ll)
756 {
757 int dummy=strat->sl;
758 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
759 {
760 if (strat->honey && !strat->posInLDependsOnLength)
761 h->SetLength(strat->length_pLength);
762 return 1;
763 }
764 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
765#ifdef KDEBUG
766 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
767#endif
768 h->Clear();
769 return -1;
770 }
771 }
772 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
773 {
774 Print(".%ld",d);mflush();
775 reddeg = d+1;
776 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
777 {
778 strat->overflow=TRUE;
779 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
780 h->GetP();
781 at = strat->posInL(strat->L,strat->Ll,h,strat);
782 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
783 h->Clear();
784 return -1;
785 }
786 }
787 }
788}
789
790/*2
791*reduces h with elements from T choosing the first possible
792* element in t with respect to the given pDivisibleBy
793*/
795{
796 if (strat->tl<0) return 1;
797 if (h->IsNull()) return 0;
798
799 int at;
800 long reddeg,d;
801 int pass = 0;
802 int cnt = RED_CANONICALIZE;
803 int j = 0;
804
805 reddeg = d = h->GetpFDeg();
806 if (! strat->homog)
807 {
808 d += h->ecart;
809 reddeg = strat->LazyDegree+d;
810 }
811 h->SetShortExpVector();
812 loop
813 {
814 j = kFindDivisibleByInT(strat, h);
815 if (j < 0)
816 {
817 h->SetDegStuffReturnLDeg(strat->LDegLast);
818 return 1;
819 }
820
822 strat->T[j].pNorm();
823#ifdef KDEBUG
824 if (TEST_OPT_DEBUG)
825 {
826 PrintS("reduce ");
827 h->wrp();
828 PrintS(" with ");
829 strat->T[j].wrp();
830 }
831#endif
832 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
833#ifdef KDEBUG
834 if (TEST_OPT_DEBUG)
835 {
836 PrintS(" to ");
837 wrp(h->p);
838 PrintLn();
839 }
840#endif
841 if (h->IsNull())
842 {
844 kDeleteLcm(h);
845 h->Clear();
846 return 0;
847 }
848 if (TEST_OPT_IDLIFT)
849 {
850 if (h->p!=NULL)
851 {
852 if(p_GetComp(h->p,currRing)>strat->syzComp)
853 {
854 h->Delete();
855 return 0;
856 }
857 }
858 else if (h->t_p!=NULL)
859 {
860 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
861 {
862 h->Delete();
863 return 0;
864 }
865 }
866 }
867 #if 0
868 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
869 {
870 if (h->p!=NULL)
871 {
872 if(p_GetComp(h->p,currRing)>strat->syzComp)
873 {
874 return 1;
875 }
876 }
877 else if (h->t_p!=NULL)
878 {
879 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
880 {
881 return 1;
882 }
883 }
884 }
885 #endif
886 h->SetShortExpVector();
887
888#if 0
889 if ((strat->syzComp!=0) && !strat->honey)
890 {
891 if ((strat->syzComp>0) &&
892 (h->Comp() > strat->syzComp))
893 {
894 assume(h->MinComp() > strat->syzComp);
895#ifdef KDEBUG
896 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
897#endif
898 if (strat->homog)
899 h->SetDegStuffReturnLDeg(strat->LDegLast);
900 return -2;
901 }
902 }
903#endif
904 if (!strat->homog)
905 {
906 if (!TEST_OPT_OLDSTD && strat->honey)
907 {
908 h->SetpFDeg();
909 if (strat->T[j].ecart <= h->ecart)
910 h->ecart = d - h->GetpFDeg();
911 else
912 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
913
914 d = h->GetpFDeg() + h->ecart;
915 }
916 else
917 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
918 /*- try to reduce the s-polynomial -*/
919 cnt--;
920 pass++;
921 /*
922 *test whether the polynomial should go to the lazyset L
923 *-if the degree jumps
924 *-if the number of pre-defined reductions jumps
925 */
926 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
927 && ((d >= reddeg) || (pass > strat->LazyPass)))
928 {
929 h->SetLmCurrRing();
930 if (strat->posInLDependsOnLength)
931 h->SetLength(strat->length_pLength);
932 at = strat->posInL(strat->L,strat->Ll,h,strat);
933 if (at <= strat->Ll)
934 {
935 int dummy=strat->sl;
936 if (kFindDivisibleByInS(strat,&dummy, h) < 0)
937 return 1;
938 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
939#ifdef KDEBUG
940 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
941#endif
942 h->Clear();
943 return -1;
944 }
945 }
946 if (UNLIKELY(cnt==0))
947 {
948 h->CanonicalizeP();
950 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
951 }
952 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
953 {
954 reddeg = d+1;
955 Print(".%ld",d);mflush();
956 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
957 {
958 strat->overflow=TRUE;
959 //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
960 h->GetP();
961 at = strat->posInL(strat->L,strat->Ll,h,strat);
962 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
963 h->Clear();
964 return -1;
965 }
966 }
967 }
968 }
969}
970
971/*2
972* reduces h with elements from T choosing first possible
973* element in T with respect to the given ecart
974* used for computing normal forms outside kStd
975*/
976static poly redMoraNF (poly h,kStrategy strat, int flag)
977{
978 LObject H;
979 H.p = h;
980 int j = 0;
981 int z = 10;
982 int o = H.SetpFDeg();
983 H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
985 H.sev = pGetShortExpVector(H.p);
986 loop
987 {
988 if (j > strat->tl)
989 {
990 return H.p;
991 }
992 if (TEST_V_DEG_STOP)
993 {
994 if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
995 if (H.p==NULL) return NULL;
996 }
997 unsigned long not_sev = ~ H.sev;
998 if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
999 )
1000 {
1001 /*- remember the found T-poly -*/
1002 // poly pi = strat->T[j].p;
1003 int ei = strat->T[j].ecart;
1004 int li = strat->T[j].length;
1005 int ii = j;
1006 /*
1007 * the polynomial to reduce with (up to the moment) is;
1008 * pi with ecart ei and length li
1009 */
1010 loop
1011 {
1012 /*- look for a better one with respect to ecart -*/
1013 /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1014 j++;
1015 if (j > strat->tl) break;
1016 if (ei <= H.ecart) break;
1017 if (((strat->T[j].ecart < ei)
1018 || ((strat->T[j].ecart == ei)
1019 && (strat->T[j].length < li)))
1020 && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1021 )
1022 {
1023 /*
1024 * the polynomial to reduce with is now;
1025 */
1026 // pi = strat->T[j].p;
1027 ei = strat->T[j].ecart;
1028 li = strat->T[j].length;
1029 ii = j;
1030 }
1031 }
1032 /*
1033 * end of search: have to reduce with pi
1034 */
1035 z++;
1036 if (z>10)
1037 {
1038 pNormalize(H.p);
1039 z=0;
1040 }
1041 if ((ei > H.ecart) && (strat->kNoether==NULL))
1042 {
1043 /*
1044 * It is not possible to reduce h with smaller ecart;
1045 * we have to reduce with bad ecart: H has to enter in T
1046 */
1047 LObject L= H;
1048 L.Copy();
1049 H.GetP();
1050 H.length=H.pLength=pLength(H.p);
1051 ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1052 (flag & KSTD_NF_NONORM)==0);
1053 enterT(H,strat);
1054 H = L;
1055 }
1056 else
1057 {
1058 /*
1059 * we reduce with good ecart, h need not to be put to T
1060 */
1061 ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1062 (flag & KSTD_NF_NONORM)==0);
1063 }
1064 if (H.p == NULL)
1065 return NULL;
1066 /*- try to reduce the s-polynomial -*/
1067 o = H.SetpFDeg();
1068 if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
1069 H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1070 j = 0;
1071 H.sev = pGetShortExpVector(H.p);
1072 }
1073 else
1074 {
1075 j++;
1076 }
1077 }
1078}
1079
1080static poly redMoraNFRing (poly h,kStrategy strat, int flag)
1081{
1082 LObject H;
1083 H.p = h;
1084 int j0, j = 0;
1085 int docoeffred = 0;
1086 poly T0p = strat->T[0].p;
1087 int T0ecart = strat->T[0].ecart;
1088 int o = H.SetpFDeg();
1089 H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
1090 if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
1091 H.sev = pGetShortExpVector(H.p);
1092 unsigned long not_sev = ~ H.sev;
1093 if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2)
1094 {
1095 docoeffred = 1; // euclidean ring required: n_QuotRem
1096 if (currRing->cf->cfQuotRem==ndQuotRem)
1097 {
1098 docoeffred = 0;
1099 }
1100 }
1101 loop
1102 {
1103 /* cut down the lead coefficients, only possible if the degree of
1104 * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
1105 * we ask for the length of T[0] to be <= 2 */
1106 if (docoeffred)
1107 {
1108 j0 = kTestDivisibleByT0_Z(strat, &H);
1109 if ((j0 == 0)
1110 && (n_DivBy(pGetCoeff(H.p), pGetCoeff(T0p), currRing->cf) == FALSE)
1111 && (T0ecart <= H.ecart))
1112 {
1113 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
1114 * => we try to cut down the lead coefficient at least */
1115 /* first copy T[j0] in order to multiply it with a coefficient later on */
1116 number mult, rest;
1117 TObject tj = strat->T[0];
1118 tj.Copy();
1119 /* compute division with remainder of lc(h) and lc(T[j]) */
1120 mult = n_QuotRem(pGetCoeff(H.p), pGetCoeff(T0p),
1121 &rest, currRing->cf);
1122 /* set corresponding new lead coefficient already. we do not
1123 * remove the lead term in ksReducePolyLC, but only apply
1124 * a lead coefficient reduction */
1125 tj.Mult_nn(mult);
1126 ksReducePolyLC(&H, &tj, NULL, &rest, strat);
1127 tj.Delete();
1128 tj.Clear();
1129 }
1130 }
1131 if (j > strat->tl)
1132 {
1133 return H.p;
1134 }
1135 if (TEST_V_DEG_STOP)
1136 {
1137 if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
1138 if (H.p==NULL) return NULL;
1139 }
1140 if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1141 && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1142 )
1143 {
1144 /*- remember the found T-poly -*/
1145 // poly pi = strat->T[j].p;
1146 int ei = strat->T[j].ecart;
1147 int li = strat->T[j].length;
1148 int ii = j;
1149 /*
1150 * the polynomial to reduce with (up to the moment) is;
1151 * pi with ecart ei and length li
1152 */
1153 loop
1154 {
1155 /*- look for a better one with respect to ecart -*/
1156 /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1157 j++;
1158 if (j > strat->tl) break;
1159 if (ei <= H.ecart) break;
1160 if (((strat->T[j].ecart < ei)
1161 || ((strat->T[j].ecart == ei)
1162 && (strat->T[j].length < li)))
1163 && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1164 && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1165 )
1166 {
1167 /*
1168 * the polynomial to reduce with is now;
1169 */
1170 // pi = strat->T[j].p;
1171 ei = strat->T[j].ecart;
1172 li = strat->T[j].length;
1173 ii = j;
1174 }
1175 }
1176 /*
1177 * end of search: have to reduce with pi
1178 */
1179 if ((ei > H.ecart) && (strat->kNoether==NULL))
1180 {
1181 /*
1182 * It is not possible to reduce h with smaller ecart;
1183 * we have to reduce with bad ecart: H has to enter in T
1184 */
1185 LObject L= H;
1186 L.Copy();
1187 H.GetP();
1188 H.length=H.pLength=pLength(H.p);
1189 ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1190 (flag & KSTD_NF_NONORM)==0);
1191 enterT_strong(H,strat);
1192 H = L;
1193 }
1194 else
1195 {
1196 /*
1197 * we reduce with good ecart, h need not to be put to T
1198 */
1199 ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1200 (flag & KSTD_NF_NONORM)==0);
1201 }
1202 if (H.p == NULL)
1203 return NULL;
1204 /*- try to reduce the s-polynomial -*/
1205 o = H.SetpFDeg();
1206 if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1207 H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1208 j = 0;
1209 H.sev = pGetShortExpVector(H.p);
1210 not_sev = ~ H.sev;
1211 }
1212 else
1213 {
1214 j++;
1215 }
1216 }
1217}
1218
1219/*2
1220*reorders L with respect to posInL
1221*/
1223{
1224 int i,j,at;
1225
1226 for (i=1; i<=strat->Ll; i++)
1227 {
1228 at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
1229 if (at != i)
1230 {
1231 LObject p = strat->L[i];
1232 for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
1233 strat->L[at] = p;
1234 }
1235 }
1236}
1237
1238/*2
1239*reorders T with respect to length
1240*/
1242{
1243 int i,j,at;
1244 TObject p;
1245 unsigned long sev;
1246
1247
1248 for (i=1; i<=strat->tl; i++)
1249 {
1250 if (strat->T[i-1].length > strat->T[i].length)
1251 {
1252 p = strat->T[i];
1253 sev = strat->sevT[i];
1254 at = i-1;
1255 loop
1256 {
1257 at--;
1258 if (at < 0) break;
1259 if (strat->T[i].length > strat->T[at].length) break;
1260 }
1261 for (j = i-1; j>at; j--)
1262 {
1263 strat->T[j+1]=strat->T[j];
1264 strat->sevT[j+1]=strat->sevT[j];
1265 strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
1266 }
1267 strat->T[at+1]=p;
1268 strat->sevT[at+1] = sev;
1269 strat->R[p.i_r] = &(strat->T[at+1]);
1270 }
1271 }
1272}
1273
1274/*2
1275*looks whether exactly (currRing->N)-1 axis are used
1276*returns last != 0 in this case
1277*last is the (first) unused axis
1278*/
1279void missingAxis (int* last,kStrategy strat)
1280{
1281 int i = 0;
1282 int k = 0;
1283
1284 *last = 0;
1286 {
1287 loop
1288 {
1289 i++;
1290 if (i > (currRing->N)) break;
1291 if (strat->NotUsedAxis[i])
1292 {
1293 *last = i;
1294 k++;
1295 }
1296 if (k>1)
1297 {
1298 *last = 0;
1299 break;
1300 }
1301 }
1302 }
1303}
1304
1305/*2
1306*last is the only non used axis, it looks
1307*for a monomial in p being a pure power of this
1308*variable and returns TRUE in this case
1309*(*length) gives the length between the pure power and the leading term
1310*(should be minimal)
1311*/
1312BOOLEAN hasPurePower (const poly p,int last, int *length,kStrategy strat)
1313{
1314 poly h;
1315 int i;
1316
1317 if (pNext(p) == strat->tail)
1318 return FALSE;
1319 pp_Test(p, currRing, strat->tailRing);
1320 if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
1321 {
1323 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
1324 if (i == last)
1325 {
1326 *length = 0;
1327 return TRUE;
1328 }
1329 *length = 1;
1330 h = pNext(p);
1331 while (h != NULL)
1332 {
1333 i = p_IsPurePower(h, strat->tailRing);
1334 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
1335 if (i==last) return TRUE;
1336 (*length)++;
1337 pIter(h);
1338 }
1339 }
1340 return FALSE;
1341}
1342
1344{
1345 if (L->bucket != NULL)
1346 {
1347 poly p = L->GetP();
1348 return hasPurePower(p, last, length, strat);
1349 }
1350 else
1351 {
1352 return hasPurePower(L->p, last, length, strat);
1353 }
1354}
1355
1356/*2
1357* looks up the position of polynomial p in L
1358* in the case of looking for the pure powers
1359*/
1360int posInL10 (const LSet set,const int length, LObject* p,const kStrategy strat)
1361{
1362 int j,dp,dL;
1363
1364 if (length<0) return 0;
1365 if (hasPurePower(p,strat->lastAxis,&dp,strat))
1366 {
1367 int op= p->GetpFDeg() +p->ecart;
1368 for (j=length; j>=0; j--)
1369 {
1370 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1371 return j+1;
1372 if (dp < dL)
1373 return j+1;
1374 if ((dp == dL)
1375 && (set[j].GetpFDeg()+set[j].ecart >= op))
1376 return j+1;
1377 }
1378 }
1379 j=length;
1380 loop
1381 {
1382 if (j<0) break;
1383 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1384 j--;
1385 }
1386 return strat->posInLOld(set,j,p,strat);
1387}
1388
1389
1390/*2
1391* computes the s-polynomials L[ ].p in L
1392*/
1394{
1395 int dL;
1396 int j=strat->Ll;
1397 loop
1398 {
1399 if (j<0) break;
1400 if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1401 {
1402 LObject p;
1403 p=strat->L[strat->Ll];
1404 strat->L[strat->Ll]=strat->L[j];
1405 strat->L[j]=p;
1406 break;
1407 }
1408 j--;
1409 }
1410 if (j<0)
1411 {
1412 j=strat->Ll;
1413 loop
1414 {
1415 if (j<0) break;
1416 if (pNext(strat->L[j].p) == strat->tail)
1417 {
1419 pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1420 else
1421 pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1422 strat->L[j].p = NULL;
1423 poly m1 = NULL, m2 = NULL;
1424 // check that spoly creation is ok
1425 while (strat->tailRing != currRing &&
1426 !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1427 {
1428 assume(m1 == NULL && m2 == NULL);
1429 // if not, change to a ring where exponents are at least
1430 // large enough
1431 kStratChangeTailRing(strat);
1432 }
1433 /* create the real one */
1434 ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1435 strat->tailRing, m1, m2, strat->R);
1436
1437 strat->L[j].SetLmCurrRing();
1438 if (!strat->honey)
1439 strat->initEcart(&strat->L[j]);
1440 else
1441 strat->L[j].SetLength(strat->length_pLength);
1442
1443 BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1444
1445 strat->L[j].PrepareRed(strat->use_buckets);
1446
1447 if (pp)
1448 {
1449 LObject p;
1450 p=strat->L[strat->Ll];
1451 strat->L[strat->Ll]=strat->L[j];
1452 strat->L[j]=p;
1453 break;
1454 }
1455 }
1456 j--;
1457 }
1458 }
1459}
1460
1461/*2
1462* computes the s-polynomials L[ ].p in L and
1463* cuts elements in L above noether
1464*/
1466{
1467
1468 int i = 0;
1469 kTest_TS(strat);
1470 while (i <= strat->Ll)
1471 {
1472 if (pNext(strat->L[i].p) == strat->tail)
1473 {
1474 /*- deletes the int spoly and computes -*/
1475 if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
1476 {
1478 pLmDelete(strat->L[i].p);
1479 else
1480 pLmFree(strat->L[i].p);
1481 strat->L[i].p = NULL;
1482 }
1483 else
1484 {
1486 pLmDelete(strat->L[i].p);
1487 else
1488 pLmFree(strat->L[i].p);
1489 strat->L[i].p = NULL;
1490 poly m1 = NULL, m2 = NULL;
1491 // check that spoly creation is ok
1492 while (strat->tailRing != currRing &&
1493 !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
1494 {
1495 assume(m1 == NULL && m2 == NULL);
1496 // if not, change to a ring where exponents are at least
1497 // large enough
1498 kStratChangeTailRing(strat);
1499 }
1500 /* create the real one */
1501 ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
1502 strat->tailRing, m1, m2, strat->R);
1503 if (! strat->L[i].IsNull())
1504 {
1505 strat->L[i].SetLmCurrRing();
1506 strat->L[i].SetpFDeg();
1507 strat->L[i].ecart
1508 = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
1509 if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
1510 }
1511 }
1512 }
1513 deleteHC(&(strat->L[i]), strat);
1514 if (strat->L[i].IsNull())
1515 deleteInL(strat->L,&strat->Ll,i,strat);
1516 else
1517 {
1518#ifdef KDEBUG
1519 kTest_L(&(strat->L[i]), strat, TRUE, i, strat->T, strat->tl);
1520#endif
1521 i++;
1522 }
1523 }
1524 kTest_TS(strat);
1525}
1526
1527/*2
1528* cuts in T above strat->kNoether and tries to cancel a unit
1529* changes also S as S is a subset of T
1530*/
1532{
1533 int i = 0;
1534 LObject p;
1535
1536 while (i <= strat->tl)
1537 {
1538 p = strat->T[i];
1539 deleteHC(&p,strat, TRUE);
1540 /*- tries to cancel a unit: -*/
1541 cancelunit(&p);
1542 if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
1543 p.pCleardenom();
1544 if (p.p != strat->T[i].p)
1545 {
1546 strat->sevT[i] = pGetShortExpVector(p.p);
1547 p.SetpFDeg();
1548 }
1549 strat->T[i] = p;
1550 i++;
1551 }
1552}
1553
1554/*2
1555* arranges red, pos and T if strat->kAllAxis (first time)
1556*/
1558{
1559 if (strat->update)
1560 {
1561 kTest_TS(strat);
1562 strat->update = (strat->tl == -1);
1563 if (TEST_OPT_WEIGHTM)
1564 {
1566 if (strat->tailRing != currRing)
1567 {
1568 strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1569 strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1570 }
1571 int i;
1572 for (i=strat->Ll; i>=0; i--)
1573 {
1574 strat->L[i].SetpFDeg();
1575 }
1576 for (i=strat->tl; i>=0; i--)
1577 {
1578 strat->T[i].SetpFDeg();
1579 }
1580 if (ecartWeights)
1581 {
1582 omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1584 }
1585 }
1586 if (TEST_OPT_FASTHC)
1587 {
1588 strat->posInL = strat->posInLOld;
1589 strat->lastAxis = 0;
1590 }
1591 if (TEST_OPT_FINDET)
1592 return;
1593
1594 strat->use_buckets = kMoraUseBucket(strat);
1595 updateT(strat);
1596
1598 {
1599 strat->posInT = posInT2;
1600 reorderT(strat);
1601 }
1602 }
1603 kTest_TS(strat);
1604}
1605
1606/*2
1607*-puts p to the standardbasis s at position at
1608*-reduces the tail of p if TEST_OPT_REDTAIL
1609*-tries to cancel a unit
1610*-HEckeTest
1611* if TRUE
1612* - decides about reduction-strategies
1613* - computes noether
1614* - stops computation if TEST_OPT_FINDET
1615* - cuts the tails of the polynomials
1616* in s,t and the elements in L above noether
1617* and cancels units if possible
1618* - reorders s,L
1619*/
1620void enterSMora (LObject &p,int atS,kStrategy strat, int atR = -1)
1621{
1622 enterSBba(p, atS, strat, atR);
1623 #ifdef KDEBUG
1624 if (TEST_OPT_DEBUG)
1625 {
1626 Print("new s%d:",atS);
1627 p_wrp(p.p,currRing,strat->tailRing);
1628 PrintLn();
1629 }
1630 #endif
1631 HEckeTest(p.p,strat);
1632 if (strat->kAllAxis)
1633 {
1634 if (newHEdge(strat))
1635 {
1636 firstUpdate(strat);
1637 if (TEST_OPT_FINDET)
1638 return;
1639
1640 /*- cuts elements in L above noether and reorders L -*/
1641 updateLHC(strat);
1642 /*- reorders L with respect to posInL -*/
1643 reorderL(strat);
1644 }
1645 }
1646 else if ((strat->kNoether==NULL)
1647 && (TEST_OPT_FASTHC))
1648 {
1649 if (strat->posInLOldFlag)
1650 {
1651 missingAxis(&strat->lastAxis,strat);
1652 if (strat->lastAxis)
1653 {
1654 strat->posInLOld = strat->posInL;
1655 strat->posInLOldFlag = FALSE;
1656 strat->posInL = posInL10;
1657 strat->posInLDependsOnLength = TRUE;
1658 updateL(strat);
1659 reorderL(strat);
1660 }
1661 }
1662 else if (strat->lastAxis)
1663 updateL(strat);
1664 }
1665}
1666
1667/*2
1668*-puts p to the standardbasis s at position at
1669*-HEckeTest
1670* if TRUE
1671* - computes noether
1672*/
1673void enterSMoraNF (LObject &p, int atS,kStrategy strat, int atR = -1)
1674{
1675 enterSBba(p, atS, strat, atR);
1676 if ((!strat->kAllAxis) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1677 if (strat->kAllAxis)
1678 newHEdge(strat);
1679}
1680
1682{
1683 /* setting global variables ------------------- */
1684 strat->enterS = enterSBba;
1685 strat->red = redHoney;
1686 if (strat->honey)
1687 strat->red = redHoney;
1688 else if (currRing->pLexOrder && !strat->homog)
1689 strat->red = redLazy;
1690 else
1691 {
1692 strat->LazyPass *=4;
1693 strat->red = redHomog;
1694 }
1696 {
1697 if (rField_is_Z(currRing))
1698 strat->red = redRing_Z;
1699 else
1700 strat->red = redRing;
1701 }
1702 if (TEST_OPT_IDLIFT
1703 && (!rIsNCRing(currRing))
1704 && (!rField_is_Ring(currRing)))
1705 strat->red=redLiftstd;
1706 if (currRing->pLexOrder && strat->honey)
1707 strat->initEcart = initEcartNormal;
1708 else
1709 strat->initEcart = initEcartBBA;
1710 if (strat->honey)
1712 else
1714// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1715// {
1716// //interred machen Aenderung
1717// strat->pOrigFDeg=pFDeg;
1718// strat->pOrigLDeg=pLDeg;
1719// //h=ggetid("ecart");
1720// //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1721// //{
1722// // ecartWeights=iv2array(IDINTVEC(h));
1723// //}
1724// //else
1725// {
1726// ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1727// /*uses automatic computation of the ecartWeights to set them*/
1728// kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1729// }
1730// pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1731// if (TEST_OPT_PROT)
1732// {
1733// for(i=1; i<=(currRing->N); i++)
1734// Print(" %d",ecartWeights[i]);
1735// PrintLn();
1736// mflush();
1737// }
1738// }
1739}
1740
1741void initSba(ideal F,kStrategy strat)
1742{
1743 int i;
1744 //idhdl h;
1745 /* setting global variables ------------------- */
1746 strat->enterS = enterSSba;
1747 strat->red2 = redHoney;
1748 if (strat->honey)
1749 strat->red2 = redHoney;
1750 else if (currRing->pLexOrder && !strat->homog)
1751 strat->red2 = redLazy;
1752 else
1753 {
1754 strat->LazyPass *=4;
1755 strat->red2 = redHomog;
1756 }
1758 {
1760 {strat->red2 = redRiloc;}
1761 else
1762 {strat->red2 = redRing;}
1763 }
1764 if (currRing->pLexOrder && strat->honey)
1765 strat->initEcart = initEcartNormal;
1766 else
1767 strat->initEcart = initEcartBBA;
1768 if (strat->honey)
1770 else
1772 //strat->kIdeal = NULL;
1773 //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1774 //else strat->kIdeal->rtyp=MODUL_CMD;
1775 //strat->kIdeal->data=(void *)strat->Shdl;
1776 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1777 {
1778 //interred machen Aenderung
1779 strat->pOrigFDeg = currRing->pFDeg;
1780 strat->pOrigLDeg = currRing->pLDeg;
1781 //h=ggetid("ecart");
1782 //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1783 //{
1784 // ecartWeights=iv2array(IDINTVEC(h));
1785 //}
1786 //else
1787 {
1788 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1789 /*uses automatic computation of the ecartWeights to set them*/
1791 }
1793 if (TEST_OPT_PROT)
1794 {
1795 for(i=1; i<=(currRing->N); i++)
1796 Print(" %d",ecartWeights[i]);
1797 PrintLn();
1798 mflush();
1799 }
1800 }
1801 // for sig-safe reductions in signature-based
1802 // standard basis computations
1804 strat->red = redSigRing;
1805 else
1806 strat->red = redSig;
1807 //strat->sbaOrder = 1;
1808 strat->currIdx = 1;
1809}
1810
1811void initMora(ideal F,kStrategy strat)
1812{
1813 int i,j;
1814
1815 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1816 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1817 strat->enterS = enterSMora;
1818 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1819 strat->posInLOld = strat->posInL;
1820 strat->posInLOldFlag = TRUE;
1821 strat->initEcart = initEcartNormal;
1822 if (strat->homog)
1823 strat->red = redFirst; /*take the first possible in T*/
1824 else
1825 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1826 if ( currRing->ppNoether!=NULL )
1827 {
1828 strat->kNoether = pCopy((currRing->ppNoether));
1829 if (TEST_OPT_PROT)
1830 {
1831 Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
1832 mflush();
1833 }
1834 }
1835 if (strat->kNoether!=NULL)
1836 {
1837 HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
1838 }
1839 else
1840 {
1841 HCord = INT_MAX-3;/*- very large -*/
1842 }
1843
1845 {
1846 if (rField_is_Z(currRing))
1847 strat->red = redRiloc_Z;
1848 else
1849 strat->red = redRiloc;
1850 }
1851
1852 /*reads the ecartWeights used for Graebes method from the
1853 *intvec ecart and set ecartWeights
1854 */
1855 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1856 {
1857 //interred machen Aenderung
1858 strat->pOrigFDeg=currRing->pFDeg;
1859 strat->pOrigLDeg=currRing->pLDeg;
1860 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1861 /*uses automatic computation of the ecartWeights to set them*/
1863
1865 if (TEST_OPT_PROT)
1866 {
1867 for(i=1; i<=(currRing->N); i++)
1868 Print(" %d",ecartWeights[i]);
1869 PrintLn();
1870 mflush();
1871 }
1872 }
1873 kOptimizeLDeg(currRing->pLDeg, strat);
1874}
1875
1876void kDebugPrint(kStrategy strat);
1877
1878ideal mora (ideal F, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat)
1879{
1880 int olddeg = 0;
1881 int reduc = 0;
1882 int red_result = 1;
1883 int hilbeledeg=1,hilbcount=0;
1884 BITSET save1;
1885 SI_SAVE_OPT1(save1);
1887 {
1890 }
1891
1892 strat->update = TRUE;
1893 /*- setting global variables ------------------- -*/
1894 initBuchMoraCrit(strat);
1895 initHilbCrit(F,Q,&hilb,strat);
1896 initMora(F,strat);
1898 initBuchMoraPosRing(strat);
1899 else
1900 initBuchMoraPos(strat);
1901 /*Shdl=*/initBuchMora(F,Q,strat);
1902 if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1903 /*updateS in initBuchMora has Hecketest
1904 * and could have put strat->kHEdgdeFound FALSE*/
1905 if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1906 {
1907 strat->posInLOld = strat->posInL;
1908 strat->posInLOldFlag = FALSE;
1909 strat->posInL = posInL10;
1910 updateL(strat);
1911 reorderL(strat);
1912 }
1913 kTest_TS(strat);
1914 strat->use_buckets = kMoraUseBucket(strat);
1915
1916#ifdef HAVE_TAIL_RING
1917 if (strat->homog && strat->red == redFirst)
1918 if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1920#endif
1921
1922 if (BVERBOSE(23))
1923 {
1924 kDebugPrint(strat);
1925 }
1926//deleteInL(strat->L,&strat->Ll,1,strat);
1927//deleteInL(strat->L,&strat->Ll,0,strat);
1928
1929 /*- compute-------------------------------------------*/
1930 while (strat->Ll >= 0)
1931 {
1932 #ifdef KDEBUG
1933 if (TEST_OPT_DEBUG) messageSets(strat);
1934 #endif
1935 if (siCntrlc)
1936 {
1937 while (strat->Ll >= 0)
1938 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1939 strat->noClearS=TRUE;
1940 }
1942 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1943 {
1944 /*
1945 * stops computation if
1946 * - 24 (degBound)
1947 * && upper degree is bigger than Kstd1_deg
1948 */
1949 while ((strat->Ll >= 0)
1950 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1951 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1952 )
1953 {
1954 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1955 //if (TEST_OPT_PROT)
1956 //{
1957 // PrintS("D"); mflush();
1958 //}
1959 }
1960 if (strat->Ll<0) break;
1961 else strat->noClearS=TRUE;
1962 }
1963 strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1964 if (strat->Ll==0) strat->interpt=TRUE;
1965 strat->Ll--;
1966 // create the real Spoly
1967 if (pNext(strat->P.p) == strat->tail)
1968 {
1969 /*- deletes the short spoly and computes -*/
1971 pLmDelete(strat->P.p);
1972 else
1973 pLmFree(strat->P.p);
1974 strat->P.p = NULL;
1975 poly m1 = NULL, m2 = NULL;
1976 // check that spoly creation is ok
1977 while (strat->tailRing != currRing &&
1978 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1979 {
1980 assume(m1 == NULL && m2 == NULL);
1981 // if not, change to a ring where exponents are large enough
1982 kStratChangeTailRing(strat);
1983 }
1984 /* create the real one */
1985 ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1986 strat->tailRing, m1, m2, strat->R);
1987 if (!strat->use_buckets)
1988 strat->P.SetLength(strat->length_pLength);
1989 strat->P.PrepareRed(strat->use_buckets);
1990 }
1991 else if (strat->P.p1 == NULL)
1992 {
1993 // for input polys, prepare reduction (buckets !)
1994 strat->P.SetLength(strat->length_pLength);
1995 strat->P.PrepareRed(strat->use_buckets);
1996 }
1997
1998 // the s-poly
1999 if (!strat->P.IsNull())
2000 {
2001 // might be NULL from noether !!!
2002 if (TEST_OPT_PROT)
2003 message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
2004 // reduce
2005 red_result = strat->red(&strat->P,strat);
2006 }
2007
2008 // the reduced s-poly
2009 if (! strat->P.IsNull())
2010 {
2011 strat->P.GetP();
2012 // statistics
2013 if (TEST_OPT_PROT) PrintS("s");
2014 // normalization
2016 strat->P.pCleardenom();
2017 else
2018 strat->P.pNorm();
2019 // tailreduction
2020 strat->P.p = redtail(&(strat->P),strat->sl,strat);
2021 if (strat->P.p==NULL)
2022 {
2023 WerrorS("exponent overflow - wrong ordering");
2024 return(idInit(1,1));
2025 }
2026 // set ecart -- might have changed because of tail reductions
2027 if ((!strat->noTailReduction) && (!strat->honey))
2028 strat->initEcart(&strat->P);
2029 // cancel unit
2030 cancelunit(&strat->P);
2031 // for char 0, clear denominators
2032 if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2034 strat->P.pCleardenom();
2035
2036 strat->P.SetShortExpVector();
2037 enterT(strat->P,strat);
2038 // build new pairs
2040 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2041 else
2042 enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2043 // put in S
2044 strat->enterS(strat->P,
2045 posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2046 strat, strat->tl);
2047 // apply hilbert criterion
2048 if (hilb!=NULL)
2049 {
2050 if (strat->homog==isHomog)
2051 khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2052 else
2053 khCheckLocInhom(Q,w,hilb,hilbcount,strat);
2054 }
2055
2056 // clear strat->P
2057 kDeleteLcm(&strat->P);
2058
2059#ifdef KDEBUG
2060 // make sure kTest_TS does not complain about strat->P
2061 strat->P.Clear();
2062#endif
2063 }
2064 if (strat->kAllAxis)
2065 {
2066 if ((TEST_OPT_FINDET)
2067 || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL) < Kstd1_mu)))
2068 {
2069 // obachman: is this still used ???
2070 /*
2071 * stops computation if strat->kAllAxis and
2072 * - 27 (finiteDeterminacyTest)
2073 * or
2074 * - 23
2075 * (multBound)
2076 * && multiplicity of the ideal is smaller then a predefined number mu
2077 */
2078 while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2079 }
2080 }
2081 kTest_TS(strat);
2082 }
2083 /*- complete reduction of the standard basis------------------------ -*/
2084 if (TEST_OPT_REDSB) completeReduce(strat);
2085 else if (TEST_OPT_PROT) PrintLn();
2086 /*- release temp data------------------------------- -*/
2087 exitBuchMora(strat);
2088 /*- polynomials used for HECKE: HC, noether -*/
2089 if (TEST_OPT_FINDET)
2090 {
2091 if (strat->kNoether!=NULL)
2092 Kstd1_mu=currRing->pFDeg(strat->kNoether,currRing);
2093 else
2094 Kstd1_mu=-1;
2095 }
2096 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2097 if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2098// if (TEST_OPT_WEIGHTM)
2099// {
2100// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2101// if (ecartWeights)
2102// {
2103// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2104// ecartWeights=NULL;
2105// }
2106// }
2107 if(nCoeff_is_Z(currRing->cf))
2108 finalReduceByMon(strat);
2109 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2110 SI_RESTORE_OPT1(save1);
2111 idTest(strat->Shdl);
2112 return (strat->Shdl);
2113}
2114
2115poly kNF1 (ideal F,ideal Q,poly q, kStrategy strat, int lazyReduce)
2116{
2117 assume(q!=NULL);
2118 assume(!(idIs0(F)&&(Q==NULL)));
2119
2120// lazy_reduce flags: can be combined by |
2121//#define KSTD_NF_LAZY 1
2122 // do only a reduction of the leading term
2123//#define KSTD_NF_ECART 2
2124 // only local: reduce even with bad ecart
2125 poly p;
2126 int i;
2127 int j;
2128 int o;
2129 LObject h;
2130 BITSET save1;
2131 SI_SAVE_OPT1(save1);
2132
2133 //if ((idIs0(F))&&(Q==NULL))
2134 // return pCopy(q); /*F=0*/
2135 //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
2136 /*- creating temp data structures------------------- -*/
2137 strat->kAllAxis = (currRing->ppNoether) != NULL;
2138 strat->kNoether = pCopy((currRing->ppNoether));
2143 && (! TEST_V_DEG_STOP)
2144 && (0<Kstd1_deg)
2145 && ((strat->kNoether==NULL)
2147 {
2148 pLmDelete(&strat->kNoether);
2149 strat->kNoether=pOne();
2150 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2151 pSetm(strat->kNoether);
2152 // strat->kAllAxis=TRUE;
2153 }
2154 initBuchMoraCrit(strat);
2156 initBuchMoraPosRing(strat);
2157 else
2158 initBuchMoraPos(strat);
2159 initMora(F,strat);
2160 strat->enterS = enterSMoraNF;
2161 /*- set T -*/
2162 strat->tl = -1;
2163 strat->tmax = setmaxT;
2164 strat->T = initT();
2165 strat->R = initR();
2166 strat->sevT = initsevT();
2167 /*- set S -*/
2168 strat->sl = -1;
2169 /*- init local data struct.-------------------------- -*/
2170 /*Shdl=*/initS(F,Q,strat);
2171 if ((strat->ak!=0)
2172 && (strat->kAllAxis)) /*never true for ring-cf*/
2173 {
2174 if (strat->ak!=1)
2175 {
2176 pSetComp(strat->kNoether,1);
2177 pSetmComp(strat->kNoether);
2178 poly p=pHead(strat->kNoether);
2179 pSetComp(p,strat->ak);
2180 pSetmComp(p);
2181 p=pAdd(strat->kNoether,p);
2182 strat->kNoether=pNext(p);
2184 }
2185 }
2186 if (((lazyReduce & KSTD_NF_LAZY)==0)
2187 && (!rField_is_Ring(currRing)))
2188 {
2189 for (i=strat->sl; i>=0; i--)
2190 pNorm(strat->S[i]);
2191 }
2192 /*- puts the elements of S also to T -*/
2193 for (i=0; i<=strat->sl; i++)
2194 {
2195 h.p = strat->S[i];
2196 h.ecart = strat->ecartS[i];
2197 if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
2198 else assume(strat->sevS[i] == pGetShortExpVector(h.p));
2199 h.length = pLength(h.p);
2200 h.sev = strat->sevS[i];
2201 h.SetpFDeg();
2202 enterT(h,strat);
2203 }
2204#ifdef KDEBUG
2205// kDebugPrint(strat);
2206#endif
2207 /*- compute------------------------------------------- -*/
2208 p = pCopy(q);
2209 deleteHC(&p,&o,&j,strat);
2210 kTest(strat);
2211 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2212 if (BVERBOSE(23)) kDebugPrint(strat);
2214 {
2215 if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & (KSTD_NF_ECART|KSTD_NF_CANCELUNIT));
2216 }
2217 else
2218 {
2219 if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & (KSTD_NF_ECART|KSTD_NF_CANCELUNIT));
2220 }
2221 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2222 {
2223 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2224 p = redtail(p,strat->sl,strat);
2225 }
2226 /*- release temp data------------------------------- -*/
2227 cleanT(strat);
2228 assume(strat->L==NULL); /*strat->L unused */
2229 assume(strat->B==NULL); /*strat->B unused */
2230 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2231 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2232 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2233 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2234 omFree(strat->sevT);
2235 omFree(strat->S_2_R);
2236 omFree(strat->R);
2237
2238 omfree((ADDRESS)strat->fromQ);
2239 strat->fromQ=NULL;
2240 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2241// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2242// {
2243// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2244// if (ecartWeights)
2245// {
2246// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2247// ecartWeights=NULL;
2248// }
2249// }
2250 idDelete(&strat->Shdl);
2251 SI_RESTORE_OPT1(save1);
2252 if (TEST_OPT_PROT) PrintLn();
2253 return p;
2254}
2255
2256ideal kNF1 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce)
2257{
2258 assume(!idIs0(q));
2259 assume(!(idIs0(F)&&(Q==NULL)));
2260
2261// lazy_reduce flags: can be combined by |
2262//#define KSTD_NF_LAZY 1
2263 // do only a reduction of the leading term
2264//#define KSTD_NF_ECART 2
2265 // only local: reduce even with bad ecart
2266 poly p;
2267 int i;
2268 int j;
2269 int o;
2270 LObject h;
2271 ideal res;
2272 BITSET save1;
2273 SI_SAVE_OPT1(save1);
2274
2275 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2276 //if ((idIs0(F))&&(Q==NULL))
2277 // return idCopy(q); /*F=0*/
2278 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2279 /*- creating temp data structures------------------- -*/
2280 strat->kAllAxis = (currRing->ppNoether) != NULL;
2281 strat->kNoether=pCopy((currRing->ppNoether));
2284 && (0<Kstd1_deg)
2285 && ((strat->kNoether==NULL)
2287 {
2288 pLmDelete(&strat->kNoether);
2289 strat->kNoether=pOne();
2290 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2291 pSetm(strat->kNoether);
2292 //strat->kAllAxis=TRUE;
2293 }
2294 initBuchMoraCrit(strat);
2296 initBuchMoraPosRing(strat);
2297 else
2298 initBuchMoraPos(strat);
2299 initMora(F,strat);
2300 strat->enterS = enterSMoraNF;
2301 /*- set T -*/
2302 strat->tl = -1;
2303 strat->tmax = setmaxT;
2304 strat->T = initT();
2305 strat->R = initR();
2306 strat->sevT = initsevT();
2307 /*- set S -*/
2308 strat->sl = -1;
2309 /*- init local data struct.-------------------------- -*/
2310 /*Shdl=*/initS(F,Q,strat);
2311 if ((strat->ak!=0)
2312 && (strat->kNoether!=NULL))
2313 {
2314 if (strat->ak!=1)
2315 {
2316 pSetComp(strat->kNoether,1);
2317 pSetmComp(strat->kNoether);
2318 poly p=pHead(strat->kNoether);
2319 pSetComp(p,strat->ak);
2320 pSetmComp(p);
2321 p=pAdd(strat->kNoether,p);
2322 strat->kNoether=pNext(p);
2324 }
2325 }
2326 if (((lazyReduce & KSTD_NF_LAZY)==0)
2327 && (!rField_is_Ring(currRing)))
2328 {
2329 for (i=strat->sl; i>=0; i--)
2330 pNorm(strat->S[i]);
2331 }
2332 /*- compute------------------------------------------- -*/
2333 res=idInit(IDELEMS(q),strat->ak);
2334 for (i=0; i<IDELEMS(q); i++)
2335 {
2336 if (q->m[i]!=NULL)
2337 {
2338 p = pCopy(q->m[i]);
2339 deleteHC(&p,&o,&j,strat);
2340 if (p!=NULL)
2341 {
2342 /*- puts the elements of S also to T -*/
2343 for (j=0; j<=strat->sl; j++)
2344 {
2345 h.p = strat->S[j];
2346 h.ecart = strat->ecartS[j];
2347 h.pLength = h.length = pLength(h.p);
2348 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2349 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2350 h.sev = strat->sevS[j];
2351 h.SetpFDeg();
2353 enterT_strong(h,strat);
2354 else
2355 enterT(h,strat);
2356 }
2357 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2359 {
2360 p = redMoraNFRing(p,strat, lazyReduce);
2361 }
2362 else
2363 p = redMoraNF(p,strat, lazyReduce);
2364 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2365 {
2366 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2367 p = redtail(p,strat->sl,strat);
2368 }
2369 cleanT(strat);
2370 }
2371 res->m[i]=p;
2372 }
2373 //else
2374 // res->m[i]=NULL;
2375 }
2376 /*- release temp data------------------------------- -*/
2377 assume(strat->L==NULL); /*strat->L unused */
2378 assume(strat->B==NULL); /*strat->B unused */
2379 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2380 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2381 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2382 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2383 omFree(strat->sevT);
2384 omFree(strat->S_2_R);
2385 omFree(strat->R);
2386 omfree((ADDRESS)strat->fromQ);
2387 strat->fromQ=NULL;
2388 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2389// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2390// {
2391// pFDeg=strat->pOrigFDeg;
2392// pLDeg=strat->pOrigLDeg;
2393// if (ecartWeights)
2394// {
2395// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2396// ecartWeights=NULL;
2397// }
2398// }
2399 idDelete(&strat->Shdl);
2400 SI_RESTORE_OPT1(save1);
2401 if (TEST_OPT_PROT) PrintLn();
2402 return res;
2403}
2404
2406
2407long kModDeg(poly p,const ring r)
2408{
2409 long o=p_WDegree(p, r);
2410 long i=__p_GetComp(p, r);
2411 if (i==0) return o;
2412 //assume((i>0) && (i<=kModW->length()));
2413 if (i<=kModW->length())
2414 return o+(*kModW)[i-1];
2415 return o;
2416}
2417long kHomModDeg(poly p,const ring r)
2418{
2419 int i;
2420 long j=0;
2421
2422 for (i=r->N;i>0;i--)
2423 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2424 if (kModW == NULL) return j;
2425 i = __p_GetComp(p,r);
2426 if (i==0) return j;
2427 return j+(*kModW)[i-1];
2428}
2429
2430ideal kStd_internal(ideal F, ideal Q, tHomog h,intvec ** w, bigintmat *hilb,
2431 int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
2432{
2433 assume(!idIs0(F));
2434 assume((Q==NULL)||(!idIs0(Q)));
2435
2436 kStrategy strat=new skStrategy;
2437
2438 ideal r;
2439 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2440 BOOLEAN delete_w=(w==NULL);
2441
2442 strat->s_poly=sp;
2444 strat->syzComp = syzComp;
2445 if (TEST_OPT_SB_1
2447 )
2448 strat->newIdeal = newIdeal;
2450 strat->LazyPass=20;
2451 else
2452 strat->LazyPass=2;
2453 strat->LazyDegree = 1;
2454 strat->ak = 0;
2455 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2456 strat->kModW=kModW=NULL;
2457 strat->kHomW=kHomW=NULL;
2458 if (vw != NULL)
2459 {
2460 currRing->pLexOrder=FALSE;
2461 strat->kHomW=kHomW=vw;
2462 strat->pOrigFDeg = currRing->pFDeg;
2463 strat->pOrigLDeg = currRing->pLDeg;
2465 toReset = TRUE;
2466 }
2467 if (h==testHomog)
2468 {
2469 if (strat->ak == 0)
2470 {
2471 h = (tHomog)idHomIdeal(F,Q);
2472 w=NULL;
2473 }
2474 else if (!TEST_OPT_DEGBOUND)
2475 {
2476 if (w!=NULL)
2477 h = (tHomog)idHomModule(F,Q,w);
2478 else
2479 h = (tHomog)idHomIdeal(F,Q);
2480 }
2481 }
2482 currRing->pLexOrder=b;
2483 if (h==isHomog)
2484 {
2485 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2486 {
2487 strat->kModW = kModW = *w;
2488 if (vw == NULL)
2489 {
2490 strat->pOrigFDeg = currRing->pFDeg;
2491 strat->pOrigLDeg = currRing->pLDeg;
2493 toReset = TRUE;
2494 }
2495 }
2496 currRing->pLexOrder = TRUE;
2497 if (hilb==NULL) strat->LazyPass*=2;
2498 }
2499 strat->homog=h;
2500#ifdef KDEBUG
2501 idTest(F);
2502 if (Q!=NULL) idTest(Q);
2503#endif
2504#ifdef HAVE_PLURAL
2506 {
2507 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2508 strat->no_prod_crit = ! bIsSCA;
2509 if (w!=NULL)
2510 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2511 else
2512 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2513 }
2514 else
2515#endif
2516 {
2517 #if PRE_INTEGER_CHECK
2518 //the preinteger check strategy is not for modules
2519 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2520 {
2521 ideal FCopy = idCopy(F);
2522 poly pFmon = preIntegerCheck(FCopy, Q);
2523 if(pFmon != NULL)
2524 {
2525 idInsertPoly(FCopy, pFmon);
2526 strat->kModW=kModW=NULL;
2527 if (h==testHomog)
2528 {
2529 h = (tHomog)idHomIdeal(FCopy,Q);
2530 w=NULL;
2531 }
2532 currRing->pLexOrder=b;
2533 if (h==isHomog)
2534 {
2535 if ((w!=NULL) && (*w!=NULL))
2536 {
2537 strat->kModW = kModW = *w;
2538 if (vw == NULL)
2539 {
2540 strat->pOrigFDeg = currRing->pFDeg;
2541 strat->pOrigLDeg = currRing->pLDeg;
2543 toReset = TRUE;
2544 }
2545 }
2546 currRing->pLexOrder = TRUE;
2547 if (hilb==NULL) strat->LazyPass*=2;
2548 }
2549 strat->homog=h;
2550 }
2551 omTestMemory(1);
2552 if(w == NULL)
2553 {
2555 r=mora(FCopy,Q,NULL,hilb,strat);
2556 else
2557 r=bba(FCopy,Q,NULL,hilb,strat);
2558 }
2559 else
2560 {
2562 r=mora(FCopy,Q,*w,hilb,strat);
2563 else
2564 r=bba(FCopy,Q,*w,hilb,strat);
2565 }
2566 idDelete(&FCopy);
2567 }
2568 else
2569 #endif
2570 {
2571 if(w==NULL)
2572 {
2574 r=mora(F,Q,NULL,hilb,strat);
2575 else
2576 r=bba(F,Q,NULL,hilb,strat);
2577 }
2578 else
2579 {
2581 r=mora(F,Q,*w,hilb,strat);
2582 else
2583 r=bba(F,Q,*w,hilb,strat);
2584 }
2585 }
2586 }
2587#ifdef KDEBUG
2588 idTest(r);
2589#endif
2590 if (toReset)
2591 {
2592 kModW = NULL;
2594 }
2595 currRing->pLexOrder = b;
2596//Print("%d reductions canceled \n",strat->cel);
2597 delete(strat);
2598 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2599 return r;
2600}
2601
2602ideal kStd2(ideal F, ideal Q, tHomog h,intvec ** w, bigintmat *hilb,int syzComp,
2603 int newIdeal, intvec *vw, s_poly_proc_t sp)
2604{
2605 if(idIs0(F))
2606 return idInit(1,F->rank);
2607
2608 if(idIs0(Q)) Q=NULL;
2609#ifdef HAVE_SHIFTBBA
2610 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2611#endif
2612
2613 if ((hilb==NULL)
2614 && (vw==NULL)
2615 && (newIdeal==0)
2616 && (sp==NULL)
2617 && (IDELEMS(F)>1)
2618 && (!TEST_OPT_SB_1)
2619 && (currRing->ppNoether==NULL)
2620 && !rIsPluralRing(currRing) /*!rIsLPRing already tested above*/
2621 && (!id_IsModule(F,currRing)))
2622 {
2623 /* test HC precomputation*/
2627 && (!idIsMonomial(F)))
2628 {
2629 currRing->ppNoether=kTryHC(F,Q);
2630 ideal res=kStd_internal(F,Q,h,w,hilb,syzComp,newIdeal,vw,sp);
2631 if (currRing->ppNoether!=NULL) pLmDelete(currRing->ppNoether);
2632 currRing->ppNoether=NULL;
2633 return res;
2634 }
2635 /* test hilbstd */
2638 && (!TEST_OPT_RETURN_SB)
2639 && (currRing->LexOrder
2641 && (!idIsMonomial(F)))
2642 {
2643 ideal result=kTryHilbstd(F,Q);
2644 //ideal result=kTryHilbstd_par(F,Q,h,w);
2645 if (result!=NULL)
2646 {
2647 return result;
2648 }
2649 }
2650 }
2651 return kStd_internal(F,Q,h,w,hilb,syzComp,newIdeal,vw,sp);
2652}
2653
2654ideal kStd(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2655 int newIdeal, intvec *vw, s_poly_proc_t sp)
2656{
2657 bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
2658 ideal res=kStd2(F,Q,h,w,hh,syzComp,newIdeal,vw,sp);
2659 if (hh!=NULL) delete hh;
2660 return res;
2661}
2662
2663ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int sbaOrder, int arri, bigintmat *hilb,int syzComp,
2664 int newIdeal, intvec *vw)
2665{
2666 if(idIs0(F))
2667 return idInit(1,F->rank);
2669 {
2670 ideal r;
2671 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2672 BOOLEAN delete_w=(w==NULL);
2673 kStrategy strat=new skStrategy;
2674 strat->sbaOrder = sbaOrder;
2675 if (arri!=0)
2676 {
2677 strat->rewCrit1 = arriRewDummy;
2678 strat->rewCrit2 = arriRewCriterion;
2680 }
2681 else
2682 {
2686 }
2687
2689 strat->syzComp = syzComp;
2690 if (TEST_OPT_SB_1)
2691 //if(!rField_is_Ring(currRing)) // always true here
2692 strat->newIdeal = newIdeal;
2694 strat->LazyPass=20;
2695 else
2696 strat->LazyPass=2;
2697 strat->LazyDegree = 1;
2701 strat->ak = 0;
2702 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2703 strat->kModW=kModW=NULL;
2704 strat->kHomW=kHomW=NULL;
2705 if (vw != NULL)
2706 {
2707 currRing->pLexOrder=FALSE;
2708 strat->kHomW=kHomW=vw;
2709 strat->pOrigFDeg = currRing->pFDeg;
2710 strat->pOrigLDeg = currRing->pLDeg;
2712 toReset = TRUE;
2713 }
2714 if (h==testHomog)
2715 {
2716 if (strat->ak == 0)
2717 {
2718 h = (tHomog)idHomIdeal(F,Q);
2719 w=NULL;
2720 }
2721 else if (!TEST_OPT_DEGBOUND)
2722 {
2723 if (w!=NULL)
2724 h = (tHomog)idHomModule(F,Q,w);
2725 else
2726 h = (tHomog)idHomIdeal(F,Q);
2727 }
2728 }
2729 currRing->pLexOrder=b;
2730 if (h==isHomog)
2731 {
2732 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2733 {
2734 strat->kModW = kModW = *w;
2735 if (vw == NULL)
2736 {
2737 strat->pOrigFDeg = currRing->pFDeg;
2738 strat->pOrigLDeg = currRing->pLDeg;
2740 toReset = TRUE;
2741 }
2742 }
2743 currRing->pLexOrder = TRUE;
2744 if (hilb==NULL) strat->LazyPass*=2;
2745 }
2746 strat->homog=h;
2747 #ifdef KDEBUG
2748 idTest(F);
2749 if(Q != NULL)
2750 idTest(Q);
2751 #endif
2752 #ifdef HAVE_PLURAL
2754 {
2755 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2756 strat->no_prod_crit = ! bIsSCA;
2757 if (w!=NULL)
2758 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2759 else
2760 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2761 }
2762 else
2763 #endif
2764 {
2766 {
2767 if (w!=NULL)
2768 r=mora(F,Q,*w,hilb,strat);
2769 else
2770 r=mora(F,Q,NULL,hilb,strat);
2771 }
2772 else
2773 {
2774 strat->sigdrop = FALSE;
2775 if (w!=NULL)
2776 r=sba(F,Q,*w,hilb,strat);
2777 else
2778 r=sba(F,Q,NULL,hilb,strat);
2779 }
2780 }
2781 #ifdef KDEBUG
2782 idTest(r);
2783 #endif
2784 if (toReset)
2785 {
2786 kModW = NULL;
2788 }
2789 currRing->pLexOrder = b;
2790 //Print("%d reductions canceled \n",strat->cel);
2791 //delete(strat);
2792 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2793 return r;
2794 }
2795 else
2796 {
2797 //--------------------------RING CASE-------------------------
2798 assume(sbaOrder == 1);
2799 assume(arri == 0);
2800 ideal r;
2801 r = idCopy(F);
2802 int sbaEnterS = -1;
2803 bool sigdrop = TRUE;
2804 //This is how we set the SBA algorithm;
2805 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2806 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2807 && (blockred <= blockedreductions))
2808 {
2809 loops++;
2810 if(loops == 1)
2811 sigdrop = FALSE;
2812 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2813 BOOLEAN delete_w=(w==NULL);
2814 kStrategy strat=new skStrategy;
2815 strat->sbaEnterS = sbaEnterS;
2816 strat->sigdrop = sigdrop;
2817 #if 0
2818 strat->blockred = blockred;
2819 #else
2820 strat->blockred = 0;
2821 #endif
2822 strat->blockredmax = blockedreductions;
2823 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2824 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2825 strat->sbaOrder = sbaOrder;
2826 if (arri!=0)
2827 {
2828 strat->rewCrit1 = arriRewDummy;
2829 strat->rewCrit2 = arriRewCriterion;
2831 }
2832 else
2833 {
2837 }
2838
2840 strat->syzComp = syzComp;
2841 if (TEST_OPT_SB_1)
2843 strat->newIdeal = newIdeal;
2845 strat->LazyPass=20;
2846 else
2847 strat->LazyPass=2;
2848 strat->LazyDegree = 1;
2852 strat->ak = 0;
2853 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2854 strat->kModW=kModW=NULL;
2855 strat->kHomW=kHomW=NULL;
2856 if (vw != NULL)
2857 {
2858 currRing->pLexOrder=FALSE;
2859 strat->kHomW=kHomW=vw;
2860 strat->pOrigFDeg = currRing->pFDeg;
2861 strat->pOrigLDeg = currRing->pLDeg;
2863 toReset = TRUE;
2864 }
2865 if (h==testHomog)
2866 {
2867 if (strat->ak == 0)
2868 {
2869 h = (tHomog)idHomIdeal(F,Q);
2870 w=NULL;
2871 }
2872 else if (!TEST_OPT_DEGBOUND)
2873 {
2874 if (w!=NULL)
2875 h = (tHomog)idHomModule(F,Q,w);
2876 else
2877 h = (tHomog)idHomIdeal(F,Q);
2878 }
2879 }
2880 currRing->pLexOrder=b;
2881 if (h==isHomog)
2882 {
2883 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2884 {
2885 strat->kModW = kModW = *w;
2886 if (vw == NULL)
2887 {
2888 strat->pOrigFDeg = currRing->pFDeg;
2889 strat->pOrigLDeg = currRing->pLDeg;
2891 toReset = TRUE;
2892 }
2893 }
2894 currRing->pLexOrder = TRUE;
2895 if (hilb==NULL) strat->LazyPass*=2;
2896 }
2897 strat->homog=h;
2898 #ifdef KDEBUG
2899 idTest(F);
2900 if(Q != NULL)
2901 idTest(Q);
2902 #endif
2903 #ifdef HAVE_PLURAL
2905 {
2906 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2907 strat->no_prod_crit = ! bIsSCA;
2908 if (w!=NULL)
2909 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2910 else
2911 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2912 }
2913 else
2914 #endif
2915 {
2917 {
2918 if (w!=NULL)
2919 r=mora(F,Q,*w,hilb,strat);
2920 else
2921 r=mora(F,Q,NULL,hilb,strat);
2922 }
2923 else
2924 {
2925 if (w!=NULL)
2926 r=sba(r,Q,*w,hilb,strat);
2927 else
2928 {
2929 r=sba(r,Q,NULL,hilb,strat);
2930 }
2931 }
2932 }
2933 #ifdef KDEBUG
2934 idTest(r);
2935 #endif
2936 if (toReset)
2937 {
2938 kModW = NULL;
2940 }
2941 currRing->pLexOrder = b;
2942 //Print("%d reductions canceled \n",strat->cel);
2943 sigdrop = strat->sigdrop;
2944 sbaEnterS = strat->sbaEnterS;
2945 blockred = strat->blockred;
2946 delete(strat);
2947 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2948 }
2949 // Go to std
2950 if(sigdrop || blockred > blockedreductions)
2951 {
2952 r = kStd2(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2953 }
2954 return r;
2955 }
2956}
2957
2958#ifdef HAVE_SHIFTBBA
2959ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, bigintmat *hilb,int syzComp,
2960 int newIdeal, intvec *vw, BOOLEAN rightGB)
2961{
2963 assume(idIsInV(F));
2965 {
2966 /* error: no local ord yet with shifts */
2967 WerrorS("No local ordering possible for shift algebra");
2968 return(NULL);
2969 }
2970 ideal r;
2971 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2972 BOOLEAN delete_w=(w==NULL);
2973 kStrategy strat=new skStrategy;
2974
2975 strat->rightGB = rightGB;
2976
2978 strat->syzComp = syzComp;
2979 if (TEST_OPT_SB_1)
2981 strat->newIdeal = newIdeal;
2983 strat->LazyPass=20;
2984 else
2985 strat->LazyPass=2;
2986 strat->LazyDegree = 1;
2987 strat->ak = 0;
2988 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2989 strat->kModW=kModW=NULL;
2990 strat->kHomW=kHomW=NULL;
2991 if (vw != NULL)
2992 {
2993 currRing->pLexOrder=FALSE;
2994 strat->kHomW=kHomW=vw;
2995 strat->pOrigFDeg = currRing->pFDeg;
2996 strat->pOrigLDeg = currRing->pLDeg;
2998 toReset = TRUE;
2999 }
3000 if (h==testHomog)
3001 {
3002 if (strat->ak == 0)
3003 {
3004 h = (tHomog)idHomIdeal(F,Q);
3005 w=NULL;
3006 }
3007 else if (!TEST_OPT_DEGBOUND)
3008 {
3009 if (w!=NULL)
3010 h = (tHomog)idHomModule(F,Q,w);
3011 else
3012 h = (tHomog)idHomIdeal(F,Q);
3013 }
3014 }
3015 currRing->pLexOrder=b;
3016 if (h==isHomog)
3017 {
3018 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3019 {
3020 strat->kModW = kModW = *w;
3021 if (vw == NULL)
3022 {
3023 strat->pOrigFDeg = currRing->pFDeg;
3024 strat->pOrigLDeg = currRing->pLDeg;
3026 toReset = TRUE;
3027 }
3028 }
3029 currRing->pLexOrder = TRUE;
3030 if (hilb==NULL) strat->LazyPass*=2;
3031 }
3032 strat->homog=h;
3033#ifdef KDEBUG
3034 idTest(F);
3035#endif
3036 /* global ordering */
3037 if (w!=NULL)
3038 r=bbaShift(F,Q,*w,hilb,strat);
3039 else
3040 r=bbaShift(F,Q,NULL,hilb,strat);
3041#ifdef KDEBUG
3042 idTest(r);
3043#endif
3044 if (toReset)
3045 {
3046 kModW = NULL;
3048 }
3049 currRing->pLexOrder = b;
3050//Print("%d reductions canceled \n",strat->cel);
3051 delete(strat);
3052 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3053 assume(idIsInV(r));
3054 return r;
3055}
3056#endif
3057
3058//##############################################################
3059//##############################################################
3060//##############################################################
3061//##############################################################
3062//##############################################################
3063
3064ideal kMin_std2(ideal F, ideal Q, tHomog h,intvec ** w, ideal &M, bigintmat *hilb,
3065 int syzComp, int reduced)
3066{
3067 if(idIs0(F))
3068 {
3069 M=idInit(1,F->rank);
3070 return idInit(1,F->rank);
3071 }
3073 {
3074 ideal sb;
3075 sb = kStd2(F, Q, h, w, hilb);
3076 idSkipZeroes(sb);
3077 if(IDELEMS(sb) <= IDELEMS(F))
3078 {
3079 M = idCopy(sb);
3080 idSkipZeroes(M);
3081 return(sb);
3082 }
3083 else
3084 {
3085 M = idCopy(F);
3086 idSkipZeroes(M);
3087 return(sb);
3088 }
3089 }
3090 ideal r=NULL;
3091 int Kstd1_OldDeg = Kstd1_deg,i;
3092 intvec* temp_w=NULL;
3093 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3094 BOOLEAN delete_w=(w==NULL);
3095 BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3096 kStrategy strat=new skStrategy;
3097
3099 strat->syzComp = syzComp;
3101 strat->LazyPass=20;
3102 else
3103 strat->LazyPass=2;
3104 strat->LazyDegree = 1;
3105 strat->minim=(reduced % 2)+1;
3106 strat->ak = 0;
3107 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
3108 if (delete_w)
3109 {
3110 temp_w=new intvec((strat->ak)+1);
3111 w = &temp_w;
3112 }
3113 if (h==testHomog)
3114 {
3115 if (strat->ak == 0)
3116 {
3117 h = (tHomog)idHomIdeal(F,Q);
3118 w=NULL;
3119 }
3120 else
3121 {
3122 h = (tHomog)idHomModule(F,Q,w);
3123 }
3124 }
3125 if (h==isHomog)
3126 {
3127 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3128 {
3129 kModW = *w;
3130 strat->kModW = *w;
3131 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3132 strat->pOrigFDeg = currRing->pFDeg;
3133 strat->pOrigLDeg = currRing->pLDeg;
3135
3136 toReset = TRUE;
3137 if (reduced>1)
3138 {
3139 Kstd1_OldDeg=Kstd1_deg;
3140 Kstd1_deg = -1;
3141 for (i=IDELEMS(F)-1;i>=0;i--)
3142 {
3143 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3144 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3145 }
3146 }
3147 }
3148 currRing->pLexOrder = TRUE;
3149 strat->LazyPass*=2;
3150 }
3151 strat->homog=h;
3152 ideal SB=NULL;
3154 {
3155 r=idMinBase(F,&SB); // SB and M via minbase
3156 strat->M=r;
3157 r=SB;
3158 }
3159 else
3160 {
3161 if (w!=NULL)
3162 r=bba(F,Q,*w,hilb,strat);
3163 else
3164 r=bba(F,Q,NULL,hilb,strat);
3165 }
3166#ifdef KDEBUG
3167 {
3168 int i;
3169 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3170 }
3171#endif
3172 idSkipZeroes(r);
3173 if (toReset)
3174 {
3176 kModW = NULL;
3177 }
3178 currRing->pLexOrder = b;
3179 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3180 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3181 {
3182 M=idInit(1,F->rank);
3183 M->m[0]=pOne();
3184 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3185 if (strat->M!=NULL) idDelete(&strat->M);
3186 }
3187 else if (strat->M==NULL)
3188 {
3189 M=idInit(1,F->rank);
3190 WarnS("no minimal generating set computed");
3191 }
3192 else
3193 {
3194 idSkipZeroes(strat->M);
3195 M=strat->M;
3196 strat->M=NULL;
3197 }
3198 delete(strat);
3199 if (reduced>2)
3200 {
3201 Kstd1_deg=Kstd1_OldDeg;
3202 if (!oldDegBound)
3204 }
3205 else
3206 {
3207 if (IDELEMS(M)>IDELEMS(r))
3208 {
3209 idDelete(&M);
3210 M=idCopy(r);
3211 }
3212 }
3213 return r;
3214}
3215
3216ideal kMin_std(ideal F, ideal Q, tHomog h,intvec ** w, ideal &M, intvec *hilb,
3217 int syzComp, int reduced)
3218{
3219 bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
3220 ideal res=kMin_std2(F,Q,h,w,M,hh,syzComp,reduced);
3221 if (hh!=NULL) delete hh;
3222 return res;
3223}
3224poly kNF(ideal F, ideal Q, poly p,int syzComp, int lazyReduce)
3225{
3226 if (p==NULL)
3227 return NULL;
3228
3229 poly pp = p;
3230
3231#ifdef HAVE_PLURAL
3232 if(rIsSCA(currRing))
3233 {
3234 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3235 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3236 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3237
3238 if(Q == currRing->qideal)
3240 }
3241#endif
3242 if(idIs0(Q)) Q=NULL;
3243
3244 if ((idIs0(F))&&(Q==NULL))
3245 {
3246#ifdef HAVE_PLURAL
3247 if(p != pp)
3248 return pp;
3249#endif
3250 return pCopy(p); /*F+Q=0*/
3251 }
3252
3253 kStrategy strat=new skStrategy;
3254 strat->syzComp = syzComp;
3256 poly res;
3257
3259 {
3260#ifdef HAVE_SHIFTBBA
3261 if (currRing->isLPring)
3262 {
3263 WerrorS("No local ordering possible for shift algebra");
3264 return(NULL);
3265 }
3266#endif
3267 res=kNF1(F,Q,pp,strat,lazyReduce);
3268 }
3269 else
3270 res=kNF2(F,Q,pp,strat,lazyReduce);
3271 delete(strat);
3272
3273#ifdef HAVE_PLURAL
3274 if(pp != p)
3275 p_Delete(&pp, currRing);
3276#endif
3277 return res;
3278}
3279
3280poly kNFBound(ideal F, ideal Q, poly p,int bound,int syzComp, int lazyReduce)
3281{
3282 if (p==NULL)
3283 return NULL;
3284
3285 poly pp = p;
3286
3287#ifdef HAVE_PLURAL
3288 if(rIsSCA(currRing))
3289 {
3290 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3291 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3292 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3293
3294 if(Q == currRing->qideal)
3296 }
3297#endif
3298
3299 if ((idIs0(F))&&(Q==NULL))
3300 {
3301#ifdef HAVE_PLURAL
3302 if(p != pp)
3303 return pp;
3304#endif
3305 return pCopy(p); /*F+Q=0*/
3306 }
3307
3308 kStrategy strat=new skStrategy;
3309 strat->syzComp = syzComp;
3311 poly res;
3312 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3313 delete(strat);
3314
3315#ifdef HAVE_PLURAL
3316 if(pp != p)
3317 p_Delete(&pp, currRing);
3318#endif
3319 return res;
3320}
3321
3322ideal kNF(ideal F, ideal Q, ideal p,int syzComp,int lazyReduce)
3323{
3324 ideal res;
3325 if (TEST_OPT_PROT)
3326 {
3327 Print("(S:%d)",IDELEMS(p));mflush();
3328 }
3329 if (idIs0(p))
3330 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3331
3332 ideal pp = p;
3333#ifdef HAVE_PLURAL
3334 if(rIsSCA(currRing))
3335 {
3336 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3337 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3338 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3339
3340 if(Q == currRing->qideal)
3342 }
3343#endif
3344
3345 if (idIs0(Q)) Q=NULL;
3346
3347 if ((idIs0(F))&&(Q==NULL))
3348 {
3349#ifdef HAVE_PLURAL
3350 if(p != pp)
3351 return pp;
3352#endif
3353 return idCopy(p); /*F+Q=0*/
3354 }
3355
3356 kStrategy strat=new skStrategy;
3357 strat->syzComp = syzComp;
3359 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3360 {
3361 strat->ak = si_max(strat->ak,(int)F->rank);
3362 }
3363
3365 {
3366#ifdef HAVE_SHIFTBBA
3367 if (currRing->isLPring)
3368 {
3369 WerrorS("No local ordering possible for shift algebra");
3370 return(NULL);
3371 }
3372#endif
3373 res=kNF1(F,Q,pp,strat,lazyReduce);
3374 }
3375 else
3376 res=kNF2(F,Q,pp,strat,lazyReduce);
3377 delete(strat);
3378
3379#ifdef HAVE_PLURAL
3380 if(pp != p)
3382#endif
3383
3384 return res;
3385}
3386
3387ideal kNFBound(ideal F, ideal Q, ideal p,int bound,int syzComp,int lazyReduce)
3388{
3389 ideal res;
3390 if (TEST_OPT_PROT)
3391 {
3392 Print("(S:%d)",IDELEMS(p));mflush();
3393 }
3394 if (idIs0(p))
3395 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3396
3397 ideal pp = p;
3398#ifdef HAVE_PLURAL
3399 if(rIsSCA(currRing))
3400 {
3401 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3402 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3403 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3404
3405 if(Q == currRing->qideal)
3407 }
3408#endif
3409
3410 if ((idIs0(F))&&(Q==NULL))
3411 {
3412#ifdef HAVE_PLURAL
3413 if(p != pp)
3414 return pp;
3415#endif
3416 return idCopy(p); /*F+Q=0*/
3417 }
3418
3419 kStrategy strat=new skStrategy;
3420 strat->syzComp = syzComp;
3422 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3423 {
3424 strat->ak = si_max(strat->ak,(int)F->rank);
3425 }
3426
3427 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3428 delete(strat);
3429
3430#ifdef HAVE_PLURAL
3431 if(pp != p)
3433#endif
3434
3435 return res;
3436}
3437
3438poly k_NF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing)
3439{
3440 const ring save = currRing;
3441 if( currRing != _currRing ) rChangeCurrRing(_currRing);
3442 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3443 if( currRing != save ) rChangeCurrRing(save);
3444 return ret;
3445}
3446
3447/*2
3448*interreduces F
3449*/
3450// old version
3451ideal kInterRedOld (ideal F,const ideal Q)
3452{
3453 int j;
3454 kStrategy strat = new skStrategy;
3455
3456 ideal tempF = F;
3457 ideal tempQ = Q;
3458
3459#ifdef HAVE_PLURAL
3460 if(rIsSCA(currRing))
3461 {
3462 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3463 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3464 tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3465
3466 // this should be done on the upper level!!! :
3467 // tempQ = SCAQuotient(currRing);
3468
3469 if(Q == currRing->qideal)
3470 tempQ = SCAQuotient(currRing);
3471 }
3472#endif
3473
3474// if (TEST_OPT_PROT)
3475// {
3476// writeTime("start InterRed:");
3477// mflush();
3478// }
3479 //strat->syzComp = 0;
3480 strat->kAllAxis = (currRing->ppNoether) != NULL;
3481 strat->kNoether=pCopy((currRing->ppNoether));
3482 strat->ak = 0;
3483 if (id_IsModule(tempF,currRing)) strat->ak = id_RankFreeModule(tempF,currRing);
3484 initBuchMoraCrit(strat);
3485 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3486 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3487 strat->enterS = enterSBba;
3488 strat->posInT = posInT17;
3489 strat->initEcart = initEcartNormal;
3490 strat->sl = -1;
3491 strat->tl = -1;
3492 strat->tmax = setmaxT;
3493 strat->T = initT();
3494 strat->R = initR();
3495 strat->sevT = initsevT();
3497 initS(tempF, tempQ, strat);
3498 if (TEST_OPT_REDSB)
3499 strat->noTailReduction=FALSE;
3500 updateS(TRUE,strat);
3502 completeReduce(strat);
3503 //else if (TEST_OPT_PROT) PrintLn();
3504 cleanT(strat);
3505 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3506 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3507 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3508 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3509 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3510 omfree(strat->sevT);
3511 omfree(strat->S_2_R);
3512 omfree(strat->R);
3513
3514 if (strat->fromQ)
3515 {
3516 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3517 {
3518 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3519 }
3520 omFree((ADDRESS)strat->fromQ);
3521 strat->fromQ=NULL;
3522 }
3523// if (TEST_OPT_PROT)
3524// {
3525// writeTime("end Interred:");
3526// mflush();
3527// }
3528 ideal shdl=strat->Shdl;
3529 idSkipZeroes(shdl);
3530 if (strat->fromQ)
3531 {
3532 omfree(strat->fromQ);
3533 strat->fromQ=NULL;
3534 ideal res=kInterRed(shdl,NULL);
3535 idDelete(&shdl);
3536 shdl=res;
3537 }
3538 delete(strat);
3539#ifdef HAVE_PLURAL
3540 if( tempF != F )
3541 id_Delete( &tempF, currRing);
3542#endif
3543 return shdl;
3544}
3545// new version
3546ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
3547{
3548 need_retry=0;
3549 int red_result = 1;
3550 int olddeg,reduc;
3551 BOOLEAN withT = FALSE;
3552 // BOOLEAN toReset=FALSE;
3553 kStrategy strat=new skStrategy;
3554 tHomog h;
3555
3557 strat->LazyPass=20;
3558 else
3559 strat->LazyPass=2;
3560 strat->LazyDegree = 1;
3561 strat->ak = id_RankFreeModule(F,currRing);
3562 strat->syzComp = strat->ak;
3563 strat->kModW=kModW=NULL;
3564 strat->kHomW=kHomW=NULL;
3565 if (strat->ak == 0)
3566 {
3567 h = (tHomog)idHomIdeal(F,Q);
3568 }
3569 else if (!TEST_OPT_DEGBOUND)
3570 {
3571 h = (tHomog)idHomIdeal(F,Q);
3572 }
3573 else
3574 h = isNotHomog;
3575 if (h==isHomog)
3576 {
3577 strat->LazyPass*=2;
3578 }
3579 strat->homog=h;
3580#ifdef KDEBUG
3581 idTest(F);
3582#endif
3583
3584 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3586 initBuchMoraPosRing(strat);
3587 else
3588 initBuchMoraPos(strat);
3589 initBba(strat);
3590 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3591 strat->posInL=posInL0; /* ord according pComp */
3592
3593 /*Shdl=*/initBuchMora(F, Q, strat);
3594 reduc = olddeg = 0;
3595
3596#ifndef NO_BUCKETS
3598 strat->use_buckets = 1;
3599#endif
3600
3601 // redtailBBa against T for inhomogeneous input
3602 if (!TEST_OPT_OLDSTD)
3603 withT = ! strat->homog;
3604
3605 // strat->posInT = posInT_pLength;
3606 kTest_TS(strat);
3607
3608#ifdef HAVE_TAIL_RING
3610#endif
3611
3612 /* compute------------------------------------------------------- */
3613 while (strat->Ll >= 0)
3614 {
3615 #ifdef KDEBUG
3616 if (TEST_OPT_DEBUG) messageSets(strat);
3617 #endif
3618 if (strat->Ll== 0) strat->interpt=TRUE;
3619 /* picks the last element from the lazyset L */
3620 strat->P = strat->L[strat->Ll];
3621 strat->Ll--;
3622
3623 if (strat->P.p1 == NULL)
3624 {
3625 // for input polys, prepare reduction
3626 strat->P.PrepareRed(strat->use_buckets);
3627 }
3628
3629 if (strat->P.p == NULL && strat->P.t_p == NULL)
3630 {
3631 red_result = 0;
3632 }
3633 else
3634 {
3635 if (TEST_OPT_PROT)
3636 message(strat->P.pFDeg(),
3637 &olddeg,&reduc,strat, red_result);
3638
3639 /* reduction of the element chosen from L */
3640 red_result = strat->red(&strat->P,strat);
3641 }
3642
3643 // reduction to non-zero new poly
3644 if (red_result == 1)
3645 {
3646 /* statistic */
3647 if (TEST_OPT_PROT) PrintS("s");
3648
3649 // get the polynomial (canonicalize bucket, make sure P.p is set)
3650 strat->P.GetP(strat->lmBin);
3651
3652 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3653
3654 // reduce the tail and normalize poly
3655 // in the ring case we cannot expect LC(f) = 1,
3656 // therefore we call pCleardenom instead of pNorm
3658 {
3659 strat->P.pCleardenom();
3660 }
3661 else
3662 {
3663 strat->P.pNorm();
3664 }
3665
3666#ifdef KDEBUG
3667 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3668#endif
3669
3670 // enter into S, L, and T
3671 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3672 {
3673 enterT(strat->P, strat);
3674 // posInS only depends on the leading term
3675 strat->enterS(strat->P, pos, strat, strat->tl);
3676
3677 if (pos<strat->sl)
3678 {
3679 need_retry++;
3680 // move all "larger" elements fromS to L
3681 // remove them from T
3682 int ii=pos+1;
3683 for(;ii<=strat->sl;ii++)
3684 {
3685 LObject h;
3686 h.Clear();
3687 h.tailRing=strat->tailRing;
3688 h.p=strat->S[ii]; strat->S[ii]=NULL;
3689 strat->initEcart(&h);
3690 h.sev=strat->sevS[ii];
3691 int jj=strat->tl;
3692 while (jj>=0)
3693 {
3694 if (strat->T[jj].p==h.p)
3695 {
3696 strat->T[jj].p=NULL;
3697 if (jj<strat->tl)
3698 {
3699 memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3700 (strat->tl-jj)*sizeof(strat->T[jj]));
3701 memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3702 (strat->tl-jj)*sizeof(strat->sevT[jj]));
3703 }
3704 strat->tl--;
3705 break;
3706 }
3707 jj--;
3708 }
3709 int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3710 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3711 #ifdef KDEBUG
3712 if (TEST_OPT_DEBUG)
3713 {
3714 Print("move S[%d] -> L[%d]: ",ii,pos);
3715 p_wrp(h.p,currRing, strat->tailRing);
3716 PrintLn();
3717 }
3718 #endif
3719 }
3720 if (strat->fromQ!=NULL)
3721 {
3722 for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3723 }
3724 strat->sl=pos;
3725 }
3726 }
3727 else
3728 {
3729 // clean P
3730 }
3731 kDeleteLcm(&strat->P);
3732 }
3733
3734#ifdef KDEBUG
3735 if (TEST_OPT_DEBUG)
3736 {
3737 messageSets(strat);
3738 }
3739 strat->P.Clear();
3740#endif
3741 //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3742 }
3743#ifdef KDEBUG
3744 //if (TEST_OPT_DEBUG) messageSets(strat);
3745#endif
3746 /* complete reduction of the standard basis--------- */
3747
3748 if((need_retry<=0) && (TEST_OPT_REDSB))
3749 {
3750 completeReduce(strat);
3751 if (strat->completeReduce_retry)
3752 {
3753 // completeReduce needed larger exponents, retry
3754 // hopefully: kStratChangeTailRing already provided a larger tailRing
3755 // (otherwise: it will fail again)
3757 completeReduce(strat);
3758 if (strat->completeReduce_retry)
3759 {
3760#ifdef HAVE_TAIL_RING
3761 if(currRing->bitmask>strat->tailRing->bitmask)
3762 {
3763 // retry without T
3765 cleanT(strat);strat->tailRing=currRing;
3766 int i;
3767 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3768 completeReduce(strat);
3769 }
3770 if (strat->completeReduce_retry)
3771#endif
3772 Werror("exponent bound is %ld",currRing->bitmask);
3773 }
3774 }
3775 }
3776 else if (TEST_OPT_PROT) PrintLn();
3777
3778
3779 /* release temp data-------------------------------- */
3780 exitBuchMora(strat);
3781// if (TEST_OPT_WEIGHTM)
3782// {
3783// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3784// if (ecartWeights)
3785// {
3786// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3787// ecartWeights=NULL;
3788// }
3789// }
3790 //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3791 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3792 ideal res=strat->Shdl;
3793 strat->Shdl=NULL;
3794 delete strat;
3795 return res;
3796}
3797ideal kInterRed (ideal F,const ideal Q)
3798{
3799#ifdef HAVE_PLURAL
3800 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3801#endif
3804 )
3805 return kInterRedOld(F,Q);
3806
3807 //return kInterRedOld(F,Q);
3808
3809 BITSET save1;
3810 SI_SAVE_OPT1(save1);
3811 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3813 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3814 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3815 //extern char * showOption() ;
3816 //Print("%s\n",showOption());
3817
3818 int need_retry;
3819 int counter=3;
3820 ideal res, res1;
3821 int elems=0;
3822 ideal null=NULL;
3823 if ((Q==NULL) || (!TEST_OPT_REDSB))
3824 {
3825 elems=idElem(F);
3826 res=kInterRedBba(F,Q,need_retry);
3827 }
3828 else
3829 {
3830 ideal FF=idSimpleAdd(F,Q);
3831 res=kInterRedBba(FF,NULL,need_retry);
3832 idDelete(&FF);
3833 null=idInit(1,1);
3834 if (need_retry)
3835 res1=kNF(null,Q,res,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
3836 else
3837 res1=kNF(null,Q,res);
3838 idDelete(&res);
3839 res=res1;
3840 need_retry=1;
3841 }
3842 if (idElem(res)<=1) need_retry=0;
3843 while (need_retry && (counter>0))
3844 {
3845 #ifdef KDEBUG
3846 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3847 #endif
3848 res1=kInterRedBba(res,Q,need_retry);
3849 int new_elems=idElem(res1);
3850 counter -= (new_elems >= elems);
3851 elems = new_elems;
3852 idDelete(&res);
3853 if (idElem(res1)<=1) need_retry=0;
3854 if ((Q!=NULL) && (TEST_OPT_REDSB))
3855 {
3856 if (need_retry)
3857 res=kNF(null,Q,res1,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
3858 else
3859 res=kNF(null,Q,res1);
3860 idDelete(&res1);
3861 }
3862 else
3863 res = res1;
3864 if (idElem(res)<=1) need_retry=0;
3865 }
3866 if (null!=NULL) idDelete(&null);
3867 SI_RESTORE_OPT1(save1);
3869 return res;
3870}
3871
3872// returns TRUE if mora should use buckets, false otherwise
3874{
3875#ifdef MORA_USE_BUCKETS
3877 return FALSE;
3878 if ((strat->red == redFirst)
3879 ||((strat->red == redEcart)&&(strat->kNoether!=NULL)))
3880 {
3881#ifdef NO_LDEG
3882 if (strat->syzComp==0)
3883 return TRUE;
3884#else
3885 if ((strat->homog || strat->honey) && (strat->syzComp==0))
3886 return TRUE;
3887#endif
3888 }
3889 else
3890 {
3891 assume(strat->red == redEcart || strat->red == redRiloc || strat->red == redRiloc_Z);
3892 if (strat->honey && (strat->syzComp==0))
3893 return TRUE;
3894 }
3895#endif
3896 return FALSE;
3897}
#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
void * ADDRESS
Definition auxiliary.h:120
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition cf_gcd.cc:676
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
int p
Definition cfModGcd.cc:4086
CanonicalForm b
Definition cfModGcd.cc:4111
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
intvec * kModW
Definition kutil.h:336
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
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:292
char noTailReduction
Definition kutil.h:377
int currIdx
Definition kutil.h:318
char posInLOldFlag
Definition kutil.h:381
pFDegProc pOrigFDeg_TailRing
Definition kutil.h:299
int Ll
Definition kutil.h:352
TSet T
Definition kutil.h:327
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
omBin lmBin
Definition kutil.h:345
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
BOOLEAN * NotUsedAxis
Definition kutil.h:333
LSet B
Definition kutil.h:329
int ak
Definition kutil.h:354
TObject ** R
Definition kutil.h:341
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:296
int lastAxis
Definition kutil.h:356
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
intvec * kHomW
Definition kutil.h:337
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
unsigned sbaOrder
Definition kutil.h:317
pFDegProc pOrigFDeg
Definition kutil.h:297
int blockredmax
Definition kutil.h:365
int tmax
Definition kutil.h:351
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition kutil.h:289
char LDegLast
Definition kutil.h:384
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:288
char kAllAxis
Definition kutil.h:375
intset fromQ
Definition kutil.h:322
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:287
char use_buckets
Definition kutil.h:382
char interpt
Definition kutil.h:370
int newIdeal
Definition kutil.h:357
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
char z2homog
Definition kutil.h:373
int LazyPass
Definition kutil.h:354
char no_prod_crit
Definition kutil.h:393
char overflow
Definition kutil.h:403
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.h:291
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
pLDegProc pOrigLDeg
Definition kutil.h:298
char update
Definition kutil.h:380
s_poly_proc_t s_poly
Definition kutil.h:301
pLDegProc pOrigLDeg_TailRing
Definition kutil.h:300
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition coeffs.h:809
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition coeffs.h:519
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition coeffs.h:682
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 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
#define Print
Definition emacs.cc:80
#define WarnS
Definition emacs.cc:78
return result
CanonicalForm res
Definition facAbsFact.cc:60
const CanonicalForm & w
Definition facAbsFact.cc:51
CanonicalForm H
Definition facAbsFact.cc:60
int j
Definition facHensel.cc:110
void WerrorS(const char *s)
Definition feFopen.cc:24
#define VAR
Definition globaldefs.h:5
long scMult0Int(ideal S, ideal Q)
Definition hdegree.cc:924
STATIC_VAR poly last
Definition hdegree.cc:1137
ideal idMinBase(ideal h1, ideal *SB)
Definition ideals.cc:51
#define idDelete(H)
delete an ideal
Definition ideals.h:29
#define idSimpleAdd(A, B)
Definition ideals.h:42
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition ideals.h:96
#define idTest(id)
Definition ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition ideals.h:91
ideal idCopy(ideal A)
Definition ideals.h:60
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
bigintmat * iv2biv(intvec *hilb, const coeffs cf)
Definition intvec.cc:851
STATIC_VAR Poly * h
Definition janet.cc:971
KINLINE TSet initT()
Definition kInline.h:84
KINLINE TObject ** initR()
Definition kInline.h:95
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition kInline.h:1255
KINLINE unsigned long * initsevT()
Definition kInline.h:100
int redLiftstd(LObject *h, kStrategy strat)
Definition kLiftstd.cc:167
static ideal nc_GB(const ideal F, const ideal Q, const intvec *w, const bigintmat *hilb, kStrategy strat, const ring r)
Definition nc.h:27
void khCheck(ideal Q, intvec *w, bigintmat *hilb, int &eledeg, int &count, kStrategy strat)
Definition khstd.cc:28
void khCheckLocInhom(ideal Q, intvec *w, bigintmat *hilb, int &count, kStrategy strat)
Definition khstd.cc:248
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
long kHomModDeg(poly p, const ring r)
Definition kstd1.cc:2417
void reorderT(kStrategy strat)
Definition kstd1.cc:1241
poly kNFBound(ideal F, ideal Q, poly p, int bound, int syzComp, int lazyReduce)
Definition kstd1.cc:3280
void initMora(ideal F, kStrategy strat)
Definition kstd1.cc:1811
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:794
void firstUpdate(kStrategy strat)
Definition kstd1.cc:1557
long kModDeg(poly p, const ring r)
Definition kstd1.cc:2407
poly k_NF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce, const ring _currRing)
NOTE: this is just a wrapper which sets currRing for the actual kNF call.
Definition kstd1.cc:3438
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:168
ideal kStd_internal(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
pure GB/SB computations
Definition kstd1.cc:2430
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1673
static int doRed(LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
Definition kstd1.cc:118
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition kstd1.cc:3216
void updateLHC(kStrategy strat)
Definition kstd1.cc:1465
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition kstd1.cc:2959
void missingAxis(int *last, kStrategy strat)
Definition kstd1.cc:1279
void reorderL(kStrategy strat)
Definition kstd1.cc:1222
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition kstd1.cc:1360
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition kstd1.cc:3546
ideal kMin_std2(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, bigintmat *hilb, int syzComp, int reduced)
Definition kstd1.cc:3064
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition kstd1.cc:3873
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd1.cc:2115
ideal kInterRed(ideal F, const ideal Q)
Definition kstd1.cc:3797
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition kstd1.cc:100
void initBba(kStrategy strat)
Definition kstd1.cc:1681
ideal mora(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd1.cc:1878
int redRiloc(LObject *h, kStrategy strat)
Definition kstd1.cc:385
ideal kStd2(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
generic interface to GB/SB computations, large hilbert vectors
Definition kstd1.cc:2602
void initSba(ideal F, kStrategy strat)
Definition kstd1.cc:1741
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition kstd1.cc:1080
ideal kSba(ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw)
Definition kstd1.cc:2663
void kDebugPrint(kStrategy strat)
Definition kutil.cc:11505
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1620
VAR intvec * kHomW
Definition kstd1.cc:2405
VAR intvec * kModW
Definition kstd1.cc:2405
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3451
void updateL(kStrategy strat)
Definition kstd1.cc:1393
VAR BITSET validOpts
Definition kstd1.cc:60
void updateT(kStrategy strat)
Definition kstd1.cc:1531
BOOLEAN hasPurePower(const poly p, int last, int *length, kStrategy strat)
Definition kstd1.cc:1312
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3224
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition kstd1.cc:976
VAR BITSET kOptions
Definition kstd1.cc:45
int redRiloc_Z(LObject *h, kStrategy strat)
Definition kstd1.cc:566
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
generic interface to GB/SB computations
Definition kstd1.cc:2654
#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_CANCELUNIT
Definition kstd1.h:24
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition kstd1.h:15
#define KSTD_NF_ECART
Definition kstd1.h:20
EXTERN_VAR int Kstd1_mu
Definition kstd1.h:70
poly kTryHC(ideal F, ideal Q)
Definition kstdhelper.cc:33
ideal kTryHilbstd(ideal F, ideal Q)
int redRing_Z(LObject *h, kStrategy strat)
Definition kstd2.cc:724
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 kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3944
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2114
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
ideal bbaShift(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:4594
int redSig(LObject *h, kStrategy strat)
Definition kstd2.cc:1373
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
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7467
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:6840
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5285
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9751
VAR int HCord
Definition kutil.cc:239
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6650
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9143
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6625
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8917
BOOLEAN kTest(kStrategy strat)
Definition kutil.cc:1011
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1074
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1946
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1276
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6566
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4932
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4494
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1322
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
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5618
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3452
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9242
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 HEckeTest(poly pp, kStrategy strat)
Definition kutil.cc:493
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 initEcartNormal(TObject *h)
Definition kutil.cc:1300
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4670
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8559
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10481
void cleanT(kStrategy strat)
Definition kutil.cc:557
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:796
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
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 messageSets(kStrategy strat)
Definition kutil.cc:7540
poly preIntegerCheck(const ideal Forig, const ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition kutil.cc:10540
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3211
void initEcartBBA(TObject *h)
Definition kutil.cc:1308
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1315
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7508
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
BOOLEAN newHEdge(kStrategy strat)
Definition kutil.cc:10409
void cancelunit(LObject *L, BOOLEAN inNF)
Definition kutil.cc:365
void initHilbCrit(ideal, ideal, bigintmat **hilb, kStrategy strat)
Definition kutil.cc:9417
LObject * LSet
Definition kutil.h:61
static void kDeleteLcm(LObject *P)
Definition kutil.h:870
#define setmaxT
Definition kutil.h:34
#define RED_CANONICALIZE
Definition kutil.h:37
class sTObject TObject
Definition kutil.h:58
class sLObject LObject
Definition kutil.h:59
static bool rIsSCA(const ring r)
Definition nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition sca.cc:1518
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition sca.cc:1463
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
number ndQuotRem(number a, number b, number *r, const coeffs R)
Definition numbers.cc:350
#define nEqual(n1, n2)
Definition numbers.h:20
#define omfree(addr)
#define omFreeSize(addr, size)
omError_t omTestMemory(int check_level)
Definition omDebug.c:94
#define omAlloc(size)
#define omFree(addr)
#define NULL
Definition omList.c:12
VAR BOOLEAN siCntrlc
Definition options.c:14
VAR unsigned si_opt_1
Definition options.c:5
#define TEST_OPT_WEIGHTM
Definition options.h:123
#define OPT_SUGARCRIT
Definition options.h:81
#define OPT_PROT
Definition options.h:76
#define OPT_INFREDTAIL
Definition options.h:95
#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 OPT_WEIGHTM
Definition options.h:98
#define TEST_OPT_FINDET
Definition options.h:113
#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 OPT_NOT_SUGAR
Definition options.h:79
#define TEST_OPT_OLDSTD
Definition options.h:125
#define OPT_REDTHROUGH
Definition options.h:83
#define OPT_REDSB
Definition options.h:77
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_REDSB
Definition options.h:106
#define OPT_NOTREGULARITY
Definition options.h:97
#define TEST_OPT_DEGBOUND
Definition options.h:115
#define TEST_OPT_SB_1
Definition options.h:121
#define TEST_OPT_RETURN_SB
Definition options.h:114
#define TEST_OPT_MULTBOUND
Definition options.h:116
#define TEST_OPT_PROT
Definition options.h:105
#define TEST_OPT_REDTHROUGH
Definition options.h:124
#define OPT_INTERRUPT
Definition options.h:80
#define OPT_DEGBOUND
Definition options.h:91
#define TEST_V_DEG_STOP
Definition options.h:140
#define TEST_OPT_FASTHC
Definition options.h:111
#define TEST_OPT_DEBUG
Definition options.h:110
#define OPT_FASTHC
Definition options.h:86
#define TEST_OPT_REDTAIL_SYZ
Definition options.h:119
#define OPT_OLDSTD
Definition options.h:87
#define TEST_OPT_STAIRCASEBOUND
Definition options.h:117
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
pShallowCopyDeleteProc pGetShallowCopyDeleteProc(ring, ring)
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition p_polys.cc:1227
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition p_polys.cc:3729
long pLDeg0c(poly p, int *l, const ring r)
Definition p_polys.cc:771
long pLDeg0(poly p, int *l, const ring r)
Definition p_polys.cc:740
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition p_polys.cc:3717
long p_WDegree(poly p, const ring r)
Definition p_polys.cc:715
static int pLength(poly a)
Definition p_polys.h:190
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:725
static long p_FDeg(const poly p, const ring r)
Definition p_polys.h:382
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:315
#define pp_Test(p, lmRing, tailRing)
Definition p_polys.h:163
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 void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:373
void rChangeCurrRing(ring r)
Definition polys.cc:16
VAR coeffs coeffs_BIGINT
Definition polys.cc:14
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 pAdd(p, q)
Definition polys.h:204
#define pTest(p)
Definition polys.h:415
#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 pSetm(p)
Definition polys.h:272
#define pIsConstant(p)
like above, except that Comp must be 0
Definition polys.h:239
#define pGetComp(p)
Component.
Definition polys.h:38
void pNorm(poly p)
Definition polys.h:363
#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 pMaxComp(p)
Definition polys.h:300
#define pSetComp(p, v)
Definition polys.h:39
#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
#define pSetmComp(p)
TODO:
Definition polys.h:274
#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 pCopy(p)
return a copy of the poly
Definition polys.h:186
#define pOne()
Definition polys.h:316
#define pWTotaldegree(p)
Definition polys.h:284
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
BOOLEAN rHasBlockOrder(const ring r)
Definition ring.cc:1923
BOOLEAN rOrd_is_Ds(const ring r)
Definition ring.cc:2075
BOOLEAN rOrd_is_ds(const ring r)
Definition ring.cc:2065
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515
static BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:769
static BOOLEAN rHasGlobalOrdering(const ring r)
Definition ring.h:768
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
long(* pLDegProc)(poly p, int *length, ring r)
Definition ring.h:38
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:417
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:512
static BOOLEAN rIsNCRing(const ring r)
Definition ring.h:427
static BOOLEAN rField_is_numeric(const ring r)
Definition ring.h:521
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:598
static BOOLEAN rHasMixedOrdering(const ring r)
Definition ring.h:770
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition ring.h:554
#define rField_is_Ring(R)
Definition ring.h:491
ideal SCAQuotient(const ring r)
Definition sca.h:10
static short scaLastAltVar(ring r)
Definition sca.h:25
static short scaFirstAltVar(ring r)
Definition sca.h:18
#define idIsInV(I)
Definition shiftop.h:49
ideal idInit(int idsize, int rank)
initialise an ideal / module
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
BOOLEAN id_IsModule(ideal A, const ring src)
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
BOOLEAN idIsMonomial(ideal h)
returns true if h is generated by monomials
#define IDELEMS(i)
static int idElem(const ideal F)
number of non-zero polys in F
#define M
Definition sirandom.c:25
#define Q
Definition sirandom.c:26
tHomog
Definition structs.h:31
@ isHomog
Definition structs.h:33
@ testHomog
Definition structs.h:34
@ isNotHomog
Definition structs.h:32
skStrategy * kStrategy
Definition structs.h:54
#define loop
Definition structs.h:71
long totaldegreeWecart(poly p, ring r)
Definition weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition weight.cc:247
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition weight.cc:182
EXTERN_VAR short * ecartWeights
Definition weight.h:12