 |
My Project
debian-1:4.1.2-p1+ds-2
|
Go to the documentation of this file.
18 #define PLURAL_INTERNAL_DECLARATIONS 1
37 #define SBA_INTERRED_START 0
38 #define SBA_TAIL_RED 1
39 #define SBA_PRODUCT_CRITERION 0
40 #define SBA_PRINT_ZERO_REDUCTIONS 0
41 #define SBA_PRINT_REDUCTION_STEPS 0
42 #define SBA_PRINT_OPERATIONS 0
43 #define SBA_PRINT_SIZE_G 0
44 #define SBA_PRINT_SIZE_SYZ 0
45 #define SBA_PRINT_PRODUCT_CRITERION 0
48 #if SBA_PRINT_REDUCTION_STEPS
49 VAR long sba_reduction_steps;
50 VAR long sba_interreduction_steps;
52 #if SBA_PRINT_OPERATIONS
53 VAR long sba_operations;
54 VAR long sba_interreduction_operations;
86 unsigned long not_sev = ~L->sev;
91 const unsigned long* sevT=strat->
sevT;
103 if (
j > strat->
tl)
return o;
123 if (
j > strat->
tl)
return o;
141 unsigned long not_sev = ~L->sev;
146 const unsigned long* sevT=strat->
sevT;
147 number rest, orest,
mult;
158 if (
j > strat->
tl)
return o;
159 #if defined(PDEBUG) || defined(PDIV_DEBUG)
188 if (
j > strat->
tl)
return o;
189 #if defined(PDEBUG) || defined(PDIV_DEBUG)
218 unsigned long not_sev = ~L->sev;
222 const unsigned long* sevT=strat->
sevT;
235 if (
j > strat->
tl)
return -1;
236 #if defined(PDEBUG) || defined(PDIV_DEBUG)
243 if (!(sevT[
j] & not_sev) &&
257 if (
j > strat->
tl)
return -1;
258 #if defined(PDEBUG) || defined(PDIV_DEBUG)
264 if (!(sevT[
j] & not_sev) &&
282 if (
j > strat->
tl)
return -1;
283 #if defined(PDEBUG) || defined(PDIV_DEBUG)
291 if (!(sevT[
j] & not_sev) &&
305 if (
j > strat->
tl)
return -1;
306 #if defined(PDEBUG) || defined(PDIV_DEBUG)
313 if (!(sevT[
j] & not_sev) &&
328 unsigned long not_sev = ~L->sev;
329 poly
p = L->GetLmCurrRing();
343 ende=
posInS(strat,*max_ind,
p,0)+1;
344 if (ende>(*max_ind)) ende=(*max_ind);
353 if (
j > ende)
return -1;
354 #if defined(PDEBUG) || defined(PDIV_DEBUG)
362 if ( !(strat->
sevS[
j] & not_sev) &&
376 if (
j > ende)
return -1;
377 #if defined(PDEBUG) || defined(PDIV_DEBUG)
384 if ( !(strat->
sevS[
j] & not_sev) &&
397 unsigned long not_sev = ~L->sev;
398 poly
p = L->GetLmCurrRing();
411 if (
j > ende)
return -1;
412 #if defined(PDEBUG) || defined(PDIV_DEBUG)
420 if ( !(strat->
sevS[
j] & not_sev) &&
434 if (
j > ende)
return -1;
435 #if defined(PDEBUG) || defined(PDIV_DEBUG)
442 if ( !(strat->
sevS[
j] & not_sev) &&
461 poly zeroPoly =
NULL;
462 unsigned long a = (
unsigned long)
pGetCoeff(
p);
465 int a_ind2 =
ind2(a);
469 for (
int i = 1;
i <= leadRing->N;
i++)
478 poly lead_mult =
p_ISet(1, tailRing);
479 if (
n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
481 int too_much = k_ind2 + a_ind2 -
n_GetChar(leadRing->cf);
483 zeroPoly =
p_ISet(a, tailRing);
484 for (
int i = 1;
i <= leadRing->N;
i++)
491 while ( (0 <
ind2(s_exp)) && (
ind2(s_exp) <= too_much) )
493 too_much = too_much -
ind2(s_exp);
497 for (
int j = 1;
j <= s_exp;
j++)
514 p_Setm(lead_mult, tailRing);
515 zeroPoly =
p_Mult_mm(zeroPoly, lead_mult, tailRing);
517 for (
int i = 1;
i <= leadRing->N;
i++)
570 if (
h->IsNull())
return 0;
571 if (strat->
tl<0)
return 1;
582 long reddeg =
h->GetpFDeg();
584 h->SetShortExpVector();
615 if (
h->GetLmTailRing() ==
NULL)
661 if (
h->GetLmTailRing() ==
NULL)
670 h->SetShortExpVector();
675 (strat->
Ll >= 0) && ((d > reddeg) || (pass > strat->
LazyPass)))
680 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
693 if (d >= (
long)strat->
tailRing->bitmask)
695 if (
h->pTotalDeg() >= (long)strat->
tailRing->bitmask)
700 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
717 if (
h->IsNull())
return 0;
718 if (strat->
tl<0)
return 1;
729 long reddeg =
h->GetpFDeg();
731 h->SetShortExpVector();
753 if (
h->GetLmTailRing() ==
NULL)
766 if (
h->GetLmTailRing() ==
NULL)
772 h->SetShortExpVector();
777 (strat->
Ll >= 0) && ((d > reddeg) || (pass > strat->
LazyPass)))
782 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
795 if (d >= (
long)strat->
tailRing->bitmask)
797 if (
h->pTotalDeg() >= (long)strat->
tailRing->bitmask)
802 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
824 if (strat->
tl<0)
return 1;
830 unsigned long not_sev;
835 h->SetShortExpVector();
837 h_p =
h->GetLmTailRing();
844 li = strat->
T[
j].pLength;
845 if (li<=0) li=strat->
T[
j].GetpLength();
862 if ((strat->
T[
i].pLength < li)
870 li = strat->
T[
i].pLength;
871 if (li<=0) li=strat->
T[
i].GetpLength();
892 #if SBA_PRINT_REDUCTION_STEPS
893 sba_interreduction_steps++;
895 #if SBA_PRINT_OPERATIONS
896 sba_interreduction_operations +=
pLength(strat->
T[ii].p);
908 h_p =
h->GetLmTailRing();
914 h->SetShortExpVector();
926 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
935 Print(
" lazy: -> L%d\n",at);
948 assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
950 Red->HeadNormalize();
984 if (strat->
tl<0)
return 1;
990 PrintS(
"------- IN REDSIG -------\n");
997 PrintS(
"---------------------------\n");
1000 int i,
j,at,pass, ii;
1003 unsigned long not_sev;
1008 h->SetShortExpVector();
1010 h_p =
h->GetLmTailRing();
1020 li = strat->
T[
j].pLength;
1021 if (li<=0) li=strat->
T[
j].GetpLength();
1038 if ((strat->
T[
i].pLength < li)
1046 li = strat->
T[
i].pLength;
1047 if (li<=0) li=strat->
T[
i].GetpLength();
1069 Print(
"BEFORE REDUCTION WITH %d:\n",ii);
1070 PrintS(
"--------------------------------\n");
1077 PrintS(
"--------------------------------\n");
1078 printf(
"INDEX OF REDUCER T: %d\n",ii);
1081 #if SBA_PRINT_REDUCTION_STEPS
1083 sba_reduction_steps++;
1085 #if SBA_PRINT_OPERATIONS
1087 sba_operations +=
pLength(strat->
T[ii].p);
1094 Print(
"SigSAFE: %d\n",sigSafe);
1109 h_p =
h->GetLmTailRing();
1115 h->SetShortExpVector();
1127 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1128 if (at <= strat->Ll)
1130 int dummy=strat->
sl;
1138 Print(
" lazy: -> L%d\n",at);
1162 beforeredsig =
pCopy(
h->sig);
1164 if (strat->
tl<0)
return 1;
1170 Print(
"------- IN REDSIG -------\n");
1177 Print(
"---------------------------\n");
1180 int i,
j,at,pass, ii;
1183 unsigned long not_sev;
1188 h->SetShortExpVector();
1190 h_p =
h->GetLmTailRing();
1212 h->i_r1 = strat->
tl;
1215 if (
h->GetLmTailRing() ==
NULL)
1222 if(
pLtCmp(beforeredsig,
h->sig) == 1)
1245 li = strat->
T[
j].pLength;
1246 if (li<=0) li=strat->
T[
j].GetpLength();
1262 if ((strat->
T[
i].pLength < li)
1270 li = strat->
T[
i].pLength;
1271 if (li<=0) li=strat->
T[
i].GetpLength();
1293 Print(
"BEFORE REDUCTION WITH %d:\n",ii);
1294 Print(
"--------------------------------\n");
1301 Print(
"--------------------------------\n");
1302 printf(
"INDEX OF REDUCER T: %d\n",ii);
1330 #if SBA_PRINT_REDUCTION_STEPS
1332 sba_reduction_steps++;
1334 #if SBA_PRINT_OPERATIONS
1336 sba_operations +=
pLength(strat->
T[ii].p);
1343 Print(
"SigSAFE: %d\n",sigSafe);
1358 h_p =
h->GetLmTailRing();
1364 h->SetShortExpVector();
1376 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1377 if (at <= strat->Ll)
1379 int dummy=strat->
sl;
1387 Print(
" lazy: -> L%d\n",at);
1400 #define REDTAIL_CANONICALIZE 100
1404 p =
h = L->GetLmTailRing();
1406 return L->GetLmCurrRing();
1414 Ln.sevSig = L->sevSig;
1415 Ln.pLength = L->GetpLength() - 1;
1430 Ln.SetShortExpVector();
1436 With = &(strat->
T[
j]);
1441 if (With ==
NULL)
break;
1465 #if SBA_PRINT_REDUCTION_STEPS
1467 sba_reduction_steps++;
1469 #if SBA_PRINT_OPERATIONS
1471 sba_operations +=
pLength(With->p);
1481 pNext(
h) = Ln.LmExtractAndIter();
1484 }
while (!Ln.IsNull());
1487 if (Ln.IsNull())
goto all_done;
1488 if (! withT) With_s.Init(
currRing);
1495 pNext(
h) = Ln.LmExtractAndIter();
1512 return L->GetLmCurrRing();
1521 if (strat->
tl<0)
return 1;
1526 long reddeg =
h->GetpFDeg();
1528 unsigned long not_sev;
1530 h->SetShortExpVector();
1531 poly h_p =
h->GetLmTailRing();
1536 if (
j < 0)
return 1;
1538 li = strat->
T[
j].pLength;
1539 if (li<=0) li=strat->
T[
j].GetpLength();
1557 if ((strat->
T[
i].pLength < li)
1565 li = strat->
T[
i].pLength;
1566 if (li<=0) li=strat->
T[
i].GetpLength();
1588 #if SBA_PRINT_REDUCTION_STEPS
1589 sba_interreduction_steps++;
1591 #if SBA_PRINT_OPERATIONS
1592 sba_interreduction_operations +=
pLength(strat->
T[ii].p);
1604 h_p=
h->GetLmTailRing();
1611 h->SetShortExpVector();
1617 (strat->
Ll >= 0) && ((d > reddeg) || (pass > strat->
LazyPass)))
1620 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1621 if (at <= strat->Ll)
1624 int dummy=strat->
sl;
1636 else if (d != reddeg)
1638 if (d>=(
long)strat->
tailRing->bitmask)
1640 if (
h->pTotalDeg() >= (long)strat->
tailRing->bitmask)
1645 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1666 if (strat->
tl<0)
return 1;
1670 int i,
j,at,pass,ei, ii, h_d;
1671 unsigned long not_sev;
1675 d = reddeg =
h->GetpFDeg() +
h->ecart;
1676 h->SetShortExpVector();
1678 h_p =
h->GetLmTailRing();
1685 if (
j < 0)
return 1;
1687 ei = strat->
T[
j].ecart;
1688 li = strat->
T[
j].pLength;
1689 if (li<=0) li=strat->
T[
j].GetpLength();
1707 if ((((strat->
T[
i].ecart < ei) && (ei>
h->ecart))
1708 || ((strat->
T[
i].ecart <=
h->ecart) && (strat->
T[
i].pLength < li)))
1716 ei = strat->
T[
i].ecart;
1717 li = strat->
T[
i].pLength;
1718 if (li<=0) li=strat->
T[
i].GetpLength();
1737 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1755 Print(
"\nwith T[%d]:",ii);
1762 #if SBA_PRINT_REDUCTION_STEPS
1763 sba_interreduction_steps++;
1765 #if SBA_PRINT_OPERATIONS
1766 sba_interreduction_operations +=
pLength(strat->
T[ii].p);
1792 else if (
h->t_p!=
NULL)
1801 h->SetShortExpVector();
1803 h_d =
h->SetpFDeg();
1808 h->ecart = d-h_d+ei-
h->ecart;
1822 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1823 if (at <= strat->Ll)
1825 int dummy=strat->
sl;
1831 Print(
" degree jumped: -> L%d\n",at);
1837 else if (d > reddeg)
1839 if (d>=(
long)strat->
tailRing->bitmask)
1841 if (
h->pTotalDeg()+
h->ecart >= (long)strat->
tailRing->bitmask)
1846 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
1868 #define REDNF_CANONICALIZE 60
1879 P.SetShortExpVector();
1985 P.SetShortExpVector();
2034 P.SetShortExpVector();
2115 P.SetShortExpVector();
2143 P.SetShortExpVector();
2182 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2205 withT = ! strat->
homog;
2210 #ifdef HAVE_TAIL_RING
2226 while (strat->
Ll >= 0)
2233 while (strat->
Ll >= 0)
2246 while ((strat->
Ll >= 0)
2247 && (strat->
L[strat->
Ll].p1!=
NULL) && (strat->
L[strat->
Ll].p2!=
NULL)
2252 if (strat->
Ll<0)
break;
2257 strat->
P = strat->
L[strat->
Ll];
2287 else if (strat->
P.p1 ==
NULL)
2289 if (strat->
minim > 0)
2295 if ((strat->
P.p ==
NULL) && (strat->
P.t_p ==
NULL))
2303 &olddeg,&reduc,strat, red_result);
2306 red_result = strat->red(&strat->P,strat);
2316 if (red_result == 1)
2319 strat->
P.GetP(strat->
lmBin);
2328 int pos=
posInS(strat,strat->
sl,strat->
P.p,strat->
P.ecart);
2339 strat->
P.pCleardenom();
2344 strat->
P.pCleardenom();
2348 strat->
P.pCleardenom();
2357 strat->
P.p =
redtailBba(&(strat->
P),pos-1,strat, withT);
2369 if (strat->
minim==1)
2376 strat->
M->m[minimcnt]=strat->
P.p2;
2380 pNext(strat->
M->m[minimcnt])
2396 strat->
enterS(strat->
P, pos, strat, strat->
tl);
2411 if (hilb!=
NULL)
khCheck(
Q,
w,hilb,hilbeledeg,hilbcount,strat);
2419 if (strat->
s_poly(strat))
2424 int pos=
posInS(strat,strat->
sl,strat->
P.p,strat->
P.ecart);
2430 strat->
enterS(strat->
P, pos, strat, strat->
tl);
2434 else if (strat->
P.p1 ==
NULL && strat->
minim > 0)
2440 memset(&(strat->
P), 0,
sizeof(strat->
P));
2476 #ifdef HAVE_TAIL_RING
2498 for(
int i = 0;
i<=strat->
sl;
i++)
2533 return (strat->
Shdl);
2545 #if SBA_PRINT_ZERO_REDUCTIONS
2546 long zeroreductions = 0;
2548 #if SBA_PRINT_PRODUCT_CRITERION
2549 long product_criterion = 0;
2551 #if SBA_PRINT_SIZE_G
2553 int size_g_non_red = 0;
2555 #if SBA_PRINT_SIZE_SYZ
2559 #if SBA_PRINT_REDUCTION_STEPS
2560 sba_reduction_steps = 0;
2561 sba_interreduction_steps = 0;
2563 #if SBA_PRINT_OPERATIONS
2565 sba_interreduction_operations = 0;
2569 ring sRing, currRingOld;
2574 if (sRing!=currRingOld)
2593 dummy =
pCopy(F->m[0]);
2595 F->m[
i] = F->m[
i+1];
2616 dummy =
pCopy(F->m[0]);
2618 F->m[
i] = F->m[
i+1];
2636 for (
int i=0;
i<
sort->length();++
i)
2637 F->m[
i] = F1->m[(*
sort)[
i]-1];
2651 F->m[
j] = F->m[
j-1];
2669 printf(
"SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2671 printf(
"ordSgn = %d\n",
currRing->OrdSgn);
2674 int srmax,lrmax, red_result = 1;
2676 int hilbeledeg=1,hilbcount=0,minimcnt=0;
2690 reduc = olddeg = lrmax = 0;
2703 #ifdef HAVE_TAIL_RING
2721 strat->
enterS(strat->
L[strat->
Ll-(
i)], strat->
sl+1, strat, strat->
tl);
2731 while (strat->
Ll >= 0)
2733 if (strat->
Ll > lrmax) lrmax =strat->
Ll;
2763 f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2764 lrmax, reduc,
Q,
w, hilb );
2774 strat->
P = strat->
L[strat->
Ll];
2780 if (!strat->
rewCrit2(strat->
P.sig, ~strat->
P.sevSig, strat->
P.GetLmCurrRing(), strat, strat->
P.checked+1))
2784 PrintS(
"SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2785 PrintS(
"-------------------------------------------------\n");
2790 PrintS(
"-------------------------------------------------\n");
2825 else if (strat->
P.p1 ==
NULL)
2827 if (strat->
minim > 0)
2833 if (strat->
P.p ==
NULL && strat->
P.t_p ==
NULL)
2841 PrintS(
"Poly before red: ");
2845 #if SBA_PRODUCT_CRITERION
2846 if (strat->
P.prod_crit)
2848 #if SBA_PRINT_PRODUCT_CRITERION
2849 product_criterion++;
2851 int pos =
posInSyz(strat, strat->
P.sig);
2858 red_result = strat->
red(&strat->
P,strat);
2861 red_result = strat->
red(&strat->
P,strat);
2877 strat->
P.p =
pNeg(strat->
P.p);
2878 strat->
P.sig =
pNeg(strat->
P.sig);
2881 if(strat->
P.sig !=
NULL)
2883 if(strat->
P.p !=
NULL)
2890 red_result =
redRing(&strat->
P,strat);
2895 strat->
P.sig =
NULL;
2899 strat->
enterS(strat->
P, 0, strat, strat->
tl);
2915 if (red_result != 0)
2917 PrintS(
"Poly after red: ");
2919 pWrite(strat->
P.GetLmCurrRing());
2921 printf(
"%d\n",red_result);
2926 if(strat->
P.p !=
NULL)
2928 &olddeg,&reduc,strat, red_result);
2930 message((strat->honey ? strat->P.ecart : 0),
2931 &olddeg,&reduc,strat, red_result);
2939 if (red_result == 1)
2942 strat->
P.GetP(strat->
lmBin);
2946 (strat->
P).FDeg = (strat->
P).pFDeg();
2958 int pos = strat->
sl+1;
2966 beforetailred =
pCopy(strat->
P.sig);
2972 strat->
P.p =
redtailSba(&(strat->
P),pos-1,strat, withT);
2980 strat->
P.pCleardenom();
2983 strat->
P.p =
redtailSba(&(strat->
P),pos-1,strat, withT);
2984 strat->
P.pCleardenom();
2991 strat->
P.p =
redtailSba(&(strat->
P),pos-1,strat, withT);
3000 strat->
enterS(strat->
P, 0, strat, strat->
tl);
3006 if(strat->
P.sig ==
NULL ||
pLtCmp(beforetailred,strat->
P.sig) == 1)
3010 red_result =
redRing(&strat->
P,strat);
3019 strat->
enterS(strat->
P, 0, strat, strat->
tl);
3025 if(strat->
P.p ==
NULL)
3026 goto case_when_red_result_changed;
3032 for (
int jj = 0; jj<strat->
tl+1; jj++)
3036 strat->
T[jj].is_sigsafe =
FALSE;
3042 for (
int jj = 0; jj<strat->
tl+1; jj++)
3044 strat->
T[jj].is_sigsafe =
FALSE;
3054 if (strat->
minim==1)
3061 strat->
M->m[minimcnt]=strat->
P.p2;
3065 pNext(strat->
M->m[minimcnt])
3075 strat->
T[strat->
tl].is_sigsafe =
FALSE;
3089 strat->
enterS(strat->
P, pos, strat, strat->
tl);
3093 for (
int tk=0; tk<strat->
sl+1; tk++)
3114 for(
int ps=0;ps<strat->
sl+1;ps++)
3122 (strat->
syzmax)*
sizeof(
unsigned long),
3124 *
sizeof(
unsigned long));
3156 unsigned max_cmp =
IDELEMS(F);
3166 for (
int i=0;
i<strat->
sl; ++
i)
3183 for (
unsigned i=cmp+1;
i<=max_cmp; ++
i)
3186 for (
int j=0;
j<strat->
sl; ++
j)
3224 printf(
"---------------------------\n");
3225 Print(
" %d. ELEMENT ADDED TO GCURR:\n",strat->
sl+1);
3248 if (hilb!=
NULL)
khCheck(
Q,
w,hilb,hilbeledeg,hilbcount,strat);
3251 if (strat->
sl>srmax) srmax = strat->
sl;
3255 case_when_red_result_changed:
3263 #if SBA_PRINT_ZERO_REDUCTIONS
3272 int pos =
posInSyz(strat, strat->
P.sig);
3276 Print(
"ADDING STUFF TO SYZ : ");
3289 memset(&(strat->
P), 0,
sizeof(strat->
P));
3295 printf(
"\nSigDrop!\n");
3297 printf(
"\nEnded with no SigDrop\n");
3303 if(strat->
P.sig !=
NULL)
3307 memset(&(strat->
P), 0,
sizeof(strat->
P));
3342 #ifdef HAVE_TAIL_RING
3358 #if SBA_PRINT_SIZE_SYZ
3360 size_syz = strat->
syzl;
3373 #if SBA_PRINT_SIZE_G
3388 for(;
k>=0 && (strat->
L[
k].p1 !=
NULL || strat->
L[
k].p2 !=
NULL);
k--)
3398 for(;
k>=0 && strat->
L[
k].p1 ==
NULL && strat->
L[
k].p2 ==
NULL;
k--)
3401 strat->
enterS(strat->
L[
k], strat->
sl+1, strat, strat->
tl);
3409 for(
k=strat->
sl;
k>=0;
k--)
3442 #if SBA_PRINT_SIZE_G
3446 printf(
"SIZE OF SHDL: %d\n",
IDELEMS(strat->
Shdl));
3450 printf(
" %d. ",oo+1);
3455 #if SBA_PRINT_ZERO_REDUCTIONS
3456 printf(
"----------------------------------------------------------\n");
3457 printf(
"ZERO REDUCTIONS: %ld\n",zeroreductions);
3460 #if SBA_PRINT_REDUCTION_STEPS
3461 printf(
"----------------------------------------------------------\n");
3462 printf(
"S-REDUCTIONS: %ld\n",sba_reduction_steps);
3464 #if SBA_PRINT_OPERATIONS
3465 printf(
"OPERATIONS: %ld\n",sba_operations);
3467 #if SBA_PRINT_REDUCTION_STEPS
3468 printf(
"- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3469 printf(
"INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3471 #if SBA_PRINT_OPERATIONS
3472 printf(
"INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3474 #if SBA_PRINT_REDUCTION_STEPS
3475 printf(
"- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3476 printf(
"ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3477 sba_interreduction_steps = 0;
3478 sba_reduction_steps = 0;
3480 #if SBA_PRINT_OPERATIONS
3481 printf(
"ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3482 sba_interreduction_operations = 0;
3485 #if SBA_PRINT_SIZE_G
3486 printf(
"----------------------------------------------------------\n");
3487 printf(
"SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3491 #if SBA_PRINT_SIZE_SYZ
3492 printf(
"SIZE OF SYZ: %ld\n",size_syz);
3493 printf(
"----------------------------------------------------------\n");
3496 #if SBA_PRINT_PRODUCT_CRITERION
3497 printf(
"PRODUCT CRITERIA: %ld\n",product_criterion);
3498 product_criterion = 0;
3500 return (strat->
Shdl);
3503 poly
kNF2 (ideal F,ideal
Q,poly q,
kStrategy strat,
int lazyReduce)
3524 #ifdef HAVE_SHIFTBBA
3575 #ifdef HAVE_SHIFTBBA
3666 ideal
kNF2 (ideal F,ideal
Q,ideal q,
kStrategy strat,
int lazyReduce)
3691 #ifdef HAVE_SHIFTBBA
3744 #ifdef HAVE_SHIFTBBA
3848 void f5c (
kStrategy strat,
int& olddeg,
int& minimcnt,
int& hilbeledeg,
3849 int& hilbcount,
int& srmax,
int& lrmax,
int& reduc, ideal
Q,
3852 int Ll_old, red_result = 1;
3858 reduc = olddeg = lrmax = 0;
3863 while (strat->
tl >= 0)
3865 if(!strat->
T[strat->
tl].is_redundant)
3868 h.p = strat->
T[strat->
tl].p;
3869 h.tailRing = strat->
T[strat->
tl].tailRing;
3870 h.t_p = strat->
T[strat->
tl].t_p;
3909 while (strat->
Ll>Ll_old)
3911 strat->
P = strat->
L[strat->
Ll];
3915 PrintS(
"NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
3916 PrintS(
"-------------------------------------------------\n");
3920 printf(
"%d\n",strat->
tl);
3921 PrintS(
"-------------------------------------------------\n");
3954 else if (strat->
P.p1 ==
NULL)
3956 if (strat->
minim > 0)
3963 if (strat->
P.p ==
NULL && strat->
P.t_p ==
NULL)
3971 &olddeg,&reduc,strat, red_result);
3974 PrintS(
"Poly before red: ");
3978 red_result = strat->red2(&strat->P,strat);
3988 if (red_result == 1)
3991 strat->
P.GetP(strat->
lmBin);
4002 pos =
posInS(strat,strat->
sl,strat->
P.p,strat->
P.ecart);
4006 pos =
posInS(strat,strat->
sl,strat->
P.p,strat->
P.ecart);
4015 strat->
P.pCleardenom();
4018 strat->
P.p =
redtailBba(&(strat->
P),pos-1,strat, withT);
4019 strat->
P.pCleardenom();
4026 strat->
P.p =
redtailBba(&(strat->
P),pos-1,strat, withT);
4036 if (strat->
minim==1)
4043 strat->
M->m[minimcnt]=strat->
P.p2;
4047 pNext(strat->
M->m[minimcnt])
4060 strat->
enterS(strat->
P, pos, strat, strat->
tl);
4063 PrintS(
"ELEMENT ADDED TO GCURR DURING INTERRED: ");
4067 if (hilb!=
NULL)
khCheck(
Q,
w,hilb,hilbeledeg,hilbcount,strat);
4071 if (strat->
sl>srmax) srmax = strat->
sl;
4087 memset(&(strat->
P), 0,
sizeof(strat->
P));
4091 while (cc<strat->tl+1)
4093 strat->
T[cc].sig =
pOne();
4096 strat->
sig[cc] = strat->
T[cc].sig;
4097 strat->
sevSig[cc] = strat->
T[cc].sevSig;
4098 strat->
T[cc].is_sigsafe =
TRUE;
4106 for (
int cd=strat->
Ll;
cd>=0;
cd--)
4114 printf(
"\nAfter f5c sorting\n");
4115 for(
int i=0;
i<=strat->
sl;
i++)
4121 PrintS(
"------------------- STRAT S ---------------------\n");
4123 while (cc<strat->tl+1)
4127 printf(
"- - - - - -\n");
4130 PrintS(
"-------------------------------------------------\n");
4131 PrintS(
"------------------- STRAT T ---------------------\n");
4133 while (cc<strat->tl+1)
4137 printf(
"- - - - - -\n");
4140 PrintS(
"-------------------------------------------------\n");
4141 PrintS(
"------------------- STRAT L ---------------------\n");
4143 while (cc<strat->Ll+1)
4149 printf(
"- - - - - -\n");
4152 PrintS(
"-------------------------------------------------\n");
4153 printf(
"F5C DONE\nSTRAT SL: %d -- %d\n",strat->
sl, strat->
currIdx);
4160 #ifdef HAVE_SHIFTBBA
4167 int hilbeledeg=1,hilbcount=0,minimcnt=0;
4195 #ifdef HAVE_TAIL_RING
4205 while (strat->
Ll >= 0)
4220 while ((strat->
Ll >= 0)
4221 && (strat->
L[strat->
Ll].p1!=
NULL) && (strat->
L[strat->
Ll].p2!=
NULL)
4226 if (strat->
Ll<0)
break;
4230 strat->
P = strat->
L[strat->
Ll];
4253 else if (strat->
P.p1 ==
NULL)
4255 if (strat->
minim > 0)
4261 if (strat->
P.p ==
NULL && strat->
P.t_p ==
NULL)
4269 &olddeg,&reduc,strat, red_result);
4272 red_result = strat->red(&strat->P,strat);
4277 if (red_result == 1)
4280 strat->
P.GetP(strat->
lmBin);
4289 int pos=
posInS(strat,strat->
sl,strat->
P.p,strat->
P.ecart);
4297 strat->
P.pCleardenom();
4300 strat->
P.p =
redtailBba(&(strat->
P),pos-1,strat, withT);
4301 strat->
P.pCleardenom();
4312 strat->
P.p =
redtailBba(&(strat->
P),pos-1,strat, withT);
4327 if (strat->
minim==1)
4334 strat->
M->m[minimcnt]=strat->
P.p2;
4338 pNext(strat->
M->m[minimcnt])
4352 strat->
enterS(strat->
P, pos, strat, strat->
tl);
4357 if (hilb!=
NULL)
khCheck(
Q,
w,hilb,hilbeledeg,hilbcount,strat);
4365 if (strat->
s_poly(strat))
4370 int pos=
posInS(strat,strat->
sl,strat->
P.p,strat->
P.ecart);
4373 strat->
enterS(strat->
P, pos, strat, strat->
tl);
4379 else if (strat->
P.p1 ==
NULL && strat->
minim > 0)
4384 memset(&(strat->
P), 0,
sizeof(strat->
P));
4394 for (
int k = 0;
k <= strat->
sl; ++
k)
4397 for (
int j = 0;
j<=strat->
tl; ++
j)
4404 if (
pLmCmp(strat->
T[
j].p, strat->
S[
k]) != 0) {
4422 #ifdef HAVE_TAIL_RING
4429 WarnS(
"reduction with S is not yet supported by Letterplace");
4457 return (strat->
Shdl);
4461 ideal
freegb(ideal F, ideal
Q)
4487 if (
h->IsNull())
return 0;
4495 d =
h->GetpFDeg() +
h->ecart;
4498 h->SetShortExpVector();
4504 h->SetDegStuffReturnLDeg(strat->
LDegLast);
4509 strat->
T[
j].pNorm();
4535 h->SetShortExpVector();
4548 h->SetDegStuffReturnLDeg(strat->
LDegLast);
4558 if (strat->
T[
j].ecart <=
h->ecart)
4559 h->ecart = d -
h->GetpFDeg();
4561 h->ecart = d -
h->GetpFDeg() + strat->
T[
j].ecart -
h->ecart;
4563 d =
h->GetpFDeg() +
h->ecart;
4566 d =
h->SetDegStuffReturnLDeg(strat->
LDegLast);
4575 && ((d >= reddeg) || (pass > strat->
LazyPass)))
4580 at = strat->
posInL(strat->
L,strat->
Ll,
h,strat);
4581 if (at <= strat->Ll)
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
void kStratInitChangeTailRing(kStrategy strat)
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
static poly p_LmDeleteAndNext(poly p, const ring r)
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
void initBuchMoraCrit(kStrategy strat)
#define pGetComp(p)
Component.
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
void pNorm(poly p, const ring R=currRing)
void cleanT(kStrategy strat)
static BOOLEAN rIsLPRing(const ring r)
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
#define SBA_INTERRED_START
#define idDelete(H)
delete an ideal
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
void rChangeCurrRing(ring r)
#define TEST_OPT_DEGBOUND
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
#define REDTAIL_CANONICALIZE
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
void initBbaShift(kStrategy strat)
void pEnlargeSet(poly **p, int l, int increment)
static poly p_Mult_mm(poly p, poly m, const ring r)
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
void updateResult(ideal r, ideal Q, kStrategy strat)
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
static BOOLEAN length(leftv result, leftv arg)
long ind_fact_2(long arg)
#define TEST_OPT_CONTENTSB
#define __p_GetComp(p, r)
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
void initSbaCrit(kStrategy strat)
const poly kBucketGetLm(kBucket_pt bucket)
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, intvec *hilb)
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
int posInSyz(const kStrategy strat, poly sig)
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
#define p_LmEqual(p1, p2, r)
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
static unsigned pLength(poly a)
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
static void p_SetExpV(poly p, int *ev, const ring r)
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
static poly p_Copy(poly p, const ring r)
returns a copy of p
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
#define TEST_OPT_INTSTRATEGY
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
void kBucketDestroy(kBucket_pt *bucket_pt)
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
int redRing(LObject *h, kStrategy strat)
char posInLDependsOnLength
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
CanonicalForm cd(bCommonDen(FF))
#define TEST_OPT_NOT_BUCKETS
void initEcartNormal(TObject *h)
void PrintS(const char *s)
void enterTShift(LObject p, kStrategy strat, int atT)
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
void kBucketInit(kBucket_pt bucket, poly lm, int length)
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static BOOLEAN rField_is_Ring(const ring r)
void completeReduce(kStrategy strat, BOOLEAN withT)
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
KINLINE poly kNoetherTail()
void exitBuchMora(kStrategy strat)
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start)
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
void initBuchMora(ideal F, ideal Q, kStrategy strat)
void enterSyz(LObject &p, kStrategy strat, int atT)
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
int posInLF5CRing(const LSet set, int start, const int length, LObject *p, const kStrategy)
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
void initBuchMoraPos(kStrategy strat)
static void p_GetExpV(poly p, int *ev, const ring r)
static int p_LmCmp(poly p, poly q, const ring r)
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR)
void messageStat(int hilbcount, kStrategy strat)
void initSyzRules(kStrategy strat)
void sort(CFArray &A, int l=0)
quick sort A
void kDebugPrint(kStrategy strat)
void rDelete(ring r)
unconditionally deletes fields in r
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
int redSig(LObject *h, kStrategy strat)
void initBba(kStrategy strat)
void initSbaPos(kStrategy strat)
poly redNFBound(poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
static void p_Delete(poly *p, const ring r)
static poly p_Add_q(poly p, poly q, const ring r)
void postReduceByMonSig(LObject *h, kStrategy strat)
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
static FORCE_INLINE number n_EucNorm(number a, const coeffs r)
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start)
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
void initBuchMoraPosRing(kStrategy strat)
void rWrite(ring r, BOOLEAN details)
ideal rightgb(ideal F, ideal Q)
static int si_max(const int a, const int b)
static CanonicalForm bound(const CFMatrix &M)
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
pShallowCopyDeleteProc p_shallow_copy_delete
KINLINE poly redtailBbaBound(poly p, int pos, kStrategy strat, int bound, BOOLEAN normalize)
int redRing_Z(LObject *h, kStrategy strat)
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
void Werror(const char *fmt,...)
ideal idInit(int idsize, int rank)
initialise an ideal / module
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
void WerrorS(const char *s)
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:...
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
#define omRealloc0Size(addr, o_size, size)
char completeReduce_retry
static void p_Setm(poly p, const ring r)
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
void cancelunit(LObject *L, BOOLEAN inNF)
#define TEST_OPT_REDTHROUGH
void initSba(ideal F, kStrategy strat)
#define REDNF_CANONICALIZE
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
void messageStatSBA(int hilbcount, kStrategy strat)
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
int redLazy(LObject *h, kStrategy strat)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
void deleteInL(LSet set, int *length, int j, kStrategy strat)
void(* initEcart)(TObject *L)
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
int(* red)(LObject *L, kStrategy strat)
void initEcartBBA(TObject *h)
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
#define pCopy(p)
return a copy of the poly
#define SI_RESTORE_OPT1(A)
int(* posInT)(const TSet T, const int tl, LObject &h)
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
static poly p_Mult_q(poly p, poly q, const ring r)
void deleteInS(int i, kStrategy strat)
static void kDeleteLcm(LObject *P)
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
int redFirstShift(LObject *h, kStrategy strat)
ideal kInterRed(ideal F, ideal Q)
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
static BOOLEAN rField_is_Z(const ring r)
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
unsigned long p_GetShortExpVector(const poly p, const ring r)
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
void exitSba(kStrategy strat)
int redHoney(LObject *h, kStrategy strat)
static void nc_kBucketPolyRed_NF(kBucket_pt b, poly p, number *c)
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
void enterT(LObject &p, kStrategy strat, int atT)
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
int redSigRing(LObject *h, kStrategy strat)
ideal freegb(ideal F, ideal Q)
int redHomog(LObject *h, kStrategy strat)
void initS(ideal F, ideal Q, kStrategy strat)