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

924 {
925  assume(temp->length() == u->length() && u->length() == v->length());
926 
927  if((MivSame(temp, u)) == 1)
928  {
929  return 0;
930  }
931  if((MivSame(temp, v)) == 1)
932  {
933  return 1;
934  }
935  return 2;
936 }
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:902
#define assume(x)
Definition: mod2.h:394
int length() const
Definition: intvec.h:86

◆ MAltwalk1()

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

Definition at line 9680 of file walk.cc.

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

◆ MAltwalk2()

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

Definition at line 4289 of file walk.cc.

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

◆ Mfpertvector()

intvec* Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1521 of file walk.cc.

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

◆ Mfrwalk()

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

Definition at line 8221 of file walk.cc.

8223 {
8224  BITSET save1 = si_opt_1; // save current options
8225  //check that weight radius is valid
8226  if(weight_rad < 0)
8227  {
8228  WerrorS("Invalid radius.\n");
8229  return NULL;
8230  }
8231  if(reduction == 0)
8232  {
8233  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
8234  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
8235  }
8236  Set_Error(FALSE);
8238  //Print("// pSetm_Error = (%d)", ErrorCheck());
8239  //Print("\n// ring ro = %s;", rString(currRing));
8240 
8241  nnflow = 0;
8242  Xngleich = 0;
8243  Xcall = 0;
8244 #ifdef TIME_TEST
8245  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8246  xftinput = clock();
8247 #endif
8248  ring oldRing = currRing;
8249  int i, nV = currRing->N;
8250  XivNull = new intvec(nV);
8251  Xivinput = ivtarget;
8252  ngleich = 0;
8253 #ifdef TIME_TEST
8254  to=clock();
8255 #endif
8256  ideal I = MstdCC(G);
8257  G = NULL;
8258 #ifdef TIME_TEST
8259  xftostd=clock()-to;
8260 #endif
8261  Xsigma = ivstart;
8262 
8263  Xnlev=nV;
8264 
8265 #ifdef FIRST_STEP_FRACTAL
8266  ideal Gw = MwalkInitialForm(I, ivstart);
8267  for(i=IDELEMS(Gw)-1; i>=0; i--)
8268  {
8269  if((Gw->m[i]!=NULL) // len >=0
8270  && (Gw->m[i]->next!=NULL) // len >=1
8271  && (Gw->m[i]->next->next!=NULL)) // len >=2
8272  {
8273  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
8274  intvec* Mdp;
8275  if(ivstart->length() == nV)
8276  {
8277  if(MivSame(ivstart, iv_dp) != 1)
8278  Mdp = MivWeightOrderdp(ivstart);
8279  else
8280  Mdp = MivMatrixOrderdp(nV);
8281  }
8282  else
8283  {
8284  Mdp = ivstart;
8285  }
8286 
8287  Xsigma = Mfpertvector(I, Mdp);
8289 
8290  delete Mdp;
8291  delete iv_dp;
8292  break;
8293  }
8294  }
8295  idDelete(&Gw);
8296 #endif
8297 
8298  ideal I1;
8299  intvec* Mlp;
8300  Xivlp = Mivlp(nV);
8301 
8302  if(ivtarget->length() == nV)
8303  {
8304  if(MivComp(ivtarget, Xivlp) != 1)
8305  {
8306  if (rParameter(currRing) != NULL)
8307  DefRingPar(ivtarget);
8308  else
8309  rChangeCurrRing(VMrDefault(ivtarget));
8310 
8311  I1 = idrMoveR(I, oldRing,currRing);
8312  Mlp = MivWeightOrderlp(ivtarget);
8313  Xtau = Mfpertvector(I1, Mlp);
8314  }
8315  else
8316  {
8317  if (rParameter(currRing) != NULL)
8318  DefRingParlp();
8319  else
8320  VMrDefaultlp();
8321 
8322  I1 = idrMoveR(I, oldRing,currRing);
8323  Mlp = MivMatrixOrderlp(nV);
8324  Xtau = Mfpertvector(I1, Mlp);
8325  }
8326  }
8327  else
8328  {
8329  rChangeCurrRing(VMatrDefault(ivtarget));
8330  I1 = idrMoveR(I,oldRing,currRing);
8331  Mlp = ivtarget;
8332  Xtau = Mfpertvector(I1, Mlp);
8333  }
8334  delete Mlp;
8336 
8337  //ivString(Xsigma, "Xsigma");
8338  //ivString(Xtau, "Xtau");
8339 
8340  id_Delete(&I, oldRing);
8341  ring tRing = currRing;
8342  if(ivtarget->length() == nV)
8343  {
8344 /*
8345  if (rParameter(currRing) != NULL)
8346  DefRingPar(ivstart);
8347  else
8348  rChangeCurrRing(VMrDefault(ivstart));
8349 */
8350  rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8351  }
8352  else
8353  {
8354  //rChangeCurrRing(VMatrDefault(ivstart));
8355  rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8356  }
8357 
8358  I = idrMoveR(I1,tRing,currRing);
8359 #ifdef TIME_TEST
8360  to=clock();
8361 #endif
8362  ideal J = MstdCC(I);
8363  idDelete(&I);
8364 #ifdef TIME_TEST
8365  xftostd=xftostd+clock()-to;
8366 #endif
8367  ideal resF;
8368  ring helpRing = currRing;
8369 
8370  J = rec_r_fractal_call(J,1,ivtarget,weight_rad,reduction,printout);
8371  //idString(J,"//*** Mfrwalk: J");
8372  //Print("\n//** Mfrwalk hier (1)\n");
8373  rChangeCurrRing(oldRing);
8374  //Print("\n//** Mfrwalk hier (2)\n");
8375  resF = idrMoveR(J, helpRing,currRing);
8376  //Print("\n//** Mfrwalk hier (3)\n");
8377  //idSkipZeroes(resF);
8378  //Print("\n//** Mfrwalk hier (4)\n");
8379  si_opt_1 = save1; //set original options, e. g. option(RedSB)
8380  delete Xivlp;
8381  //delete Xsigma;
8382  delete Xtau;
8383  delete XivNull;
8384  //Print("\n//** Mfrwalk hier (5)\n");
8385 #ifdef TIME_TEST
8386  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8387  xtlift, xtred, xtnw);
8388 
8389 
8390  // Print("\n// pSetm_Error = (%d)", ErrorCheck());
8391  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8392  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8393 #endif
8394  //Print("\n//** Mfrwalk hier (6)\n");
8395  //idString(resF,"resF");
8396  //Print("\n//** Mfrwalk hier (7)\n");
8397  return(resF);
8398 }
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1521
intvec * Xivlp
Definition: walk.cc:4519
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1807
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
intvec * Xivinput
Definition: walk.cc:4518
int nnflow
Definition: walk.cc:6953
int ngleich
Definition: walk.cc:4514
int Xngleich
Definition: walk.cc:6955
#define FALSE
Definition: auxiliary.h:94
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1445
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *ivtarget, int weight_rad, int reduction, int printout)
Definition: walk.cc:7462
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2799
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
intvec * Xsigma
Definition: walk.cc:4515
int Xnlev
Definition: walk.cc:1520
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:902
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1465
void WerrorS(const char *s)
Definition: feFopen.cc:24
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:616
intvec * Xtau
Definition: walk.cc:4516
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2850
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:18
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2907
int Xcall
Definition: walk.cc:6954
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
Definition: intvec.h:14
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
void rChangeCurrRing(ring r)
Definition: polys.cc:12
static void DefRingParlp(void)
Definition: walk.cc:2997
static ideal MstdCC(ideal G)
Definition: walk.cc:941
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2948
int length() const
Definition: intvec.h:86
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1426
intvec * MivUnit(int nV)
Definition: walk.cc:1505
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:770
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2740
intvec * XivNull
Definition: walk.cc:6936
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1410
intvec * Mivlp(int nR)
Definition: walk.cc:1031
static ring VMrDefault(intvec *va)
Definition: walk.cc:2689

