My Project  debian-1:4.1.2-p1+ds-2
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 895 of file walk.cc.

900  {
901  if ((*u)[i] != (*v)[i])
902  {
903  return 0;
904  }
905  }
906  return 1;
907 }
908 

◆ MAltwalk1()

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

Definition at line 9599 of file walk.cc.

9603  {
9604  endwalks = 1;
9605  }
9606  for(i=nV-1; i>=0; i--)
9607  {
9608  //(*extra_curr_weight)[i] = (*curr_weight)[i];
9609  (*curr_weight)[i] = (*next_weight)[i];
9610  }
9611  delete next_weight;
9612  }//while
9613 
9614  // check whether the pertubed target vector is correct
9615 
9616  //define and execute ring with lex. order
9617  if (rParameter(currRing) != NULL)
9618  {
9619  DefRingParlp();
9620  }
9621  else
9622  {
9623  VMrDefaultlp();
9624  }
9625  G1 = idrMoveR(G, newRing,currRing);
9626 
9627  if( test_w_in_ConeCC(G1, target_weight) != 1 || ntestwinC == 0)
9628  {
9629  //PrintS("\n// The perturbed target vector doesn't STAY in the correct cone!!");
9630  if(tp_deg == 1)
9631  {
9632  //Print("\n// subroutine takes %d steps and applys \"std\"", nwalk);
9633 #ifdef TIME_TEST
9634  to=clock();
9635 #endif
9636  ideal G2 = MstdCC(G1);
9637 #ifdef TIME_TEST
9638  xtextra=xtextra+clock()-to;
9639 #endif
9640  idDelete(&G1);
9641  G1 = G2;
9642  G2 = NULL;
9643  }
9644  else
9645  {
9646  //nOverflow_Error = Overflow_Error;
9647 #ifdef TIME_TEST
9648  tproc = tproc+clock()-tinput;
9649 #endif
9650  // Print("\n// B subroutine takes %d steps and calls \"Mpwalk\" (1,%d) :", nwalk, tp_deg-1);
9651  G1 = Mpwalk_MAltwalk1(G1, curr_weight, tp_deg-1);
9652  }
9653  }
9654 
9655  MPW_Finish:
9656  newRing = currRing;
9657  rChangeCurrRing(YXXRing);
9658  ideal result = idrMoveR(G1, newRing,currRing);
9659 
9660  delete ivNull;
9661  delete target_weight;
9662 
9663  //Print("\n// \"Mpwalk\" (1,%d) took %d steps and %.2f sec. Overflow_Error (%d)", tp_deg, nwalk, ((double) clock()-tinput)/1000000, nOverflow_Error);
9664  //Print("\n// Mprwalk took %d steps. Ring= %s;\n", nwalk, rString(currRing));
9665  return(result);
9666 }
9667 
9668 /*******************************************************************
9669  * Implementation of the first alternative Groebner Walk Algorithm *
9670  *******************************************************************/
9671 ideal MAltwalk1(ideal Go, int op_deg, int tp_deg, intvec* curr_weight,
9672  intvec* target_weight)
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

◆ MAltwalk2()

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

Definition at line 4221 of file walk.cc.

4222  {
4223  DefRingParlp();
4224  }
4225  else
4226  {
4227  VMrDefaultlp();
4228  }
4229  KSTD_Finish:
4230  if(isGB == FALSE)
4231  {
4232  F1 = idrMoveR(G, newRing,currRing);
4233  }
4234  else
4235  {
4236  F1 = G;
4237  }
4238 #ifdef TIME_TEST
4239  to=clock();
4240 #endif
4241  // Print("\n// apply the Buchberger's alg in ring = %s",rString(currRing));
4242  // idElements(F1, "F1");
4243  G = MstdCC(F1);
4244 #ifdef TIME_TEST
4245  xtextra=xtextra+clock()-to;
4246 #endif
4247 
4248 
4249  idDelete(&F1);
4250  newRing = currRing;
4251  }
4252 
4253  LastGB_Finish:
4254  rChangeCurrRing(EXXRing);
4255  result = idrMoveR(G, newRing,currRing);
4256  }
4257 
4258  if(Overflow_Error == FALSE)
4259  {
4260  Overflow_Error=nError;
4261  }
4262 #ifdef TIME_TEST
4263  //Print("\n// \"Rec_LastGB\" (%d) took %d steps and %.2f sec.Overflow_Error (%d)", tp_deg, nwalk, ((double) tproc)/1000000, nOverflow_Error);
4264 #endif
4265  return(result);
4266 }
4267 
4268 /* The following subroutine is the implementation of our second improved
4269  Groebner walk algorithm, i.e. the second altervative algorithm.
4270  First we use the Grobner walk algorithm and then we call the changed
4271  perturbation walk algorithm with increased degree, if an intermediate
4272  weight vector is equal to the current target weight vector.
4273  This call will be only repeated until we get the wanted reduced Groebner
4274  basis or n times, where n is the numbers of variables.
4275 */
4276 
4277 /******************************
4278  * walk + recursive LastGB *
4279  ******************************/
4280 ideal MAltwalk2(ideal Go, intvec* curr_weight, intvec* target_weight)
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);

