My Project
Functions
walk.h File Reference
#include "kernel/structs.h"

Go to the source code of this file.

Functions

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

Function Documentation

◆ M3ivSame()

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

Definition at line 914 of file walk.cc.

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

◆ MAltwalk1()

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

Definition at line 9671 of file walk.cc.

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

◆ MAltwalk2()

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

Definition at line 4280 of file walk.cc.

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

◆ Mfpertvector()

intvec* Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1512 of file walk.cc.

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

◆ Mfrwalk()

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

Definition at line 8212 of file walk.cc.

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

◆ Mfwalk()

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

Definition at line 8031 of file walk.cc.

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

◆ MidLift()

ideal MidLift ( ideal  Gomega,
ideal  M 
)

◆ Mivdp()

intvec* Mivdp ( int  nR)

Definition at line 1007 of file walk.cc.

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

◆ Mivlp()

intvec* Mivlp ( int  nR)

Definition at line 1022 of file walk.cc.

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

◆ MivMatrixOrder()

intvec* MivMatrixOrder ( intvec iv)

Definition at line 963 of file walk.cc.

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

◆ MivMatrixOrderdp()

intvec* MivMatrixOrderdp ( int  iv)

Definition at line 1417 of file walk.cc.

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

◆ MivMatrixOrderlp()

intvec* MivMatrixOrderlp ( int  nV)

Definition at line 1401 of file walk.cc.

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

◆ Mivperttarget()

intvec* Mivperttarget ( ideal  G,
int  ndeg 
)

◆ MivSame()

int MivSame ( intvec u,
intvec v 
)

Definition at line 893 of file walk.cc.

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

◆ MivUnit()

intvec* MivUnit ( int  nV)

Definition at line 1496 of file walk.cc.

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

◆ MivWeightOrderdp()

intvec* MivWeightOrderdp ( intvec ivstart)

Definition at line 1456 of file walk.cc.

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

◆ MivWeightOrderlp()

intvec* MivWeightOrderlp ( intvec ivstart)

Definition at line 1436 of file walk.cc.

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

◆ MkInterRedNextWeight()

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

Definition at line 2570 of file walk.cc.

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

◆ MLiftLmalG()

ideal MLiftLmalG ( ideal  L,
ideal  G 
)

◆ MLiftLmalGMin()

ideal MLiftLmalGMin ( ideal  L,
ideal  G 
)

◆ MLiftLmalGNew()

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

◆ MPertNextWeight()

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

◆ MPertVectors()

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

Definition at line 1088 of file walk.cc.

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

◆ MPertVectorslp()

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

Definition at line 1299 of file walk.cc.

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

◆ Mprwalk()

ideal Mprwalk ( ideal  Go,
intvec orig_M,
intvec target_M,
int  weight_rad,
int  op_deg,
int  tp_deg,
int  nP,
int  reduction,
int  printout 
)

Definition at line 6388 of file walk.cc.

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

◆ Mpwalk()

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

Definition at line 5947 of file walk.cc.

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

◆ Mrwalk()

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

Definition at line 5603 of file walk.cc.

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

◆ MSimpleIV()

intvec* MSimpleIV ( intvec iv)

◆ Mwalk()

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

Definition at line 5302 of file walk.cc.

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

◆ MwalkInitialForm()

ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 761 of file walk.cc.

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

◆ MwalkNextWeight()

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

◆ TranMImprovwalk()

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

Definition at line 8396 of file walk.cc.

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

◆ TranMPertVectorslp()

intvec* TranMPertVectorslp ( ideal  G)