◆ Mfwalk()

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

Definition at line 8040 of file walk.cc.

8042 {
8043  BITSET save1 = si_opt_1; // save current options
8044  if(reduction == 0)
8045  {
8046  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
8047  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
8048  }
8049  Set_Error(FALSE);
8051  //Print("// pSetm_Error = (%d)", ErrorCheck());
8052  //Print("\n// ring ro = %s;", rString(currRing));
8053 
8054  nnflow = 0;
8055  Xngleich = 0;
8056  Xcall = 0;
8057 #ifdef TIME_TEST
8058  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8059  xftinput = clock();
8060 #endif
8061  ring oldRing = currRing;
8062  int i, nV = currRing->N;
8063  XivNull = new intvec(nV);
8064  Xivinput = ivtarget;
8065  ngleich = 0;
8066 #ifdef TIME_TEST
8067  to=clock();
8068 #endif
8069  ideal I = MstdCC(G);
8070  G = NULL;
8071 #ifdef TIME_TEST
8072  xftostd=clock()-to;
8073 #endif
8074  Xsigma = ivstart;
8075 
8076  Xnlev=nV;
8077 
8078 #ifdef FIRST_STEP_FRACTAL
8079  ideal Gw = MwalkInitialForm(I, ivstart);
8080  for(i=IDELEMS(Gw)-1; i>=0; i--)
8081  {
8082  if((Gw->m[i]!=NULL) // len >=0
8083  && (Gw->m[i]->next!=NULL) // len >=1
8084  && (Gw->m[i]->next->next!=NULL)) // len >=2
8085  {
8086  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
8087  intvec* Mdp;
8088  if(ivstart->length() == nV)
8089  {
8090  if(MivSame(ivstart, iv_dp) != 1)
8091  Mdp = MivWeightOrderdp(ivstart);
8092  else
8093  Mdp = MivMatrixOrderdp(nV);
8094  }
8095  else
8096  {
8097  Mdp = ivstart;
8098  }
8099 
8100  Xsigma = Mfpertvector(I, Mdp);
8102 
8103  delete Mdp;
8104  delete iv_dp;
8105  break;
8106  }
8107  }
8108  idDelete(&Gw);
8109 #endif
8110 
8111  ideal I1;
8112  intvec* Mlp;
8113  Xivlp = Mivlp(nV);
8114 
8115  if(ivtarget->length() == nV)
8116  {
8117  if(MivComp(ivtarget, Xivlp) != 1)
8118  {
8119  if (rParameter(currRing) != NULL)
8120  DefRingPar(ivtarget);
8121  else
8122  rChangeCurrRing(VMrDefault(ivtarget));
8123 
8124  I1 = idrMoveR(I, oldRing,currRing);
8125  Mlp = MivWeightOrderlp(ivtarget);
8126  Xtau = Mfpertvector(I1, Mlp);
8127  }
8128  else
8129  {
8130  if (rParameter(currRing) != NULL)
8131  DefRingParlp();
8132  else
8133  VMrDefaultlp();
8134 
8135  I1 = idrMoveR(I, oldRing,currRing);
8136  Mlp = MivMatrixOrderlp(nV);
8137  Xtau = Mfpertvector(I1, Mlp);
8138  }
8139  }
8140  else
8141  {
8142  rChangeCurrRing(VMatrDefault(ivtarget));
8143  I1 = idrMoveR(I,oldRing,currRing);
8144  Mlp = ivtarget;
8145  Xtau = Mfpertvector(I1, Mlp);
8146  }
8147  delete Mlp;
8149 
8150  //ivString(Xsigma, "Xsigma");
8151  //ivString(Xtau, "Xtau");
8152 
8153  id_Delete(&I, oldRing);
8154  ring tRing = currRing;
8155  if(ivtarget->length() == nV)
8156  {
8157 /*
8158  if (rParameter(currRing) != NULL)
8159  DefRingPar(ivstart);
8160  else
8161  rChangeCurrRing(VMrDefault(ivstart));
8162 */
8163  rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8164  }
8165  else
8166  {
8167  //rChangeCurrRing(VMatrDefault(ivstart));
8168  rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8169  }
8170 
8171  I = idrMoveR(I1,tRing,currRing);
8172 #ifdef TIME_TEST
8173  to=clock();
8174 #endif
8175  ideal J = MstdCC(I);
8176  idDelete(&I);
8177 #ifdef TIME_TEST
8178  xftostd=xftostd+clock()-to;
8179 #endif
8180  ideal resF;
8181  ring helpRing = currRing;
8182 
8183  J = rec_fractal_call(J,1,ivtarget,reduction,printout);
8184  //idString(J,"//** Mfwalk: J");
8185  rChangeCurrRing(oldRing);
8186  //Print("\n//Mfwalk: (2)\n");
8187  resF = idrMoveR(J, helpRing,currRing);
8188  //Print("\n//Mfwalk: (3)\n");
8189  idSkipZeroes(resF);
8190  //Print("\n//Mfwalk: (4)\n");
8191 
8192  si_opt_1 = save1; //set original options, e. g. option(RedSB)
8193  delete Xivlp;
8194  //delete Xsigma;
8195  delete Xtau;
8196  delete XivNull;
8197  //Print("\n//Mfwalk: (5)\n");
8198 #ifdef TIME_TEST
8199  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8200  xtlift, xtred, xtnw);
8201 
8202 
8203  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
8204  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8205  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8206 #endif
8207  //Print("\n//Mfwalk: (6)\n");
8208  //idString(resF,"//** Mfwalk: resF");
8209  return(idCopy(resF));
8210 }
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1521
intvec * Xivlp
Definition: walk.cc:4519
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1807
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
intvec * Xivinput
Definition: walk.cc:4518
int nnflow
Definition: walk.cc:6953
int ngleich
Definition: walk.cc:4514
int Xngleich
Definition: walk.cc:6955
#define FALSE
Definition: auxiliary.h:94
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1445
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2799
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
intvec * Xsigma
Definition: walk.cc:4515
int Xnlev
Definition: walk.cc:1520
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:902
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1465
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:616
intvec * Xtau
Definition: walk.cc:4516
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2850
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:18
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2907
int Xcall
Definition: walk.cc:6954
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
Definition: intvec.h:14
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
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:6960
ideal idCopy(ideal A)
Definition: ideals.h:60
void rChangeCurrRing(ring r)
Definition: polys.cc:12
static void DefRingParlp(void)
Definition: walk.cc:2997
static ideal MstdCC(ideal G)
Definition: walk.cc:941
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2948
int length() const
Definition: intvec.h:86
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1426
intvec * MivUnit(int nV)
Definition: walk.cc:1505
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:770
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2740
intvec * XivNull
Definition: walk.cc:6936
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1410
intvec * Mivlp(int nR)
Definition: walk.cc:1031
static ring VMrDefault(intvec *va)
Definition: walk.cc:2689