◆ Mfpertvector()

intvec* Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1479 of file walk.cc.

1480 {
1481  int i;
1482  intvec* ivM = new intvec(nV*nV);
1483 
1484  for(i=0; i<nV; i++)
1485  {
1486  (*ivM)[i] = 1;
1487  }
1488  for(i=1; i<nV; i++)
1489  {
1490  (*ivM)[(i+1)*nV - i] = -1;
1491  }
1492  return(ivM);
1493 }
1494 */
1495 
1496 intvec* MivUnit(int nV)
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 }
1506 
1507 
1508 /************************************************************************
1509 * compute a perturbed weight vector of a matrix order w.r.t. an ideal *
1510 *************************************************************************/
1511 VAR int Xnlev;
1512 intvec* Mfpertvector(ideal G, intvec* ivtarget)
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;

◆ Mfrwalk()

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

Definition at line 8143 of file walk.cc.

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 }
8202 
8203 /*******************************************************************************
8204  * The implementation of the fractal walk algorithm with random element *
8205  * *
8206  * The main procedur Mfwalk calls the recursive Subroutine *
8207  * rec_r_fractal_call to compute the wanted Groebner basis. *
8208  * At the main procedure we compute the reduced Groebner basis w.r.t. a "fast" *
8209  * order, e.g. "dp" and a sequence of weight vectors which are row vectors *
8210  * of a matrix. This matrix defines the given monomial order, e.g. "lp" *
8211  *******************************************************************************/
8212 ideal Mfrwalk(ideal G, intvec* ivstart, intvec* ivtarget,
8213  int weight_rad, int reduction, int printout)
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));

◆ Mfwalk()

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

Definition at line 7963 of file walk.cc.

7968  {
7969  rChangeCurrRing(oRing);
7970  Gomega1 = idrMoveR(Gomega1, oRing,currRing);
7971  Gresult = rec_r_fractal_call(idCopy(Gomega1),nlev+1,omega,weight_rad,reduction,printout);
7972  }
7973 #ifdef CHECK_IDEAL_MWALK
7974  if(printout > 2)
7975  {
7976  idString(Gresult,"//** rec_r_fractal_call: M");
7977  }
7978 #endif
7979  //convert a Groebner basis from a ring to another ring
7980  new_ring = currRing;
7981 
7982  rChangeCurrRing(oRing);
7983  Gresult1 = idrMoveR(Gresult, new_ring,currRing);
7984  Gomega2 = idrMoveR(Gomega1, new_ring,currRing);
7985 #ifdef TIME_TEST
7986  to=clock();
7987 #endif
7988  // Lifting process
7989  F = MLifttwoIdeal(Gomega2, Gresult1, G);
7990 #ifdef TIME_TEST
7991  xtlift=xtlift+clock()-to;
7992 #endif
7993 #ifdef CHECK_IDEAL_MWALK
7994  if(printout > 2)
7995  {
7996  idString(F,"//** rec_r_fractal_call: F");
7997  }
7998 #endif
8000  idDelete(&Gresult1);
8001  idDelete(&Gomega2);
8002  idDelete(&G);
8003 
8004  rChangeCurrRing(new_ring);
8005  //F1 = idrMoveR(F, oRing,currRing);
8006  G = idrMoveR(F,oRing,currRing);
8007 /*
8008 #ifdef TIME_TEST
8009  to=clock();
8010 #endif
8011  // Interreduce G
8012  G = kInterRedCC(F1, NULL);
8013 #ifdef TIME_TEST
8014  xtred=xtred+clock()-to;
8015 #endif
8016  idDelete(&F1);
8017 */
8018  }
8019 }
8020 
8021 
8022 /*******************************************************************************
8023  * The implementation of the fractal walk algorithm *
8024  * *
8025  * The main procedure Mfwalk calls the recursive Subroutine *
8026  * rec_fractal_call to compute the wanted Groebner basis. *
8027  * At the main procedur we compute the reduced Groebner basis w.r.t. a "fast" *
8028  * order, e.g. "dp" and a sequence of weight vectors which are row vectors *
8029  * of a matrix. This matrix defines the given monomial order, e.g. "lp" *
8030  *******************************************************************************/
8031 ideal Mfwalk(ideal G, intvec* ivstart, intvec* ivtarget,
8032  int reduction, int printout)
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));

