11 #define BUCHBERGER_ALG //we use the improved Buchberger alg. 18 #define CHECK_IDEAL_MWALK //to print intermediate results 23 #define INVEPS_SMALL_IN_FRACTAL //to choose the small invers of epsilon 24 #define INVEPS_SMALL_IN_MPERTVECTOR //to choose the small invers of epsilon 25 #define INVEPS_SMALL_IN_TRAN //to choose the small invers of epsilon 27 #define FIRST_STEP_FRACTAL // to define the first step of the fractal 28 #define MSTDCC_FRACTAL // apply Buchberger alg to compute a red GB, if tau doesn't stay in the correct cone 86 #include <sys/types.h> 99 clock_t xtif, xtstd, xtlift, xtred, xtnw;
100 clock_t xftostd, xtextra, xftinput, to;
113 return (
unsigned long*)
omAlloc0(maxnr*
sizeof(
unsigned long));
117 return (
int*)
omAlloc0(maxnr*
sizeof(
int));
358 ideal shdl=strat->
Shdl;
366 static void TimeString(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
367 clock_t tlf,clock_t tred, clock_t tnw,
int step)
369 double totm = ((double) (clock() - tinput))/1000000;
370 double ostd,mostd, mif, mstd, mlf, mred, mnw, mxif,mxstd,mxlf,mxred,mxnw,tot;
372 Print(
"\n// total time = %.2f sec", totm);
373 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
374 mostd=((((
double) tostd)/1000000)/totm)*100);
375 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
376 mif=((((
double) tif)/1000000)/totm)*100);
377 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
378 mstd=((((
double) tstd)/1000000)/totm)*100);
379 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
380 mlf=((((
double) tlf)/1000000)/totm)*100);
381 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
382 mred=((((
double) tred)/1000000)/totm)*100);
383 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
384 mnw=((((
double) tnw)/1000000)/totm)*100);
385 PrintS(
"\n Time for the last step:");
386 Print(
"\n// xinfo = %.2f sec = %.2f", ((
double) xtif)/1000000,
387 mxif=((((
double) xtif)/1000000)/totm)*100);
388 Print(
"\n// xstd = %.2f sec = %.2f", ((
double) xtstd)/1000000,
389 mxstd=((((
double) xtstd)/1000000)/totm)*100);
390 Print(
"\n// xlift = %.2f sec = %.2f", ((
double) xtlift)/1000000,
391 mxlf=((((
double) xtlift)/1000000)/totm)*100);
392 Print(
"\n// xired = %.2f sec = %.2f", ((
double) xtred)/1000000,
393 mxred=((((
double) xtred)/1000000)/totm)*100);
394 Print(
"\n// xnextw= %.2f sec = %.2f", ((
double) xtnw)/1000000,
395 mxnw=((((
double) xtnw)/1000000)/totm)*100);
397 tot=mostd+mif+mstd+mlf+mred+mnw+mxif+mxstd+mxlf+mxred+mxnw;
398 double res = (double) 100 - tot;
399 Print(
"\n// &%d&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f(%.2f)\\ \\",
400 step, ostd, totm, mostd,mif,mstd,mlf,mred,mnw,mxif,mxstd,mxlf,mxred,mxnw,tot,res,
401 ((((
double) xtextra)/1000000)/totm)*100);
404 static void TimeStringFractal(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
405 clock_t textra, clock_t tlf,clock_t tred, clock_t tnw)
408 double totm = ((double) (clock() - tinput))/1000000;
409 double ostd, mostd, mif, mstd, mextra, mlf, mred, mnw, tot,
res;
410 Print(
"\n// total time = %.2f sec", totm);
411 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
412 mostd=((((
double) tostd)/1000000)/totm)*100);
413 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
414 mif=((((
double) tif)/1000000)/totm)*100);
415 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
416 mstd=((((
double) tstd)/1000000)/totm)*100);
417 Print(
"\n// xstd = %.2f sec = %.2f", ((
double) textra)/1000000,
418 mextra=((((
double) textra)/1000000)/totm)*100);
419 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
420 mlf=((((
double) tlf)/1000000)/totm)*100);
421 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
422 mred=((((
double) tred)/1000000)/totm)*100);
423 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
424 mnw=((((
double) tnw)/1000000)/totm)*100);
425 tot = mostd+mif+mstd+mextra+mlf+mred+mnw;
426 res = (double) 100.00-tot;
427 Print(
"\n// &%.2f &%.2f&%.2f &%.2f &%.2f &%.2f &%.2f &%.2f &%.2f&%.2f&%.2f\\ \\ ",
428 ostd,totm,mostd,mif,mstd,mextra,mlf,mred,mnw,tot,res);
432 #ifdef CHECK_IDEAL_MWALK 437 Print(
"\n// ideal %s = ", st);
438 for(i=0; i<nL-1; i++)
504 Print(
"\n// intvec %s = ", ch);
506 for(
int i=0;
i<nV;
i++)
510 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;
597 static void cancel(mpz_t zaehler, mpz_t nenner)
602 mpz_gcd(g, zaehler, nenner);
604 mpz_div(zaehler , zaehler, g);
605 mpz_div(nenner , nenner, g);
612 static int isVectorNeg(
intvec* omega)
616 for(i=omega->
length(); i>=0; i--)
634 mpz_init_set_ui(sing_int, 2147483647);
647 mpz_set_si(zvec, (*weight)[i-1]);
648 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
649 mpz_add(zsum, zsum, zmul);
652 wgrad = mpz_get_ui(zsum);
654 if(mpz_cmp(zsum, sing_int)>0)
659 PrintS(
"\n// ** OVERFLOW in \"MwalkInitialForm\": ");
660 mpz_out_str( stdout, 10, zsum);
661 PrintS(
" is greater than 2147483647 (max. integer representation)");
680 int max = 0, maxtemp;
703 mpz_init_set_ui(sing_int, 2147483647);
716 mpz_set_si(zvec, (*weight)[i-1]);
717 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
718 mpz_add(ztmp, ztmp, zmul);
720 mpz_init_set(result, ztmp);
737 mpz_t
max; mpz_init(max);
738 mpz_t maxtmp; mpz_init(maxtmp);
748 if(mpz_cmp(maxtmp, max)>0)
750 mpz_set(max, maxtmp);
756 if(mpz_cmp(maxtmp, max)==0)
776 ideal Gomega =
idInit(nG, 1);
778 for(i=nG-1; i>=0; i--)
798 PrintS(
"//** the result may be WRONG, i.e. 0!!\n");
808 for(i=nG-1; i>=0; i--)
844 static inline long Mlcm(
long &i1,
long &i2)
846 long temp =
gcd(i1, i2);
847 return ((i1 / temp)* i2);
860 for(i=n-1; i>=0; i--)
862 result += (*a)[
i] * (*b)[
i];
876 for(i=n-1; i>=0; i--)
878 (*result)[
i] = (*a)[
i] - (*b)[
i];
891 for(i=nR-1; i>=0; i--)
908 for (i=0; i<niv; i++)
910 if ((*u)[i] != (*v)[i])
980 (*ivm)[
i] = (*iv)[
i];
984 (*ivm)[i*nR+i-1] = 1;
1001 (*ivm)[
i] = (*iv)[
i];
1007 (*ivm)[j+i*nR] = (*iw)[j+i*nR];
1021 for(i=nR-1; i>=0; i--)
1107 if(pdeg > nV || pdeg <= 0)
1109 WerrorS(
"//** The perturbed degree is wrong!!");
1118 mpz_t *pert_vector = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1119 mpz_t *pert_vector1 = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1123 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1124 mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
1128 int ntemp, maxAi, maxA=0;
1129 for(i=1; i<pdeg; i++)
1131 maxAi = (*ivtarget)[i*nV];
1136 for(j=i*nV+1; j<(i+1)*nV; j++)
1138 ntemp = (*ivtarget)[
j];
1155 mpz_t tot_deg; mpz_init(tot_deg);
1156 mpz_t maxdeg; mpz_init(maxdeg);
1157 mpz_t inveps; mpz_init(inveps);
1160 for(i=nG-1; i>=0; i--)
1163 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1165 mpz_set(tot_deg, maxdeg);
1170 mpz_mul_ui(inveps, tot_deg, maxA);
1171 mpz_add_ui(inveps, inveps, 1);
1175 #ifdef INVEPS_SMALL_IN_MPERTVECTOR 1176 if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
1179 mpz_fdiv_q_ui(inveps, inveps, pdeg);
1184 mpz_out_str(stdout, 10, inveps);
1189 for( i=1; i < pdeg; i++ )
1193 mpz_mul(pert_vector[j], pert_vector[j], inveps);
1194 if((*ivtarget)[i*nV+j]<0)
1196 mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
1200 mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
1207 mpz_init_set_ui(sing_int, 2147483647);
1210 mpz_init_set_ui(check_int, 100000);
1214 mpz_set(ztemp, pert_vector[0]);
1217 mpz_gcd(ztemp, ztemp, pert_vector[i]);
1218 if(mpz_cmp_si(ztemp, 1) == 0)
1223 if(mpz_cmp_si(ztemp, 1) != 0)
1227 mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
1233 if(mpz_cmp(pert_vector[i], check_int)>=0)
1237 mpz_fdiv_q_ui(pert_vector1[j], pert_vector[j], 100);
1248 (*result)[
i] = mpz_get_si(pert_vector1[i]);
1249 if(mpz_cmp(pert_vector1[i], sing_int)>=0)
1259 (*result)[
i] = mpz_get_si(pert_vector[i]);
1260 if(mpz_cmp(pert_vector[i], sing_int)>=0)
1266 PrintS(
"\n// ** OVERFLOW in \"MPertvectors\": ");
1267 mpz_out_str( stdout, 10, pert_vector[i]);
1268 PrintS(
" is greater than 2147483647 (max. integer representation)");
1269 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1277 Print(
"\n// %d element(s) of it is overflow!!", ntrue);
1282 mpz_clear(sing_int);
1283 mpz_clear(check_int);
1318 if(pdeg > nV || pdeg <= 0)
1320 WerrorS(
"//** The perturbed degree is wrong!!");
1325 (*pert_vector)[
i]=(*ivtarget)[
i];
1333 int ntemp, maxAi, maxA=0;
1334 for(i=1; i<pdeg; i++)
1336 maxAi = (*ivtarget)[i*nV];
1337 for(j=i*nV+1; j<(i+1)*nV; j++)
1339 ntemp = (*ivtarget)[
j];
1349 int inveps, tot_deg = 0, maxdeg;
1352 for(i=nG-1; i>=0; i--)
1356 if (maxdeg > tot_deg )
1363 inveps = (tot_deg * maxA) + 1;
1365 #ifdef INVEPS_SMALL_IN_FRACTAL 1367 if(inveps > pdeg && pdeg > 3)
1369 inveps = inveps / pdeg;
1373 PrintS(
"\n// the \"big\" inverse epsilon %d", inveps);
1377 for ( i=1; i < pdeg; i++ )
1381 (*pert_vector)[
j] = inveps*((*pert_vector)[
j]) + (*ivtarget)[i*nV+
j];
1385 int temp = (*pert_vector)[0];
1388 temp =
gcd(temp, (*pert_vector)[i]);
1398 (*pert_vector)[
i] = (*pert_vector)[
i] / temp;
1417 (*ivM)[i*nV +
i] = 1;
1437 (*ivM)[(i+1)*nV - i] = -1;
1448 int nV = ivstart->
length();
1453 (*ivM)[
i] = (*ivstart)[
i];
1457 (*ivM)[i*nV + i-1] = 1;
1468 int nV = ivstart->
length();
1473 (*ivM)[
i] = (*ivstart)[
i];
1481 (*ivM)[(i+1)*nV - i] = -1;
1509 for(i=nV-1; i>=0; i--)
1530 int ntemp, maxAi, maxA=0;
1533 maxAi = (*ivtarget)[i*nV];
1538 for(j=i*nV+1; j<(i+1)*nV; j++)
1540 ntemp = (*ivtarget)[
j];
1550 maxA = maxA + maxAi;
1555 mpz_t tot_deg; mpz_init(tot_deg);
1556 mpz_t maxdeg; mpz_init(maxdeg);
1557 mpz_t inveps; mpz_init(inveps);
1560 for(i=nG-1; i>=0; i--)
1563 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1565 mpz_set(tot_deg, maxdeg);
1571 mpz_mul_ui(inveps, tot_deg, maxA);
1572 mpz_add_ui(inveps, inveps, 1);
1575 #ifdef INVEPS_SMALL_IN_FRACTAL 1576 if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
1578 mpz_cdiv_q_ui(inveps, inveps, nV);
1586 mpz_t *ivtemp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
1587 mpz_t *pert_vector=(mpz_t *)
omAlloc(niv*
sizeof(mpz_t));
1589 for(i=0; i < nV; i++)
1591 mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
1592 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1595 mpz_t ztmp; mpz_init(ztmp);
1602 mpz_mul(ztmp, inveps, ivtemp[j]);
1603 if((*ivtarget)[i*nV+j]<0)
1605 mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
1609 mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
1615 mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
1621 mpz_init_set_ui(sing_int, 2147483647);
1627 mpz_set(ztmp, pert_vector[0]);
1628 for(i=0; i<niv; i++)
1630 mpz_gcd(ztmp, ztmp, pert_vector[i]);
1631 if(mpz_cmp_si(ztmp, 1)==0)
1637 for(i=0; i<niv; i++)
1639 mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
1640 (* result)[
i] = mpz_get_si(pert_vector[i]);
1645 for(i=0; i<niv; i++)
1647 if(mpz_cmp(pert_vector[i], sing_int)>0)
1654 Print(
"\n// Xlev = %d and the %d-th element is",
Xnlev, i+1);
1655 PrintS(
"\n// ** OVERFLOW in \"Mfpertvector\": ");
1656 mpz_out_str( stdout, 10, pert_vector[i]);
1657 PrintS(
" is greater than 2147483647 (max. integer representation)");
1658 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1672 mpz_clear(sing_int);
1711 if (result->m[k]!=
NULL)
1752 for(j=
IDELEMS(idLG)-1; j>=0; j--)
1754 F->m[
i] =
pAdd(F->m[i], idLG->m[j]);
1811 for(i=iva->
length()-1; i>=0; i--)
1813 if((*iva)[
i] - (*ivb)[
i] != 0)
1835 for(i=1; i < (vec->
length()); i++)
1865 if((*vec)[i] == k || (*vec)[i] == -k)
2244 target_weight !=
NULL && G !=
NULL);
2250 mpz_t t_zaehler, t_nenner;
2251 mpz_init(t_zaehler);
2254 mpz_t s_zaehler, s_nenner, temp, MwWd;
2255 mpz_init(s_zaehler);
2262 mpz_set_si(sing_int, 2147483647);
2264 mpz_t sing_int_half;
2265 mpz_init(sing_int_half);
2266 mpz_set_si(sing_int_half, 3*(1073741824/2));
2268 mpz_t deg_w0_p1, deg_d0_p1;
2269 mpz_init(deg_w0_p1);
2270 mpz_init(deg_d0_p1);
2294 for (j=0; j<nRing; j++)
2296 (*diff_weight1)[
j] = (*curr_weight)[
j];
2300 for(j=0; j<nRing; j++)
2302 (*curr_weight)[
j] = (*diff_weight1)[
j];
2304 for(j=0; j<nRing; j++)
2306 (*diff_weight1)[
j] = floor(0.1*(*diff_weight1)[j] + 0.5);
2312 for(j=0; j<nRing; j++)
2314 (*diff_weight1)[
j] = (*curr_weight)[
j];
2319 (*curr_weight)[
j] = (*diff_weight1)[
j];
2321 (*diff_weight1)[
j] = floor(0.1*(*diff_weight1)[j] + 0.5);
2326 intvec* diff_weight =
MivSub(target_weight, curr_weight);
2329 for (j=0; j<nG; j++)
2344 mpz_sub(s_zaehler, deg_w0_p1, MwWd);
2345 if(mpz_cmp(s_zaehler, t_null) != 0)
2348 mpz_sub(s_nenner, MwWd, deg_d0_p1);
2350 if( (mpz_cmp(s_zaehler,t_null) > 0 &&
2351 mpz_cmp(s_nenner, s_zaehler)>=0) ||
2352 (mpz_cmp(s_zaehler, t_null) < 0 &&
2353 mpz_cmp(s_nenner, s_zaehler)<=0))
2356 if (mpz_cmp(s_zaehler, t_null) < 0)
2358 mpz_neg(s_zaehler, s_zaehler);
2359 mpz_neg(s_nenner, s_nenner);
2363 cancel(s_zaehler, s_nenner);
2365 if(mpz_cmp(t_nenner, t_null) != 0)
2367 mpz_mul(sztn, s_zaehler, t_nenner);
2368 mpz_mul(sntz, s_nenner, t_zaehler);
2370 if(mpz_cmp(sztn,sntz) < 0)
2372 mpz_add(t_nenner, t_null, s_nenner);
2373 mpz_add(t_zaehler,t_null, s_zaehler);
2378 mpz_add(t_nenner, t_null, s_nenner);
2379 mpz_add(t_zaehler,t_null, s_zaehler);
2389 mpz_t *
vec=(mpz_t*)
omAlloc(nRing*
sizeof(mpz_t));
2394 if(mpz_cmp(t_nenner, t_null) == 0)
2397 PrintS(
"\n//MwalkNextWeightCC: t_nenner=0\n");
2400 diff_weight =
ivCopy(curr_weight);
2405 if(mpz_cmp_si(t_nenner, 1)==0 && mpz_cmp_si(t_zaehler,1)==0)
2408 diff_weight =
ivCopy(target_weight);
2415 gcd_tmp = (*curr_weight)[0];
2417 for (j=1; j<nRing; j++)
2419 gcd_tmp =
gcd(gcd_tmp, (*curr_weight)[j]);
2427 for (j=0; j<nRing; j++)
2429 gcd_tmp =
gcd(gcd_tmp, (*diff_weight)[j]);
2438 for (j=0; j<nRing; j++)
2440 (*curr_weight)[
j] = (*curr_weight)[
j]/gcd_tmp;
2441 (*diff_weight)[
j] = (*diff_weight)[
j]/gcd_tmp;
2445 #ifdef NEXT_VECTORS_CC 2446 Print(
"\n// gcd of the weight vectors (current and target) = %d", gcd_tmp);
2450 PrintS(
"\n// t_zaehler: "); mpz_out_str( stdout, 10, t_zaehler);
2451 PrintS(
", t_nenner: "); mpz_out_str( stdout, 10, t_nenner);
2459 for (j=0; j<nRing; j++)
2461 mpz_set_si(dcw, (*curr_weight)[j]);
2462 mpz_mul(s_nenner, t_nenner, dcw);
2464 if( (*diff_weight)[j]>0)
2466 mpz_mul_ui(s_zaehler, t_zaehler, (*diff_weight)[j]);
2470 mpz_mul_ui(s_zaehler, t_zaehler, -(*diff_weight)[j]);
2471 mpz_neg(s_zaehler, s_zaehler);
2473 mpz_add(sntz, s_nenner, s_zaehler);
2474 mpz_init_set(vec[j], sntz);
2476 #ifdef NEXT_VECTORS_CC 2477 Print(
"\n// j = %d ==> ", j);
2479 mpz_out_str( stdout, 10, t_nenner);
2480 Print(
" * %d)", (*curr_weight)[j]);
2481 PrintS(
" + ("); mpz_out_str( stdout, 10, t_zaehler);
2482 Print(
" * %d) = ", (*diff_weight)[j]);
2483 mpz_out_str( stdout, 10, s_nenner);
2485 mpz_out_str( stdout, 10, s_zaehler);
2486 PrintS(
" = "); mpz_out_str( stdout, 10, sntz);
2487 Print(
" ==> vector[%d]: ", j); mpz_out_str(stdout, 10, vec[j]);
2496 if(mpz_cmp_si(ggt,1) != 0)
2498 mpz_gcd(ggt, ggt, sntz);
2503 if(mpz_cmp_si(ggt,1) != 0)
2505 for (j=0; j<nRing; j++)
2507 mpz_divexact(vec[j], vec[j], ggt);
2510 #ifdef NEXT_VECTORS_CC 2511 PrintS(
"\n// gcd of elements of the vector: ");
2512 mpz_out_str( stdout, 10, ggt);
2515 for (j=0; j<nRing; j++)
2517 (*diff_weight)[
j] = mpz_get_si(vec[j]);
2522 for (j=0; j<nRing; j++)
2524 if(mpz_cmp(vec[j], sing_int)>=0)
2529 PrintS(
"\n// ** OVERFLOW in \"MwalkNextWeightCC\": ");
2530 mpz_out_str( stdout, 10, vec[j]);
2531 PrintS(
" is greater than 2147483647 (max. integer representation)\n");
2538 delete diff_weight1;
2539 mpz_clear(t_zaehler);
2540 mpz_clear(t_nenner);
2541 mpz_clear(s_zaehler);
2542 mpz_clear(s_nenner);
2547 mpz_clear(deg_w0_p1);
2548 mpz_clear(deg_d0_p1);
2551 mpz_clear(sing_int_half);
2552 mpz_clear(sing_int);
2699 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2701 r->wvhdl[0][i] = (*va)[
i];
2705 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2706 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2750 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2751 r->wvhdl[1] = (
int*)
omAlloc(nv*
sizeof(
int));
2755 r->wvhdl[0][
i] = (*vb)[
i];
2756 r->wvhdl[1][
i] = (*va)[
i];
2761 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2762 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2809 r->wvhdl[0] = (
int*)
omAlloc(nv*nv*
sizeof(
int));
2813 for(i=0; i<nv*nv; i++)
2814 r->wvhdl[0][i] = (*va)[
i];
2818 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2819 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2861 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2862 r->wvhdl[1] = (
int*)
omAlloc(nvs*
sizeof(
int));
2865 for(i=0; i<nvs; i++)
2867 r->wvhdl[1][
i] = (*va)[
i];
2871 r->wvhdl[0][
i] = (*vb)[
i];
2875 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2876 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2920 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2921 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2957 res->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2958 for(
int i=0;
i<nv;
i++)
2959 res->wvhdl[0][
i] = (*va)[
i];
2964 res->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2965 res->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2970 res->block1[0] = nv;
2975 res->block1[1] = nv;
3011 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
3012 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
3073 for(i=hilb->
length()-1; i>=0; i--)
3092 poly p,lm,factor1,factor2;
3112 p =
pCopy(Gomega->m[i]);
3113 lm =
pCopy(Gomega->m[j]);
3160 int nwalk=0, endwalks=0, nnwinC=1;
3162 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3163 ring newRing, oldRing, TargetRing;
3167 intvec* pert_target_vector;
3172 #ifndef BUCHBERGER_ALG 3178 for(i=nV-1; i>0; i--)
3180 (*last_omega)[
i] = 1;
3182 (*last_omega)[0] = 10000;
3187 if(tp_deg > 1 && tp_deg <= nV)
3204 pert_target_vector = target_weight;
3211 target_weight =
Mivlp(nV);
3225 xtnw=xtnw+clock()-to;
3228 #ifdef PRINT_VECTORS 3229 MivString(curr_weight, target_weight, next_weight);
3248 if(
MivComp(next_weight, ivNull) == 1)
3256 if(
MivComp(next_weight, target_weight) == 1)
3259 for(i=nV-1; i>=0; i--)
3261 (*extra_curr_weight)[
i] = (*curr_weight)[
i];
3264 for(i=nV-1; i>=0; i--)
3266 (*curr_weight)[
i] = (*next_weight)[
i];
3275 xtif=xtif+clock()-to;
3289 #ifndef BUCHBERGER_ALG 3290 if(isNolVector(curr_weight) == 0)
3298 #endif // BUCHBERGER_ALG 3317 #ifdef BUCHBERGER_ALG 3322 #endif // BUCHBERGER_ALG 3324 xtstd=xtstd+clock()-to;
3337 xtlift=xtlift+clock()-to;
3353 xtred=xtred+clock()-to;
3386 Print(
"\n// takes %d steps and calls the recursion of level %d:",
3389 F1 =
LastGB(G,curr_weight, tp_deg-1);
3435 delete target_weight;
3452 for(i=
IDELEMS(G)-1; i>=0; i--)
3455 && (G->m[i]->next!=
NULL)
3456 && (G->m[i]->next->next!=
NULL)
3457 && (G->m[i]->next->next->next!=
NULL)
3458 && (G->m[i]->next->next->next->next!=
NULL) )
3472 for(i=
IDELEMS(G)-1; i>=0; i--)
3489 for(i=
IDELEMS(G)-1; i>=0; i--)
3492 && (G->m[i]->next!=
NULL)
3493 && (G->m[i]->next->next!=
NULL))
3528 for (i=nH-1;i>=0; i--)
3549 for(i=nG-1; i>=0; i--)
3617 int mtmp,
m=(*iva)[0];
3619 for(i=ivMat->
length(); i>=0; i--)
3638 mpz_set_si(ndeg, Trandegreebound(
G)+1);
3644 mpz_init_set_si(maxdeg, Trandegreebound(
G));
3647 mpz_pow_ui(ztmp, maxdeg, 2);
3648 mpz_mul_ui(ztmp, ztmp, 2);
3649 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3650 mpz_add(ndeg, ztmp, maxdeg);
3651 mpz_mul_ui(ndeg, ndeg, m);
3657 #endif //UPPER_BOUND 3659 #ifdef INVEPS_SMALL_IN_TRAN 3660 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3662 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3668 mpz_init_set(deg_tmp, ndeg);
3670 mpz_t *ivres=( mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3671 mpz_init_set_si(ivres[nV-1],1);
3673 for(i=nV-2; i>=0; i--)
3675 mpz_init_set(ivres[i], deg_tmp);
3676 mpz_mul(deg_tmp, deg_tmp, ndeg);
3679 mpz_t *ivtmp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3685 mpz_init_set_ui(sing_int, 2147483647);
3694 if( (*ivMat)[i*nV+j] >= 0 )
3696 mpz_mul_ui(ivres[i], ivres[i], (*ivMat)[i*nV+j]);
3700 mpz_mul_ui(ivres[i], ivres[i], -(*ivMat)[i*nV+j]);
3701 mpz_neg(ivres[i], ivres[i]);
3703 mpz_add(ivtmp[j], ivtmp[j], ivres[i]);
3711 (*repr_vector)[
i] = mpz_get_si(ivtmp[i]);
3712 if(mpz_cmp(ivtmp[i], sing_int)>=0)
3719 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3720 mpz_out_str( stdout, 10, ivtmp[i]);
3721 PrintS(
" is greater than 2147483647 (max. integer representation)");
3722 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3728 ivString(repr_vector,
"repvector");
3729 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3738 mpz_clear(sing_int);
3748 static intvec* TranPertVector_lp(ideal
G)
3762 mpz_set_si(ndeg, Trandegreebound(G)+1);
3768 mpz_init_set_si(maxdeg, Trandegreebound(G));
3771 mpz_pow_ui(ztmp, maxdeg, 2);
3772 mpz_mul_ui(ztmp, ztmp, 2);
3773 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3774 mpz_add(ndeg, ztmp, maxdeg);
3783 #ifdef INVEPS_SMALL_IN_TRAN 3784 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3785 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3792 mpz_init_set(deg_tmp, ndeg);
3794 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3795 mpz_init_set_si(ivres[nV-1], 1);
3797 for(i=nV-2; i>=0; i--)
3799 mpz_init_set(ivres[i], deg_tmp);
3800 mpz_mul(deg_tmp, deg_tmp, ndeg);
3804 mpz_init_set_ui(sing_int, 2147483647);
3810 (*repr_vector)[
i] = mpz_get_si(ivres[i]);
3812 if(mpz_cmp(ivres[i], sing_int)>=0)
3818 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3819 mpz_out_str( stdout, 10, ivres[i]);
3820 PrintS(
" is greater than 2147483647 (max. integer representation)");
3821 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3827 ivString(repr_vector,
"repvector");
3828 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3836 mpz_clear(sing_int);
3853 int degtmp, maxdeg = 0;
3864 mpz_init_set_si(ztmp, maxdeg);
3865 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3866 mpz_init_set_si(ivres[nV-1], 1);
3868 for(i=nV-2; i>=0; i--)
3870 mpz_init_set(ivres[i], ztmp);
3871 mpz_mul_ui(ztmp, ztmp, maxdeg);
3874 mpz_t *ivtmp=(mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
3882 if((*M)[i*nV+
j] < 0)
3884 mpz_mul_ui(ztmp, ivres[i], -(*M)[i*nV+j]);
3885 mpz_neg(ztmp, ztmp);
3888 mpz_mul_ui(ztmp, ivres[i], (*M)[i*nV+j]);
3890 mpz_add(ivtmp[j], ivtmp[j], ztmp);
3894 mpz_init_set_ui(sing_int, 2147483647);
3900 (*repvector)[
i] = mpz_get_si(ivtmp[i]);
3901 if(mpz_cmp(ivtmp[i], sing_int)>0)
3907 PrintS(
"\n// ** OVERFLOW in \"Repr.Matrix\": ");
3908 mpz_out_str( stdout, 10, ivtmp[i]);
3909 PrintS(
" is greater than 2147483647 (max. integer representation)");
3910 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repvector)[i]);
3917 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3923 mpz_clear(sing_int);
3943 intvec* orig_target_weight,
int tp_deg,
int npwinc)
3951 clock_t tinput = clock();
3955 int nwalk=0, endwalks=0, nnwinC=1;
3957 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3958 ring newRing, oldRing, TargetRing;
3965 #ifndef BUCHBERGER_ALG 3971 for(i=nV-1; i>0; i--)
3972 (*last_omega)[
i] = 1;
3973 (*last_omega)[0] = 10000;
3978 if(tp_deg > 1 && tp_deg <= nV)
4050 xtif=xtif+clock()-to;
4053 #ifndef BUCHBERGER_ALG 4054 if(isNolVector(curr_weight) == 0)
4062 #endif // BUCHBERGER_ALG 4081 #ifdef BUCHBERGER_ALG 4086 #endif // BUCHBERGER_ALG 4088 xtstd=xtstd+clock()-to;
4101 xtlift=xtlift+clock()-to;
4117 xtred=xtred+clock()-to;
4133 xtnw=xtnw+clock()-to;
4135 #ifdef PRINT_VECTORS 4136 MivString(curr_weight, target_weight, next_weight);
4141 #ifdef TEST_OVERFLOW 4154 if(
MivComp(next_weight, ivNull) == 1)
4161 if(
MivComp(next_weight, target_weight) == 1)
4172 tproc=tproc+clock()-tinput;
4178 G =
Rec_LastGB(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4185 for(i=nV-1; i>=0; i--)
4187 (*curr_weight)[
i] = (*next_weight)[
i];
4213 tproc=tproc+clock()-tinput;
4215 F1 =
Rec_LastGB(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4217 delete target_weight;
4254 xtextra=xtextra+clock()-to;
4296 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
4298 clock_t tostd, tproc;
4302 int nwalk=0, endwalks=0;
4304 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4307 ring newRing, oldRing;
4325 Print(
"\n// Computation of the first std took = %.2f sec",
4326 ((
double) tostd)/1000000);
4342 xtif=xtif+clock()-to;
4372 xtstd=xtstd+clock()-to;
4385 xtlift=xtlift+clock()-to;
4400 xtred=xtred+clock()-to;
4414 xtnw=xtnw+clock()-to;
4416 #ifdef PRINT_VECTORS 4417 MivString(curr_weight, target_weight, next_weight);
4426 #ifdef TEST_OVERFLOW 4427 goto TEST_OVERFLOW_OI;
4446 if(
MivComp(next_weight, ivNull) == 1)
4453 if(
MivComp(next_weight, target_weight) == 1)
4455 if(
MivSame(target_weight, exivlp)==1)
4460 tproc = clock()-xftinput;
4464 G =
Rec_LastGB(G, curr_weight, target_weight, 2,1);
4472 for(i=nV-1; i>=0; i--)
4475 (*curr_weight)[
i] = (*next_weight)[
i];
4479 #ifdef TEST_OVERFLOW 4491 TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
4526 int weight_rad,
int pert_deg)
4529 target_weight !=
NULL && G->m[0] !=
NULL);
4540 (*curr_weight)[
i] = (*orig_M)[
i];
4543 int k=0,weight_norm;
4549 ideal G_test, G_test1, G_test2;
4557 while(weight_norm == 0)
4561 (*next_weight2)[
i] = rand() % 60000 - 30000;
4562 weight_norm = weight_norm + (*next_weight2)[
i]*(*next_weight2)[
i];
4564 weight_norm = 1 + floor(
sqrt(weight_norm));
4568 if((*next_weight2)[i] < 0)
4570 (*next_weight2)[
i] = 1 + (*curr_weight)[
i] + floor(weight_rad*(*next_weight2)[i]/weight_norm);
4574 (*next_weight2)[
i] = (*curr_weight)[
i] + floor(weight_rad*(*next_weight2)[i]/weight_norm);
4584 found_random_weight =
TRUE;
4596 delete curr_weight1;
4614 if(found_random_weight ==
TRUE)
4623 (*result)[
i] = (*next_weight2)[
i];
4630 (*result)[
i] = (*next_weight1)[
i];
4640 (*result)[
i] = (*next_weight2)[
i];
4647 (*result)[
i] = (*next_weight)[
i];
4659 (*result)[
i] = (*next_weight1)[
i];
4666 (*result)[
i] = (*next_weight)[
i];
4674 if(found_random_weight ==
TRUE)
4680 (*result)[
i] = (*next_weight2)[
i];
4687 (*result)[
i] = (*next_weight)[
i];
4695 (*result)[
i] = (*next_weight)[
i];
4701 delete next_weight2;
4704 if(found_random_weight ==
TRUE)
4711 delete next_weight1;
4718 return next_weight1;
4729 int tp_deg,
int npwinc)
4735 int nwalk=0, endwalks=0, nnwinC=1, nlast = 0;
4736 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
4737 ring newRing, oldRing, TargetRing;
4740 #ifndef BUCHBERGER_ALG 4744 for(i=nV-1; i>0; i--)
4746 (*last_omega)[
i] = 1;
4748 (*last_omega)[0] = 10000;
4755 if(tp_deg > 1 && tp_deg <= nV)
4816 xtif = xtif + clock()-to;
4819 #ifndef BUCHBERGER_ALG 4820 if(isNolVector(curr_weight) == 0)
4848 #ifdef BUCHBERGER_ALG 4855 xtstd = xtstd + clock() - to;
4869 xtlift = xtlift + clock() -to;
4887 xtred = xtred + clock() -to;
4905 xtnw = xtnw + clock() - to;
4908 #ifdef PRINT_VECTORS 4909 MivString(curr_weight, target_weight, next_weight);
4923 if(
MivComp(next_weight, ivNull) == 1)
4930 if(
MivComp(next_weight, target_weight) == 1)
4938 G =
REC_GB_Mwalk(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4945 for(i=nV-1; i>=0; i--)
4947 (*curr_weight)[
i] = (*next_weight)[
i];
4970 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4976 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight,tp_deg+1,nnwinC);
4979 delete target_weight;
5027 #ifndef BUCHBERGER_ALG 5043 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5046 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5054 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
5056 ring newRing, oldRing;
5059 #ifndef BUCHBERGER_ALG 5063 for(i=nV-1; i>=0; i--)
5064 (*tmp_weight)[
i] = (*curr_weight)[
i];
5068 for(i=nV-1; i>0; i--)
5069 (*last_omega)[
i] = 1;
5070 (*last_omega)[0] = 10000;
5096 tif = tif + clock()-to;
5107 #ifdef CHECK_IDEAL_MWALK 5108 Print(
"\n// **** Groebnerwalk took %d steps and ", nwalk);
5109 PrintS(
"\n// **** call the rec. Pert. Walk to compute a red GB of:");
5113 if(
MivSame(exivlp, target_weight)==1)
5118 Print(
"\n// time for the last std(Gw) = %.2f sec",
5119 ((
double) (clock()-tim)/1000000));
5134 xtlift = xtlift + clock() - to;
5158 #ifndef BUCHBERGER_ALG 5159 if(isNolVector(curr_weight) == 0)
5167 #endif // BUCHBERGER_ALG 5185 #ifdef BUCHBERGER_ALG 5192 tstd = tstd + clock() - to;
5208 tlift = tlift + clock() - to;
5228 tred = tred + clock() - to;
5232 xtred = xtred + clock() - to;
5247 tnw = tnw + clock() - to;
5249 #ifdef PRINT_VECTORS 5250 MivString(curr_weight, target_weight, next_weight);
5257 PrintS(
"\n// ** The computed vector does NOT stay in Cone!!\n");
5275 if(
MivComp(next_weight, ivNull) == 1)
5281 if(
MivComp(next_weight, target_weight) == 1)
5285 for(i=nV-1; i>=0; i--)
5287 (*tmp_weight)[
i] = (*curr_weight)[
i];
5288 (*curr_weight)[
i] = (*next_weight)[
i];
5300 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5312 ring baseRing,
int reduction,
int printout)
5325 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5326 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5332 int nV = baseRing->N;
5334 ideal Gomega,
M, F, FF, Gomega1, Gomega2, M1;
5336 ring XXRing = baseRing;
5351 (*curr_weight)[
i] = (*orig_M)[
i];
5352 (*target_weight)[
i] = (*target_M)[
i];
5354 #ifndef BUCHBERGER_ALG 5358 for(i=nV-1; i>0; i--)
5360 (*last_omega)[
i] = 1;
5362 (*last_omega)[0] = 10000;
5365 #ifdef CHECK_IDEAL_MWALK 5372 if(target_M->
length() == nV)
5381 if(orig_M->
length() == nV)
5385 newRing=
VMrRefine(target_weight, curr_weight);
5417 tif = tif + clock()-to;
5420 #ifdef CHECK_IDEAL_MWALK 5423 idString(Gomega,
"//** Mwalk: Gomega");
5432 PrintS(
"middle of Cone");
5440 #ifndef BUCHBERGER_ALG 5441 if(isNolVector(curr_weight) == 0)
5453 if(orig_M->
length() == nV)
5457 newRing=
VMrRefine(target_weight, curr_weight);
5466 if(target_M->
length() == nV)
5470 newRing=
VMrRefine(target_weight, curr_weight);
5489 #ifndef BUCHBERGER_ALG 5496 tstd = tstd + clock() - to;
5499 #ifdef CHECK_IDEAL_MWALK 5518 tlift = tlift + clock() - to;
5520 #ifdef CHECK_IDEAL_MWALK 5534 #ifdef CHECK_IDEAL_MWALK 5561 tnw = tnw + clock() - to;
5563 #ifdef PRINT_VECTORS 5566 MivString(curr_weight, target_weight, next_weight);
5571 if(
MivComp(curr_weight,next_weight)==1)
5576 if(
MivComp(target_weight,curr_weight) == 1)
5581 for(i=nV-1; i>=0; i--)
5584 (*curr_weight)[
i] = (*next_weight)[
i];
5595 #ifndef BUCHBERGER_ALG 5599 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5605 Print(
"\n//** Mwalk: Groebner Walk took %d steps.\n",
nstep);
5625 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5626 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5642 if(pert_deg > nV || pert_deg < 1)
5644 WerrorS(
"Invalid perturbation degree.\n");
5648 ideal Gomega,
M, F,FF, Gomega1, Gomega2, M1;
5661 (*curr_weight)[
i] = (*orig_M)[
i];
5662 (*target_weight)[
i] = (*target_M)[
i];
5665 #ifndef BUCHBERGER_ALG 5669 for(i=nV-1; i>0; i--)
5671 (*last_omega)[
i] = 1;
5673 (*last_omega)[0] = 10000;
5677 if(target_M->
length() == nV)
5685 if(orig_M->
length() == nV)
5688 newRing=
VMrRefine(target_weight, curr_weight);
5710 tif = tif + clock()-to;
5717 #ifdef CHECK_IDEAL_MWALK 5720 idString(Gomega,
"//** Mrwalk: Gomega");
5734 #ifndef BUCHBERGER_ALG 5735 if(isNolVector(curr_weight) == 0)
5746 if(orig_M->
length() == nV)
5749 newRing=
VMrRefine(target_weight, curr_weight);
5758 if(target_M->
length() == nV)
5761 newRing=
VMrRefine(target_weight, curr_weight);
5775 #ifndef BUCHBERGER_ALG 5782 tstd = tstd + clock() - to;
5785 #ifdef CHECK_IDEAL_MWALK 5804 tlift = tlift + clock() - to;
5806 #ifdef CHECK_IDEAL_MWALK 5820 tstd = tstd + clock() - to;
5823 #ifdef CHECK_IDEAL_MWALK 5850 tnw = tnw + clock() - to;
5858 tif = tif + clock()-to;
5868 if(target_M->
length() == nV)
5882 tnw = tnw + clock() - to;
5890 tif = tif + clock()-to;
5896 if(
MivComp(next_weight, ivNull) == 1 ||
MivComp(target_weight,curr_weight) == 1)
5904 if(
MivComp(curr_weight,next_weight)==1)
5909 #ifdef PRINT_VECTORS 5912 MivString(curr_weight, target_weight, next_weight);
5916 for(i=nV-1; i>=0; i--)
5918 (*curr_weight)[
i] = (*next_weight)[
i];
5927 #ifndef BUCHBERGER_ALG 5932 Print(
"\n//** Mrwalk: Groebner Walk took %d steps.\n",
nstep);
5935 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5969 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5971 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5977 int i, ntwC=1, ntestw=1, nV =
currRing->N;
5980 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
5982 WerrorS(
"Invalid perturbation degree.\n");
5987 ideal Gomega,
M, F, FF,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5988 ring newRing, oldRing, TargetRing;
5992 intvec* orig_target = target_weight;
5993 intvec* pert_target_vector = target_weight;
5996 #ifndef BUCHBERGER_ALG 6003 for(i=nV-1; i>0; i--)
6004 (*last_omega)[
i] = 1;
6005 (*last_omega)[0] = 10000;
6012 if(
MivComp(curr_weight, iv_dp) == 1)
6046 if(op_deg != 1)
delete iv_M_dp;
6051 if(tp_deg > 1 && tp_deg <= nV)
6063 if(
MivSame(target_weight, exivlp) == 1)
6074 pert_target_vector = target_weight;
6080 Print(
"\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6081 #ifdef PRINT_VECTORS 6082 ivString(curr_weight,
"//** Mpwalk: new current weight");
6083 ivString(target_weight,
"//** Mpwalk: new target weight");
6096 tif = tif + clock()-to;
6098 #ifdef CHECK_IDEAL_MWALK 6101 idString(Gomega,
"//** Mpwalk: Gomega");
6104 if(reduction == 0 &&
nstep > 1)
6117 if(endwalks ==
TRUE)
6128 #ifndef BUCHBERGER_ALG 6129 if(isNolVector(curr_weight) == 0)
6133 #endif // BUCHBERGER_ALG 6157 PrintS(
"\n// compute a rGB of Gw:\n");
6159 #ifndef BUCHBERGER_ALG 6169 #ifdef BUCHBERGER_ALG 6176 if(endwalks ==
TRUE)
6179 xtstd = xtstd+clock()-to;
6185 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
6186 ((
double) clock())/1000000 -((
double)tim) /1000000);
6194 tstd=tstd+clock()-to;
6197 #ifdef CHECK_IDEAL_MWALK 6215 if(endwalks ==
FALSE)
6216 tlift = tlift+clock()-to;
6220 #ifdef CHECK_IDEAL_MWALK 6242 PrintS(
"\n //** Mpwalk: reduce the Groebner basis.\n");
6249 if(endwalks ==
FALSE)
6250 tred = tred+clock()-to;
6256 if(endwalks ==
TRUE)
6268 #ifdef PRINT_VECTORS 6271 MivString(curr_weight, target_weight, next_weight);
6284 if(
MivComp(next_weight, ivNull) == 1){
6290 if(
MivComp(next_weight, target_weight) == 1)
6293 for(i=nV-1; i>=0; i--)
6294 (*curr_weight)[
i] = (*next_weight)[
i];
6302 if(
MivSame(orig_target, exivlp) == 1) {
6326 if( ntestw != 1 || ntwC == 0)
6328 if(ntestw != 1 && printout >2)
6330 ivString(pert_target_vector,
"tau");
6331 PrintS(
"\n// ** perturbed target vector doesn't stay in cone!!");
6340 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1){
6349 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6372 delete target_weight;
6381 TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6389 Print(
"\n//** Mpwalk: Perturbation Walk took %d steps.\n",
nstep);
6398 int op_deg,
int tp_deg,
int nP,
int reduction,
int printout)
6410 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
6412 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
6418 int i, ntwC=1, ntestw=1, nV =
currRing->N;
6428 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
6430 WerrorS(
"Invalid perturbation degree.\n");
6436 ideal Gomega,
M, F, FF,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
6437 ring newRing, oldRing, TargetRing;
6446 (*curr_weight)[
i] = (*orig_M)[
i];
6447 (*target_weight)[
i] = (*target_M)[
i];
6449 intvec* orig_target = target_weight;
6450 intvec* pert_target_vector = target_weight;
6453 #ifndef BUCHBERGER_ALG 6460 for(i=nV-1; i>0; i--)
6461 (*last_omega)[
i] = 1;
6462 (*last_omega)[0] = 10000;
6467 if(orig_M->
length() == nV)
6469 if(
MivComp(curr_weight, iv_dp) == 1)
6525 if(op_deg != 1)
delete iv_M_dp;
6530 if(target_M->
length() == nV)
6532 if(tp_deg > 1 && tp_deg <= nV)
6541 if(
MivSame(target_weight, exivlp) == 1)
6552 pert_target_vector = target_weight;
6559 if(tp_deg > 1 && tp_deg <= nV)
6569 Print(
"\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6570 ivString(curr_weight,
"//** Mprwalk: new current weight");
6571 ivString(target_weight,
"//** Mprwalk: new target weight");
6579 tif = tif + clock()-to;
6585 #ifdef CHECK_IDEAL_MWALK 6588 idString(Gomega,
"//** Mprwalk: Gomega");
6592 if(reduction == 0 &&
nstep > 1)
6605 if(endwalks ==
TRUE)
6616 #ifndef BUCHBERGER_ALG 6617 if(isNolVector(curr_weight) == 0)
6621 #endif // BUCHBERGER_ALG 6625 if(target_M->
length() == nV)
6642 if(endwalks ==
TRUE)
6651 PrintS(
"\n// compute a rGB of Gw:\n");
6653 #ifndef BUCHBERGER_ALG 6663 #ifdef BUCHBERGER_ALG 6669 #ifdef CHECK_IDEAL_MWALK 6676 if(endwalks ==
TRUE)
6678 xtstd = xtstd+clock()-to;
6680 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
6681 ((
double) clock())/1000000 -((
double)tim) /1000000);
6685 tstd=tstd+clock()-to;
6699 if(endwalks ==
FALSE)
6700 tlift = tlift+clock()-to;
6704 #ifdef CHECK_IDEAL_MWALK 6726 PrintS(
"\n //** Mprwalk: reduce the Groebner basis.\n");
6733 if(endwalks ==
FALSE)
6734 tred = tred+clock()-to;
6741 if(endwalks ==
TRUE)
6750 tnw = tnw + clock() - to;
6759 tif = tif + clock()-to;
6767 PrintS(
"\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
6771 if(target_M->
length() == nV)
6784 tnw = tnw + clock() - to;
6792 tif = tif + clock()-to;
6797 #ifdef PRINT_VECTORS 6800 MivString(curr_weight, target_weight, next_weight);
6812 if(
MivComp(next_weight, ivNull) == 1){
6818 if(
MivComp(next_weight, target_weight) == 1)
6821 for(i=nV-1; i>=0; i--)
6822 (*curr_weight)[
i] = (*next_weight)[
i];
6830 if(target_M->
length() == nV)
6832 if(
MivSame(orig_target, exivlp) == 1)
6855 if(ntestw != 1 || ntwC == 0)
6857 if(ntestw != 1 && printout > 2)
6859 #ifdef PRINT_VECTORS 6860 ivString(pert_target_vector,
"tau");
6862 PrintS(
"\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
6871 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1 || target_M->
length() != nV)
6875 PrintS(
"\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
6884 PrintS(
"\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
6888 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6913 delete target_weight;
6922 TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6931 Print(
"\n//** Mprwalk: Perturbation Walk took %d steps.\n",
nstep);
6948 (*ivM)[i*nV +
j] = 1;
6966 Print(
"\n\n// Entering the %d-th recursion:", nlev);
6969 ring new_ring, testring;
6971 ideal Gomega, Gomega1, Gomega2, FF, F, Gresult, Gresult1, G1, Gt;
6974 #ifndef BUCHBERGER_ALG 6983 for(i = nV -1; i>=0; i--)
6985 (*omtmp)[
i] = (*ivtarget)[
i];
6991 for(i=nV-1; i>0; i--)
6992 (*last_omega)[
i] = 1;
6993 (*last_omega)[0] = 10000;
6996 for(i=0; i<nV; i++) {
6997 if(Xsigma->
length() == nV)
6998 (*omega)[
i] = (*Xsigma)[
i];
7000 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
7002 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
7005 if(nlev == 1)
Xcall = 1;
7012 #ifdef FIRST_STEP_FRACTAL 7015 if((nlev == 1 &&
Xcall == 0) || (nlev == 2 &&
Xngleich == 1))
7025 NEXT_VECTOR_FRACTAL:
7032 xtnw=xtnw+clock()-to;
7038 if (
MivComp(next_vect, omega2) == 1)
7044 Print(
"\n//** rec_fractal_call: Perturb the both vectors with degree %d.",nlev);
7051 if(ivtarget->
length() == nV)
7070 if(ivtarget->
length() == nV)
7089 for(i=nV-1; i>=0; i--) {
7090 (*omega2)[
i] = (*Xtau)[nV+
i];
7091 (*omega)[
i] = (*Xsigma)[nV+
i];
7102 xtnw=xtnw+clock()-to;
7106 #ifdef PRINT_VECTORS 7109 MivString(omega, omega2, next_vect);
7119 if(ivtarget->
length() == nV)
7134 #ifdef TEST_OVERFLOW 7136 Gt =
NULL;
return(Gt);
7140 Print(
"\n//** rec_fractal_call: Applying Buchberger's algorithm in ring r = %s;",
7149 xtextra=xtextra+clock()-to;
7157 Print(
"\n//** rec_fractal_call: Overflow. (4) Leaving the %d-th recursion with %d steps.\n",
7175 if (
MivComp(next_vect, XivNull) == 1)
7177 if(ivtarget->
length() == nV)
7202 Print(
"\n//** rec_fractal_call: Correct cone. (5) Leaving the %d-th recursion with %d steps.\n",
7207 idString(Gt,
"//** rec_fractal_call: Gt");
7215 PrintS(
"\n//** rec_fractal_call: Wrong cone. Tau doesn't stay in the correct cone.\n");
7218 #ifndef MSTDCC_FRACTAL 7220 if(ivtarget->
length() == nV)
7228 #ifdef TEST_OVERFLOW 7230 Gt =
NULL;
return(Gt);
7233 if(
MivSame(Xtau, Xtautmp) == 1)
7237 PrintS(
"\n//** rec_fractal_call: Updated vectors are equal to the old vectors.\n");
7240 goto FRACTAL_MSTDCC;
7246 for(i=nV-1; i>=0; i--)
7247 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
7252 goto NEXT_VECTOR_FRACTAL;
7258 Print(
"\n//** rec_fractal_call: Wrong cone. Applying Buchberger's algorithm in ring = %s.\n",
7266 xtextra=xtextra+clock()-to;
7271 if(ivtarget->
length() == nV)
7295 if(ivtarget->
length() == nV)
7314 Print(
"\n//** rec_fractal_call: Vectors updated. (6) Leaving the %d-th recursion with %d steps.\n",
7326 for(i=nV-1; i>=0; i--) {
7328 (*omega)[
i] = (*next_vect)[
i];
7337 xtif=xtif+clock()-to;
7339 #ifdef CHECK_IDEAL_MWALK 7342 idString(Gomega,
"//** rec_fractal_call: Gomega");
7356 goto NEXT_VECTOR_FRACTAL;
7360 #ifndef BUCHBERGER_ALG 7361 if(isNolVector(omega) == 0)
7367 if(ivtarget->
length() == nV)
7390 PrintS(
"\n//** rec_fractal_call: Maximal recursion depth.\n");
7395 #ifdef BUCHBERGER_ALG 7402 xtstd=xtstd+clock()-to;
7411 #ifdef CHECK_IDEAL_MWALK 7414 idString(Gresult,
"//** rec_fractal_call: M");
7429 xtlift=xtlift+clock()-to;
7431 #ifdef CHECK_IDEAL_MWALK 7434 idString(F,
"//** rec_fractal_call: F");
7463 int weight_rad,
int reduction,
int printout)
7469 ring new_ring, testring;
7471 ideal Gomega, Gomega1, Gomega2, F, FF, Gresult, Gresult1, G1, Gt;
7476 #ifndef BUCHBERGER_ALG 7488 for(
i = nV -1;
i>=0;
i--)
7490 (*omtmp)[
i] = (*ivtarget)[
i];
7494 for(
i=nV-1;
i>0;
i--)
7495 (*last_omega)[
i] = 1;
7496 (*last_omega)[0] = 10000;
7499 for(
i=0;
i<nV;
i++) {
7500 if(Xsigma->
length() == nV)
7501 (*omega)[
i] = (*Xsigma)[
i];
7503 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
7505 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+
i];
7508 if(nlev == 1)
Xcall = 1;
7515 #ifdef FIRST_STEP_FRACTAL 7520 if((nlev == 1 &&
Xcall == 0) || (nlev == 2 &&
Xngleich == 1))
7530 NEXT_VECTOR_FRACTAL:
7537 xtnw=xtnw+clock()-to;
7543 PrintS(
"\n**// rec_r_fractal_call: there is a polynomial in Gomega with at least 3 monomials.\n");
7552 xtnw=xtnw+clock()-to;
7562 xtnw=xtnw+clock()-to;
7570 if (
MivComp(next_vect, omega2) == 1)
7576 Print(
"\n//** rec_r_fractal_call: Perturb both vectors with degree %d.",nlev);
7581 if(ivtarget->
length() == nV)
7600 if(ivtarget->
length() == nV)
7616 if(ivtarget->
length() > nV)
7624 for(
i=nV-1;
i>=0;
i--)
7626 (*omega2)[
i] = (*Xtau)[nV+
i];
7627 (*omega)[
i] = (*Xsigma)[nV+
i];
7639 xtnw=xtnw+clock()-to;
7651 xtnw=xtnw+clock()-to;
7662 xtnw=xtnw+clock()-to;
7667 #ifdef PRINT_VECTORS 7670 MivString(omega, omega2, next_vect);
7681 if(ivtarget->
length() == nV)
7700 #ifdef TEST_OVERFLOW 7707 Print(
"\n//** rec_r_fractal_call: applying Buchberger's algorithm in ring r = %s;",
7716 xtextra=xtextra+clock()-to;
7724 Print(
"\n//** rec_r_fractal_call: (1) Leaving the %d-th recursion with %d steps.\n",
7739 if (
MivComp(next_vect, XivNull) == 1)
7743 if(ivtarget->
length() == nV)
7768 Print(
"\n//** rec_r_fractal_call: (2) Leaving the %d-th recursion with %d steps.\n",
7778 Print(
"\n//** rec_r_fractal_call: target weight doesn't stay in the correct cone.\n");
7781 #ifndef MSTDCC_FRACTAL 7782 #ifdef PRINT_VECTORS 7789 if(ivtarget->
length() == nV)
7797 #ifdef TEST_OVERFLOW 7799 Gt =
NULL;
return(Gt);
7802 if(
MivSame(Xtau, Xtautmp) == 1)
7806 goto FRACTAL_MSTDCC;
7811 #ifdef PRINT_VECTORS 7818 for(
i=nV-1;
i>=0;
i--)
7819 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+
i];
7825 goto NEXT_VECTOR_FRACTAL;
7831 Print(
"\n//** rec_r_fractal_call: apply Buchberger's algorithm in ring = %s.\n",
7839 xtextra=xtextra+clock()-to;
7844 if(ivtarget->
length() == nV)
7868 if(ivtarget->
length() == nV)
7887 Print(
"\n//** rec_r_fractal_call: (3) Leaving the %d-th recursion with %d steps.\n",
7899 for(
i=nV-1;
i>=0;
i--)
7901 (*altomega)[
i] = (*omega)[
i];
7902 (*omega)[
i] = (*next_vect)[
i];
7911 xtif=xtif+clock()-to;
7915 #ifdef CHECK_IDEAL_MWALK 7918 idString(Gomega,
"//** rec_r_fractal_call: Gomega");
7932 goto NEXT_VECTOR_FRACTAL;
7936 #ifndef BUCHBERGER_ALG 7937 if(isNolVector(omega) == 0)
7942 if(ivtarget->
length() == nV)
7966 #ifdef BUCHBERGER_ALG 7973 xtstd=xtstd+clock()-to;
7982 #ifdef CHECK_IDEAL_MWALK 7985 idString(Gresult,
"//** rec_r_fractal_call: M");
8000 xtlift=xtlift+clock()-to;
8002 #ifdef CHECK_IDEAL_MWALK 8005 idString(F,
"//** rec_r_fractal_call: F");
8058 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8063 XivNull =
new intvec(nV);
8064 Xivinput = ivtarget;
8078 #ifdef FIRST_STEP_FRACTAL 8080 for(i=
IDELEMS(Gw)-1; i>=0; i--)
8083 && (Gw->m[i]->next!=
NULL)
8084 && (Gw->m[i]->next->next!=
NULL))
8088 if(ivstart->
length() == nV)
8090 if(
MivSame(ivstart, iv_dp) != 1)
8115 if(ivtarget->
length() == nV)
8117 if(
MivComp(ivtarget, Xivlp) != 1)
8155 if(ivtarget->
length() == nV)
8178 xftostd=xftostd+clock()-to;
8199 TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8200 xtlift, xtred, xtnw);
8205 Print(
"\n// the numbers of Overflow_Error (%d)",
nnflow);
8222 int weight_rad,
int reduction,
int printout)
8245 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8250 XivNull =
new intvec(nV);
8251 Xivinput = ivtarget;
8265 #ifdef FIRST_STEP_FRACTAL 8267 for(i=
IDELEMS(Gw)-1; i>=0; i--)
8270 && (Gw->m[i]->next!=
NULL)
8271 && (Gw->m[i]->next->next!=
NULL))
8275 if(ivstart->
length() == nV)
8277 if(
MivSame(ivstart, iv_dp) != 1)
8302 if(ivtarget->
length() == nV)
8304 if(
MivComp(ivtarget, Xivlp) != 1)
8342 if(ivtarget->
length() == nV)
8365 xftostd=xftostd+clock()-to;
8386 TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8387 xtlift, xtred, xtnw);
8392 Print(
"\n// the numbers of Overflow_Error (%d)",
nnflow);
8408 clock_t mtim = clock();
8416 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8417 clock_t tinput = clock();
8419 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
8420 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
8421 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
8423 ring newRing, oldRing, lpRing;
8431 int nGB, endwalks = 0, nwalkpert=0;
8434 #ifndef BUCHBERGER_ALG 8439 for(
i=nV-1;
i>0;
i--)
8440 (*last_omega)[
i] = 1;
8441 (*last_omega)[0] = 10000;
8445 for(
i=nV-1;
i>=0;
i--)
8446 (*target_weight)[
i] = (*target_tmp)[
i];
8455 if(
MivComp(curr_weight, iv_dp) == 1)
8471 #ifdef REPRESENTATION_OF_SIGMA 8477 if(
MivComp(curr_weight, iv_dp) == 1)
8478 MDp = MatrixOrderdp(nV);
8482 curr_weight = RepresentationMatrix_Dp(G, MDp);
8499 tostd=tostd+clock()-to;
8502 goto COMPUTE_NEW_VECTOR;
8521 #ifndef BUCHBERGER_ALG 8522 if(isNolVector(curr_weight) == 0)
8526 #endif // BUCHBERGER_ALG 8543 #ifdef BUCHBERGER_ALG 8548 #endif // BUCHBERGER_ALG 8550 tstd=tstd+clock()-to;
8566 tlift=tlift+clock()-to;
8583 tred=tred+clock()-to;
8600 #ifdef PRINT_VECTORS 8601 MivString(curr_weight, target_weight, next_weight);
8613 OMEGA_OVERFLOW_TRAN_NEW:
8616 #ifdef TEST_OVERFLOW 8625 if(
MivSame(target_tmp, iv_lp) == 1)
8643 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0){
8652 G =
LastGB(G1, curr_weight, nV-1);
8660 npert[endwalks]=nwalk-npert_tmp;
8669 if(
MivComp(next_weight, target_weight) == 1 ||
8670 MivComp(next_weight, curr_weight) == 1 )
8676 npert[endwalks]=nwalk-npert_tmp;
8682 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1){
8689 if(
MivSame(target_tmp, iv_lp) == 1)
8736 if(p->next !=
NULL &&
8737 p->next->next !=
NULL &&
8738 p->next->next->next !=
NULL)
8743 (*vector_tmp)[
i] = (*target_weight)[
i];
8745 delete target_weight;
8748 if(
MivComp(vector_tmp, target_weight)==1)
8753 goto OMEGA_OVERFLOW_TRAN_NEW;
8760 goto OMEGA_OVERFLOW_TRAN_NEW;
8770 if(plength3 ==
FALSE)
8795 goto COMPUTE_NEW_VECTOR;
8799 for(
i=nV-1;
i>=0;
i--)
8800 (*curr_weight)[
i] = (*next_weight)[
i];
8804 #ifdef TEST_OVERFLOW 8835 ideal TranMrImprovwalk(ideal
G,
intvec* curr_weight,
intvec* target_tmp,
int nP,
int weight_rad,
int pert_deg)
8838 clock_t mtim = clock();
8846 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8847 clock_t tinput = clock();
8849 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
8850 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
8851 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
8853 ring newRing, oldRing, lpRing;
8861 int weight_norm, nGB, endwalks = 0, nwalkpert=0, npertstep=0;
8864 #ifndef BUCHBERGER_ALG 8869 for(
i=nV-1;
i>0;
i--)
8871 (*last_omega)[
i] = 1;
8873 (*last_omega)[0] = 10000;
8877 for(
i=nV-1;
i>=0;
i--)
8879 (*target_weight)[
i] = (*target_tmp)[
i];
8888 if(
MivComp(curr_weight, iv_dp) == 1)
8911 #ifdef REPRESENTATION_OF_SIGMA 8917 if(
MivComp(curr_weight, iv_dp) == 1)
8919 MDp = MatrixOrderdp(nV);
8925 curr_weight = RepresentationMatrix_Dp(
G, MDp);
8946 tostd=tostd+clock()-to;
8949 goto COMPUTE_NEW_VECTOR;
8968 #ifndef BUCHBERGER_ALG 8969 if(isNolVector(curr_weight) == 0)
8977 #endif // BUCHBERGER_ALG 8997 #ifdef BUCHBERGER_ALG 9004 tstd=tstd+clock()-to;
9019 tlift=tlift+clock()-to;
9036 tred=tred+clock()-to;
9129 #ifdef PRINT_VECTORS 9130 MivString(curr_weight, target_weight, next_weight);
9142 OMEGA_OVERFLOW_TRAN_NEW:
9145 #ifdef TEST_OVERFLOW 9149 #ifdef CHECK_IDEAL_MWALK 9154 if(
MivSame(target_tmp, iv_lp) == 1)
9183 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0)
9194 G =
LastGB(G1, curr_weight, nV-1);
9202 npert[endwalks]=nwalk-npert_tmp;
9211 if(
MivComp(next_weight, target_weight) == 1 ||
MivComp(next_weight, curr_weight) == 1 )
9217 npert[endwalks]=nwalk-npert_tmp;
9223 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1)
9231 if(
MivSame(target_tmp, iv_lp) == 1)
9287 if(p->next !=
NULL &&
9288 p->next->next !=
NULL &&
9289 p->next->next->next !=
NULL)
9295 (*vector_tmp)[
i] = (*target_weight)[
i];
9297 delete target_weight;
9300 if(
MivComp(vector_tmp, target_weight)==1)
9305 goto OMEGA_OVERFLOW_TRAN_NEW;
9312 goto OMEGA_OVERFLOW_TRAN_NEW;
9322 if(plength3 ==
FALSE)
9348 goto COMPUTE_NEW_VECTOR;
9352 for(
i=nV-1;
i>=0;
i--)
9354 (*curr_weight)[
i] = (*next_weight)[
i];
9358 #ifdef TEST_OVERFLOW 9371 Print(
"\n// Computation took %d steps and %.2f sec", nwalk, ((
double) (clock()-mtim)/1000000));
9373 TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
9392 clock_t tinput=clock();
9397 if(tp_deg < 1 || tp_deg > nV)
9399 WerrorS(
"Invalid perturbation degree.\n");
9403 int nwalk=0, endwalks=0, ntestwinC=1;
9404 int tp_deg_tmp = tp_deg;
9405 ideal Gomega,
M, F,
G, M1, F1, Gomega1, Gomega2, G1;
9406 ring newRing, oldRing, TargetRing;
9439 target_weight =
Mivlp(nV);
9449 if(tp_deg != tp_deg_tmp)
9459 #ifndef BUCHBERGER_ALG 9464 for(i=nV-1; i>0; i--)
9466 (*last_omega)[
i] = 1;
9468 (*last_omega)[0] = 10000;
9488 xtif=xtif+clock()-to;
9491 #ifndef BUCHBERGER_ALG 9492 if(isNolVector(curr_weight) == 0)
9525 #ifdef BUCHBERGER_ALG 9530 #endif // BUCHBERGER_ALG 9532 xtstd=xtstd+clock()-to;
9548 xtlift=xtlift+clock()-to;
9565 xtred=xtred+clock()-to;
9580 xtnw=xtnw+clock()-to;
9582 #ifdef PRINT_VECTORS 9583 MivString(curr_weight, target_weight, next_weight);
9592 tproc = tproc+clock()-tinput;
9605 if(
MivComp(next_weight, ivNull) == 1)
9611 if(
MivComp(next_weight, target_weight) == 1)
9615 for(i=nV-1; i>=0; i--)
9618 (*curr_weight)[
i] = (*next_weight)[
i];
9647 xtextra=xtextra+clock()-to;
9657 tproc = tproc+clock()-tinput;
9670 delete target_weight;
9691 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
9693 clock_t tostd, tproc;
9698 int nwalk=0, endwalks=0;
9699 int op_tmp = op_deg;
9700 ideal Gomega,
M, F,
G, Gomega1, Gomega2, M1, F1;
9701 ring newRing, oldRing;
9708 #ifndef BUCHBERGER_ALG 9711 intvec* cw_tmp = curr_weight;
9715 for(i=nV-1; i>0; i--)
9717 (*last_omega)[
i] = 1;
9719 (*last_omega)[0] = 10000;
9733 if(
MivComp(curr_weight, iv_dp) == 1)
9736 if(op_tmp == op_deg)
9748 if(op_tmp == op_deg)
9772 curr_weight = cw_tmp;
9804 xtif=xtif+clock()-to;
9809 for(i=nV-1; i>=0; i--)
9810 (*curr_weight)[
i] = (*extra_curr_weight)[
i];
9811 delete extra_curr_weight;
9817 #ifndef BUCHBERGER_ALG 9818 if(isNolVector(curr_weight) == 0)
9826 #endif // BUCHBERGER_ALG 9846 #ifdef BUCHBERGER_ALG 9851 #endif // BUCHBERGER_ALG 9853 xtstd=xtstd+clock()-to;
9867 xtlift=xtlift+clock()-to;
9886 xtred=xtred+clock()-to;
9901 xtnw=xtnw+clock()-to;
9903 #ifdef PRINT_VECTORS 9904 MivString(curr_weight, target_weight, next_weight);
9927 if(
MivComp(next_weight, ivNull) == 1)
9934 if(
MivComp(next_weight, target_weight) == 1)
9936 if(tp_deg == 1 ||
MivSame(target_weight, exivlp) == 0)
9943 tproc = clock()-xftinput;
9956 for(i=nV-1; i>=0; i--)
9959 (*curr_weight)[
i] = (*next_weight)[
i];
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
void id_Normalize(ideal I, const ring r)
normialize all polys in id
KINLINE TObject ** initR()
intvec * MivMatrixOrder(intvec *iv)
static int test_w_in_ConeCC(ideal G, intvec *iv)
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)
#define idDelete(H)
delete an ideal
ideal Mpwalk(ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP, int reduction, int printout)
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 ideal rec_r_fractal_call(ideal G, int nlev, intvec *ivtarget, int weight_rad, int reduction, int printout)
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)
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
intvec * ivCopy(const intvec *o)
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 ring VMatrRefine(intvec *va, intvec *vb)
#define pEqualPolys(p1, p2)
poly singclap_pdivide(poly f, poly g, const ring r)
void Set_Error(BOOLEAN f)
int(* posInT)(const TSet T, const int tl, LObject &h)
static void VMrDefaultlp(void)
static long MivDotProduct(intvec *a, intvec *b)
int posInT0(const TSet, const int length, LObject &)
static int MivAbsMaxArg(intvec *vec)
static void cancel(mpz_t zaehler, mpz_t nenner)
intvec * MPertVectorslp(ideal G, intvec *ivtarget, int pdeg)
ideal Mfwalk(ideal G, intvec *ivstart, intvec *ivtarget, int reduction, int printout)
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)
const CanonicalForm CFMap CFMap & N
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)
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
static ideal idHeadCC(ideal h)
int M3ivSame(intvec *temp, intvec *u, intvec *v)
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
ideal Mwalk(ideal Go, intvec *orig_M, intvec *target_M, ring baseRing, int reduction, int printout)
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)
#define pIsConstant(p)
like above, except that Comp might be != 0
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)
static ideal Rec_LastGB(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
static unsigned pLength(poly a)
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)
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
static ideal rec_fractal_call(ideal G, int nlev, intvec *ivtarget, int reduction, int printout)
#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)
static int isNegNolVector(intvec *hilb)
const Variable & v
< [in] a sqrfree bivariate poly
static long gcd(const long a, const long b)
static int lengthpoly(ideal G)
static intvec * MExpPol(poly f)
static void DefRingPar(intvec *va)
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
static ideal middleOfCone(ideal G, ideal Gomega)
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
void rDelete(ring r)
unconditionally deletes fields in 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
void updateS(BOOLEAN toT, kStrategy strat)
static void idString(ideal L, const char *st)
intvec * MivMatrixOrderdp(int nV)
#define SI_SAVE_OPT(A, B)
void completeReduce(kStrategy strat, BOOLEAN withT)
ideal MAltwalk2(ideal Go, intvec *curr_weight, intvec *target_weight)
ideal Mrwalk(ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int pert_deg, int reduction, int printout)
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 int maxlengthpoly(ideal G)
static intset initec(int maxnr)
ideal Mprwalk(ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int op_deg, int tp_deg, int nP, int reduction, int printout)
void initEcartNormal(TObject *h)
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
ideal MwalkAlt(ideal Go, intvec *curr_weight, intvec *target_weight)
static ideal idVec2Ideal(poly vec)
static void ivString(intvec *iv, const char *ch)
ideal MwalkInitialForm(ideal G, intvec *ivw)
ideal Mfrwalk(ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad, int reduction, int printout)
static ring VMrRefine(intvec *va, intvec *vb)
intvec * MivMatrixOrderlp(int nV)
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)