My Project
Loading...
Searching...
No Matches
Functions
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 914 of file walk.cc.

915{
916 assume(temp->length() == u->length() && u->length() == v->length());
917
918 if((MivSame(temp, u)) == 1)
919 {
920 return 0;
921 }
922 if((MivSame(temp, v)) == 1)
923 {
924 return 1;
925 }
926 return 2;
927}
int length() const
Definition: intvec.h:94
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:893

◆ MAltwalk1()

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

Definition at line 9671 of file walk.cc.

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

◆ MAltwalk2()

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

Definition at line 4280 of file walk.cc.

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

◆ Mfpertvector()

intvec * Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1512 of file walk.cc.

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

◆ Mfrwalk()

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

Definition at line 8212 of file walk.cc.

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

◆ Mfwalk()

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

Definition at line 8031 of file walk.cc.

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

◆ MidLift()

ideal MidLift ( ideal  Gomega,
ideal  M 
)

◆ Mivdp()

intvec * Mivdp ( int  nR)

Definition at line 1007 of file walk.cc.

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

◆ Mivlp()

intvec * Mivlp ( int  nR)

Definition at line 1022 of file walk.cc.

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

◆ MivMatrixOrder()

intvec * MivMatrixOrder ( intvec iv)

Definition at line 963 of file walk.cc.

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

◆ MivMatrixOrderdp()

intvec * MivMatrixOrderdp ( int  iv)

Definition at line 1417 of file walk.cc.

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

◆ MivMatrixOrderlp()

intvec * MivMatrixOrderlp ( int  nV)

Definition at line 1401 of file walk.cc.

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

◆ Mivperttarget()

intvec * Mivperttarget ( ideal  G,
int  ndeg 
)

◆ MivSame()

int MivSame ( intvec u,
intvec v 
)

Definition at line 893 of file walk.cc.

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

◆ MivUnit()

intvec * MivUnit ( int  nV)

Definition at line 1496 of file walk.cc.

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

◆ MivWeightOrderdp()

intvec * MivWeightOrderdp ( intvec ivstart)

Definition at line 1456 of file walk.cc.

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

◆ MivWeightOrderlp()

intvec * MivWeightOrderlp ( intvec ivstart)

Definition at line 1436 of file walk.cc.

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

◆ MkInterRedNextWeight()

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

Definition at line 2570 of file walk.cc.

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

◆ 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 1088 of file walk.cc.

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

◆ MPertVectorslp()

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

Definition at line 1299 of file walk.cc.

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

◆ 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 6388 of file walk.cc.

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

◆ 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 5947 of file walk.cc.

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

◆ Mrwalk()

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

Definition at line 5603 of file walk.cc.

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

◆ 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 5302 of file walk.cc.

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

◆ MwalkInitialForm()

ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 761 of file walk.cc.

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

◆ 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 8396 of file walk.cc.

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

◆ TranMPertVectorslp()

intvec * TranMPertVectorslp ( ideal  G)