◆ MidLift()

ideal MidLift ( ideal  Gomega,
ideal  M 
)

◆ Mivdp()

intvec* Mivdp ( int  nR)

Definition at line 983 of file walk.cc.

984 {
985  assume((iv->length())*(iv->length()) == iw->length());
986  int i,j, nR = iv->length();
987 
988  intvec* ivm = new intvec(nR*nR);
989 
990  for(i=0; i<nR; i++)
991  {
992  (*ivm)[i] = (*iv)[i];
993  }

◆ Mivlp()

intvec* Mivlp ( int  nR)

Definition at line 997 of file walk.cc.

997  {
998  (*ivm)[j+i*nR] = (*iw)[j+i*nR];
999  }
1000  }
1001  return ivm;
1002 }
1003 

◆ MivMatrixOrder()

intvec* MivMatrixOrder ( intvec iv)

Definition at line 941 of file walk.cc.

948 {
949  BITSET save1,save2;
950  SI_SAVE_OPT(save1,save2);
952  ideal G1 = kStd(G, NULL, isHomog, NULL);
953  SI_RESTORE_OPT(save1,save2);
954 
955  idSkipZeroes(G1);
956  return G1;

◆ MivMatrixOrderdp()

intvec* MivMatrixOrderdp ( int  iv)

Definition at line 1387 of file walk.cc.

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 }
1397 
1398 /*****************************************************************************
1399  * define a lexicographic order matrix as intvec *
1400  *****************************************************************************/
1401 intvec* MivMatrixOrderlp(int nV)

◆ MivMatrixOrderlp()

intvec* MivMatrixOrderlp ( int  nV)

Definition at line 1372 of file walk.cc.

