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
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
118
120{
121 int ret;
122#if KDEBUG > 0
123 kTest_L(h);
124 kTest_T(with);
125#endif
126 // Hmmm ... why do we do this -- polys from T should already be normalized
128 with->pNorm();
129#ifdef KDEBUG
130 if (TEST_OPT_DEBUG)
131 {
132 PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
133 }
134#endif
135 if (intoT)
136 {
137 // need to do it exactly like this: otherwise
138 // we might get errors
139 LObject L= *h;
140 L.Copy();
141 h->GetP();
142 h->length=h->pLength=pLength(h->p);
143 ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, NULL, strat);
144 if (ret)
145 {
146 if (ret < 0) return ret;
147 if (h->tailRing != strat->tailRing)
148 h->ShallowCopyDelete(strat->tailRing,
150 strat->tailRing));
151 }
153 enterT_strong(*h,strat);
154 else
155 enterT(*h,strat);
156 *h = L;
157 }
158 else
159 ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, NULL, strat);
160#ifdef KDEBUG
161 if (TEST_OPT_DEBUG)
162 {
163 PrintS("to ");h->wrp();PrintLn();
164 }
165#endif
166 return ret;
167}
168
170{
171 int i,at,ei,li,ii;
172 int j = 0;
173 int pass = 0;
174 long d,reddeg;
175
176 d = h->GetpFDeg()+ h->ecart;
177 reddeg = strat->LazyDegree+d;
178 h->SetShortExpVector();
179 loop
180 {
181 j = kFindDivisibleByInT(strat, h);
182 if (j < 0)
183 {
184 if (strat->honey) h->SetLength(strat->length_pLength);
185 return 1;
186 }
187
188 ei = strat->T[j].ecart;
189 ii = j;
190
191 if (ei > h->ecart && ii < strat->tl)
192 {
193 unsigned long not_sev=~h->sev;
194 poly h_t= h->GetLmTailRing();
195 li = strat->T[j].length;
196 if (li<=0) li=strat->T[j].GetpLength();
197 // the polynomial to reduce with (up to the moment) is;
198 // pi with ecart ei and length li
199 // look for one with smaller ecart
200 i = j;
201 loop
202 {
203 /*- takes the first possible with respect to ecart -*/
204 i++;
205#if 1
206 if (i > strat->tl) break;
207 if (strat->T[i].length<=0) strat->T[i].GetpLength();
208 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
209 strat->T[i].length < li))
210 &&
211 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h_t, not_sev, strat->tailRing))
212#else
213 j = kFindDivisibleByInT(strat, h, i);
214 if (j < 0) break;
215 i = j;
216 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
217 strat->T[i].length < li))
218#endif
219 {
220 // the polynomial to reduce with is now
221 ii = i;
222 ei = strat->T[i].ecart;
223 if (ei <= h->ecart) break;
224 li = strat->T[i].length;
225 }
226 }
227 }
228
229 // end of search: have to reduce with pi
230 if (ei > h->ecart)
231 {
232 // It is not possible to reduce h with smaller ecart;
233 // if possible h goes to the lazy-set L,i.e
234 // if its position in L would be not the last one
235 strat->fromT = TRUE;
236 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
237 {
238 h->SetLmCurrRing();
239 if (strat->honey && strat->posInLDependsOnLength)
240 h->SetLength(strat->length_pLength);
241 assume(h->FDeg == h->pFDeg());
242 at = strat->posInL(strat->L,strat->Ll,h,strat);
243 if (at <= strat->Ll)
244 {
245 /*- h will not become the next element to reduce -*/
246 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
247#ifdef KDEBUG
248 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
249#endif
250 h->Clear();
251 strat->fromT = FALSE;
252 return -1;
253 }
254 }
255 }
256
257 // now we finally can reduce
258 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
259 strat->fromT=FALSE;
260
261 // are we done ???
262 if (h->IsNull())
263 {
265 kDeleteLcm(h);
266 h->Clear();
267 return 0;
268 }
269 if (TEST_OPT_IDLIFT)
270 {
271 if (h->p!=NULL)
272 {
273 if(p_GetComp(h->p,currRing)>strat->syzComp)
274 {
275 h->Delete();
276 return 0;
277 }
278 }
279 else if (h->t_p!=NULL)
280 {
281 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
282 {
283 h->Delete();
284 return 0;
285 }
286 }
287 }
288 #if 0
289 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
290 {
291 if (h->p!=NULL)
292 {
293 if(p_GetComp(h->p,currRing)>strat->syzComp)
294 {
295 return 1;
296 }
297 }
298 else if (h->t_p!=NULL)
299 {
300 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
301 {
302 return 1;
303 }
304 }
305 }
306 #endif
307
308 // done ? NO!
309 h->SetShortExpVector();
310 h->SetpFDeg();
311 if (strat->honey)
312 {
313 if (ei <= h->ecart)
314 h->ecart = d-h->GetpFDeg();
315 else
316 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
317 }
318 else
319 // this has the side effect of setting h->length
320 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
321#if 0
322 if (strat->syzComp!=0)
323 {
324 if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
325 {
326 assume(h->MinComp() > strat->syzComp);
327 if (strat->honey) h->SetLength();
328#ifdef KDEBUG
329 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
330#endif
331 return -2;
332 }
333 }
334#endif
335 /*- try to reduce the s-polynomial -*/
336 pass++;
337 d = h->GetpFDeg()+h->ecart;
338 /*
339 *test whether the polynomial should go to the lazyset L
340 *-if the degree jumps
341 *-if the number of pre-defined reductions jumps
342 */
343 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
344 && ((d >= reddeg) || (pass > strat->LazyPass)))
345 {
346 h->SetLmCurrRing();
347 if (strat->honey && strat->posInLDependsOnLength)
348 h->SetLength(strat->length_pLength);
349 assume(h->FDeg == h->pFDeg());
350 at = strat->posInL(strat->L,strat->Ll,h,strat);
351 if (at <= strat->Ll)
352 {
353 int dummy=strat->sl;
354 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
355 {
356 if (strat->honey && !strat->posInLDependsOnLength)
357 h->SetLength(strat->length_pLength);
358 return 1;
359 }
360 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
361#ifdef KDEBUG
362 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
363#endif
364 h->Clear();
365 return -1;
366 }
367 }
368 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
369 {
370 Print(".%ld",d);mflush();
371 reddeg = d+1;
372 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
373 {
374 strat->overflow=TRUE;
375 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
376 h->GetP();
377 at = strat->posInL(strat->L,strat->Ll,h,strat);
378 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
379 h->Clear();
380 return -1;
381 }
382 }
383 }
384}
385
387{
388 int i,at,ei,li,ii;
389 int j = 0;
390 int pass = 0;
391 long d,reddeg;
392
393 d = h->GetpFDeg()+ h->ecart;
394 reddeg = strat->LazyDegree+d;
395 h->SetShortExpVector();
396 loop
397 {
398 j = kFindDivisibleByInT(strat, h);
399 if (j < 0)
400 {
401 // over ZZ: cleanup coefficients by complete reduction with monomials
402 postReduceByMon(h, strat);
403 if(h->p == NULL)
404 {
405 kDeleteLcm(h);
406 h->Clear();
407 return 0;
408 }
409 if (strat->honey) h->SetLength(strat->length_pLength);
410 if(strat->tl >= 0)
411 h->i_r1 = strat->tl;
412 else
413 h->i_r1 = -1;
414 if (h->GetLmTailRing() == NULL)
415 {
416 kDeleteLcm(h);
417 h->Clear();
418 return 0;
419 }
420 return 1;
421 }
422
423 ei = strat->T[j].ecart;
424 ii = j;
425 if (ei > h->ecart && ii < strat->tl)
426 {
427 li = strat->T[j].length;
428 // the polynomial to reduce with (up to the moment) is;
429 // pi with ecart ei and length li
430 // look for one with smaller ecart
431 i = j;
432 loop
433 {
434 /*- takes the first possible with respect to ecart -*/
435 i++;
436#if 1
437 if (i > strat->tl) break;
438 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
439 strat->T[i].length < li))
440 &&
441 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
442 &&
443 n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
444#else
445 j = kFindDivisibleByInT(strat, h, i);
446 if (j < 0) break;
447 i = j;
448 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
449 strat->T[i].length < li))
450#endif
451 {
452 // the polynomial to reduce with is now
453 ii = i;
454 ei = strat->T[i].ecart;
455 if (ei <= h->ecart) break;
456 li = strat->T[i].length;
457 }
458 }
459 }
460
461 // end of search: have to reduce with pi
462 if (ei > h->ecart)
463 {
464 // It is not possible to reduce h with smaller ecart;
465 // if possible h goes to the lazy-set L,i.e
466 // if its position in L would be not the last one
467 strat->fromT = TRUE;
468 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
469 {
470 h->SetLmCurrRing();
471 if (strat->honey && strat->posInLDependsOnLength)
472 h->SetLength(strat->length_pLength);
473 assume(h->FDeg == h->pFDeg());
474 at = strat->posInL(strat->L,strat->Ll,h,strat);
475 if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
476 {
477 /*- h will not become the next element to reduce -*/
478 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
479 #ifdef KDEBUG
480 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
481 #endif
482 h->Clear();
483 strat->fromT = FALSE;
484 return -1;
485 }
486 }
487 doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
488 }
489 else
490 {
491 // now we finally can reduce
492 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
493 }
494 strat->fromT=FALSE;
495 // are we done ???
496 if (h->IsNull())
497 {
498 kDeleteLcm(h);
499 h->Clear();
500 return 0;
501 }
502
503 // NO!
504 h->SetShortExpVector();
505 h->SetpFDeg();
506 if (strat->honey)
507 {
508 if (ei <= h->ecart)
509 h->ecart = d-h->GetpFDeg();
510 else
511 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
512 }
513 else
514 // this has the side effect of setting h->length
515 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
516 /*- try to reduce the s-polynomial -*/
517 pass++;
518 d = h->GetpFDeg()+h->ecart;
519 /*
520 *test whether the polynomial should go to the lazyset L
521 *-if the degree jumps
522 *-if the number of pre-defined reductions jumps
523 */
524 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
525 && ((d >= reddeg) || (pass > strat->LazyPass)))
526 {
527 h->SetLmCurrRing();
528 if (strat->honey && strat->posInLDependsOnLength)
529 h->SetLength(strat->length_pLength);
530 assume(h->FDeg == h->pFDeg());
531 at = strat->posInL(strat->L,strat->Ll,h,strat);
532 if (at <= strat->Ll)
533 {
534 int dummy=strat->sl;
535 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
536 {
537 if (strat->honey && !strat->posInLDependsOnLength)
538 h->SetLength(strat->length_pLength);
539 return 1;
540 }
541 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
542#ifdef KDEBUG
543 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
544#endif
545 h->Clear();
546 return -1;
547 }
548 }
549 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
550 {
551 Print(".%ld",d);mflush();
552 reddeg = d+1;
553 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
554 {
555 strat->overflow=TRUE;
556 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
557 h->GetP();
558 at = strat->posInL(strat->L,strat->Ll,h,strat);
559 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
560 h->Clear();
561 return -1;
562 }
563 }
564 }
565}
566
568{
569 int i,at,ei,li,ii;
570 int j = 0;
571 int pass = 0;
572 long d,reddeg;
573 int docoeffred = 0;
574 poly T0p = strat->T[0].p;
575 int T0ecart = strat->T[0].ecart;
576
577
578 d = h->GetpFDeg()+ h->ecart;
579 reddeg = strat->LazyDegree+d;
580 h->SetShortExpVector();
581 if ((strat->tl>=0)
582 &&strat->T[0].GetpFDeg() == 0
583 && strat->T[0].length <= 2)
584 {
585 docoeffred = 1;
586 }
587 loop
588 {
589 /* cut down the lead coefficients, only possible if the degree of
590 * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
591 * we ask for the length of T[0] to be <= 2 */
592 if (docoeffred)
593 {
594 j = kTestDivisibleByT0_Z(strat, h);
595 if (j == 0 && n_DivBy(pGetCoeff(h->p), pGetCoeff(T0p), currRing->cf) == FALSE
596 && T0ecart <= h->ecart)
597 {
598 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
599 * => we try to cut down the lead coefficient at least */
600 /* first copy T[j] in order to multiply it with a coefficient later on */
602 TObject tj = strat->T[0];
603 tj.Copy();
604 /* compute division with remainder of lc(h) and lc(T[j]) */
606 &rest, currRing->cf);
607 /* set corresponding new lead coefficient already. we do not
608 * remove the lead term in ksReducePolyLC, but only apply
609 * a lead coefficient reduction */
610 tj.Mult_nn(mult);
611 ksReducePolyLC(h, &tj, NULL, &rest, strat);
612 tj.Delete();
613 tj.Clear();
614 if (n_IsZero(pGetCoeff(h->GetP()),currRing->cf))
615 {
616 h->LmDeleteAndIter();
617 }
618 }
619 }
620 j = kFindDivisibleByInT(strat, h);
621 if (j < 0)
622 {
623 // over ZZ: cleanup coefficients by complete reduction with monomials
624 postReduceByMon(h, strat);
625 if(h->p == NULL)
626 {
627 kDeleteLcm(h);
628 h->Clear();
629 return 0;
630 }
631 if (strat->honey) h->SetLength(strat->length_pLength);
632 if(strat->tl >= 0)
633 h->i_r1 = strat->tl;
634 else
635 h->i_r1 = -1;
636 if (h->GetLmTailRing() == NULL)
637 {
638 kDeleteLcm(h);
639 h->Clear();
640 return 0;
641 }
642 return 1;
643 }
644
645 ei = strat->T[j].ecart;
646 ii = j;
647#if 1
648 if (ei > h->ecart && ii < strat->tl)
649 {
650 li = strat->T[j].length;
651 // the polynomial to reduce with (up to the moment) is;
652 // pi with ecart ei and length li
653 // look for one with smaller ecart
654 i = j;
655 loop
656 {
657 /*- takes the first possible with respect to ecart -*/
658 i++;
659#if 1
660 if (i > strat->tl) break;
661 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
662 strat->T[i].length < li))
663 &&
664 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
665 &&
666 n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
667#else
668 j = kFindDivisibleByInT(strat, h, i);
669 if (j < 0) break;
670 i = j;
671 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
672 strat->T[i].length < li))
673#endif
674 {
675 // the polynomial to reduce with is now
676 ii = i;
677 ei = strat->T[i].ecart;
678 if (ei <= h->ecart) break;
679 li = strat->T[i].length;
680 }
681 }
682 }
683#endif
684
685 // end of search: have to reduce with pi
686 if (ei > h->ecart)
687 {
688 // It is not possible to reduce h with smaller ecart;
689 // if possible h goes to the lazy-set L,i.e
690 // if its position in L would be not the last one
691 strat->fromT = TRUE;
692 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
693 {
694 h->SetLmCurrRing();
695 if (strat->honey && strat->posInLDependsOnLength)
696 h->SetLength(strat->length_pLength);
697 assume(h->FDeg == h->pFDeg());
698 at = strat->posInL(strat->L,strat->Ll,h,strat);
699 if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
700 {
701 /*- h will not become the next element to reduce -*/
702 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
703#ifdef KDEBUG
704 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
705#endif
706 h->Clear();
707 strat->fromT = FALSE;
708 return -1;
709 }
710 }
711 doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
712 }
713 else
714 {
715 // now we finally can reduce
716 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
717 }
718 strat->fromT=FALSE;
719 // are we done ???
720 if (h->IsNull())
721 {
722 kDeleteLcm(h);
723 h->Clear();
724 return 0;
725 }
726
727 // NO!
728 h->SetShortExpVector();
729 h->SetpFDeg();
730 if (strat->honey)
731 {
732 if (ei <= h->ecart)
733 h->ecart = d-h->GetpFDeg();
734 else
735 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
736 }
737 else
738 // this has the side effect of setting h->length
739 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
740 /*- try to reduce the s-polynomial -*/
741 pass++;
742 d = h->GetpFDeg()+h->ecart;
743 /*
744 *test whether the polynomial should go to the lazyset L
745 *-if the degree jumps
746 *-if the number of pre-defined reductions jumps
747 */
748 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
749 && ((d >= reddeg) || (pass > strat->LazyPass)))
750 {
751 h->SetLmCurrRing();
752 if (strat->honey && strat->posInLDependsOnLength)
753 h->SetLength(strat->length_pLength);
754 assume(h->FDeg == h->pFDeg());
755 at = strat->posInL(strat->L,strat->Ll,h,strat);
756 if (at <= strat->Ll)
757 {
758 int dummy=strat->sl;
759 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
760 {
761 if (strat->honey && !strat->posInLDependsOnLength)
762 h->SetLength(strat->length_pLength);
763 return 1;
764 }
765 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
766#ifdef KDEBUG
767 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
768#endif
769 h->Clear();
770 return -1;
771 }
772 }
773 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
774 {
775 Print(".%ld",d);mflush();
776 reddeg = d+1;
777 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
778 {
779 strat->overflow=TRUE;
780 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
781 h->GetP();
782 at = strat->posInL(strat->L,strat->Ll,h,strat);
783 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
784 h->Clear();
785 return -1;
786 }
787 }
788 }
789}
790
791/*2
792*reduces h with elements from T choosing the first possible
793* element in t with respect to the given pDivisibleBy
794*/
796{
797 if (strat->tl<0) return 1;
798 if (h->IsNull()) return 0;
799
800 int at;
801 long reddeg,d;
802 int pass = 0;
803 int cnt = RED_CANONICALIZE;
804 int j = 0;
805
806 if (! strat->homog)
807 {
808 d = h->GetpFDeg() + 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;
984 if ((flag & 2) == 0) cancelunit(&H,TRUE);
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]) */
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 LObject p;
1226
1227 for (i=1; i<=strat->Ll; i++)
1228 {
1229 at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
1230 if (at != i)
1231 {
1232 p = strat->L[i];
1233 for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
1234 strat->L[at] = p;
1235 }
1236 }
1237}
1238
1239/*2
1240*reorders T with respect to length
1241*/
1243{
1244 int i,j,at;
1245 TObject p;
1246 unsigned long sev;
1247
1248
1249 for (i=1; i<=strat->tl; i++)
1250 {
1251 if (strat->T[i-1].length > strat->T[i].length)
1252 {
1253 p = strat->T[i];
1254 sev = strat->sevT[i];
1255 at = i-1;
1256 loop
1257 {
1258 at--;
1259 if (at < 0) break;
1260 if (strat->T[i].length > strat->T[at].length) break;
1261 }
1262 for (j = i-1; j>at; j--)
1263 {
1264 strat->T[j+1]=strat->T[j];
1265 strat->sevT[j+1]=strat->sevT[j];
1266 strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
1267 }
1268 strat->T[at+1]=p;
1269 strat->sevT[at+1] = sev;
1270 strat->R[p.i_r] = &(strat->T[at+1]);
1271 }
1272 }
1273}
1274
1275/*2
1276*looks whether exactly (currRing->N)-1 axis are used
1277*returns last != 0 in this case
1278*last is the (first) unused axis
1279*/
1280void missingAxis (int* last,kStrategy strat)
1281{
1282 int i = 0;
1283 int k = 0;
1284
1285 *last = 0;
1287 {
1288 loop
1289 {
1290 i++;
1291 if (i > (currRing->N)) break;
1292 if (strat->NotUsedAxis[i])
1293 {
1294 *last = i;
1295 k++;
1296 }
1297 if (k>1)
1298 {
1299 *last = 0;
1300 break;
1301 }
1302 }
1303 }
1304}
1305
1306/*2
1307*last is the only non used axis, it looks
1308*for a monomial in p being a pure power of this
1309*variable and returns TRUE in this case
1310*(*length) gives the length between the pure power and the leading term
1311*(should be minimal)
1312*/
1313BOOLEAN hasPurePower (const poly p,int last, int *length,kStrategy strat)
1314{
1315 poly h;
1316 int i;
1317
1318 if (pNext(p) == strat->tail)
1319 return FALSE;
1320 pp_Test(p, currRing, strat->tailRing);
1321 if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
1322 {
1324 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
1325 if (i == last)
1326 {
1327 *length = 0;
1328 return TRUE;
1329 }
1330 *length = 1;
1331 h = pNext(p);
1332 while (h != NULL)
1333 {
1334 i = p_IsPurePower(h, strat->tailRing);
1335 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
1336 if (i==last) return TRUE;
1337 (*length)++;
1338 pIter(h);
1339 }
1340 }
1341 return FALSE;
1342}
1343
1345{
1346 if (L->bucket != NULL)
1347 {
1348 poly p = L->GetP();
1349 return hasPurePower(p, last, length, strat);
1350 }
1351 else
1352 {
1353 return hasPurePower(L->p, last, length, strat);
1354 }
1355}
1356
1357/*2
1358* looks up the position of polynomial p in L
1359* in the case of looking for the pure powers
1360*/
1361int posInL10 (const LSet set,const int length, LObject* p,const kStrategy strat)
1362{
1363 int j,dp,dL;
1364
1365 if (length<0) return 0;
1366 if (hasPurePower(p,strat->lastAxis,&dp,strat))
1367 {
1368 int op= p->GetpFDeg() +p->ecart;
1369 for (j=length; j>=0; j--)
1370 {
1371 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1372 return j+1;
1373 if (dp < dL)
1374 return j+1;
1375 if ((dp == dL)
1376 && (set[j].GetpFDeg()+set[j].ecart >= op))
1377 return j+1;
1378 }
1379 }
1380 j=length;
1381 loop
1382 {
1383 if (j<0) break;
1384 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1385 j--;
1386 }
1387 return strat->posInLOld(set,j,p,strat);
1388}
1389
1390
1391/*2
1392* computes the s-polynomials L[ ].p in L
1393*/
1395{
1396 LObject p;
1397 int dL;
1398 int j=strat->Ll;
1399 loop
1400 {
1401 if (j<0) break;
1402 if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1403 {
1404 p=strat->L[strat->Ll];
1405 strat->L[strat->Ll]=strat->L[j];
1406 strat->L[j]=p;
1407 break;
1408 }
1409 j--;
1410 }
1411 if (j<0)
1412 {
1413 j=strat->Ll;
1414 loop
1415 {
1416 if (j<0) break;
1417 if (pNext(strat->L[j].p) == strat->tail)
1418 {
1420 pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1421 else
1422 pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1423 strat->L[j].p = NULL;
1424 poly m1 = NULL, m2 = NULL;
1425 // check that spoly creation is ok
1426 while (strat->tailRing != currRing &&
1427 !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1428 {
1429 assume(m1 == NULL && m2 == NULL);
1430 // if not, change to a ring where exponents are at least
1431 // large enough
1432 kStratChangeTailRing(strat);
1433 }
1434 /* create the real one */
1435 ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1436 strat->tailRing, m1, m2, strat->R);
1437
1438 strat->L[j].SetLmCurrRing();
1439 if (!strat->honey)
1440 strat->initEcart(&strat->L[j]);
1441 else
1442 strat->L[j].SetLength(strat->length_pLength);
1443
1444 BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1445
1446 if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
1447
1448 if (pp)
1449 {
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
1595 {
1596 strat->red = redFirst;
1597 strat->use_buckets = kMoraUseBucket(strat);
1598 }
1599 updateT(strat);
1600
1602 {
1603 strat->posInT = posInT2;
1604 reorderT(strat);
1605 }
1606 }
1607 kTest_TS(strat);
1608}
1609
1610/*2
1611*-puts p to the standardbasis s at position at
1612*-reduces the tail of p if TEST_OPT_REDTAIL
1613*-tries to cancel a unit
1614*-HEckeTest
1615* if TRUE
1616* - decides about reduction-strategies
1617* - computes noether
1618* - stops computation if TEST_OPT_FINDET
1619* - cuts the tails of the polynomials
1620* in s,t and the elements in L above noether
1621* and cancels units if possible
1622* - reorders s,L
1623*/
1624void enterSMora (LObject &p,int atS,kStrategy strat, int atR = -1)
1625{
1626 enterSBba(p, atS, strat, atR);
1627 #ifdef KDEBUG
1628 if (TEST_OPT_DEBUG)
1629 {
1630 Print("new s%d:",atS);
1631 p_wrp(p.p,currRing,strat->tailRing);
1632 PrintLn();
1633 }
1634 #endif
1635 HEckeTest(p.p,strat);
1636 if (strat->kAllAxis)
1637 {
1638 if (newHEdge(strat))
1639 {
1640 firstUpdate(strat);
1641 if (TEST_OPT_FINDET)
1642 return;
1643
1644 /*- cuts elements in L above noether and reorders L -*/
1645 updateLHC(strat);
1646 /*- reorders L with respect to posInL -*/
1647 reorderL(strat);
1648 }
1649 }
1650 else if ((strat->kNoether==NULL)
1651 && (TEST_OPT_FASTHC))
1652 {
1653 if (strat->posInLOldFlag)
1654 {
1655 missingAxis(&strat->lastAxis,strat);
1656 if (strat->lastAxis)
1657 {
1658 strat->posInLOld = strat->posInL;
1659 strat->posInLOldFlag = FALSE;
1660 strat->posInL = posInL10;
1661 strat->posInLDependsOnLength = TRUE;
1662 updateL(strat);
1663 reorderL(strat);
1664 }
1665 }
1666 else if (strat->lastAxis)
1667 updateL(strat);
1668 }
1669}
1670
1671/*2
1672*-puts p to the standardbasis s at position at
1673*-HEckeTest
1674* if TRUE
1675* - computes noether
1676*/
1677void enterSMoraNF (LObject &p, int atS,kStrategy strat, int atR = -1)
1678{
1679 enterSBba(p, atS, strat, atR);
1680 if ((!strat->kAllAxis) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1681 if (strat->kAllAxis)
1682 newHEdge(strat);
1683}
1684
1686{
1687 /* setting global variables ------------------- */
1688 strat->enterS = enterSBba;
1689 strat->red = redHoney;
1690 if (strat->honey)
1691 strat->red = redHoney;
1692 else if (currRing->pLexOrder && !strat->homog)
1693 strat->red = redLazy;
1694 else
1695 {
1696 strat->LazyPass *=4;
1697 strat->red = redHomog;
1698 }
1700 {
1701 if (rField_is_Z(currRing))
1702 strat->red = redRing_Z;
1703 else
1704 strat->red = redRing;
1705 }
1706 if (TEST_OPT_IDLIFT
1707 && (!rIsNCRing(currRing))
1708 && (!rField_is_Ring(currRing)))
1709 strat->red=redLiftstd;
1710 if (currRing->pLexOrder && strat->honey)
1711 strat->initEcart = initEcartNormal;
1712 else
1713 strat->initEcart = initEcartBBA;
1714 if (strat->honey)
1716 else
1718// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1719// {
1720// //interred machen Aenderung
1721// strat->pOrigFDeg=pFDeg;
1722// strat->pOrigLDeg=pLDeg;
1723// //h=ggetid("ecart");
1724// //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1725// //{
1726// // ecartWeights=iv2array(IDINTVEC(h));
1727// //}
1728// //else
1729// {
1730// ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1731// /*uses automatic computation of the ecartWeights to set them*/
1732// kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1733// }
1734// pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1735// if (TEST_OPT_PROT)
1736// {
1737// for(i=1; i<=(currRing->N); i++)
1738// Print(" %d",ecartWeights[i]);
1739// PrintLn();
1740// mflush();
1741// }
1742// }
1743}
1744
1746{
1747 int i;
1748 //idhdl h;
1749 /* setting global variables ------------------- */
1750 strat->enterS = enterSSba;
1751 strat->red2 = redHoney;
1752 if (strat->honey)
1753 strat->red2 = redHoney;
1754 else if (currRing->pLexOrder && !strat->homog)
1755 strat->red2 = redLazy;
1756 else
1757 {
1758 strat->LazyPass *=4;
1759 strat->red2 = redHomog;
1760 }
1762 {
1764 {strat->red2 = redRiloc;}
1765 else
1766 {strat->red2 = redRing;}
1767 }
1768 if (currRing->pLexOrder && strat->honey)
1769 strat->initEcart = initEcartNormal;
1770 else
1771 strat->initEcart = initEcartBBA;
1772 if (strat->honey)
1774 else
1776 //strat->kIdeal = NULL;
1777 //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1778 //else strat->kIdeal->rtyp=MODUL_CMD;
1779 //strat->kIdeal->data=(void *)strat->Shdl;
1780 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1781 {
1782 //interred machen Aenderung
1783 strat->pOrigFDeg = currRing->pFDeg;
1784 strat->pOrigLDeg = currRing->pLDeg;
1785 //h=ggetid("ecart");
1786 //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1787 //{
1788 // ecartWeights=iv2array(IDINTVEC(h));
1789 //}
1790 //else
1791 {
1792 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1793 /*uses automatic computation of the ecartWeights to set them*/
1795 }
1797 if (TEST_OPT_PROT)
1798 {
1799 for(i=1; i<=(currRing->N); i++)
1800 Print(" %d",ecartWeights[i]);
1801 PrintLn();
1802 mflush();
1803 }
1804 }
1805 // for sig-safe reductions in signature-based
1806 // standard basis computations
1808 strat->red = redSigRing;
1809 else
1810 strat->red = redSig;
1811 //strat->sbaOrder = 1;
1812 strat->currIdx = 1;
1813}
1814
1816{
1817 int i,j;
1818
1819 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1820 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1821 strat->enterS = enterSMora;
1822 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1823 strat->posInLOld = strat->posInL;
1824 strat->posInLOldFlag = TRUE;
1825 strat->initEcart = initEcartNormal;
1826 strat->kAllAxis = (currRing->ppNoether) != NULL;
1827 if ( strat->kAllAxis )
1828 {
1829 strat->kNoether = pCopy((currRing->ppNoether));
1830 strat->red = redFirst; /*take the first possible in T*/
1831 if (TEST_OPT_PROT)
1832 {
1833 Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
1834 mflush();
1835 }
1836 }
1837 else if (strat->homog)
1838 strat->red = redFirst; /*take the first possible in T*/
1839 else
1840 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1841 if (strat->kAllAxis)
1842 {
1843 HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
1844 }
1845 else
1846 {
1847 HCord = 32000;/*- very large -*/
1848 }
1849
1851 {
1852 if (rField_is_Z(currRing))
1853 strat->red = redRiloc_Z;
1854 else
1855 strat->red = redRiloc;
1856 }
1857
1858 /*reads the ecartWeights used for Graebes method from the
1859 *intvec ecart and set ecartWeights
1860 */
1861 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1862 {
1863 //interred machen Aenderung
1864 strat->pOrigFDeg=currRing->pFDeg;
1865 strat->pOrigLDeg=currRing->pLDeg;
1866 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1867 /*uses automatic computation of the ecartWeights to set them*/
1869
1871 if (TEST_OPT_PROT)
1872 {
1873 for(i=1; i<=(currRing->N); i++)
1874 Print(" %d",ecartWeights[i]);
1875 PrintLn();
1876 mflush();
1877 }
1878 }
1879 kOptimizeLDeg(currRing->pLDeg, strat);
1880}
1881
1882void kDebugPrint(kStrategy strat);
1883
1885{
1886 int olddeg = 0;
1887 int reduc = 0;
1888 int red_result = 1;
1889 int hilbeledeg=1,hilbcount=0;
1890 BITSET save1;
1893 {
1894 si_opt_1 &= ~Sy_bit(OPT_REDSB);
1895 si_opt_1 &= ~Sy_bit(OPT_REDTAIL);
1896 }
1897
1898 strat->update = TRUE;
1899 /*- setting global variables ------------------- -*/
1900 initBuchMoraCrit(strat);
1901 initHilbCrit(F,Q,&hilb,strat);
1902 initMora(F,strat);
1904 initBuchMoraPosRing(strat);
1905 else
1906 initBuchMoraPos(strat);
1907 /*Shdl=*/initBuchMora(F,Q,strat);
1908 if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1909 /*updateS in initBuchMora has Hecketest
1910 * and could have put strat->kHEdgdeFound FALSE*/
1911 if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1912 {
1913 strat->posInLOld = strat->posInL;
1914 strat->posInLOldFlag = FALSE;
1915 strat->posInL = posInL10;
1916 updateL(strat);
1917 reorderL(strat);
1918 }
1919 kTest_TS(strat);
1920 strat->use_buckets = kMoraUseBucket(strat);
1921
1922#ifdef HAVE_TAIL_RING
1923 if (strat->homog && strat->red == redFirst)
1924 if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1926#endif
1927
1928 if (BVERBOSE(23))
1929 {
1930 kDebugPrint(strat);
1931 }
1932//deleteInL(strat->L,&strat->Ll,1,strat);
1933//deleteInL(strat->L,&strat->Ll,0,strat);
1934
1935 /*- compute-------------------------------------------*/
1936 while (strat->Ll >= 0)
1937 {
1938 #ifdef KDEBUG
1939 if (TEST_OPT_DEBUG) messageSets(strat);
1940 #endif
1941 if (siCntrlc)
1942 {
1943 while (strat->Ll >= 0)
1944 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1945 strat->noClearS=TRUE;
1946 }
1948 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1949 {
1950 /*
1951 * stops computation if
1952 * - 24 (degBound)
1953 * && upper degree is bigger than Kstd1_deg
1954 */
1955 while ((strat->Ll >= 0)
1956 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1957 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1958 )
1959 {
1960 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1961 //if (TEST_OPT_PROT)
1962 //{
1963 // PrintS("D"); mflush();
1964 //}
1965 }
1966 if (strat->Ll<0) break;
1967 else strat->noClearS=TRUE;
1968 }
1969 strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1970 if (strat->Ll==0) strat->interpt=TRUE;
1971 strat->Ll--;
1972 // create the real Spoly
1973 if (pNext(strat->P.p) == strat->tail)
1974 {
1975 /*- deletes the short spoly and computes -*/
1977 pLmDelete(strat->P.p);
1978 else
1979 pLmFree(strat->P.p);
1980 strat->P.p = NULL;
1981 poly m1 = NULL, m2 = NULL;
1982 // check that spoly creation is ok
1983 while (strat->tailRing != currRing &&
1984 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1985 {
1986 assume(m1 == NULL && m2 == NULL);
1987 // if not, change to a ring where exponents are large enough
1988 kStratChangeTailRing(strat);
1989 }
1990 /* create the real one */
1991 ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1992 strat->tailRing, m1, m2, strat->R);
1993 if (!strat->use_buckets)
1994 strat->P.SetLength(strat->length_pLength);
1995 }
1996 else if (strat->P.p1 == NULL)
1997 {
1998 // for input polys, prepare reduction (buckets !)
1999 strat->P.SetLength(strat->length_pLength);
2000 strat->P.PrepareRed(strat->use_buckets);
2001 }
2002
2003 // the s-poly
2004 if (!strat->P.IsNull())
2005 {
2006 // might be NULL from noether !!!
2007 if (TEST_OPT_PROT)
2008 message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
2009 // reduce
2010 red_result = strat->red(&strat->P,strat);
2011 }
2012
2013 // the reduced s-poly
2014 if (! strat->P.IsNull())
2015 {
2016 strat->P.GetP();
2017 // statistics
2018 if (TEST_OPT_PROT) PrintS("s");
2019 // normalization
2021 strat->P.pCleardenom();
2022 else
2023 strat->P.pNorm();
2024 // tailreduction
2025 strat->P.p = redtail(&(strat->P),strat->sl,strat);
2026 if (strat->P.p==NULL)
2027 {
2028 WerrorS("exponent overflow - wrong ordering");
2029 return(idInit(1,1));
2030 }
2031 // set ecart -- might have changed because of tail reductions
2032 if ((!strat->noTailReduction) && (!strat->honey))
2033 strat->initEcart(&strat->P);
2034 // cancel unit
2035 cancelunit(&strat->P);
2036 // for char 0, clear denominators
2037 if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2039 strat->P.pCleardenom();
2040
2041 strat->P.SetShortExpVector();
2042 enterT(strat->P,strat);
2043 // build new pairs
2045 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2046 else
2047 enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2048 // put in S
2049 strat->enterS(strat->P,
2050 posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2051 strat, strat->tl);
2052 // apply hilbert criterion
2053 if (hilb!=NULL)
2054 {
2055 if (strat->homog==isHomog)
2057 else
2059 }
2060
2061 // clear strat->P
2062 kDeleteLcm(&strat->P);
2063
2064#ifdef KDEBUG
2065 // make sure kTest_TS does not complain about strat->P
2066 strat->P.Clear();
2067#endif
2068 }
2069 if (strat->kAllAxis)
2070 {
2071 if ((TEST_OPT_FINDET)
2072 || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL) < Kstd1_mu)))
2073 {
2074 // obachman: is this still used ???
2075 /*
2076 * stops computation if strat->kAllAxis and
2077 * - 27 (finiteDeterminacyTest)
2078 * or
2079 * - 23
2080 * (multBound)
2081 * && multiplicity of the ideal is smaller then a predefined number mu
2082 */
2083 while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2084 }
2085 }
2086 kTest_TS(strat);
2087 }
2088 /*- complete reduction of the standard basis------------------------ -*/
2089 if (TEST_OPT_REDSB) completeReduce(strat);
2090 else if (TEST_OPT_PROT) PrintLn();
2091 /*- release temp data------------------------------- -*/
2092 exitBuchMora(strat);
2093 /*- polynomials used for HECKE: HC, noether -*/
2094 if (TEST_OPT_FINDET)
2095 {
2096 if (strat->kNoether!=NULL)
2097 Kstd1_mu=currRing->pFDeg(strat->kNoether,currRing);
2098 else
2099 Kstd1_mu=-1;
2100 }
2101 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2102 if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2103 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2105// if (TEST_OPT_WEIGHTM)
2106// {
2107// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2108// if (ecartWeights)
2109// {
2110// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2111// ecartWeights=NULL;
2112// }
2113// }
2114 if(nCoeff_is_Z(currRing->cf))
2115 finalReduceByMon(strat);
2116 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2118 idTest(strat->Shdl);
2119 return (strat->Shdl);
2120}
2121
2122poly kNF1 (ideal F,ideal Q,poly q, kStrategy strat, int lazyReduce)
2123{
2124 assume(q!=NULL);
2125 assume(!(idIs0(F)&&(Q==NULL)));
2126
2127// lazy_reduce flags: can be combined by |
2128//#define KSTD_NF_LAZY 1
2129 // do only a reduction of the leading term
2130//#define KSTD_NF_ECART 2
2131 // only local: reduce even with bad ecart
2132 poly p;
2133 int i;
2134 int j;
2135 int o;
2136 LObject h;
2137 BITSET save1;
2139
2140 //if ((idIs0(F))&&(Q==NULL))
2141 // return pCopy(q); /*F=0*/
2142 //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
2143 /*- creating temp data structures------------------- -*/
2144 strat->kAllAxis = (currRing->ppNoether) != NULL;
2145 strat->kNoether = pCopy((currRing->ppNoether));
2148 si_opt_1&=~Sy_bit(OPT_INTSTRATEGY);
2150 && (! TEST_V_DEG_STOP)
2151 && (0<Kstd1_deg)
2152 && ((strat->kNoether==NULL)
2154 {
2155 pLmDelete(&strat->kNoether);
2156 strat->kNoether=pOne();
2157 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2158 pSetm(strat->kNoether);
2159 // strat->kAllAxis=TRUE;
2160 }
2161 initBuchMoraCrit(strat);
2163 initBuchMoraPosRing(strat);
2164 else
2165 initBuchMoraPos(strat);
2166 initMora(F,strat);
2167 strat->enterS = enterSMoraNF;
2168 /*- set T -*/
2169 strat->tl = -1;
2170 strat->tmax = setmaxT;
2171 strat->T = initT();
2172 strat->R = initR();
2173 strat->sevT = initsevT();
2174 /*- set S -*/
2175 strat->sl = -1;
2176 /*- init local data struct.-------------------------- -*/
2177 /*Shdl=*/initS(F,Q,strat);
2178 if ((strat->ak!=0)
2179 && (strat->kAllAxis)) /*never true for ring-cf*/
2180 {
2181 if (strat->ak!=1)
2182 {
2183 pSetComp(strat->kNoether,1);
2184 pSetmComp(strat->kNoether);
2185 poly p=pHead(strat->kNoether);
2186 pSetComp(p,strat->ak);
2187 pSetmComp(p);
2188 p=pAdd(strat->kNoether,p);
2189 strat->kNoether=pNext(p);
2191 }
2192 }
2193 if (((lazyReduce & KSTD_NF_LAZY)==0)
2194 && (!rField_is_Ring(currRing)))
2195 {
2196 for (i=strat->sl; i>=0; i--)
2197 pNorm(strat->S[i]);
2198 }
2199 /*- puts the elements of S also to T -*/
2200 for (i=0; i<=strat->sl; i++)
2201 {
2202 h.p = strat->S[i];
2203 h.ecart = strat->ecartS[i];
2204 if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
2205 else assume(strat->sevS[i] == pGetShortExpVector(h.p));
2206 h.length = pLength(h.p);
2207 h.sev = strat->sevS[i];
2208 h.SetpFDeg();
2209 enterT(h,strat);
2210 }
2211#ifdef KDEBUG
2212// kDebugPrint(strat);
2213#endif
2214 /*- compute------------------------------------------- -*/
2215 p = pCopy(q);
2216 deleteHC(&p,&o,&j,strat);
2217 kTest(strat);
2218 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2219 if (BVERBOSE(23)) kDebugPrint(strat);
2221 {
2222 if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2223 }
2224 else
2225 {
2226 if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2227 }
2228 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2229 {
2230 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2231 p = redtail(p,strat->sl,strat);
2232 }
2233 /*- release temp data------------------------------- -*/
2234 cleanT(strat);
2235 assume(strat->L==NULL); /*strat->L unused */
2236 assume(strat->B==NULL); /*strat->B unused */
2237 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2238 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2239 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2240 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2241 omFree(strat->sevT);
2242 omFree(strat->S_2_R);
2243 omFree(strat->R);
2244
2245 omfree((ADDRESS)strat->fromQ);
2246 strat->fromQ=NULL;
2247 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2248// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2249// {
2250// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2251// if (ecartWeights)
2252// {
2253// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2254// ecartWeights=NULL;
2255// }
2256// }
2257 idDelete(&strat->Shdl);
2259 if (TEST_OPT_PROT) PrintLn();
2260 return p;
2261}
2262
2264{
2265 assume(!idIs0(q));
2266 assume(!(idIs0(F)&&(Q==NULL)));
2267
2268// lazy_reduce flags: can be combined by |
2269//#define KSTD_NF_LAZY 1
2270 // do only a reduction of the leading term
2271//#define KSTD_NF_ECART 2
2272 // only local: reduce even with bad ecart
2273 poly p;
2274 int i;
2275 int j;
2276 int o;
2277 LObject h;
2278 ideal res;
2279 BITSET save1;
2281
2282 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2283 //if ((idIs0(F))&&(Q==NULL))
2284 // return idCopy(q); /*F=0*/
2285 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2286 /*- creating temp data structures------------------- -*/
2287 strat->kAllAxis = (currRing->ppNoether) != NULL;
2288 strat->kNoether=pCopy((currRing->ppNoether));
2291 && (0<Kstd1_deg)
2292 && ((strat->kNoether==NULL)
2294 {
2295 pLmDelete(&strat->kNoether);
2296 strat->kNoether=pOne();
2297 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2298 pSetm(strat->kNoether);
2299 //strat->kAllAxis=TRUE;
2300 }
2301 initBuchMoraCrit(strat);
2303 initBuchMoraPosRing(strat);
2304 else
2305 initBuchMoraPos(strat);
2306 initMora(F,strat);
2307 strat->enterS = enterSMoraNF;
2308 /*- set T -*/
2309 strat->tl = -1;
2310 strat->tmax = setmaxT;
2311 strat->T = initT();
2312 strat->R = initR();
2313 strat->sevT = initsevT();
2314 /*- set S -*/
2315 strat->sl = -1;
2316 /*- init local data struct.-------------------------- -*/
2317 /*Shdl=*/initS(F,Q,strat);
2318 if ((strat->ak!=0)
2319 && (strat->kNoether!=NULL))
2320 {
2321 if (strat->ak!=1)
2322 {
2323 pSetComp(strat->kNoether,1);
2324 pSetmComp(strat->kNoether);
2325 poly p=pHead(strat->kNoether);
2326 pSetComp(p,strat->ak);
2327 pSetmComp(p);
2328 p=pAdd(strat->kNoether,p);
2329 strat->kNoether=pNext(p);
2331 }
2332 }
2333 if (((lazyReduce & KSTD_NF_LAZY)==0)
2334 && (!rField_is_Ring(currRing)))
2335 {
2336 for (i=strat->sl; i>=0; i--)
2337 pNorm(strat->S[i]);
2338 }
2339 /*- compute------------------------------------------- -*/
2340 res=idInit(IDELEMS(q),strat->ak);
2341 for (i=0; i<IDELEMS(q); i++)
2342 {
2343 if (q->m[i]!=NULL)
2344 {
2345 p = pCopy(q->m[i]);
2346 deleteHC(&p,&o,&j,strat);
2347 if (p!=NULL)
2348 {
2349 /*- puts the elements of S also to T -*/
2350 for (j=0; j<=strat->sl; j++)
2351 {
2352 h.p = strat->S[j];
2353 h.ecart = strat->ecartS[j];
2354 h.pLength = h.length = pLength(h.p);
2355 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2356 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2357 h.sev = strat->sevS[j];
2358 h.SetpFDeg();
2360 enterT_strong(h,strat);
2361 else
2362 enterT(h,strat);
2363 }
2364 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2366 {
2367 p = redMoraNFRing(p,strat, lazyReduce);
2368 }
2369 else
2370 p = redMoraNF(p,strat, lazyReduce);
2371 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2372 {
2373 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2374 p = redtail(p,strat->sl,strat);
2375 }
2376 cleanT(strat);
2377 }
2378 res->m[i]=p;
2379 }
2380 //else
2381 // res->m[i]=NULL;
2382 }
2383 /*- release temp data------------------------------- -*/
2384 assume(strat->L==NULL); /*strat->L unused */
2385 assume(strat->B==NULL); /*strat->B unused */
2386 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2387 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2388 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2389 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2390 omFree(strat->sevT);
2391 omFree(strat->S_2_R);
2392 omFree(strat->R);
2393 omfree((ADDRESS)strat->fromQ);
2394 strat->fromQ=NULL;
2395 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2396// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2397// {
2398// pFDeg=strat->pOrigFDeg;
2399// pLDeg=strat->pOrigLDeg;
2400// if (ecartWeights)
2401// {
2402// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2403// ecartWeights=NULL;
2404// }
2405// }
2406 idDelete(&strat->Shdl);
2408 if (TEST_OPT_PROT) PrintLn();
2409 return res;
2410}
2411
2413
2414long kModDeg(poly p,const ring r)
2415{
2416 long o=p_WDegree(p, r);
2417 long i=__p_GetComp(p, r);
2418 if (i==0) return o;
2419 //assume((i>0) && (i<=kModW->length()));
2420 if (i<=kModW->length())
2421 return o+(*kModW)[i-1];
2422 return o;
2423}
2424long kHomModDeg(poly p,const ring r)
2425{
2426 int i;
2427 long j=0;
2428
2429 for (i=r->N;i>0;i--)
2430 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2431 if (kModW == NULL) return j;
2432 i = __p_GetComp(p,r);
2433 if (i==0) return j;
2434 return j+(*kModW)[i-1];
2435}
2436
2437static poly kTryHC(ideal F, ideal Q)
2438{
2439 if (TEST_OPT_PROT) PrintS("try HC in Zp ring\n");
2440 // create Zp_ring
2443 nKillChar(Zp_ring->cf);
2444 Zp_ring->cf=nInitChar(n_Zp, (void*)(long)32003);
2446 // map data
2450 ideal QQ=NULL;
2452 // call std
2454 // clean
2455 idDelete(&FF);
2456 if (QQ!=NULL) idDelete(&QQ);
2457 idDelete(&res);
2458 // map back
2460 poly p=NULL;
2461 if (Zp_ring->ppNoether!=NULL)
2462 {
2464 Zp_ring->ppNoether=NULL;
2465 if (TEST_OPT_PROT) PrintS("HC found in Zp ring\n");
2466 }
2468 return p;
2469}
2470
2472 int newIdeal, intvec *vw, s_poly_proc_t sp)
2473{
2474 if(idIs0(F))
2475 return idInit(1,F->rank);
2476
2477 if((Q!=NULL)&&(idIs0(Q))) Q=NULL;
2478#ifdef HAVE_SHIFTBBA
2479 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2480#endif
2481
2482 /* test HC precomputation*/
2483 poly save_noether=currRing->ppNoether;
2484 int ak = id_RankFreeModule(F,currRing);
2485 if((ak==0)
2486 && (h!=isHomog)
2487 && (w==NULL)
2488 && (hilb==NULL)
2489 && (vw==NULL)
2490 && (newIdeal==0)
2491 && (sp==NULL)
2495 currRing->ppNoether=kTryHC(F,Q);
2496
2497 ideal r;
2498 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2500 kStrategy strat=new skStrategy;
2501
2502 strat->s_poly=sp;
2504 strat->syzComp = syzComp;
2505 if (TEST_OPT_SB_1
2507 )
2508 strat->newIdeal = newIdeal;
2510 strat->LazyPass=20;
2511 else
2512 strat->LazyPass=2;
2513 strat->LazyDegree = 1;
2514 strat->ak = ak;
2515 strat->kModW=kModW=NULL;
2516 strat->kHomW=kHomW=NULL;
2517 if (vw != NULL)
2518 {
2519 currRing->pLexOrder=FALSE;
2520 strat->kHomW=kHomW=vw;
2521 strat->pOrigFDeg = currRing->pFDeg;
2522 strat->pOrigLDeg = currRing->pLDeg;
2524 toReset = TRUE;
2525 }
2526 if (h==testHomog)
2527 {
2528 if (strat->ak == 0)
2529 {
2530 h = (tHomog)idHomIdeal(F,Q);
2531 w=NULL;
2532 }
2533 else if (!TEST_OPT_DEGBOUND)
2534 {
2535 if (w!=NULL)
2536 h = (tHomog)idHomModule(F,Q,w);
2537 else
2538 h = (tHomog)idHomIdeal(F,Q);
2539 }
2540 }
2541 currRing->pLexOrder=b;
2542 if (h==isHomog)
2543 {
2544 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2545 {
2546 strat->kModW = kModW = *w;
2547 if (vw == NULL)
2548 {
2549 strat->pOrigFDeg = currRing->pFDeg;
2550 strat->pOrigLDeg = currRing->pLDeg;
2552 toReset = TRUE;
2553 }
2554 }
2555 currRing->pLexOrder = TRUE;
2556 if (hilb==NULL) strat->LazyPass*=2;
2557 }
2558 strat->homog=h;
2559#ifdef KDEBUG
2560 idTest(F);
2561 if (Q!=NULL) idTest(Q);
2562#endif
2563#ifdef HAVE_PLURAL
2565 {
2566 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2567 strat->no_prod_crit = ! bIsSCA;
2568 if (w!=NULL)
2569 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2570 else
2571 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2572 }
2573 else
2574#endif
2575 {
2576 #if PRE_INTEGER_CHECK
2577 //the preinteger check strategy is not for modules
2578 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2579 {
2580 ideal FCopy = idCopy(F);
2581 poly pFmon = preIntegerCheck(FCopy, Q);
2582 if(pFmon != NULL)
2583 {
2585 strat->kModW=kModW=NULL;
2586 if (h==testHomog)
2587 {
2588 if (strat->ak == 0)
2589 {
2591 w=NULL;
2592 }
2593 else if (!TEST_OPT_DEGBOUND)
2594 {
2595 if (w!=NULL)
2597 else
2599 }
2600 }
2601 currRing->pLexOrder=b;
2602 if (h==isHomog)
2603 {
2604 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2605 {
2606 strat->kModW = kModW = *w;
2607 if (vw == NULL)
2608 {
2609 strat->pOrigFDeg = currRing->pFDeg;
2610 strat->pOrigLDeg = currRing->pLDeg;
2612 toReset = TRUE;
2613 }
2614 }
2615 currRing->pLexOrder = TRUE;
2616 if (hilb==NULL) strat->LazyPass*=2;
2617 }
2618 strat->homog=h;
2619 }
2620 omTestMemory(1);
2621 if(w == NULL)
2622 {
2624 r=mora(FCopy,Q,NULL,hilb,strat);
2625 else
2626 r=bba(FCopy,Q,NULL,hilb,strat);
2627 }
2628 else
2629 {
2631 r=mora(FCopy,Q,*w,hilb,strat);
2632 else
2633 r=bba(FCopy,Q,*w,hilb,strat);
2634 }
2635 idDelete(&FCopy);
2636 }
2637 else
2638 #endif
2639 {
2640 if(w==NULL)
2641 {
2643 r=mora(F,Q,NULL,hilb,strat);
2644 else
2645 r=bba(F,Q,NULL,hilb,strat);
2646 }
2647 else
2648 {
2650 r=mora(F,Q,*w,hilb,strat);
2651 else
2652 r=bba(F,Q,*w,hilb,strat);
2653 }
2654 }
2655 }
2656#ifdef KDEBUG
2657 idTest(r);
2658#endif
2659 if (toReset)
2660 {
2661 kModW = NULL;
2663 }
2664 currRing->pLexOrder = b;
2665//Print("%d reductions canceled \n",strat->cel);
2666 delete(strat);
2667 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2668 if (currRing->ppNoether!=save_noether) pLmDelete(&currRing->ppNoether);
2669 currRing->ppNoether=save_noether;
2670 return r;
2671}
2672
2673ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int sbaOrder, int arri, intvec *hilb,int syzComp,
2674 int newIdeal, intvec *vw)
2675{
2676 if(idIs0(F))
2677 return idInit(1,F->rank);
2679 {
2680 ideal r;
2681 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2683 kStrategy strat=new skStrategy;
2684 strat->sbaOrder = sbaOrder;
2685 if (arri!=0)
2686 {
2687 strat->rewCrit1 = arriRewDummy;
2688 strat->rewCrit2 = arriRewCriterion;
2690 }
2691 else
2692 {
2696 }
2697
2699 strat->syzComp = syzComp;
2700 if (TEST_OPT_SB_1)
2701 //if(!rField_is_Ring(currRing)) // always true here
2702 strat->newIdeal = newIdeal;
2704 strat->LazyPass=20;
2705 else
2706 strat->LazyPass=2;
2707 strat->LazyDegree = 1;
2711 strat->ak = id_RankFreeModule(F,currRing);
2712 strat->kModW=kModW=NULL;
2713 strat->kHomW=kHomW=NULL;
2714 if (vw != NULL)
2715 {
2716 currRing->pLexOrder=FALSE;
2717 strat->kHomW=kHomW=vw;
2718 strat->pOrigFDeg = currRing->pFDeg;
2719 strat->pOrigLDeg = currRing->pLDeg;
2721 toReset = TRUE;
2722 }
2723 if (h==testHomog)
2724 {
2725 if (strat->ak == 0)
2726 {
2727 h = (tHomog)idHomIdeal(F,Q);
2728 w=NULL;
2729 }
2730 else if (!TEST_OPT_DEGBOUND)
2731 {
2732 if (w!=NULL)
2733 h = (tHomog)idHomModule(F,Q,w);
2734 else
2735 h = (tHomog)idHomIdeal(F,Q);
2736 }
2737 }
2738 currRing->pLexOrder=b;
2739 if (h==isHomog)
2740 {
2741 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2742 {
2743 strat->kModW = kModW = *w;
2744 if (vw == NULL)
2745 {
2746 strat->pOrigFDeg = currRing->pFDeg;
2747 strat->pOrigLDeg = currRing->pLDeg;
2749 toReset = TRUE;
2750 }
2751 }
2752 currRing->pLexOrder = TRUE;
2753 if (hilb==NULL) strat->LazyPass*=2;
2754 }
2755 strat->homog=h;
2756 #ifdef KDEBUG
2757 idTest(F);
2758 if(Q != NULL)
2759 idTest(Q);
2760 #endif
2761 #ifdef HAVE_PLURAL
2763 {
2764 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2765 strat->no_prod_crit = ! bIsSCA;
2766 if (w!=NULL)
2767 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2768 else
2769 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2770 }
2771 else
2772 #endif
2773 {
2775 {
2776 if (w!=NULL)
2777 r=mora(F,Q,*w,hilb,strat);
2778 else
2779 r=mora(F,Q,NULL,hilb,strat);
2780 }
2781 else
2782 {
2783 strat->sigdrop = FALSE;
2784 if (w!=NULL)
2785 r=sba(F,Q,*w,hilb,strat);
2786 else
2787 r=sba(F,Q,NULL,hilb,strat);
2788 }
2789 }
2790 #ifdef KDEBUG
2791 idTest(r);
2792 #endif
2793 if (toReset)
2794 {
2795 kModW = NULL;
2797 }
2798 currRing->pLexOrder = b;
2799 //Print("%d reductions canceled \n",strat->cel);
2800 //delete(strat);
2801 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2802 return r;
2803 }
2804 else
2805 {
2806 //--------------------------RING CASE-------------------------
2807 assume(sbaOrder == 1);
2808 assume(arri == 0);
2809 ideal r;
2810 r = idCopy(F);
2811 int sbaEnterS = -1;
2812 bool sigdrop = TRUE;
2813 //This is how we set the SBA algorithm;
2814 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2815 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2816 && (blockred <= blockedreductions))
2817 {
2818 loops++;
2819 if(loops == 1)
2820 sigdrop = FALSE;
2821 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2823 kStrategy strat=new skStrategy;
2824 strat->sbaEnterS = sbaEnterS;
2825 strat->sigdrop = sigdrop;
2826 #if 0
2827 strat->blockred = blockred;
2828 #else
2829 strat->blockred = 0;
2830 #endif
2832 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2833 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2834 strat->sbaOrder = sbaOrder;
2835 if (arri!=0)
2836 {
2837 strat->rewCrit1 = arriRewDummy;
2838 strat->rewCrit2 = arriRewCriterion;
2840 }
2841 else
2842 {
2846 }
2847
2849 strat->syzComp = syzComp;
2850 if (TEST_OPT_SB_1)
2852 strat->newIdeal = newIdeal;
2854 strat->LazyPass=20;
2855 else
2856 strat->LazyPass=2;
2857 strat->LazyDegree = 1;
2861 strat->ak = id_RankFreeModule(F,currRing);
2862 strat->kModW=kModW=NULL;
2863 strat->kHomW=kHomW=NULL;
2864 if (vw != NULL)
2865 {
2866 currRing->pLexOrder=FALSE;
2867 strat->kHomW=kHomW=vw;
2868 strat->pOrigFDeg = currRing->pFDeg;
2869 strat->pOrigLDeg = currRing->pLDeg;
2871 toReset = TRUE;
2872 }
2873 if (h==testHomog)
2874 {
2875 if (strat->ak == 0)
2876 {
2877 h = (tHomog)idHomIdeal(F,Q);
2878 w=NULL;
2879 }
2880 else if (!TEST_OPT_DEGBOUND)
2881 {
2882 if (w!=NULL)
2883 h = (tHomog)idHomModule(F,Q,w);
2884 else
2885 h = (tHomog)idHomIdeal(F,Q);
2886 }
2887 }
2888 currRing->pLexOrder=b;
2889 if (h==isHomog)
2890 {
2891 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2892 {
2893 strat->kModW = kModW = *w;
2894 if (vw == NULL)
2895 {
2896 strat->pOrigFDeg = currRing->pFDeg;
2897 strat->pOrigLDeg = currRing->pLDeg;
2899 toReset = TRUE;
2900 }
2901 }
2902 currRing->pLexOrder = TRUE;
2903 if (hilb==NULL) strat->LazyPass*=2;
2904 }
2905 strat->homog=h;
2906 #ifdef KDEBUG
2907 idTest(F);
2908 if(Q != NULL)
2909 idTest(Q);
2910 #endif
2911 #ifdef HAVE_PLURAL
2913 {
2914 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2915 strat->no_prod_crit = ! bIsSCA;
2916 if (w!=NULL)
2917 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2918 else
2919 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2920 }
2921 else
2922 #endif
2923 {
2925 {
2926 if (w!=NULL)
2927 r=mora(F,Q,*w,hilb,strat);
2928 else
2929 r=mora(F,Q,NULL,hilb,strat);
2930 }
2931 else
2932 {
2933 if (w!=NULL)
2934 r=sba(r,Q,*w,hilb,strat);
2935 else
2936 {
2937 r=sba(r,Q,NULL,hilb,strat);
2938 }
2939 }
2940 }
2941 #ifdef KDEBUG
2942 idTest(r);
2943 #endif
2944 if (toReset)
2945 {
2946 kModW = NULL;
2948 }
2949 currRing->pLexOrder = b;
2950 //Print("%d reductions canceled \n",strat->cel);
2951 sigdrop = strat->sigdrop;
2952 sbaEnterS = strat->sbaEnterS;
2953 blockred = strat->blockred;
2954 delete(strat);
2955 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2956 }
2957 // Go to std
2958 if(sigdrop || blockred > blockedreductions)
2959 {
2960 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2961 }
2962 return r;
2963 }
2964}
2965
2966#ifdef HAVE_SHIFTBBA
2968 int newIdeal, intvec *vw, BOOLEAN rightGB)
2969{
2971 assume(idIsInV(F));
2972 ideal r;
2973 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2975 kStrategy strat=new skStrategy;
2976
2977 strat->rightGB = rightGB;
2978
2980 strat->syzComp = syzComp;
2981 if (TEST_OPT_SB_1)
2983 strat->newIdeal = newIdeal;
2985 strat->LazyPass=20;
2986 else
2987 strat->LazyPass=2;
2988 strat->LazyDegree = 1;
2989 strat->ak = id_RankFreeModule(F,currRing);
2990 strat->kModW=kModW=NULL;
2991 strat->kHomW=kHomW=NULL;
2992 if (vw != NULL)
2993 {
2994 currRing->pLexOrder=FALSE;
2995 strat->kHomW=kHomW=vw;
2996 strat->pOrigFDeg = currRing->pFDeg;
2997 strat->pOrigLDeg = currRing->pLDeg;
2999 toReset = TRUE;
3000 }
3001 if (h==testHomog)
3002 {
3003 if (strat->ak == 0)
3004 {
3005 h = (tHomog)idHomIdeal(F,Q);
3006 w=NULL;
3007 }
3008 else if (!TEST_OPT_DEGBOUND)
3009 {
3010 if (w!=NULL)
3011 h = (tHomog)idHomModule(F,Q,w);
3012 else
3013 h = (tHomog)idHomIdeal(F,Q);
3014 }
3015 }
3016 currRing->pLexOrder=b;
3017 if (h==isHomog)
3018 {
3019 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3020 {
3021 strat->kModW = kModW = *w;
3022 if (vw == NULL)
3023 {
3024 strat->pOrigFDeg = currRing->pFDeg;
3025 strat->pOrigLDeg = currRing->pLDeg;
3027 toReset = TRUE;
3028 }
3029 }
3030 currRing->pLexOrder = TRUE;
3031 if (hilb==NULL) strat->LazyPass*=2;
3032 }
3033 strat->homog=h;
3034#ifdef KDEBUG
3035 idTest(F);
3036#endif
3038 {
3039 /* error: no local ord yet with shifts */
3040 WerrorS("No local ordering possible for shift algebra");
3041 return(NULL);
3042 }
3043 else
3044 {
3045 /* global ordering */
3046 if (w!=NULL)
3047 r=bbaShift(F,Q,*w,hilb,strat);
3048 else
3049 r=bbaShift(F,Q,NULL,hilb,strat);
3050 }
3051#ifdef KDEBUG
3052 idTest(r);
3053#endif
3054 if (toReset)
3055 {
3056 kModW = NULL;
3058 }
3059 currRing->pLexOrder = b;
3060//Print("%d reductions canceled \n",strat->cel);
3061 delete(strat);
3062 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3063 assume(idIsInV(r));
3064 return r;
3065}
3066#endif
3067
3068//##############################################################
3069//##############################################################
3070//##############################################################
3071//##############################################################
3072//##############################################################
3073
3075 int syzComp, int reduced)
3076{
3077 if(idIs0(F))
3078 {
3079 M=idInit(1,F->rank);
3080 return idInit(1,F->rank);
3081 }
3083 {
3084 ideal sb;
3085 sb = kStd(F, Q, h, w, hilb);
3087 if(IDELEMS(sb) <= IDELEMS(F))
3088 {
3089 M = idCopy(sb);
3090 idSkipZeroes(M);
3091 return(sb);
3092 }
3093 else
3094 {
3095 M = idCopy(F);
3096 idSkipZeroes(M);
3097 return(sb);
3098 }
3099 }
3100 ideal r=NULL;
3101 int Kstd1_OldDeg = Kstd1_deg,i;
3103 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3106 kStrategy strat=new skStrategy;
3107
3109 strat->syzComp = syzComp;
3111 strat->LazyPass=20;
3112 else
3113 strat->LazyPass=2;
3114 strat->LazyDegree = 1;
3115 strat->minim=(reduced % 2)+1;
3116 strat->ak = id_RankFreeModule(F,currRing);
3117 if (delete_w)
3118 {
3119 temp_w=new intvec((strat->ak)+1);
3120 w = &temp_w;
3121 }
3122 if (h==testHomog)
3123 {
3124 if (strat->ak == 0)
3125 {
3126 h = (tHomog)idHomIdeal(F,Q);
3127 w=NULL;
3128 }
3129 else
3130 {
3131 h = (tHomog)idHomModule(F,Q,w);
3132 }
3133 }
3134 if (h==isHomog)
3135 {
3136 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3137 {
3138 kModW = *w;
3139 strat->kModW = *w;
3140 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3141 strat->pOrigFDeg = currRing->pFDeg;
3142 strat->pOrigLDeg = currRing->pLDeg;
3144
3145 toReset = TRUE;
3146 if (reduced>1)
3147 {
3149 Kstd1_deg = -1;
3150 for (i=IDELEMS(F)-1;i>=0;i--)
3151 {
3152 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3153 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3154 }
3155 }
3156 }
3157 currRing->pLexOrder = TRUE;
3158 strat->LazyPass*=2;
3159 }
3160 strat->homog=h;
3161 ideal SB=NULL;
3163 {
3164 r=idMinBase(F,&SB); // SB and M via minbase
3165 strat->M=r;
3166 r=SB;
3167 }
3168 else
3169 {
3170 if (w!=NULL)
3171 r=bba(F,Q,*w,hilb,strat);
3172 else
3173 r=bba(F,Q,NULL,hilb,strat);
3174 }
3175#ifdef KDEBUG
3176 {
3177 int i;
3178 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3179 }
3180#endif
3181 idSkipZeroes(r);
3182 if (toReset)
3183 {
3185 kModW = NULL;
3186 }
3187 currRing->pLexOrder = b;
3188 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3189 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3190 {
3191 M=idInit(1,F->rank);
3192 M->m[0]=pOne();
3193 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3194 if (strat->M!=NULL) idDelete(&strat->M);
3195 }
3196 else if (strat->M==NULL)
3197 {
3198 M=idInit(1,F->rank);
3199 WarnS("no minimal generating set computed");
3200 }
3201 else
3202 {
3203 idSkipZeroes(strat->M);
3204 M=strat->M;
3205 strat->M=NULL;
3206 }
3207 delete(strat);
3208 if (reduced>2)
3209 {
3211 if (!oldDegBound)
3212 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3213 }
3214 else
3215 {
3216 if (IDELEMS(M)>IDELEMS(r))
3217 {
3218 idDelete(&M);
3219 M=idCopy(r);
3220 }
3221 }
3222 return r;
3223}
3224
3225poly kNF(ideal F, ideal Q, poly p,int syzComp, int lazyReduce)
3226{
3227 if (p==NULL)
3228 return NULL;
3229
3230 poly pp = p;
3231
3232#ifdef HAVE_PLURAL
3233 if(rIsSCA(currRing))
3234 {
3235 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3236 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3238
3239 if(Q == currRing->qideal)
3241 }
3242#endif
3243 if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3244
3245 if ((idIs0(F))&&(Q==NULL))
3246 {
3247#ifdef HAVE_PLURAL
3248 if(p != pp)
3249 return pp;
3250#endif
3251 return pCopy(p); /*F+Q=0*/
3252 }
3253
3254 kStrategy strat=new skStrategy;
3255 strat->syzComp = syzComp;
3257 poly res;
3258
3260 {
3261#ifdef HAVE_SHIFTBBA
3262 if (currRing->isLPring)
3263 {
3264 WerrorS("No local ordering possible for shift algebra");
3265 return(NULL);
3266 }
3267#endif
3268 res=kNF1(F,Q,pp,strat,lazyReduce);
3269 }
3270 else
3271 res=kNF2(F,Q,pp,strat,lazyReduce);
3272 delete(strat);
3273
3274#ifdef HAVE_PLURAL
3275 if(pp != p)
3276 p_Delete(&pp, currRing);
3277#endif
3278 return res;
3279}
3280
3281poly kNFBound(ideal F, ideal Q, poly p,int bound,int syzComp, int lazyReduce)
3282{
3283 if (p==NULL)
3284 return NULL;
3285
3286 poly pp = p;
3287
3288#ifdef HAVE_PLURAL
3289 if(rIsSCA(currRing))
3290 {
3291 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3292 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3294
3295 if(Q == currRing->qideal)
3297 }
3298#endif
3299
3300 if ((idIs0(F))&&(Q==NULL))
3301 {
3302#ifdef HAVE_PLURAL
3303 if(p != pp)
3304 return pp;
3305#endif
3306 return pCopy(p); /*F+Q=0*/
3307 }
3308
3309 kStrategy strat=new skStrategy;
3310 strat->syzComp = syzComp;
3312 poly res;
3313 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3314 delete(strat);
3315
3316#ifdef HAVE_PLURAL
3317 if(pp != p)
3318 p_Delete(&pp, currRing);
3319#endif
3320 return res;
3321}
3322
3323ideal kNF(ideal F, ideal Q, ideal p,int syzComp,int lazyReduce)
3324{
3325 ideal res;
3326 if (TEST_OPT_PROT)
3327 {
3328 Print("(S:%d)",IDELEMS(p));mflush();
3329 }
3330 if (idIs0(p))
3331 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3332
3333 ideal pp = p;
3334#ifdef HAVE_PLURAL
3335 if(rIsSCA(currRing))
3336 {
3337 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3338 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3340
3341 if(Q == currRing->qideal)
3343 }
3344#endif
3345
3346 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3347
3348 if ((idIs0(F))&&(Q==NULL))
3349 {
3350#ifdef HAVE_PLURAL
3351 if(p != pp)
3352 return pp;
3353#endif
3354 return idCopy(p); /*F+Q=0*/
3355 }
3356
3357 kStrategy strat=new skStrategy;
3358 strat->syzComp = syzComp;
3360 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3361 {
3362 strat->ak = si_max(strat->ak,(int)F->rank);
3363 }
3364
3366 {
3367#ifdef HAVE_SHIFTBBA
3368 if (currRing->isLPring)
3369 {
3370 WerrorS("No local ordering possible for shift algebra");
3371 return(NULL);
3372 }
3373#endif
3374 res=kNF1(F,Q,pp,strat,lazyReduce);
3375 }
3376 else
3377 res=kNF2(F,Q,pp,strat,lazyReduce);
3378 delete(strat);
3379
3380#ifdef HAVE_PLURAL
3381 if(pp != p)
3383#endif
3384
3385 return res;
3386}
3387
3389{
3390 ideal res;
3391 if (TEST_OPT_PROT)
3392 {
3393 Print("(S:%d)",IDELEMS(p));mflush();
3394 }
3395 if (idIs0(p))
3396 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3397
3398 ideal pp = p;
3399#ifdef HAVE_PLURAL
3400 if(rIsSCA(currRing))
3401 {
3402 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3403 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3405
3406 if(Q == currRing->qideal)
3408 }
3409#endif
3410
3411 if ((idIs0(F))&&(Q==NULL))
3412 {
3413#ifdef HAVE_PLURAL
3414 if(p != pp)
3415 return pp;
3416#endif
3417 return idCopy(p); /*F+Q=0*/
3418 }
3419
3420 kStrategy strat=new skStrategy;
3421 strat->syzComp = syzComp;
3423 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3424 {
3425 strat->ak = si_max(strat->ak,(int)F->rank);
3426 }
3427
3428 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3429 delete(strat);
3430
3431#ifdef HAVE_PLURAL
3432 if(pp != p)
3434#endif
3435
3436 return res;
3437}
3438
3439poly k_NF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing)
3440{
3441 const ring save = currRing;
3443 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3445 return ret;
3446}
3447
3448/*2
3449*interreduces F
3450*/
3451// old version
3453{
3454 int j;
3455 kStrategy strat = new skStrategy;
3456
3457 ideal tempF = F;
3458 ideal tempQ = Q;
3459
3460#ifdef HAVE_PLURAL
3461 if(rIsSCA(currRing))
3462 {
3463 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3464 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3466
3467 // this should be done on the upper level!!! :
3468 // tempQ = SCAQuotient(currRing);
3469
3470 if(Q == currRing->qideal)
3472 }
3473#endif
3474
3475// if (TEST_OPT_PROT)
3476// {
3477// writeTime("start InterRed:");
3478// mflush();
3479// }
3480 //strat->syzComp = 0;
3481 strat->kAllAxis = (currRing->ppNoether) != NULL;
3482 strat->kNoether=pCopy((currRing->ppNoether));
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;
3530 if (strat->fromQ)
3531 {
3532 omfree(strat->fromQ);
3533 strat->fromQ=NULL;
3535 idDelete(&shdl);
3536 shdl=res;
3537 }
3538 delete(strat);
3539#ifdef HAVE_PLURAL
3540 if( tempF != F )
3542#endif
3543 return shdl;
3544}
3545// new version
3547{
3548 need_retry=0;
3549 int red_result = 1;
3550 int olddeg,reduc;
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 if (0)
3661 //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3662 {
3663 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3664 strat->P.pCleardenom();
3665 }
3666 }
3667 else
3668 {
3669 strat->P.pNorm();
3670 if (0)
3671 //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3672 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3673 }
3674
3675#ifdef KDEBUG
3676 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3677#endif
3678
3679 // enter into S, L, and T
3680 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3681 {
3682 enterT(strat->P, strat);
3683 // posInS only depends on the leading term
3684 strat->enterS(strat->P, pos, strat, strat->tl);
3685
3686 if (pos<strat->sl)
3687 {
3688 need_retry++;
3689 // move all "larger" elements fromS to L
3690 // remove them from T
3691 int ii=pos+1;
3692 for(;ii<=strat->sl;ii++)
3693 {
3694 LObject h;
3695 h.Clear();
3696 h.tailRing=strat->tailRing;
3697 h.p=strat->S[ii]; strat->S[ii]=NULL;
3698 strat->initEcart(&h);
3699 h.sev=strat->sevS[ii];
3700 int jj=strat->tl;
3701 while (jj>=0)
3702 {
3703 if (strat->T[jj].p==h.p)
3704 {
3705 strat->T[jj].p=NULL;
3706 if (jj<strat->tl)
3707 {
3708 memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3709 (strat->tl-jj)*sizeof(strat->T[jj]));
3710 memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3711 (strat->tl-jj)*sizeof(strat->sevT[jj]));
3712 }
3713 strat->tl--;
3714 break;
3715 }
3716 jj--;
3717 }
3718 int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3719 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3720 #ifdef KDEBUG
3721 if (TEST_OPT_DEBUG)
3722 {
3723 Print("move S[%d] -> L[%d]: ",ii,pos);
3724 p_wrp(h.p,currRing, strat->tailRing);
3725 PrintLn();
3726 }
3727 #endif
3728 }
3729 if (strat->fromQ!=NULL)
3730 {
3731 for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3732 }
3733 strat->sl=pos;
3734 }
3735 }
3736 else
3737 {
3738 // clean P
3739 }
3740 kDeleteLcm(&strat->P);
3741 }
3742
3743#ifdef KDEBUG
3744 if (TEST_OPT_DEBUG)
3745 {
3746 messageSets(strat);
3747 }
3748 strat->P.Clear();
3749#endif
3750 //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3751 }
3752#ifdef KDEBUG
3753 //if (TEST_OPT_DEBUG) messageSets(strat);
3754#endif
3755 /* complete reduction of the standard basis--------- */
3756
3757 if((need_retry<=0) && (TEST_OPT_REDSB))
3758 {
3759 completeReduce(strat);
3760 if (strat->completeReduce_retry)
3761 {
3762 // completeReduce needed larger exponents, retry
3763 // hopefully: kStratChangeTailRing already provided a larger tailRing
3764 // (otherwise: it will fail again)
3766 completeReduce(strat);
3767 if (strat->completeReduce_retry)
3768 {
3769#ifdef HAVE_TAIL_RING
3770 if(currRing->bitmask>strat->tailRing->bitmask)
3771 {
3772 // retry without T
3774 cleanT(strat);strat->tailRing=currRing;
3775 int i;
3776 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3777 completeReduce(strat);
3778 }
3779 if (strat->completeReduce_retry)
3780#endif
3781 Werror("exponent bound is %ld",currRing->bitmask);
3782 }
3783 }
3784 }
3785 else if (TEST_OPT_PROT) PrintLn();
3786
3787
3788 /* release temp data-------------------------------- */
3789 exitBuchMora(strat);
3790// if (TEST_OPT_WEIGHTM)
3791// {
3792// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3793// if (ecartWeights)
3794// {
3795// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3796// ecartWeights=NULL;
3797// }
3798// }
3799 //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3800 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3801 ideal res=strat->Shdl;
3802 strat->Shdl=NULL;
3803 delete strat;
3804 return res;
3805}
3807{
3808#ifdef HAVE_PLURAL
3809 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3810#endif
3813 )
3814 return kInterRedOld(F,Q);
3815
3816 //return kInterRedOld(F,Q);
3817
3818 BITSET save1;
3820 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3822 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3823 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3824 //extern char * showOption() ;
3825 //Print("%s\n",showOption());
3826
3827 int need_retry;
3828 int counter=3;
3829 ideal res, res1;
3830 int elems;
3831 ideal null=NULL;
3832 if ((Q==NULL) || (!TEST_OPT_REDSB))
3833 {
3834 elems=idElem(F);
3836 }
3837 else
3838 {
3839 ideal FF=idSimpleAdd(F,Q);
3841 idDelete(&FF);
3842 null=idInit(1,1);
3843 if (need_retry)
3845 else
3846 res1=kNF(null,Q,res);
3847 idDelete(&res);
3848 res=res1;
3849 need_retry=1;
3850 }
3851 if (idElem(res)<=1) need_retry=0;
3852 while (need_retry && (counter>0))
3853 {
3854 #ifdef KDEBUG
3855 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3856 #endif
3858 int new_elems=idElem(res1);
3859 counter -= (new_elems >= elems);
3860 elems = new_elems;
3861 idDelete(&res);
3862 if (idElem(res1)<=1) need_retry=0;
3863 if ((Q!=NULL) && (TEST_OPT_REDSB))
3864 {
3865 if (need_retry)
3867 else
3868 res=kNF(null,Q,res1);
3869 idDelete(&res1);
3870 }
3871 else
3872 res = res1;
3873 if (idElem(res)<=1) need_retry=0;
3874 }
3875 if (null!=NULL) idDelete(&null);
3878 return res;
3879}
3880
3881// returns TRUE if mora should use buckets, false otherwise
3883{
3884#ifdef MORA_USE_BUCKETS
3886 return FALSE;
3887 if (strat->red == redFirst)
3888 {
3889#ifdef NO_LDEG
3890 if (strat->syzComp==0)
3891 return TRUE;
3892#else
3893 if ((strat->homog || strat->honey) && (strat->syzComp==0))
3894 return TRUE;
3895#endif
3896 }
3897 else
3898 {
3899 assume(strat->red == redEcart || strat->red == redRiloc || strat->red == redRiloc_Z);
3900 if (strat->honey && (strat->syzComp==0))
3901 return TRUE;
3902 }
3903#endif
3904 return FALSE;
3905}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
#define UNLIKELY(X)
Definition auxiliary.h:404
int BOOLEAN
Definition auxiliary.h:87
#define TRUE
Definition auxiliary.h:100
#define FALSE
Definition auxiliary.h:96
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
int length() const
KINLINE poly kNoetherTail()
Definition kInline.h:66
intvec * kModW
Definition kutil.h:335
bool sigdrop
Definition kutil.h:358
int syzComp
Definition kutil.h:354
int * S_2_R
Definition kutil.h:342
ring tailRing
Definition kutil.h:343
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:291
char noTailReduction
Definition kutil.h:376
int currIdx
Definition kutil.h:317
char posInLOldFlag
Definition kutil.h:380
pFDegProc pOrigFDeg_TailRing
Definition kutil.h:298
int Ll
Definition kutil.h:351
TSet T
Definition kutil.h:326
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:293
omBin lmBin
Definition kutil.h:344
intset ecartS
Definition kutil.h:309
char honey
Definition kutil.h:375
char rightGB
Definition kutil.h:367
polyset S
Definition kutil.h:306
int minim
Definition kutil.h:357
poly kNoether
Definition kutil.h:329
BOOLEAN * NotUsedAxis
Definition kutil.h:332
LSet B
Definition kutil.h:328
int ak
Definition kutil.h:353
TObject ** R
Definition kutil.h:340
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:295
int lastAxis
Definition kutil.h:355
ideal M
Definition kutil.h:305
int tl
Definition kutil.h:350
int(* red2)(LObject *L, kStrategy strat)
Definition kutil.h:279
unsigned long * sevT
Definition kutil.h:325
intvec * kHomW
Definition kutil.h:336
poly tail
Definition kutil.h:334
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:284
int blockred
Definition kutil.h:363
ideal Shdl
Definition kutil.h:303
unsigned sbaOrder
Definition kutil.h:316
pFDegProc pOrigFDeg
Definition kutil.h:296
int blockredmax
Definition kutil.h:364
int tmax
Definition kutil.h:350
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition kutil.h:288
char LDegLast
Definition kutil.h:383
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:287
char kAllAxis
Definition kutil.h:374
intset fromQ
Definition kutil.h:321
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:286
char use_buckets
Definition kutil.h:381
char interpt
Definition kutil.h:369
int newIdeal
Definition kutil.h:356
char fromT
Definition kutil.h:377
char completeReduce_retry
Definition kutil.h:401
void(* initEcart)(TObject *L)
Definition kutil.h:280
LObject P
Definition kutil.h:302
char noClearS
Definition kutil.h:400
int Lmax
Definition kutil.h:351
char z2homog
Definition kutil.h:372
int LazyPass
Definition kutil.h:353
char no_prod_crit
Definition kutil.h:392
char overflow
Definition kutil.h:402
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.h:290
LSet L
Definition kutil.h:327
char length_pLength
Definition kutil.h:385
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:281
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:278
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
int sl
Definition kutil.h:348
int sbaEnterS
Definition kutil.h:361
int LazyDegree
Definition kutil.h:353
char posInLDependsOnLength
Definition kutil.h:387
unsigned long * sevS
Definition kutil.h:322
char homog
Definition kutil.h:370
pLDegProc pOrigLDeg
Definition kutil.h:297
char update
Definition kutil.h:379
s_poly_proc_t s_poly
Definition kutil.h:300
pLDegProc pOrigLDeg_TailRing
Definition kutil.h:299
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition coeffs.h:809
@ n_Zp
\F{p < 2^31}
Definition coeffs.h:29
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 nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition coeffs.h:701
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition numbers.cc:406
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
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition coeffs.h:80
void nKillChar(coeffs r)
undo all initialisations
Definition numbers.cc:556
#define Print
Definition emacs.cc:80
#define WarnS
Definition emacs.cc:78
CanonicalForm res
Definition facAbsFact.cc:60
const CanonicalForm & w
Definition facAbsFact.cc:51
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:1144
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
STATIC_VAR Poly * h
Definition janet.cc:971
KINLINE TSet initT()
Definition kInline.h:84
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition kInline.h:1209
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 intvec *hilb, kStrategy strat, const ring r)
Definition nc.h:27
void khCheckLocInhom(ideal Q, intvec *w, intvec *hilb, int &count, kStrategy strat)
Definition khstd.cc:244
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
Definition khstd.cc:28
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition kspoly.cc:1204
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:2424
void reorderT(kStrategy strat)
Definition kstd1.cc:1242
poly kNFBound(ideal F, ideal Q, poly p, int bound, int syzComp, int lazyReduce)
Definition kstd1.cc:3281
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd1.cc:1884
void initMora(ideal F, kStrategy strat)
Definition kstd1.cc:1815
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:795
void firstUpdate(kStrategy strat)
Definition kstd1.cc:1557
long kModDeg(poly p, const ring r)
Definition kstd1.cc:2414
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:3439
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:169
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1677
static int doRed(LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
Definition kstd1.cc:119
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition kstd1.cc:3074
void updateLHC(kStrategy strat)
Definition kstd1.cc:1465
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition kstd1.cc:2967
void missingAxis(int *last, kStrategy strat)
Definition kstd1.cc:1280
void reorderL(kStrategy strat)
Definition kstd1.cc:1222
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition kstd1.cc:1361
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition kstd1.cc:3546
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition kstd1.cc:3882
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd1.cc:2122
ideal kInterRed(ideal F, const ideal Q)
Definition kstd1.cc:3806
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition kstd1.cc:100
void initBba(kStrategy strat)
Definition kstd1.cc:1685
int redRiloc(LObject *h, kStrategy strat)
Definition kstd1.cc:386
void initSba(ideal F, kStrategy strat)
Definition kstd1.cc:1745
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition kstd1.cc:1080
void kDebugPrint(kStrategy strat)
Definition kutil.cc:11496
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1624
VAR intvec * kHomW
Definition kstd1.cc:2412
VAR intvec * kModW
Definition kstd1.cc:2412
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3452
void updateL(kStrategy strat)
Definition kstd1.cc:1394
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:1313
static poly kTryHC(ideal F, ideal Q)
Definition kstd1.cc:2437
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3225
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:567
ideal kSba(ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, intvec *hilb, int syzComp, int newIdeal, intvec *vw)
Definition kstd1.cc:2673
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition kstd1.cc:2471
#define KSTD_NF_LAZY
Definition kstd1.h:17
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:50
#define KSTD_NF_NONORM
Definition kstd1.h:21
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition kstd1.h:14
#define KSTD_NF_ECART
Definition kstd1.h:19
EXTERN_VAR int Kstd1_mu
Definition kstd1.h:50
int redRing_Z(LObject *h, kStrategy strat)
Definition kstd2.cc:677
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition kstd2.cc:421
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject *L)
tests if T[0] divides the leading monomial of L, returns -1 if not
Definition kstd2.cc:146
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3929
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2067
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1107
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2967
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2609
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1862
int redSigRing(LObject *h, kStrategy strat)
Definition kstd2.cc:1493
int redSig(LObject *h, kStrategy strat)
Definition kstd2.cc:1326
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition kstd2.cc:4012
int redRing(LObject *h, kStrategy strat)
Definition kstd2.cc:945
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition kstd2.cc:321
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:4574
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7465
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:6838
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5283
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9748
VAR int HCord
Definition kutil.cc:244
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6648
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9140
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6623
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8914
BOOLEAN kTest(kStrategy strat)
Definition kutil.cc:1010
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1071
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1944
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1274
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6564
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4930
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4492
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition kutil.cc:9414
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1320
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9577
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7588
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10957
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5616
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3450
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9239
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition kutil.cc:10700
void HEckeTest(poly pp, kStrategy strat)
Definition kutil.cc:498
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:924
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9833
void initEcartNormal(TObject *h)
Definition kutil.cc:1298
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4668
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8556
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10476
void cleanT(kStrategy strat)
Definition kutil.cc:563
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:799
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition kutil.cc:291
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10076
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4462
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1213
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11050
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9432
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10282
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9662
void messageSets(kStrategy strat)
Definition kutil.cc:7538
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:10535
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3209
void initEcartBBA(TObject *h)
Definition kutil.cc:1306
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1313
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7506
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition kutil.cc:10865
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8791
BOOLEAN newHEdge(kStrategy strat)
Definition kutil.cc:10404
void cancelunit(LObject *L, BOOLEAN inNF)
Definition kutil.cc:370
LObject * LSet
Definition kutil.h:60
static void kDeleteLcm(LObject *P)
Definition kutil.h:868
#define setmaxT
Definition kutil.h:33
#define RED_CANONICALIZE
Definition kutil.h:36
class sTObject TObject
Definition kutil.h:57
class sLObject LObject
Definition kutil.h:58
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:387
#define p_GetComp(p, r)
Definition monomials.h:64
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
#define __p_GetComp(p, r)
Definition monomials.h:63
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:121
#define OPT_SUGARCRIT
Definition options.h:80
#define OPT_PROT
Definition options.h:75
#define OPT_INFREDTAIL
Definition options.h:94
#define OPT_INTSTRATEGY
Definition options.h:92
#define TEST_OPT_IDLIFT
Definition options.h:129
#define TEST_OPT_INTSTRATEGY
Definition options.h:110
#define BVERBOSE(a)
Definition options.h:35
#define OPT_WEIGHTM
Definition options.h:97
#define TEST_OPT_FINDET
Definition options.h:111
#define OPT_REDTAIL
Definition options.h:91
#define SI_SAVE_OPT1(A)
Definition options.h:21
#define SI_RESTORE_OPT1(A)
Definition options.h:24
#define OPT_NOT_SUGAR
Definition options.h:78
#define TEST_OPT_OLDSTD
Definition options.h:123
#define OPT_REDTHROUGH
Definition options.h:82
#define OPT_REDSB
Definition options.h:76
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_REDSB
Definition options.h:104
#define OPT_NOTREGULARITY
Definition options.h:96
#define TEST_OPT_DEGBOUND
Definition options.h:113
#define TEST_OPT_SB_1
Definition options.h:119
#define TEST_OPT_RETURN_SB
Definition options.h:112
#define TEST_OPT_MULTBOUND
Definition options.h:114
#define TEST_OPT_PROT
Definition options.h:103
#define TEST_OPT_REDTHROUGH
Definition options.h:122
#define OPT_INTERRUPT
Definition options.h:79
#define OPT_DEGBOUND
Definition options.h:90
#define TEST_V_DEG_STOP
Definition options.h:137
#define TEST_OPT_FASTHC
Definition options.h:109
#define TEST_OPT_DEBUG
Definition options.h:108
#define OPT_FASTHC
Definition options.h:85
#define TEST_OPT_REDTAIL_SYZ
Definition options.h:117
#define OPT_OLDSTD
Definition options.h:86
#define TEST_OPT_STAIRCASEBOUND
Definition options.h:115
#define TEST_OPT_NOT_BUCKETS
Definition options.h:105
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:3670
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition p_polys.cc:4151
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:3658
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:723
static long p_FDeg(const poly p, const ring r)
Definition p_polys.h:380
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:313
#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:1924
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition p_polys.h:469
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:373
void rChangeCurrRing(ring r)
Definition polys.cc:15
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
Compatibility layer for legacy polynomial operations (over currRing)
#define pAdd(p, q)
Definition polys.h:203
#define pTest(p)
Definition polys.h:414
#define pDelete(p_ptr)
Definition polys.h:186
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:67
#define pSetm(p)
Definition polys.h:271
#define pIsConstant(p)
like above, except that Comp must be 0
Definition polys.h:238
#define pGetComp(p)
Component.
Definition polys.h:37
void pNorm(poly p)
Definition polys.h:362
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition polys.h:146
#define pMaxComp(p)
Definition polys.h:299
#define pSetComp(p, v)
Definition polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:76
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition polys.h:152
void wrp(poly p)
Definition polys.h:310
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:70
#define pSetmComp(p)
TODO:
Definition polys.h:273
#define pNormalize(p)
Definition polys.h:317
#define pSetExp(p, i, v)
Definition polys.h:42
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition polys.h:105
#define pCopy(p)
return a copy of the poly
Definition polys.h:185
#define pOne()
Definition polys.h:315
#define pWTotaldegree(p)
Definition polys.h:283
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 rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition ring.cc:3465
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition ring.cc:1424
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:452
BOOLEAN rOrd_is_ds(const ring r)
Definition ring.cc:2036
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:514
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:405
long(* pLDegProc)(poly p, int *length, ring r)
Definition ring.h:37
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:416
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:511
static BOOLEAN rIsNCRing(const ring r)
Definition ring.h:426
static BOOLEAN rField_is_numeric(const ring r)
Definition ring.h:520
BOOLEAN rHasMixedOrdering(const ring r)
Definition ring.h:768
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:597
BOOLEAN rHasGlobalOrdering(const ring r)
Definition ring.h:766
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:767
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition ring.h:553
#define rField_is_Ring(R)
Definition ring.h:490
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
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
ideal id_PermIdeal(ideal I, int R, int C, const int *perm, const ring src, const ring dst, nMapFunc nMap, const int *par_perm, int P, BOOLEAN use_mult)
mapping ideals/matrices to other rings
#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:35
@ isHomog
Definition structs.h:37
@ testHomog
Definition structs.h:38
@ isNotHomog
Definition structs.h:36
#define BITSET
Definition structs.h:16
#define loop
Definition structs.h:75
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