◆ MidLift()

ideal MidLift ( ideal  Gomega,
ideal  M 
)

◆ Mivdp()

intvec* Mivdp ( int  nR)

Definition at line 1016 of file walk.cc.

1017 {
1018  int i;
1019  intvec* ivm = new intvec(nR);
1020 
1021  for(i=nR-1; i>=0; i--)
1022  {
1023  (*ivm)[i] = 1;
1024  }
1025  return ivm;
1026 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123

◆ Mivlp()

intvec* Mivlp ( int  nR)

Definition at line 1031 of file walk.cc.

1032 {
1033  intvec* ivm = new intvec(nR);
1034  (*ivm)[0] = 1;
1035 
1036  return ivm;
1037 }
Definition: intvec.h:14

◆ MivMatrixOrder()

intvec* MivMatrixOrder ( intvec iv)

Definition at line 972 of file walk.cc.

973 {
974  int i, nR = iv->length();
975 
976  intvec* ivm = new intvec(nR*nR);
977 
978  for(i=0; i<nR; i++)
979  {
980  (*ivm)[i] = (*iv)[i];
981  }
982  for(i=1; i<nR; i++)
983  {
984  (*ivm)[i*nR+i-1] = 1;
985  }
986  return ivm;
987 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: intvec.h:86

◆ MivMatrixOrderdp()

intvec* MivMatrixOrderdp ( int  iv)

Definition at line 1426 of file walk.cc.

1427 {
1428  int i;
1429  intvec* ivM = new intvec(nV*nV);
1430 
1431  for(i=0; i<nV; i++)
1432  {
1433  (*ivM)[i] = 1;
1434  }
1435  for(i=1; i<nV; i++)
1436  {
1437  (*ivM)[(i+1)*nV - i] = -1;
1438  }
1439  return(ivM);
1440 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123

◆ MivMatrixOrderlp()

intvec* MivMatrixOrderlp ( int  nV)

Definition at line 1410 of file walk.cc.

1411 {
1412  int i;
1413  intvec* ivM = new intvec(nV*nV);
1414 
1415  for(i=0; i<nV; i++)
1416  {
1417  (*ivM)[i*nV + i] = 1;
1418  }
1419  return(ivM);
1420 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123

◆ Mivperttarget()

intvec* Mivperttarget ( ideal  G,
int  ndeg 
)

◆ MivSame()

int MivSame ( intvec u,
intvec v 
)

Definition at line 902 of file walk.cc.

903 {
904  assume(u->length() == v->length());
905 
906  int i, niv = u->length();
907 
908  for (i=0; i<niv; i++)
909  {
910  if ((*u)[i] != (*v)[i])
911  {
912  return 0;
913  }
914  }
915  return 1;
916 }
#define assume(x)
Definition: mod2.h:394
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: intvec.h:86

◆ MivUnit()

intvec* MivUnit ( int  nV)

Definition at line 1505 of file walk.cc.

1506 {
1507  int i;
1508  intvec* ivM = new intvec(nV);
1509  for(i=nV-1; i>=0; i--)
1510  {
1511  (*ivM)[i] = 1;
1512  }
1513  return(ivM);
1514 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123

◆ MivWeightOrderdp()

intvec* MivWeightOrderdp ( intvec ivstart)

Definition at line 1465 of file walk.cc.

1466 {
1467  int i;
1468  int nV = ivstart->length();
1469  intvec* ivM = new intvec(nV*nV);
1470 
1471  for(i=0; i<nV; i++)
1472  {
1473  (*ivM)[i] = (*ivstart)[i];
1474  }
1475  for(i=0; i<nV; i++)
1476  {
1477  (*ivM)[nV+i] = 1;
1478  }
1479  for(i=2; i<nV; i++)
1480  {
1481  (*ivM)[(i+1)*nV - i] = -1;
1482  }
1483  return(ivM);
1484 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: intvec.h:86

◆ MivWeightOrderlp()

intvec* MivWeightOrderlp ( intvec ivstart)

Definition at line 1445 of file walk.cc.

1446 {
1447  int i;
1448  int nV = ivstart->length();
1449  intvec* ivM = new intvec(nV*nV);
1450 
1451  for(i=0; i<nV; i++)
1452  {
1453  (*ivM)[i] = (*ivstart)[i];
1454  }
1455  for(i=1; i<nV; i++)
1456  {
1457  (*ivM)[i*nV + i-1] = 1;
1458  }
1459  return(ivM);
1460 }
Definition: intvec.h:14
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: intvec.h:86

◆ MkInterRedNextWeight()

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

Definition at line 2579 of file walk.cc.

2580 {
2581  intvec* tmp = new intvec(iva->length());
2582  intvec* result;
2583 
2584  if(G == NULL)
2585  {
2586  return tmp;
2587  }
2588  if(MivComp(iva, ivb) == 1)
2589  {
2590  return tmp;
2591  }
2592  result = MwalkNextWeightCC(iva, ivb, G);
2593 
2594  if(MivComp(result, iva) == 1)
2595  {
2596  delete result;
2597  return tmp;
2598  }
2599 
2600  delete tmp;
2601  return result;
2602 }
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1807
static TreeM * G
Definition: janet.cc:38
Definition: intvec.h:14
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2237
#define NULL
Definition: omList.c:10
int length() const
Definition: intvec.h:86
return result
Definition: facAbsBiFact.cc:76

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

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

◆ MPertVectorslp()

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

Definition at line 1308 of file walk.cc.

1309 {
1310  // ivtarget is a matrix order of the lex. order
1311  int nV = currRing->N;
1312  //assume(pdeg <= nV && pdeg >= 0);
1313 
1314  int i, j, nG = IDELEMS(G);
1315  intvec* pert_vector = new intvec(nV);
1316 
1317  //Checking that the perturbated degree is valid
1318  if(pdeg > nV || pdeg <= 0)
1319  {
1320  WerrorS("//** The perturbed degree is wrong!!");
1321  return pert_vector;
1322  }
1323  for(i=0; i<nV; i++)
1324  {
1325  (*pert_vector)[i]=(*ivtarget)[i];
1326  }
1327  if(pdeg == 1)
1328  {
1329  return pert_vector;
1330  }
1331  // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
1332  // where the Ai are the i-te rows of the matrix target_ord.
1333  int ntemp, maxAi, maxA=0;
1334  for(i=1; i<pdeg; i++)
1335  {
1336  maxAi = (*ivtarget)[i*nV];
1337  for(j=i*nV+1; j<(i+1)*nV; j++)
1338  {
1339  ntemp = (*ivtarget)[j];
1340  if(ntemp > maxAi)
1341  {
1342  maxAi = ntemp;
1343  }
1344  }
1345  maxA += maxAi;
1346  }
1347 
1348  // Calculate inveps := 1/eps, where 1/eps > deg(p)*max1 for all p in G.
1349  int inveps, tot_deg = 0, maxdeg;
1350 
1351  intvec* ivUnit = Mivdp(nV);//19.02
1352  for(i=nG-1; i>=0; i--)
1353  {
1354  // maxdeg = pTotaldegree(G->m[i], currRing); //it's wrong for ex1,2,rose
1355  maxdeg = MwalkWeightDegree(G->m[i], ivUnit);
1356  if (maxdeg > tot_deg )
1357  {
1358  tot_deg = maxdeg;
1359  }
1360  }
1361  delete ivUnit;
1362 
1363  inveps = (tot_deg * maxA) + 1;
1364 
1365 #ifdef INVEPS_SMALL_IN_FRACTAL
1366  // Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", inveps, pdeg);
1367  if(inveps > pdeg && pdeg > 3)
1368  {
1369  inveps = inveps / pdeg;
1370  }
1371  // Print(" %d", inveps);
1372 #else
1373  PrintS("\n// the \"big\" inverse epsilon %d", inveps);
1374 #endif
1375 
1376  // Pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg
1377  for ( i=1; i < pdeg; i++ )
1378  {
1379  for(j=0; j<nV; j++)
1380  {
1381  (*pert_vector)[j] = inveps*((*pert_vector)[j]) + (*ivtarget)[i*nV+j];
1382  }
1383  }
1384 
1385  int temp = (*pert_vector)[0];
1386  for(i=1; i<nV; i++)
1387  {
1388  temp = gcd(temp, (*pert_vector)[i]);
1389  if(temp == 1)
1390  {
1391  break;
1392  }
1393  }
1394  if(temp != 1)
1395  {
1396  for(i=0; i<nV; i++)
1397  {
1398  (*pert_vector)[i] = (*pert_vector)[i] / temp;
1399  }
1400  }
1401 
1402  intvec* result = pert_vector;
1403  delete pert_vector;
1404  return result;
1405 }
void WerrorS(const char *s)
Definition: feFopen.cc:24
static TreeM * G
Definition: janet.cc:38
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
Definition: intvec.h:14
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
#define IDELEMS(i)
Definition: simpleideals.h:24
intvec * Mivdp(int nR)
Definition: walk.cc:1016
static long gcd(const long a, const long b)
Definition: walk.cc:541
static int MwalkWeightDegree(poly p, intvec *weight_vector)
Definition: walk.cc:677
return result
Definition: facAbsBiFact.cc:76

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

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

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

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

◆ Mrwalk()

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

Definition at line 5612 of file walk.cc.

5614 {
5615  BITSET save1 = si_opt_1; // save current options
5616  if(reduction == 0)
5617  {
5618  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5619  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5620  }
5621 
5622  Set_Error(FALSE);
5624 #ifdef TIME_TEST
5625  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5626  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5627  tinput = clock();
5628  clock_t tim;
5629 #endif
5630  nstep=0;
5631  int i,nwalk;//polylength;
5632  int nV = currRing->N;
5633 
5634  //check that weight radius is valid
5635  if(weight_rad < 0)
5636  {
5637  WerrorS("Invalid radius.\n");
5638  return NULL;
5639  }
5640 
5641  //check that perturbation degree is valid
5642  if(pert_deg > nV || pert_deg < 1)
5643  {
5644  WerrorS("Invalid perturbation degree.\n");
5645  return NULL;
5646  }
5647 
5648  ideal Gomega, M, F,FF, Gomega1, Gomega2, M1;
5649  ring newRing;
5650  ring targetRing;
5651  ring baseRing = currRing;
5652  ring XXRing = currRing;
5653  intvec* iv_M;
5654  intvec* ivNull = new intvec(nV);
5655  intvec* curr_weight = new intvec(nV);
5656  intvec* target_weight = new intvec(nV);
5657  intvec* next_weight= new intvec(nV);
5658 
5659  for(i=0; i<nV; i++)
5660  {
5661  (*curr_weight)[i] = (*orig_M)[i];
5662  (*target_weight)[i] = (*target_M)[i];
5663  }
5664 
5665 #ifndef BUCHBERGER_ALG
5666  intvec* hilb_func;
5667  // to avoid (1,0,...,0) as the target vector
5668  intvec* last_omega = new intvec(nV);
5669  for(i=nV-1; i>0; i--)
5670  {
5671  (*last_omega)[i] = 1;
5672  }
5673  (*last_omega)[0] = 10000;
5674 #endif
5676 
5677  if(target_M->length() == nV)
5678  {
5679  targetRing = VMrDefault(target_weight); // define the target ring
5680  }
5681  else
5682  {
5683  targetRing = VMatrDefault(target_M);
5684  }
5685  if(orig_M->length() == nV)
5686  {
5687  //newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5688  newRing=VMrRefine(target_weight, curr_weight);
5689  }
5690  else
5691  {
5692  newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5693  }
5694  rChangeCurrRing(newRing);
5695 #ifdef TIME_TEST
5696  to = clock();
5697 #endif
5698  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5699 #ifdef TIME_TEST
5700  tostd = clock()-to;
5701 #endif
5702  baseRing = currRing;
5703  nwalk = 0;
5704 
5705 #ifdef TIME_TEST
5706  to = clock();
5707 #endif
5708  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5709 #ifdef TIME_TEST
5710  tif = tif + clock()-to; //time for computing initial form ideal
5711 #endif
5712 
5713  while(1)
5714  {
5715  nwalk ++;
5716  nstep ++;
5717 #ifdef CHECK_IDEAL_MWALK
5718  if(printout > 1)
5719  {
5720  idString(Gomega,"//** Mrwalk: Gomega");
5721  }
5722 #endif
5723  if(reduction == 0)
5724  {
5725  FF = middleOfCone(G,Gomega);
5726  if(FF != NULL)
5727  {
5728  idDelete(&G);
5729  G = idCopy(FF);
5730  idDelete(&FF);
5731  goto NEXT_VECTOR;
5732  }
5733  }
5734 #ifndef BUCHBERGER_ALG
5735  if(isNolVector(curr_weight) == 0)
5736  {
5737  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5738  }
5739  else
5740  {
5741  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5742  }
5743 #endif
5744  if(nwalk == 1)
5745  {
5746  if(orig_M->length() == nV)
5747  {
5748  /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
5749  newRing=VMrRefine(target_weight, curr_weight);
5750  }
5751  else
5752  {
5753  newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5754  }
5755  }
5756  else
5757  {
5758  if(target_M->length() == nV)
5759  {
5760  /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
5761  newRing=VMrRefine(target_weight, curr_weight);
5762  }
5763  else
5764  {
5765  newRing = VMatrRefine(target_M,curr_weight);
5766  }
5767  }
5768  rChangeCurrRing(newRing);
5769  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5770  idDelete(&Gomega);
5771  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5772 #ifdef TIME_TEST
5773  to = clock();
5774 #endif
5775 #ifndef BUCHBERGER_ALG
5776  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5777  delete hilb_func;
5778 #else
5779  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5780 #endif
5781 #ifdef TIME_TEST
5782  tstd = tstd + clock() - to;
5783 #endif
5784  idSkipZeroes(M);
5785 #ifdef CHECK_IDEAL_MWALK
5786  if(printout > 2)
5787  {
5788  idString(M, "//** Mrwalk: M");
5789  }
5790 #endif
5791  //change the ring to baseRing
5792  rChangeCurrRing(baseRing);
5793  M1 = idrMoveR(M, newRing,currRing);
5794  idDelete(&M);
5795  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5796  idDelete(&Gomega1);
5797 #ifdef TIME_TEST
5798  to = clock();
5799 #endif
5800  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
5801  // where Gomega is a reduced Groebner basis w.r.t. the current ring
5802  F = MLifttwoIdeal(Gomega2, M1, G);
5803 #ifdef TIME_TEST
5804  tlift = tlift + clock() - to;
5805 #endif
5806 #ifdef CHECK_IDEAL_MWALK
5807  if(printout > 2)
5808  {
5809  idString(F,"//** Mrwalk: F");
5810  }
5811 #endif
5812  idDelete(&Gomega2);
5813  idDelete(&M1);
5814  rChangeCurrRing(newRing); // change the ring to newRing
5815  G = idrMoveR(F,baseRing,currRing);
5816  idDelete(&F);
5817  baseRing = currRing;
5818 #ifdef TIME_TEST
5819  to = clock();
5820  tstd = tstd + clock() - to;
5821 #endif
5822  idSkipZeroes(G);
5823 #ifdef CHECK_IDEAL_MWALK
5824  if(printout > 2)
5825  {
5826  idString(G,"//** Mrwalk: G");
5827  }
5828 #endif
5829 
5830  rChangeCurrRing(targetRing);
5831  G = idrMoveR(G,newRing,currRing);
5832 
5833  // test whether target cone is reached
5834  if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
5835  {
5836  baseRing = currRing;
5837  break;
5838  }
5839 
5840  rChangeCurrRing(newRing);
5841  G = idrMoveR(G,targetRing,currRing);
5842  baseRing = currRing;
5843 
5844  NEXT_VECTOR:
5845 #ifdef TIME_TEST
5846  to = clock();
5847 #endif
5848  next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5849 #ifdef TIME_TEST
5850  tnw = tnw + clock() - to;
5851 #endif
5852 
5853 #ifdef TIME_TEST
5854  to = clock();
5855 #endif
5856  Gomega = MwalkInitialForm(G, next_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5857 #ifdef TIME_TEST
5858  tif = tif + clock()-to; //time for computing initial form ideal
5859 #endif
5860 
5861  //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
5862  //polylength = lengthpoly(Gomega);
5863  if(lengthpoly(Gomega) > 0)
5864  {
5865  //there is a polynomial in Gomega with at least 3 monomials,
5866  //low-dimensional facet of the cone
5867  delete next_weight;
5868  if(target_M->length() == nV)
5869  {
5870  //iv_M = MivMatrixOrder(curr_weight);
5871  iv_M = MivMatrixOrderRefine(curr_weight,target_M);
5872  }
5873  else
5874  {
5875  iv_M = MivMatrixOrderRefine(curr_weight,target_M);
5876  }
5877 #ifdef TIME_TEST
5878  to = clock();
5879 #endif
5880  next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, pert_deg);
5881 #ifdef TIME_TEST
5882  tnw = tnw + clock() - to;
5883 #endif
5884  idDelete(&Gomega);
5885 #ifdef TIME_TEST
5886  to = clock();
5887 #endif
5888  Gomega = MwalkInitialForm(G, next_weight);
5889 #ifdef TIME_TEST
5890  tif = tif + clock()-to; //time for computing initial form ideal
5891 #endif
5892  delete iv_M;
5893  }
5894 
5895  // test whether target weight vector is reached
5896  if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)
5897  {
5898  baseRing = currRing;
5899  delete next_weight;
5900  break;
5901  }
5902  if(reduction ==0)
5903  {
5904  if(MivComp(curr_weight,next_weight)==1)
5905  {
5906  break;
5907  }
5908  }
5909 #ifdef PRINT_VECTORS
5910  if(printout > 0)
5911  {
5912  MivString(curr_weight, target_weight, next_weight);
5913  }
5914 #endif
5915 
5916  for(i=nV-1; i>=0; i--)
5917  {
5918  (*curr_weight)[i] = (*next_weight)[i];
5919  }
5920  delete next_weight;
5921  }
5922  baseRing = currRing;
5923  rChangeCurrRing(XXRing);
5924  ideal result = idrMoveR(G,baseRing,currRing);
5925  idDelete(&G);
5926  delete ivNull;
5927 #ifndef BUCHBERGER_ALG
5928  delete last_omega;
5929 #endif
5930  if(printout > 0)
5931  {
5932  Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
5933  }
5934 #ifdef TIME_TEST
5935  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5936  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5937  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5938 #endif
5939  si_opt_1 = save1; //set original options
5940  return(result);
5941 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1730
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:794
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1807
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define FALSE
Definition: auxiliary.h:94
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2799
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
Definition: walk.cc:992
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:2231
void WerrorS(const char *s)
Definition: feFopen.cc:24
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2850
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:18
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
Definition: intvec.h:14
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:3365
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2237
int i
Definition: cfEzgcd.cc:123
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
Definition: walk.cc:4525
ideal idCopy(ideal A)
Definition: ideals.h:60
void rChangeCurrRing(ring r)
Definition: polys.cc:12
static ideal MstdCC(ideal G)
Definition: walk.cc:941
int nstep
kstd2.cc
Definition: walk.cc:88
static int lengthpoly(ideal G)
Definition: walk.cc:3449
#define NULL
Definition: omList.c:10
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3088
int length() const
Definition: intvec.h:86
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
static void idString(ideal L, const char *st)
Definition: walk.cc:433
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1309
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:770
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2740
return result
Definition: facAbsBiFact.cc:76
static ring VMrDefault(intvec *va)
Definition: walk.cc:2689

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

5313 {
5314  // save current options
5315  BITSET save1 = si_opt_1;
5316  if(reduction == 0)
5317  {
5318  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5319  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5320  }
5321  Set_Error(FALSE);
5323  //BOOLEAN endwalks = FALSE;
5324 #ifdef TIME_TEST
5325  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5326  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5327  tinput = clock();
5328  clock_t tim;
5329 #endif
5330  nstep=0;
5331  int i,nwalk;
5332  int nV = baseRing->N;
5333 
5334  ideal Gomega, M, F, FF, Gomega1, Gomega2, M1;
5335  ring newRing;
5336  ring XXRing = baseRing;
5337  ring targetRing;
5338  intvec* ivNull = new intvec(nV);
5339  intvec* curr_weight = new intvec(nV);
5340  intvec* target_weight = new intvec(nV);
5341  intvec* exivlp = Mivlp(nV);
5342 /*
5343  intvec* tmp_weight = new intvec(nV);
5344  for(i=0; i<nV; i++)
5345  {
5346  (*tmp_weight)[i] = (*orig_M)[i];
5347  }
5348 */
5349  for(i=0; i<nV; i++)
5350  {
5351  (*curr_weight)[i] = (*orig_M)[i];
5352  (*target_weight)[i] = (*target_M)[i];
5353  }
5354 #ifndef BUCHBERGER_ALG
5355  intvec* hilb_func;
5356  // to avoid (1,0,...,0) as the target vector
5357  intvec* last_omega = new intvec(nV);
5358  for(i=nV-1; i>0; i--)
5359  {
5360  (*last_omega)[i] = 1;
5361  }
5362  (*last_omega)[0] = 10000;
5363 #endif
5365 #ifdef CHECK_IDEAL_MWALK
5366  if(printout > 2)
5367  {
5368  idString(Go,"//** Mwalk: Go");
5369  }
5370 #endif
5371 
5372  if(target_M->length() == nV)
5373  {
5374  // define the target ring
5375  targetRing = VMrDefault(target_weight);
5376  }
5377  else
5378  {
5379  targetRing = VMatrDefault(target_M);
5380  }
5381  if(orig_M->length() == nV)
5382  {
5383  // define a new ring with ordering "(a(curr_weight),lp)
5384  //newRing = VMrDefault(curr_weight);
5385  newRing=VMrRefine(target_weight, curr_weight);
5386  }
5387  else
5388  {
5389  newRing = VMatrRefine(target_M,curr_weight); //newRing = VMatrDefault(orig_M);
5390  }
5391  rChangeCurrRing(newRing);
5392  if(printout > 2)
5393  {
5394  Print("\n//** Mrwalk: Current ring r = %s;\n", rString(currRing));
5395  }
5396 #ifdef TIME_TEST
5397  to = clock();
5398 #endif
5399  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5400 #ifdef TIME_TEST
5401  tostd = clock()-to;
5402 #endif
5403 
5404  baseRing = currRing;
5405  nwalk = 0;
5406 
5407  while(1)
5408  {
5409  nwalk ++;
5410  nstep ++;
5411  //compute an initial form ideal of <G> w.r.t. "curr_vector"
5412 #ifdef TIME_TEST
5413  to = clock();
5414 #endif
5415  Gomega = MwalkInitialForm(G, curr_weight);
5416 #ifdef TIME_TEST
5417  tif = tif + clock()-to;
5418 #endif
5419 
5420 #ifdef CHECK_IDEAL_MWALK
5421  if(printout > 1)
5422  {
5423  idString(Gomega,"//** Mwalk: Gomega");
5424  }
5425 #endif
5426 
5427  if(reduction == 0)
5428  {
5429  FF = middleOfCone(G,Gomega);
5430  if(FF != NULL)
5431  {
5432  PrintS("middle of Cone");
5433  idDelete(&G);
5434  G = idCopy(FF);
5435  idDelete(&FF);
5436  goto NEXT_VECTOR;
5437  }
5438  }
5439 
5440 #ifndef BUCHBERGER_ALG
5441  if(isNolVector(curr_weight) == 0)
5442  {
5443  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5444  }
5445  else
5446  {
5447  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5448  }
5449 #endif
5450 
5451  if(nwalk == 1)
5452  {
5453  if(orig_M->length() == nV)
5454  {
5455  // define a new ring with ordering "(a(curr_weight),lp)
5456  //newRing = VMrDefault(curr_weight);
5457  newRing=VMrRefine(target_weight, curr_weight);
5458  }
5459  else
5460  {
5461  newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5462  }
5463  }
5464  else
5465  {
5466  if(target_M->length() == nV)
5467  {
5468  //define a new ring with ordering "(a(curr_weight),lp)"
5469  //newRing = VMrDefault(curr_weight);
5470  newRing=VMrRefine(target_weight, curr_weight);
5471  }
5472  else
5473  {
5474  //define a new ring with matrix ordering
5475  newRing = VMatrRefine(target_M,curr_weight);
5476  }
5477  }
5478  rChangeCurrRing(newRing);
5479  if(printout > 2)
5480  {
5481  Print("\n// Current ring r = %s;\n", rString(currRing));
5482  }
5483  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5484  idDelete(&Gomega);
5485  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5486 #ifdef TIME_TEST
5487  to = clock();
5488 #endif
5489 #ifndef BUCHBERGER_ALG
5490  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5491  delete hilb_func;
5492 #else
5493  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5494 #endif
5495 #ifdef TIME_TEST
5496  tstd = tstd + clock() - to;
5497 #endif
5498  idSkipZeroes(M);
5499 #ifdef CHECK_IDEAL_MWALK
5500  if(printout > 2)
5501  {
5502  idString(M, "//** Mwalk: M");
5503  }
5504 #endif
5505  //change the ring to baseRing
5506  rChangeCurrRing(baseRing);
5507  M1 = idrMoveR(M, newRing,currRing);
5508  idDelete(&M);
5509  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5510  idDelete(&Gomega1);
5511 #ifdef TIME_TEST
5512  to = clock();
5513 #endif
5514  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
5515  // where Gomega is a reduced Groebner basis w.r.t. the current ring
5516  F = MLifttwoIdeal(Gomega2, M1, G);
5517 #ifdef TIME_TEST
5518  tlift = tlift + clock() - to;
5519 #endif
5520 #ifdef CHECK_IDEAL_MWALK
5521  if(printout > 2)
5522  {
5523  idString(F, "//** Mwalk: F");
5524  }
5525 #endif
5526  idDelete(&Gomega2);
5527  idDelete(&M1);
5528 
5529  rChangeCurrRing(newRing); // change the ring to newRing
5530  G = idrMoveR(F,baseRing,currRing);
5531  idDelete(&F);
5532  idSkipZeroes(G);
5533 
5534 #ifdef CHECK_IDEAL_MWALK
5535  if(printout > 2)
5536  {
5537  idString(G, "//** Mwalk: G");
5538  }
5539 #endif
5540 
5541  rChangeCurrRing(targetRing);
5542  G = idrMoveR(G,newRing,currRing);
5543  // test whether target cone is reached
5544  if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
5545  {
5546  baseRing = currRing;
5547  break;
5548  //endwalks = TRUE;
5549  }
5550 
5551  rChangeCurrRing(newRing);
5552  G = idrMoveR(G,targetRing,currRing);
5553  baseRing = currRing;
5554 
5555  NEXT_VECTOR:
5556 #ifdef TIME_TEST
5557  to = clock();
5558 #endif
5559  intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5560 #ifdef TIME_TEST
5561  tnw = tnw + clock() - to;
5562 #endif
5563 #ifdef PRINT_VECTORS
5564  if(printout > 0)
5565  {
5566  MivString(curr_weight, target_weight, next_weight);
5567  }
5568 #endif
5569  if(reduction ==0)
5570  {
5571  if(MivComp(curr_weight,next_weight)==1)
5572  {
5573  break;
5574  }
5575  }
5576  if(MivComp(target_weight,curr_weight) == 1)
5577  {
5578  break;
5579  }
5580 
5581  for(i=nV-1; i>=0; i--)
5582  {
5583  //(*tmp_weight)[i] = (*curr_weight)[i];
5584  (*curr_weight)[i] = (*next_weight)[i];
5585  }
5586  delete next_weight;
5587  }
5588  rChangeCurrRing(XXRing);
5589  ideal result = idrMoveR(G,baseRing,currRing);
5590  idDelete(&Go);
5591  idDelete(&G);
5592  //delete tmp_weight;
5593  delete ivNull;
5594  delete exivlp;
5595 #ifndef BUCHBERGER_ALG
5596  delete last_omega;
5597 #endif
5598 #ifdef TIME_TEST
5599  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5600  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5601  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5602 #endif
5603  if(printout > 0)
5604  {
5605  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
5606  }
5607  si_opt_1 = save1; //set original options
5608  return(result);
5609 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1730
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:794
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1807
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define FALSE
Definition: auxiliary.h:94
char * rString(ring r)
Definition: ring.cc:648
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2799
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:2231
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2850
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:18
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
Definition: intvec.h:14
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:3365
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2237
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
ideal idCopy(ideal A)
Definition: ideals.h:60
void rChangeCurrRing(ring r)
Definition: polys.cc:12
static ideal MstdCC(ideal G)
Definition: walk.cc:941
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3088
int length() const
Definition: intvec.h:86
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
static void idString(ideal L, const char *st)
Definition: walk.cc:433
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1309
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:770
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2740
return result
Definition: facAbsBiFact.cc:76
intvec * Mivlp(int nR)
Definition: walk.cc:1031
static ring VMrDefault(intvec *va)
Definition: walk.cc:2689

◆ MwalkInitialForm()

ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 770 of file walk.cc.

771 {
772  BOOLEAN nError = Overflow_Error;
774 
775  int i, nG = IDELEMS(G);
776  ideal Gomega = idInit(nG, 1);
777 
778  for(i=nG-1; i>=0; i--)
779  {
780  Gomega->m[i] = MpolyInitialForm(G->m[i], ivw);
781  }
782  if(Overflow_Error == FALSE)
783  {
784  Overflow_Error = nError;
785  }
786  return Gomega;
787 }
#define FALSE
Definition: auxiliary.h:94
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition: walk.cc:731
static TreeM * G
Definition: janet.cc:38
BOOLEAN Overflow_Error
Definition: walk.cc:96
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
int BOOLEAN
Definition: auxiliary.h:85

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

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

◆ TranMPertVectorslp()

intvec* TranMPertVectorslp ( ideal  G)