1378  {
1379  temp = gcd(temp, (*pert_vector)[i]);
1380  if(temp == 1)
1381  {
1382  break;

◆ Mivperttarget()

intvec* Mivperttarget ( ideal  G,
int  ndeg 
)

◆ MivSame()

int MivSame ( intvec u,
intvec v 
)

Definition at line 875 of file walk.cc.

878 {
879  int i, nR = currRing->N;
880  intvec* result = new intvec(nR);
881 
882  for(i=nR-1; i>=0; i--)
883  {
884  (*result)[i] = pGetExp(f,i+1);
885  }
886  return result;
887 }
888 
889 /*****************************************************

◆ MivUnit()

intvec* MivUnit ( int  nV)

Definition at line 1464 of file walk.cc.

1467  {
1468  (*ivM)[nV+i] = 1;
1469  }
1470  for(i=2; i<nV; i++)
1471  {
1472  (*ivM)[(i+1)*nV - i] = -1;
1473  }

◆ MivWeightOrderdp()

intvec* MivWeightOrderdp ( intvec ivstart)

Definition at line 1424 of file walk.cc.

1427  {
1428  (*ivM)[(i+1)*nV - i] = -1;
1429  }
1430  return(ivM);
1431 }
1432 
1433 /*****************************************************************************
1434  * creates an intvec of the monomial order Wp(ivstart) *
1435  *****************************************************************************/
1436 intvec* MivWeightOrderlp(intvec* ivstart)
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  {

◆ MivWeightOrderlp()

intvec* MivWeightOrderlp ( intvec ivstart)

Definition at line 1405 of file walk.cc.

1407  {
1408  (*ivM)[i*nV + i] = 1;
1409  }
1410  return(ivM);
1411 }
1412 
1413 
1414 /*****************************************************************************
1415  * define a reverse lexicographic order (dp) matrix as intvec *
1416  *****************************************************************************/
1417 intvec* MivMatrixOrderdp(int nV)
1418 {
1419  int i;
1420  intvec* ivM = new intvec(nV*nV);

◆ MkInterRedNextWeight()

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

Definition at line 2530 of file walk.cc.

2548  {
2549  Overflow_Error = nError;
2550  }
2552  for(j=0; j<IDELEMS(G); j++)
2553  {

◆ 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 1061 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 

◆ MPertVectorslp()

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

Definition at line 1271 of file walk.cc.

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 }
1292 
1293 /*****************************************************************************
1294  * The following procedure returns *
1295  * Pert(A1) = 1/eps^(pdeg-1)*A_1 + 1/eps^(pdeg-2)*A_2+...+A_pdeg, *
1296  * where the A_i are the i-th rows of the matrix target_ord and *
1297  * 1/eps > deg(p)*(max(A_2) + max(A_3)+...+max(A_pdeg)) *
1298  *****************************************************************************/
1299 intvec* MPertVectorslp(ideal G, intvec* ivtarget, int pdeg)
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++ )

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

6331  {
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 }
6384 
6385 /*******************************************************
6386  * THE PERTURBATION WALK ALGORITHM WITH RANDOM ELEMENT *
6387  *******************************************************/
6388 ideal Mprwalk(ideal Go, intvec* orig_M, intvec* target_M, int weight_rad,
6389  int op_deg, int tp_deg, int nP, int reduction, int printout)
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;

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

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 }
5933 
5934 /**************************************************************/
5935 /* Implementation of the perturbation walk algorithm */
5936 /**************************************************************/
5937 /* If the perturbed target weight vector or an intermediate weight vector
5938  doesn't stay in the correct Groebner cone, we have only
5939  a reduced Groebner basis for the given ideal with respect to
5940  a monomial order which differs to the given order.
5941  Then we have to compute the wanted reduced Groebner basis for it.
5942  For this, we can use
5943  1) the improved Buchberger algorithm or
5944  2) the changed perturbation walk algorithm with a decreased degree.
5945 */
5946 // if nP = 0 use kStd, else call LastGB
5947 ideal Mpwalk(ideal Go, int op_deg, int tp_deg,intvec* curr_weight,
5948  intvec* target_weight, int nP, int reduction, int printout)
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  {

◆ Mrwalk()

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

Definition at line 5540 of file walk.cc.

5546  :
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 }
5601 
5602 // THE RANDOM WALK ALGORITHM
5603 ideal Mrwalk(ideal Go, intvec* orig_M, intvec* target_M, int weight_rad, int pert_deg,
5604  int reduction, int printout)
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();

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

5246  {
5247  newRing = currRing;
5248  PrintS("\n// ** The computed vector does NOT stay in Cone!!\n");
5249 
5250  if (rParameter(currRing) != NULL)
5251  {
5252  DefRingPar(target_weight);
5253  }
5254  else
5255  {
5256  rChangeCurrRing(VMrDefault(target_weight));
5257  }
5258  F1 = idrMoveR(G, newRing,currRing);
5259  G = MstdCC(F1);
5260  idDelete(&F1);
5261 
5262  newRing = currRing;
5263  break;
5264  }
5265 
5266  if(MivComp(next_weight, ivNull) == 1)
5267  {
5268  newRing = currRing;
5269  delete next_weight;
5270  break;
5271  }
5272  if(MivComp(next_weight, target_weight) == 1)
5273  {
5274  endwalks = 1;
5275  }
5276  for(i=nV-1; i>=0; i--)
5277  {
5278  (*tmp_weight)[i] = (*curr_weight)[i];
5279  (*curr_weight)[i] = (*next_weight)[i];
5280  }
5281  delete next_weight;
5282  }
5283  rChangeCurrRing(XXRing);
5284  G = idrMoveR(G, newRing,currRing);
5285 
5286  delete tmp_weight;
5287  delete ivNull;
5288  delete exivlp;
5289 
5290 #ifdef TIME_TEST
5291  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5292 
5293  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5294  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5295 #endif
5296  return(G);
5297 }
5298 
5299 /*******************************
5300  * THE GROEBNER WALK ALGORITHM *
5301  *******************************/
5302 ideal Mwalk(ideal Go, intvec* orig_M, intvec* target_M,
5303  ring baseRing, int reduction, int printout)
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;

