My Project
Loading...
Searching...
No Matches
walk.h File Reference
#include "kernel/structs.h"

Go to the source code of this file.

Functions

ideal MwalkInitialForm (ideal G, intvec *curr_weight)
 
intvecMwalkNextWeight (intvec *curr_weight, intvec *target_weight, ideal G)
 
int MivSame (intvec *u, intvec *v)
 
int M3ivSame (intvec *next_weight, intvec *u, intvec *v)
 
intvecMivdp (int nR)
 
intvecMivlp (int nR)
 
intvecMivMatrixOrder (intvec *iv)
 
intvecMivMatrixOrderdp (int iv)
 
intvecMPertVectors (ideal G, intvec *ivtarget, int pdeg)
 
intvecMPertVectorslp (ideal G, intvec *ivtarget, int pdeg)
 
intvecMivMatrixOrderlp (int nV)
 
intvecMfpertvector (ideal G, intvec *iv)
 
intvecMivUnit (int nV)
 
intvecMivWeightOrderlp (intvec *ivstart)
 
intvecMivWeightOrderdp (intvec *ivstart)
 
ideal MidLift (ideal Gomega, ideal M)
 
ideal MLiftLmalG (ideal L, ideal G)
 
ideal MLiftLmalGNew (ideal Gomega, ideal M, ideal G)
 
ideal MLiftLmalGMin (ideal L, ideal G)
 
intvecMkInterRedNextWeight (intvec *iva, intvec *ivb, ideal G)
 
intvecMPertNextWeight (intvec *iva, ideal G, int deg)
 
intvecMivperttarget (ideal G, int ndeg)
 
intvecMSimpleIV (intvec *iv)
 
ideal Mwalk (ideal Go, intvec *orig_M, intvec *target_M, ring baseRing, int reduction, int printout)
 
ideal Mrwalk (ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int pert_deg, int reduction, int printout)
 
ideal Mpwalk (ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP, int reduction, int printout)
 
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)
 
ideal Mfwalk (ideal G, intvec *ivstart, intvec *ivtarget, int reduction, int printout)
 
ideal Mfrwalk (ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad, int reduction, int printout)
 
intvecTranMPertVectorslp (ideal G)
 
ideal TranMImprovwalk (ideal Go, intvec *curr_weight, intvec *target_weight, int nP)
 
ideal MAltwalk1 (ideal G, int op, int tp, intvec *curr_weight, intvec *target_weight)
 
ideal MAltwalk2 (ideal G, intvec *curr_weight, intvec *target_weight)
 

Function Documentation

◆ M3ivSame()

int M3ivSame ( intvec * next_weight,
intvec * u,
intvec * v )

Definition at line 915 of file walk.cc.

916{
917 assume(temp->length() == u->length() && u->length() == v->length());
918
919 if((MivSame(temp, u)) == 1)
920 {
921 return 0;
922 }
923 if((MivSame(temp, v)) == 1)
924 {
925 return 1;
926 }
927 return 2;
928}
int length() const
Definition intvec.h:95
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
#define assume(x)
Definition mod2.h:389
int MivSame(intvec *u, intvec *v)
Definition walk.cc:894

◆ MAltwalk1()

ideal MAltwalk1 ( ideal G,
int op,
int tp,
intvec * curr_weight,
intvec * target_weight )

Definition at line 9672 of file walk.cc.

