12 #define BUCHBERGER_ALG //we use the improved Buchberger alg. 19 #define CHECK_IDEAL_MWALK //to print intermediate results 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 29 #define MSTDCC_FRACTAL // apply Buchberger alg to compute a red GB, if tau doesn't stay in the correct cone 87 #include <sys/types.h> 112 return (
unsigned long*)
omAlloc0(maxnr*
sizeof(
unsigned long));
116 return (
int*)
omAlloc0(maxnr*
sizeof(
int));
357 ideal shdl=strat->
Shdl;
365 static void TimeString(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
366 clock_t tlf,clock_t tred, clock_t tnw,
int step)
368 double totm = ((double) (clock() - tinput))/1000000;
369 double ostd,mostd, mif, mstd, mlf, mred, mnw, mxif,mxstd,mxlf,mxred,mxnw,tot;
371 Print(
"\n// total time = %.2f sec", totm);
372 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
373 mostd=((((
double) tostd)/1000000)/totm)*100);
374 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
375 mif=((((
double) tif)/1000000)/totm)*100);
376 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
377 mstd=((((
double) tstd)/1000000)/totm)*100);
378 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
379 mlf=((((
double) tlf)/1000000)/totm)*100);
380 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
381 mred=((((
double) tred)/1000000)/totm)*100);
382 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
383 mnw=((((
double) tnw)/1000000)/totm)*100);
384 PrintS(
"\n Time for the last step:");
385 Print(
"\n// xinfo = %.2f sec = %.2f", ((
double)
xtif)/1000000,
386 mxif=((((
double) xtif)/1000000)/totm)*100);
387 Print(
"\n// xstd = %.2f sec = %.2f", ((
double)
xtstd)/1000000,
388 mxstd=((((
double) xtstd)/1000000)/totm)*100);
389 Print(
"\n// xlift = %.2f sec = %.2f", ((
double)
xtlift)/1000000,
390 mxlf=((((
double) xtlift)/1000000)/totm)*100);
391 Print(
"\n// xired = %.2f sec = %.2f", ((
double)
xtred)/1000000,
392 mxred=((((
double) xtred)/1000000)/totm)*100);
393 Print(
"\n// xnextw= %.2f sec = %.2f", ((
double)
xtnw)/1000000,
394 mxnw=((((
double) xtnw)/1000000)/totm)*100);
396 tot=mostd+mif+mstd+mlf+mred+mnw+mxif+mxstd+mxlf+mxred+mxnw;
397 double res = (double) 100 - tot;
398 Print(
"\n// &%d&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f(%.2f)\\ \\",
399 step, ostd, totm, mostd,mif,mstd,mlf,mred,mnw,mxif,mxstd,mxlf,mxred,mxnw,tot,res,
400 ((((
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 436 Print(
"\n// ideal %s = ", st);
437 for(i=0; i<nL-1; i++)
503 Print(
"\n// intvec %s = ", ch);
505 for(
int i=0;
i<nV;
i++)
509 Print(
"%d;", (*iv)[nV]);
520 Print(
"%d, ", (*iva)[i]);
522 Print(
"%d) ==> (", (*iva)[nV]);
525 Print(
"%d, ", (*ivb)[i]);
527 Print(
"%d) := (", (*ivb)[nV]);
531 Print(
"%d, ", (*ivc)[i]);
533 Print(
"%d)", (*ivc)[nV]);
540 static inline long gcd(
const long a,
const long b)
542 long r, p0 =
a, p1 =
b;
568 int gcd_tmp = (*curr_weight)[0];
569 for (j=1; j<nRing; j++)
571 gcd_tmp =
gcd(gcd_tmp, (*curr_weight)[j]);
579 for (j=0; j<nRing; j++)
581 gcd_tmp =
gcd(gcd_tmp, (*diff_weight)[j]);
594 static void cancel(mpz_t zaehler, mpz_t nenner)
599 mpz_gcd(g, zaehler, nenner);
601 mpz_div(zaehler , zaehler, g);
602 mpz_div(nenner , nenner, g);
609 static int isVectorNeg(
intvec* omega)
613 for(i=omega->
length(); i>=0; i--)
631 mpz_init_set_ui(sing_int, 2147483647);
644 mpz_set_si(zvec, (*weight)[i-1]);
645 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
646 mpz_add(zsum, zsum, zmul);
649 wgrad = mpz_get_ui(zsum);
651 if(mpz_cmp(zsum, sing_int)>0)
656 PrintS(
"\n// ** OVERFLOW in \"MwalkInitialForm\": ");
657 mpz_out_str( stdout, 10, zsum);
658 PrintS(
" is greater than 2147483647 (max. integer representation)");
677 int max = 0, maxtemp;
700 mpz_init_set_ui(sing_int, 2147483647);
713 mpz_set_si(zvec, (*weight)[i-1]);
714 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
715 mpz_add(ztmp, ztmp, zmul);
717 mpz_init_set(result, ztmp);
734 mpz_t
max; mpz_init(max);
735 mpz_t maxtmp; mpz_init(maxtmp);
745 if(mpz_cmp(maxtmp, max)>0)
747 mpz_set(max, maxtmp);
753 if(mpz_cmp(maxtmp, max)==0)
773 ideal Gomega =
idInit(nG, 1);
775 for(i=nG-1; i>=0; i--)
795 PrintS(
"//** the result may be WRONG, i.e. 0!!\n");
805 for(i=nG-1; i>=0; i--)
841 static inline long Mlcm(
long &i1,
long &i2)
843 long temp =
gcd(i1, i2);
844 return ((i1 / temp)* i2);
857 for(i=n-1; i>=0; i--)
859 result += (*a)[
i] * (*b)[
i];
873 for(i=n-1; i>=0; i--)
875 (*result)[
i] = (*a)[
i] - (*b)[
i];
888 for(i=nR-1; i>=0; i--)
905 for (i=0; i<niv; i++)
907 if ((*u)[i] != (*v)[i])
977 (*ivm)[
i] = (*iv)[
i];
981 (*ivm)[i*nR+i-1] = 1;
998 (*ivm)[
i] = (*iv)[
i];
1004 (*ivm)[j+i*nR] = (*iw)[j+i*nR];
1018 for(i=nR-1; i>=0; i--)
1104 if(pdeg > nV || pdeg <= 0)
1106 WerrorS(
"//** The perturbed degree is wrong!!");
1115 mpz_t *pert_vector = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1116 mpz_t *pert_vector1 = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1120 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1121 mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
1125 int ntemp, maxAi, maxA=0;
1126 for(i=1; i<pdeg; i++)
1128 maxAi = (*ivtarget)[i*nV];
1133 for(j=i*nV+1; j<(i+1)*nV; j++)
1135 ntemp = (*ivtarget)[
j];
1152 mpz_t tot_deg; mpz_init(tot_deg);
1153 mpz_t maxdeg; mpz_init(maxdeg);
1154 mpz_t inveps; mpz_init(inveps);
1157 for(i=nG-1; i>=0; i--)
1160 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1162 mpz_set(tot_deg, maxdeg);
1167 mpz_mul_ui(inveps, tot_deg, maxA);
1168 mpz_add_ui(inveps, inveps, 1);
1172 #ifdef INVEPS_SMALL_IN_MPERTVECTOR 1173 if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
1176 mpz_fdiv_q_ui(inveps, inveps, pdeg);
1181 mpz_out_str(stdout, 10, inveps);
1186 for( i=1; i < pdeg; i++ )
1190 mpz_mul(pert_vector[j], pert_vector[j], inveps);
1191 if((*ivtarget)[i*nV+j]<0)
1193 mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
1197 mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
1204 mpz_init_set_ui(sing_int, 2147483647);
1207 mpz_init_set_ui(check_int, 100000);
1211 mpz_set(ztemp, pert_vector[0]);
1214 mpz_gcd(ztemp, ztemp, pert_vector[i]);
1215 if(mpz_cmp_si(ztemp, 1) == 0)
1220 if(mpz_cmp_si(ztemp, 1) != 0)
1224 mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
1230 if(mpz_cmp(pert_vector[i], check_int)>=0)
1234 mpz_fdiv_q_ui(pert_vector1[j], pert_vector[j], 100);
1245 (*result)[
i] = mpz_get_si(pert_vector1[i]);
1246 if(mpz_cmp(pert_vector1[i], sing_int)>=0)
1256 (*result)[
i] = mpz_get_si(pert_vector[i]);
1257 if(mpz_cmp(pert_vector[i], sing_int)>=0)
1263 PrintS(
"\n// ** OVERFLOW in \"MPertvectors\": ");
1264 mpz_out_str( stdout, 10, pert_vector[i]);
1265 PrintS(
" is greater than 2147483647 (max. integer representation)");
1266 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1274 Print(
"\n// %d element(s) of it is overflow!!", ntrue);
1279 mpz_clear(sing_int);
1280 mpz_clear(check_int);
1315 if(pdeg > nV || pdeg <= 0)
1317 WerrorS(
"//** The perturbed degree is wrong!!");
1322 (*pert_vector)[
i]=(*ivtarget)[
i];
1330 int ntemp, maxAi, maxA=0;
1331 for(i=1; i<pdeg; i++)
1333 maxAi = (*ivtarget)[i*nV];
1334 for(j=i*nV+1; j<(i+1)*nV; j++)
1336 ntemp = (*ivtarget)[
j];
1346 int inveps, tot_deg = 0, maxdeg;
1349 for(i=nG-1; i>=0; i--)
1353 if (maxdeg > tot_deg )
1360 inveps = (tot_deg * maxA) + 1;
1362 #ifdef INVEPS_SMALL_IN_FRACTAL 1364 if(inveps > pdeg && pdeg > 3)
1366 inveps = inveps / pdeg;
1370 PrintS(
"\n// the \"big\" inverse epsilon %d", inveps);
1374 for ( i=1; i < pdeg; i++ )
1378 (*pert_vector)[
j] = inveps*((*pert_vector)[
j]) + (*ivtarget)[i*nV+
j];
1382 int temp = (*pert_vector)[0];
1385 temp =
gcd(temp, (*pert_vector)[i]);
1395 (*pert_vector)[
i] = (*pert_vector)[
i] / temp;
1414 (*ivM)[i*nV +
i] = 1;
1434 (*ivM)[(i+1)*nV - i] = -1;
1445 int nV = ivstart->
length();
1450 (*ivM)[
i] = (*ivstart)[
i];
1454 (*ivM)[i*nV + i-1] = 1;
1465 int nV = ivstart->
length();
1470 (*ivM)[
i] = (*ivstart)[
i];
1478 (*ivM)[(i+1)*nV - i] = -1;
1506 for(i=nV-1; i>=0; i--)
1527 int ntemp, maxAi, maxA=0;
1530 maxAi = (*ivtarget)[i*nV];
1535 for(j=i*nV+1; j<(i+1)*nV; j++)
1537 ntemp = (*ivtarget)[
j];
1547 maxA = maxA + maxAi;
1552 mpz_t tot_deg; mpz_init(tot_deg);
1553 mpz_t maxdeg; mpz_init(maxdeg);
1554 mpz_t inveps; mpz_init(inveps);
1557 for(i=nG-1; i>=0; i--)
1560 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1562 mpz_set(tot_deg, maxdeg);
1568 mpz_mul_ui(inveps, tot_deg, maxA);
1569 mpz_add_ui(inveps, inveps, 1);
1572 #ifdef INVEPS_SMALL_IN_FRACTAL 1573 if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
1575 mpz_cdiv_q_ui(inveps, inveps, nV);
1583 mpz_t *ivtemp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
1584 mpz_t *pert_vector=(mpz_t *)
omAlloc(niv*
sizeof(mpz_t));
1586 for(i=0; i < nV; i++)
1588 mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
1589 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1592 mpz_t ztmp; mpz_init(ztmp);
1599 mpz_mul(ztmp, inveps, ivtemp[j]);
1600 if((*ivtarget)[i*nV+j]<0)
1602 mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
1606 mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
1612 mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
1618 mpz_init_set_ui(sing_int, 2147483647);
1625 mpz_set(ztmp, pert_vector[0]);
1626 for(i=0; i<niv; i++)
1628 mpz_gcd(ztmp, ztmp, pert_vector[i]);
1629 if(mpz_cmp_si(ztmp, 1)==0)
1635 for(i=0; i<niv; i++)
1637 mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
1638 (* result)[
i] = mpz_get_si(pert_vector[i]);
1643 for(i=0; i<niv; i++)
1645 if(mpz_cmp(pert_vector[i], sing_int)>0)
1652 Print(
"\n// Xlev = %d and the %d-th element is",
Xnlev, i+1);
1653 PrintS(
"\n// ** OVERFLOW in \"Mfpertvector\": ");
1654 mpz_out_str( stdout, 10, pert_vector[i]);
1655 PrintS(
" is greater than 2147483647 (max. integer representation)");
1656 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1670 mpz_clear(sing_int);
1709 if (result->m[k]!=
NULL)
1750 for(j=
IDELEMS(idLG)-1; j>=0; j--)
1752 F->m[
i] =
pAdd(F->m[i], idLG->m[j]);
1809 for(i=iva->
length()-1; i>=0; i--)
1811 if((*iva)[
i] - (*ivb)[
i] != 0)
1833 for(i=1; i < (vec->
length()); i++)
1863 if((*vec)[i] == k || (*vec)[i] == -k)
2242 target_weight !=
NULL && G !=
NULL);
2248 mpz_t t_zaehler, t_nenner;
2249 mpz_init(t_zaehler);
2252 mpz_t s_zaehler, s_nenner, temp, MwWd;
2253 mpz_init(s_zaehler);
2260 mpz_set_si(sing_int, 2147483647);
2262 mpz_t sing_int_half;
2263 mpz_init(sing_int_half);
2264 mpz_set_si(sing_int_half, 3*(1073741824/2));
2266 mpz_t deg_w0_p1, deg_d0_p1;
2267 mpz_init(deg_w0_p1);
2268 mpz_init(deg_d0_p1);
2292 for (j=0; j<nRing; j++)
2294 (*diff_weight1)[
j] = (*curr_weight)[
j];
2298 for(j=0; j<nRing; j++)
2300 (*curr_weight)[
j] = (*diff_weight1)[
j];
2302 for(j=0; j<nRing; j++)
2304 (*diff_weight1)[
j] = floor(0.1*(*diff_weight1)[j] + 0.5);
2310 for(j=0; j<nRing; j++)
2312 (*diff_weight1)[
j] = (*curr_weight)[
j];
2317 (*curr_weight)[
j] = (*diff_weight1)[
j];
2319 (*diff_weight1)[
j] = floor(0.1*(*diff_weight1)[j] + 0.5);
2324 intvec* diff_weight =
MivSub(target_weight, curr_weight);
2327 for (j=0; j<nG; j++)
2342 mpz_sub(s_zaehler, deg_w0_p1, MwWd);
2343 if(mpz_cmp(s_zaehler, t_null) != 0)
2346 mpz_sub(s_nenner, MwWd, deg_d0_p1);
2348 if( (mpz_cmp(s_zaehler,t_null) > 0 &&
2349 mpz_cmp(s_nenner, s_zaehler)>=0) ||
2350 (mpz_cmp(s_zaehler, t_null) < 0 &&
2351 mpz_cmp(s_nenner, s_zaehler)<=0))
2354 if (mpz_cmp(s_zaehler, t_null) < 0)
2356 mpz_neg(s_zaehler, s_zaehler);
2357 mpz_neg(s_nenner, s_nenner);
2361 cancel(s_zaehler, s_nenner);
2363 if(mpz_cmp(t_nenner, t_null) != 0)
2365 mpz_mul(sztn, s_zaehler, t_nenner);
2366 mpz_mul(sntz, s_nenner, t_zaehler);
2368 if(mpz_cmp(sztn,sntz) < 0)
2370 mpz_add(t_nenner, t_null, s_nenner);
2371 mpz_add(t_zaehler,t_null, s_zaehler);
2376 mpz_add(t_nenner, t_null, s_nenner);
2377 mpz_add(t_zaehler,t_null, s_zaehler);
2387 mpz_t *
vec=(mpz_t*)
omAlloc(nRing*
sizeof(mpz_t));
2392 if(mpz_cmp(t_nenner, t_null) == 0)
2395 Print(
"\n//MwalkNextWeightCC: t_nenner=0\n");
2398 diff_weight =
ivCopy(curr_weight);
2403 if(mpz_cmp_si(t_nenner, 1)==0 && mpz_cmp_si(t_zaehler,1)==0)
2406 diff_weight =
ivCopy(target_weight);
2413 gcd_tmp = (*curr_weight)[0];
2415 for (j=1; j<nRing; j++)
2417 gcd_tmp =
gcd(gcd_tmp, (*curr_weight)[j]);
2425 for (j=0; j<nRing; j++)
2427 gcd_tmp =
gcd(gcd_tmp, (*diff_weight)[j]);
2436 for (j=0; j<nRing; j++)
2438 (*curr_weight)[
j] = (*curr_weight)[
j]/gcd_tmp;
2439 (*diff_weight)[
j] = (*diff_weight)[
j]/gcd_tmp;
2443 #ifdef NEXT_VECTORS_CC 2444 Print(
"\n// gcd of the weight vectors (current and target) = %d", gcd_tmp);
2448 PrintS(
"\n// t_zaehler: "); mpz_out_str( stdout, 10, t_zaehler);
2449 PrintS(
", t_nenner: "); mpz_out_str( stdout, 10, t_nenner);
2457 for (j=0; j<nRing; j++)
2459 mpz_set_si(dcw, (*curr_weight)[j]);
2460 mpz_mul(s_nenner, t_nenner, dcw);
2462 if( (*diff_weight)[j]>0)
2464 mpz_mul_ui(s_zaehler, t_zaehler, (*diff_weight)[j]);
2468 mpz_mul_ui(s_zaehler, t_zaehler, -(*diff_weight)[j]);
2469 mpz_neg(s_zaehler, s_zaehler);
2471 mpz_add(sntz, s_nenner, s_zaehler);
2472 mpz_init_set(vec[j], sntz);
2474 #ifdef NEXT_VECTORS_CC 2475 Print(
"\n// j = %d ==> ", j);
2477 mpz_out_str( stdout, 10, t_nenner);
2478 Print(
" * %d)", (*curr_weight)[j]);
2479 Print(
" + ("); mpz_out_str( stdout, 10, t_zaehler);
2480 Print(
" * %d) = ", (*diff_weight)[j]);
2481 mpz_out_str( stdout, 10, s_nenner);
2483 mpz_out_str( stdout, 10, s_zaehler);
2484 PrintS(
" = "); mpz_out_str( stdout, 10, sntz);
2485 Print(
" ==> vector[%d]: ", j); mpz_out_str(stdout, 10, vec[j]);
2494 if(mpz_cmp_si(ggt,1) != 0)
2496 mpz_gcd(ggt, ggt, sntz);
2501 if(mpz_cmp_si(ggt,1) != 0)
2503 for (j=0; j<nRing; j++)
2505 mpz_divexact(vec[j], vec[j], ggt);
2508 #ifdef NEXT_VECTORS_CC 2509 PrintS(
"\n// gcd of elements of the vector: ");
2510 mpz_out_str( stdout, 10, ggt);
2513 for (j=0; j<nRing; j++)
2515 (*diff_weight)[
j] = mpz_get_si(vec[j]);
2520 for (j=0; j<nRing; j++)
2522 if(mpz_cmp(vec[j], sing_int)>=0)
2527 PrintS(
"\n// ** OVERFLOW in \"MwalkNextWeightCC\": ");
2528 mpz_out_str( stdout, 10, vec[j]);
2529 PrintS(
" is greater than 2147483647 (max. integer representation)\n");
2536 delete diff_weight1;
2537 mpz_clear(t_zaehler);
2538 mpz_clear(t_nenner);
2539 mpz_clear(s_zaehler);
2540 mpz_clear(s_nenner);
2545 mpz_clear(deg_w0_p1);
2546 mpz_clear(deg_d0_p1);
2549 mpz_clear(sing_int_half);
2550 mpz_clear(sing_int);
2697 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2699 r->wvhdl[0][i] = (*va)[
i];
2702 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2703 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2704 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2748 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2749 r->wvhdl[1] = (
int*)
omAlloc(nv*
sizeof(
int));
2753 r->wvhdl[0][
i] = (*vb)[
i];
2754 r->wvhdl[1][
i] = (*va)[
i];
2758 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2759 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2760 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2807 r->wvhdl[0] = (
int*)
omAlloc(nv*nv*
sizeof(
int));
2811 for(i=0; i<nv*nv; i++)
2812 r->wvhdl[0][i] = (*va)[
i];
2815 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2816 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2817 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2859 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2860 r->wvhdl[1] = (
int*)
omAlloc(nvs*
sizeof(
int));
2863 for(i=0; i<nvs; i++)
2865 r->wvhdl[1][
i] = (*va)[
i];
2869 r->wvhdl[0][
i] = (*vb)[
i];
2872 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2873 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2874 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2917 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2918 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2919 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2955 res->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2957 res->wvhdl[0][i] = (*va)[
i];
2961 res->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2962 res->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2963 res->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2968 res->block1[0] = nv;
2973 res->block1[1] = nv;
3008 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
3009 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
3010 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
3053 for(i=hilb->
length()-1; i>=0; i--)
3069 for(i=hilb->
length()-1; i>=0; i--)
3088 poly p,lm,factor1,factor2;
3108 p =
pCopy(Gomega->m[i]);
3109 lm =
pCopy(Gomega->m[j]);
3156 int nwalk=0, endwalks=0, nnwinC=1;
3158 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3159 ring newRing, oldRing, TargetRing;
3163 intvec* pert_target_vector;
3168 #ifndef BUCHBERGER_ALG 3174 for(i=nV-1; i>0; i--)
3176 (*last_omega)[
i] = 1;
3178 (*last_omega)[0] = 10000;
3183 if(tp_deg > 1 && tp_deg <= nV)
3200 pert_target_vector = target_weight;
3207 target_weight =
Mivlp(nV);
3220 #ifdef PRINT_VECTORS 3221 MivString(curr_weight, target_weight, next_weight);
3240 if(
MivComp(next_weight, ivNull) == 1)
3248 if(
MivComp(next_weight, target_weight) == 1)
3251 for(i=nV-1; i>=0; i--)
3253 (*extra_curr_weight)[
i] = (*curr_weight)[
i];
3256 for(i=nV-1; i>=0; i--)
3258 (*curr_weight)[
i] = (*next_weight)[
i];
3277 #ifndef BUCHBERGER_ALG 3286 #endif // BUCHBERGER_ALG 3303 #ifdef BUCHBERGER_ALG 3308 #endif // BUCHBERGER_ALG 3362 Print(
"\n// takes %d steps and calls the recursion of level %d:",
3365 F1 =
LastGB(G,curr_weight, tp_deg-1);
3411 delete target_weight;
3428 for(i=
IDELEMS(G)-1; i>=0; i--)
3431 && (G->m[i]->next!=
NULL)
3432 && (G->m[i]->next->next!=
NULL)
3433 && (G->m[i]->next->next->next!=
NULL)
3434 && (G->m[i]->next->next->next->next!=
NULL) )
3448 for(i=
IDELEMS(G)-1; i>=0; i--)
3465 for(i=
IDELEMS(G)-1; i>=0; i--)
3468 && (G->m[i]->next!=
NULL)
3469 && (G->m[i]->next->next!=
NULL))
3504 for (i=nH-1;i>=0; i--)
3525 for(i=nG-1; i>=0; i--)
3593 int mtmp,
m=(*iva)[0];
3595 for(i=ivMat->
length(); i>=0; i--)
3614 mpz_set_si(ndeg, Trandegreebound(
G)+1);
3620 mpz_init_set_si(maxdeg, Trandegreebound(
G));
3623 mpz_pow_ui(ztmp, maxdeg, 2);
3624 mpz_mul_ui(ztmp, ztmp, 2);
3625 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3626 mpz_add(ndeg, ztmp, maxdeg);
3627 mpz_mul_ui(ndeg, ndeg, m);
3633 #endif //UPPER_BOUND 3635 #ifdef INVEPS_SMALL_IN_TRAN 3636 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3638 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3644 mpz_init_set(deg_tmp, ndeg);
3646 mpz_t *ivres=( mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3647 mpz_init_set_si(ivres[nV-1],1);
3649 for(i=nV-2; i>=0; i--)
3651 mpz_init_set(ivres[i], deg_tmp);
3652 mpz_mul(deg_tmp, deg_tmp, ndeg);
3655 mpz_t *ivtmp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3661 mpz_init_set_ui(sing_int, 2147483647);
3670 if( (*ivMat)[i*nV+j] >= 0 )
3672 mpz_mul_ui(ivres[i], ivres[i], (*ivMat)[i*nV+j]);
3676 mpz_mul_ui(ivres[i], ivres[i], -(*ivMat)[i*nV+j]);
3677 mpz_neg(ivres[i], ivres[i]);
3679 mpz_add(ivtmp[j], ivtmp[j], ivres[i]);
3687 (*repr_vector)[
i] = mpz_get_si(ivtmp[i]);
3688 if(mpz_cmp(ivtmp[i], sing_int)>=0)
3695 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3696 mpz_out_str( stdout, 10, ivtmp[i]);
3697 PrintS(
" is greater than 2147483647 (max. integer representation)");
3698 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3704 ivString(repr_vector,
"repvector");
3705 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3714 mpz_clear(sing_int);
3724 static intvec* TranPertVector_lp(ideal
G)
3738 mpz_set_si(ndeg, Trandegreebound(G)+1);
3744 mpz_init_set_si(maxdeg, Trandegreebound(G));
3747 mpz_pow_ui(ztmp, maxdeg, 2);
3748 mpz_mul_ui(ztmp, ztmp, 2);
3749 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3750 mpz_add(ndeg, ztmp, maxdeg);
3759 #ifdef INVEPS_SMALL_IN_TRAN 3760 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3761 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3768 mpz_init_set(deg_tmp, ndeg);
3770 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3771 mpz_init_set_si(ivres[nV-1], 1);
3773 for(i=nV-2; i>=0; i--)
3775 mpz_init_set(ivres[i], deg_tmp);
3776 mpz_mul(deg_tmp, deg_tmp, ndeg);
3780 mpz_init_set_ui(sing_int, 2147483647);
3786 (*repr_vector)[
i] = mpz_get_si(ivres[i]);
3788 if(mpz_cmp(ivres[i], sing_int)>=0)
3794 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3795 mpz_out_str( stdout, 10, ivres[i]);
3796 PrintS(
" is greater than 2147483647 (max. integer representation)");
3797 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3803 ivString(repr_vector,
"repvector");
3804 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3812 mpz_clear(sing_int);
3829 int degtmp, maxdeg = 0;
3840 mpz_init_set_si(ztmp, maxdeg);
3841 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3842 mpz_init_set_si(ivres[nV-1], 1);
3844 for(i=nV-2; i>=0; i--)
3846 mpz_init_set(ivres[i], ztmp);
3847 mpz_mul_ui(ztmp, ztmp, maxdeg);
3850 mpz_t *ivtmp=(mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
3858 if((*M)[i*nV+
j] < 0)
3860 mpz_mul_ui(ztmp, ivres[i], -(*M)[i*nV+j]);
3861 mpz_neg(ztmp, ztmp);
3864 mpz_mul_ui(ztmp, ivres[i], (*M)[i*nV+j]);
3866 mpz_add(ivtmp[j], ivtmp[j], ztmp);
3870 mpz_init_set_ui(sing_int, 2147483647);
3876 (*repvector)[
i] = mpz_get_si(ivtmp[i]);
3877 if(mpz_cmp(ivtmp[i], sing_int)>0)
3883 PrintS(
"\n// ** OVERFLOW in \"Repr.Matrix\": ");
3884 mpz_out_str( stdout, 10, ivtmp[i]);
3885 PrintS(
" is greater than 2147483647 (max. integer representation)");
3886 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repvector)[i]);
3893 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3899 mpz_clear(sing_int);
3919 intvec* orig_target_weight,
int tp_deg,
int npwinc)
3926 clock_t tinput = clock();
3929 int nwalk=0, endwalks=0, nnwinC=1;
3931 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3932 ring newRing, oldRing, TargetRing;
3939 #ifndef BUCHBERGER_ALG 3945 for(i=nV-1; i>0; i--)
3946 (*last_omega)[
i] = 1;
3947 (*last_omega)[0] = 10000;
3952 if(tp_deg > 1 && tp_deg <= nV)
4023 #ifndef BUCHBERGER_ALG 4032 #endif // BUCHBERGER_ALG 4049 #ifdef BUCHBERGER_ALG 4054 #endif // BUCHBERGER_ALG 4089 #ifdef PRINT_VECTORS 4090 MivString(curr_weight, target_weight, next_weight);
4095 #ifdef TEST_OVERFLOW 4108 if(
MivComp(next_weight, ivNull) == 1)
4115 if(
MivComp(next_weight, target_weight) == 1)
4125 tproc=tproc+clock()-tinput;
4130 G =
Rec_LastGB(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4137 for(i=nV-1; i>=0; i--)
4139 (*curr_weight)[
i] = (*next_weight)[
i];
4164 tproc=tproc+clock()-tinput;
4165 F1 =
Rec_LastGB(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4167 delete target_weight;
4244 clock_t tostd, tproc;
4248 int nwalk=0, endwalks=0;
4250 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4253 ring newRing, oldRing;
4271 Print(
"\n// Computation of the first std took = %.2f sec",
4272 ((
double) tostd)/1000000);
4362 #ifdef PRINT_VECTORS 4363 MivString(curr_weight, target_weight, next_weight);
4372 #ifdef TEST_OVERFLOW 4373 goto TEST_OVERFLOW_OI;
4392 if(
MivComp(next_weight, ivNull) == 1)
4399 if(
MivComp(next_weight, target_weight) == 1)
4401 if(
MivSame(target_weight, exivlp)==1)
4410 G =
Rec_LastGB(G, curr_weight, target_weight, 2,1);
4418 for(i=nV-1; i>=0; i--)
4421 (*curr_weight)[
i] = (*next_weight)[
i];
4425 #ifdef TEST_OVERFLOW 4472 int weight_rad,
int pert_deg)
4475 target_weight !=
NULL && G->m[0] !=
NULL);
4486 (*curr_weight)[
i] = (*orig_M)[
i];
4489 int k=0,weight_norm;
4496 ideal G_test, G_test1, G_test2;
4504 while(weight_norm == 0)
4508 (*next_weight2)[
i] = rand() % 60000 - 30000;
4509 weight_norm = weight_norm + (*next_weight2)[
i]*(*next_weight2)[
i];
4511 weight_norm = 1 + floor(
sqrt(weight_norm));
4515 if((*next_weight2)[i] < 0)
4517 (*next_weight2)[
i] = 1 + (*curr_weight)[
i] + floor(weight_rad*(*next_weight2)[i]/weight_norm);
4521 (*next_weight2)[
i] = (*curr_weight)[
i] + floor(weight_rad*(*next_weight2)[i]/weight_norm);
4531 found_random_weight =
TRUE;
4543 delete curr_weight1;
4561 if(found_random_weight ==
TRUE)
4570 (*result)[
i] = (*next_weight2)[
i];
4577 (*result)[
i] = (*next_weight1)[
i];
4587 (*result)[
i] = (*next_weight2)[
i];
4594 (*result)[
i] = (*next_weight)[
i];
4606 (*result)[
i] = (*next_weight1)[
i];
4613 (*result)[
i] = (*next_weight)[
i];
4621 if(found_random_weight ==
TRUE)
4627 (*result)[
i] = (*next_weight2)[
i];
4634 (*result)[
i] = (*next_weight)[
i];
4642 (*result)[
i] = (*next_weight)[
i];
4648 delete next_weight2;
4651 if(found_random_weight ==
TRUE)
4658 delete next_weight1;
4665 return next_weight1;
4676 int tp_deg,
int npwinc)
4682 int nwalk=0, endwalks=0, nnwinC=1, nlast = 0;
4683 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
4684 ring newRing, oldRing, TargetRing;
4687 #ifndef BUCHBERGER_ALG 4691 for(i=nV-1; i>0; i--)
4693 (*last_omega)[
i] = 1;
4695 (*last_omega)[0] = 10000;
4702 if(tp_deg > 1 && tp_deg <= nV)
4762 #ifndef BUCHBERGER_ALG 4789 #ifdef BUCHBERGER_ALG 4835 #ifdef PRINT_VECTORS 4836 MivString(curr_weight, target_weight, next_weight);
4850 if(
MivComp(next_weight, ivNull) == 1)
4857 if(
MivComp(next_weight, target_weight) == 1)
4865 G =
REC_GB_Mwalk(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4872 for(i=nV-1; i>=0; i--)
4874 (*curr_weight)[
i] = (*next_weight)[
i];
4897 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4903 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight,tp_deg+1,nnwinC);
4906 delete target_weight;
4950 #ifndef BUCHBERGER_ALG 4965 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
4975 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4977 ring newRing, oldRing;
4980 #ifndef BUCHBERGER_ALG 4984 for(i=nV-1; i>=0; i--)
4985 (*tmp_weight)[
i] = (*curr_weight)[
i];
4989 for(i=nV-1; i>0; i--)
4990 (*last_omega)[
i] = 1;
4991 (*last_omega)[0] = 10000;
5010 tif = tif + clock()-
to;
5018 #ifdef CHECK_IDEAL_MWALK 5019 Print(
"\n// **** Groebnerwalk took %d steps and ", nwalk);
5020 PrintS(
"\n// **** call the rec. Pert. Walk to compute a red GB of:");
5024 if(
MivSame(exivlp, target_weight)==1)
5029 Print(
"\n// time for the last std(Gw) = %.2f sec",
5030 ((
double) (clock()-tim)/1000000));
5065 #ifndef BUCHBERGER_ALG 5074 #endif // BUCHBERGER_ALG 5090 #ifdef BUCHBERGER_ALG 5096 tstd = tstd + clock() -
to;
5108 tlift = tlift + clock() -
to;
5124 tred = tred + clock() -
to;
5139 tnw = tnw + clock() -
to;
5140 #ifdef PRINT_VECTORS 5141 MivString(curr_weight, target_weight, next_weight);
5148 PrintS(
"\n// ** The computed vector does NOT stay in Cone!!\n");
5166 if(
MivComp(next_weight, ivNull) == 1)
5172 if(
MivComp(next_weight, target_weight) == 1)
5176 for(i=nV-1; i>=0; i--)
5178 (*tmp_weight)[
i] = (*curr_weight)[
i];
5179 (*curr_weight)[
i] = (*next_weight)[
i];
5191 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5203 ring baseRing,
int reduction,
int printout)
5216 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5223 int nV = baseRing->N;
5225 ideal Gomega,
M, F, FF, Gomega1, Gomega2, M1;
5227 ring XXRing = baseRing;
5242 (*curr_weight)[
i] = (*orig_M)[
i];
5243 (*target_weight)[
i] = (*target_M)[
i];
5245 #ifndef BUCHBERGER_ALG 5249 for(i=nV-1; i>0; i--)
5251 (*last_omega)[
i] = 1;
5253 (*last_omega)[0] = 10000;
5256 #ifdef CHECK_IDEAL_MWALK 5263 if(target_M->
length() == nV)
5272 if(orig_M->
length() == nV)
5276 newRing=
VMrRefine(target_weight, curr_weight);
5308 tif = tif + clock()-
to;
5311 #ifdef CHECK_IDEAL_MWALK 5314 idString(Gomega,
"//** Mwalk: Gomega");
5323 PrintS(
"middle of Cone");
5331 #ifndef BUCHBERGER_ALG 5344 if(orig_M->
length() == nV)
5348 newRing=
VMrRefine(target_weight, curr_weight);
5357 if(target_M->
length() == nV)
5361 newRing=
VMrRefine(target_weight, curr_weight);
5380 #ifndef BUCHBERGER_ALG 5387 tstd = tstd + clock() -
to;
5390 #ifdef CHECK_IDEAL_MWALK 5409 tlift = tlift + clock() -
to;
5411 #ifdef CHECK_IDEAL_MWALK 5425 #ifdef CHECK_IDEAL_MWALK 5452 tnw = tnw + clock() -
to;
5454 #ifdef PRINT_VECTORS 5457 MivString(curr_weight, target_weight, next_weight);
5462 if(
MivComp(curr_weight,next_weight)==1)
5467 if(
MivComp(target_weight,curr_weight) == 1)
5472 for(i=nV-1; i>=0; i--)
5475 (*curr_weight)[
i] = (*next_weight)[
i];
5486 #ifndef BUCHBERGER_ALG 5490 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5496 Print(
"\n//** Mwalk: Groebner Walk took %d steps.\n",
nstep);
5517 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5529 Werror(
"Invalid radius.\n");
5534 if(pert_deg > nV || pert_deg < 1)
5536 Werror(
"Invalid perturbation degree.\n");
5540 ideal Gomega,
M, F,FF, Gomega1, Gomega2, M1;
5553 (*curr_weight)[
i] = (*orig_M)[
i];
5554 (*target_weight)[
i] = (*target_M)[
i];
5557 #ifndef BUCHBERGER_ALG 5561 for(i=nV-1; i>0; i--)
5563 (*last_omega)[
i] = 1;
5565 (*last_omega)[0] = 10000;
5569 if(target_M->
length() == nV)
5577 if(orig_M->
length() == nV)
5580 newRing=
VMrRefine(target_weight, curr_weight);
5602 tif = tif + clock()-
to;
5609 #ifdef CHECK_IDEAL_MWALK 5612 idString(Gomega,
"//** Mrwalk: Gomega");
5626 #ifndef BUCHBERGER_ALG 5638 if(orig_M->
length() == nV)
5641 newRing=
VMrRefine(target_weight, curr_weight);
5650 if(target_M->
length() == nV)
5653 newRing=
VMrRefine(target_weight, curr_weight);
5667 #ifndef BUCHBERGER_ALG 5674 tstd = tstd + clock() -
to;
5677 #ifdef CHECK_IDEAL_MWALK 5696 tlift = tlift + clock() -
to;
5698 #ifdef CHECK_IDEAL_MWALK 5712 tstd = tstd + clock() -
to;
5715 #ifdef CHECK_IDEAL_MWALK 5742 tnw = tnw + clock() -
to;
5750 tif = tif + clock()-
to;
5760 if(target_M->
length() == nV)
5774 tnw = tnw + clock() -
to;
5782 tif = tif + clock()-
to;
5788 if(
MivComp(next_weight, ivNull) == 1 ||
MivComp(target_weight,curr_weight) == 1)
5796 if(
MivComp(curr_weight,next_weight)==1)
5801 #ifdef PRINT_VECTORS 5804 MivString(curr_weight, target_weight, next_weight);
5808 for(i=nV-1; i>=0; i--)
5810 (*curr_weight)[
i] = (*next_weight)[
i];
5819 #ifndef BUCHBERGER_ALG 5824 Print(
"\n//** Mrwalk: Groebner Walk took %d steps.\n",
nstep);
5827 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5861 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5869 int i, ntwC=1, ntestw=1, nV =
currRing->N;
5872 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
5874 Werror(
"Invalid perturbation degree.\n");
5879 ideal Gomega,
M, F, FF,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5880 ring newRing, oldRing, TargetRing;
5884 intvec* orig_target = target_weight;
5885 intvec* pert_target_vector = target_weight;
5888 #ifndef BUCHBERGER_ALG 5895 for(i=nV-1; i>0; i--)
5896 (*last_omega)[
i] = 1;
5897 (*last_omega)[0] = 10000;
5904 if(
MivComp(curr_weight, iv_dp) == 1)
5938 if(op_deg != 1)
delete iv_M_dp;
5943 if(tp_deg > 1 && tp_deg <= nV)
5955 if(
MivSame(target_weight, exivlp) == 1)
5966 pert_target_vector = target_weight;
5972 Print(
"\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
5973 #ifdef PRINT_VECTORS 5974 ivString(curr_weight,
"//** Mpwalk: new current weight");
5975 ivString(target_weight,
"//** Mpwalk: new target weight");
5988 tif = tif + clock()-
to;
5990 #ifdef CHECK_IDEAL_MWALK 5993 idString(Gomega,
"//** Mpwalk: Gomega");
5996 if(reduction == 0 &&
nstep > 1)
6009 if(endwalks ==
TRUE)
6020 #ifndef BUCHBERGER_ALG 6025 #endif // BUCHBERGER_ALG 6049 PrintS(
"\n// compute a rGB of Gw:\n");
6051 #ifndef BUCHBERGER_ALG 6061 #ifdef BUCHBERGER_ALG 6068 if(endwalks ==
TRUE)
6076 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
6077 ((
double) clock())/1000000 -((
double)tim) /1000000);
6084 tstd=tstd+clock()-
to;
6087 #ifdef CHECK_IDEAL_MWALK 6105 if(endwalks ==
FALSE)
6106 tlift = tlift+clock()-
to;
6110 #ifdef CHECK_IDEAL_MWALK 6132 PrintS(
"\n //** Mpwalk: reduce the Groebner basis.\n");
6139 if(endwalks ==
FALSE)
6140 tred = tred+clock()-
to;
6146 if(endwalks ==
TRUE)
6158 #ifdef PRINT_VECTORS 6161 MivString(curr_weight, target_weight, next_weight);
6174 if(
MivComp(next_weight, ivNull) == 1){
6180 if(
MivComp(next_weight, target_weight) == 1)
6183 for(i=nV-1; i>=0; i--)
6184 (*curr_weight)[
i] = (*next_weight)[
i];
6192 if(
MivSame(orig_target, exivlp) == 1) {
6216 if( ntestw != 1 || ntwC == 0)
6218 if(ntestw != 1 && printout >2)
6220 ivString(pert_target_vector,
"tau");
6221 PrintS(
"\n// ** perturbed target vector doesn't stay in cone!!");
6228 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1){
6237 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6258 delete target_weight;
6275 Print(
"\n//** Mpwalk: Perturbation Walk took %d steps.\n",
nstep);
6284 int op_deg,
int tp_deg,
int nP,
int reduction,
int printout)
6296 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
6304 int i, ntwC=1, ntestw=1, nV =
currRing->N;
6309 Werror(
"Invalid radius.\n");
6314 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
6316 Werror(
"Invalid perturbation degree.\n");
6322 ideal Gomega,
M, F, FF,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
6323 ring newRing, oldRing, TargetRing;
6332 (*curr_weight)[
i] = (*orig_M)[
i];
6333 (*target_weight)[
i] = (*target_M)[
i];
6335 intvec* orig_target = target_weight;
6336 intvec* pert_target_vector = target_weight;
6339 #ifndef BUCHBERGER_ALG 6346 for(i=nV-1; i>0; i--)
6347 (*last_omega)[
i] = 1;
6348 (*last_omega)[0] = 10000;
6353 if(orig_M->
length() == nV)
6355 if(
MivComp(curr_weight, iv_dp) == 1)
6411 if(op_deg != 1)
delete iv_M_dp;
6416 if(target_M->
length() == nV)
6418 if(tp_deg > 1 && tp_deg <= nV)
6427 if(
MivSame(target_weight, exivlp) == 1)
6438 pert_target_vector = target_weight;
6445 if(tp_deg > 1 && tp_deg <= nV)
6455 Print(
"\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6456 ivString(curr_weight,
"//** Mprwalk: new current weight");
6457 ivString(target_weight,
"//** Mprwalk: new target weight");
6465 tif = tif + clock()-
to;
6471 #ifdef CHECK_IDEAL_MWALK 6474 idString(Gomega,
"//** Mprwalk: Gomega");
6478 if(reduction == 0 &&
nstep > 1)
6491 if(endwalks ==
TRUE)
6502 #ifndef BUCHBERGER_ALG 6507 #endif // BUCHBERGER_ALG 6511 if(target_M->
length() == nV)
6528 if(endwalks ==
TRUE)
6537 PrintS(
"\n// compute a rGB of Gw:\n");
6539 #ifndef BUCHBERGER_ALG 6549 #ifdef BUCHBERGER_ALG 6555 #ifdef CHECK_IDEAL_MWALK 6562 if(endwalks ==
TRUE)
6566 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
6567 ((
double) clock())/1000000 -((
double)tim) /1000000);
6571 tstd=tstd+clock()-
to;
6585 if(endwalks ==
FALSE)
6586 tlift = tlift+clock()-
to;
6590 #ifdef CHECK_IDEAL_MWALK 6612 PrintS(
"\n //** Mprwalk: reduce the Groebner basis.\n");
6619 if(endwalks ==
FALSE)
6620 tred = tred+clock()-
to;
6627 if(endwalks ==
TRUE)
6636 tnw = tnw + clock() -
to;
6645 tif = tif + clock()-
to;
6653 Print(
"\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
6657 if(target_M->
length() == nV)
6670 tnw = tnw + clock() -
to;
6678 tif = tif + clock()-
to;
6683 #ifdef PRINT_VECTORS 6686 MivString(curr_weight, target_weight, next_weight);
6698 if(
MivComp(next_weight, ivNull) == 1){
6704 if(
MivComp(next_weight, target_weight) == 1)
6707 for(i=nV-1; i>=0; i--)
6708 (*curr_weight)[
i] = (*next_weight)[
i];
6716 if(target_M->
length() == nV)
6718 if(
MivSame(orig_target, exivlp) == 1)
6741 if(ntestw != 1 || ntwC == 0)
6743 if(ntestw != 1 && printout > 2)
6745 #ifdef PRINT_VECTORS 6746 ivString(pert_target_vector,
"tau");
6748 PrintS(
"\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
6757 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1 || target_M->
length() != nV)
6761 PrintS(
"\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
6770 PrintS(
"\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
6774 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6799 delete target_weight;
6817 Print(
"\n//** Mprwalk: Perturbation Walk took %d steps.\n",
nstep);
6834 (*ivM)[i*nV +
j] = 1;
6852 Print(
"\n\n// Entering the %d-th recursion:", nlev);
6855 ring new_ring, testring;
6857 ideal Gomega, Gomega1, Gomega2, FF, F, F1, Gresult, Gresult1, G1, Gt;
6860 #ifndef BUCHBERGER_ALG 6869 for(i = nV -1; i>=0; i--)
6871 (*omtmp)[
i] = (*ivtarget)[
i];
6877 for(i=nV-1; i>0; i--)
6878 (*last_omega)[
i] = 1;
6879 (*last_omega)[0] = 10000;
6882 for(i=0; i<nV; i++) {
6883 if(Xsigma->
length() == nV)
6884 (*omega)[
i] = (*Xsigma)[
i];
6886 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
6888 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
6891 if(nlev == 1)
Xcall = 1;
6898 #ifdef FIRST_STEP_FRACTAL 6901 if((nlev == 1 &&
Xcall == 0) || (nlev == 2 &&
Xngleich == 1))
6911 NEXT_VECTOR_FRACTAL:
6924 if (
MivComp(next_vect, omega2) == 1)
6930 Print(
"\n//** rec_fractal_call: Perturb the both vectors with degree %d.",nlev);
6937 if(ivtarget->
length() == nV)
6956 if(ivtarget->
length() == nV)
6975 for(i=nV-1; i>=0; i--) {
6976 (*omega2)[
i] = (*Xtau)[nV+
i];
6977 (*omega)[
i] = (*Xsigma)[nV+
i];
6992 #ifdef PRINT_VECTORS 6995 MivString(omega, omega2, next_vect);
7005 if(ivtarget->
length() == nV)
7020 #ifdef TEST_OVERFLOW 7022 Gt =
NULL;
return(Gt);
7026 Print(
"\n//** rec_fractal_call: Applying Buchberger's algorithm in ring r = %s;",
7043 Print(
"\n//** rec_fractal_call: Overflow. (4) Leaving the %d-th recursion with %d steps.\n",
7061 if (
MivComp(next_vect, XivNull) == 1)
7063 if(ivtarget->
length() == nV)
7088 Print(
"\n//** rec_fractal_call: Correct cone. (5) Leaving the %d-th recursion with %d steps.\n",
7093 idString(Gt,
"//** rec_fractal_call: Gt");
7101 Print(
"\n//** rec_fractal_call: Wrong cone. Tau doesn't stay in the correct cone.\n");
7104 #ifndef MSTDCC_FRACTAL 7106 if(ivtarget->
length() == nV)
7114 #ifdef TEST_OVERFLOW 7116 Gt =
NULL;
return(Gt);
7119 if(
MivSame(Xtau, Xtautmp) == 1)
7123 Print(
"\n//** rec_fractal_call: Updated vectors are equal to the old vectors.\n");
7126 goto FRACTAL_MSTDCC;
7132 for(i=nV-1; i>=0; i--)
7133 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
7138 goto NEXT_VECTOR_FRACTAL;
7144 Print(
"\n//** rec_fractal_call: Wrong cone. Applying Buchberger's algorithm in ring = %s.\n",
7157 if(ivtarget->
length() == nV)
7181 if(ivtarget->
length() == nV)
7200 Print(
"\n//** rec_fractal_call: Vectors updated. (6) Leaving the %d-th recursion with %d steps.\n",
7212 for(i=nV-1; i>=0; i--) {
7214 (*omega)[
i] = (*next_vect)[
i];
7225 #ifdef CHECK_IDEAL_MWALK 7228 idString(Gomega,
"//** rec_fractal_call: Gomega");
7242 goto NEXT_VECTOR_FRACTAL;
7246 #ifndef BUCHBERGER_ALG 7253 if(ivtarget->
length() == nV)
7276 Print(
"\n//** rec_fractal_call: Maximal recursion depth.\n");
7281 #ifdef BUCHBERGER_ALG 7297 #ifdef CHECK_IDEAL_MWALK 7300 idString(Gresult,
"//** rec_fractal_call: M");
7317 #ifdef CHECK_IDEAL_MWALK 7320 idString(F,
"//** rec_fractal_call: F");
7349 int weight_rad,
int reduction,
int printout)
7355 ring new_ring, testring;
7357 ideal Gomega, Gomega1, Gomega2, F, FF, F1, Gresult, Gresult1, G1, Gt;
7359 #ifndef BUCHBERGER_ALG 7371 for(
i = nV -1;
i>=0;
i--)
7373 (*omtmp)[
i] = (*ivtarget)[
i];
7377 for(
i=nV-1;
i>0;
i--)
7378 (*last_omega)[
i] = 1;
7379 (*last_omega)[0] = 10000;
7382 for(
i=0;
i<nV;
i++) {
7383 if(Xsigma->
length() == nV)
7384 (*omega)[
i] = (*Xsigma)[
i];
7386 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
7388 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+
i];
7391 if(nlev == 1)
Xcall = 1;
7398 #ifdef FIRST_STEP_FRACTAL 7403 if((nlev == 1 &&
Xcall == 0) || (nlev == 2 &&
Xngleich == 1))
7413 NEXT_VECTOR_FRACTAL:
7426 PrintS(
"\n**// rec_r_fractal_call: there is a polynomial in Gomega with at least 3 monomials.\n");
7453 if (
MivComp(next_vect, omega2) == 1)
7459 Print(
"\n//** rec_r_fractal_call: Perturb both vectors with degree %d.",nlev);
7464 if(ivtarget->
length() == nV)
7483 if(ivtarget->
length() == nV)
7499 if(ivtarget->
length() > nV)
7507 for(
i=nV-1;
i>=0;
i--)
7509 (*omega2)[
i] = (*Xtau)[nV+
i];
7510 (*omega)[
i] = (*Xsigma)[nV+
i];
7550 #ifdef PRINT_VECTORS 7553 MivString(omega, omega2, next_vect);
7564 if(ivtarget->
length() == nV)
7583 #ifdef TEST_OVERFLOW 7590 Print(
"\n//** rec_r_fractal_call: applying Buchberger's algorithm in ring r = %s;",
7607 Print(
"\n//** rec_r_fractal_call: (1) Leaving the %d-th recursion with %d steps.\n",
7622 if (
MivComp(next_vect, XivNull) == 1)
7626 if(ivtarget->
length() == nV)
7651 Print(
"\n//** rec_r_fractal_call: (2) Leaving the %d-th recursion with %d steps.\n",
7661 Print(
"\n//** rec_r_fractal_call: target weight doesn't stay in the correct cone.\n");
7664 #ifndef MSTDCC_FRACTAL 7665 #ifdef PRINT_VECTORS 7672 if(ivtarget->
length() == nV)
7680 #ifdef TEST_OVERFLOW 7682 Gt =
NULL;
return(Gt);
7685 if(
MivSame(Xtau, Xtautmp) == 1)
7689 goto FRACTAL_MSTDCC;
7694 #ifdef PRINT_VECTORS 7701 for(
i=nV-1;
i>=0;
i--)
7702 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+
i];
7708 goto NEXT_VECTOR_FRACTAL;
7714 Print(
"\n//** rec_r_fractal_call: apply Buchberger's algorithm in ring = %s.\n",
7727 if(ivtarget->
length() == nV)
7751 if(ivtarget->
length() == nV)
7770 Print(
"\n//** rec_r_fractal_call: (3) Leaving the %d-th recursion with %d steps.\n",
7782 for(
i=nV-1;
i>=0;
i--)
7784 (*altomega)[
i] = (*omega)[
i];
7785 (*omega)[
i] = (*next_vect)[
i];
7798 #ifdef CHECK_IDEAL_MWALK 7801 idString(Gomega,
"//** rec_r_fractal_call: Gomega");
7815 goto NEXT_VECTOR_FRACTAL;
7819 #ifndef BUCHBERGER_ALG 7825 if(ivtarget->
length() == nV)
7849 #ifdef BUCHBERGER_ALG 7865 #ifdef CHECK_IDEAL_MWALK 7868 idString(Gresult,
"//** rec_r_fractal_call: M");
7885 #ifdef CHECK_IDEAL_MWALK 7888 idString(F,
"//** rec_r_fractal_call: F");
7946 XivNull =
new intvec(nV);
7947 Xivinput = ivtarget;
7961 #ifdef FIRST_STEP_FRACTAL 7963 for(i=
IDELEMS(Gw)-1; i>=0; i--)
7966 && (Gw->m[i]->next!=
NULL)
7967 && (Gw->m[i]->next->next!=
NULL))
7971 if(ivstart->
length() == nV)
7973 if(
MivSame(ivstart, iv_dp) != 1)
7998 if(ivtarget->
length() == nV)
8000 if(
MivComp(ivtarget, Xivlp) != 1)
8038 if(ivtarget->
length() == nV)
8088 Print(
"\n// the numbers of Overflow_Error (%d)",
nnflow);
8105 int weight_rad,
int reduction,
int printout)
8111 Werror(
"Invalid radius.\n");
8133 XivNull =
new intvec(nV);
8134 Xivinput = ivtarget;
8148 #ifdef FIRST_STEP_FRACTAL 8150 for(i=
IDELEMS(Gw)-1; i>=0; i--)
8153 && (Gw->m[i]->next!=
NULL)
8154 && (Gw->m[i]->next->next!=
NULL))
8158 if(ivstart->
length() == nV)
8160 if(
MivSame(ivstart, iv_dp) != 1)
8185 if(ivtarget->
length() == nV)
8187 if(
MivComp(ivtarget, Xivlp) != 1)
8225 if(ivtarget->
length() == nV)
8275 Print(
"\n// the numbers of Overflow_Error (%d)",
nnflow);
8291 clock_t mtim = clock();
8298 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8300 clock_t tinput = clock();
8302 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
8303 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
8304 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
8306 ring newRing, oldRing, lpRing;
8314 int nGB, endwalks = 0, nwalkpert=0, npertstep=0;
8317 #ifndef BUCHBERGER_ALG 8322 for(
i=nV-1;
i>0;
i--)
8323 (*last_omega)[
i] = 1;
8324 (*last_omega)[0] = 10000;
8328 for(
i=nV-1;
i>=0;
i--)
8329 (*target_weight)[
i] = (*target_tmp)[
i];
8336 if(
MivComp(curr_weight, iv_dp) == 1)
8350 #ifdef REPRESENTATION_OF_SIGMA 8356 if(
MivComp(curr_weight, iv_dp) == 1)
8357 MDp = MatrixOrderdp(nV);
8361 curr_weight = RepresentationMatrix_Dp(G, MDp);
8375 tostd=tostd+clock()-
to;
8377 goto COMPUTE_NEW_VECTOR;
8392 #ifndef BUCHBERGER_ALG 8397 #endif // BUCHBERGER_ALG 8412 #ifdef BUCHBERGER_ALG 8417 #endif // BUCHBERGER_ALG 8418 tstd=tstd+clock()-
to;
8430 tlift=tlift+clock()-
to;
8443 tred=tred+clock()-
to;
8455 #ifdef PRINT_VECTORS 8456 MivString(curr_weight, target_weight, next_weight);
8468 OMEGA_OVERFLOW_TRAN_NEW:
8471 #ifdef TEST_OVERFLOW 8480 if(
MivSame(target_tmp, iv_lp) == 1)
8496 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0){
8505 G =
LastGB(G1, curr_weight, nV-1);
8511 npert[endwalks]=nwalk-npert_tmp;
8520 if(
MivComp(next_weight, target_weight) == 1 ||
8521 MivComp(next_weight, curr_weight) == 1 )
8527 npert[endwalks]=nwalk-npert_tmp;
8533 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1){
8540 if(
MivSame(target_tmp, iv_lp) == 1)
8587 if(p->next !=
NULL &&
8588 p->next->next !=
NULL &&
8589 p->next->next->next !=
NULL)
8594 (*vector_tmp)[
i] = (*target_weight)[
i];
8596 delete target_weight;
8599 if(
MivComp(vector_tmp, target_weight)==1)
8604 goto OMEGA_OVERFLOW_TRAN_NEW;
8611 goto OMEGA_OVERFLOW_TRAN_NEW;
8621 if(plength3 ==
FALSE)
8647 goto COMPUTE_NEW_VECTOR;
8651 for(
i=nV-1;
i>=0;
i--)
8652 (*curr_weight)[
i] = (*next_weight)[
i];
8656 #ifdef TEST_OVERFLOW 8687 ideal TranMrImprovwalk(ideal
G,
intvec* curr_weight,
intvec* target_tmp,
int nP,
int weight_rad,
int pert_deg)
8690 clock_t mtim = clock();
8697 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8699 clock_t tinput = clock();
8701 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
8702 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
8703 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
8705 ring newRing, oldRing, lpRing;
8713 int weight_norm, nGB, endwalks = 0, nwalkpert=0, npertstep=0;
8716 #ifndef BUCHBERGER_ALG 8721 for(
i=nV-1;
i>0;
i--)
8723 (*last_omega)[
i] = 1;
8725 (*last_omega)[0] = 10000;
8729 for(
i=nV-1;
i>=0;
i--)
8731 (*target_weight)[
i] = (*target_tmp)[
i];
8738 if(
MivComp(curr_weight, iv_dp) == 1)
8759 #ifdef REPRESENTATION_OF_SIGMA 8765 if(
MivComp(curr_weight, iv_dp) == 1)
8767 MDp = MatrixOrderdp(nV);
8773 curr_weight = RepresentationMatrix_Dp(
G, MDp);
8791 tostd=tostd+clock()-
to;
8793 goto COMPUTE_NEW_VECTOR;
8808 #ifndef BUCHBERGER_ALG 8817 #endif // BUCHBERGER_ALG 8835 #ifdef BUCHBERGER_ALG 8841 tstd=tstd+clock()-
to;
8852 tlift=tlift+clock()-
to;
8865 tred=tred+clock()-
to;
8953 #ifdef PRINT_VECTORS 8954 MivString(curr_weight, target_weight, next_weight);
8966 OMEGA_OVERFLOW_TRAN_NEW:
8969 #ifdef TEST_OVERFLOW 8973 #ifdef CHECK_IDEAL_MWALK 8978 if(
MivSame(target_tmp, iv_lp) == 1)
9005 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0)
9016 G =
LastGB(G1, curr_weight, nV-1);
9022 npert[endwalks]=nwalk-npert_tmp;
9031 if(
MivComp(next_weight, target_weight) == 1 ||
MivComp(next_weight, curr_weight) == 1 )
9037 npert[endwalks]=nwalk-npert_tmp;
9043 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1)
9051 if(
MivSame(target_tmp, iv_lp) == 1)
9107 if(p->next !=
NULL &&
9108 p->next->next !=
NULL &&
9109 p->next->next->next !=
NULL)
9115 (*vector_tmp)[
i] = (*target_weight)[
i];
9117 delete target_weight;
9120 if(
MivComp(vector_tmp, target_weight)==1)
9125 goto OMEGA_OVERFLOW_TRAN_NEW;
9132 goto OMEGA_OVERFLOW_TRAN_NEW;
9142 if(plength3 ==
FALSE)
9168 goto COMPUTE_NEW_VECTOR;
9172 for(
i=nV-1;
i>=0;
i--)
9174 (*curr_weight)[
i] = (*next_weight)[
i];
9178 #ifdef TEST_OVERFLOW 9191 Print(
"\n// Computation took %d steps and %.2f sec", nwalk, ((
double) (clock()-mtim)/1000000));
9193 TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
9211 clock_t tinput=clock();
9215 if(tp_deg < 1 || tp_deg > nV)
9217 Werror(
"Invalid perturbation degree.\n");
9221 int nwalk=0, endwalks=0, ntestwinC=1;
9222 int tp_deg_tmp = tp_deg;
9223 ideal Gomega,
M, F,
G, M1, F1, Gomega1, Gomega2, G1;
9224 ring newRing, oldRing, TargetRing;
9257 target_weight =
Mivlp(nV);
9267 if(tp_deg != tp_deg_tmp)
9277 #ifndef BUCHBERGER_ALG 9282 for(i=nV-1; i>0; i--)
9284 (*last_omega)[
i] = 1;
9286 (*last_omega)[0] = 10000;
9305 #ifndef BUCHBERGER_ALG 9337 #ifdef BUCHBERGER_ALG 9342 #endif // BUCHBERGER_ALG 9380 #ifdef PRINT_VECTORS 9381 MivString(curr_weight, target_weight, next_weight);
9389 tproc = tproc+clock()-tinput;
9401 if(
MivComp(next_weight, ivNull) == 1)
9407 if(
MivComp(next_weight, target_weight) == 1)
9411 for(i=nV-1; i>=0; i--)
9414 (*curr_weight)[
i] = (*next_weight)[
i];
9448 tproc = tproc+clock()-tinput;
9460 delete target_weight;
9482 clock_t tostd, tproc;
9486 int nwalk=0, endwalks=0;
9487 int op_tmp = op_deg;
9488 ideal Gomega,
M, F,
G, Gomega1, Gomega2, M1, F1;
9489 ring newRing, oldRing;
9496 #ifndef BUCHBERGER_ALG 9499 intvec* cw_tmp = curr_weight;
9503 for(i=nV-1; i>0; i--)
9505 (*last_omega)[
i] = 1;
9507 (*last_omega)[0] = 10000;
9519 if(
MivComp(curr_weight, iv_dp) == 1)
9522 if(op_tmp == op_deg)
9534 if(op_tmp == op_deg)
9558 curr_weight = cw_tmp;
9589 for(i=nV-1; i>=0; i--)
9590 (*curr_weight)[
i] = (*extra_curr_weight)[
i];
9591 delete extra_curr_weight;
9597 #ifndef BUCHBERGER_ALG 9606 #endif // BUCHBERGER_ALG 9624 #ifdef BUCHBERGER_ALG 9629 #endif // BUCHBERGER_ALG 9667 #ifdef PRINT_VECTORS 9668 MivString(curr_weight, target_weight, next_weight);
9691 if(
MivComp(next_weight, ivNull) == 1)
9698 if(
MivComp(next_weight, target_weight) == 1)
9700 if(tp_deg == 1 ||
MivSame(target_weight, exivlp) == 0)
9720 for(i=nV-1; i>=0; i--)
9723 (*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 int pLength(poly a)
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)
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)
static int isNolVector(intvec *hilb)
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)
void Werror(const char *fmt,...)
intvec * MivMatrixOrderlp(int nV)
static ring VMrDefault(intvec *va)
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
static int simplify_gcd(intvec *curr_weight, intvec *diff_weight)
#define pCopy(p)
return a copy of the poly
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
static int * initS_2_R(int maxnr)