◆ MwalkInitialForm()

ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 749 of file walk.cc.

762 {
763  BOOLEAN nError = Overflow_Error;
765 
766  int i, nG = IDELEMS(G);

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

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 }
8390 
8391 /*******************************************************
8392  * Tran's algorithm *
8393  * *
8394  * use kStd, if nP = 0, else call Ab_Rec_Pert (LastGB) *
8395  *******************************************************/
8396 ideal TranMImprovwalk(ideal G,intvec* curr_weight,intvec* target_tmp, int nP)
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  {

◆ TranMPertVectorslp()

intvec* TranMPertVectorslp ( ideal  G)
ivString
static void ivString(intvec *iv, const char *ch)
Definition: walk.cc:488
FALSE
#define FALSE
Definition: auxiliary.h:96
idCopy
ideal idCopy(ideal A)
Definition: ideals.h:59
VMatrDefault
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2746
OPT_REDSB
#define OPT_REDSB
Definition: options.h:73
TranMImprovwalk
ideal TranMImprovwalk(ideal G, intvec *curr_weight, intvec *target_tmp, int nP)
Definition: walk.cc:8326
reduction
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1089
Mwalk
ideal Mwalk(ideal Go, intvec *orig_M, intvec *target_M, ring baseRing, int reduction, int printout)
Definition: walk.cc:5239
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
idDelete
#define idDelete(H)
delete an ideal
Definition: ideals.h:28
rChangeCurrRing
void rChangeCurrRing(ring r)
Definition: polys.cc:15
result
return result
Definition: facAbsBiFact.cc:76
kInterRedCC
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:264
pGetExp
#define pGetExp(p, i)
Exponent.
Definition: polys.h:40
Mivdp
intvec * Mivdp(int nR)
Definition: walk.cc:983
si_opt_1
VAR unsigned si_opt_1
Definition: options.c:5
MPertVectorslp
intvec * MPertVectorslp(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1271
BITSET
#define BITSET
Definition: structs.h:19
gcd
static long gcd(const long a, const long b)
Definition: walk.cc:527
rec_r_fractal_call
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *ivtarget, int weight_rad, int reduction, int printout)
Definition: walk.cc:7386
Mpwalk
ideal Mpwalk(ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP, int reduction, int printout)
Definition: walk.cc:5884
MivUnit
intvec * MivUnit(int nV)
Definition: walk.cc:1464
MwalkWeightDegree
static int MwalkWeightDegree(poly p, intvec *weight_vector)
Definition: walk.cc:659
Overflow_Error
VAR BOOLEAN Overflow_Error
Definition: walk.cc:87
pDelete
#define pDelete(p_ptr)
Definition: polys.h:175
testHomog
Definition: structs.h:42
Xnlev
VAR int Xnlev
Definition: walk.cc:1478
LastGB
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition: walk.cc:3095
Xivlp
VAR intvec * Xivlp
Definition: walk.cc:4450
idString
static void idString(ideal L, const char *st)
Definition: walk.cc:420
Xcall
VAR int Xcall
Definition: walk.cc:6880
lengthpoly
static int lengthpoly(ideal G)
Definition: walk.cc:3389
MivMatrixOrderRefine
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
Definition: walk.cc:960
MAltwalk2
ideal MAltwalk2(ideal Go, intvec *curr_weight, intvec *target_weight)
Definition: walk.cc:4221
TRUE
#define TRUE
Definition: auxiliary.h:100
rec_fractal_call
static ideal rec_fractal_call(ideal G, int nlev, intvec *ivtarget, int reduction, int printout)
Definition: walk.cc:6885
i
int i
Definition: cfEzgcd.cc:125
Set_Error
void Set_Error(BOOLEAN f)
Definition: walk.cc:85
idrMoveR
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:247
ngleich
VAR int ngleich
Definition: walk.cc:4445
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: walk.cc:6324
nstep
VAR int nstep
kstd2.cc
Definition: walk.cc:79
Sy_bit
#define Sy_bit(x)
Definition: options.h:30
M
#define M
Definition: sirandom.c:25
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:87
MivComp
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1763
test_w_in_ConeCC
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:772
MivSame
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:875
Mfwalk
ideal Mfwalk(ideal G, intvec *ivstart, intvec *ivtarget, int reduction, int printout)
Definition: walk.cc:7963
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition: simpleideals.cc:180
VAR
#define VAR
Definition: globaldefs.h:5
Xtau
VAR intvec * Xtau
Definition: walk.cc:4447
G
STATIC_VAR TreeM * G
Definition: janet.cc:31
SI_RESTORE_OPT
#define SI_RESTORE_OPT(A, B)
Definition: options.h:22
rString
char * rString(ring r)
Definition: ring.cc:672
OPT_REDTAIL
#define OPT_REDTAIL
Definition: options.h:88
MivMatrixOrderdp
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1387
intvec
Definition: intvec.h:18
isHomog
Definition: structs.h:41
pIter
#define pIter(p)
Definition: monomials.h:34
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
MwalkNextWeightCC
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2189
MpolyInitialForm
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition: walk.cc:711
MivMatrixOrder
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:941
MstdCC
static ideal MstdCC(ideal G)
Definition: walk.cc:912
MivWeightOrderdp
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1424
VMrDefault
static ring VMrDefault(intvec *va)
Definition: walk.cc:2638
MWalkRandomNextWeight
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
Definition: walk.cc:4455
MwalkInitialForm
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:749
IDRING
#define IDRING(a)
Definition: ipid.h:121
DefRingPar
static void DefRingPar(intvec *va)
Definition: walk.cc:2892
MPertVectors
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1061
Xivinput
VAR intvec * Xivinput
Definition: walk.cc:4449
rDelete
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:447
MAltwalk1
ideal MAltwalk1(ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight)
Definition: walk.cc:9599
MivMatrixOrderlp
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1372
Mivlp
intvec * Mivlp(int nR)
Definition: walk.cc:997
hFirstSeries
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1335
MkInterRedNextWeight
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2530
ringorder_a
Definition: ring.h:69
Print
#define Print
Definition: emacs.cc:79
DefRingParlp
static void DefRingParlp(void)
Definition: walk.cc:2941
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:11
Mpwalk_MAltwalk1
static ideal Mpwalk_MAltwalk1(ideal Go, intvec *curr_weight, int tp_deg)
Definition: walk.cc:9306
islengthpoly2
static int islengthpoly2(ideal G)
Definition: walk.cc:3424
Mrwalk
ideal Mrwalk(ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int pert_deg, int reduction, int printout)
Definition: walk.cc:5540
VMrRefine
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2688
currRingHdl
VAR idhdl currRingHdl
Definition: ipid.cc:58
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:223
VMrDefaultlp
static void VMrDefaultlp(void)
Definition: walk.cc:2852
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
SI_SAVE_OPT
#define SI_SAVE_OPT(A, B)
Definition: options.h:19
p
int p
Definition: cfModGcd.cc:4019
MivWeightOrderlp
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1405
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Mfpertvector
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1479
XivNull
VAR intvec * XivNull
Definition: walk.cc:6863
pCopy
#define pCopy(p)
return a copy of the poly
Definition: polys.h:174
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:23
MstdhomCC
static ideal MstdhomCC(ideal G)
Definition: walk.cc:926
kStd
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:2087
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:65
Mfrwalk
ideal Mfrwalk(ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad, int reduction, int printout)
Definition: walk.cc:8143
MLifttwoIdeal
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1686
rParameter
static const char ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:619
intvec::length
int length() const
Definition: intvec.h:94
id_Head
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
Definition: simpleideals.cc:1183
pSub
#define pSub(a, b)
Definition: polys.h:271
VMatrRefine
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2796
id_Normalize
void id_Normalize(ideal I, const ring r)
normialize all polys in id
Definition: simpleideals.cc:1706
nnflow
VAR int nnflow
Definition: walk.cc:6879
Xngleich
VAR int Xngleich
Definition: walk.cc:6881
rComplete
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:3397
Xsigma
VAR intvec * Xsigma
Definition: walk.cc:4446
middleOfCone
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3029