12 #define BUCHBERGER_ALG //we use the improved Buchberger alg.
24 #define INVEPS_SMALL_IN_FRACTAL //to choose the small invers of epsilon
25 #define INVEPS_SMALL_IN_MPERTVECTOR //to choose the small invers of epsilon
26 #define INVEPS_SMALL_IN_TRAN //to choose the small invers of epsilon
28 #define FIRST_STEP_FRACTAL // to define the first step of the fractal
86 #include <sys/types.h>
111 return (
unsigned long*)
omAlloc0(maxnr*
sizeof(
unsigned long));
115 return (
int*)
omAlloc0(maxnr*
sizeof(
int));
135 strat->
S=strat->
Shdl->m;
141 memset(strat->
fromQ,0,i*
sizeof(
int));
147 h.p =
pCopy(Q->m[i]);
168 pos =
posInS(strat,strat->
sl,h.p,h.ecart);
172 strat->
enterS(h,pos,strat, strat->
tl+1);
185 h.p =
pCopy(F->m[i]);
201 pos =
posInS(strat,strat->
sl,h.p,h.ecart);
203 strat->
enterS(h,pos,strat, strat->
tl+1);
253 pos =
posInS(strat->
S,strat->
sl,h.p,h.ecart);
255 strat->
enterS(h,pos,strat, strat->
tl+1);
263 strat->
enterS(h,0,strat, strat->
tl+1);
353 ideal shdl=strat->
Shdl;
362 static void TimeString(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
363 clock_t tlf,clock_t tred, clock_t tnw,
int step)
365 double totm = ((double) (clock() - tinput))/1000000;
366 double ostd,mostd, mif, mstd, mlf, mred, mnw, mxif,mxstd,mxlf,mxred,mxnw,tot;
368 Print(
"\n// total time = %.2f sec", totm);
369 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
370 mostd=((((
double) tostd)/1000000)/totm)*100);
371 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
372 mif=((((
double) tif)/1000000)/totm)*100);
373 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
374 mstd=((((
double) tstd)/1000000)/totm)*100);
375 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
376 mlf=((((
double) tlf)/1000000)/totm)*100);
377 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
378 mred=((((
double) tred)/1000000)/totm)*100);
379 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
380 mnw=((((
double) tnw)/1000000)/totm)*100);
381 PrintS(
"\n Time for the last step:");
382 Print(
"\n// xinfo = %.2f sec = %.2f", ((
double)
xtif)/1000000,
383 mxif=((((
double) xtif)/1000000)/totm)*100);
384 Print(
"\n// xstd = %.2f sec = %.2f", ((
double)
xtstd)/1000000,
385 mxstd=((((
double) xtstd)/1000000)/totm)*100);
386 Print(
"\n// xlift = %.2f sec = %.2f", ((
double)
xtlift)/1000000,
387 mxlf=((((
double) xtlift)/1000000)/totm)*100);
388 Print(
"\n// xired = %.2f sec = %.2f", ((
double)
xtred)/1000000,
389 mxred=((((
double) xtred)/1000000)/totm)*100);
390 Print(
"\n// xnextw= %.2f sec = %.2f", ((
double)
xtnw)/1000000,
391 mxnw=((((
double) xtnw)/1000000)/totm)*100);
393 tot=mostd+mif+mstd+mlf+mred+mnw+mxif+mxstd+mxlf+mxred+mxnw;
394 double res = (double) 100 - tot;
395 Print(
"\n// &%d&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f(%.2f)\\ \\",
396 step, ostd, totm, mostd,mif,mstd,mlf,mred,mnw,mxif,mxstd,mxlf,mxred,mxnw,tot,res,
397 ((((
double)
xtextra)/1000000)/totm)*100);
403 static void TimeStringFractal(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
404 clock_t textra, clock_t tlf,clock_t tred, clock_t tnw)
407 double totm = ((double) (clock() - tinput))/1000000;
408 double ostd, mostd, mif, mstd, mextra, mlf, mred, mnw, tot,
res;
409 Print(
"\n// total time = %.2f sec", totm);
410 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
411 mostd=((((
double) tostd)/1000000)/totm)*100);
412 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
413 mif=((((
double) tif)/1000000)/totm)*100);
414 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
415 mstd=((((
double) tstd)/1000000)/totm)*100);
416 Print(
"\n// xstd = %.2f sec = %.2f", ((
double) textra)/1000000,
417 mextra=((((
double) textra)/1000000)/totm)*100);
418 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
419 mlf=((((
double) tlf)/1000000)/totm)*100);
420 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
421 mred=((((
double) tred)/1000000)/totm)*100);
422 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
423 mnw=((((
double) tnw)/1000000)/totm)*100);
424 tot = mostd+mif+mstd+mextra+mlf+mred+mnw;
425 res = (double) 100.00-tot;
426 Print(
"\n// &%.2f &%.2f&%.2f &%.2f &%.2f &%.2f &%.2f &%.2f &%.2f&%.2f&%.2f\\ \\ ",
427 ostd,totm,mostd,mif,mstd,mextra,mlf,mred,mnw,tot,res);
431 #ifdef CHECK_IDEAL_MWALK
432 static void idString(ideal L,
const char* st)
436 Print(
"\n// ideal %s = ", st);
437 for(i=0; i<nL-1; i++)
445 #if defined(CHECK_IDEAL_MWALK) || defined(ENDWALKS)
446 static void headidString(ideal L,
char* st)
450 Print(
"\n// ideal %s = ", st);
451 for(i=0; i<nL-1; i++)
459 #if defined(CHECK_IDEAL_MWALK) || defined(ENDWALKS)
460 static void idElements(ideal L,
char* st)
463 int *K=(
int *)
omAlloc(nL*
sizeof(
int));
465 Print(
"\n// #monoms of %s = ", st);
477 for(j=i+1; j<nL; j++)
491 Print(
"%d[%d], ", K[i], nsame);
503 Print(
"\n// intvec %s = ", ch);
505 for(
int i=0; i<nV; i++)
507 Print(
"%d, ", (*iv)[i]);
509 Print(
"%d;", (*iv)[nV]);
521 Print(
"%d, ", (*iva)[i]);
523 Print(
"%d) ==> (", (*iva)[nV]);
526 Print(
"%d, ", (*ivb)[i]);
528 Print(
"%d) := (", (*ivb)[nV]);
532 Print(
"%d, ", (*ivc)[i]);
534 Print(
"%d)", (*ivc)[nV]);
541 static inline long gcd(
const long a,
const long b)
543 long r, p0 =
a, p1 =
b;
565 static void cancel(mpz_t zaehler, mpz_t nenner)
570 mpz_gcd(g, zaehler, nenner);
572 mpz_div(zaehler , zaehler, g);
573 mpz_div(nenner , nenner, g);
580 static int isVectorNeg(
intvec* omega)
584 for(i=omega->
length(); i>=0; i--)
602 mpz_init_set_ui(sing_int, 2147483647);
615 mpz_set_si(zvec, (*weight)[i-1]);
616 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
617 mpz_add(zsum, zsum, zmul);
620 wgrad = mpz_get_ui(zsum);
622 if(mpz_cmp(zsum, sing_int)>0)
627 PrintS(
"\n// ** OVERFLOW in \"MwalkInitialForm\": ");
628 mpz_out_str( stdout, 10, zsum);
629 PrintS(
" is greater than 2147483647 (max. integer representation)");
648 int max = 0, maxtemp;
671 mpz_init_set_ui(sing_int, 2147483647);
684 mpz_set_si(zvec, (*weight)[i-1]);
685 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
686 mpz_add(ztmp, ztmp, zmul);
688 mpz_init_set(result, ztmp);
705 mpz_t
max; mpz_init(max);
706 mpz_t maxtmp; mpz_init(maxtmp);
716 if(mpz_cmp(maxtmp, max)>0)
718 mpz_init_set(max, maxtmp);
724 if(mpz_cmp(maxtmp, max)==0)
742 ideal Gomega =
idInit(nG, 1);
744 for(i=nG-1; i>=0; i--)
764 PrintS(
"//** the result may be WRONG, i.e. 0!!\n");
774 for(i=nG-1; i>=0; i--)
810 static inline long Mlcm(
long &i1,
long &i2)
812 long temp =
gcd(i1, i2);
813 return ((i1 / temp)* i2);
826 for(i=n-1; i>=0; i--)
828 result += (*a)[
i] * (*b)[
i];
842 for(i=n-1; i>=0; i--)
844 (*result)[
i] = (*a)[
i] - (*b)[
i];
857 for(i=nR-1; i>=0; i--)
874 for (i=0; i<niv; i++)
876 if ((*u)[i] != (*v)[i])
946 (*ivm)[
i] = (*iv)[
i];
950 (*ivm)[i*nR+i-1] = 1;
967 (*ivm)[
i] = (*iv)[
i];
968 (*ivm)[i+nR] = (*iw)[
i];
972 (*ivm)[i*nR+i-2] = 1;
985 for(i=nR-1; i>=0; i--)
1008 static void checkComplexity(ideal
G,
char* cG)
1013 int i, tmpdeg, maxdeg=0;
1014 number tmpcoeff , maxcoeff=
currRing->cf->nNULL;
1016 for(i=nG-1; i>=0; i--)
1019 if(tmpdeg > maxdeg )
1025 for(i=nG-1; i>=0; i--)
1034 maxcoeff =
nCopy(tmpcoeff);
1040 p =
pNSet(maxcoeff);
1043 Print(
"// max total degree of %s = %d\n",cG, maxdeg);
1044 Print(
"// max coefficient of %s = %s", cG, pStr);
1045 Print(
" which consists of %d digits", (
int)strlen(pStr));
1072 if(pdeg > nV || pdeg <= 0)
1074 WerrorS(
"//** The perturbed degree is wrong!!");
1083 mpz_t *pert_vector = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1088 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1093 int ntemp, maxAi, maxA=0;
1094 for(i=1; i<pdeg; i++)
1096 maxAi = (*ivtarget)[i*nV];
1101 for(j=i*nV+1; j<(i+1)*nV; j++)
1103 ntemp = (*ivtarget)[
j];
1120 mpz_t tot_deg; mpz_init(tot_deg);
1121 mpz_t maxdeg; mpz_init(maxdeg);
1122 mpz_t inveps; mpz_init(inveps);
1125 for(i=nG-1; i>=0; i--)
1128 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1130 mpz_set(tot_deg, maxdeg);
1135 mpz_mul_ui(inveps, tot_deg, maxA);
1136 mpz_add_ui(inveps, inveps, 1);
1140 #ifdef INVEPS_SMALL_IN_MPERTVECTOR
1141 if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
1144 mpz_fdiv_q_ui(inveps, inveps, pdeg);
1149 mpz_out_str(stdout, 10, inveps);
1154 for( i=1; i < pdeg; i++ )
1158 mpz_mul(pert_vector[j], pert_vector[j], inveps);
1159 if((*ivtarget)[i*nV+j]<0)
1161 mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
1165 mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
1171 mpz_set(ztemp, pert_vector[0]);
1174 mpz_gcd(ztemp, ztemp, pert_vector[i]);
1175 if(mpz_cmp_si(ztemp, 1) == 0)
1180 if(mpz_cmp_si(ztemp, 1) != 0)
1184 mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
1192 (* pert_vector1)[
i] = mpz_get_si(pert_vector[i]);
1193 (* pert_vector1)[
i] = 0.1*(* pert_vector1)[
i];
1194 (* pert_vector1)[
i] = floor((* pert_vector1)[i] + 0.5);
1195 if((* pert_vector1)[i] == 0)
1203 delete pert_vector1;
1204 goto CHECK_OVERFLOW;
1213 mpz_set_si(pert_vector[i], (*pert_vector1)[i]);
1220 delete pert_vector1;
1227 mpz_init_set_ui(sing_int, 2147483647);
1232 (*result)[
i] = mpz_get_si(pert_vector[i]);
1233 if(mpz_cmp(pert_vector[i], sing_int)>=0)
1239 PrintS(
"\n// ** OVERFLOW in \"MPertvectors\": ");
1240 mpz_out_str( stdout, 10, pert_vector[i]);
1241 PrintS(
" is greater than 2147483647 (max. integer representation)");
1242 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1250 Print(
"\n// %d element(s) of it is overflow!!", ntrue);
1254 mpz_clear(sing_int);
1289 if(pdeg > nV || pdeg <= 0)
1291 WerrorS(
"//** The perturbed degree is wrong!!");
1296 (*pert_vector)[
i]=(*ivtarget)[
i];
1304 int ntemp, maxAi, maxA=0;
1305 for(i=1; i<pdeg; i++)
1307 maxAi = (*ivtarget)[i*nV];
1308 for(j=i*nV+1; j<(i+1)*nV; j++)
1310 ntemp = (*ivtarget)[
j];
1320 int inveps, tot_deg = 0, maxdeg;
1323 for(i=nG-1; i>=0; i--)
1327 if (maxdeg > tot_deg )
1334 inveps = (tot_deg * maxA) + 1;
1336 #ifdef INVEPS_SMALL_IN_FRACTAL
1338 if(inveps > pdeg && pdeg > 3)
1340 inveps = inveps / pdeg;
1344 PrintS(
"\n// the \"big\" inverse epsilon %d", inveps);
1348 for ( i=1; i < pdeg; i++ )
1352 (*pert_vector)[
j] = inveps*((*pert_vector)[
j]) + (*ivtarget)[i*nV+
j];
1356 int temp = (*pert_vector)[0];
1359 temp =
gcd(temp, (*pert_vector)[i]);
1369 (*pert_vector)[
i] = (*pert_vector)[
i] / temp;
1388 (*ivM)[i*nV +
i] = 1;
1408 (*ivM)[(i+1)*nV - i] = -1;
1419 int nV = ivstart->
length();
1424 (*ivM)[
i] = (*ivstart)[
i];
1428 (*ivM)[i*nV + i-1] = 1;
1439 int nV = ivstart->
length();
1444 (*ivM)[
i] = (*ivstart)[
i];
1452 (*ivM)[(i+1)*nV - i] = -1;
1459 static intvec* MatrixOrderdp(
int nV)
1470 (*ivM)[(i+1)*nV - i] = -1;
1480 for(i=nV-1; i>=0; i--)
1501 int ntemp, maxAi, maxA=0;
1504 maxAi = (*ivtarget)[i*nV];
1509 for(j=i*nV+1; j<(i+1)*nV; j++)
1511 ntemp = (*ivtarget)[
j];
1521 maxA = maxA + maxAi;
1526 mpz_t tot_deg; mpz_init(tot_deg);
1527 mpz_t maxdeg; mpz_init(maxdeg);
1528 mpz_t inveps; mpz_init(inveps);
1531 for(i=nG-1; i>=0; i--)
1534 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1536 mpz_set(tot_deg, maxdeg);
1542 mpz_mul_ui(inveps, tot_deg, maxA);
1543 mpz_add_ui(inveps, inveps, 1);
1546 #ifdef INVEPS_SMALL_IN_FRACTAL
1547 if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
1549 mpz_cdiv_q_ui(inveps, inveps, nV);
1557 mpz_t *ivtemp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
1558 mpz_t *pert_vector=(mpz_t *)
omAlloc(niv*
sizeof(mpz_t));
1560 for(i=0; i < nV; i++)
1562 mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
1563 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1566 mpz_t ztmp; mpz_init(ztmp);
1573 mpz_mul(ztmp, inveps, ivtemp[j]);
1574 if((*ivtarget)[i*nV+j]<0)
1576 mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
1580 mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
1586 mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
1592 mpz_init_set_ui(sing_int, 2147483647);
1599 mpz_set(ztmp, pert_vector[0]);
1600 for(i=0; i<niv; i++)
1602 mpz_gcd(ztmp, ztmp, pert_vector[i]);
1603 if(mpz_cmp_si(ztmp, 1)==0)
1609 for(i=0; i<niv; i++)
1611 mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
1612 (* result)[
i] = mpz_get_si(pert_vector[i]);
1618 (* result1)[
i] = mpz_get_si(pert_vector[i]);
1619 (* result1)[
i] = 0.1*(* result1)[
i];
1620 (* result1)[
i] = floor((* result1)[i] + 0.5);
1621 if((* result1)[i] == 0)
1630 goto CHECK_OVERFLOW;
1641 mpz_set_si(pert_vector[i], (*result1)[i]);
1652 for(i=0; i<niv; i++)
1654 if(mpz_cmp(pert_vector[i], sing_int)>0)
1661 Print(
"\n// Xlev = %d and the %d-th element is", Xnlev, i+1);
1662 PrintS(
"\n// ** OVERFLOW in \"Mfpertvector\": ");
1663 mpz_out_str( stdout, 10, pert_vector[i]);
1664 PrintS(
" is greater than 2147483647 (max. integer representation)");
1665 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1679 mpz_clear(sing_int);
1717 if (result->m[k]!=
NULL)
1758 for(j=
IDELEMS(idLG)-1; j>=0; j--)
1760 F->m[
i] =
pAdd(F->m[i], idLG->m[j]);
1771 static void checkidealCC(ideal G,
char* Ch)
1776 Print(
"\n//** Ideal %s besteht aus %d Polynomen mit ", Ch, nG);
1785 Print(
"%d, ", ntmp);
1789 Print(
" bzw. %d ", ntmp);
1793 Print(
"//** %s besitzt %d Monome.", Ch, nmon);
1800 static void HeadidString(ideal L,
char* st)
1804 Print(
"// The head terms of the ideal %s = ", st);
1817 for(i=iva->
length()-1; i>=0; i--)
1819 if((*iva)[
i] - (*ivb)[
i] != 0)
1841 for(i=1; i < (vec->
length()); i++)
1872 target_weight !=
NULL && G !=
NULL);
1875 int checkRed,
j, kkk, nG =
IDELEMS(G);
1878 mpz_t t_zaehler, t_nenner;
1879 mpz_init(t_zaehler);
1882 mpz_t s_zaehler, s_nenner, temp, MwWd;
1883 mpz_init(s_zaehler);
1890 mpz_set_si(sing_int, 2147483647);
1892 mpz_t sing_int_half;
1893 mpz_init(sing_int_half);
1894 mpz_set_si(sing_int_half, 3*(1073741824/2));
1896 mpz_t deg_w0_p1, deg_d0_p1;
1897 mpz_init(deg_w0_p1);
1898 mpz_init(deg_d0_p1);
1915 intvec* diff_weight =
MivSub(target_weight, curr_weight);
1917 intvec* diff_weight1 =
MivSub(target_weight, curr_weight);
1920 for (j=0; j<nG; j++)
1935 mpz_sub(s_zaehler, deg_w0_p1, MwWd);
1937 if(mpz_cmp(s_zaehler, t_null) != 0)
1940 mpz_sub(s_nenner, MwWd, deg_d0_p1);
1943 if( (mpz_cmp(s_zaehler,t_null) > 0 &&
1944 mpz_cmp(s_nenner, s_zaehler)>=0) ||
1945 (mpz_cmp(s_zaehler, t_null) < 0 &&
1946 mpz_cmp(s_nenner, s_zaehler)<=0))
1949 if (mpz_cmp(s_zaehler, t_null) < 0)
1951 mpz_neg(s_zaehler, s_zaehler);
1952 mpz_neg(s_nenner, s_nenner);
1956 cancel(s_zaehler, s_nenner);
1958 if(mpz_cmp(t_nenner, t_null) != 0)
1960 mpz_mul(sztn, s_zaehler, t_nenner);
1961 mpz_mul(sntz, s_nenner, t_zaehler);
1963 if(mpz_cmp(sztn,sntz) < 0)
1965 mpz_add(t_nenner, t_null, s_nenner);
1966 mpz_add(t_zaehler,t_null, s_zaehler);
1971 mpz_add(t_nenner, t_null, s_nenner);
1972 mpz_add(t_zaehler,t_null, s_zaehler);
1982 mpz_t *
vec=(mpz_t*)
omAlloc(nRing*
sizeof(mpz_t));
1986 if(mpz_cmp(t_nenner, t_null) == 0)
1989 Print(
"\n//MwalkNextWeightCC: t_nenner ist Null!");
1992 diff_weight =
ivCopy(curr_weight);
1997 if(mpz_cmp_si(t_nenner, 1)==0 && mpz_cmp_si(t_zaehler,1)==0)
2000 diff_weight =
ivCopy(target_weight);
2009 gcd_tmp = (*curr_weight)[0];
2011 for (j=1; j<nRing; j++)
2013 gcd_tmp =
gcd(gcd_tmp, (*curr_weight)[j]);
2021 for (j=0; j<nRing; j++)
2023 gcd_tmp =
gcd(gcd_tmp, (*diff_weight)[j]);
2032 for (j=0; j<nRing; j++)
2034 (*curr_weight)[
j] = (*curr_weight)[
j]/gcd_tmp;
2035 (*diff_weight)[
j] = (*diff_weight)[
j]/gcd_tmp;
2040 for (j=0; j<nRing; j++)
2042 mpz_set_si(vec[j], (*diff_weight)[j]);
2047 #ifdef NEXT_VECTORS_CC
2048 Print(
"\n// gcd of the weight vectors (current and target) = %d", gcd_tmp);
2052 PrintS(
"\n// t_zaehler: "); mpz_out_str( stdout, 10, t_zaehler);
2053 PrintS(
", t_nenner: "); mpz_out_str( stdout, 10, t_nenner);
2059 for (j=0; j<nRing; j++)
2061 mpz_set_si(dcw, (*curr_weight)[j]);
2062 mpz_mul(s_nenner, t_nenner, dcw);
2064 if( (*diff_weight)[j]>0)
2066 mpz_mul_ui(s_zaehler, t_zaehler, (*diff_weight)[j]);
2070 mpz_mul_ui(s_zaehler, t_zaehler, -(*diff_weight)[j]);
2071 mpz_neg(s_zaehler, s_zaehler);
2073 mpz_add(sntz, s_nenner, s_zaehler);
2074 mpz_init_set(vec[j], sntz);
2076 #ifdef NEXT_VECTORS_CC
2077 Print(
"\n// j = %d ==> ", j);
2079 mpz_out_str( stdout, 10, t_nenner);
2080 Print(
" * %d)", (*curr_weight)[j]);
2081 Print(
" + ("); mpz_out_str( stdout, 10, t_zaehler);
2082 Print(
" * %d) = ", (*diff_weight)[j]);
2083 mpz_out_str( stdout, 10, s_nenner);
2085 mpz_out_str( stdout, 10, s_zaehler);
2086 PrintS(
" = "); mpz_out_str( stdout, 10, sntz);
2087 Print(
" ==> vector[%d]: ", j); mpz_out_str(stdout, 10, vec[j]);
2096 if(mpz_cmp_si(ggt,1) != 0)
2098 mpz_gcd(ggt, ggt, sntz);
2103 #ifdef NEXT_VECTORS_CC
2104 PrintS(
"\n// gcd of elements of the vector: ");
2105 mpz_out_str( stdout, 10, ggt);
2116 for(j=0; j<nRing; j++)
2118 if(mpz_cmp(vec[j], sing_int_half) >= 0)
2124 for (j=0; j<nRing; j++)
2126 (*diff_weight)[
j] = mpz_get_si(vec[j]);
2131 for (j=0; j<nRing; j++)
2133 (*diff_weight)[
j] = mpz_get_si(vec[j]);
2137 for (j=0; j<nRing; j++)
2139 if(mpz_cmp_si(ggt,1)==0)
2141 (*diff_weight1)[
j] = floor(0.1*(*diff_weight)[j] + 0.5);
2146 mpz_divexact(vec[j], vec[j], ggt);
2147 (*diff_weight1)[
j] = floor(0.1*(*diff_weight)[j] + 0.5);
2170 Print(
"\n// MwalkNextWeightCC: geaenderter vector liegt in Groebnerkegel! \n");
2171 for (j=0; j<nRing; j++)
2173 (*diff_weight)[
j] = (*diff_weight1)[
j];
2190 for (j=0; j<nRing; j++)
2192 if(mpz_cmp(vec[j], sing_int)>=0)
2197 PrintS(
"\n// ** OVERFLOW in \"MwalkNextWeightCC\": ");
2198 mpz_out_str( stdout, 10, vec[j]);
2199 PrintS(
" is greater than 2147483647 (max. integer representation)\n");
2206 delete diff_weight1;
2207 mpz_clear(t_zaehler);
2208 mpz_clear(t_nenner);
2209 mpz_clear(s_zaehler);
2210 mpz_clear(s_nenner);
2215 mpz_clear(deg_w0_p1);
2216 mpz_clear(deg_d0_p1);
2219 mpz_clear(sing_int_half);
2220 mpz_clear(sing_int);
2231 for(kkk=0; kkk<
IDELEMS(G);kkk++)
2310 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2311 r->wvhdl[1] = (
int*)
omAlloc((nv-1)*
sizeof(int));
2313 for(i=0; i<nv-1; i++)
2315 r->wvhdl[1][
i] = (*vb)[
i];
2316 r->wvhdl[0][
i] = (*va)[
i];
2318 r->wvhdl[0][nv] = (*va)[nv];
2321 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2322 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2323 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2392 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2394 r->wvhdl[0][i] = (*va)[
i];
2397 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2398 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2399 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2462 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2464 r->wvhdl[0][i] = (*va)[
i];
2467 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2468 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2469 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2537 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2538 r->wvhdl[1] = (
int*)
omAlloc(nv*
sizeof(
int));
2542 r->wvhdl[0][
i] = (*va)[
i];
2543 r->wvhdl[1][
i] = (*vb)[
i];
2549 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2550 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2551 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2620 r->wvhdl[0] = (
int*)
omAlloc(nv*nv*
sizeof(
int));
2624 for(i=0; i<nv*nv; i++)
2625 r->wvhdl[0][i] = (*va)[
i];
2628 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2629 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2630 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2698 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2699 r->wvhdl[1] = (
int*)
omAlloc(nvs*
sizeof(
int));
2702 for(i=0; i<nvs; i++)
2704 r->wvhdl[1][
i] = (*va)[
i];
2708 r->wvhdl[0][
i] = (*vb)[
i];
2711 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2712 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2713 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2783 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2784 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2785 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2820 res->VarOffset =
NULL;
2828 res->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2830 res->wvhdl[0][i] = (*va)[
i];
2834 res->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2835 res->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2836 res->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2841 res->block1[0] = nv;
2846 res->block1[1] = nv;
2862 for (i=nv-1; i>=0; i--)
2889 r->VarOffset =
NULL;
2902 for(i=nv-1; i>=0; i--)
2913 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2914 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2915 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2963 static int isNolVector(
intvec* hilb)
2966 for(i=hilb->
length()-1; i>=0; i--)
2992 int nwalk=0, endwalks=0, nnwinC=1;
2994 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
2995 ring newRing, oldRing, TargetRing;
2999 intvec* pert_target_vector;
3004 #ifndef BUCHBERGER_ALG
3010 for(i=nV-1; i>0; i--)
3012 (*last_omega)[
i] = 1;
3014 (*last_omega)[0] = 10000;
3019 if(tp_deg > 1 && tp_deg <= nV)
3036 pert_target_vector = target_weight;
3043 target_weight =
Mivlp(nV);
3054 xtnw=xtnw+clock()-
to;
3056 #ifdef PRINT_VECTORS
3057 MivString(curr_weight, target_weight, next_weight);
3076 if(
MivComp(next_weight, ivNull) == 1)
3084 if(
MivComp(next_weight, target_weight) == 1)
3087 for(i=nV-1; i>=0; i--)
3089 (*extra_curr_weight)[
i] = (*curr_weight)[
i];
3092 for(i=nV-1; i>=0; i--)
3094 (*curr_weight)[
i] = (*next_weight)[
i];
3100 xtif=xtif+clock()-
to;
3106 idElements(Gomega,
"Gw");
3107 headidString(Gomega,
"Gw");
3111 #ifndef BUCHBERGER_ALG
3112 if(isNolVector(curr_weight) == 0)
3120 #endif // BUCHBERGER_ALG
3137 #ifdef BUCHBERGER_ALG
3142 #endif // BUCHBERGER_ALG
3143 xtstd=xtstd+clock()-
to;
3152 xtlift=xtlift+clock()-
to;
3164 xtred=xtred+clock()-
to;
3196 Print(
"\n// takes %d steps and calls the recursion of level %d:",
3199 F1 =
LastGB(G,curr_weight, tp_deg-1);
3245 delete target_weight;
3262 for(i=
IDELEMS(G)-1; i>=0; i--)
3271 && (G->m[i]->next!=
NULL)
3272 && (G->m[i]->next->next!=
NULL)
3273 && (G->m[i]->next->next->next!=
NULL)
3290 for(i=
IDELEMS(G)-1; i>=0; i--)
3293 && (G->m[i]->next!=
NULL)
3294 && (G->m[i]->next->next!=
NULL))
3329 for (i=nH-1;i>=0; i--)
3350 for(i=nG-1; i>=0; i--)
3375 static int Trandegreebound(ideal G)
3383 for(i=nG-1; i>=0; i--)
3419 int mtmp,
m=(*iva)[0];
3421 for(i=ivMat->
length(); i>=0; i--)
3440 mpz_set_si(ndeg, Trandegreebound(G)+1);
3446 mpz_init_set_si(maxdeg, Trandegreebound(G));
3449 mpz_pow_ui(ztmp, maxdeg, 2);
3450 mpz_mul_ui(ztmp, ztmp, 2);
3451 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3452 mpz_add(ndeg, ztmp, maxdeg);
3453 mpz_mul_ui(ndeg, ndeg, m);
3459 #endif //UPPER_BOUND
3461 #ifdef INVEPS_SMALL_IN_TRAN
3462 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3464 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3470 mpz_init_set(deg_tmp, ndeg);
3472 mpz_t *ivres=( mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3473 mpz_init_set_si(ivres[nV-1],1);
3475 for(i=nV-2; i>=0; i--)
3477 mpz_init_set(ivres[i], deg_tmp);
3478 mpz_mul(deg_tmp, deg_tmp, ndeg);
3481 mpz_t *ivtmp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3487 mpz_init_set_ui(sing_int, 2147483647);
3496 if( (*ivMat)[i*nV+j] >= 0 )
3498 mpz_mul_ui(ivres[i], ivres[i], (*ivMat)[i*nV+j]);
3502 mpz_mul_ui(ivres[i], ivres[i], -(*ivMat)[i*nV+j]);
3503 mpz_neg(ivres[i], ivres[i]);
3505 mpz_add(ivtmp[j], ivtmp[j], ivres[i]);
3513 (*repr_vector)[
i] = mpz_get_si(ivtmp[i]);
3514 if(mpz_cmp(ivtmp[i], sing_int)>=0)
3521 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3522 mpz_out_str( stdout, 10, ivtmp[i]);
3523 PrintS(
" is greater than 2147483647 (max. integer representation)");
3524 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3530 ivString(repr_vector,
"repvector");
3531 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3540 mpz_clear(sing_int);
3550 static intvec* TranPertVector_lp(ideal G)
3564 mpz_set_si(ndeg, Trandegreebound(G)+1);
3570 mpz_init_set_si(maxdeg, Trandegreebound(G));
3573 mpz_pow_ui(ztmp, maxdeg, 2);
3574 mpz_mul_ui(ztmp, ztmp, 2);
3575 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3576 mpz_add(ndeg, ztmp, maxdeg);
3585 #ifdef INVEPS_SMALL_IN_TRAN
3586 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3587 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3594 mpz_init_set(deg_tmp, ndeg);
3596 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3597 mpz_init_set_si(ivres[nV-1], 1);
3599 for(i=nV-2; i>=0; i--)
3601 mpz_init_set(ivres[i], deg_tmp);
3602 mpz_mul(deg_tmp, deg_tmp, ndeg);
3606 mpz_init_set_ui(sing_int, 2147483647);
3612 (*repr_vector)[
i] = mpz_get_si(ivres[i]);
3614 if(mpz_cmp(ivres[i], sing_int)>=0)
3620 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3621 mpz_out_str( stdout, 10, ivres[i]);
3622 PrintS(
" is greater than 2147483647 (max. integer representation)");
3623 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3629 ivString(repr_vector,
"repvector");
3630 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3638 mpz_clear(sing_int);
3655 int degtmp, maxdeg = 0;
3657 for(i=
IDELEMS(G)-1; i>=0; i--)
3666 mpz_init_set_si(ztmp, maxdeg);
3667 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3668 mpz_init_set_si(ivres[nV-1], 1);
3670 for(i=nV-2; i>=0; i--)
3672 mpz_init_set(ivres[i], ztmp);
3673 mpz_mul_ui(ztmp, ztmp, maxdeg);
3676 mpz_t *ivtmp=(mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
3684 if((*M)[i*nV+
j] < 0)
3686 mpz_mul_ui(ztmp, ivres[i], -(*M)[i*nV+j]);
3687 mpz_neg(ztmp, ztmp);
3690 mpz_mul_ui(ztmp, ivres[i], (*M)[i*nV+j]);
3692 mpz_add(ivtmp[j], ivtmp[j], ztmp);
3696 mpz_init_set_ui(sing_int, 2147483647);
3702 (*repvector)[
i] = mpz_get_si(ivtmp[i]);
3703 if(mpz_cmp(ivtmp[i], sing_int)>0)
3709 PrintS(
"\n// ** OVERFLOW in \"Repr.Matrix\": ");
3710 mpz_out_str( stdout, 10, ivtmp[i]);
3711 PrintS(
" is greater than 2147483647 (max. integer representation)");
3712 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repvector)[i]);
3719 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3725 mpz_clear(sing_int);
3745 static int testnegintvec(
intvec*
v)
3762 intvec* orig_target_weight,
int tp_deg,
int npwinc)
3769 clock_t tinput = clock();
3772 int nwalk=0, endwalks=0, nnwinC=1;
3774 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3775 ring newRing, oldRing, TargetRing;
3782 #ifndef BUCHBERGER_ALG
3788 for(i=nV-1; i>0; i--)
3789 (*last_omega)[
i] = 1;
3790 (*last_omega)[0] = 10000;
3795 if(tp_deg > 1 && tp_deg <= nV)
3864 xtif=xtif+clock()-
to;
3866 #ifndef BUCHBERGER_ALG
3867 if(isNolVector(curr_weight) == 0)
3875 #endif // BUCHBERGER_ALG
3892 #ifdef BUCHBERGER_ALG
3897 #endif // BUCHBERGER_ALG
3898 xtstd=xtstd+clock()-
to;
3907 xtlift=xtlift+clock()-
to;
3919 xtred=xtred+clock()-
to;
3931 xtnw=xtnw+clock()-
to;
3932 #ifdef PRINT_VECTORS
3933 MivString(curr_weight, target_weight, next_weight);
3939 #ifdef TEST_OVERFLOW
3952 if(
MivComp(next_weight, ivNull) == 1)
3959 if(
MivComp(next_weight, target_weight) == 1)
3969 tproc=tproc+clock()-tinput;
3974 G =
Rec_LastGB(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
3981 for(i=nV-1; i>=0; i--)
3983 (*curr_weight)[
i] = (*next_weight)[
i];
4008 tproc=tproc+clock()-tinput;
4009 F1 =
Rec_LastGB(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4011 delete target_weight;
4084 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
xtextra=0;
4086 clock_t tostd, tproc;
4090 int nwalk=0, endwalks=0;
4092 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4095 ring newRing, oldRing;
4128 xtif=xtif+clock()-
to;
4132 for(i=nV-1; i>=0; i--)
4133 (*curr_weight)[
i] = (*extra_curr_weight)[
i];
4134 delete extra_curr_weight;
4154 xtstd=xtstd+clock()-
to;
4164 xtlift=xtlift+clock()-
to;
4176 xtred=xtred+clock()-
to;
4186 xtnw=xtnw+clock()-
to;
4187 #ifdef PRINT_VECTORS
4188 MivString(curr_weight, target_weight, next_weight);
4197 #ifdef TEST_OVERFLOW
4198 goto TEST_OVERFLOW_OI;
4217 if(
MivComp(next_weight, ivNull) == 1)
4224 if(
MivComp(next_weight, target_weight) == 1)
4226 if(
MivSame(target_weight, exivlp)==1)
4233 G =
Rec_LastGB(G, curr_weight, target_weight, 2,1);
4241 for(i=nV-1; i>=0; i--)
4244 (*curr_weight)[
i] = (*next_weight)[
i];
4248 #ifdef TEST_OVERFLOW
4259 TimeStringFractal(
xftinput, tostd, xtif, xtstd,
xtextra,xtlift, xtred,xtnw);
4300 if(
MivComp(next_weight, target_weight) == 1)
4302 return(next_weight);
4314 while(weight_norm == 0)
4319 (*next_weight22)[
i] = rand() % 60000 - 30000;
4320 weight_norm = weight_norm + (*next_weight22)[
i]*(*next_weight22)[
i];
4322 weight_norm = 1 + floor(
sqrt(weight_norm));
4325 for(i=nV-1; i>=0; i--)
4327 if((*next_weight22)[i] < 0)
4329 (*next_weight22)[
i] = 1 + (*curr_weight)[
i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
4333 (*next_weight22)[
i] = (*curr_weight)[
i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
4342 delete next_weight22;
4358 (*result)[
i] = (*next_weight2)[
i];
4365 (*result)[
i] = (*next_weight1)[
i];
4375 (*result)[
i] = (*next_weight2)[
i];
4382 (*result)[
i] = (*next_weight)[
i];
4387 delete next_weight1;
4393 delete next_weight2;
4399 return next_weight2;
4424 while(weight_norm == 0)
4428 (*next_weight22)[
i] = rand() % 60000 - 30000;
4429 weight_norm = weight_norm + (*next_weight22)[
i]*(*next_weight22)[
i];
4431 weight_norm = 1 + floor(
sqrt(weight_norm));
4435 if((*next_weight22)[i] < 0)
4437 (*next_weight22)[
i] = 1 + (*curr_weight)[
i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
4441 (*next_weight22)[
i] = (*curr_weight)[
i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
4447 delete next_weight22;
4467 (*result)[
i] = (*next_weight2)[
i];
4475 (*result)[
i] = (*next_weight1)[
i];
4485 (*result)[
i] = (*next_weight2)[
i];
4493 (*result)[
i] = (*next_weight)[
i];
4506 (*result)[
i] = (*next_weight2)[
i];
4513 (*result)[
i] = (*next_weight)[
i];
4521 delete next_weight2;
4523 delete next_weight1;
4529 delete next_weight2;
4530 delete next_weight1;
4542 int tp_deg,
int npwinc)
4548 int nwalk=0, endwalks=0, nnwinC=1, nlast = 0;
4549 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
4550 ring newRing, oldRing, TargetRing;
4553 #ifndef BUCHBERGER_ALG
4557 for(i=nV-1; i>0; i--)
4559 (*last_omega)[
i] = 1;
4561 (*last_omega)[0] = 10000;
4568 if(tp_deg > 1 && tp_deg <= nV)
4626 xtif = xtif + clock()-
to;
4628 #ifndef BUCHBERGER_ALG
4629 if(isNolVector(curr_weight) == 0)
4655 #ifdef BUCHBERGER_ALG
4661 xtstd = xtstd + clock() -
to;
4671 xtlift = xtlift + clock() -
to;
4685 xtred = xtred + clock() -
to;
4699 xtnw = xtnw + clock() -
to;
4701 #ifdef PRINT_VECTORS
4702 MivString(curr_weight, target_weight, next_weight);
4716 if(
MivComp(next_weight, ivNull) == 1)
4723 if(
MivComp(next_weight, target_weight) == 1)
4731 G =
REC_GB_Mwalk(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4738 for(i=nV-1; i>=0; i--)
4740 (*curr_weight)[
i] = (*next_weight)[
i];
4763 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4769 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight,tp_deg+1,nnwinC);
4772 delete target_weight;
4816 #ifndef BUCHBERGER_ALG
4831 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
4832 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
4841 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4844 ring newRing, oldRing;
4847 #ifndef BUCHBERGER_ALG
4851 for(i=nV-1; i>=0; i--)
4852 (*tmp_weight)[
i] = (*curr_weight)[
i];
4856 for(i=nV-1; i>0; i--)
4857 (*last_omega)[
i] = 1;
4858 (*last_omega)[0] = 10000;
4877 tif = tif + clock()-
to;
4891 if(
MivSame(exivlp, target_weight)==1)
4900 #ifdef CHECK_IDEAL_MWALK
4901 idElements(Gomega,
"G_omega");
4902 headidString(Gomega,
"Gw");
4908 xtlift = xtlift + clock() -
to;
4931 #ifndef BUCHBERGER_ALG
4932 if(isNolVector(curr_weight) == 0)
4940 #endif // BUCHBERGER_ALG
4956 #ifdef BUCHBERGER_ALG
4961 #endif // BUCHBERGER_ALG
4962 tstd = tstd + clock() -
to;
4972 tlift = tlift + clock() -
to;
4988 tred = tred + clock() -
to;
4992 xtred = xtred + clock() -
to;
5003 tnw = tnw + clock() -
to;
5004 #ifdef PRINT_VECTORS
5005 MivString(curr_weight, target_weight, next_weight);
5012 PrintS(
"\n// ** The computed vector does NOT stay in Cone!!\n");
5030 if(
MivComp(next_weight, ivNull) == 1)
5036 if(
MivComp(next_weight, target_weight) == 1)
5040 for(i=nV-1; i>=0; i--)
5042 (*tmp_weight)[
i] = (*curr_weight)[
i];
5043 (*curr_weight)[
i] = (*next_weight)[
i];
5055 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5076 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5077 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5082 int i,nwalk,endwalks = 0;
5083 int nV = baseRing->N;
5085 ideal Gomega,
M, F, Gomega1, Gomega2, M1;
5087 ring XXRing = baseRing;
5095 (*tmp_weight)[
i] = (*target_M)[
i];
5099 (*curr_weight)[
i] = (*orig_M)[
i];
5100 (*target_weight)[
i] = (*target_M)[
i];
5102 #ifndef BUCHBERGER_ALG
5106 for(i=nV-1; i>0; i--)
5108 (*last_omega)[
i] = 1;
5110 (*last_omega)[0] = 10000;
5113 #ifdef CHECK_IDEAL_MWALK
5119 if(orig_M->
length() == nV)
5142 #ifdef CHECK_IDEAL_MWALK
5147 tif = tif + clock()-
to;
5149 #ifdef CHECK_IDEAL_MWALK
5150 idString(Gomega,
"Gomega");
5152 #ifndef BUCHBERGER_ALG
5153 if(isNolVector(curr_weight) == 0)
5164 if(orig_M->
length() == nV)
5175 if(target_M->
length() == nV)
5177 newRing =
VMrRefine(curr_weight,target_weight);
5191 #ifndef BUCHBERGER_ALG
5198 tstd = tstd + clock() -
to;
5201 #ifdef CHECK_IDEAL_MWALK
5202 PrintS(
"\n//** Mwalk: computed M.\n");
5217 tlift = tlift + clock() -
to;
5219 #ifdef CHECK_IDEAL_MWALK
5233 tstd = tstd + clock() -
to;
5236 #ifdef CHECK_IDEAL_MWALK
5244 tnw = tnw + clock() -
to;
5246 #ifdef PRINT_VECTORS
5247 MivString(curr_weight, target_weight, next_weight);
5249 if(
MivComp(next_weight, ivNull) == 1 ||
MivComp(target_weight,curr_weight) == 1)
5251 #ifdef CHECK_IDEAL_MWALK
5252 PrintS(
"\n//** Mwalk: entering last cone.\n");
5255 if(target_M->
length() == nV)
5266 #ifdef CHECK_IDEAL_MWALK
5267 idString(Gomega1,
"Gomega");
5270 #ifdef CHECK_IDEAL_MWALK
5279 #ifdef CHECK_IDEAL_MWALK
5298 tred = tred + clock() -
to;
5303 #ifdef CHECK_IDEAL_MWALK
5304 PrintS(
"\n//** Mwalk: last cone.\n");
5307 #ifdef CHECK_IDEAL_MWALK
5308 PrintS(
"\n//** Mwalk: update weight vectors.\n");
5310 for(i=nV-1; i>=0; i--)
5312 (*tmp_weight)[
i] = (*curr_weight)[
i];
5313 (*curr_weight)[
i] = (*next_weight)[
i];
5326 #ifndef BUCHBERGER_ALG
5330 Print(
"\n//** Mwalk: Groebner Walk took %d steps.\n",
nstep);
5331 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5332 Print(
"\n//** Mwalk: Ergebnis.\n");
5350 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5351 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5356 int i,nwalk,endwalks = 0;
5357 int nV = baseRing->N;
5359 ideal Gomega,
M, F, Gomega1, Gomega2, M1;
5361 ring XXRing = baseRing;
5369 (*tmp_weight)[
i] = (*target_M)[
i];
5373 (*curr_weight)[
i] = (*orig_M)[
i];
5374 (*target_weight)[
i] = (*target_M)[
i];
5376 #ifndef BUCHBERGER_ALG
5380 for(i=nV-1; i>0; i--)
5382 (*last_omega)[
i] = 1;
5384 (*last_omega)[0] = 10000;
5387 #ifdef CHECK_IDEAL_MWALK
5393 if(orig_M->
length() == nV)
5416 #ifdef CHECK_IDEAL_MWALK
5421 tif = tif + clock()-
to;
5423 #ifdef CHECK_IDEAL_MWALK
5424 idString(Gomega,
"Gomega");
5426 #ifndef BUCHBERGER_ALG
5427 if(isNolVector(curr_weight) == 0)
5438 if(orig_M->
length() == nV)
5449 if(target_M->
length() == nV)
5451 newRing =
VMrRefine(curr_weight,target_weight);
5465 #ifndef BUCHBERGER_ALG
5472 tstd = tstd + clock() -
to;
5475 #ifdef CHECK_IDEAL_MWALK
5476 PrintS(
"\n//** Mwalk: computed M.\n");
5491 tlift = tlift + clock() -
to;
5493 #ifdef CHECK_IDEAL_MWALK
5507 tstd = tstd + clock() -
to;
5510 #ifdef CHECK_IDEAL_MWALK
5518 tnw = tnw + clock() -
to;
5520 #ifdef PRINT_VECTORS
5521 MivString(curr_weight, target_weight, next_weight);
5523 if(
MivComp(next_weight, ivNull) == 1 ||
MivComp(target_weight,curr_weight) == 1)
5525 #ifdef CHECK_IDEAL_MWALK
5526 PrintS(
"\n//** Mwalk: entering last cone.\n");
5529 if(target_M->
length() == nV)
5540 #ifdef CHECK_IDEAL_MWALK
5541 idString(Gomega1,
"Gomega");
5544 #ifdef CHECK_IDEAL_MWALK
5553 #ifdef CHECK_IDEAL_MWALK
5572 tred = tred + clock() -
to;
5577 #ifdef CHECK_IDEAL_MWALK
5578 PrintS(
"\n//** Mwalk: last cone.\n");
5581 #ifdef CHECK_IDEAL_MWALK
5582 PrintS(
"\n//** Mwalk: update weight vectors.\n");
5584 for(i=nV-1; i>=0; i--)
5586 (*tmp_weight)[
i] = (*curr_weight)[
i];
5587 (*curr_weight)[
i] = (*next_weight)[
i];
5600 #ifndef BUCHBERGER_ALG
5604 Print(
"\n//** Mwalk: Groebner Walk took %d steps.\n",
nstep);
5605 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5606 Print(
"\n//** Mwalk: Ergebnis.\n");
5615 ideal Mwalk_tst(ideal Go,
intvec* curr_weight,
intvec* target_weight)
5620 int nwalk=0, endwalks=0;
5622 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
5624 ring newRing, oldRing;
5629 for(i=nV-1; i>=0; i--)
5631 (*tmp_weight)[
i] = (*curr_weight)[
i];
5635 #ifndef BUCHBERGER_ALG
5640 for(i=nV-1; i>0; i--)
5641 (*last_omega)[
i] = 1;
5642 (*last_omega)[0] = 10000;
5653 idString(Gomega,
"Gw");
5655 #ifndef BUCHBERGER_ALG
5656 if(isNolVector(curr_weight) == 0)
5660 #endif // BUCHBERGER_ALG
5672 #ifdef BUCHBERGER_ALG
5677 #endif // BUCHBERGER_ALG
5709 #ifdef PRINT_VECTORS
5710 MivString(curr_weight, target_weight, next_weight);
5713 if(
MivComp(next_weight, ivNull) == 1)
5718 if(
MivComp(next_weight, target_weight) == 1)
5721 for(i=nV-1; i>=0; i--)
5722 (*tmp_weight)[
i] = (*curr_weight)[
i];
5725 for(i=nV-1; i>=0; i--)
5726 (*curr_weight)[
i] = (*next_weight)[
i];
5753 intvec* target_weight,
int nP)
5759 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5761 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5767 int i, ntwC=1, ntestw=1, nV =
currRing->N;
5770 ideal Gomega,
M, F,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5771 ring newRing, oldRing, TargetRing;
5775 intvec* orig_target = target_weight;
5776 intvec* pert_target_vector = target_weight;
5779 #ifndef BUCHBERGER_ALG
5786 for(i=nV-1; i>0; i--)
5787 (*last_omega)[
i] = 1;
5788 (*last_omega)[0] = 10000;
5795 if(
MivComp(curr_weight, iv_dp) == 1)
5822 if(op_deg != 1)
delete iv_M_dp;
5827 if(tp_deg > 1 && tp_deg <= nV)
5836 if(
MivSame(target_weight, exivlp) == 1)
5850 pert_target_vector = target_weight;
5873 headidString(G,
"G");
5878 tif = tif + clock()-
to;
5880 #ifndef BUCHBERGER_ALG
5881 if(isNolVector(curr_weight) == 0)
5885 #endif // BUCHBERGER_ALG
5902 idElements(Gomega1,
"Gw");
5903 headidString(Gomega1,
"headGw");
5904 PrintS(
"\n// compute a rGB of Gw:\n");
5906 #ifndef BUCHBERGER_ALG
5915 #ifdef BUCHBERGER_ALG
5920 #endif // BUCHBERGER_ALG
5923 xtstd = xtstd+clock()-
to;
5925 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
5926 ((
double) clock())/1000000 -((
double)tim) /1000000);
5930 tstd=tstd+clock()-
to;
5945 tlift = tlift+clock()-
to;
5963 tred = tred+clock()-
to;
5976 #ifdef PRINT_VECTORS
5977 MivString(curr_weight, target_weight, next_weight);
5989 if(
MivComp(next_weight, ivNull) == 1){
5995 if(
MivComp(next_weight, target_weight) == 1)
5998 for(i=nV-1; i>=0; i--)
5999 (*curr_weight)[
i] = (*next_weight)[
i];
6007 if(
MivSame(orig_target, exivlp) == 1)
6021 headidString(G,
"G");
6030 if( ntestw != 1 || ntwC == 0)
6043 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1){
6052 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6072 delete target_weight;
6081 TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6100 (*ivM)[i*nV +
j] = 1;
6118 ring new_ring, testring;
6120 ideal Gomega, Gomega1, Gomega2, F, F1, Gresult, Gresult1, G1, Gt;
6123 #ifndef BUCHBERGER_ALG
6135 for(i=nV-1; i>0; i--)
6136 (*last_omega)[
i] = 1;
6137 (*last_omega)[0] = 10000;
6140 for(i=0; i<nV; i++) {
6141 if(Xsigma->
length() == nV)
6142 (*omega)[
i] = (*Xsigma)[
i];
6144 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
6146 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
6149 if(nlev == 1) Xcall = 1;
6156 #ifdef FIRST_STEP_FRACTAL
6159 if((nlev == 1 && Xcall == 0) || (nlev == 2 && Xngleich == 1))
6169 NEXT_VECTOR_FRACTAL:
6173 xtnw=xtnw+clock()-
to;
6174 #ifdef PRINT_VECTORS
6175 MivString(omega, omega2, next_vect);
6180 if(Xngleich == 0 && nlev == 1)
6181 if (
MivComp(next_vect, omega2) != 1)
6211 for(i=nV-1; i>=0; i--) {
6212 (*omega2)[
i] = (*Xtau)[nV+
i];
6213 (*omega)[
i] = (*Xsigma)[nV+
i];
6223 xtnw=xtnw+clock()-
to;
6225 #ifdef PRINT_VECTORS
6226 MivString(omega, omega2, next_vect);
6246 #ifdef TEST_OVERFLOW
6248 Gt =
NULL;
return(Gt);
6277 if (
MivComp(next_vect, XivNull) == 1)
6301 #ifndef MSTDCC_FRACTAL
6305 #ifdef TEST_OVERFLOW
6307 Gt =
NULL;
return(Gt);
6310 if(
MivSame(Xtau, Xtautmp) == 1)
6314 goto FRACTAL_MSTDCC;
6321 for(i=nV-1; i>=0; i--)
6322 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
6328 goto NEXT_VECTOR_FRACTAL;
6340 if(
MivSame(Xivinput, Xivlp) == 1)
6375 for(i=nV-1; i>=0; i--) {
6376 (*altomega)[
i] = (*omega)[
i];
6377 (*omega)[
i] = (*next_vect)[
i];
6384 xtif=xtif+clock()-
to;
6386 #ifndef BUCHBERGER_ALG
6387 if(isNolVector(omega) == 0)
6391 #endif // BUCHBERGER_ALG
6404 if(nlev == Xnlev ||
lengthpoly(Gomega1) == 0)
6415 #ifdef BUCHBERGER_ALG
6420 #endif // BUCHBERGER_ALG
6421 xtstd=xtstd+clock()-
to;
6439 xtlift=xtlift+clock()-
to;
6450 xtred=xtred+clock()-
to;
6464 ring new_ring, testring;
6466 ideal Gomega, Gomega1, Gomega2, F, F1, Gresult, Gresult1, G1, Gt;
6469 #ifndef BUCHBERGER_ALG
6481 for(i=nV-1; i>0; i--)
6482 (*last_omega)[
i] = 1;
6483 (*last_omega)[0] = 10000;
6486 for(i=0; i<nV; i++) {
6487 if(Xsigma->
length() == nV)
6488 (*omega)[
i] = (*Xsigma)[
i];
6490 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
6492 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
6495 if(nlev == 1) Xcall = 1;
6502 #ifdef FIRST_STEP_FRACTAL
6505 if((nlev == 1 && Xcall == 0) || (nlev == 2 && Xngleich == 1))
6515 NEXT_VECTOR_FRACTAL:
6520 xtnw=xtnw+clock()-
to;
6521 #ifdef PRINT_VECTORS
6522 MivString(omega, omega2, next_vect);
6527 if(Xngleich == 0 && nlev == 1)
6528 if (
MivComp(next_vect, omega2) == 1)
6558 for(i=nV-1; i>=0; i--) {
6559 (*omega2)[
i] = (*Xtau)[nV+
i];
6560 (*omega)[
i] = (*Xsigma)[nV+
i];
6570 xtnw=xtnw+clock()-
to;
6572 #ifdef PRINT_VECTORS
6573 MivString(omega, omega2, next_vect);
6593 #ifdef TEST_OVERFLOW
6595 Gt =
NULL;
return(Gt);
6624 if (
MivComp(next_vect, XivNull) == 1)
6648 #ifndef MSTDCC_FRACTAL
6652 #ifdef TEST_OVERFLOW
6654 Gt =
NULL;
return(Gt);
6657 if(
MivSame(Xtau, Xtautmp) == 1)
6661 goto FRACTAL_MSTDCC;
6668 for(i=nV-1; i>=0; i--)
6669 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
6675 goto NEXT_VECTOR_FRACTAL;
6687 if(
MivSame(Xivinput, Xivlp) == 1)
6722 for(i=nV-1; i>=0; i--) {
6723 (*altomega)[
i] = (*omega)[
i];
6724 (*omega)[
i] = (*next_vect)[
i];
6731 xtif=xtif+clock()-
to;
6733 #ifndef BUCHBERGER_ALG
6734 if(isNolVector(omega) == 0)
6738 #endif // BUCHBERGER_ALG
6751 if(nlev == Xnlev ||
lengthpoly(Gomega1) == 0)
6762 #ifdef BUCHBERGER_ALG
6767 #endif // BUCHBERGER_ALG
6768 xtstd=xtstd+clock()-
to;
6786 xtlift=xtlift+clock()-
to;
6797 xtred=xtred+clock()-
to;
6824 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
xtextra=0;
6829 XivNull =
new intvec(nV);
6830 Xivinput = ivtarget;
6840 #ifdef FIRST_STEP_FRACTAL
6842 for(i=
IDELEMS(Gw)-1; i>=0; i--)
6845 && (Gw->m[i]->next!=
NULL)
6846 && (Gw->m[i]->next->next!=
NULL))
6851 if(
MivSame(ivstart, iv_dp) != 1)
6871 if(
MivComp(ivtarget, Xivlp) != 1)
6929 xtlift, xtred, xtnw);
6934 Print(
"\n// the numbers of Overflow_Error (%d)", nnflow);
6950 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
xtextra=0;
6955 XivNull =
new intvec(nV);
6956 Xivinput = ivtarget;
6966 #ifdef FIRST_STEP_FRACTAL
6968 for(i=
IDELEMS(Gw)-1; i>=0; i--)
6971 && (Gw->m[i]->next!=
NULL)
6972 && (Gw->m[i]->next->next!=
NULL))
6977 if(
MivSame(ivstart, iv_dp) != 1)
6997 if(
MivComp(ivtarget, Xivlp) != 1)
7055 xtlift, xtred, xtnw);
7060 Print(
"\n// the numbers of Overflow_Error (%d)", nnflow);
7074 clock_t mtim = clock();
7081 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
7083 clock_t tinput = clock();
7085 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
7086 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
7087 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
7089 ring newRing, oldRing, lpRing;
7097 int nGB, endwalks = 0, nwalkpert=0, npertstep=0;
7100 #ifndef BUCHBERGER_ALG
7105 for(i=nV-1; i>0; i--)
7106 (*last_omega)[
i] = 1;
7107 (*last_omega)[0] = 10000;
7111 for(i=nV-1; i>=0; i--)
7112 (*target_weight)[
i] = (*target_tmp)[
i];
7119 if(
MivComp(curr_weight, iv_dp) == 1)
7133 #ifdef REPRESENTATION_OF_SIGMA
7139 if(
MivComp(curr_weight, iv_dp) == 1)
7140 MDp = MatrixOrderdp(nV);
7144 curr_weight = RepresentationMatrix_Dp(G, MDp);
7158 tostd=tostd+clock()-
to;
7160 goto COMPUTE_NEW_VECTOR;
7175 #ifndef BUCHBERGER_ALG
7176 if(isNolVector(curr_weight) == 0)
7180 #endif // BUCHBERGER_ALG
7195 #ifdef BUCHBERGER_ALG
7200 #endif // BUCHBERGER_ALG
7201 tstd=tstd+clock()-
to;
7213 tlift=tlift+clock()-
to;
7226 tred=tred+clock()-
to;
7238 #ifdef PRINT_VECTORS
7239 MivString(curr_weight, target_weight, next_weight);
7252 OMEGA_OVERFLOW_TRAN_NEW:
7255 #ifdef TEST_OVERFLOW
7259 #ifdef CHECK_IDEAL_MWALK
7264 if(
MivSame(target_tmp, iv_lp) == 1)
7280 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0){
7289 G =
LastGB(G1, curr_weight, nV-1);
7295 npert[endwalks]=nwalk-npert_tmp;
7304 if(
MivComp(next_weight, target_weight) == 1 ||
7305 MivComp(next_weight, curr_weight) == 1 )
7311 npert[endwalks]=nwalk-npert_tmp;
7317 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1){
7324 if(
MivSame(target_tmp, iv_lp) == 1)
7342 for(i=
IDELEMS(Glp)-1; i>=0; i--)
7368 for(i=
IDELEMS(Glp)-1; i>=0; i--)
7371 if(p->next !=
NULL &&
7372 p->next->next !=
NULL &&
7373 p->next->next->next !=
NULL)
7378 (*vector_tmp)[
i] = (*target_weight)[
i];
7380 delete target_weight;
7383 if(
MivComp(vector_tmp, target_weight)==1)
7388 goto OMEGA_OVERFLOW_TRAN_NEW;
7395 goto OMEGA_OVERFLOW_TRAN_NEW;
7405 if(plength3 ==
FALSE)
7431 goto COMPUTE_NEW_VECTOR;
7435 for(i=nV-1; i>=0; i--)
7436 (*curr_weight)[
i] = (*next_weight)[
i];
7440 #ifdef TEST_OVERFLOW
7453 Print(
"\n// Computation took %d steps and %.2f sec",
7454 nwalk, ((
double) (clock()-mtim)/1000000));
7456 TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
7471 ideal TranMrImprovwalk(ideal G,
intvec* curr_weight,
intvec* target_tmp,
int nP,
int weight_rad,
int pert_deg)
7474 clock_t mtim = clock();
7481 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
7483 clock_t tinput = clock();
7485 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
7486 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
7487 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
7489 ring newRing, oldRing, lpRing;
7497 int weight_norm, nGB, endwalks = 0, nwalkpert=0, npertstep=0;
7500 #ifndef BUCHBERGER_ALG
7505 for(i=nV-1; i>0; i--)
7507 (*last_omega)[
i] = 1;
7509 (*last_omega)[0] = 10000;
7513 for(i=nV-1; i>=0; i--)
7515 (*target_weight)[
i] = (*target_tmp)[
i];
7522 if(
MivComp(curr_weight, iv_dp) == 1)
7543 #ifdef REPRESENTATION_OF_SIGMA
7549 if(
MivComp(curr_weight, iv_dp) == 1)
7551 MDp = MatrixOrderdp(nV);
7557 curr_weight = RepresentationMatrix_Dp(G, MDp);
7575 tostd=tostd+clock()-
to;
7577 goto COMPUTE_NEW_VECTOR;
7592 #ifndef BUCHBERGER_ALG
7593 if(isNolVector(curr_weight) == 0)
7601 #endif // BUCHBERGER_ALG
7619 #ifdef BUCHBERGER_ALG
7625 tstd=tstd+clock()-
to;
7636 tlift=tlift+clock()-
to;
7649 tred=tred+clock()-
to;
7737 #ifdef PRINT_VECTORS
7738 MivString(curr_weight, target_weight, next_weight);
7750 OMEGA_OVERFLOW_TRAN_NEW:
7753 #ifdef TEST_OVERFLOW
7757 #ifdef CHECK_IDEAL_MWALK
7762 if(
MivSame(target_tmp, iv_lp) == 1)
7789 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0)
7800 G =
LastGB(G1, curr_weight, nV-1);
7806 npert[endwalks]=nwalk-npert_tmp;
7815 if(
MivComp(next_weight, target_weight) == 1 ||
MivComp(next_weight, curr_weight) == 1 )
7821 npert[endwalks]=nwalk-npert_tmp;
7827 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1)
7835 if(
MivSame(target_tmp, iv_lp) == 1)
7863 for(i=
IDELEMS(Glp)-1; i>=0; i--)
7888 for(i=
IDELEMS(Glp)-1; i>=0; i--)
7891 if(p->next !=
NULL &&
7892 p->next->next !=
NULL &&
7893 p->next->next->next !=
NULL)
7899 (*vector_tmp)[
i] = (*target_weight)[
i];
7901 delete target_weight;
7904 if(
MivComp(vector_tmp, target_weight)==1)
7909 goto OMEGA_OVERFLOW_TRAN_NEW;
7916 goto OMEGA_OVERFLOW_TRAN_NEW;
7926 if(plength3 ==
FALSE)
7952 goto COMPUTE_NEW_VECTOR;
7956 for(i=nV-1; i>=0; i--)
7958 (*curr_weight)[
i] = (*next_weight)[
i];
7962 #ifdef TEST_OVERFLOW
7975 Print(
"\n// Computation took %d steps and %.2f sec", nwalk, ((
double) (clock()-mtim)/1000000));
7977 TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
7995 clock_t tinput=clock();
7997 int nwalk=0, endwalks=0, ntestwinC=1;
7998 int tp_deg_tmp = tp_deg;
7999 ideal Gomega,
M, F,
G, M1, F1, Gomega1, Gomega2, G1;
8000 ring newRing, oldRing, TargetRing;
8033 target_weight =
Mivlp(nV);
8043 if(tp_deg != tp_deg_tmp)
8053 #ifndef BUCHBERGER_ALG
8058 for(i=nV-1; i>0; i--)
8060 (*last_omega)[
i] = 1;
8062 (*last_omega)[0] = 10000;
8079 xtif=xtif+clock()-
to;
8081 #ifndef BUCHBERGER_ALG
8082 if(isNolVector(curr_weight) == 0)
8105 Print(
"\n// it is %d-th step!!", nwalk);
8106 idElements(Gomega1,
"Gw");
8107 PrintS(
"\n// compute a rGB of Gw:");
8113 #ifdef BUCHBERGER_ALG
8118 #endif // BUCHBERGER_ALG
8119 xtstd=xtstd+clock()-
to;
8131 xtlift=xtlift+clock()-
to;
8144 xtred=xtred+clock()-
to;
8155 xtnw=xtnw+clock()-
to;
8156 #ifdef PRINT_VECTORS
8157 MivString(curr_weight, target_weight, next_weight);
8165 tproc = tproc+clock()-tinput;
8177 if(
MivComp(next_weight, ivNull) == 1)
8183 if(
MivComp(next_weight, target_weight) == 1)
8187 for(i=nV-1; i>=0; i--)
8190 (*curr_weight)[
i] = (*next_weight)[
i];
8210 PrintS(
"\n// The perturbed target vector doesn't STAY in the correct cone!!");
8224 tproc = tproc+clock()-tinput;
8236 delete target_weight;
8246 ideal
Mprwalk(ideal Go,
intvec* curr_weight,
intvec* target_weight,
int weight_rad,
int op_deg,
int tp_deg, ring baseRing)
8253 clock_t tinput=0, tostd=0, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
8254 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
8258 int i,nwalk,nV = baseRing->N;
8260 ideal
G, Gomega,
M, F, Gomega1, Gomega2, M1;
8262 ring XXRing = baseRing;
8264 intvec* orig_target = target_weight;
8265 intvec* pert_target_vector = target_weight;
8268 #ifdef CHECK_IDEAL_MWALK
8273 (*tmp_weight)[
i] = (*curr_weight)[
i];
8275 #ifndef BUCHBERGER_ALG
8281 (*last_omega)[
i] = 1;
8283 (*last_omega)[0] = 10000;
8295 tostd = tostd + to - clock();
8297 #ifdef CHECK_IDEAL_MWALK
8312 if(tp_deg > 1 && tp_deg <= nV)
8314 pert_target_vector = target_weight;
8316 #ifdef CHECK_IDEAL_MWALK
8317 ivString(curr_weight,
"new curr_weight");
8318 ivString(target_weight,
"new target_weight");
8329 tif = tif + clock()-
to;
8331 #ifdef CHECK_IDEAL_MWALK
8332 idString(Gomega,
"Gomega");
8334 #ifndef BUCHBERGER_ALG
8335 if(isNolVector(curr_weight) == 0)
8350 newRing =
VMrRefine(curr_weight,target_weight);
8359 #ifndef BUCHBERGER_ALG
8367 tstd = tstd + clock() -
to;
8369 #ifdef CHECK_IDEAL_MWALK
8383 tlift = tlift + clock() -
to;
8385 #ifdef CHECK_IDEAL_MWALK
8392 #ifdef CHECK_IDEAL_MWALK
8400 tnw = tnw + clock() -
to;
8402 #ifdef PRINT_VECTORS
8403 MivString(curr_weight, target_weight, next_weight);
8407 PrintS(
"\n//**Mprwalk: OVERFLOW: The computed vector does not stay in cone, the result may be wrong.\n");
8418 for(i=nV-1; i>=0; i--)
8420 (*tmp_weight)[
i] = (*curr_weight)[
i];
8421 (*curr_weight)[
i] = (*next_weight)[
i];
8434 #ifndef BUCHBERGER_ALG
8438 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
8456 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
xtextra=0;
8458 clock_t tostd, tproc;
8462 int nwalk=0, endwalks=0;
8463 int op_tmp = op_deg;
8464 ideal Gomega,
M, F,
G, Gomega1, Gomega2, M1, F1;
8465 ring newRing, oldRing;
8472 #ifndef BUCHBERGER_ALG
8475 intvec* cw_tmp = curr_weight;
8479 for(i=nV-1; i>0; i--)
8481 (*last_omega)[
i] = 1;
8483 (*last_omega)[0] = 10000;
8495 if(
MivComp(curr_weight, iv_dp) == 1)
8498 if(op_tmp == op_deg)
8510 if(op_tmp == op_deg)
8534 curr_weight = cw_tmp;
8561 xtif=xtif+clock()-
to;
8565 for(i=nV-1; i>=0; i--)
8566 (*curr_weight)[
i] = (*extra_curr_weight)[
i];
8567 delete extra_curr_weight;
8573 #ifndef BUCHBERGER_ALG
8574 if(isNolVector(curr_weight) == 0)
8582 #endif // BUCHBERGER_ALG
8600 #ifdef BUCHBERGER_ALG
8605 #endif // BUCHBERGER_ALG
8606 xtstd=xtstd+clock()-
to;
8616 xtlift=xtlift+clock()-
to;
8629 xtred=xtred+clock()-
to;
8640 xtnw=xtnw+clock()-
to;
8641 #ifdef PRINT_VECTORS
8642 MivString(curr_weight, target_weight, next_weight);
8666 if(
MivComp(next_weight, ivNull) == 1)
8673 if(
MivComp(next_weight, target_weight) == 1)
8675 if(tp_deg == 1 ||
MivSame(target_weight, exivlp) == 0)
8695 for(i=nV-1; i>=0; i--)
8698 (*curr_weight)[
i] = (*next_weight)[
i];
8715 Print(
"\n// \"Main procedure\" took %d steps, %.2f sec. and Overflow_Error(%d)",
8716 nwalk, ((
double) tproc)/1000000, nOverflow_Error);
8718 TimeStringFractal(
xftinput, tostd, xtif, xtstd,
xtextra, xtlift, xtred, xtnw);
8722 Print(
"\n// Awalk1 took %d steps.\n",
nstep);
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
ideal Mfwalk(ideal G, intvec *ivstart, intvec *ivtarget)
KINLINE TObject ** initR()
intvec * MivMatrixOrder(intvec *iv)
static int test_w_in_ConeCC(ideal G, intvec *iv)
ideal idVec2Ideal(poly vec)
static unsigned long * initsevS(int maxnr)
intvec * Mfpertvector(ideal G, intvec *ivtarget)
KINLINE unsigned long * initsevT()
static ideal REC_GB_Mwalk(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
static long Mlcm(long &i1, long &i2)
static int MivComp(intvec *iva, intvec *ivb)
static ring VMrDefault1(intvec *va)
static int test_G_GB_walk(ideal H0, ideal H1)
intvec * MMatrixone(int nV)
Compatiblity layer for legacy polynomial operations (over currRing)
static int MivAbsMax(intvec *vec)
intvec * MivWeightOrderlp(intvec *ivstart)
static ring VMatrDefault(intvec *va)
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
#define omFreeSize(addr, size)
static poly MpolyInitialForm(poly g, intvec *curr_weight)
const CanonicalForm CFMap CFMap int &both_non_zero int n
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
intvec * ivCopy(const intvec *o)
void enterpairsSpecial(poly h, int k, int ecart, int pos, kStrategy strat, int atR=-1)
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
int MivSame(intvec *u, intvec *v)
intvec * MivWeightOrderdp(intvec *ivstart)
static int MLmWeightedDegree(const poly p, intvec *weight)
void WerrorS(const char *s)
static intvec * MivSub(intvec *a, intvec *b)
static char const ** rParameter(const ring r)
(r->cf->parameter)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy ...
static ring VMatrRefine(intvec *va, intvec *vb)
#define pEqualPolys(p1, p2)
void Set_Error(BOOLEAN f)
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
int(* posInT)(const TSet T, const int tl, LObject &h)
ideal Mfrwalk(ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad)
static void VMrDefaultlp(void)
static int pLength(poly a)
static long MivDotProduct(intvec *a, intvec *b)
int posInT0(const TSet, const int length, LObject &)
static void cancel(mpz_t zaehler, mpz_t nenner)
intvec * MPertVectorslp(ideal G, intvec *ivtarget, int pdeg)
static poly redBba(poly h, int maxIndex, kStrategy strat)
void enterT(LObject &p, kStrategy strat, int atT)
void(* initEcart)(TObject *L)
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
#define pGetExp(p, i)
Exponent.
void initS(ideal F, ideal Q, kStrategy strat)
static int rBlocks(ring r)
#define SI_RESTORE_OPT(A, B)
Coefficient rings, fields and other domains suitable for Singular polynomials.
ideal MAltwalk1(ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight)
#define TEST_OPT_INTSTRATEGY
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
static int islengthpoly2(ideal G)
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...
static int max(int a, int b)
ideal Mprwalk(ideal Go, intvec *curr_weight, intvec *target_weight, int weight_rad, int op_deg, int tp_deg, ring baseRing)
static ideal idHeadCC(ideal h)
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl.cc )
int M3ivSame(intvec *temp, intvec *u, intvec *v)
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
ideal Mrwalk(ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int pert_deg, ring baseRing)
ideal Mpwalk(ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP)
gmp_float sqrt(const gmp_float &a)
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
void initBuchMoraCrit(kStrategy strat)
static intvec * NewVectorlp(ideal I)
static ideal Mpwalk_MAltwalk1(ideal Go, intvec *curr_weight, int tp_deg)
void PrintS(const char *s)
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
static ideal Rec_LastGB(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
static void MLmWeightedDegree_gmp(mpz_t result, const poly p, intvec *weight)
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static ideal MstdhomCC(ideal G)
#define rHasLocalOrMixedOrdering_currRing()
void rChangeCurrRing(ring r)
static void DefRingParlp(void)
ideal idInit(int idsize, int rank)
initialise an ideal / module
static ideal MstdCC(ideal G)
const Variable & v
< [in] a sqrfree bivariate poly
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *omtmp, int weight_rad)
static long gcd(const long a, const long b)
static int lengthpoly(ideal G)
static intvec * MExpPol(poly f)
static void DefRingPar(intvec *va)
BOOLEAN rHasGlobalOrdering(const ring r)
ideal TranMImprovwalk(ideal G, intvec *curr_weight, intvec *target_tmp, int nP)
static ideal kInterRedCC(ideal F, ideal Q)
static ideal MidMult(ideal A, ideal B)
static int MwalkWeightDegree(poly p, intvec *weight_vector)
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
static ideal rec_fractal_call(ideal G, int nlev, intvec *omtmp)
void updateS(BOOLEAN toT, kStrategy strat)
intvec * MivMatrixOrderdp(int nV)
#define SI_SAVE_OPT(A, B)
void CleanUp(ring r=currRing)
void completeReduce(kStrategy strat, BOOLEAN withT)
ideal MAltwalk2(ideal Go, intvec *curr_weight, intvec *target_weight)
ideal idLift(ideal mod, ideal submod, ideal *rest, BOOLEAN goodShape, BOOLEAN isSB, BOOLEAN divide, matrix *unit)
static void p_Setm(poly p, const ring r)
static intset initec(int maxnr)
static poly redMora(poly h, int maxIndex, kStrategy strat)
void initEcartNormal(TObject *h)
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
ideal Mwalk(ideal Go, intvec *orig_M, intvec *target_M, ring baseRing)
ideal MwalkAlt(ideal Go, intvec *curr_weight, intvec *target_weight)
static void ivString(intvec *iv, const char *ch)
ideal MwalkInitialForm(ideal G, intvec *ivw)
static ring VMrRefine(intvec *va, intvec *vb)
BOOLEAN lRingDependend(lists L)
void idDelete(ideal *h)
delete an ideal
intvec * MivMatrixOrderlp(int nV)
static intvec * MWalkRandomNextWeight(ideal G, intvec *curr_weight, intvec *target_weight, int weight_rad, int pert_deg)
static ring VMrDefault(intvec *va)
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
#define pCopy(p)
return a copy of the poly
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
static int * initS_2_R(int maxnr)