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> 111 return (
unsigned long*)
omAlloc0(maxnr*
sizeof(
unsigned long));
115 return (
int*)
omAlloc0(maxnr*
sizeof(
int));
356 ideal shdl=strat->
Shdl;
364 static void TimeString(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
365 clock_t tlf,clock_t tred, clock_t tnw,
int step)
367 double totm = ((double) (clock() - tinput))/1000000;
368 double ostd,mostd, mif, mstd, mlf, mred, mnw, mxif,mxstd,mxlf,mxred,mxnw,tot;
370 Print(
"\n// total time = %.2f sec", totm);
371 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
372 mostd=((((
double) tostd)/1000000)/totm)*100);
373 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
374 mif=((((
double) tif)/1000000)/totm)*100);
375 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
376 mstd=((((
double) tstd)/1000000)/totm)*100);
377 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
378 mlf=((((
double) tlf)/1000000)/totm)*100);
379 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
380 mred=((((
double) tred)/1000000)/totm)*100);
381 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
382 mnw=((((
double) tnw)/1000000)/totm)*100);
383 PrintS(
"\n Time for the last step:");
384 Print(
"\n// xinfo = %.2f sec = %.2f", ((
double)
xtif)/1000000,
385 mxif=((((
double) xtif)/1000000)/totm)*100);
386 Print(
"\n// xstd = %.2f sec = %.2f", ((
double)
xtstd)/1000000,
387 mxstd=((((
double) xtstd)/1000000)/totm)*100);
388 Print(
"\n// xlift = %.2f sec = %.2f", ((
double)
xtlift)/1000000,
389 mxlf=((((
double) xtlift)/1000000)/totm)*100);
390 Print(
"\n// xired = %.2f sec = %.2f", ((
double)
xtred)/1000000,
391 mxred=((((
double) xtred)/1000000)/totm)*100);
392 Print(
"\n// xnextw= %.2f sec = %.2f", ((
double)
xtnw)/1000000,
393 mxnw=((((
double) xtnw)/1000000)/totm)*100);
395 tot=mostd+mif+mstd+mlf+mred+mnw+mxif+mxstd+mxlf+mxred+mxnw;
396 double res = (double) 100 - tot;
397 Print(
"\n// &%d&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f&%.2f(%.2f)\\ \\",
398 step, ostd, totm, mostd,mif,mstd,mlf,mred,mnw,mxif,mxstd,mxlf,mxred,mxnw,tot,res,
399 ((((
double)
xtextra)/1000000)/totm)*100);
402 static void TimeStringFractal(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
403 clock_t textra, clock_t tlf,clock_t tred, clock_t tnw)
406 double totm = ((double) (clock() - tinput))/1000000;
407 double ostd, mostd, mif, mstd, mextra, mlf, mred, mnw, tot,
res;
408 Print(
"\n// total time = %.2f sec", totm);
409 Print(
"\n// tostd = %.2f sec = %.2f", ostd=((
double) tostd)/1000000,
410 mostd=((((
double) tostd)/1000000)/totm)*100);
411 Print(
"\n// tif = %.2f sec = %.2f", ((
double) tif)/1000000,
412 mif=((((
double) tif)/1000000)/totm)*100);
413 Print(
"\n// std = %.2f sec = %.2f", ((
double) tstd)/1000000,
414 mstd=((((
double) tstd)/1000000)/totm)*100);
415 Print(
"\n// xstd = %.2f sec = %.2f", ((
double) textra)/1000000,
416 mextra=((((
double) textra)/1000000)/totm)*100);
417 Print(
"\n// lift = %.2f sec = %.2f", ((
double) tlf)/1000000,
418 mlf=((((
double) tlf)/1000000)/totm)*100);
419 Print(
"\n// ired = %.2f sec = %.2f", ((
double) tred)/1000000,
420 mred=((((
double) tred)/1000000)/totm)*100);
421 Print(
"\n// nextw = %.2f sec = %.2f", ((
double) tnw)/1000000,
422 mnw=((((
double) tnw)/1000000)/totm)*100);
423 tot = mostd+mif+mstd+mextra+mlf+mred+mnw;
424 res = (double) 100.00-tot;
425 Print(
"\n// &%.2f &%.2f&%.2f &%.2f &%.2f &%.2f &%.2f &%.2f &%.2f&%.2f&%.2f\\ \\ ",
426 ostd,totm,mostd,mif,mstd,mextra,mlf,mred,mnw,tot,res);
430 #ifdef CHECK_IDEAL_MWALK 435 Print(
"\n// ideal %s = ", st);
436 for(i=0; i<nL-1; i++)
502 Print(
"\n// intvec %s = ", ch);
504 for(
int i=0;
i<nV;
i++)
508 Print(
"%d;", (*iv)[nV]);
519 Print(
"%d, ", (*iva)[i]);
521 Print(
"%d) ==> (", (*iva)[nV]);
524 Print(
"%d, ", (*ivb)[i]);
526 Print(
"%d) := (", (*ivb)[nV]);
530 Print(
"%d, ", (*ivc)[i]);
532 Print(
"%d)", (*ivc)[nV]);
539 static inline long gcd(
const long a,
const long b)
541 long r, p0 =
a, p1 =
b;
595 static void cancel(mpz_t zaehler, mpz_t nenner)
600 mpz_gcd(g, zaehler, nenner);
602 mpz_div(zaehler , zaehler, g);
603 mpz_div(nenner , nenner, g);
610 static int isVectorNeg(
intvec* omega)
614 for(i=omega->
length(); i>=0; i--)
632 mpz_init_set_ui(sing_int, 2147483647);
645 mpz_set_si(zvec, (*weight)[i-1]);
646 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
647 mpz_add(zsum, zsum, zmul);
650 wgrad = mpz_get_ui(zsum);
652 if(mpz_cmp(zsum, sing_int)>0)
657 PrintS(
"\n// ** OVERFLOW in \"MwalkInitialForm\": ");
658 mpz_out_str( stdout, 10, zsum);
659 PrintS(
" is greater than 2147483647 (max. integer representation)");
678 int max = 0, maxtemp;
701 mpz_init_set_ui(sing_int, 2147483647);
714 mpz_set_si(zvec, (*weight)[i-1]);
715 mpz_mul_ui(zmul, zvec,
pGetExp(p, i));
716 mpz_add(ztmp, ztmp, zmul);
718 mpz_init_set(result, ztmp);
735 mpz_t
max; mpz_init(max);
736 mpz_t maxtmp; mpz_init(maxtmp);
746 if(mpz_cmp(maxtmp, max)>0)
748 mpz_set(max, maxtmp);
754 if(mpz_cmp(maxtmp, max)==0)
774 ideal Gomega =
idInit(nG, 1);
776 for(i=nG-1; i>=0; i--)
796 PrintS(
"//** the result may be WRONG, i.e. 0!!\n");
806 for(i=nG-1; i>=0; i--)
842 static inline long Mlcm(
long &i1,
long &i2)
844 long temp =
gcd(i1, i2);
845 return ((i1 / temp)* i2);
858 for(i=n-1; i>=0; i--)
860 result += (*a)[
i] * (*b)[
i];
874 for(i=n-1; i>=0; i--)
876 (*result)[
i] = (*a)[
i] - (*b)[
i];
889 for(i=nR-1; i>=0; i--)
906 for (i=0; i<niv; i++)
908 if ((*u)[i] != (*v)[i])
978 (*ivm)[
i] = (*iv)[
i];
982 (*ivm)[i*nR+i-1] = 1;
999 (*ivm)[
i] = (*iv)[
i];
1005 (*ivm)[j+i*nR] = (*iw)[j+i*nR];
1019 for(i=nR-1; i>=0; i--)
1105 if(pdeg > nV || pdeg <= 0)
1107 WerrorS(
"//** The perturbed degree is wrong!!");
1116 mpz_t *pert_vector = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1117 mpz_t *pert_vector1 = (mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
1121 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1122 mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
1126 int ntemp, maxAi, maxA=0;
1127 for(i=1; i<pdeg; i++)
1129 maxAi = (*ivtarget)[i*nV];
1134 for(j=i*nV+1; j<(i+1)*nV; j++)
1136 ntemp = (*ivtarget)[
j];
1153 mpz_t tot_deg; mpz_init(tot_deg);
1154 mpz_t maxdeg; mpz_init(maxdeg);
1155 mpz_t inveps; mpz_init(inveps);
1158 for(i=nG-1; i>=0; i--)
1161 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1163 mpz_set(tot_deg, maxdeg);
1168 mpz_mul_ui(inveps, tot_deg, maxA);
1169 mpz_add_ui(inveps, inveps, 1);
1173 #ifdef INVEPS_SMALL_IN_MPERTVECTOR 1174 if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
1177 mpz_fdiv_q_ui(inveps, inveps, pdeg);
1182 mpz_out_str(stdout, 10, inveps);
1187 for( i=1; i < pdeg; i++ )
1191 mpz_mul(pert_vector[j], pert_vector[j], inveps);
1192 if((*ivtarget)[i*nV+j]<0)
1194 mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
1198 mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
1205 mpz_init_set_ui(sing_int, 2147483647);
1208 mpz_init_set_ui(check_int, 100000);
1212 mpz_set(ztemp, pert_vector[0]);
1215 mpz_gcd(ztemp, ztemp, pert_vector[i]);
1216 if(mpz_cmp_si(ztemp, 1) == 0)
1221 if(mpz_cmp_si(ztemp, 1) != 0)
1225 mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
1231 if(mpz_cmp(pert_vector[i], check_int)>=0)
1235 mpz_fdiv_q_ui(pert_vector1[j], pert_vector[j], 100);
1246 (*result)[
i] = mpz_get_si(pert_vector1[i]);
1247 if(mpz_cmp(pert_vector1[i], sing_int)>=0)
1257 (*result)[
i] = mpz_get_si(pert_vector[i]);
1258 if(mpz_cmp(pert_vector[i], sing_int)>=0)
1264 PrintS(
"\n// ** OVERFLOW in \"MPertvectors\": ");
1265 mpz_out_str( stdout, 10, pert_vector[i]);
1266 PrintS(
" is greater than 2147483647 (max. integer representation)");
1267 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1275 Print(
"\n// %d element(s) of it is overflow!!", ntrue);
1280 mpz_clear(sing_int);
1281 mpz_clear(check_int);
1316 if(pdeg > nV || pdeg <= 0)
1318 WerrorS(
"//** The perturbed degree is wrong!!");
1323 (*pert_vector)[
i]=(*ivtarget)[
i];
1331 int ntemp, maxAi, maxA=0;
1332 for(i=1; i<pdeg; i++)
1334 maxAi = (*ivtarget)[i*nV];
1335 for(j=i*nV+1; j<(i+1)*nV; j++)
1337 ntemp = (*ivtarget)[
j];
1347 int inveps, tot_deg = 0, maxdeg;
1350 for(i=nG-1; i>=0; i--)
1354 if (maxdeg > tot_deg )
1361 inveps = (tot_deg * maxA) + 1;
1363 #ifdef INVEPS_SMALL_IN_FRACTAL 1365 if(inveps > pdeg && pdeg > 3)
1367 inveps = inveps / pdeg;
1371 PrintS(
"\n// the \"big\" inverse epsilon %d", inveps);
1375 for ( i=1; i < pdeg; i++ )
1379 (*pert_vector)[
j] = inveps*((*pert_vector)[
j]) + (*ivtarget)[i*nV+
j];
1383 int temp = (*pert_vector)[0];
1386 temp =
gcd(temp, (*pert_vector)[i]);
1396 (*pert_vector)[
i] = (*pert_vector)[
i] / temp;
1415 (*ivM)[i*nV +
i] = 1;
1435 (*ivM)[(i+1)*nV - i] = -1;
1446 int nV = ivstart->
length();
1451 (*ivM)[
i] = (*ivstart)[
i];
1455 (*ivM)[i*nV + i-1] = 1;
1466 int nV = ivstart->
length();
1471 (*ivM)[
i] = (*ivstart)[
i];
1479 (*ivM)[(i+1)*nV - i] = -1;
1507 for(i=nV-1; i>=0; i--)
1528 int ntemp, maxAi, maxA=0;
1531 maxAi = (*ivtarget)[i*nV];
1536 for(j=i*nV+1; j<(i+1)*nV; j++)
1538 ntemp = (*ivtarget)[
j];
1548 maxA = maxA + maxAi;
1553 mpz_t tot_deg; mpz_init(tot_deg);
1554 mpz_t maxdeg; mpz_init(maxdeg);
1555 mpz_t inveps; mpz_init(inveps);
1558 for(i=nG-1; i>=0; i--)
1561 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1563 mpz_set(tot_deg, maxdeg);
1569 mpz_mul_ui(inveps, tot_deg, maxA);
1570 mpz_add_ui(inveps, inveps, 1);
1573 #ifdef INVEPS_SMALL_IN_FRACTAL 1574 if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
1576 mpz_cdiv_q_ui(inveps, inveps, nV);
1584 mpz_t *ivtemp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
1585 mpz_t *pert_vector=(mpz_t *)
omAlloc(niv*
sizeof(mpz_t));
1587 for(i=0; i < nV; i++)
1589 mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
1590 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1593 mpz_t ztmp; mpz_init(ztmp);
1600 mpz_mul(ztmp, inveps, ivtemp[j]);
1601 if((*ivtarget)[i*nV+j]<0)
1603 mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
1607 mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
1613 mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
1619 mpz_init_set_ui(sing_int, 2147483647);
1626 mpz_set(ztmp, pert_vector[0]);
1627 for(i=0; i<niv; i++)
1629 mpz_gcd(ztmp, ztmp, pert_vector[i]);
1630 if(mpz_cmp_si(ztmp, 1)==0)
1636 for(i=0; i<niv; i++)
1638 mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
1639 (* result)[
i] = mpz_get_si(pert_vector[i]);
1644 for(i=0; i<niv; i++)
1646 if(mpz_cmp(pert_vector[i], sing_int)>0)
1653 Print(
"\n// Xlev = %d and the %d-th element is",
Xnlev, i+1);
1654 PrintS(
"\n// ** OVERFLOW in \"Mfpertvector\": ");
1655 mpz_out_str( stdout, 10, pert_vector[i]);
1656 PrintS(
" is greater than 2147483647 (max. integer representation)");
1657 Print(
"\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1671 mpz_clear(sing_int);
1710 if (result->m[k]!=
NULL)
1751 for(j=
IDELEMS(idLG)-1; j>=0; j--)
1753 F->m[
i] =
pAdd(F->m[i], idLG->m[j]);
1810 for(i=iva->
length()-1; i>=0; i--)
1812 if((*iva)[
i] - (*ivb)[
i] != 0)
1834 for(i=1; i < (vec->
length()); i++)
1864 if((*vec)[i] == k || (*vec)[i] == -k)
2243 target_weight !=
NULL && G !=
NULL);
2249 mpz_t t_zaehler, t_nenner;
2250 mpz_init(t_zaehler);
2253 mpz_t s_zaehler, s_nenner, temp, MwWd;
2254 mpz_init(s_zaehler);
2261 mpz_set_si(sing_int, 2147483647);
2263 mpz_t sing_int_half;
2264 mpz_init(sing_int_half);
2265 mpz_set_si(sing_int_half, 3*(1073741824/2));
2267 mpz_t deg_w0_p1, deg_d0_p1;
2268 mpz_init(deg_w0_p1);
2269 mpz_init(deg_d0_p1);
2293 for (j=0; j<nRing; j++)
2295 (*diff_weight1)[
j] = (*curr_weight)[
j];
2299 for(j=0; j<nRing; j++)
2301 (*curr_weight)[
j] = (*diff_weight1)[
j];
2303 for(j=0; j<nRing; j++)
2305 (*diff_weight1)[
j] = floor(0.1*(*diff_weight1)[j] + 0.5);
2311 for(j=0; j<nRing; j++)
2313 (*diff_weight1)[
j] = (*curr_weight)[
j];
2318 (*curr_weight)[
j] = (*diff_weight1)[
j];
2320 (*diff_weight1)[
j] = floor(0.1*(*diff_weight1)[j] + 0.5);
2325 intvec* diff_weight =
MivSub(target_weight, curr_weight);
2328 for (j=0; j<nG; j++)
2343 mpz_sub(s_zaehler, deg_w0_p1, MwWd);
2344 if(mpz_cmp(s_zaehler, t_null) != 0)
2347 mpz_sub(s_nenner, MwWd, deg_d0_p1);
2349 if( (mpz_cmp(s_zaehler,t_null) > 0 &&
2350 mpz_cmp(s_nenner, s_zaehler)>=0) ||
2351 (mpz_cmp(s_zaehler, t_null) < 0 &&
2352 mpz_cmp(s_nenner, s_zaehler)<=0))
2355 if (mpz_cmp(s_zaehler, t_null) < 0)
2357 mpz_neg(s_zaehler, s_zaehler);
2358 mpz_neg(s_nenner, s_nenner);
2362 cancel(s_zaehler, s_nenner);
2364 if(mpz_cmp(t_nenner, t_null) != 0)
2366 mpz_mul(sztn, s_zaehler, t_nenner);
2367 mpz_mul(sntz, s_nenner, t_zaehler);
2369 if(mpz_cmp(sztn,sntz) < 0)
2371 mpz_add(t_nenner, t_null, s_nenner);
2372 mpz_add(t_zaehler,t_null, s_zaehler);
2377 mpz_add(t_nenner, t_null, s_nenner);
2378 mpz_add(t_zaehler,t_null, s_zaehler);
2388 mpz_t *
vec=(mpz_t*)
omAlloc(nRing*
sizeof(mpz_t));
2393 if(mpz_cmp(t_nenner, t_null) == 0)
2396 PrintS(
"\n//MwalkNextWeightCC: t_nenner=0\n");
2399 diff_weight =
ivCopy(curr_weight);
2404 if(mpz_cmp_si(t_nenner, 1)==0 && mpz_cmp_si(t_zaehler,1)==0)
2407 diff_weight =
ivCopy(target_weight);
2414 gcd_tmp = (*curr_weight)[0];
2416 for (j=1; j<nRing; j++)
2418 gcd_tmp =
gcd(gcd_tmp, (*curr_weight)[j]);
2426 for (j=0; j<nRing; j++)
2428 gcd_tmp =
gcd(gcd_tmp, (*diff_weight)[j]);
2437 for (j=0; j<nRing; j++)
2439 (*curr_weight)[
j] = (*curr_weight)[
j]/gcd_tmp;
2440 (*diff_weight)[
j] = (*diff_weight)[
j]/gcd_tmp;
2444 #ifdef NEXT_VECTORS_CC 2445 Print(
"\n// gcd of the weight vectors (current and target) = %d", gcd_tmp);
2449 PrintS(
"\n// t_zaehler: "); mpz_out_str( stdout, 10, t_zaehler);
2450 PrintS(
", t_nenner: "); mpz_out_str( stdout, 10, t_nenner);
2458 for (j=0; j<nRing; j++)
2460 mpz_set_si(dcw, (*curr_weight)[j]);
2461 mpz_mul(s_nenner, t_nenner, dcw);
2463 if( (*diff_weight)[j]>0)
2465 mpz_mul_ui(s_zaehler, t_zaehler, (*diff_weight)[j]);
2469 mpz_mul_ui(s_zaehler, t_zaehler, -(*diff_weight)[j]);
2470 mpz_neg(s_zaehler, s_zaehler);
2472 mpz_add(sntz, s_nenner, s_zaehler);
2473 mpz_init_set(vec[j], sntz);
2475 #ifdef NEXT_VECTORS_CC 2476 Print(
"\n// j = %d ==> ", j);
2478 mpz_out_str( stdout, 10, t_nenner);
2479 Print(
" * %d)", (*curr_weight)[j]);
2480 PrintS(
" + ("); mpz_out_str( stdout, 10, t_zaehler);
2481 Print(
" * %d) = ", (*diff_weight)[j]);
2482 mpz_out_str( stdout, 10, s_nenner);
2484 mpz_out_str( stdout, 10, s_zaehler);
2485 PrintS(
" = "); mpz_out_str( stdout, 10, sntz);
2486 Print(
" ==> vector[%d]: ", j); mpz_out_str(stdout, 10, vec[j]);
2495 if(mpz_cmp_si(ggt,1) != 0)
2497 mpz_gcd(ggt, ggt, sntz);
2502 if(mpz_cmp_si(ggt,1) != 0)
2504 for (j=0; j<nRing; j++)
2506 mpz_divexact(vec[j], vec[j], ggt);
2509 #ifdef NEXT_VECTORS_CC 2510 PrintS(
"\n// gcd of elements of the vector: ");
2511 mpz_out_str( stdout, 10, ggt);
2514 for (j=0; j<nRing; j++)
2516 (*diff_weight)[
j] = mpz_get_si(vec[j]);
2521 for (j=0; j<nRing; j++)
2523 if(mpz_cmp(vec[j], sing_int)>=0)
2528 PrintS(
"\n// ** OVERFLOW in \"MwalkNextWeightCC\": ");
2529 mpz_out_str( stdout, 10, vec[j]);
2530 PrintS(
" is greater than 2147483647 (max. integer representation)\n");
2537 delete diff_weight1;
2538 mpz_clear(t_zaehler);
2539 mpz_clear(t_nenner);
2540 mpz_clear(s_zaehler);
2541 mpz_clear(s_nenner);
2546 mpz_clear(deg_w0_p1);
2547 mpz_clear(deg_d0_p1);
2550 mpz_clear(sing_int_half);
2551 mpz_clear(sing_int);
2698 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2700 r->wvhdl[0][i] = (*va)[
i];
2703 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2704 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2705 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2749 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2750 r->wvhdl[1] = (
int*)
omAlloc(nv*
sizeof(
int));
2754 r->wvhdl[0][
i] = (*vb)[
i];
2755 r->wvhdl[1][
i] = (*va)[
i];
2759 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2760 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2761 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2808 r->wvhdl[0] = (
int*)
omAlloc(nv*nv*
sizeof(
int));
2812 for(i=0; i<nv*nv; i++)
2813 r->wvhdl[0][i] = (*va)[
i];
2816 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2817 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2818 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2860 r->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2861 r->wvhdl[1] = (
int*)
omAlloc(nvs*
sizeof(
int));
2864 for(i=0; i<nvs; i++)
2866 r->wvhdl[1][
i] = (*va)[
i];
2870 r->wvhdl[0][
i] = (*vb)[
i];
2873 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2874 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2875 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2918 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2919 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2920 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2956 res->wvhdl[0] = (
int*)
omAlloc(nv*
sizeof(
int));
2958 res->wvhdl[0][i] = (*va)[
i];
2962 res->order = (
int *)
omAlloc(nb *
sizeof(
int *));
2963 res->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2964 res->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
2969 res->block1[0] = nv;
2974 res->block1[1] = nv;
3009 r->order = (
int *)
omAlloc(nb *
sizeof(
int *));
3010 r->block0 = (
int *)
omAlloc0(nb *
sizeof(
int *));
3011 r->block1 = (
int *)
omAlloc0(nb *
sizeof(
int *));
3072 for(i=hilb->
length()-1; i>=0; i--)
3091 poly p,lm,factor1,factor2;
3111 p =
pCopy(Gomega->m[i]);
3112 lm =
pCopy(Gomega->m[j]);
3159 int nwalk=0, endwalks=0, nnwinC=1;
3161 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3162 ring newRing, oldRing, TargetRing;
3166 intvec* pert_target_vector;
3171 #ifndef BUCHBERGER_ALG 3177 for(i=nV-1; i>0; i--)
3179 (*last_omega)[
i] = 1;
3181 (*last_omega)[0] = 10000;
3186 if(tp_deg > 1 && tp_deg <= nV)
3203 pert_target_vector = target_weight;
3210 target_weight =
Mivlp(nV);
3223 #ifdef PRINT_VECTORS 3224 MivString(curr_weight, target_weight, next_weight);
3243 if(
MivComp(next_weight, ivNull) == 1)
3251 if(
MivComp(next_weight, target_weight) == 1)
3254 for(i=nV-1; i>=0; i--)
3256 (*extra_curr_weight)[
i] = (*curr_weight)[
i];
3259 for(i=nV-1; i>=0; i--)
3261 (*curr_weight)[
i] = (*next_weight)[
i];
3280 #ifndef BUCHBERGER_ALG 3281 if(isNolVector(curr_weight) == 0)
3289 #endif // BUCHBERGER_ALG 3306 #ifdef BUCHBERGER_ALG 3311 #endif // BUCHBERGER_ALG 3365 Print(
"\n// takes %d steps and calls the recursion of level %d:",
3368 F1 =
LastGB(G,curr_weight, tp_deg-1);
3414 delete target_weight;
3431 for(i=
IDELEMS(G)-1; i>=0; i--)
3434 && (G->m[i]->next!=
NULL)
3435 && (G->m[i]->next->next!=
NULL)
3436 && (G->m[i]->next->next->next!=
NULL)
3437 && (G->m[i]->next->next->next->next!=
NULL) )
3451 for(i=
IDELEMS(G)-1; i>=0; i--)
3468 for(i=
IDELEMS(G)-1; i>=0; i--)
3471 && (G->m[i]->next!=
NULL)
3472 && (G->m[i]->next->next!=
NULL))
3507 for (i=nH-1;i>=0; i--)
3528 for(i=nG-1; i>=0; i--)
3596 int mtmp,
m=(*iva)[0];
3598 for(i=ivMat->
length(); i>=0; i--)
3617 mpz_set_si(ndeg, Trandegreebound(
G)+1);
3623 mpz_init_set_si(maxdeg, Trandegreebound(
G));
3626 mpz_pow_ui(ztmp, maxdeg, 2);
3627 mpz_mul_ui(ztmp, ztmp, 2);
3628 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3629 mpz_add(ndeg, ztmp, maxdeg);
3630 mpz_mul_ui(ndeg, ndeg, m);
3636 #endif //UPPER_BOUND 3638 #ifdef INVEPS_SMALL_IN_TRAN 3639 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3641 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3647 mpz_init_set(deg_tmp, ndeg);
3649 mpz_t *ivres=( mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3650 mpz_init_set_si(ivres[nV-1],1);
3652 for(i=nV-2; i>=0; i--)
3654 mpz_init_set(ivres[i], deg_tmp);
3655 mpz_mul(deg_tmp, deg_tmp, ndeg);
3658 mpz_t *ivtmp=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3664 mpz_init_set_ui(sing_int, 2147483647);
3673 if( (*ivMat)[i*nV+j] >= 0 )
3675 mpz_mul_ui(ivres[i], ivres[i], (*ivMat)[i*nV+j]);
3679 mpz_mul_ui(ivres[i], ivres[i], -(*ivMat)[i*nV+j]);
3680 mpz_neg(ivres[i], ivres[i]);
3682 mpz_add(ivtmp[j], ivtmp[j], ivres[i]);
3690 (*repr_vector)[
i] = mpz_get_si(ivtmp[i]);
3691 if(mpz_cmp(ivtmp[i], sing_int)>=0)
3698 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3699 mpz_out_str( stdout, 10, ivtmp[i]);
3700 PrintS(
" is greater than 2147483647 (max. integer representation)");
3701 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3707 ivString(repr_vector,
"repvector");
3708 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3717 mpz_clear(sing_int);
3727 static intvec* TranPertVector_lp(ideal
G)
3741 mpz_set_si(ndeg, Trandegreebound(G)+1);
3747 mpz_init_set_si(maxdeg, Trandegreebound(G));
3750 mpz_pow_ui(ztmp, maxdeg, 2);
3751 mpz_mul_ui(ztmp, ztmp, 2);
3752 mpz_mul_ui(maxdeg, maxdeg, nV+1);
3753 mpz_add(ndeg, ztmp, maxdeg);
3762 #ifdef INVEPS_SMALL_IN_TRAN 3763 if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
3764 mpz_cdiv_q_ui(ndeg, ndeg, nV);
3771 mpz_init_set(deg_tmp, ndeg);
3773 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3774 mpz_init_set_si(ivres[nV-1], 1);
3776 for(i=nV-2; i>=0; i--)
3778 mpz_init_set(ivres[i], deg_tmp);
3779 mpz_mul(deg_tmp, deg_tmp, ndeg);
3783 mpz_init_set_ui(sing_int, 2147483647);
3789 (*repr_vector)[
i] = mpz_get_si(ivres[i]);
3791 if(mpz_cmp(ivres[i], sing_int)>=0)
3797 PrintS(
"\n// ** OVERFLOW in \"Repr.Vector\": ");
3798 mpz_out_str( stdout, 10, ivres[i]);
3799 PrintS(
" is greater than 2147483647 (max. integer representation)");
3800 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repr_vector)[i]);
3806 ivString(repr_vector,
"repvector");
3807 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3815 mpz_clear(sing_int);
3832 int degtmp, maxdeg = 0;
3843 mpz_init_set_si(ztmp, maxdeg);
3844 mpz_t *ivres=(mpz_t *)
omAlloc(nV*
sizeof(mpz_t));
3845 mpz_init_set_si(ivres[nV-1], 1);
3847 for(i=nV-2; i>=0; i--)
3849 mpz_init_set(ivres[i], ztmp);
3850 mpz_mul_ui(ztmp, ztmp, maxdeg);
3853 mpz_t *ivtmp=(mpz_t*)
omAlloc(nV*
sizeof(mpz_t));
3861 if((*M)[i*nV+
j] < 0)
3863 mpz_mul_ui(ztmp, ivres[i], -(*M)[i*nV+j]);
3864 mpz_neg(ztmp, ztmp);
3867 mpz_mul_ui(ztmp, ivres[i], (*M)[i*nV+j]);
3869 mpz_add(ivtmp[j], ivtmp[j], ztmp);
3873 mpz_init_set_ui(sing_int, 2147483647);
3879 (*repvector)[
i] = mpz_get_si(ivtmp[i]);
3880 if(mpz_cmp(ivtmp[i], sing_int)>0)
3886 PrintS(
"\n// ** OVERFLOW in \"Repr.Matrix\": ");
3887 mpz_out_str( stdout, 10, ivtmp[i]);
3888 PrintS(
" is greater than 2147483647 (max. integer representation)");
3889 Print(
"\n// So vector[%d] := %d is wrong!!\n",i+1,(*repvector)[i]);
3896 Print(
"\n// %d element(s) of it are overflow!!", ntrue);
3902 mpz_clear(sing_int);
3922 intvec* orig_target_weight,
int tp_deg,
int npwinc)
3929 clock_t tinput = clock();
3932 int nwalk=0, endwalks=0, nnwinC=1;
3934 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
3935 ring newRing, oldRing, TargetRing;
3942 #ifndef BUCHBERGER_ALG 3948 for(i=nV-1; i>0; i--)
3949 (*last_omega)[
i] = 1;
3950 (*last_omega)[0] = 10000;
3955 if(tp_deg > 1 && tp_deg <= nV)
4026 #ifndef BUCHBERGER_ALG 4027 if(isNolVector(curr_weight) == 0)
4035 #endif // BUCHBERGER_ALG 4052 #ifdef BUCHBERGER_ALG 4057 #endif // BUCHBERGER_ALG 4092 #ifdef PRINT_VECTORS 4093 MivString(curr_weight, target_weight, next_weight);
4098 #ifdef TEST_OVERFLOW 4111 if(
MivComp(next_weight, ivNull) == 1)
4118 if(
MivComp(next_weight, target_weight) == 1)
4128 tproc=tproc+clock()-tinput;
4133 G =
Rec_LastGB(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4140 for(i=nV-1; i>=0; i--)
4142 (*curr_weight)[
i] = (*next_weight)[
i];
4167 tproc=tproc+clock()-tinput;
4168 F1 =
Rec_LastGB(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4170 delete target_weight;
4247 clock_t tostd, tproc;
4251 int nwalk=0, endwalks=0;
4253 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4256 ring newRing, oldRing;
4274 Print(
"\n// Computation of the first std took = %.2f sec",
4275 ((
double) tostd)/1000000);
4365 #ifdef PRINT_VECTORS 4366 MivString(curr_weight, target_weight, next_weight);
4375 #ifdef TEST_OVERFLOW 4376 goto TEST_OVERFLOW_OI;
4395 if(
MivComp(next_weight, ivNull) == 1)
4402 if(
MivComp(next_weight, target_weight) == 1)
4404 if(
MivSame(target_weight, exivlp)==1)
4413 G =
Rec_LastGB(G, curr_weight, target_weight, 2,1);
4421 for(i=nV-1; i>=0; i--)
4424 (*curr_weight)[
i] = (*next_weight)[
i];
4428 #ifdef TEST_OVERFLOW 4475 int weight_rad,
int pert_deg)
4478 target_weight !=
NULL && G->m[0] !=
NULL);
4489 (*curr_weight)[
i] = (*orig_M)[
i];
4492 int k=0,weight_norm;
4499 ideal G_test, G_test1, G_test2;
4507 while(weight_norm == 0)
4511 (*next_weight2)[
i] = rand() % 60000 - 30000;
4512 weight_norm = weight_norm + (*next_weight2)[
i]*(*next_weight2)[
i];
4514 weight_norm = 1 + floor(
sqrt(weight_norm));
4518 if((*next_weight2)[i] < 0)
4520 (*next_weight2)[
i] = 1 + (*curr_weight)[
i] + floor(weight_rad*(*next_weight2)[i]/weight_norm);
4524 (*next_weight2)[
i] = (*curr_weight)[
i] + floor(weight_rad*(*next_weight2)[i]/weight_norm);
4534 found_random_weight =
TRUE;
4546 delete curr_weight1;
4564 if(found_random_weight ==
TRUE)
4573 (*result)[
i] = (*next_weight2)[
i];
4580 (*result)[
i] = (*next_weight1)[
i];
4590 (*result)[
i] = (*next_weight2)[
i];
4597 (*result)[
i] = (*next_weight)[
i];
4609 (*result)[
i] = (*next_weight1)[
i];
4616 (*result)[
i] = (*next_weight)[
i];
4624 if(found_random_weight ==
TRUE)
4630 (*result)[
i] = (*next_weight2)[
i];
4637 (*result)[
i] = (*next_weight)[
i];
4645 (*result)[
i] = (*next_weight)[
i];
4651 delete next_weight2;
4654 if(found_random_weight ==
TRUE)
4661 delete next_weight1;
4668 return next_weight1;
4679 int tp_deg,
int npwinc)
4685 int nwalk=0, endwalks=0, nnwinC=1, nlast = 0;
4686 ideal Gomega,
M, F, Gomega1, Gomega2, M1,F1,
result,ssG;
4687 ring newRing, oldRing, TargetRing;
4690 #ifndef BUCHBERGER_ALG 4694 for(i=nV-1; i>0; i--)
4696 (*last_omega)[
i] = 1;
4698 (*last_omega)[0] = 10000;
4705 if(tp_deg > 1 && tp_deg <= nV)
4765 #ifndef BUCHBERGER_ALG 4766 if(isNolVector(curr_weight) == 0)
4792 #ifdef BUCHBERGER_ALG 4838 #ifdef PRINT_VECTORS 4839 MivString(curr_weight, target_weight, next_weight);
4853 if(
MivComp(next_weight, ivNull) == 1)
4860 if(
MivComp(next_weight, target_weight) == 1)
4868 G =
REC_GB_Mwalk(G,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4875 for(i=nV-1; i>=0; i--)
4877 (*curr_weight)[
i] = (*next_weight)[
i];
4900 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight, tp_deg+1,nnwinC);
4906 F1 =
REC_GB_Mwalk(F1,curr_weight, orig_target_weight,tp_deg+1,nnwinC);
4909 delete target_weight;
4953 #ifndef BUCHBERGER_ALG 4968 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
4978 ideal Gomega,
M, F, Gomega1, Gomega2, M1, F1,
G;
4980 ring newRing, oldRing;
4983 #ifndef BUCHBERGER_ALG 4987 for(i=nV-1; i>=0; i--)
4988 (*tmp_weight)[
i] = (*curr_weight)[
i];
4992 for(i=nV-1; i>0; i--)
4993 (*last_omega)[
i] = 1;
4994 (*last_omega)[0] = 10000;
5013 tif = tif + clock()-
to;
5021 #ifdef CHECK_IDEAL_MWALK 5022 Print(
"\n// **** Groebnerwalk took %d steps and ", nwalk);
5023 PrintS(
"\n// **** call the rec. Pert. Walk to compute a red GB of:");
5027 if(
MivSame(exivlp, target_weight)==1)
5032 Print(
"\n// time for the last std(Gw) = %.2f sec",
5033 ((
double) (clock()-tim)/1000000));
5068 #ifndef BUCHBERGER_ALG 5069 if(isNolVector(curr_weight) == 0)
5077 #endif // BUCHBERGER_ALG 5093 #ifdef BUCHBERGER_ALG 5099 tstd = tstd + clock() -
to;
5111 tlift = tlift + clock() -
to;
5127 tred = tred + clock() -
to;
5142 tnw = tnw + clock() -
to;
5143 #ifdef PRINT_VECTORS 5144 MivString(curr_weight, target_weight, next_weight);
5151 PrintS(
"\n// ** The computed vector does NOT stay in Cone!!\n");
5169 if(
MivComp(next_weight, ivNull) == 1)
5175 if(
MivComp(next_weight, target_weight) == 1)
5179 for(i=nV-1; i>=0; i--)
5181 (*tmp_weight)[
i] = (*curr_weight)[
i];
5182 (*curr_weight)[
i] = (*next_weight)[
i];
5194 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5206 ring baseRing,
int reduction,
int printout)
5219 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5226 int nV = baseRing->N;
5228 ideal Gomega,
M, F, FF, Gomega1, Gomega2, M1;
5230 ring XXRing = baseRing;
5245 (*curr_weight)[
i] = (*orig_M)[
i];
5246 (*target_weight)[
i] = (*target_M)[
i];
5248 #ifndef BUCHBERGER_ALG 5252 for(i=nV-1; i>0; i--)
5254 (*last_omega)[
i] = 1;
5256 (*last_omega)[0] = 10000;
5259 #ifdef CHECK_IDEAL_MWALK 5266 if(target_M->
length() == nV)
5275 if(orig_M->
length() == nV)
5279 newRing=
VMrRefine(target_weight, curr_weight);
5311 tif = tif + clock()-
to;
5314 #ifdef CHECK_IDEAL_MWALK 5317 idString(Gomega,
"//** Mwalk: Gomega");
5326 PrintS(
"middle of Cone");
5334 #ifndef BUCHBERGER_ALG 5335 if(isNolVector(curr_weight) == 0)
5347 if(orig_M->
length() == nV)
5351 newRing=
VMrRefine(target_weight, curr_weight);
5360 if(target_M->
length() == nV)
5364 newRing=
VMrRefine(target_weight, curr_weight);
5383 #ifndef BUCHBERGER_ALG 5390 tstd = tstd + clock() -
to;
5393 #ifdef CHECK_IDEAL_MWALK 5412 tlift = tlift + clock() -
to;
5414 #ifdef CHECK_IDEAL_MWALK 5428 #ifdef CHECK_IDEAL_MWALK 5455 tnw = tnw + clock() -
to;
5457 #ifdef PRINT_VECTORS 5460 MivString(curr_weight, target_weight, next_weight);
5465 if(
MivComp(curr_weight,next_weight)==1)
5470 if(
MivComp(target_weight,curr_weight) == 1)
5475 for(i=nV-1; i>=0; i--)
5478 (*curr_weight)[
i] = (*next_weight)[
i];
5489 #ifndef BUCHBERGER_ALG 5493 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5499 Print(
"\n//** Mwalk: Groebner Walk took %d steps.\n",
nstep);
5520 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5537 if(pert_deg > nV || pert_deg < 1)
5539 WerrorS(
"Invalid perturbation degree.\n");
5543 ideal Gomega,
M, F,FF, Gomega1, Gomega2, M1;
5556 (*curr_weight)[
i] = (*orig_M)[
i];
5557 (*target_weight)[
i] = (*target_M)[
i];
5560 #ifndef BUCHBERGER_ALG 5564 for(i=nV-1; i>0; i--)
5566 (*last_omega)[
i] = 1;
5568 (*last_omega)[0] = 10000;
5572 if(target_M->
length() == nV)
5580 if(orig_M->
length() == nV)
5583 newRing=
VMrRefine(target_weight, curr_weight);
5605 tif = tif + clock()-
to;
5612 #ifdef CHECK_IDEAL_MWALK 5615 idString(Gomega,
"//** Mrwalk: Gomega");
5629 #ifndef BUCHBERGER_ALG 5630 if(isNolVector(curr_weight) == 0)
5641 if(orig_M->
length() == nV)
5644 newRing=
VMrRefine(target_weight, curr_weight);
5653 if(target_M->
length() == nV)
5656 newRing=
VMrRefine(target_weight, curr_weight);
5670 #ifndef BUCHBERGER_ALG 5677 tstd = tstd + clock() -
to;
5680 #ifdef CHECK_IDEAL_MWALK 5699 tlift = tlift + clock() -
to;
5701 #ifdef CHECK_IDEAL_MWALK 5715 tstd = tstd + clock() -
to;
5718 #ifdef CHECK_IDEAL_MWALK 5745 tnw = tnw + clock() -
to;
5753 tif = tif + clock()-
to;
5763 if(target_M->
length() == nV)
5777 tnw = tnw + clock() -
to;
5785 tif = tif + clock()-
to;
5791 if(
MivComp(next_weight, ivNull) == 1 ||
MivComp(target_weight,curr_weight) == 1)
5799 if(
MivComp(curr_weight,next_weight)==1)
5804 #ifdef PRINT_VECTORS 5807 MivString(curr_weight, target_weight, next_weight);
5811 for(i=nV-1; i>=0; i--)
5813 (*curr_weight)[
i] = (*next_weight)[
i];
5822 #ifndef BUCHBERGER_ALG 5827 Print(
"\n//** Mrwalk: Groebner Walk took %d steps.\n",
nstep);
5830 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw,
nstep);
5864 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5872 int i, ntwC=1, ntestw=1, nV =
currRing->N;
5875 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
5877 WerrorS(
"Invalid perturbation degree.\n");
5882 ideal Gomega,
M, F, FF,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5883 ring newRing, oldRing, TargetRing;
5887 intvec* orig_target = target_weight;
5888 intvec* pert_target_vector = target_weight;
5891 #ifndef BUCHBERGER_ALG 5898 for(i=nV-1; i>0; i--)
5899 (*last_omega)[
i] = 1;
5900 (*last_omega)[0] = 10000;
5907 if(
MivComp(curr_weight, iv_dp) == 1)
5941 if(op_deg != 1)
delete iv_M_dp;
5946 if(tp_deg > 1 && tp_deg <= nV)
5958 if(
MivSame(target_weight, exivlp) == 1)
5969 pert_target_vector = target_weight;
5975 Print(
"\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
5976 #ifdef PRINT_VECTORS 5977 ivString(curr_weight,
"//** Mpwalk: new current weight");
5978 ivString(target_weight,
"//** Mpwalk: new target weight");
5991 tif = tif + clock()-
to;
5993 #ifdef CHECK_IDEAL_MWALK 5996 idString(Gomega,
"//** Mpwalk: Gomega");
5999 if(reduction == 0 &&
nstep > 1)
6012 if(endwalks ==
TRUE)
6023 #ifndef BUCHBERGER_ALG 6024 if(isNolVector(curr_weight) == 0)
6028 #endif // BUCHBERGER_ALG 6052 PrintS(
"\n// compute a rGB of Gw:\n");
6054 #ifndef BUCHBERGER_ALG 6064 #ifdef BUCHBERGER_ALG 6071 if(endwalks ==
TRUE)
6079 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
6080 ((
double) clock())/1000000 -((
double)tim) /1000000);
6087 tstd=tstd+clock()-
to;
6090 #ifdef CHECK_IDEAL_MWALK 6108 if(endwalks ==
FALSE)
6109 tlift = tlift+clock()-
to;
6113 #ifdef CHECK_IDEAL_MWALK 6135 PrintS(
"\n //** Mpwalk: reduce the Groebner basis.\n");
6142 if(endwalks ==
FALSE)
6143 tred = tred+clock()-
to;
6149 if(endwalks ==
TRUE)
6161 #ifdef PRINT_VECTORS 6164 MivString(curr_weight, target_weight, next_weight);
6177 if(
MivComp(next_weight, ivNull) == 1){
6183 if(
MivComp(next_weight, target_weight) == 1)
6186 for(i=nV-1; i>=0; i--)
6187 (*curr_weight)[
i] = (*next_weight)[
i];
6195 if(
MivSame(orig_target, exivlp) == 1) {
6219 if( ntestw != 1 || ntwC == 0)
6221 if(ntestw != 1 && printout >2)
6223 ivString(pert_target_vector,
"tau");
6224 PrintS(
"\n// ** perturbed target vector doesn't stay in cone!!");
6231 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1){
6240 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6261 delete target_weight;
6278 Print(
"\n//** Mpwalk: Perturbation Walk took %d steps.\n",
nstep);
6287 int op_deg,
int tp_deg,
int nP,
int reduction,
int printout)
6299 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
6307 int i, ntwC=1, ntestw=1, nV =
currRing->N;
6317 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
6319 WerrorS(
"Invalid perturbation degree.\n");
6325 ideal Gomega,
M, F, FF,
G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
6326 ring newRing, oldRing, TargetRing;
6335 (*curr_weight)[
i] = (*orig_M)[
i];
6336 (*target_weight)[
i] = (*target_M)[
i];
6338 intvec* orig_target = target_weight;
6339 intvec* pert_target_vector = target_weight;
6342 #ifndef BUCHBERGER_ALG 6349 for(i=nV-1; i>0; i--)
6350 (*last_omega)[
i] = 1;
6351 (*last_omega)[0] = 10000;
6356 if(orig_M->
length() == nV)
6358 if(
MivComp(curr_weight, iv_dp) == 1)
6414 if(op_deg != 1)
delete iv_M_dp;
6419 if(target_M->
length() == nV)
6421 if(tp_deg > 1 && tp_deg <= nV)
6430 if(
MivSame(target_weight, exivlp) == 1)
6441 pert_target_vector = target_weight;
6448 if(tp_deg > 1 && tp_deg <= nV)
6458 Print(
"\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6459 ivString(curr_weight,
"//** Mprwalk: new current weight");
6460 ivString(target_weight,
"//** Mprwalk: new target weight");
6468 tif = tif + clock()-
to;
6474 #ifdef CHECK_IDEAL_MWALK 6477 idString(Gomega,
"//** Mprwalk: Gomega");
6481 if(reduction == 0 &&
nstep > 1)
6494 if(endwalks ==
TRUE)
6505 #ifndef BUCHBERGER_ALG 6506 if(isNolVector(curr_weight) == 0)
6510 #endif // BUCHBERGER_ALG 6514 if(target_M->
length() == nV)
6531 if(endwalks ==
TRUE)
6540 PrintS(
"\n// compute a rGB of Gw:\n");
6542 #ifndef BUCHBERGER_ALG 6552 #ifdef BUCHBERGER_ALG 6558 #ifdef CHECK_IDEAL_MWALK 6565 if(endwalks ==
TRUE)
6569 Print(
"\n// time for the last std(Gw) = %.2f sec\n",
6570 ((
double) clock())/1000000 -((
double)tim) /1000000);
6574 tstd=tstd+clock()-
to;
6588 if(endwalks ==
FALSE)
6589 tlift = tlift+clock()-
to;
6593 #ifdef CHECK_IDEAL_MWALK 6615 PrintS(
"\n //** Mprwalk: reduce the Groebner basis.\n");
6622 if(endwalks ==
FALSE)
6623 tred = tred+clock()-
to;
6630 if(endwalks ==
TRUE)
6639 tnw = tnw + clock() -
to;
6648 tif = tif + clock()-
to;
6656 PrintS(
"\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
6660 if(target_M->
length() == nV)
6673 tnw = tnw + clock() -
to;
6681 tif = tif + clock()-
to;
6686 #ifdef PRINT_VECTORS 6689 MivString(curr_weight, target_weight, next_weight);
6701 if(
MivComp(next_weight, ivNull) == 1){
6707 if(
MivComp(next_weight, target_weight) == 1)
6710 for(i=nV-1; i>=0; i--)
6711 (*curr_weight)[
i] = (*next_weight)[
i];
6719 if(target_M->
length() == nV)
6721 if(
MivSame(orig_target, exivlp) == 1)
6744 if(ntestw != 1 || ntwC == 0)
6746 if(ntestw != 1 && printout > 2)
6748 #ifdef PRINT_VECTORS 6749 ivString(pert_target_vector,
"tau");
6751 PrintS(
"\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
6760 if(nP == 0 || tp_deg == 1 ||
MivSame(orig_target, exivlp) != 1 || target_M->
length() != nV)
6764 PrintS(
"\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
6773 PrintS(
"\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
6777 eF1 =
LastGB(F2, curr_weight, tp_deg-1);
6802 delete target_weight;
6820 Print(
"\n//** Mprwalk: Perturbation Walk took %d steps.\n",
nstep);
6837 (*ivM)[i*nV +
j] = 1;
6855 Print(
"\n\n// Entering the %d-th recursion:", nlev);
6858 ring new_ring, testring;
6860 ideal Gomega, Gomega1, Gomega2, FF, F, F1, Gresult, Gresult1, G1, Gt;
6863 #ifndef BUCHBERGER_ALG 6872 for(i = nV -1; i>=0; i--)
6874 (*omtmp)[
i] = (*ivtarget)[
i];
6880 for(i=nV-1; i>0; i--)
6881 (*last_omega)[
i] = 1;
6882 (*last_omega)[0] = 10000;
6885 for(i=0; i<nV; i++) {
6886 if(Xsigma->
length() == nV)
6887 (*omega)[
i] = (*Xsigma)[
i];
6889 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
6891 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
6894 if(nlev == 1)
Xcall = 1;
6901 #ifdef FIRST_STEP_FRACTAL 6904 if((nlev == 1 &&
Xcall == 0) || (nlev == 2 &&
Xngleich == 1))
6914 NEXT_VECTOR_FRACTAL:
6927 if (
MivComp(next_vect, omega2) == 1)
6933 Print(
"\n//** rec_fractal_call: Perturb the both vectors with degree %d.",nlev);
6940 if(ivtarget->
length() == nV)
6959 if(ivtarget->
length() == nV)
6978 for(i=nV-1; i>=0; i--) {
6979 (*omega2)[
i] = (*Xtau)[nV+
i];
6980 (*omega)[
i] = (*Xsigma)[nV+
i];
6995 #ifdef PRINT_VECTORS 6998 MivString(omega, omega2, next_vect);
7008 if(ivtarget->
length() == nV)
7023 #ifdef TEST_OVERFLOW 7025 Gt =
NULL;
return(Gt);
7029 Print(
"\n//** rec_fractal_call: Applying Buchberger's algorithm in ring r = %s;",
7046 Print(
"\n//** rec_fractal_call: Overflow. (4) Leaving the %d-th recursion with %d steps.\n",
7064 if (
MivComp(next_vect, XivNull) == 1)
7066 if(ivtarget->
length() == nV)
7091 Print(
"\n//** rec_fractal_call: Correct cone. (5) Leaving the %d-th recursion with %d steps.\n",
7096 idString(Gt,
"//** rec_fractal_call: Gt");
7104 PrintS(
"\n//** rec_fractal_call: Wrong cone. Tau doesn't stay in the correct cone.\n");
7107 #ifndef MSTDCC_FRACTAL 7109 if(ivtarget->
length() == nV)
7117 #ifdef TEST_OVERFLOW 7119 Gt =
NULL;
return(Gt);
7122 if(
MivSame(Xtau, Xtautmp) == 1)
7126 PrintS(
"\n//** rec_fractal_call: Updated vectors are equal to the old vectors.\n");
7129 goto FRACTAL_MSTDCC;
7135 for(i=nV-1; i>=0; i--)
7136 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+i];
7141 goto NEXT_VECTOR_FRACTAL;
7147 Print(
"\n//** rec_fractal_call: Wrong cone. Applying Buchberger's algorithm in ring = %s.\n",
7160 if(ivtarget->
length() == nV)
7184 if(ivtarget->
length() == nV)
7203 Print(
"\n//** rec_fractal_call: Vectors updated. (6) Leaving the %d-th recursion with %d steps.\n",
7215 for(i=nV-1; i>=0; i--) {
7217 (*omega)[
i] = (*next_vect)[
i];
7228 #ifdef CHECK_IDEAL_MWALK 7231 idString(Gomega,
"//** rec_fractal_call: Gomega");
7245 goto NEXT_VECTOR_FRACTAL;
7249 #ifndef BUCHBERGER_ALG 7250 if(isNolVector(omega) == 0)
7256 if(ivtarget->
length() == nV)
7279 PrintS(
"\n//** rec_fractal_call: Maximal recursion depth.\n");
7284 #ifdef BUCHBERGER_ALG 7300 #ifdef CHECK_IDEAL_MWALK 7303 idString(Gresult,
"//** rec_fractal_call: M");
7320 #ifdef CHECK_IDEAL_MWALK 7323 idString(F,
"//** rec_fractal_call: F");
7352 int weight_rad,
int reduction,
int printout)
7358 ring new_ring, testring;
7360 ideal Gomega, Gomega1, Gomega2, F, FF, F1, Gresult, Gresult1, G1, Gt;
7362 #ifndef BUCHBERGER_ALG 7374 for(
i = nV -1;
i>=0;
i--)
7376 (*omtmp)[
i] = (*ivtarget)[
i];
7380 for(
i=nV-1;
i>0;
i--)
7381 (*last_omega)[
i] = 1;
7382 (*last_omega)[0] = 10000;
7385 for(
i=0;
i<nV;
i++) {
7386 if(Xsigma->
length() == nV)
7387 (*omega)[
i] = (*Xsigma)[
i];
7389 (*omega)[
i] = (*Xsigma)[(nV*(nlev-1))+
i];
7391 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+
i];
7394 if(nlev == 1)
Xcall = 1;
7401 #ifdef FIRST_STEP_FRACTAL 7406 if((nlev == 1 &&
Xcall == 0) || (nlev == 2 &&
Xngleich == 1))
7416 NEXT_VECTOR_FRACTAL:
7429 PrintS(
"\n**// rec_r_fractal_call: there is a polynomial in Gomega with at least 3 monomials.\n");
7456 if (
MivComp(next_vect, omega2) == 1)
7462 Print(
"\n//** rec_r_fractal_call: Perturb both vectors with degree %d.",nlev);
7467 if(ivtarget->
length() == nV)
7486 if(ivtarget->
length() == nV)
7502 if(ivtarget->
length() > nV)
7510 for(
i=nV-1;
i>=0;
i--)
7512 (*omega2)[
i] = (*Xtau)[nV+
i];
7513 (*omega)[
i] = (*Xsigma)[nV+
i];
7553 #ifdef PRINT_VECTORS 7556 MivString(omega, omega2, next_vect);
7567 if(ivtarget->
length() == nV)
7586 #ifdef TEST_OVERFLOW 7593 Print(
"\n//** rec_r_fractal_call: applying Buchberger's algorithm in ring r = %s;",
7610 Print(
"\n//** rec_r_fractal_call: (1) Leaving the %d-th recursion with %d steps.\n",
7625 if (
MivComp(next_vect, XivNull) == 1)
7629 if(ivtarget->
length() == nV)
7654 Print(
"\n//** rec_r_fractal_call: (2) Leaving the %d-th recursion with %d steps.\n",
7664 Print(
"\n//** rec_r_fractal_call: target weight doesn't stay in the correct cone.\n");
7667 #ifndef MSTDCC_FRACTAL 7668 #ifdef PRINT_VECTORS 7675 if(ivtarget->
length() == nV)
7683 #ifdef TEST_OVERFLOW 7685 Gt =
NULL;
return(Gt);
7688 if(
MivSame(Xtau, Xtautmp) == 1)
7692 goto FRACTAL_MSTDCC;
7697 #ifdef PRINT_VECTORS 7704 for(
i=nV-1;
i>=0;
i--)
7705 (*omega2)[
i] = (*Xtau)[(nlev-1)*nV+
i];
7711 goto NEXT_VECTOR_FRACTAL;
7717 Print(
"\n//** rec_r_fractal_call: apply Buchberger's algorithm in ring = %s.\n",
7730 if(ivtarget->
length() == nV)
7754 if(ivtarget->
length() == nV)
7773 Print(
"\n//** rec_r_fractal_call: (3) Leaving the %d-th recursion with %d steps.\n",
7785 for(
i=nV-1;
i>=0;
i--)
7787 (*altomega)[
i] = (*omega)[
i];
7788 (*omega)[
i] = (*next_vect)[
i];
7801 #ifdef CHECK_IDEAL_MWALK 7804 idString(Gomega,
"//** rec_r_fractal_call: Gomega");
7818 goto NEXT_VECTOR_FRACTAL;
7822 #ifndef BUCHBERGER_ALG 7823 if(isNolVector(omega) == 0)
7828 if(ivtarget->
length() == nV)
7852 #ifdef BUCHBERGER_ALG 7868 #ifdef CHECK_IDEAL_MWALK 7871 idString(Gresult,
"//** rec_r_fractal_call: M");
7888 #ifdef CHECK_IDEAL_MWALK 7891 idString(F,
"//** rec_r_fractal_call: F");
7949 XivNull =
new intvec(nV);
7950 Xivinput = ivtarget;
7964 #ifdef FIRST_STEP_FRACTAL 7966 for(i=
IDELEMS(Gw)-1; i>=0; i--)
7969 && (Gw->m[i]->next!=
NULL)
7970 && (Gw->m[i]->next->next!=
NULL))
7974 if(ivstart->
length() == nV)
7976 if(
MivSame(ivstart, iv_dp) != 1)
8001 if(ivtarget->
length() == nV)
8003 if(
MivComp(ivtarget, Xivlp) != 1)
8041 if(ivtarget->
length() == nV)
8091 Print(
"\n// the numbers of Overflow_Error (%d)",
nnflow);
8108 int weight_rad,
int reduction,
int printout)
8136 XivNull =
new intvec(nV);
8137 Xivinput = ivtarget;
8151 #ifdef FIRST_STEP_FRACTAL 8153 for(i=
IDELEMS(Gw)-1; i>=0; i--)
8156 && (Gw->m[i]->next!=
NULL)
8157 && (Gw->m[i]->next->next!=
NULL))
8161 if(ivstart->
length() == nV)
8163 if(
MivSame(ivstart, iv_dp) != 1)
8188 if(ivtarget->
length() == nV)
8190 if(
MivComp(ivtarget, Xivlp) != 1)
8228 if(ivtarget->
length() == nV)
8278 Print(
"\n// the numbers of Overflow_Error (%d)",
nnflow);
8294 clock_t mtim = clock();
8301 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8303 clock_t tinput = clock();
8305 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
8306 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
8307 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
8309 ring newRing, oldRing, lpRing;
8317 int nGB, endwalks = 0, nwalkpert=0, npertstep=0;
8320 #ifndef BUCHBERGER_ALG 8325 for(
i=nV-1;
i>0;
i--)
8326 (*last_omega)[
i] = 1;
8327 (*last_omega)[0] = 10000;
8331 for(
i=nV-1;
i>=0;
i--)
8332 (*target_weight)[
i] = (*target_tmp)[
i];
8339 if(
MivComp(curr_weight, iv_dp) == 1)
8353 #ifdef REPRESENTATION_OF_SIGMA 8359 if(
MivComp(curr_weight, iv_dp) == 1)
8360 MDp = MatrixOrderdp(nV);
8364 curr_weight = RepresentationMatrix_Dp(G, MDp);
8378 tostd=tostd+clock()-
to;
8380 goto COMPUTE_NEW_VECTOR;
8395 #ifndef BUCHBERGER_ALG 8396 if(isNolVector(curr_weight) == 0)
8400 #endif // BUCHBERGER_ALG 8415 #ifdef BUCHBERGER_ALG 8420 #endif // BUCHBERGER_ALG 8421 tstd=tstd+clock()-
to;
8433 tlift=tlift+clock()-
to;
8446 tred=tred+clock()-
to;
8458 #ifdef PRINT_VECTORS 8459 MivString(curr_weight, target_weight, next_weight);
8471 OMEGA_OVERFLOW_TRAN_NEW:
8474 #ifdef TEST_OVERFLOW 8483 if(
MivSame(target_tmp, iv_lp) == 1)
8499 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0){
8508 G =
LastGB(G1, curr_weight, nV-1);
8514 npert[endwalks]=nwalk-npert_tmp;
8523 if(
MivComp(next_weight, target_weight) == 1 ||
8524 MivComp(next_weight, curr_weight) == 1 )
8530 npert[endwalks]=nwalk-npert_tmp;
8536 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1){
8543 if(
MivSame(target_tmp, iv_lp) == 1)
8590 if(p->next !=
NULL &&
8591 p->next->next !=
NULL &&
8592 p->next->next->next !=
NULL)
8597 (*vector_tmp)[
i] = (*target_weight)[
i];
8599 delete target_weight;
8602 if(
MivComp(vector_tmp, target_weight)==1)
8607 goto OMEGA_OVERFLOW_TRAN_NEW;
8614 goto OMEGA_OVERFLOW_TRAN_NEW;
8624 if(plength3 ==
FALSE)
8650 goto COMPUTE_NEW_VECTOR;
8654 for(
i=nV-1;
i>=0;
i--)
8655 (*curr_weight)[
i] = (*next_weight)[
i];
8659 #ifdef TEST_OVERFLOW 8690 ideal TranMrImprovwalk(ideal
G,
intvec* curr_weight,
intvec* target_tmp,
int nP,
int weight_rad,
int pert_deg)
8693 clock_t mtim = clock();
8700 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8702 clock_t tinput = clock();
8704 int nsteppert=0,
i, nV =
currRing->N, nwalk=0, npert_tmp=0;
8705 int *npert=(
int*)
omAlloc(2*nV*
sizeof(
int));
8706 ideal Gomega,
M,F, G1, Gomega1, Gomega2, M1, F1;
8708 ring newRing, oldRing, lpRing;
8716 int weight_norm, nGB, endwalks = 0, nwalkpert=0, npertstep=0;
8719 #ifndef BUCHBERGER_ALG 8724 for(
i=nV-1;
i>0;
i--)
8726 (*last_omega)[
i] = 1;
8728 (*last_omega)[0] = 10000;
8732 for(
i=nV-1;
i>=0;
i--)
8734 (*target_weight)[
i] = (*target_tmp)[
i];
8741 if(
MivComp(curr_weight, iv_dp) == 1)
8762 #ifdef REPRESENTATION_OF_SIGMA 8768 if(
MivComp(curr_weight, iv_dp) == 1)
8770 MDp = MatrixOrderdp(nV);
8776 curr_weight = RepresentationMatrix_Dp(
G, MDp);
8794 tostd=tostd+clock()-
to;
8796 goto COMPUTE_NEW_VECTOR;
8811 #ifndef BUCHBERGER_ALG 8812 if(isNolVector(curr_weight) == 0)
8820 #endif // BUCHBERGER_ALG 8838 #ifdef BUCHBERGER_ALG 8844 tstd=tstd+clock()-
to;
8855 tlift=tlift+clock()-
to;
8868 tred=tred+clock()-
to;
8956 #ifdef PRINT_VECTORS 8957 MivString(curr_weight, target_weight, next_weight);
8969 OMEGA_OVERFLOW_TRAN_NEW:
8972 #ifdef TEST_OVERFLOW 8976 #ifdef CHECK_IDEAL_MWALK 8981 if(
MivSame(target_tmp, iv_lp) == 1)
9008 if(nP == 0 ||
MivSame(target_tmp, iv_lp) == 0)
9019 G =
LastGB(G1, curr_weight, nV-1);
9025 npert[endwalks]=nwalk-npert_tmp;
9034 if(
MivComp(next_weight, target_weight) == 1 ||
MivComp(next_weight, curr_weight) == 1 )
9040 npert[endwalks]=nwalk-npert_tmp;
9046 if(endwalks == 1 &&
MivComp(next_weight, curr_weight) == 1)
9054 if(
MivSame(target_tmp, iv_lp) == 1)
9110 if(p->next !=
NULL &&
9111 p->next->next !=
NULL &&
9112 p->next->next->next !=
NULL)
9118 (*vector_tmp)[
i] = (*target_weight)[
i];
9120 delete target_weight;
9123 if(
MivComp(vector_tmp, target_weight)==1)
9128 goto OMEGA_OVERFLOW_TRAN_NEW;
9135 goto OMEGA_OVERFLOW_TRAN_NEW;
9145 if(plength3 ==
FALSE)
9171 goto COMPUTE_NEW_VECTOR;
9175 for(
i=nV-1;
i>=0;
i--)
9177 (*curr_weight)[
i] = (*next_weight)[
i];
9181 #ifdef TEST_OVERFLOW 9194 Print(
"\n// Computation took %d steps and %.2f sec", nwalk, ((
double) (clock()-mtim)/1000000));
9196 TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
9214 clock_t tinput=clock();
9218 if(tp_deg < 1 || tp_deg > nV)
9220 WerrorS(
"Invalid perturbation degree.\n");
9224 int nwalk=0, endwalks=0, ntestwinC=1;
9225 int tp_deg_tmp = tp_deg;
9226 ideal Gomega,
M, F,
G, M1, F1, Gomega1, Gomega2, G1;
9227 ring newRing, oldRing, TargetRing;
9260 target_weight =
Mivlp(nV);
9270 if(tp_deg != tp_deg_tmp)
9280 #ifndef BUCHBERGER_ALG 9285 for(i=nV-1; i>0; i--)
9287 (*last_omega)[
i] = 1;
9289 (*last_omega)[0] = 10000;
9308 #ifndef BUCHBERGER_ALG 9309 if(isNolVector(curr_weight) == 0)
9340 #ifdef BUCHBERGER_ALG 9345 #endif // BUCHBERGER_ALG 9383 #ifdef PRINT_VECTORS 9384 MivString(curr_weight, target_weight, next_weight);
9392 tproc = tproc+clock()-tinput;
9404 if(
MivComp(next_weight, ivNull) == 1)
9410 if(
MivComp(next_weight, target_weight) == 1)
9414 for(i=nV-1; i>=0; i--)
9417 (*curr_weight)[
i] = (*next_weight)[
i];
9451 tproc = tproc+clock()-tinput;
9463 delete target_weight;
9485 clock_t tostd, tproc;
9489 int nwalk=0, endwalks=0;
9490 int op_tmp = op_deg;
9491 ideal Gomega,
M, F,
G, Gomega1, Gomega2, M1, F1;
9492 ring newRing, oldRing;
9499 #ifndef BUCHBERGER_ALG 9502 intvec* cw_tmp = curr_weight;
9506 for(i=nV-1; i>0; i--)
9508 (*last_omega)[
i] = 1;
9510 (*last_omega)[0] = 10000;
9522 if(
MivComp(curr_weight, iv_dp) == 1)
9525 if(op_tmp == op_deg)
9537 if(op_tmp == op_deg)
9561 curr_weight = cw_tmp;
9592 for(i=nV-1; i>=0; i--)
9593 (*curr_weight)[
i] = (*extra_curr_weight)[
i];
9594 delete extra_curr_weight;
9600 #ifndef BUCHBERGER_ALG 9601 if(isNolVector(curr_weight) == 0)
9609 #endif // BUCHBERGER_ALG 9627 #ifdef BUCHBERGER_ALG 9632 #endif // BUCHBERGER_ALG 9670 #ifdef PRINT_VECTORS 9671 MivString(curr_weight, target_weight, next_weight);
9694 if(
MivComp(next_weight, ivNull) == 1)
9701 if(
MivComp(next_weight, target_weight) == 1)
9703 if(tp_deg == 1 ||
MivSame(target_weight, exivlp) == 0)
9723 for(i=nV-1; i>=0; i--)
9726 (*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)
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)