9674{
9675 Set_Error(FALSE );
9677#ifdef TIME_TEST
9678 BOOLEAN nOverflow_Error = FALSE;
9679#endif
9680 // Print("// pSetm_Error = (%d)", ErrorCheck());
9681
9682#ifdef TIME_TEST
9683 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
9684 xftinput = clock();
9685 clock_t tostd, tproc;
9686#endif
9687
9688 nstep = 0;
9689 int i, nV = currRing->N;
9690 int nwalk=0, endwalks=0;
9691 int op_tmp = op_deg;
9692 ideal Gomega, M, F, G, Gomega1, Gomega2, M1, F1;
9693 ring newRing, oldRing;
9694 intvec* next_weight;
9695 intvec* iv_M_dp;
9696 intvec* ivNull = new intvec(nV);
9697 intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
9698 intvec* exivlp = Mivlp(nV);
9699 //intvec* extra_curr_weight = new intvec(nV);
9700#ifndef BUCHBERGER_ALG
9701 intvec* hilb_func;
9702#endif
9703 intvec* cw_tmp = curr_weight;
9704
9705 // to avoid (1,0,...,0) as the target vector
9706 intvec* last_omega = new intvec(nV);
9707 for(i=nV-1; i>0; i--)
9708 {
9709 (*last_omega)[i] = 1;
9710 }
9711 (*last_omega)[0] = 10000;
9712
9713 ring XXRing = currRing;
9714
9715#ifdef TIME_TEST
9716 to=clock();
9717#endif
9718 /* compute a pertubed weight vector of the original weight vector.
9719 The perturbation degree is recursive decrease until that vector
9720 stays inn the correct cone. */
9721 while(1)
9722 {
9723 if(Overflow_Error == FALSE)
9724 {
9725 if(MivComp(curr_weight, iv_dp) == 1)
9726 {
9727 //rOrdStr(currRing) = "dp"
9728 if(op_tmp == op_deg)
9729 {
9730 G = MstdCC(Go);
9731 if(op_deg != 1)
9732 {
9733 iv_M_dp = MivMatrixOrderdp(nV);
9734 }
9735 }
9736 }
9737 }
9738 else
9739 {
9740 if(op_tmp == op_deg)
9741 {
9742 //rOrdStr(currRing) = (a(...),lp,C)
9743 if (rParameter(currRing) != NULL)
9744 {
9745 DefRingPar(cw_tmp);
9746 }
9747 else
9748 {
9749 rChangeCurrRing(VMrDefault(cw_tmp));
9750 }
9751 G = idrMoveR(Go, XXRing,currRing);
9752 G = MstdCC(G);
9753 if(op_deg != 1)
9754 iv_M_dp = MivMatrixOrder(cw_tmp);
9755 }
9756 }
9758 if(op_deg != 1)
9759 {
9760 curr_weight = MPertVectors(G, iv_M_dp, op_deg);
9761 }
9762 else
9763 {
9764 curr_weight = cw_tmp;
9765 break;
9766 }
9767 if(Overflow_Error == FALSE)
9768 {
9769 break;
9770 }
9772 op_deg --;
9773 }
9774#ifdef TIME_TEST
9775 tostd=clock()-to;
9776#endif
9777
9778 if(op_tmp != 1 )
9779 delete iv_M_dp;
9780 delete iv_dp;
9781
9782 if(currRing->order[0] == ringorder_a)
9783 goto NEXT_VECTOR;
9784
9785 while(1)
9786 {
9787 nwalk ++;
9788 nstep ++;
9789
9790#ifdef TIME_TEST
9791 to = clock();
9792#endif
9793 // compute an initial form ideal of <G> w.r.t. "curr_vector"
9794 Gomega = MwalkInitialForm(G, curr_weight);
9795#ifdef TIME_TEST
9796 xtif=xtif+clock()-to;
9797#endif
9798#if 0
9799 if(Overflow_Error == TRUE)
9800 {
9801 for(i=nV-1; i>=0; i--)
9802 (*curr_weight)[i] = (*extra_curr_weight)[i];
9803 delete extra_curr_weight;
9804
9805 newRing = currRing;
9806 goto MSTD_ALT1;
9807 }
9808#endif
9809#ifndef BUCHBERGER_ALG
9810 if(isNolVector(curr_weight) == 0)
9811 {
9812 hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
9813 }
9814 else
9815 {
9816 hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
9817 }
9818#endif // BUCHBERGER_ALG
9819
9820 oldRing = currRing;
9821
9822 // define a new ring which ordering is "(a(curr_weight),lp)
9823 if (rParameter(currRing) != NULL)
9824 {
9825 DefRingPar(curr_weight);
9826 }
9827 else
9828 {
9829 rChangeCurrRing(VMrDefault(curr_weight));
9830 }
9831 newRing = currRing;
9832 Gomega1 = idrMoveR(Gomega, oldRing,currRing);
9833
9834#ifdef TIME_TEST
9835 to=clock();
9836#endif
9837 // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
9838#ifdef BUCHBERGER_ALG
9839 M = MstdhomCC(Gomega1);
9840#else
9841 M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
9842 delete hilb_func;
9843#endif // BUCHBERGER_ALG
9844#ifdef TIME_TEST
9845 xtstd=xtstd+clock()-to;
9846#endif
9847
9848 // change the ring to oldRing
9849 rChangeCurrRing(oldRing);
9850 M1 = idrMoveR(M, newRing,currRing);
9851 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
9852
9853#ifdef TIME_TEST
9854 to=clock();
9855#endif
9856 // compute a reduced Groebner basis of <G> w.r.t. "newRing" by the lifting process
9857 F = MLifttwoIdeal(Gomega2, M1, G);
9858#ifdef TIME_TEST
9859 xtlift=xtlift+clock()-to;
9860#endif
9861
9862 idDelete(&M1);
9863 idDelete(&Gomega2);
9864 idDelete(&G);
9865
9866 // change the ring to newRing
9867 rChangeCurrRing(newRing);
9868 F1 = idrMoveR(F, oldRing,currRing);
9869 if (oldRing!=IDRING(currRingHdl)) rDelete(oldRing); // do not delete the global currRing
9870 oldRing=NULL;
9871
9872#ifdef TIME_TEST
9873 to=clock();
9874#endif
9875 // reduce the Groebner basis <G> w.r.t. new ring
9876 G = kInterRedCC(F1, NULL);
9877#ifdef TIME_TEST
9878 xtred=xtred+clock()-to;
9879#endif
9880 idDelete(&F1);
9881
9882 if(endwalks == 1)
9883 {
9884 break;
9885 }
9886 NEXT_VECTOR:
9887#ifdef TIME_TEST
9888 to=clock();
9889#endif
9890 // compute a next weight vector
9891 next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
9892#ifdef TIME_TEST
9893 xtnw=xtnw+clock()-to;
9894#endif
9895#ifdef PRINT_VECTORS
9896 MivString(curr_weight, target_weight, next_weight);
9897#endif
9898 if(Overflow_Error == TRUE)
9899 {
9900 newRing = currRing;
9901
9902 if (rParameter(currRing) != NULL)
9903 {
9904 DefRingPar(target_weight);
9905 }
9906 else
9907 {
9908 rChangeCurrRing(VMrDefault(target_weight));
9909 }
9910 F1 = idrMoveR(G, newRing,currRing);
9911 G = MstdCC(F1);
9912 idDelete(&F1);
9913 newRing = currRing;
9914 break; //for while
9915 }
9916
9917
9918 /* G is the wanted Groebner basis if next_weight == curr_weight */
9919 if(MivComp(next_weight, ivNull) == 1)
9920 {
9921 newRing = currRing;
9922 delete next_weight;
9923 break; //for while
9924 }
9925
9926 if(MivComp(next_weight, target_weight) == 1)
9927 {
9928 if(tp_deg == 1 || MivSame(target_weight, exivlp) == 0)
9929 endwalks = 1;
9930 else
9931 {
9932 // MSTD_ALT1:
9933#ifdef TIME_TEST
9934 nOverflow_Error = Overflow_Error;
9935 tproc = clock()-xftinput;
9936#endif
9937
9938 //Print("\n// main routine takes %d steps and calls \"Mpwalk\" (1,%d):", nwalk, tp_deg);
9939
9940 // compute the red. GB of <G> w.r.t. the lex order by the "recursive-modified" perturbation walk alg (1,tp_deg)
9941 G = Mpwalk_MAltwalk1(G, curr_weight, tp_deg);
9942 delete next_weight;
9943 break; // for while
9944 }
9945 }
9946
9947 //NOT Changed, to free memory
9948 for(i=nV-1; i>=0; i--)
9949 {
9950 //(*extra_curr_weight)[i] = (*curr_weight)[i];
9951 (*curr_weight)[i] = (*next_weight)[i];
9952 }
9953 delete next_weight;
9954 }//while
9955
9956 rChangeCurrRing(XXRing);
9957 ideal result = idrMoveR(G, newRing,currRing);
9958 id_Delete(&G, newRing);
9959
9960 delete ivNull;
9961 if(op_deg != 1 )
9962 {
9963 delete curr_weight;
9964 }
9965 delete exivlp;
9966#ifdef TIME_TEST
9967/*
9968 Print("\n// \"Main procedure\" took %d steps, %.2f sec. and Overflow_Error(%d)",
9969 nwalk, ((double) tproc)/1000000, nOverflow_Error);
9970
9971 TimeStringFractal(xftinput, tostd, xtif, xtstd,xtextra, xtlift, xtred, xtnw);
9972*/
9973 // Print("\n// pSetm_Error = (%d)", ErrorCheck());
9974 // Print("\n// Overflow_Error? (%d)", Overflow_Error);
9975 // Print("\n// Awalk1 took %d steps.\n", nstep);
9976#endif
9977 return(result);
9978}
int BOOLEAN
Definition auxiliary.h:88
#define TRUE
Definition auxiliary.h:101
#define FALSE
Definition auxiliary.h:97
int i
Definition cfEzgcd.cc:132
return result
intvec * hFirstSeries(ideal A, intvec *module_w, ideal Q, intvec *wdegree)
Definition hilb.cc:2150
#define idDelete(H)
delete an ideal
Definition ideals.h:29
VAR idhdl currRingHdl
Definition ipid.cc:57
#define IDRING(a)
Definition ipid.h:127
STATIC_VAR TreeM * G
Definition janet.cc:31
ideal kStd2(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
generic interface to GB/SB computations, large hilbert vectors
Definition kstd1.cc:2602
#define NULL
Definition omList.c:12
void rChangeCurrRing(ring r)
Definition polys.cc:16
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:248
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:454
@ ringorder_a
Definition ring.h:71
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition ring.h:631
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define M
Definition sirandom.c:25
@ isHomog
Definition structs.h:33
int F1(int a1, int &r1)
F1.
static ideal kInterRedCC(ideal F, ideal Q)
Definition walk.cc:269
intvec * MivUnit(int nV)
Definition walk.cc:1497
VAR int nstep
kstd2.cc
Definition walk.cc:80
static ideal MstdhomCC(ideal G)
Definition walk.cc:948
static int MivComp(intvec *iva, intvec *ivb)
Definition walk.cc:1799
intvec * MivMatrixOrderdp(int nV)
Definition walk.cc:1418
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition walk.cc:1089
intvec * MivMatrixOrder(intvec *iv)
Definition walk.cc:964
void Set_Error(BOOLEAN f)
Definition walk.cc:86
static ideal Mpwalk_MAltwalk1(ideal Go, intvec *curr_weight, int tp_deg)
Definition walk.cc:9378
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition walk.cc:1722
static ring VMrDefault(intvec *va)
Definition walk.cc:2681
VAR BOOLEAN Overflow_Error
Definition walk.cc:88
intvec * Mivlp(int nR)
Definition walk.cc:1023
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition walk.cc:762
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition walk.cc:2571
static void DefRingPar(intvec *va)
Definition walk.cc:2940
static ideal MstdCC(ideal G)
Definition walk.cc:933

◆ MAltwalk2()

ideal MAltwalk2 ( ideal G,
intvec * curr_weight,
intvec * target_weight )

Definition at line 4281 of file walk.cc.

4282{
4285 //BOOLEAN nOverflow_Error = FALSE;
4286 //Print("// pSetm_Error = (%d)", ErrorCheck());
4287#ifdef TIME_TEST
4288 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
4289 xftinput = clock();
4290 clock_t tostd, tproc;
4291#endif
4292 nstep = 0;
4293 int i, nV = currRing->N;
4294 int nwalk=0, endwalks=0;
4295 // int nhilb = 1;
4296 ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
4297 //ideal G1;
4298 //ring endRing;
4299 ring newRing, oldRing;
4300 intvec* ivNull = new intvec(nV);
4301 intvec* next_weight;
4302 //intvec* extra_curr_weight = new intvec(nV);
4303 //intvec* hilb_func;
4304 intvec* exivlp = Mivlp(nV);
4305 ring XXRing = currRing;
4306
4307 //Print("\n// ring r_input = %s;", rString(currRing));
4308#ifdef TIME_TEST
4309 to = clock();
4310#endif
4311 /* compute the reduced Groebner basis of the given ideal w.r.t.
4312 a "fast" monomial order, e.g. degree reverse lex. order (dp) */
4313 G = MstdCC(Go);
4314#ifdef TIME_TEST
4315 tostd=clock()-to;
4316
4317 Print("\n// Computation of the first std took = %.2f sec",
4318 ((double) tostd)/1000000);
4319#endif
4320 if(currRing->order[0] == ringorder_a)
4321 {
4322 goto NEXT_VECTOR;
4323 }
4324 while(1)
4325 {
4326 nwalk ++;
4327 nstep ++;
4328#ifdef TIME_TEST
4329 to = clock();
4330#endif
4331 /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
4332 Gomega = MwalkInitialForm(G, curr_weight);
4333#ifdef TIME_TEST
4334 xtif=xtif+clock()-to;
4335#endif
4336/*
4337 if(Overflow_Error == TRUE)
4338 {
4339 for(i=nV-1; i>=0; i--)
4340 (*curr_weight)[i] = (*extra_curr_weight)[i];
4341 delete extra_curr_weight;
4342 goto LAST_GB_ALT2;
4343 }
4344*/
4345 oldRing = currRing;
4346
4347 /* define a new ring that its ordering is "(a(curr_weight),lp) */
4348 if (rParameter(currRing) != NULL)
4349 {
4350 DefRingPar(curr_weight);
4351 }
4352 else
4353 {
4354 rChangeCurrRing(VMrDefault(curr_weight));
4355 }
4356 newRing = currRing;
4357 Gomega1 = idrMoveR(Gomega, oldRing,currRing);
4358#ifdef TIME_TEST
4359 to = clock();
4360#endif
4361 /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
4362 M = MstdhomCC(Gomega1);
4363#ifdef TIME_TEST
4364 xtstd=xtstd+clock()-to;
4365#endif
4366 /* change the ring to oldRing */
4367 rChangeCurrRing(oldRing);
4368 M1 = idrMoveR(M, newRing,currRing);
4369 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
4370#ifdef TIME_TEST
4371 to = clock();
4372#endif
4373 /* compute the reduced Groebner basis of <G> w.r.t. "newRing"
4374 by the liftig process */
4375 F = MLifttwoIdeal(Gomega2, M1, G);
4376#ifdef TIME_TEST
4377 xtlift=xtlift+clock()-to;
4378#endif
4379 idDelete(&M1);
4380 idDelete(&Gomega2);
4381 idDelete(&G);
4382
4383 /* change the ring to newRing */
4384 rChangeCurrRing(newRing);
4385 F1 = idrMoveR(F, oldRing,currRing);
4386#ifdef TIME_TEST
4387 to = clock();
4388#endif
4389 /* reduce the Groebner basis <G> w.r.t. newRing */
4390 G = kInterRedCC(F1, NULL);
4391#ifdef TIME_TEST
4392 xtred=xtred+clock()-to;
4393#endif
4394 idDelete(&F1);
4395
4396 if(endwalks == 1)
4397 break;
4398
4399 NEXT_VECTOR:
4400#ifdef TIME_TEST
4401 to = clock();
4402#endif
4403 /* compute a next weight vector */
4404 next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
4405#ifdef TIME_TEST
4406 xtnw=xtnw+clock()-to;
4407#endif
4408#ifdef PRINT_VECTORS
4409 MivString(curr_weight, target_weight, next_weight);
4410#endif
4411
4412 if(Overflow_Error == TRUE)
4413 {
4414 /*
4415 ivString(next_weight, "omega");
4416 PrintS("\n// ** The weight vector does NOT stay in Cone!!\n");
4417 */
4418#ifdef TEST_OVERFLOW
4419 goto TEST_OVERFLOW_OI;
4420#endif
4421
4422 newRing = currRing;
4423 if (rParameter(currRing) != NULL)
4424 {
4425 DefRingPar(target_weight);
4426 }
4427 else
4428 {
4429 rChangeCurrRing(VMrDefault(target_weight)); // Aenderung
4430 }
4431 F1 = idrMoveR(G, newRing,currRing);
4432 G = MstdCC(F1);
4433 idDelete(&F1);
4434 newRing = currRing;
4435 break;
4436 }
4437
4438 if(MivComp(next_weight, ivNull) == 1)
4439 {
4440 newRing = currRing;
4441 delete next_weight;
4442 break;
4443 }
4444
4445 if(MivComp(next_weight, target_weight) == 1)
4446 {
4447 if(MivSame(target_weight, exivlp)==1)
4448 {
4449 // LAST_GB_ALT2:
4450 //nOverflow_Error = Overflow_Error;
4451#ifdef TIME_TEST
4452 tproc = clock()-xftinput;
4453#endif
4454 //Print("\n// takes %d steps and calls the recursion of level 2:", nwalk);
4455 /* call the changed perturbation walk algorithm with degree 2 */
4456 G = Rec_LastGB(G, curr_weight, target_weight, 2,1);
4457 newRing = currRing;
4458 delete next_weight;
4459 break;
4460 }
4461 endwalks = 1;
4462 }
4463
4464 for(i=nV-1; i>=0; i--)
4465 {
4466 //(*extra_curr_weight)[i] = (*curr_weight)[i];
4467 (*curr_weight)[i] = (*next_weight)[i];
4468 }
4469 delete next_weight;
4470 }
4471#ifdef TEST_OVERFLOW
4472 TEST_OVERFLOW_OI:
4473#endif
4474 rChangeCurrRing(XXRing);
4475 G = idrMoveR(G, newRing,currRing);
4476 delete ivNull;
4477 delete exivlp;
4478
4479#ifdef TIME_TEST
4480 /*Print("\n// \"Main procedure\" took %d steps dnd %.2f sec. Overflow_Error (%d)",
4481 nwalk, ((double) tproc)/1000000, nOverflow_Error);
4482*/
4483 TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
4484
4485 //Print("\n// pSetm_Error = (%d)", ErrorCheck());
4486 //Print("\n// Overflow_Error? (%d)", nOverflow_Error);
4487 //Print("\n// Awalk2 took %d steps!!", nstep);
4488#endif
4489
4490 return(G);
4491}
#define Print
Definition emacs.cc:80
static ideal Rec_LastGB(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
Definition walk.cc:3934

◆ Mfpertvector()

intvec * Mfpertvector ( ideal G,
intvec * iv )

Definition at line 1513 of file walk.cc.

1514{
1515 int i, j, nG = IDELEMS(G);
1516 int nV = currRing->N;
1517 int niv = nV*nV;
1518
1519
1520 // Calculate maxA = Max(A2) + Max(A3) + ... + Max(AnV),
1521 // where the Ai are the i-te rows of the matrix 'targer_ord'.
1522 int ntemp, maxAi, maxA=0;
1523 for(i=1; i<nV; i++)
1524 {
1525 maxAi = (*ivtarget)[i*nV];
1526 if(maxAi<0)
1527 {
1528 maxAi = -maxAi;
1529 }
1530 for(j=i*nV+1; j<(i+1)*nV; j++)
1531 {
1532 ntemp = (*ivtarget)[j];
1533 if(ntemp < 0)
1534 {
1535 ntemp = -ntemp;
1536 }
1537 if(ntemp > maxAi)
1538 {
1539 maxAi = ntemp;
1540 }
1541 }
1542 maxA = maxA + maxAi;
1543 }
1544 intvec* ivUnit = Mivdp(nV);
1545
1546 // Calculate inveps = 1/eps, where 1/eps > deg(p)*maxA for all p in G.
1547 mpz_t tot_deg; mpz_init(tot_deg);
1548 mpz_t maxdeg; mpz_init(maxdeg);
1549 mpz_t inveps; mpz_init(inveps);
1550
1551
1552 for(i=nG-1; i>=0; i--)
1553 {
1554 mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
1555 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1556 {
1557 mpz_set(tot_deg, maxdeg);
1558 }
1559 }
1560
1561 delete ivUnit;
1562 //inveps = (tot_deg * maxA) + 1;
1563 mpz_mul_ui(inveps, tot_deg, maxA);
1564 mpz_add_ui(inveps, inveps, 1);
1565
1566 // takes "small" inveps
1567#ifdef INVEPS_SMALL_IN_FRACTAL
1568 if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
1569 {
1570 mpz_cdiv_q_ui(inveps, inveps, nV);
1571 }
1572 // choose the small inverse epsilon
1573#endif
1574
1575 // PrintLn(); mpz_out_str(stdout, 10, inveps);
1576
1577 // Calculate the perturbed target orders:
1578 mpz_t *ivtemp=(mpz_t *)omAlloc(nV*sizeof(mpz_t));
1579 mpz_t *pert_vector=(mpz_t *)omAlloc(niv*sizeof(mpz_t));
1580
1581 for(i=0; i < nV; i++)
1582 {
1583 mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
1584 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1585 }
1586
1587 mpz_t ztmp; mpz_init(ztmp);
1588 // BOOLEAN isneg = FALSE;
1589
1590 for(i=1; i<nV; i++)
1591 {
1592 for(j=0; j<nV; j++)
1593 {
1594 mpz_mul(ztmp, inveps, ivtemp[j]);
1595 if((*ivtarget)[i*nV+j]<0)
1596 {
1597 mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
1598 }
1599 else
1600 {
1601 mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
1602 }
1603 }
1604
1605 for(j=0; j<nV; j++)
1606 {
1607 mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
1608 }
1609 }
1610
1611 // 2147483647 is max. integer representation in SINGULAR
1612 mpz_t sing_int;
1613 mpz_init_set_ui(sing_int, 2147483647);
1614
1615 intvec* result = new intvec(niv);
1616 BOOLEAN nflow = FALSE;
1617
1618 // computes gcd
1619 mpz_set(ztmp, pert_vector[0]);
1620 for(i=0; i<niv; i++)
1621 {
1622 mpz_gcd(ztmp, ztmp, pert_vector[i]);
1623 if(mpz_cmp_si(ztmp, 1)==0)
1624 {
1625 break;
1626 }
1627 }
1628
1629 for(i=0; i<niv; i++)
1630 {
1631 mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
1632 (* result)[i] = mpz_get_si(pert_vector[i]);
1633 }
1634
1635 //CHECK_OVERFLOW:
1636
1637 for(i=0; i<niv; i++)
1638 {
1639 if(mpz_cmp(pert_vector[i], sing_int)>0)
1640 {
1641 if(nflow == FALSE)
1642 {
1643 Xnlev = i / nV;
1644 nflow = TRUE;
1646 Print("\n// Xlev = %d and the %d-th element is", Xnlev, i+1);
1647 PrintS("\n// ** OVERFLOW in \"Mfpertvector\": ");
1648 mpz_out_str( stdout, 10, pert_vector[i]);
1649 PrintS(" is greater than 2147483647 (max. integer representation)");
1650 Print("\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1651 }
1652 }
1653 }
1654 if(Overflow_Error == TRUE)
1655 {
1656 ivString(result, "new_vector");
1657 }
1658 omFree(pert_vector);
1659 omFree(ivtemp);
1660 mpz_clear(ztmp);
1661 mpz_clear(tot_deg);
1662 mpz_clear(maxdeg);
1663 mpz_clear(inveps);
1664 mpz_clear(sing_int);
1665
1667 for(j=0; j<IDELEMS(G); j++)
1668 {
1669 poly p=G->m[j];
1670 while(p!=NULL)
1671 {
1672 p_Setm(p,currRing);
1673 pIter(p);
1674 }
1675 }
1676 return result;
1677}
int p
Definition cfModGcd.cc:4086
int j
Definition facHensel.cc:110
#define pIter(p)
Definition monomials.h:37
#define omAlloc(size)
#define omFree(addr)
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
void PrintS(const char *s)
Definition reporter.cc:284
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...
Definition ring.cc:3526
#define IDELEMS(i)
static void ivString(intvec *iv, const char *ch)
Definition walk.cc:493
VAR int Xnlev
Definition walk.cc:1512
static int MwalkWeightDegree(poly p, intvec *weight_vector)
Definition walk.cc:669
intvec * Mivdp(int nR)
Definition walk.cc:1008

◆ Mfrwalk()

ideal Mfrwalk ( ideal G,
intvec * ivstart,
intvec * ivtarget,
int weight_rad,
int reduction,
int printout )

Definition at line 8213 of file walk.cc.

8215{
8216 BITSET save1 = si_opt_1; // save current options
8217 //check that weight radius is valid
8218 if(weight_rad < 0)
8219 {
8220 WerrorS("Invalid radius.\n");
8221 return NULL;
8222 }
8223 if(reduction == 0)
8224 {
8225 si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
8226 si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
8227 }
8230 //Print("// pSetm_Error = (%d)", ErrorCheck());
8231 //Print("\n// ring ro = %s;", rString(currRing));
8232
8233 nnflow = 0;
8234 Xngleich = 0;
8235 Xcall = 0;
8236#ifdef TIME_TEST
8237 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8238 xftinput = clock();
8239#endif
8240 ring oldRing = currRing;
8241 int i, nV = currRing->N;
8242 XivNull = new intvec(nV);
8243 Xivinput = ivtarget;
8244 ngleich = 0;
8245#ifdef TIME_TEST
8246 to=clock();
8247#endif
8248 ideal I = MstdCC(G);
8249 G = NULL;
8250#ifdef TIME_TEST
8251 xftostd=clock()-to;
8252#endif
8253 Xsigma = ivstart;
8254
8255 Xnlev=nV;
8256
8257#ifdef FIRST_STEP_FRACTAL
8258 ideal Gw = MwalkInitialForm(I, ivstart);
8259 for(i=IDELEMS(Gw)-1; i>=0; i--)
8260 {
8261 if((Gw->m[i]!=NULL) // len >=0
8262 && (Gw->m[i]->next!=NULL) // len >=1
8263 && (Gw->m[i]->next->next!=NULL)) // len >=2
8264 {
8265 intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
8266 intvec* Mdp;
8267 if(ivstart->length() == nV)
8268 {
8269 if(MivSame(ivstart, iv_dp) != 1)
8270 Mdp = MivWeightOrderdp(ivstart);
8271 else
8272 Mdp = MivMatrixOrderdp(nV);
8273 }
8274 else
8275 {
8276 Mdp = ivstart;
8277 }
8278
8279 Xsigma = Mfpertvector(I, Mdp);
8281
8282 delete Mdp;
8283 delete iv_dp;
8284 break;
8285 }
8286 }
8287 idDelete(&Gw);
8288#endif
8289
8290 ideal I1;
8291 intvec* Mlp;
8292 Xivlp = Mivlp(nV);
8293
8294 if(ivtarget->length() == nV)
8295 {
8296 if(MivComp(ivtarget, Xivlp) != 1)
8297 {
8298 if (rParameter(currRing) != NULL)
8299 DefRingPar(ivtarget);
8300 else
8301 rChangeCurrRing(VMrDefault(ivtarget));
8302
8303 I1 = idrMoveR(I, oldRing,currRing);
8304 Mlp = MivWeightOrderlp(ivtarget);
8305 Xtau = Mfpertvector(I1, Mlp);
8306 }
8307 else
8308 {
8309 if (rParameter(currRing) != NULL)
8310 DefRingParlp();
8311 else
8312 VMrDefaultlp();
8313
8314 I1 = idrMoveR(I, oldRing,currRing);
8315 Mlp = MivMatrixOrderlp(nV);
8316 Xtau = Mfpertvector(I1, Mlp);
8317 }
8318 }
8319 else
8320 {
8321 rChangeCurrRing(VMatrDefault(ivtarget));
8322 I1 = idrMoveR(I,oldRing,currRing);
8323 Mlp = ivtarget;
8324 Xtau = Mfpertvector(I1, Mlp);
8325 }
8326 delete Mlp;
8328
8329 //ivString(Xsigma, "Xsigma");
8330 //ivString(Xtau, "Xtau");
8331
8332 id_Delete(&I, oldRing);
8333 ring tRing = currRing;
8334 if(ivtarget->length() == nV)
8335 {
8336/*
8337 if (rParameter(currRing) != NULL)
8338 DefRingPar(ivstart);
8339 else
8340 rChangeCurrRing(VMrDefault(ivstart));
8341*/
8342 rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8343 }
8344 else
8345 {
8346 //rChangeCurrRing(VMatrDefault(ivstart));
8347 rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8348 }
8349
8350 I = idrMoveR(I1,tRing,currRing);
8351#ifdef TIME_TEST
8352 to=clock();
8353#endif
8354 ideal J = MstdCC(I);
8355 idDelete(&I);
8356#ifdef TIME_TEST
8357 xftostd=xftostd+clock()-to;
8358#endif
8359 ideal resF;
8360 ring helpRing = currRing;
8361
8362 J = rec_r_fractal_call(J,1,ivtarget,weight_rad,reduction,printout);
8363 //idString(J,"//*** Mfrwalk: J");
8364 //Print("\n//** Mfrwalk hier (1)\n");
8365 rChangeCurrRing(oldRing);
8366 //Print("\n//** Mfrwalk hier (2)\n");
8367 resF = idrMoveR(J, helpRing,currRing);
8368 //Print("\n//** Mfrwalk hier (3)\n");
8369 //idSkipZeroes(resF);
8370 //Print("\n//** Mfrwalk hier (4)\n");
8371 si_opt_1 = save1; //set original options, e. g. option(RedSB)
8372 delete Xivlp;
8373 //delete Xsigma;
8374 delete Xtau;
8375 delete XivNull;
8376 //Print("\n//** Mfrwalk hier (5)\n");
8377#ifdef TIME_TEST
8378 TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8379 xtlift, xtred, xtnw);
8380
8381
8382 // Print("\n// pSetm_Error = (%d)", ErrorCheck());
8383 Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8384 Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8385#endif
8386 //Print("\n//** Mfrwalk hier (6)\n");
8387 //idString(resF,"resF");
8388 //Print("\n//** Mfrwalk hier (7)\n");
8389 return(resF);
8390}
#define BITSET
Definition auxiliary.h:85
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition f5gb.cc:1089
void WerrorS(const char *s)
Definition feFopen.cc:24
VAR unsigned si_opt_1
Definition options.c:5
#define OPT_REDTAIL
Definition options.h:92
#define OPT_REDSB
Definition options.h:77
#define Sy_bit(x)
Definition options.h:31
intvec * MivWeightOrderdp(intvec *ivstart)
Definition walk.cc:1457
VAR intvec * Xtau
Definition walk.cc:4508
static ring VMrRefine(intvec *va, intvec *vb)
Definition walk.cc:2732
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *ivtarget, int weight_rad, int reduction, int printout)
Definition walk.cc:7454
VAR intvec * Xivlp
Definition walk.cc:4511
intvec * MivWeightOrderlp(intvec *ivstart)
Definition walk.cc:1437
VAR intvec * XivNull
Definition walk.cc:6928
VAR int Xcall
Definition walk.cc:6946
static void DefRingParlp(void)
Definition walk.cc:2989
static ring VMatrRefine(intvec *va, intvec *vb)
Definition walk.cc:2842
VAR intvec * Xivinput
Definition walk.cc:4510
VAR intvec * Xsigma
Definition walk.cc:4507
intvec * MivMatrixOrderlp(int nV)
Definition walk.cc:1402
VAR int ngleich
Definition walk.cc:4506
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition walk.cc:1513
static ring VMatrDefault(intvec *va)
Definition walk.cc:2791
static void VMrDefaultlp(void)
Definition walk.cc:2899
VAR int nnflow
Definition walk.cc:6945
VAR int Xngleich
Definition walk.cc:6947

◆ Mfwalk()

ideal Mfwalk ( ideal G,
intvec * ivstart,
intvec * ivtarget,
int reduction,
int printout )

Definition at line 8032 of file walk.cc.

8034{
8035 BITSET save1 = si_opt_1; // save current options
8036 if(reduction == 0)
8037 {
8038 si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
8039 //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
8040 }
8043 //Print("// pSetm_Error = (%d)", ErrorCheck());
8044 //Print("\n// ring ro = %s;", rString(currRing));
8045
8046 nnflow = 0;
8047 Xngleich = 0;
8048 Xcall = 0;
8049#ifdef TIME_TEST
8050 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8051 xftinput = clock();
8052#endif
8053 ring oldRing = currRing;
8054 int i, nV = currRing->N;
8055 XivNull = new intvec(nV);
8056 Xivinput = ivtarget;
8057 ngleich = 0;
8058#ifdef TIME_TEST
8059 to=clock();
8060#endif
8061 ideal I = MstdCC(G);
8062 G = NULL;
8063#ifdef TIME_TEST
8064 xftostd=clock()-to;
8065#endif
8066 Xsigma = ivstart;
8067
8068 Xnlev=nV;
8069
8070#ifdef FIRST_STEP_FRACTAL
8071 ideal Gw = MwalkInitialForm(I, ivstart);
8072 for(i=IDELEMS(Gw)-1; i>=0; i--)
8073 {
8074 if((Gw->m[i]!=NULL) // len >=0
8075 && (Gw->m[i]->next!=NULL) // len >=1
8076 && (Gw->m[i]->next->next!=NULL)) // len >=2
8077 {
8078 intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
8079 intvec* Mdp;
8080 if(ivstart->length() == nV)
8081 {
8082 if(MivSame(ivstart, iv_dp) != 1)
8083 Mdp = MivWeightOrderdp(ivstart);
8084 else
8085 Mdp = MivMatrixOrderdp(nV);
8086 }
8087 else
8088 {
8089 Mdp = ivstart;
8090 }
8091
8092 Xsigma = Mfpertvector(I, Mdp);
8094
8095 delete Mdp;
8096 delete iv_dp;
8097 break;
8098 }
8099 }
8100 idDelete(&Gw);
8101#endif
8102
8103 ideal I1;
8104 intvec* Mlp;
8105 Xivlp = Mivlp(nV);
8106
8107 if(ivtarget->length() == nV)
8108 {
8109 if(MivComp(ivtarget, Xivlp) != 1)
8110 {
8111 if (rParameter(currRing) != NULL)
8112 DefRingPar(ivtarget);
8113 else
8114 rChangeCurrRing(VMrDefault(ivtarget));
8115
8116 I1 = idrMoveR(I, oldRing,currRing);
8117 Mlp = MivWeightOrderlp(ivtarget);
8118 Xtau = Mfpertvector(I1, Mlp);
8119 }
8120 else
8121 {
8122 if (rParameter(currRing) != NULL)
8123 DefRingParlp();
8124 else
8125 VMrDefaultlp();
8126
8127 I1 = idrMoveR(I, oldRing,currRing);
8128 Mlp = MivMatrixOrderlp(nV);
8129 Xtau = Mfpertvector(I1, Mlp);
8130 }
8131 }
8132 else
8133 {
8134 rChangeCurrRing(VMatrDefault(ivtarget));
8135 I1 = idrMoveR(I,oldRing,currRing);
8136 Mlp = ivtarget;
8137 Xtau = Mfpertvector(I1, Mlp);
8138 }
8139 delete Mlp;
8141
8142 //ivString(Xsigma, "Xsigma");
8143 //ivString(Xtau, "Xtau");
8144
8145 id_Delete(&I, oldRing);
8146 ring tRing = currRing;
8147 if(ivtarget->length() == nV)
8148 {
8149/*
8150 if (rParameter(currRing) != NULL)
8151 DefRingPar(ivstart);
8152 else
8153 rChangeCurrRing(VMrDefault(ivstart));
8154*/
8155 rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8156 }
8157 else
8158 {
8159 //rChangeCurrRing(VMatrDefault(ivstart));
8160 rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8161 }
8162
8163 I = idrMoveR(I1,tRing,currRing);
8164#ifdef TIME_TEST
8165 to=clock();
8166#endif
8167 ideal J = MstdCC(I);
8168 idDelete(&I);
8169#ifdef TIME_TEST
8170 xftostd=xftostd+clock()-to;
8171#endif
8172 ideal resF;
8173 ring helpRing = currRing;
8174
8175 J = rec_fractal_call(J,1,ivtarget,reduction,printout);
8176 //idString(J,"//** Mfwalk: J");
8177 rChangeCurrRing(oldRing);
8178 //Print("\n//Mfwalk: (2)\n");
8179 resF = idrMoveR(J, helpRing,currRing);
8180 //Print("\n//Mfwalk: (3)\n");
8181 idSkipZeroes(resF);
8182 //Print("\n//Mfwalk: (4)\n");
8183
8184 si_opt_1 = save1; //set original options, e. g. option(RedSB)
8185 delete Xivlp;
8186 //delete Xsigma;
8187 delete Xtau;
8188 delete XivNull;
8189 //Print("\n//Mfwalk: (5)\n");
8190#ifdef TIME_TEST
8191 TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8192 xtlift, xtred, xtnw);
8193
8194
8195 //Print("\n// pSetm_Error = (%d)", ErrorCheck());
8196 Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8197 Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8198#endif
8199 //Print("\n//Mfwalk: (6)\n");
8200 //idString(resF,"//** Mfwalk: resF");
8201 return(idCopy(resF));
8202}
ideal idCopy(ideal A)
Definition ideals.h:60
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static ideal rec_fractal_call(ideal G, int nlev, intvec *ivtarget, int reduction, int printout)
Definition walk.cc:6952

◆ MidLift()

ideal MidLift ( ideal Gomega,
ideal M )

◆ Mivdp()

intvec * Mivdp ( int nR)

Definition at line 1008 of file walk.cc.

1009{
1010 int i;
1011 intvec* ivm = new intvec(nR);
1012
1013 for(i=nR-1; i>=0; i--)
1014 {
1015 (*ivm)[i] = 1;
1016 }
1017 return ivm;
1018}

◆ Mivlp()

intvec * Mivlp ( int nR)

Definition at line 1023 of file walk.cc.

1024{
1025 intvec* ivm = new intvec(nR);
1026 (*ivm)[0] = 1;
1027
1028 return ivm;
1029}

◆ MivMatrixOrder()

intvec * MivMatrixOrder ( intvec * iv)

Definition at line 964 of file walk.cc.

965{
966 int i, nR = iv->length();
967
968 intvec* ivm = new intvec(nR*nR);
969
970 for(i=0; i<nR; i++)
971 {
972 (*ivm)[i] = (*iv)[i];
973 }
974 for(i=1; i<nR; i++)
975 {
976 (*ivm)[i*nR+i-1] = 1;
977 }
978 return ivm;
979}

◆ MivMatrixOrderdp()

intvec * MivMatrixOrderdp ( int iv)

Definition at line 1418 of file walk.cc.

1419{
1420 int i;
1421 intvec* ivM = new intvec(nV*nV);
1422
1423 for(i=0; i<nV; i++)
1424 {
1425 (*ivM)[i] = 1;
1426 }
1427 for(i=1; i<nV; i++)
1428 {
1429 (*ivM)[(i+1)*nV - i] = -1;
1430 }
1431 return(ivM);
1432}

◆ MivMatrixOrderlp()

intvec * MivMatrixOrderlp ( int nV)

Definition at line 1402 of file walk.cc.

1403{
1404 int i;
1405 intvec* ivM = new intvec(nV*nV);
1406
1407 for(i=0; i<nV; i++)
1408 {
1409 (*ivM)[i*nV + i] = 1;
1410 }
1411 return(ivM);
1412}

◆ Mivperttarget()

intvec * Mivperttarget ( ideal G,
int ndeg )

◆ MivSame()

int MivSame ( intvec * u,
intvec * v )

Definition at line 894 of file walk.cc.

895{
896 assume(u->length() == v->length());
897
898 int i, niv = u->length();
899
900 for (i=0; i<niv; i++)
901 {
902 if ((*u)[i] != (*v)[i])
903 {
904 return 0;
905 }
906 }
907 return 1;
908}

◆ MivUnit()

intvec * MivUnit ( int nV)

Definition at line 1497 of file walk.cc.

1498{
1499 int i;
1500 intvec* ivM = new intvec(nV);
1501 for(i=nV-1; i>=0; i--)
1502 {
1503 (*ivM)[i] = 1;
1504 }
1505 return(ivM);
1506}

◆ MivWeightOrderdp()

intvec * MivWeightOrderdp ( intvec * ivstart)

Definition at line 1457 of file walk.cc.

1458{
1459 int i;
1460 int nV = ivstart->length();
1461 intvec* ivM = new intvec(nV*nV);
1462
1463 for(i=0; i<nV; i++)
1464 {
1465 (*ivM)[i] = (*ivstart)[i];
1466 }
1467 for(i=0; i<nV; i++)
1468 {
1469 (*ivM)[nV+i] = 1;
1470 }
1471 for(i=2; i<nV; i++)
1472 {
1473 (*ivM)[(i+1)*nV - i] = -1;
1474 }
1475 return(ivM);
1476}

◆ MivWeightOrderlp()

intvec * MivWeightOrderlp ( intvec * ivstart)

Definition at line 1437 of file walk.cc.

1438{
1439 int i;
1440 int nV = ivstart->length();
1441 intvec* ivM = new intvec(nV*nV);
1442
1443 for(i=0; i<nV; i++)
1444 {
1445 (*ivM)[i] = (*ivstart)[i];
1446 }
1447 for(i=1; i<nV; i++)
1448 {
1449 (*ivM)[i*nV + i-1] = 1;
1450 }
1451 return(ivM);
1452}

◆ MkInterRedNextWeight()

intvec * MkInterRedNextWeight ( intvec * iva,
intvec * ivb,
ideal G )

Definition at line 2571 of file walk.cc.

2572{
2573 intvec* tmp = new intvec(iva->length());
2574 intvec* result;
2575
2576 if(G == NULL)
2577 {
2578 return tmp;
2579 }
2580 if(MivComp(iva, ivb) == 1)
2581 {
2582 return tmp;
2583 }
2584 result = MwalkNextWeightCC(iva, ivb, G);
2585
2586 if(MivComp(result, iva) == 1)
2587 {
2588 delete result;
2589 return tmp;
2590 }
2591
2592 delete tmp;
2593 return result;
2594}
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition walk.cc:2229

◆ MLiftLmalG()

ideal MLiftLmalG ( ideal L,
ideal G )

◆ MLiftLmalGMin()

ideal MLiftLmalGMin ( ideal L,
ideal G )

◆ MLiftLmalGNew()

ideal MLiftLmalGNew ( ideal Gomega,
ideal M,
ideal G )

◆ MPertNextWeight()

intvec * MPertNextWeight ( intvec * iva,
ideal G,
int deg )

◆ MPertVectors()

intvec * MPertVectors ( ideal G,
intvec * ivtarget,
int pdeg )

Definition at line 1089 of file walk.cc.

1090{
1091 // ivtarget is a matrix order of a degree reverse lex. order
1092 int nV = currRing->N;
1093 //assume(pdeg <= nV && pdeg >= 0);
1094
1095 int i, j, nG = IDELEMS(G);
1096 intvec* v_null = new intvec(nV);
1097
1098 // Check that the perturbed degree is valid
1099 if(pdeg > nV || pdeg <= 0)
1100 {
1101 WerrorS("//** The perturbed degree is wrong!!");
1102 return v_null;
1103 }
1104 delete v_null;
1105
1106 if(pdeg == 1)
1107 {
1108 return ivtarget;
1109 }
1110 mpz_t *pert_vector = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
1111 mpz_t *pert_vector1 = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
1112
1113 for(i=0; i<nV; i++)
1114 {
1115 mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1116 mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
1117 }
1118 // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
1119 // where the Ai are the i-te rows of the matrix target_ord.
1120 int ntemp, maxAi, maxA=0;
1121 for(i=1; i<pdeg; i++)
1122 {
1123 maxAi = (*ivtarget)[i*nV];
1124 if(maxAi<0)
1125 {
1126 maxAi = -maxAi;
1127 }
1128 for(j=i*nV+1; j<(i+1)*nV; j++)
1129 {
1130 ntemp = (*ivtarget)[j];
1131 if(ntemp < 0)
1132 {
1133 ntemp = -ntemp;
1134 }
1135 if(ntemp > maxAi)
1136 {
1137 maxAi = ntemp;
1138 }
1139 }
1140 maxA += maxAi;
1141 }
1142
1143 // Calculate inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.
1144
1145 intvec* ivUnit = Mivdp(nV);
1146
1147 mpz_t tot_deg; mpz_init(tot_deg);
1148 mpz_t maxdeg; mpz_init(maxdeg);
1149 mpz_t inveps; mpz_init(inveps);
1150
1151
1152 for(i=nG-1; i>=0; i--)
1153 {
1154 mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
1155 if (mpz_cmp(maxdeg, tot_deg) > 0 )
1156 {
1157 mpz_set(tot_deg, maxdeg);
1158 }
1159 }
1160
1161 delete ivUnit;
1162 mpz_mul_ui(inveps, tot_deg, maxA);
1163 mpz_add_ui(inveps, inveps, 1);
1164
1165
1166 // takes "small" inveps
1167#ifdef INVEPS_SMALL_IN_MPERTVECTOR
1168 if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
1169 {
1170 // Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", mpz_get_si(inveps), pdeg);
1171 mpz_fdiv_q_ui(inveps, inveps, pdeg);
1172 // mpz_out_str(stdout, 10, inveps);
1173 }
1174#else
1175 // PrintS("\n// the \"big\" inverse epsilon: ");
1176 mpz_out_str(stdout, 10, inveps);
1177#endif
1178
1179 // pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg,
1180 // pert_vector := A1
1181 for( i=1; i < pdeg; i++ )
1182 {
1183 for(j=0; j<nV; j++)
1184 {
1185 mpz_mul(pert_vector[j], pert_vector[j], inveps);
1186 if((*ivtarget)[i*nV+j]<0)
1187 {
1188 mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
1189 }
1190 else
1191 {
1192 mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
1193 }
1194 }
1195 }
1196
1197 // 2147483647 is max. integer representation in SINGULAR
1198 mpz_t sing_int;
1199 mpz_init_set_ui(sing_int, 2147483647);
1200
1201 mpz_t check_int;
1202 mpz_init_set_ui(check_int, 100000);
1203
1204 mpz_t ztemp;
1205 mpz_init(ztemp);
1206 mpz_set(ztemp, pert_vector[0]);
1207 for(i=1; i<nV; i++)
1208 {
1209 mpz_gcd(ztemp, ztemp, pert_vector[i]);
1210 if(mpz_cmp_si(ztemp, 1) == 0)
1211 {
1212 break;
1213 }
1214 }
1215 if(mpz_cmp_si(ztemp, 1) != 0)
1216 {
1217 for(i=0; i<nV; i++)
1218 {
1219 mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
1220 }
1221 }
1222
1223 for(i=0; i<nV; i++)
1224 {
1225 if(mpz_cmp(pert_vector[i], check_int)>=0)
1226 {
1227 for(j=0; j<nV; j++)
1228 {
1229 mpz_fdiv_q_ui(pert_vector1[j], pert_vector[j], 100);
1230 }
1231 }
1232 }
1233
1234 intvec* result = new intvec(nV);
1235
1236 int ntrue=0;
1237
1238 for(i=0; i<nV; i++)
1239 {
1240 (*result)[i] = mpz_get_si(pert_vector1[i]);
1241 if(mpz_cmp(pert_vector1[i], sing_int)>=0)
1242 {
1243 ntrue++;
1244 }
1245 }
1246 if(ntrue > 0 || test_w_in_ConeCC(G,result)==0)
1247 {
1248 ntrue=0;
1249 for(i=0; i<nV; i++)
1250 {
1251 (*result)[i] = mpz_get_si(pert_vector[i]);
1252 if(mpz_cmp(pert_vector[i], sing_int)>=0)
1253 {
1254 ntrue++;
1255 if(Overflow_Error == FALSE)
1256 {
1258 PrintS("\n// ** OVERFLOW in \"MPertvectors\": ");
1259 mpz_out_str( stdout, 10, pert_vector[i]);
1260 PrintS(" is greater than 2147483647 (max. integer representation)");
1261 Print("\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1262 }
1263 }
1264 }
1265
1266 if(Overflow_Error == TRUE)
1267 {
1268 ivString(result, "pert_vector");
1269 Print("\n// %d element(s) of it is overflow!!", ntrue);
1270 }
1271 }
1272
1273 mpz_clear(ztemp);
1274 mpz_clear(sing_int);
1275 mpz_clear(check_int);
1276 omFree(pert_vector);
1277 omFree(pert_vector1);
1278 mpz_clear(tot_deg);
1279 mpz_clear(maxdeg);
1280 mpz_clear(inveps);
1281
1283 for(j=0; j<IDELEMS(G); j++)
1284 {
1285 poly p=G->m[j];
1286 while(p!=NULL)
1287 {
1288 p_Setm(p,currRing); pIter(p);
1289 }
1290 }
1291 return result;
1292}
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition walk.cc:786

◆ MPertVectorslp()

intvec * MPertVectorslp ( ideal G,
intvec * ivtarget,
int pdeg )

Definition at line 1300 of file walk.cc.

1301{
1302 // ivtarget is a matrix order of the lex. order
1303 int nV = currRing->N;
1304 //assume(pdeg <= nV && pdeg >= 0);
1305
1306 int i, j, nG = IDELEMS(G);
1307 intvec* pert_vector = new intvec(nV);
1308
1309 //Checking that the perturbated degree is valid
1310 if(pdeg > nV || pdeg <= 0)
1311 {
1312 WerrorS("//** The perturbed degree is wrong!!");
1313 return pert_vector;
1314 }
1315 for(i=0; i<nV; i++)
1316 {
1317 (*pert_vector)[i]=(*ivtarget)[i];
1318 }
1319 if(pdeg == 1)
1320 {
1321 return pert_vector;
1322 }
1323 // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
1324 // where the Ai are the i-te rows of the matrix target_ord.
1325 int ntemp, maxAi, maxA=0;
1326 for(i=1; i<pdeg; i++)
1327 {
1328 maxAi = (*ivtarget)[i*nV];
1329 for(j=i*nV+1; j<(i+1)*nV; j++)
1330 {
1331 ntemp = (*ivtarget)[j];
1332 if(ntemp > maxAi)
1333 {
1334 maxAi = ntemp;
1335 }
1336 }
1337 maxA += maxAi;
1338 }
1339
1340 // Calculate inveps := 1/eps, where 1/eps > deg(p)*max1 for all p in G.
1341 int inveps, tot_deg = 0, maxdeg;
1342
1343 intvec* ivUnit = Mivdp(nV);//19.02
1344 for(i=nG-1; i>=0; i--)
1345 {
1346 // maxdeg = pTotaldegree(G->m[i], currRing); //it's wrong for ex1,2,rose
1347 maxdeg = MwalkWeightDegree(G->m[i], ivUnit);
1348 if (maxdeg > tot_deg )
1349 {
1350 tot_deg = maxdeg;
1351 }
1352 }
1353 delete ivUnit;
1354
1355 inveps = (tot_deg * maxA) + 1;
1356
1357#ifdef INVEPS_SMALL_IN_FRACTAL
1358 // Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", inveps, pdeg);
1359 if(inveps > pdeg && pdeg > 3)
1360 {
1361 inveps = inveps / pdeg;
1362 }
1363 // Print(" %d", inveps);
1364#else
1365 PrintS("\n// the \"big\" inverse epsilon %d", inveps);
1366#endif
1367
1368 // Pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg
1369 for ( i=1; i < pdeg; i++ )
1370 {
1371 for(j=0; j<nV; j++)
1372 {
1373 (*pert_vector)[j] = inveps*((*pert_vector)[j]) + (*ivtarget)[i*nV+j];
1374 }
1375 }
1376
1377 int temp = (*pert_vector)[0];
1378 for(i=1; i<nV; i++)
1379 {
1380 temp = gcd(temp, (*pert_vector)[i]);
1381 if(temp == 1)
1382 {
1383 break;
1384 }
1385 }
1386 if(temp != 1)
1387 {
1388 for(i=0; i<nV; i++)
1389 {
1390 (*pert_vector)[i] = (*pert_vector)[i] / temp;
1391 }
1392 }
1393
1394 intvec* result = pert_vector;
1395 delete pert_vector;
1396 return result;
1397}
static long gcd(const long a, const long b)
Definition walk.cc:533

◆ Mprwalk()

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 )

Definition at line 6389 of file walk.cc.

6391{
6392 BITSET save1 = si_opt_1; // save current options
6393 if(reduction == 0)
6394 {
6395 si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
6396 si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
6397 }
6400 //Print("// pSetm_Error = (%d)", ErrorCheck());
6401#ifdef TIME_TEST
6402 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
6403 xtextra=0;
6404 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
6405 tinput = clock();
6406
6407 clock_t tim;
6408#endif
6409 nstep = 0;
6410 int i, ntwC=1, ntestw=1, nV = currRing->N; //polylength
6411
6412 //check that weight radius is valid
6413 if(weight_rad < 0)
6414 {
6415 WerrorS("Invalid radius.\n");
6416 return NULL;
6417 }
6418
6419 //check that perturbation degree is valid
6420 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
6421 {
6422 WerrorS("Invalid perturbation degree.\n");
6423 return NULL;
6424 }
6425
6426 BOOLEAN endwalks = FALSE;
6427
6428 ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
6429 ring newRing, oldRing, TargetRing;
6430 intvec* iv_M;
6431 intvec* iv_M_dp;
6432 intvec* iv_M_lp;
6433 intvec* exivlp = Mivlp(nV);
6434 intvec* curr_weight = new intvec(nV);
6435 intvec* target_weight = new intvec(nV);
6436 for(i=0; i<nV; i++)
6437 {
6438 (*curr_weight)[i] = (*orig_M)[i];
6439 (*target_weight)[i] = (*target_M)[i];
6440 }
6441 intvec* orig_target = target_weight;
6442 intvec* pert_target_vector = target_weight;
6443 intvec* ivNull = new intvec(nV);
6444 intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
6445#ifndef BUCHBERGER_ALG
6446 intvec* hilb_func;
6447#endif
6448 intvec* next_weight;
6449
6450 // to avoid (1,0,...,0) as the target vector
6451 intvec* last_omega = new intvec(nV);
6452 for(i=nV-1; i>0; i--)
6453 (*last_omega)[i] = 1;
6454 (*last_omega)[0] = 10000;
6455
6456 ring XXRing = currRing;
6457
6458 // perturbs the original vector
6459 if(orig_M->length() == nV)
6460 {
6461 if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
6462 {
6463#ifdef TIME_TEST
6464 to = clock();
6465#endif
6466 G = MstdCC(Go);
6467#ifdef TIME_TEST
6468 tostd = clock()-to;
6469#endif
6470 if(op_deg != 1)
6471 {
6472 iv_M_dp = MivMatrixOrderdp(nV);
6473 curr_weight = MPertVectors(G, iv_M_dp, op_deg);
6474 }
6475 }
6476 else
6477 {
6478 //define ring order := (a(curr_weight),lp);
6479 if (rParameter(currRing) != NULL)
6480 DefRingPar(curr_weight);
6481 else
6482 rChangeCurrRing(VMrDefault(curr_weight));
6483
6484 G = idrMoveR(Go, XXRing,currRing);
6485#ifdef TIME_TEST
6486 to = clock();
6487#endif
6488 G = MstdCC(G);
6489#ifdef TIME_TEST
6490 tostd = clock()-to;
6491#endif
6492 if(op_deg != 1)
6493 {
6494 iv_M_dp = MivMatrixOrder(curr_weight);
6495 curr_weight = MPertVectors(G, iv_M_dp, op_deg);
6496 }
6497 }
6498 }
6499 else
6500 {
6502 G = idrMoveR(Go, XXRing,currRing);
6503#ifdef TIME_TEST
6504 to = clock();
6505#endif
6506 G = MstdCC(G);
6507#ifdef TIME_TEST
6508 tostd = clock()-to;
6509#endif
6510 if(op_deg != 1)
6511 {
6512 curr_weight = MPertVectors(G, orig_M, op_deg);
6513 }
6514 }
6515
6516 delete iv_dp;
6517 if(op_deg != 1) delete iv_M_dp;
6518
6519 ring HelpRing = currRing;
6520
6521 // perturbs the target weight vector
6522 if(target_M->length() == nV)
6523 {
6524 if(tp_deg > 1 && tp_deg <= nV)
6525 {
6526 if (rParameter(currRing) != NULL)
6527 DefRingPar(target_weight);
6528 else
6529 rChangeCurrRing(VMrDefault(target_weight));
6530
6531 TargetRing = currRing;
6532 ssG = idrMoveR(G,HelpRing,currRing);
6533 if(MivSame(target_weight, exivlp) == 1)
6534 {
6535 iv_M_lp = MivMatrixOrderlp(nV);
6536 target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
6537 }
6538 else
6539 {
6540 iv_M_lp = MivMatrixOrder(target_weight);
6541 target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
6542 }
6543 delete iv_M_lp;
6544 pert_target_vector = target_weight;
6545 rChangeCurrRing(HelpRing);
6546 G = idrMoveR(ssG, TargetRing,currRing);
6547 }
6548 }
6549 else
6550 {
6551 if(tp_deg > 1 && tp_deg <= nV)
6552 {
6553 rChangeCurrRing(VMatrDefault(target_M));
6554 TargetRing = currRing;
6555 ssG = idrMoveR(G,HelpRing,currRing);
6556 target_weight = MPertVectors(ssG, target_M, tp_deg);
6557 }
6558 }
6559 if(printout > 0)
6560 {
6561 Print("\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6562 ivString(curr_weight, "//** Mprwalk: new current weight");
6563 ivString(target_weight, "//** Mprwalk: new target weight");
6564 }
6565
6566#ifdef TIME_TEST
6567 to = clock();
6568#endif
6569 Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
6570#ifdef TIME_TEST
6571 tif = tif + clock()-to; //time for computing initial form ideal
6572#endif
6573
6574 while(1)
6575 {
6576 nstep ++;
6577#ifdef CHECK_IDEAL_MWALK
6578 if(printout > 1)
6579 {
6580 idString(Gomega,"//** Mprwalk: Gomega");
6581 }
6582#endif
6583
6584 if(reduction == 0 && nstep > 1)
6585 {
6586 FF = middleOfCone(G,Gomega);
6587 if(FF != NULL)
6588 {
6589 idDelete(&G);
6590 G = idCopy(FF);
6591 idDelete(&FF);
6592 goto NEXT_VECTOR;
6593 }
6594 }
6595
6596#ifdef ENDWALKS
6597 if(endwalks == TRUE)
6598 {
6599 if(printout > 0)
6600 {
6601 Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6602 //idElements(G, "G");
6603 //headidString(G, "G");
6604 }
6605 }
6606#endif
6607
6608#ifndef BUCHBERGER_ALG
6609 if(isNolVector(curr_weight) == 0)
6610 hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
6611 else
6612 hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
6613#endif // BUCHBERGER_ALG
6614
6615 oldRing = currRing;
6616
6617 if(target_M->length() == nV)
6618 {/*
6619 // define a new ring with ordering "(a(curr_weight),lp)
6620 if (rParameter(currRing) != NULL)
6621 DefRingPar(curr_weight);
6622 else
6623 rChangeCurrRing(VMrDefault(curr_weight));
6624*/
6625 rChangeCurrRing(VMrRefine(target_M,curr_weight));
6626 }
6627 else
6628 {
6629 rChangeCurrRing(VMatrRefine(target_M,curr_weight));
6630 }
6631 newRing = currRing;
6632 Gomega1 = idrMoveR(Gomega, oldRing,currRing);
6633#ifdef ENDWALKS
6634 if(endwalks == TRUE)
6635 {
6636 if(printout > 0)
6637 {
6638 Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6639
6640 //idElements(Gomega1, "Gw");
6641 //headidString(Gomega1, "headGw");
6642
6643 PrintS("\n// compute a rGB of Gw:\n");
6644 }
6645#ifndef BUCHBERGER_ALG
6646 ivString(hilb_func, "w");
6647#endif
6648 }
6649#endif
6650#ifdef TIME_TEST
6651 tim = clock();
6652 to = clock();
6653#endif
6654 // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
6655#ifdef BUCHBERGER_ALG
6656 M = MstdhomCC(Gomega1);
6657#else
6658 M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
6659 delete hilb_func;
6660#endif
6661#ifdef CHECK_IDEAL_MWALK
6662 if(printout > 2)
6663 {
6664 idString(M,"//** Mprwalk: M");
6665 }
6666#endif
6667#ifdef TIME_TEST
6668 if(endwalks == TRUE)
6669 {
6670 xtstd = xtstd+clock()-to;
6671#ifdef ENDWALKS
6672 Print("\n// time for the last std(Gw) = %.2f sec\n",
6673 ((double) clock())/1000000 -((double)tim) /1000000);
6674#endif
6675 }
6676 else
6677 tstd=tstd+clock()-to;
6678#endif
6679 /* change the ring to oldRing */
6680 rChangeCurrRing(oldRing);
6681 M1 = idrMoveR(M, newRing,currRing);
6682 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
6683#ifdef TIME_TEST
6684 to=clock();
6685#endif
6686 /* compute a representation of the generators of submod (M)
6687 with respect to those of mod (Gomega).
6688 Gomega is a reduced Groebner basis w.r.t. the current ring */
6689 F = MLifttwoIdeal(Gomega2, M1, G);
6690#ifdef TIME_TEST
6691 if(endwalks == FALSE)
6692 tlift = tlift+clock()-to;
6693 else
6694 xtlift=clock()-to;
6695#endif
6696#ifdef CHECK_IDEAL_MWALK
6697 if(printout > 2)
6698 {
6699 idString(F,"//** Mprwalk: F");
6700 }
6701#endif
6702
6703 idDelete(&M1);
6704 idDelete(&Gomega2);
6705 idDelete(&G);
6706
6707 // change the ring to newRing
6708 rChangeCurrRing(newRing);
6709 if(reduction == 0)
6710 {
6711 G = idrMoveR(F,oldRing,currRing);
6712 }
6713 else
6714 {
6715 F1 = idrMoveR(F, oldRing,currRing);
6716 if(printout > 2)
6717 {
6718 PrintS("\n //** Mprwalk: reduce the Groebner basis.\n");
6719 }
6720#ifdef TIME_TEST
6721 to=clock();
6722#endif
6723 G = kInterRedCC(F1, NULL);
6724#ifdef TIME_TEST
6725 if(endwalks == FALSE)
6726 tred = tred+clock()-to;
6727 else
6728 xtred=clock()-to;
6729#endif
6730 idDelete(&F1);
6731 }
6732
6733 if(endwalks == TRUE)
6734 break;
6735
6736 NEXT_VECTOR:
6737#ifdef TIME_TEST
6738 to = clock();
6739#endif
6740 next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
6741#ifdef TIME_TEST
6742 tnw = tnw + clock() - to;
6743#endif
6744
6745#ifdef TIME_TEST
6746 to = clock();
6747#endif
6748 // compute an initial form ideal of <G> w.r.t. "next_vector"
6749 Gomega = MwalkInitialForm(G, next_weight);
6750#ifdef TIME_TEST
6751 tif = tif + clock()-to; //time for computing initial form ideal
6752#endif
6753
6754 //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
6755 if(lengthpoly(Gomega) > 0)
6756 {
6757 if(printout > 1)
6758 {
6759 PrintS("\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
6760 }
6761 // low-dimensional facet of the cone
6762 delete next_weight;
6763 if(target_M->length() == nV)
6764 {
6765 iv_M = MivMatrixOrder(curr_weight);
6766 }
6767 else
6768 {
6769 iv_M = MivMatrixOrderRefine(curr_weight,target_M);
6770 }
6771#ifdef TIME_TEST
6772 to = clock();
6773#endif
6774 next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, op_deg);
6775#ifdef TIME_TEST
6776 tnw = tnw + clock() - to;
6777#endif
6778 idDelete(&Gomega);
6779#ifdef TIME_TEST
6780 to = clock();
6781#endif
6782 Gomega = MwalkInitialForm(G, next_weight);
6783#ifdef TIME_TEST
6784 tif = tif + clock()-to; //time for computing initial form ideal
6785#endif
6786 delete iv_M;
6787 }
6788
6789#ifdef PRINT_VECTORS
6790 if(printout > 0)
6791 {
6792 MivString(curr_weight, target_weight, next_weight);
6793 }
6794#endif
6795
6796 if(Overflow_Error == TRUE)
6797 {
6798 ntwC = 0;
6799 //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6800 //idElements(G, "G");
6801 delete next_weight;
6802 goto FINISH_160302;
6803 }
6804 if(MivComp(next_weight, ivNull) == 1){
6805 newRing = currRing;
6806 delete next_weight;
6807 //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6808 break;
6809 }
6810 if(MivComp(next_weight, target_weight) == 1)
6811 endwalks = TRUE;
6812
6813 for(i=nV-1; i>=0; i--)
6814 (*curr_weight)[i] = (*next_weight)[i];
6815
6816 delete next_weight;
6817 }// end of while-loop
6818
6819 if(tp_deg != 1)
6820 {
6821 FINISH_160302:
6822 if(target_M->length() == nV)
6823 {
6824 if(MivSame(orig_target, exivlp) == 1)
6825 if (rParameter(currRing) != NULL)
6826 DefRingParlp();
6827 else
6828 VMrDefaultlp();
6829 else
6830 if (rParameter(currRing) != NULL)
6831 DefRingPar(orig_target);
6832 else
6833 rChangeCurrRing(VMrDefault(orig_target));
6834 }
6835 else
6836 {
6837 rChangeCurrRing(VMatrDefault(target_M));
6838 }
6839 TargetRing=currRing;
6840 F1 = idrMoveR(G, newRing,currRing);
6841
6842 // check whether the pertubed target vector stays in the correct cone
6843 if(ntwC != 0)
6844 {
6845 ntestw = test_w_in_ConeCC(F1, pert_target_vector);
6846 }
6847 if(ntestw != 1 || ntwC == 0)
6848 {
6849 if(ntestw != 1 && printout > 2)
6850 {
6851#ifdef PRINT_VECTORS
6852 ivString(pert_target_vector, "tau");
6853#endif
6854 PrintS("\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
6855 Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6856 //idElements(F1, "G");
6857 }
6858 // LastGB is "better" than the kStd2 subroutine
6859#ifdef TIME_TEST
6860 to=clock();
6861#endif
6862 ideal eF1;
6863 if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1 || target_M->length() != nV)
6864 {
6865 if(printout > 2)
6866 {
6867 PrintS("\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
6868 }
6869 eF1 = MstdCC(F1);
6870 idDelete(&F1);
6871 }
6872 else
6873 {
6874 if(printout > 2)
6875 {
6876 PrintS("\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
6877 }
6878 rChangeCurrRing(newRing);
6879 ideal F2 = idrMoveR(F1, TargetRing,currRing);
6880 eF1 = LastGB(F2, curr_weight, tp_deg-1);
6881 F2=NULL;
6882 }
6883#ifdef TIME_TEST
6884 xtextra=clock()-to;
6885#endif
6886 ring exTargetRing = currRing;
6887
6888 rChangeCurrRing(XXRing);
6889 Eresult = idrMoveR(eF1, exTargetRing,currRing);
6890 }
6891 else
6892 {
6893 rChangeCurrRing(XXRing);
6894 Eresult = idrMoveR(F1, TargetRing,currRing);
6895 }
6896 }
6897 else
6898 {
6899 rChangeCurrRing(XXRing);
6900 Eresult = idrMoveR(G, newRing,currRing);
6901 }
6902 si_opt_1 = save1; //set original options, e. g. option(RedSB)
6903 delete ivNull;
6904 if(tp_deg != 1)
6905 delete target_weight;
6906
6907 if(op_deg != 1 )
6908 delete curr_weight;
6909
6910 delete exivlp;
6911 delete last_omega;
6912
6913#ifdef TIME_TEST
6914 TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6915 tnw+xtnw);
6916
6917 //Print("\n// pSetm_Error = (%d)", ErrorCheck());
6918 //Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
6919#endif
6920
6921 if(printout > 0)
6922 {
6923 Print("\n//** Mprwalk: Perturbation Walk took %d steps.\n", nstep);
6924 }
6925 return(Eresult);
6926}
char * rString(ring r)
Definition ring.cc:678
void F2(int a2, int &r2)
F2.
static int lengthpoly(ideal G)
Definition walk.cc:3441
static ideal middleOfCone(ideal G, ideal Gomega)
Definition walk.cc:3080
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
Definition walk.cc:4517
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
Definition walk.cc:984
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition walk.cc:3146
static void idString(ideal L, const char *st)
Definition walk.cc:425

◆ Mpwalk()

ideal Mpwalk ( ideal Go,
int op_deg,
int tp_deg,
intvec * curr_weight,
intvec * target_weight,
int nP,
int reduction,
int printout )

Definition at line 5948 of file walk.cc.

5950{
5951 BITSET save1 = si_opt_1; // save current options
5952 if(reduction == 0)
5953 {
5954 si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5955 si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5956 }
5957 Set_Error(FALSE );
5959 //Print("// pSetm_Error = (%d)", ErrorCheck());
5960#ifdef TIME_TEST
5961 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5962 xtextra=0;
5963 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5964 tinput = clock();
5965
5966 clock_t tim;
5967#endif
5968 nstep = 0;
5969 int i, ntwC=1, ntestw=1, nV = currRing->N;
5970
5971 //check that perturbation degree is valid
5972 if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
5973 {
5974 WerrorS("Invalid perturbation degree.\n");
5975 return NULL;
5976 }
5977
5978 BOOLEAN endwalks = FALSE;
5979 ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5980 ring newRing, oldRing, TargetRing;
5981 intvec* iv_M_dp;
5982 intvec* iv_M_lp;
5983 intvec* exivlp = Mivlp(nV);
5984 intvec* orig_target = target_weight;
5985 intvec* pert_target_vector = target_weight;
5986 intvec* ivNull = new intvec(nV);
5987 intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
5988#ifndef BUCHBERGER_ALG
5989 intvec* hilb_func;
5990#endif
5991 intvec* next_weight;
5992
5993 // to avoid (1,0,...,0) as the target vector
5994 intvec* last_omega = new intvec(nV);
5995 for(i=nV-1; i>0; i--)
5996 (*last_omega)[i] = 1;
5997 (*last_omega)[0] = 10000;
5998
5999 ring XXRing = currRing;
6000#ifdef TIME_TEST
6001 to = clock();
6002#endif
6003 // perturbs the original vector
6004 if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
6005 {
6006 G = MstdCC(Go);
6007#ifdef TIME_TEST
6008 tostd = clock()-to;
6009#endif
6010 if(op_deg != 1){
6011 iv_M_dp = MivMatrixOrderdp(nV);
6012 //ivString(iv_M_dp, "iv_M_dp");
6013 curr_weight = MPertVectors(G, iv_M_dp, op_deg);
6014 }
6015 }
6016 else
6017 {
6018 //define ring order := (a(curr_weight),lp);
6019/*
6020 if (rParameter(currRing) != NULL)
6021 DefRingPar(curr_weight);
6022 else
6023 rChangeCurrRing(VMrDefault(curr_weight));
6024*/
6025 rChangeCurrRing(VMrRefine(target_weight,curr_weight));
6026
6027 G = idrMoveR(Go, XXRing,currRing);
6028 G = MstdCC(G);
6029#ifdef TIME_TEST
6030 tostd = clock()-to;
6031#endif
6032 if(op_deg != 1){
6033 iv_M_dp = MivMatrixOrder(curr_weight);
6034 curr_weight = MPertVectors(G, iv_M_dp, op_deg);
6035 }
6036 }
6037 delete iv_dp;
6038 if(op_deg != 1) delete iv_M_dp;
6039
6040 ring HelpRing = currRing;
6041
6042 // perturbs the target weight vector
6043 if(tp_deg > 1 && tp_deg <= nV)
6044 {
6045/*
6046 if (rParameter(currRing) != NULL)
6047 DefRingPar(target_weight);
6048 else
6049 rChangeCurrRing(VMrDefault(target_weight));
6050*/
6051 rChangeCurrRing(VMrRefine(target_weight,curr_weight));
6052
6053 TargetRing = currRing;
6054 ssG = idrMoveR(G,HelpRing,currRing);
6055 if(MivSame(target_weight, exivlp) == 1)
6056 {
6057 iv_M_lp = MivMatrixOrderlp(nV);
6058 target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
6059 }
6060 else
6061 {
6062 iv_M_lp = MivMatrixOrder(target_weight);
6063 target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
6064 }
6065 delete iv_M_lp;
6066 pert_target_vector = target_weight;
6067 rChangeCurrRing(HelpRing);
6068 G = idrMoveR(ssG, TargetRing,currRing);
6069 }
6070 if(printout > 0)
6071 {
6072 Print("\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6073#ifdef PRINT_VECTORS
6074 ivString(curr_weight, "//** Mpwalk: new current weight");
6075 ivString(target_weight, "//** Mpwalk: new target weight");
6076#endif
6077 }
6078 while(1)
6079 {
6080 nstep ++;
6081#ifdef TIME_TEST
6082 to = clock();
6083#endif
6084 // compute an initial form ideal of <G> w.r.t. the weight vector
6085 // "curr_weight"
6086 Gomega = MwalkInitialForm(G, curr_weight);
6087#ifdef TIME_TEST
6088 tif = tif + clock()-to;
6089#endif
6090#ifdef CHECK_IDEAL_MWALK
6091 if(printout > 1)
6092 {
6093 idString(Gomega,"//** Mpwalk: Gomega");
6094 }
6095#endif
6096 if(reduction == 0 && nstep > 1)
6097 {
6098 FF = middleOfCone(G,Gomega);
6099 if(FF != NULL)
6100 {
6101 idDelete(&G);
6102 G = idCopy(FF);
6103 idDelete(&FF);
6104 goto NEXT_VECTOR;
6105 }
6106 }
6107
6108#ifdef ENDWALKS
6109 if(endwalks == TRUE)
6110 {
6111 if(printout > 0)
6112 {
6113 Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6114 }
6115 //idElements(G, "G");
6116 //headidString(G, "G");
6117 }
6118#endif
6119
6120#ifndef BUCHBERGER_ALG
6121 if(isNolVector(curr_weight) == 0)
6122 hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
6123 else
6124 hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
6125#endif // BUCHBERGER_ALG
6126
6127 oldRing = currRing;
6128
6129 // define a new ring with ordering "(a(curr_weight),lp)
6130/*
6131 if (rParameter(currRing) != NULL)
6132 DefRingPar(curr_weight);
6133 else
6134 rChangeCurrRing(VMrDefault(curr_weight));
6135*/
6136 rChangeCurrRing(VMrRefine(target_weight,curr_weight));
6137
6138 newRing = currRing;
6139 Gomega1 = idrMoveR(Gomega, oldRing,currRing);
6140
6141#ifdef ENDWALKS
6142 if(endwalks==TRUE)
6143 {
6144 if(printout > 0)
6145 {
6146 Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6147 //idElements(Gomega1, "Gw");
6148 //headidString(Gomega1, "headGw");
6149 PrintS("\n// compute a rGB of Gw:\n");
6150 }
6151#ifndef BUCHBERGER_ALG
6152 ivString(hilb_func, "w");
6153#endif
6154 }
6155#endif
6156#ifdef TIME_TEST
6157 tim = clock();
6158 to = clock();
6159#endif
6160 // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
6161#ifdef BUCHBERGER_ALG
6162 M = MstdhomCC(Gomega1);
6163#else
6164 M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
6165 delete hilb_func;
6166#endif
6167
6168 if(endwalks == TRUE)
6169 {
6170#ifdef TIME_TEST
6171 xtstd = xtstd+clock()-to;
6172#endif
6173#ifdef ENDWALKS
6174#ifdef TIME_TEST
6175 if(printout > 1)
6176 {
6177 Print("\n// time for the last std(Gw) = %.2f sec\n",
6178 ((double) clock())/1000000 -((double)tim) /1000000);
6179 }
6180#endif
6181#endif
6182 }
6183 else
6184 {
6185#ifdef TIME_TEST
6186 tstd=tstd+clock()-to;
6187#endif
6188 }
6189#ifdef CHECK_IDEAL_MWALK
6190 if(printout > 2)
6191 {
6192 idString(M,"//** Mpwalk: M");
6193 }
6194#endif
6195 // change the ring to oldRing
6196 rChangeCurrRing(oldRing);
6197 M1 = idrMoveR(M, newRing,currRing);
6198 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
6199#ifdef TIME_TEST
6200 to=clock();
6201#endif
6202 /* compute a representation of the generators of submod (M)
6203 with respect to those of mod (Gomega).
6204 Gomega is a reduced Groebner basis w.r.t. the current ring */
6205 F = MLifttwoIdeal(Gomega2, M1, G);
6206#ifdef TIME_TEST
6207 if(endwalks == FALSE)
6208 tlift = tlift+clock()-to;
6209 else
6210 xtlift=clock()-to;
6211#endif
6212#ifdef CHECK_IDEAL_MWALK
6213 if(printout > 2)
6214 {
6215 idString(F,"//** Mpwalk: F");
6216 }
6217#endif
6218
6219 idDelete(&M1);
6220 idDelete(&Gomega2);
6221 idDelete(&G);
6222
6223 // change the ring to newRing
6224 rChangeCurrRing(newRing);
6225 if(reduction == 0)
6226 {
6227 G = idrMoveR(F,oldRing,currRing);
6228 }
6229 else
6230 {
6231 F1 = idrMoveR(F, oldRing,currRing);
6232 if(printout > 2)
6233 {
6234 PrintS("\n //** Mpwalk: reduce the Groebner basis.\n");
6235 }
6236#ifdef TIME_TEST
6237 to=clock();
6238#endif
6239 G = kInterRedCC(F1, NULL);
6240#ifdef TIME_TEST
6241 if(endwalks == FALSE)
6242 tred = tred+clock()-to;
6243 else
6244 xtred=clock()-to;
6245#endif
6246 idDelete(&F1);
6247 }
6248 if(endwalks == TRUE)
6249 break;
6250
6251 NEXT_VECTOR:
6252#ifdef TIME_TEST
6253 to=clock();
6254#endif
6255 // compute a next weight vector
6256 next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
6257#ifdef TIME_TEST
6258 tnw=tnw+clock()-to;
6259#endif
6260#ifdef PRINT_VECTORS
6261 if(printout > 0)
6262 {
6263 MivString(curr_weight, target_weight, next_weight);
6264 }
6265#endif
6266
6267 if(Overflow_Error == TRUE)
6268 {
6269 ntwC = 0;
6270 //ntestomega = 1;
6271 //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6272 //idElements(G, "G");
6273 delete next_weight;
6274 goto FINISH_160302;
6275 }
6276 if(MivComp(next_weight, ivNull) == 1){
6277 newRing = currRing;
6278 delete next_weight;
6279 //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6280 break;
6281 }
6282 if(MivComp(next_weight, target_weight) == 1)
6283 endwalks = TRUE;
6284
6285 for(i=nV-1; i>=0; i--)
6286 (*curr_weight)[i] = (*next_weight)[i];
6287
6288 delete next_weight;
6289 }//end of while-loop
6290
6291 if(tp_deg != 1)
6292 {
6293 FINISH_160302:
6294 if(MivSame(orig_target, exivlp) == 1) {
6295 /* if (rParameter(currRing) != NULL)
6296 DefRingParlp();
6297 else
6298 VMrDefaultlp();
6299 else
6300 if (rParameter(currRing) != NULL)
6301 DefRingPar(orig_target);
6302 else*/
6303 rChangeCurrRing(VMrDefault(orig_target));
6304 }
6305 TargetRing=currRing;
6306 F1 = idrMoveR(G, newRing,currRing);
6307/*
6308#ifdef CHECK_IDEAL_MWALK
6309 headidString(G, "G");
6310#endif
6311*/
6312
6313 // check whether the pertubed target vector stays in the correct cone
6314 if(ntwC != 0){
6315 ntestw = test_w_in_ConeCC(F1, pert_target_vector);
6316 }
6317
6318 if( ntestw != 1 || ntwC == 0)
6319 {
6320 if(ntestw != 1 && printout >2)
6321 {
6322 ivString(pert_target_vector, "tau");
6323 PrintS("\n// ** perturbed target vector doesn't stay in cone!!");
6324 Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6325 //idElements(F1, "G");
6326 }
6327 // LastGB is "better" than the kStd2 subroutine
6328#ifdef TIME_TEST
6329 to=clock();
6330#endif
6331 ideal eF1;
6332 if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1){
6333 // PrintS("\n// ** calls \"std\" to compute a GB");
6334 eF1 = MstdCC(F1);
6335 idDelete(&F1);
6336 }
6337 else {
6338 // PrintS("\n// ** calls \"LastGB\" to compute a GB");
6339 rChangeCurrRing(newRing);
6340 ideal F2 = idrMoveR(F1, TargetRing,currRing);
6341 eF1 = LastGB(F2, curr_weight, tp_deg-1);
6342 F2=NULL;
6343 }
6344#ifdef TIME_TEST
6345 xtextra=clock()-to;
6346#endif
6347 ring exTargetRing = currRing;
6348
6349 rChangeCurrRing(XXRing);
6350 Eresult = idrMoveR(eF1, exTargetRing,currRing);
6351 }
6352 else{
6353 rChangeCurrRing(XXRing);
6354 Eresult = idrMoveR(F1, TargetRing,currRing);
6355 }
6356 }
6357 else {
6358 rChangeCurrRing(XXRing);
6359 Eresult = idrMoveR(G, newRing,currRing);
6360 }
6361 si_opt_1 = save1; //set original options, e. g. option(RedSB)
6362 delete ivNull;
6363 if(tp_deg != 1)
6364 delete target_weight;
6365
6366 if(op_deg != 1 )
6367 delete curr_weight;
6368
6369 delete exivlp;
6370 delete last_omega;
6371
6372#ifdef TIME_TEST
6373 TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6374 tnw+xtnw);
6375
6376 //Print("\n// pSetm_Error = (%d)", ErrorCheck());
6377 //Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
6378#endif
6379 if(printout > 0)
6380 {
6381 Print("\n//** Mpwalk: Perturbation Walk took %d steps.\n", nstep);
6382 }
6383 return(Eresult);
6384}

◆ Mrwalk()

ideal Mrwalk ( ideal Go,
intvec * orig_M,
intvec * target_M,
int weight_rad,
int pert_deg,
int reduction,
int printout )

Definition at line 5604 of file walk.cc.

5606{
5607 BITSET save1 = si_opt_1; // save current options
5608 if(reduction == 0)
5609 {
5610 si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5611 si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5612 }
5613
5616#ifdef TIME_TEST
5617 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5618 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5619 tinput = clock();
5620 clock_t tim;
5621#endif
5622 nstep=0;
5623 int i,nwalk;//polylength;
5624 int nV = currRing->N;
5625
5626 //check that weight radius is valid
5627 if(weight_rad < 0)
5628 {
5629 WerrorS("Invalid radius.\n");
5630 return NULL;
5631 }
5632
5633 //check that perturbation degree is valid
5634 if(pert_deg > nV || pert_deg < 1)
5635 {
5636 WerrorS("Invalid perturbation degree.\n");
5637 return NULL;
5638 }
5639
5640 ideal Gomega, M, F,FF, Gomega1, Gomega2, M1;
5641 ring newRing;
5642 ring targetRing;
5643 ring baseRing = currRing;
5644 ring XXRing = currRing;
5645 intvec* iv_M;
5646 intvec* ivNull = new intvec(nV);
5647 intvec* curr_weight = new intvec(nV);
5648 intvec* target_weight = new intvec(nV);
5649 intvec* next_weight= new intvec(nV);
5650
5651 for(i=0; i<nV; i++)
5652 {
5653 (*curr_weight)[i] = (*orig_M)[i];
5654 (*target_weight)[i] = (*target_M)[i];
5655 }
5656
5657#ifndef BUCHBERGER_ALG
5658 intvec* hilb_func;
5659 // to avoid (1,0,...,0) as the target vector
5660 intvec* last_omega = new intvec(nV);
5661 for(i=nV-1; i>0; i--)
5662 {
5663 (*last_omega)[i] = 1;
5664 }
5665 (*last_omega)[0] = 10000;
5666#endif
5668
5669 if(target_M->length() == nV)
5670 {
5671 targetRing = VMrDefault(target_weight); // define the target ring
5672 }
5673 else
5674 {
5675 targetRing = VMatrDefault(target_M);
5676 }
5677 if(orig_M->length() == nV)
5678 {
5679 //newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5680 newRing=VMrRefine(target_weight, curr_weight);
5681 }
5682 else
5683 {
5684 newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5685 }
5686 rChangeCurrRing(newRing);
5687#ifdef TIME_TEST
5688 to = clock();
5689#endif
5690 ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5691#ifdef TIME_TEST
5692 tostd = clock()-to;
5693#endif
5694 baseRing = currRing;
5695 nwalk = 0;
5696
5697#ifdef TIME_TEST
5698 to = clock();
5699#endif
5700 Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5701#ifdef TIME_TEST
5702 tif = tif + clock()-to; //time for computing initial form ideal
5703#endif
5704
5705 while(1)
5706 {
5707 nwalk ++;
5708 nstep ++;
5709#ifdef CHECK_IDEAL_MWALK
5710 if(printout > 1)
5711 {
5712 idString(Gomega,"//** Mrwalk: Gomega");
5713 }
5714#endif
5715 if(reduction == 0)
5716 {
5717 FF = middleOfCone(G,Gomega);
5718 if(FF != NULL)
5719 {
5720 idDelete(&G);
5721 G = idCopy(FF);
5722 idDelete(&FF);
5723 goto NEXT_VECTOR;
5724 }
5725 }
5726#ifndef BUCHBERGER_ALG
5727 if(isNolVector(curr_weight) == 0)
5728 {
5729 hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5730 }
5731 else
5732 {
5733 hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5734 }
5735#endif
5736 if(nwalk == 1)
5737 {
5738 if(orig_M->length() == nV)
5739 {
5740 /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
5741 newRing=VMrRefine(target_weight, curr_weight);
5742 }
5743 else
5744 {
5745 newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5746 }
5747 }
5748 else
5749 {
5750 if(target_M->length() == nV)
5751 {
5752 /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
5753 newRing=VMrRefine(target_weight, curr_weight);
5754 }
5755 else
5756 {
5757 newRing = VMatrRefine(target_M,curr_weight);
5758 }
5759 }
5760 rChangeCurrRing(newRing);
5761 Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5762 idDelete(&Gomega);
5763 // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5764#ifdef TIME_TEST
5765 to = clock();
5766#endif
5767#ifndef BUCHBERGER_ALG
5768 M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5769 delete hilb_func;
5770#else
5771 M = kStd2(Gomega1,NULL,testHomog,NULL,(bigintmat*)NULL,0,0,NULL);
5772#endif
5773#ifdef TIME_TEST
5774 tstd = tstd + clock() - to;
5775#endif
5776 idSkipZeroes(M);
5777#ifdef CHECK_IDEAL_MWALK
5778 if(printout > 2)
5779 {
5780 idString(M, "//** Mrwalk: M");
5781 }
5782#endif
5783 //change the ring to baseRing
5784 rChangeCurrRing(baseRing);
5785 M1 = idrMoveR(M, newRing,currRing);
5786 idDelete(&M);
5787 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5788 idDelete(&Gomega1);
5789#ifdef TIME_TEST
5790 to = clock();
5791#endif
5792 // compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
5793 // where Gomega is a reduced Groebner basis w.r.t. the current ring
5794 F = MLifttwoIdeal(Gomega2, M1, G);
5795#ifdef TIME_TEST
5796 tlift = tlift + clock() - to;
5797#endif
5798#ifdef CHECK_IDEAL_MWALK
5799 if(printout > 2)
5800 {
5801 idString(F,"//** Mrwalk: F");
5802 }
5803#endif
5804 idDelete(&Gomega2);
5805 idDelete(&M1);
5806 rChangeCurrRing(newRing); // change the ring to newRing
5807 G = idrMoveR(F,baseRing,currRing);
5808 idDelete(&F);
5809 baseRing = currRing;
5810#ifdef TIME_TEST
5811 to = clock();
5812 tstd = tstd + clock() - to;
5813#endif
5814 idSkipZeroes(G);
5815#ifdef CHECK_IDEAL_MWALK
5816 if(printout > 2)
5817 {
5818 idString(G,"//** Mrwalk: G");
5819 }
5820#endif
5821
5822 rChangeCurrRing(targetRing);
5823 G = idrMoveR(G,newRing,currRing);
5824
5825 // test whether target cone is reached
5826 if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
5827 {
5828 baseRing = currRing;
5829 break;
5830 }
5831
5832 rChangeCurrRing(newRing);
5833 G = idrMoveR(G,targetRing,currRing);
5834 baseRing = currRing;
5835
5836 NEXT_VECTOR:
5837#ifdef TIME_TEST
5838 to = clock();
5839#endif
5840 next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5841#ifdef TIME_TEST
5842 tnw = tnw + clock() - to;
5843#endif
5844
5845#ifdef TIME_TEST
5846 to = clock();
5847#endif
5848 Gomega = MwalkInitialForm(G, next_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5849#ifdef TIME_TEST
5850 tif = tif + clock()-to; //time for computing initial form ideal
5851#endif
5852
5853 //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
5854 //polylength = lengthpoly(Gomega);
5855 if(lengthpoly(Gomega) > 0)
5856 {
5857 //there is a polynomial in Gomega with at least 3 monomials,
5858 //low-dimensional facet of the cone
5859 delete next_weight;
5860 if(target_M->length() == nV)
5861 {
5862 //iv_M = MivMatrixOrder(curr_weight);
5863 iv_M = MivMatrixOrderRefine(curr_weight,target_M);
5864 }
5865 else
5866 {
5867 iv_M = MivMatrixOrderRefine(curr_weight,target_M);
5868 }
5869#ifdef TIME_TEST
5870 to = clock();
5871#endif
5872 next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, pert_deg);
5873#ifdef TIME_TEST
5874 tnw = tnw + clock() - to;
5875#endif
5876 idDelete(&Gomega);
5877#ifdef TIME_TEST
5878 to = clock();
5879#endif
5880 Gomega = MwalkInitialForm(G, next_weight);
5881#ifdef TIME_TEST
5882 tif = tif + clock()-to; //time for computing initial form ideal
5883#endif
5884 delete iv_M;
5885 }
5886
5887 // test whether target weight vector is reached
5888 if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)
5889 {
5890 baseRing = currRing;
5891 delete next_weight;
5892 break;
5893 }
5894 if(reduction ==0)
5895 {
5896 if(MivComp(curr_weight,next_weight)==1)
5897 {
5898 break;
5899 }
5900 }
5901#ifdef PRINT_VECTORS
5902 if(printout > 0)
5903 {
5904 MivString(curr_weight, target_weight, next_weight);
5905 }
5906#endif
5907
5908 for(i=nV-1; i>=0; i--)
5909 {
5910 (*curr_weight)[i] = (*next_weight)[i];
5911 }
5912 delete next_weight;
5913 }
5914 baseRing = currRing;
5915 rChangeCurrRing(XXRing);
5916 ideal result = idrMoveR(G,baseRing,currRing);
5917 idDelete(&G);
5918 delete ivNull;
5919#ifndef BUCHBERGER_ALG
5920 delete last_omega;
5921#endif
5922 if(printout > 0)
5923 {
5924 Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
5925 }
5926#ifdef TIME_TEST
5927 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5928 //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5929 //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5930#endif
5931 si_opt_1 = save1; //set original options
5932 return(result);
5933}
Matrices of numbers.
Definition bigintmat.h:51
@ testHomog
Definition structs.h:34

◆ MSimpleIV()

intvec * MSimpleIV ( intvec * iv)

◆ Mwalk()

ideal Mwalk ( ideal Go,
intvec * orig_M,
intvec * target_M,
ring baseRing,
int reduction,
int printout )

Definition at line 5303 of file walk.cc.

5305{
5306 // save current options
5307 BITSET save1 = si_opt_1;
5308 if(reduction == 0)
5309 {
5310 si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5311 si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5312 }
5315 //BOOLEAN endwalks = FALSE;
5316#ifdef TIME_TEST
5317 clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5318 xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5319 tinput = clock();
5320 clock_t tim;
5321#endif
5322 nstep=0;
5323 int i,nwalk;
5324 int nV = baseRing->N;
5325
5326 ideal Gomega, M, F, FF, Gomega1, Gomega2, M1;
5327 ring newRing;
5328 ring XXRing = baseRing;
5329 ring targetRing;
5330 intvec* ivNull = new intvec(nV);
5331 intvec* curr_weight = new intvec(nV);
5332 intvec* target_weight = new intvec(nV);
5333 intvec* exivlp = Mivlp(nV);
5334/*
5335 intvec* tmp_weight = new intvec(nV);
5336 for(i=0; i<nV; i++)
5337 {
5338 (*tmp_weight)[i] = (*orig_M)[i];
5339 }
5340*/
5341 for(i=0; i<nV; i++)
5342 {
5343 (*curr_weight)[i] = (*orig_M)[i];
5344 (*target_weight)[i] = (*target_M)[i];
5345 }
5346#ifndef BUCHBERGER_ALG
5347 intvec* hilb_func;
5348 // to avoid (1,0,...,0) as the target vector
5349 intvec* last_omega = new intvec(nV);
5350 for(i=nV-1; i>0; i--)
5351 {
5352 (*last_omega)[i] = 1;
5353 }
5354 (*last_omega)[0] = 10000;
5355#endif
5357#ifdef CHECK_IDEAL_MWALK
5358 if(printout > 2)
5359 {
5360 idString(Go,"//** Mwalk: Go");
5361 }
5362#endif
5363
5364 if(target_M->length() == nV)
5365 {
5366 // define the target ring
5367 targetRing = VMrDefault(target_weight);
5368 }
5369 else
5370 {
5371 targetRing = VMatrDefault(target_M);
5372 }
5373 if(orig_M->length() == nV)
5374 {
5375 // define a new ring with ordering "(a(curr_weight),lp)
5376 //newRing = VMrDefault(curr_weight);
5377 newRing=VMrRefine(target_weight, curr_weight);
5378 }
5379 else
5380 {
5381 newRing = VMatrRefine(target_M,curr_weight); //newRing = VMatrDefault(orig_M);
5382 }
5383 rChangeCurrRing(newRing);
5384 if(printout > 2)
5385 {
5386 Print("\n//** Mrwalk: Current ring r = %s;\n", rString(currRing));
5387 }
5388#ifdef TIME_TEST
5389 to = clock();
5390#endif
5391 ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5392#ifdef TIME_TEST
5393 tostd = clock()-to;
5394#endif
5395
5396 baseRing = currRing;
5397 nwalk = 0;
5398
5399 while(1)
5400 {
5401 nwalk ++;
5402 nstep ++;
5403 //compute an initial form ideal of <G> w.r.t. "curr_vector"
5404#ifdef TIME_TEST
5405 to = clock();
5406#endif
5407 Gomega = MwalkInitialForm(G, curr_weight);
5408#ifdef TIME_TEST
5409 tif = tif + clock()-to;
5410#endif
5411
5412#ifdef CHECK_IDEAL_MWALK
5413 if(printout > 1)
5414 {
5415 idString(Gomega,"//** Mwalk: Gomega");
5416 }
5417#endif
5418
5419 if(reduction == 0)
5420 {
5421 FF = middleOfCone(G,Gomega);
5422 if(FF != NULL)
5423 {
5424 PrintS("middle of Cone");
5425 idDelete(&G);
5426 G = idCopy(FF);
5427 idDelete(&FF);
5428 goto NEXT_VECTOR;
5429 }
5430 }
5431
5432#ifndef BUCHBERGER_ALG
5433 if(isNolVector(curr_weight) == 0)
5434 {
5435 hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5436 }
5437 else
5438 {
5439 hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5440 }
5441#endif
5442
5443 if(nwalk == 1)
5444 {
5445 if(orig_M->length() == nV)
5446 {
5447 // define a new ring with ordering "(a(curr_weight),lp)
5448 //newRing = VMrDefault(curr_weight);
5449 newRing=VMrRefine(target_weight, curr_weight);
5450 }
5451 else
5452 {
5453 newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5454 }
5455 }
5456 else
5457 {
5458 if(target_M->length() == nV)
5459 {
5460 //define a new ring with ordering "(a(curr_weight),lp)"
5461 //newRing = VMrDefault(curr_weight);
5462 newRing=VMrRefine(target_weight, curr_weight);
5463 }
5464 else
5465 {
5466 //define a new ring with matrix ordering
5467 newRing = VMatrRefine(target_M,curr_weight);
5468 }
5469 }
5470 rChangeCurrRing(newRing);
5471 if(printout > 2)
5472 {
5473 Print("\n// Current ring r = %s;\n", rString(currRing));
5474 }
5475 Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5476 idDelete(&Gomega);
5477 // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5478#ifdef TIME_TEST
5479 to = clock();
5480#endif
5481#ifndef BUCHBERGER_ALG
5482 M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5483 delete hilb_func;
5484#else
5485 M = kStd2(Gomega1,NULL,testHomog,NULL,(bigintmat*)NULL,0,0,NULL);
5486#endif
5487#ifdef TIME_TEST
5488 tstd = tstd + clock() - to;
5489#endif
5490 idSkipZeroes(M);
5491#ifdef CHECK_IDEAL_MWALK
5492 if(printout > 2)
5493 {
5494 idString(M, "//** Mwalk: M");
5495 }
5496#endif
5497 //change the ring to baseRing
5498 rChangeCurrRing(baseRing);
5499 M1 = idrMoveR(M, newRing,currRing);
5500 idDelete(&M);
5501 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5502 idDelete(&Gomega1);
5503#ifdef TIME_TEST
5504 to = clock();
5505#endif
5506 // compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
5507 // where Gomega is a reduced Groebner basis w.r.t. the current ring
5508 F = MLifttwoIdeal(Gomega2, M1, G);
5509#ifdef TIME_TEST
5510 tlift = tlift + clock() - to;
5511#endif
5512#ifdef CHECK_IDEAL_MWALK
5513 if(printout > 2)
5514 {
5515 idString(F, "//** Mwalk: F");
5516 }
5517#endif
5518 idDelete(&Gomega2);
5519 idDelete(&M1);
5520
5521 rChangeCurrRing(newRing); // change the ring to newRing
5522 G = idrMoveR(F,baseRing,currRing);
5523 idDelete(&F);
5524 idSkipZeroes(G);
5525
5526#ifdef CHECK_IDEAL_MWALK
5527 if(printout > 2)
5528 {
5529 idString(G, "//** Mwalk: G");
5530 }
5531#endif
5532
5533 rChangeCurrRing(targetRing);
5534 G = idrMoveR(G,newRing,currRing);
5535 // test whether target cone is reached
5536 if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
5537 {
5538 baseRing = currRing;
5539 break;
5540 //endwalks = TRUE;
5541 }
5542
5543 rChangeCurrRing(newRing);
5544 G = idrMoveR(G,targetRing,currRing);
5545 baseRing = currRing;
5546
5547 NEXT_VECTOR:
5548#ifdef TIME_TEST
5549 to = clock();
5550#endif
5551 intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5552#ifdef TIME_TEST
5553 tnw = tnw + clock() - to;
5554#endif
5555#ifdef PRINT_VECTORS
5556 if(printout > 0)
5557 {
5558 MivString(curr_weight, target_weight, next_weight);
5559 }
5560#endif
5561 if(reduction ==0)
5562 {
5563 if(MivComp(curr_weight,next_weight)==1)
5564 {
5565 break;
5566 }
5567 }
5568 if(MivComp(target_weight,curr_weight) == 1)
5569 {
5570 break;
5571 }
5572
5573 for(i=nV-1; i>=0; i--)
5574 {
5575 //(*tmp_weight)[i] = (*curr_weight)[i];
5576 (*curr_weight)[i] = (*next_weight)[i];
5577 }
5578 delete next_weight;
5579 }
5580 rChangeCurrRing(XXRing);
5581 ideal result = idrMoveR(G,baseRing,currRing);
5582 idDelete(&Go);
5583 idDelete(&G);
5584 //delete tmp_weight;
5585 delete ivNull;
5586 delete exivlp;
5587#ifndef BUCHBERGER_ALG
5588 delete last_omega;
5589#endif
5590#ifdef TIME_TEST
5591 TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5592 //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5593 //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5594#endif
5595 if(printout > 0)
5596 {
5597 Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
5598 }
5599 si_opt_1 = save1; //set original options
5600 return(result);
5601}

◆ MwalkInitialForm()

ideal MwalkInitialForm ( ideal G,
intvec * curr_weight )

Definition at line 762 of file walk.cc.

763{
764 BOOLEAN nError = Overflow_Error;
766
767 int i, nG = IDELEMS(G);
768 ideal Gomega = idInit(nG, 1);
769
770 for(i=nG-1; i>=0; i--)
771 {
772 Gomega->m[i] = MpolyInitialForm(G->m[i], ivw);
773 }
774 if(Overflow_Error == FALSE)
775 {
776 Overflow_Error = nError;
777 }
778 return Gomega;
779}
ideal idInit(int idsize, int rank)
initialise an ideal / module
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition walk.cc:723

◆ MwalkNextWeight()

intvec * MwalkNextWeight ( intvec * curr_weight,
intvec * target_weight,
ideal G )

◆ TranMImprovwalk()

ideal TranMImprovwalk ( ideal Go,
intvec * curr_weight,
intvec * target_weight,
int nP )

Definition at line 8397 of file walk.cc.

8398{
8399#ifdef TIME_TEST
8400 clock_t mtim = clock();
8401#endif
8402 Set_Error(FALSE );
8404 //Print("// pSetm_Error = (%d)", ErrorCheck());
8405 //Print("\n// ring ro = %s;", rString(currRing));
8406
8407#ifdef TIME_TEST
8408 clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8409 clock_t tinput = clock();
8410#endif
8411 int nsteppert=0, i, nV = currRing->N, nwalk=0, npert_tmp=0;
8412 int *npert=(int*)omAlloc(2*nV*sizeof(int));
8413 ideal Gomega, M,F, G1, Gomega1, Gomega2, M1, F1;
8414 //ring endRing;
8415 ring newRing, oldRing, lpRing;
8416 intvec* next_weight;
8417 intvec* ivNull = new intvec(nV); //define (0,...,0)
8418 intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
8419 intvec* iv_lp = Mivlp(nV); //define (1,0,...,0)
8420 ideal H0;
8421 //ideal H1;
8422 ideal H2, Glp;
8423 int nGB, endwalks = 0, nwalkpert=0;
8424 intvec* Mlp = MivMatrixOrderlp(nV);
8425 intvec* vector_tmp = new intvec(nV);
8426#ifndef BUCHBERGER_ALG
8427 intvec* hilb_func;
8428#endif
8429 // to avoid (1,0,...,0) as the target vector
8430 intvec* last_omega = new intvec(nV);
8431 for(i=nV-1; i>0; i--)
8432 (*last_omega)[i] = 1;
8433 (*last_omega)[0] = 10000;
8434
8435 // intvec* extra_curr_weight = new intvec(nV);
8436 intvec* target_weight = new intvec(nV);
8437 for(i=nV-1; i>=0; i--)
8438 (*target_weight)[i] = (*target_tmp)[i];
8439
8440 ring XXRing = currRing;
8441 newRing = currRing;
8442
8443#ifdef TIME_TEST
8444 to=clock();
8445#endif
8446 // compute a red. GB w.r.t. the help ring
8447 if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) = "dp"
8448 G = MstdCC(G);
8449 else
8450 {
8451 //rOrdStr(currRing) = (a(.c_w..),lp,C)
8452 if (rParameter(currRing) != NULL)
8453 DefRingPar(curr_weight);
8454 else
8455 rChangeCurrRing(VMrDefault(curr_weight));
8456 G = idrMoveR(G, XXRing,currRing);
8457 G = MstdCC(G);
8458 }
8459#ifdef TIME_TEST
8460 tostd=clock()-to;
8461#endif
8462
8463#ifdef REPRESENTATION_OF_SIGMA
8464 ideal Gw = MwalkInitialForm(G, curr_weight);
8465
8466 if(islengthpoly2(Gw)==1)
8467 {
8468 intvec* MDp;
8469 if(MivComp(curr_weight, iv_dp) == 1)
8470 MDp = MatrixOrderdp(nV); //MivWeightOrderlp(iv_dp);
8471 else
8472 MDp = MivWeightOrderlp(curr_weight);
8473
8474 curr_weight = RepresentationMatrix_Dp(G, MDp);
8475
8476 delete MDp;
8477
8478 ring exring = currRing;
8479
8480 if (rParameter(currRing) != NULL)
8481 DefRingPar(curr_weight);
8482 else
8483 rChangeCurrRing(VMrDefault(curr_weight));
8484#ifdef TIME_TEST
8485 to=clock();
8486#endif
8487 Gw = idrMoveR(G, exring,currRing);
8488 G = MstdCC(Gw);
8489 Gw = NULL;
8490#ifdef TIME_TEST
8491 tostd=tostd+clock()-to;
8492#endif
8493 //ivString(curr_weight,"rep. sigma");
8494 goto COMPUTE_NEW_VECTOR;
8495 }
8496
8497 idDelete(&Gw);
8498 delete iv_dp;
8499#endif
8500
8501
8502 while(1)
8503 {
8504#ifdef TIME_TEST
8505 to=clock();
8506#endif
8507 /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
8508 Gomega = MwalkInitialForm(G, curr_weight);
8509#ifdef TIME_TEST
8510 tif=tif+clock()-to;
8511#endif
8512
8513#ifndef BUCHBERGER_ALG
8514 if(isNolVector(curr_weight) == 0)
8515 hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
8516 else
8517 hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
8518#endif // BUCHBERGER_ALG
8519
8520 oldRing = currRing;
8521
8522 /* define a new ring that its ordering is "(a(curr_weight),lp) */
8523 if (rParameter(currRing) != NULL)
8524 DefRingPar(curr_weight);
8525 else
8526 rChangeCurrRing(VMrDefault(curr_weight));
8527
8528 newRing = currRing;
8529 Gomega1 = idrMoveR(Gomega, oldRing,currRing);
8530
8531#ifdef TIME_TEST
8532 to=clock();
8533#endif
8534 /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
8535#ifdef BUCHBERGER_ALG
8536 M = MstdhomCC(Gomega1);
8537#else
8538 M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
8539 delete hilb_func;
8540#endif // BUCHBERGER_ALG
8541#ifdef TIME_TEST
8542 tstd=tstd+clock()-to;
8543#endif
8544
8545 /* change the ring to oldRing */
8546 rChangeCurrRing(oldRing);
8547 M1 = idrMoveR(M, newRing,currRing);
8548 Gomega2 = idrMoveR(Gomega1, newRing,currRing);
8549
8550#ifdef TIME_TEST
8551 to=clock();
8552#endif
8553 /* compute a representation of the generators of submod (M)
8554 with respect to those of mod (Gomega).
8555 Gomega is a reduced Groebner basis w.r.t. the current ring */
8556 F = MLifttwoIdeal(Gomega2, M1, G);
8557#ifdef TIME_TEST
8558 tlift=tlift+clock()-to;
8559#endif
8560
8561 idDelete(&M1);
8562 idDelete(&Gomega2);
8563 idDelete(&G);
8564
8565 /* change the ring to newRing */
8566 rChangeCurrRing(newRing);
8567 F1 = idrMoveR(F, oldRing,currRing);
8568
8569#ifdef TIME_TEST
8570 to=clock();
8571#endif
8572 /* reduce the Groebner basis <G> w.r.t. new ring */
8573 G = kInterRedCC(F1, NULL);
8574#ifdef TIME_TEST
8575 tred=tred+clock()-to;
8576#endif
8577 idDelete(&F1);
8578
8579
8580 COMPUTE_NEW_VECTOR:
8581 newRing = currRing;
8582 nwalk++;
8583 nwalkpert++;
8584#ifdef TIME_TEST
8585 to=clock();
8586#endif
8587 // compute a next weight vector
8588 next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
8589#ifdef TIME_TEST
8590 tnw=tnw+clock()-to;
8591#endif
8592#ifdef PRINT_VECTORS
8593 MivString(curr_weight, target_weight, next_weight);
8594#endif
8595
8596 /* check whether the computed intermediate weight vector is in
8597 the correct cone; sometimes it is very big e.g. s7, cyc7.
8598 If it is NOT in the correct cone, then compute directly
8599 a reduced Groebner basis with respect to the lexicographic ordering
8600 for the known Groebner basis that it is computed in the last step.
8601 */
8602 //if(test_w_in_ConeCC(G, next_weight) != 1)
8603 if(Overflow_Error == TRUE)
8604 {
8605 OMEGA_OVERFLOW_TRAN_NEW:
8606 //Print("\n// takes %d steps!", nwalk-1);
8607 //Print("\n//ring lastRing = %s;", rString(currRing));
8608#ifdef TEST_OVERFLOW
8609 goto BE_FINISH;
8610#endif
8611/*
8612#ifdef CHECK_IDEAL_MWALK
8613 idElements(G, "G");
8614 //headidString(G, "G");
8615#endif
8616*/
8617 if(MivSame(target_tmp, iv_lp) == 1)
8618 if (rParameter(currRing) != NULL)
8619 DefRingParlp();
8620 else
8621 VMrDefaultlp();
8622 else
8623 if (rParameter(currRing) != NULL)
8624 DefRingPar(target_tmp);
8625 else
8626 rChangeCurrRing(VMrDefault(target_tmp));
8627
8628 lpRing = currRing;
8629 G1 = idrMoveR(G, newRing,currRing);
8630
8631#ifdef TIME_TEST
8632 to=clock();
8633#endif
8634 /*apply kStd2 or LastGB to compute a lex. red. Groebner basis of <G>*/
8635 if(nP == 0 || MivSame(target_tmp, iv_lp) == 0){
8636 //Print("\n\n// calls \"std in ring r_%d = %s;", nwalk, rString(currRing));
8637 G = MstdCC(G1);//no result for qnt1
8638 }
8639 else {
8640 rChangeCurrRing(newRing);
8641 G1 = idrMoveR(G1, lpRing,currRing);
8642
8643 //Print("\n\n// calls \"LastGB\" (%d) to compute a GB", nV-1);
8644 G = LastGB(G1, curr_weight, nV-1); //no result for kats7
8645
8646 rChangeCurrRing(lpRing);
8647 G = idrMoveR(G, newRing,currRing);
8648 }
8649#ifdef TIME_TEST
8650 textra=clock()-to;
8651#endif
8652 npert[endwalks]=nwalk-npert_tmp;
8653 npert_tmp = nwalk;
8654 endwalks ++;
8655 break;
8656 }
8657
8658 /* check whether the computed Groebner basis is really a Groebner basis.
8659 If not, we perturb the target vector with the maximal "perturbation"
8660 degree.*/
8661 if(MivComp(next_weight, target_weight) == 1 ||
8662 MivComp(next_weight, curr_weight) == 1 )
8663 {
8664 //Print("\n//ring r_%d = %s;", nwalk, rString(currRing));
8665
8666
8667 //compute the number of perturbations and its step
8668 npert[endwalks]=nwalk-npert_tmp;
8669 npert_tmp = nwalk;
8670
8671 endwalks ++;
8672
8673 /*it is very important if the walk only uses one step, e.g. Fate, liu*/
8674 if(endwalks == 1 && MivComp(next_weight, curr_weight) == 1){
8675 rChangeCurrRing(XXRing);
8676 G = idrMoveR(G, newRing,currRing);
8677 goto FINISH;
8678 }
8679 H0 = id_Head(G,currRing);
8680
8681 if(MivSame(target_tmp, iv_lp) == 1)
8682 if (rParameter(currRing) != NULL)
8683 DefRingParlp();
8684 else
8685 VMrDefaultlp();
8686 else
8687 if (rParameter(currRing) != NULL)
8688 DefRingPar(target_tmp);
8689 else
8690 rChangeCurrRing(VMrDefault(target_tmp));
8691
8692 lpRing = currRing;
8693 Glp = idrMoveR(G, newRing,currRing);
8694 H2 = idrMoveR(H0, newRing,currRing);
8695
8696 /* Apply Lemma 2.2 in Collart et. al (1997) to check whether
8697 cone(k-1) is equal to cone(k) */
8698 nGB = 1;
8699 for(i=IDELEMS(Glp)-1; i>=0; i--)
8700 {
8701 poly t;
8702 if((t=pSub(pHead(Glp->m[i]), pCopy(H2->m[i]))) != NULL)
8703 {
8704 pDelete(&t);
8705 idDelete(&H2);//5.5.02
8706 nGB = 0; //i.e. Glp is no reduced Groebner basis
8707 break;
8708 }
8709 pDelete(&t);
8710 }
8711
8712 idDelete(&H2);//5.5.02
8713
8714 if(nGB == 1)
8715 {
8716 G = Glp;
8717 Glp = NULL;
8718 break;
8719 }
8720
8721 /* perturb the target weight vector, if the vector target_tmp
8722 stays in many cones */
8723 poly p;
8724 BOOLEAN plength3 = FALSE;
8725 for(i=IDELEMS(Glp)-1; i>=0; i--)
8726 {
8727 p = MpolyInitialForm(Glp->m[i], target_tmp);
8728 if(p->next != NULL &&
8729 p->next->next != NULL &&
8730 p->next->next->next != NULL)
8731 {
8733
8734 for(i=0; i<nV; i++)
8735 (*vector_tmp)[i] = (*target_weight)[i];
8736
8737 delete target_weight;
8738 target_weight = MPertVectors(Glp, Mlp, nV);
8739
8740 if(MivComp(vector_tmp, target_weight)==1)
8741 {
8742 //PrintS("\n// The old and new representaion vector are the same!!");
8743 G = Glp;
8744 newRing = currRing;
8745 goto OMEGA_OVERFLOW_TRAN_NEW;
8746 }
8747
8748 if(Overflow_Error == TRUE)
8749 {
8750 rChangeCurrRing(newRing);
8751 G = idrMoveR(Glp, lpRing,currRing);
8752 goto OMEGA_OVERFLOW_TRAN_NEW;
8753 }
8754
8755 plength3 = TRUE;
8756 pDelete(&p);
8757 break;
8758 }
8759 pDelete(&p);
8760 }
8761
8762 if(plength3 == FALSE)
8763 {
8764 rChangeCurrRing(newRing);
8765 G = idrMoveR(Glp, lpRing,currRing);
8766 goto TRAN_LIFTING;
8767 }
8768
8769
8770 nwalkpert = 1;
8771 nsteppert ++;
8772
8773 /*
8774 Print("\n// Subroutine needs (%d) steps.", nwalk);
8775 idElements(Glp, "last G in walk:");
8776 PrintS("\n// ****************************************");
8777 Print("\n// Perturb the original target vector (%d): ", nsteppert);
8778 ivString(target_weight, "new target");
8779 PrintS("\n// ****************************************\n");
8780 */
8781 rChangeCurrRing(newRing);
8782 G = idrMoveR(Glp, lpRing,currRing);
8783
8784 delete next_weight;
8785
8786 //Print("\n// ring rNEW = %s;", rString(currRing));
8787 goto COMPUTE_NEW_VECTOR;
8788 }
8789
8790 TRAN_LIFTING:
8791 for(i=nV-1; i>=0; i--)
8792 (*curr_weight)[i] = (*next_weight)[i];
8793
8794 delete next_weight;
8795 }//while
8796#ifdef TEST_OVERFLOW
8797 BE_FINISH:
8798#endif
8799 rChangeCurrRing(XXRing);
8800 G = idrMoveR(G, lpRing,currRing);
8801
8802 FINISH:
8803 delete ivNull;
8804 delete next_weight;
8805 delete iv_lp;
8806 omFree(npert);
8807/*
8808#ifdef TIME_TEST
8809 Print("\n// Computation took %d steps and %.2f sec",
8810 nwalk, ((double) (clock()-mtim)/1000000));
8811
8812 TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
8813
8814 // Print("\n// pSetm_Error = (%d)", ErrorCheck());
8815 Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8816#endif
8817*/
8818 return(G);
8819}
#define pDelete(p_ptr)
Definition polys.h:187
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
#define pSub(a, b)
Definition polys.h:288
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
static int islengthpoly2(ideal G)
Definition walk.cc:3478

◆ TranMPertVectorslp()

intvec * TranMPertVectorslp ( ideal G)