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

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

Definition at line 920 of file walk.cc.

921 {
922  assume(temp->length() == u->length() && u->length() == v->length());
923 
924  if((MivSame(temp, u)) == 1)
925  {
926  return 0;
927  }
928  if((MivSame(temp, v)) == 1)
929  {
930  return 1;
931  }
932  return 2;
933 }
int length() const
Definition: intvec.h:86
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
#define assume(x)
Definition: mod2.h:405
ideal MAltwalk1 ( ideal  G,
int  op,
int  tp,
intvec curr_weight,
intvec target_weight 
)

Definition at line 9470 of file walk.cc.

9472 {
9473  Set_Error(FALSE );
9475 #ifdef TIME_TEST
9476  BOOLEAN nOverflow_Error = FALSE;
9477 #endif
9478  // Print("// pSetm_Error = (%d)", ErrorCheck());
9479 
9480  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
9481  xftinput = clock();
9482  clock_t tostd, tproc;
9483 
9484  nstep = 0;
9485  int i, nV = currRing->N;
9486  int nwalk=0, endwalks=0;
9487  int op_tmp = op_deg;
9488  ideal Gomega, M, F, G, Gomega1, Gomega2, M1, F1;
9489  ring newRing, oldRing;
9490  intvec* next_weight;
9491  intvec* iv_M_dp;
9492  intvec* ivNull = new intvec(nV);
9493  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
9494  intvec* exivlp = Mivlp(nV);
9495  //intvec* extra_curr_weight = new intvec(nV);
9496 #ifndef BUCHBERGER_ALG
9497  intvec* hilb_func;
9498 #endif
9499  intvec* cw_tmp = curr_weight;
9500 
9501  // to avoid (1,0,...,0) as the target vector
9502  intvec* last_omega = new intvec(nV);
9503  for(i=nV-1; i>0; i--)
9504  {
9505  (*last_omega)[i] = 1;
9506  }
9507  (*last_omega)[0] = 10000;
9508 
9509  ring XXRing = currRing;
9510 
9511  to=clock();
9512  /* compute a pertubed weight vector of the original weight vector.
9513  The perturbation degree is recursive decrease until that vector
9514  stays inn the correct cone. */
9515  while(1)
9516  {
9517  if(Overflow_Error == FALSE)
9518  {
9519  if(MivComp(curr_weight, iv_dp) == 1)
9520  {
9521  //rOrdStr(currRing) = "dp"
9522  if(op_tmp == op_deg)
9523  {
9524  G = MstdCC(Go);
9525  if(op_deg != 1)
9526  {
9527  iv_M_dp = MivMatrixOrderdp(nV);
9528  }
9529  }
9530  }
9531  }
9532  else
9533  {
9534  if(op_tmp == op_deg)
9535  {
9536  //rOrdStr(currRing) = (a(...),lp,C)
9537  if (rParameter(currRing) != NULL)
9538  {
9539  DefRingPar(cw_tmp);
9540  }
9541  else
9542  {
9543  rChangeCurrRing(VMrDefault(cw_tmp));
9544  }
9545  G = idrMoveR(Go, XXRing,currRing);
9546  G = MstdCC(G);
9547  if(op_deg != 1)
9548  iv_M_dp = MivMatrixOrder(cw_tmp);
9549  }
9550  }
9552  if(op_deg != 1)
9553  {
9554  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
9555  }
9556  else
9557  {
9558  curr_weight = cw_tmp;
9559  break;
9560  }
9561  if(Overflow_Error == FALSE)
9562  {
9563  break;
9564  }
9565  Overflow_Error = TRUE;
9566  op_deg --;
9567  }
9568  tostd=clock()-to;
9569 
9570  if(op_tmp != 1 )
9571  delete iv_M_dp;
9572  delete iv_dp;
9573 
9574  if(currRing->order[0] == ringorder_a)
9575  goto NEXT_VECTOR;
9576 
9577  while(1)
9578  {
9579  nwalk ++;
9580  nstep ++;
9581 
9582  to = clock();
9583  // compute an initial form ideal of <G> w.r.t. "curr_vector"
9584  Gomega = MwalkInitialForm(G, curr_weight);
9585  xtif=xtif+clock()-to;
9586 #if 0
9587  if(Overflow_Error == TRUE)
9588  {
9589  for(i=nV-1; i>=0; i--)
9590  (*curr_weight)[i] = (*extra_curr_weight)[i];
9591  delete extra_curr_weight;
9592 
9593  newRing = currRing;
9594  goto MSTD_ALT1;
9595  }
9596 #endif
9597 #ifndef BUCHBERGER_ALG
9598  if(isNolVector(curr_weight) == 0)
9599  {
9600  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
9601  }
9602  else
9603  {
9604  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
9605  }
9606 #endif // BUCHBERGER_ALG
9607 
9608  oldRing = currRing;
9609 
9610  // define a new ring which ordering is "(a(curr_weight),lp)
9611  if (rParameter(currRing) != NULL)
9612  {
9613  DefRingPar(curr_weight);
9614  }
9615  else
9616  {
9617  rChangeCurrRing(VMrDefault(curr_weight));
9618  }
9619  newRing = currRing;
9620  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
9621 
9622  to=clock();
9623  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
9624 #ifdef BUCHBERGER_ALG
9625  M = MstdhomCC(Gomega1);
9626 #else
9627  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
9628  delete hilb_func;
9629 #endif // BUCHBERGER_ALG
9630  xtstd=xtstd+clock()-to;
9631 
9632  // change the ring to oldRing
9633  rChangeCurrRing(oldRing);
9634  M1 = idrMoveR(M, newRing,currRing);
9635  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
9636 
9637  to=clock();
9638  // compute a reduced Groebner basis of <G> w.r.t. "newRing" by the lifting process
9639  F = MLifttwoIdeal(Gomega2, M1, G);
9640  xtlift=xtlift+clock()-to;
9641 
9642  idDelete(&M1);
9643  idDelete(&Gomega2);
9644  idDelete(&G);
9645 
9646  // change the ring to newRing
9647  rChangeCurrRing(newRing);
9648  F1 = idrMoveR(F, oldRing,currRing);
9649  if (oldRing!=IDRING(currRingHdl)) rDelete(oldRing); // do not delete the global currRing
9650  oldRing=NULL;
9651 
9652  to=clock();
9653  // reduce the Groebner basis <G> w.r.t. new ring
9654  G = kInterRedCC(F1, NULL);
9655  xtred=xtred+clock()-to;
9656  idDelete(&F1);
9657 
9658  if(endwalks == 1)
9659  {
9660  break;
9661  }
9662  NEXT_VECTOR:
9663  to=clock();
9664  // compute a next weight vector
9665  next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
9666  xtnw=xtnw+clock()-to;
9667 #ifdef PRINT_VECTORS
9668  MivString(curr_weight, target_weight, next_weight);
9669 #endif
9670  if(Overflow_Error == TRUE)
9671  {
9672  newRing = currRing;
9673 
9674  if (rParameter(currRing) != NULL)
9675  {
9676  DefRingPar(target_weight);
9677  }
9678  else
9679  {
9680  rChangeCurrRing(VMrDefault(target_weight));
9681  }
9682  F1 = idrMoveR(G, newRing,currRing);
9683  G = MstdCC(F1);
9684  idDelete(&F1);
9685  newRing = currRing;
9686  break; //for while
9687  }
9688 
9689 
9690  /* G is the wanted Groebner basis if next_weight == curr_weight */
9691  if(MivComp(next_weight, ivNull) == 1)
9692  {
9693  newRing = currRing;
9694  delete next_weight;
9695  break; //for while
9696  }
9697 
9698  if(MivComp(next_weight, target_weight) == 1)
9699  {
9700  if(tp_deg == 1 || MivSame(target_weight, exivlp) == 0)
9701  endwalks = 1;
9702  else
9703  {
9704  // MSTD_ALT1:
9705 #ifdef TIME_TEST
9706  nOverflow_Error = Overflow_Error;
9707 #endif
9708  tproc = clock()-xftinput;
9709 
9710  //Print("\n// main routine takes %d steps and calls \"Mpwalk\" (1,%d):", nwalk, tp_deg);
9711 
9712  // compute the red. GB of <G> w.r.t. the lex order by the "recursive-modified" perturbation walk alg (1,tp_deg)
9713  G = Mpwalk_MAltwalk1(G, curr_weight, tp_deg);
9714  delete next_weight;
9715  break; // for while
9716  }
9717  }
9718 
9719  //NOT Changed, to free memory
9720  for(i=nV-1; i>=0; i--)
9721  {
9722  //(*extra_curr_weight)[i] = (*curr_weight)[i];
9723  (*curr_weight)[i] = (*next_weight)[i];
9724  }
9725  delete next_weight;
9726  }//while
9727 
9728  rChangeCurrRing(XXRing);
9729  ideal result = idrMoveR(G, newRing,currRing);
9730  id_Delete(&G, newRing);
9731 
9732  delete ivNull;
9733  if(op_deg != 1 )
9734  {
9735  delete curr_weight;
9736  }
9737  delete exivlp;
9738 #ifdef TIME_TEST
9739 /*
9740  Print("\n// \"Main procedure\" took %d steps, %.2f sec. and Overflow_Error(%d)",
9741  nwalk, ((double) tproc)/1000000, nOverflow_Error);
9742 
9743  TimeStringFractal(xftinput, tostd, xtif, xtstd,xtextra, xtlift, xtred, xtnw);
9744 */
9745  // Print("\n// pSetm_Error = (%d)", ErrorCheck());
9746  // Print("\n// Overflow_Error? (%d)", Overflow_Error);
9747  // Print("\n// Awalk1 took %d steps.\n", nstep);
9748 #endif
9749  return(result);
9750 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:969
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:99
#define TRUE
Definition: auxiliary.h:144
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:2221
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
BOOLEAN Overflow_Error
Definition: walk.cc:97
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
idhdl currRingHdl
Definition: ipid.cc:65
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:100
static ideal Mpwalk_MAltwalk1(ideal Go, intvec *curr_weight, int tp_deg)
Definition: walk.cc:9206
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1094
static ideal MstdhomCC(ideal G)
Definition: walk.cc:953
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static int isNolVector(intvec *hilb)
Definition: walk.cc:3050
static ideal MstdCC(ideal G)
Definition: walk.cc:938
int nstep
kstd2.cc
Definition: walk.cc:89
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2946
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:448
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:276
#define IDRING(a)
Definition: ipid.h:126
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1423
clock_t xtlift
Definition: walk.cc:99
intvec * MivUnit(int nV)
Definition: walk.cc:1502
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
int BOOLEAN
Definition: auxiliary.h:131
clock_t xtextra
Definition: walk.cc:100
return result
Definition: facAbsBiFact.cc:76
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2577
ideal MAltwalk2 ( ideal  G,
intvec curr_weight,
intvec target_weight 
)

Definition at line 4235 of file walk.cc.

4236 {
4237  Set_Error(FALSE);
4239  //BOOLEAN nOverflow_Error = FALSE;
4240  //Print("// pSetm_Error = (%d)", ErrorCheck());
4241 #ifdef TIME_TEST
4242  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
4243  xftinput = clock();
4244  clock_t tostd, tproc;
4245 #endif
4246  nstep = 0;
4247  int i, nV = currRing->N;
4248  int nwalk=0, endwalks=0;
4249  // int nhilb = 1;
4250  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
4251  //ideal G1;
4252  //ring endRing;
4253  ring newRing, oldRing;
4254  intvec* ivNull = new intvec(nV);
4255  intvec* next_weight;
4256  //intvec* extra_curr_weight = new intvec(nV);
4257  //intvec* hilb_func;
4258  intvec* exivlp = Mivlp(nV);
4259  ring XXRing = currRing;
4260 
4261  //Print("\n// ring r_input = %s;", rString(currRing));
4262 #ifdef TIME_TEST
4263  to = clock();
4264 #endif
4265  /* compute the reduced Groebner basis of the given ideal w.r.t.
4266  a "fast" monomial order, e.g. degree reverse lex. order (dp) */
4267  G = MstdCC(Go);
4268 #ifdef TIME_TEST
4269  tostd=clock()-to;
4270 
4271  Print("\n// Computation of the first std took = %.2f sec",
4272  ((double) tostd)/1000000);
4273 #endif
4274  if(currRing->order[0] == ringorder_a)
4275  {
4276  goto NEXT_VECTOR;
4277  }
4278  while(1)
4279  {
4280  nwalk ++;
4281  nstep ++;
4282 #ifdef TIME_TEST
4283  to = clock();
4284 #endif
4285  /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
4286  Gomega = MwalkInitialForm(G, curr_weight);
4287 #ifdef TIME_TEST
4288  xtif=xtif+clock()-to;
4289 #endif
4290 /*
4291  if(Overflow_Error == TRUE)
4292  {
4293  for(i=nV-1; i>=0; i--)
4294  (*curr_weight)[i] = (*extra_curr_weight)[i];
4295  delete extra_curr_weight;
4296  goto LAST_GB_ALT2;
4297  }
4298 */
4299  oldRing = currRing;
4300 
4301  /* define a new ring that its ordering is "(a(curr_weight),lp) */
4302  if (rParameter(currRing) != NULL)
4303  {
4304  DefRingPar(curr_weight);
4305  }
4306  else
4307  {
4308  rChangeCurrRing(VMrDefault(curr_weight));
4309  }
4310  newRing = currRing;
4311  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
4312 #ifdef TIME_TEST
4313  to = clock();
4314 #endif
4315  /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
4316  M = MstdhomCC(Gomega1);
4317 #ifdef TIME_TEST
4318  xtstd=xtstd+clock()-to;
4319 #endif
4320  /* change the ring to oldRing */
4321  rChangeCurrRing(oldRing);
4322  M1 = idrMoveR(M, newRing,currRing);
4323  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
4324 #ifdef TIME_TEST
4325  to = clock();
4326 #endif
4327  /* compute the reduced Groebner basis of <G> w.r.t. "newRing"
4328  by the liftig process */
4329  F = MLifttwoIdeal(Gomega2, M1, G);
4330 #ifdef TIME_TEST
4331  xtlift=xtlift+clock()-to;
4332 #endif
4333  idDelete(&M1);
4334  idDelete(&Gomega2);
4335  idDelete(&G);
4336 
4337  /* change the ring to newRing */
4338  rChangeCurrRing(newRing);
4339  F1 = idrMoveR(F, oldRing,currRing);
4340 #ifdef TIME_TEST
4341  to = clock();
4342 #endif
4343  /* reduce the Groebner basis <G> w.r.t. newRing */
4344  G = kInterRedCC(F1, NULL);
4345 #ifdef TIME_TEST
4346  xtred=xtred+clock()-to;
4347 #endif
4348  idDelete(&F1);
4349 
4350  if(endwalks == 1)
4351  break;
4352 
4353  NEXT_VECTOR:
4354 #ifdef TIME_TEST
4355  to = clock();
4356 #endif
4357  /* compute a next weight vector */
4358  next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
4359 #ifdef TIME_TEST
4360  xtnw=xtnw+clock()-to;
4361 #endif
4362 #ifdef PRINT_VECTORS
4363  MivString(curr_weight, target_weight, next_weight);
4364 #endif
4365 
4366  if(Overflow_Error == TRUE)
4367  {
4368  /*
4369  ivString(next_weight, "omega");
4370  PrintS("\n// ** The weight vector does NOT stay in Cone!!\n");
4371  */
4372 #ifdef TEST_OVERFLOW
4373  goto TEST_OVERFLOW_OI;
4374 #endif
4375 
4376  newRing = currRing;
4377  if (rParameter(currRing) != NULL)
4378  {
4379  DefRingPar(target_weight);
4380  }
4381  else
4382  {
4383  rChangeCurrRing(VMrDefault(target_weight)); // Aenderung
4384  }
4385  F1 = idrMoveR(G, newRing,currRing);
4386  G = MstdCC(F1);
4387  idDelete(&F1);
4388  newRing = currRing;
4389  break;
4390  }
4391 
4392  if(MivComp(next_weight, ivNull) == 1)
4393  {
4394  newRing = currRing;
4395  delete next_weight;
4396  break;
4397  }
4398 
4399  if(MivComp(next_weight, target_weight) == 1)
4400  {
4401  if(MivSame(target_weight, exivlp)==1)
4402  {
4403  // LAST_GB_ALT2:
4404  //nOverflow_Error = Overflow_Error;
4405 #ifdef TIME_TEST
4406  tproc = clock()-xftinput;
4407 #endif
4408  //Print("\n// takes %d steps and calls the recursion of level 2:", nwalk);
4409  /* call the changed perturbation walk algorithm with degree 2 */
4410  G = Rec_LastGB(G, curr_weight, target_weight, 2,1);
4411  newRing = currRing;
4412  delete next_weight;
4413  break;
4414  }
4415  endwalks = 1;
4416  }
4417 
4418  for(i=nV-1; i>=0; i--)
4419  {
4420  //(*extra_curr_weight)[i] = (*curr_weight)[i];
4421  (*curr_weight)[i] = (*next_weight)[i];
4422  }
4423  delete next_weight;
4424  }
4425 #ifdef TEST_OVERFLOW
4426  TEST_OVERFLOW_OI:
4427 #endif
4428  rChangeCurrRing(XXRing);
4429  G = idrMoveR(G, newRing,currRing);
4430  delete ivNull;
4431  delete exivlp;
4432 
4433 #ifdef TIME_TEST
4434  /*Print("\n// \"Main procedure\" took %d steps dnd %.2f sec. Overflow_Error (%d)",
4435  nwalk, ((double) tproc)/1000000, nOverflow_Error);
4436 */
4437  TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
4438 
4439  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
4440  //Print("\n// Overflow_Error? (%d)", nOverflow_Error);
4441  //Print("\n// Awalk2 took %d steps!!", nstep);
4442 #endif
4443 
4444  return(G);
4445 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
#define Print
Definition: emacs.cc:83
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
clock_t xtred
Definition: walk.cc:99
#define TRUE
Definition: auxiliary.h:144
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
BOOLEAN Overflow_Error
Definition: walk.cc:97
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:100
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:99
static ideal Rec_LastGB(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
Definition: walk.cc:3918
clock_t xtnw
Definition: walk.cc:99
static ideal MstdhomCC(ideal G)
Definition: walk.cc:953
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static ideal MstdCC(ideal G)
Definition: walk.cc:938
int nstep
kstd2.cc
Definition: walk.cc:89
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2946
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:276
clock_t xtlift
Definition: walk.cc:99
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
clock_t xtextra
Definition: walk.cc:100
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2577
intvec* Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1518 of file walk.cc.

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

Definition at line 8104 of file walk.cc.

8106 {
8107  BITSET save1 = si_opt_1; // save current options
8108  //check that weight radius is valid
8109  if(weight_rad < 0)
8110  {
8111  Werror("Invalid radius.\n");
8112  return NULL;
8113  }
8114  if(reduction == 0)
8115  {
8116  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
8117  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
8118  }
8119  Set_Error(FALSE);
8121  //Print("// pSetm_Error = (%d)", ErrorCheck());
8122  //Print("\n// ring ro = %s;", rString(currRing));
8123 
8124  nnflow = 0;
8125  Xngleich = 0;
8126  Xcall = 0;
8127 #ifdef TIME_TEST
8128  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8129  xftinput = clock();
8130 #endif
8131  ring oldRing = currRing;
8132  int i, nV = currRing->N;
8133  XivNull = new intvec(nV);
8134  Xivinput = ivtarget;
8135  ngleich = 0;
8136 #ifdef TIME_TEST
8137  to=clock();
8138 #endif
8139  ideal I = MstdCC(G);
8140  G = NULL;
8141 #ifdef TIME_TEST
8142  xftostd=clock()-to;
8143 #endif
8144  Xsigma = ivstart;
8145 
8146  Xnlev=nV;
8147 
8148 #ifdef FIRST_STEP_FRACTAL
8149  ideal Gw = MwalkInitialForm(I, ivstart);
8150  for(i=IDELEMS(Gw)-1; i>=0; i--)
8151  {
8152  if((Gw->m[i]!=NULL) // len >=0
8153  && (Gw->m[i]->next!=NULL) // len >=1
8154  && (Gw->m[i]->next->next!=NULL)) // len >=2
8155  {
8156  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
8157  intvec* Mdp;
8158  if(ivstart->length() == nV)
8159  {
8160  if(MivSame(ivstart, iv_dp) != 1)
8161  Mdp = MivWeightOrderdp(ivstart);
8162  else
8163  Mdp = MivMatrixOrderdp(nV);
8164  }
8165  else
8166  {
8167  Mdp = ivstart;
8168  }
8169 
8170  Xsigma = Mfpertvector(I, Mdp);
8172 
8173  delete Mdp;
8174  delete iv_dp;
8175  break;
8176  }
8177  }
8178  idDelete(&Gw);
8179 #endif
8180 
8181  ideal I1;
8182  intvec* Mlp;
8183  Xivlp = Mivlp(nV);
8184 
8185  if(ivtarget->length() == nV)
8186  {
8187  if(MivComp(ivtarget, Xivlp) != 1)
8188  {
8189  if (rParameter(currRing) != NULL)
8190  DefRingPar(ivtarget);
8191  else
8192  rChangeCurrRing(VMrDefault(ivtarget));
8193 
8194  I1 = idrMoveR(I, oldRing,currRing);
8195  Mlp = MivWeightOrderlp(ivtarget);
8196  Xtau = Mfpertvector(I1, Mlp);
8197  }
8198  else
8199  {
8200  if (rParameter(currRing) != NULL)
8201  DefRingParlp();
8202  else
8203  VMrDefaultlp();
8204 
8205  I1 = idrMoveR(I, oldRing,currRing);
8206  Mlp = MivMatrixOrderlp(nV);
8207  Xtau = Mfpertvector(I1, Mlp);
8208  }
8209  }
8210  else
8211  {
8212  rChangeCurrRing(VMatrDefault(ivtarget));
8213  I1 = idrMoveR(I,oldRing,currRing);
8214  Mlp = ivtarget;
8215  Xtau = Mfpertvector(I1, Mlp);
8216  }
8217  delete Mlp;
8219 
8220  //ivString(Xsigma, "Xsigma");
8221  //ivString(Xtau, "Xtau");
8222 
8223  id_Delete(&I, oldRing);
8224  ring tRing = currRing;
8225  if(ivtarget->length() == nV)
8226  {
8227 /*
8228  if (rParameter(currRing) != NULL)
8229  DefRingPar(ivstart);
8230  else
8231  rChangeCurrRing(VMrDefault(ivstart));
8232 */
8233  rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8234  }
8235  else
8236  {
8237  //rChangeCurrRing(VMatrDefault(ivstart));
8238  rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8239  }
8240 
8241  I = idrMoveR(I1,tRing,currRing);
8242 #ifdef TIME_TEST
8243  to=clock();
8244 #endif
8245  ideal J = MstdCC(I);
8246  idDelete(&I);
8247 #ifdef TIME_TEST
8248  xftostd=xftostd+clock()-to;
8249 #endif
8250  ideal resF;
8251  ring helpRing = currRing;
8252 
8253  J = rec_r_fractal_call(J,1,ivtarget,weight_rad,reduction,printout);
8254  //idString(J,"//*** Mfrwalk: J");
8255  //Print("\n//** Mfrwalk hier (1)\n");
8256  rChangeCurrRing(oldRing);
8257  //Print("\n//** Mfrwalk hier (2)\n");
8258  resF = idrMoveR(J, helpRing,currRing);
8259  //Print("\n//** Mfrwalk hier (3)\n");
8260  //idSkipZeroes(resF);
8261  //Print("\n//** Mfrwalk hier (4)\n");
8262  si_opt_1 = save1; //set original options, e. g. option(RedSB)
8263  delete Xivlp;
8264  //delete Xsigma;
8265  delete Xtau;
8266  delete XivNull;
8267  //Print("\n//** Mfrwalk hier (5)\n");
8268 #ifdef TIME_TEST
8269  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8270  xtlift, xtred, xtnw);
8271 
8272 
8273  // Print("\n// pSetm_Error = (%d)", ErrorCheck());
8274  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8275  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8276 #endif
8277  //Print("\n//** Mfrwalk hier (6)\n");
8278  //idString(resF,"resF");
8279  //Print("\n//** Mfrwalk hier (7)\n");
8280  return(resF);
8281 }
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1518
intvec * Xivlp
Definition: walk.cc:4465
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
intvec * Xivinput
Definition: walk.cc:4464
int nnflow
Definition: walk.cc:6839
int ngleich
Definition: walk.cc:4460
int Xngleich
Definition: walk.cc:6841
#define FALSE
Definition: auxiliary.h:140
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1442
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *ivtarget, int weight_rad, int reduction, int printout)
Definition: walk.cc:7348
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2797
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:99
intvec * Xsigma
Definition: walk.cc:4461
int length() const
Definition: intvec.h:86
int Xnlev
Definition: walk.cc:1517
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1462
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
intvec * Xtau
Definition: walk.cc:4462
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2848
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:97
static void VMrDefaultlp(void)
Definition: walk.cc:2905
int Xcall
Definition: walk.cc:6840
clock_t xftostd
Definition: walk.cc:100
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:100
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
#define IDELEMS(i)
Definition: simpleideals.h:24
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2995
static ideal MstdCC(ideal G)
Definition: walk.cc:938
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2946
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1082
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1423
clock_t xtlift
Definition: walk.cc:99
intvec * MivUnit(int nV)
Definition: walk.cc:1502
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2738
clock_t xtextra
Definition: walk.cc:100
intvec * XivNull
Definition: walk.cc:6822
void Werror(const char *fmt,...)
Definition: reporter.cc:199
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1407
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
ideal Mfwalk ( ideal  G,
intvec ivstart,
intvec ivtarget,
int  reduction,
int  printout 
)

Definition at line 7923 of file walk.cc.

7925 {
7926  BITSET save1 = si_opt_1; // save current options
7927  if(reduction == 0)
7928  {
7929  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
7930  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
7931  }
7932  Set_Error(FALSE);
7934  //Print("// pSetm_Error = (%d)", ErrorCheck());
7935  //Print("\n// ring ro = %s;", rString(currRing));
7936 
7937  nnflow = 0;
7938  Xngleich = 0;
7939  Xcall = 0;
7940 #ifdef TIME_TEST
7941  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
7942  xftinput = clock();
7943 #endif
7944  ring oldRing = currRing;
7945  int i, nV = currRing->N;
7946  XivNull = new intvec(nV);
7947  Xivinput = ivtarget;
7948  ngleich = 0;
7949 #ifdef TIME_TEST
7950  to=clock();
7951 #endif
7952  ideal I = MstdCC(G);
7953  G = NULL;
7954 #ifdef TIME_TEST
7955  xftostd=clock()-to;
7956 #endif
7957  Xsigma = ivstart;
7958 
7959  Xnlev=nV;
7960 
7961 #ifdef FIRST_STEP_FRACTAL
7962  ideal Gw = MwalkInitialForm(I, ivstart);
7963  for(i=IDELEMS(Gw)-1; i>=0; i--)
7964  {
7965  if((Gw->m[i]!=NULL) // len >=0
7966  && (Gw->m[i]->next!=NULL) // len >=1
7967  && (Gw->m[i]->next->next!=NULL)) // len >=2
7968  {
7969  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
7970  intvec* Mdp;
7971  if(ivstart->length() == nV)
7972  {
7973  if(MivSame(ivstart, iv_dp) != 1)
7974  Mdp = MivWeightOrderdp(ivstart);
7975  else
7976  Mdp = MivMatrixOrderdp(nV);
7977  }
7978  else
7979  {
7980  Mdp = ivstart;
7981  }
7982 
7983  Xsigma = Mfpertvector(I, Mdp);
7985 
7986  delete Mdp;
7987  delete iv_dp;
7988  break;
7989  }
7990  }
7991  idDelete(&Gw);
7992 #endif
7993 
7994  ideal I1;
7995  intvec* Mlp;
7996  Xivlp = Mivlp(nV);
7997 
7998  if(ivtarget->length() == nV)
7999  {
8000  if(MivComp(ivtarget, Xivlp) != 1)
8001  {
8002  if (rParameter(currRing) != NULL)
8003  DefRingPar(ivtarget);
8004  else
8005  rChangeCurrRing(VMrDefault(ivtarget));
8006 
8007  I1 = idrMoveR(I, oldRing,currRing);
8008  Mlp = MivWeightOrderlp(ivtarget);
8009  Xtau = Mfpertvector(I1, Mlp);
8010  }
8011  else
8012  {
8013  if (rParameter(currRing) != NULL)
8014  DefRingParlp();
8015  else
8016  VMrDefaultlp();
8017 
8018  I1 = idrMoveR(I, oldRing,currRing);
8019  Mlp = MivMatrixOrderlp(nV);
8020  Xtau = Mfpertvector(I1, Mlp);
8021  }
8022  }
8023  else
8024  {
8025  rChangeCurrRing(VMatrDefault(ivtarget));
8026  I1 = idrMoveR(I,oldRing,currRing);
8027  Mlp = ivtarget;
8028  Xtau = Mfpertvector(I1, Mlp);
8029  }
8030  delete Mlp;
8032 
8033  //ivString(Xsigma, "Xsigma");
8034  //ivString(Xtau, "Xtau");
8035 
8036  id_Delete(&I, oldRing);
8037  ring tRing = currRing;
8038  if(ivtarget->length() == nV)
8039  {
8040 /*
8041  if (rParameter(currRing) != NULL)
8042  DefRingPar(ivstart);
8043  else
8044  rChangeCurrRing(VMrDefault(ivstart));
8045 */
8046  rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8047  }
8048  else
8049  {
8050  //rChangeCurrRing(VMatrDefault(ivstart));
8051  rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8052  }
8053 
8054  I = idrMoveR(I1,tRing,currRing);
8055 #ifdef TIME_TEST
8056  to=clock();
8057 #endif
8058  ideal J = MstdCC(I);
8059  idDelete(&I);
8060 #ifdef TIME_TEST
8061  xftostd=xftostd+clock()-to;
8062 #endif
8063  ideal resF;
8064  ring helpRing = currRing;
8065 
8066  J = rec_fractal_call(J,1,ivtarget,reduction,printout);
8067  //idString(J,"//** Mfwalk: J");
8068  rChangeCurrRing(oldRing);
8069  //Print("\n//Mfwalk: (2)\n");
8070  resF = idrMoveR(J, helpRing,currRing);
8071  //Print("\n//Mfwalk: (3)\n");
8072  idSkipZeroes(resF);
8073  //Print("\n//Mfwalk: (4)\n");
8074 
8075  si_opt_1 = save1; //set original options, e. g. option(RedSB)
8076  delete Xivlp;
8077  //delete Xsigma;
8078  delete Xtau;
8079  delete XivNull;
8080  //Print("\n//Mfwalk: (5)\n");
8081 #ifdef TIME_TEST
8082  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8083  xtlift, xtred, xtnw);
8084 
8085 
8086  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
8087  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8088  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8089 #endif
8090  //Print("\n//Mfwalk: (6)\n");
8091  //idString(resF,"//** Mfwalk: resF");
8092  return(idCopy(resF));
8093 }
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1518
intvec * Xivlp
Definition: walk.cc:4465
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
intvec * Xivinput
Definition: walk.cc:4464
int nnflow
Definition: walk.cc:6839
int ngleich
Definition: walk.cc:4460
int Xngleich
Definition: walk.cc:6841
#define FALSE
Definition: auxiliary.h:140
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1442
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2797
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:99
intvec * Xsigma
Definition: walk.cc:4461
int length() const
Definition: intvec.h:86
int Xnlev
Definition: walk.cc:1517
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1462
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
intvec * Xtau
Definition: walk.cc:4462
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2848
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:97
static void VMrDefaultlp(void)
Definition: walk.cc:2905
int Xcall
Definition: walk.cc:6840
clock_t xftostd
Definition: walk.cc:100
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:100
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static ideal rec_fractal_call(ideal G, int nlev, intvec *ivtarget, int reduction, int printout)
Definition: walk.cc:6846
ideal idCopy(ideal A)
Definition: ideals.h:73
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2995
static ideal MstdCC(ideal G)
Definition: walk.cc:938
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2946
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1082
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1423
clock_t xtlift
Definition: walk.cc:99
intvec * MivUnit(int nV)
Definition: walk.cc:1502
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2738
clock_t xtextra
Definition: walk.cc:100
intvec * XivNull
Definition: walk.cc:6822
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1407
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
ideal MidLift ( ideal  Gomega,
ideal  M 
)
intvec* Mivdp ( int  nR)

Definition at line 1013 of file walk.cc.

1014 {
1015  int i;
1016  intvec* ivm = new intvec(nR);
1017 
1018  for(i=nR-1; i>=0; i--)
1019  {
1020  (*ivm)[i] = 1;
1021  }
1022  return ivm;
1023 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* Mivlp ( int  nR)

Definition at line 1028 of file walk.cc.

1029 {
1030  intvec* ivm = new intvec(nR);
1031  (*ivm)[0] = 1;
1032 
1033  return ivm;
1034 }
Definition: intvec.h:16
intvec* MivMatrixOrder ( intvec iv)

Definition at line 969 of file walk.cc.

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

Definition at line 1423 of file walk.cc.

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

Definition at line 1407 of file walk.cc.

1408 {
1409  int i;
1410  intvec* ivM = new intvec(nV*nV);
1411 
1412  for(i=0; i<nV; i++)
1413  {
1414  (*ivM)[i*nV + i] = 1;
1415  }
1416  return(ivM);
1417 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* Mivperttarget ( ideal  G,
int  ndeg 
)
int MivSame ( intvec u,
intvec v 
)

Definition at line 899 of file walk.cc.

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

Definition at line 1502 of file walk.cc.

1503 {
1504  int i;
1505  intvec* ivM = new intvec(nV);
1506  for(i=nV-1; i>=0; i--)
1507  {
1508  (*ivM)[i] = 1;
1509  }
1510  return(ivM);
1511 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MivWeightOrderdp ( intvec ivstart)

Definition at line 1462 of file walk.cc.

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

Definition at line 1442 of file walk.cc.

1443 {
1444  int i;
1445  int nV = ivstart->length();
1446  intvec* ivM = new intvec(nV*nV);
1447 
1448  for(i=0; i<nV; i++)
1449  {
1450  (*ivM)[i] = (*ivstart)[i];
1451  }
1452  for(i=1; i<nV; i++)
1453  {
1454  (*ivM)[i*nV + i-1] = 1;
1455  }
1456  return(ivM);
1457 }
int length() const
Definition: intvec.h:86
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MkInterRedNextWeight ( intvec iva,
intvec ivb,
ideal  G 
)

Definition at line 2577 of file walk.cc.

2578 {
2579  intvec* tmp = new intvec(iva->length());
2580  intvec* result;
2581 
2582  if(G == NULL)
2583  {
2584  return tmp;
2585  }
2586  if(MivComp(iva, ivb) == 1)
2587  {
2588  return tmp;
2589  }
2590  result = MwalkNextWeightCC(iva, ivb, G);
2591 
2592  if(MivComp(result, iva) == 1)
2593  {
2594  delete result;
2595  return tmp;
2596  }
2597 
2598  delete tmp;
2599  return result;
2600 }
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
int length() const
Definition: intvec.h:86
static TreeM * G
Definition: janet.cc:38
Definition: intvec.h:16
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2235
#define NULL
Definition: omList.c:10
return result
Definition: facAbsBiFact.cc:76
ideal MLiftLmalG ( ideal  L,
ideal  G 
)
ideal MLiftLmalGMin ( ideal  L,
ideal  G 
)
ideal MLiftLmalGNew ( ideal  Gomega,
ideal  M,
ideal  G 
)
intvec* MPertNextWeight ( intvec iva,
ideal  G,
int  deg 
)
intvec* MPertVectors ( ideal  G,
intvec ivtarget,
int  pdeg 
)

Definition at line 1094 of file walk.cc.

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

Definition at line 1305 of file walk.cc.

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

6285 {
6286  BITSET save1 = si_opt_1; // save current options
6287  if(reduction == 0)
6288  {
6289  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
6290  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
6291  }
6292  Set_Error(FALSE);
6294  //Print("// pSetm_Error = (%d)", ErrorCheck());
6295 #ifdef TIME_TEST
6296  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
6297  xtextra=0;
6298  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
6299  tinput = clock();
6300 
6301  clock_t tim;
6302 #endif
6303  nstep = 0;
6304  int i, ntwC=1, ntestw=1, nV = currRing->N; //polylength
6305 
6306  //check that weight radius is valid
6307  if(weight_rad < 0)
6308  {
6309  Werror("Invalid radius.\n");
6310  return NULL;
6311  }
6312 
6313  //check that perturbation degree is valid
6314  if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
6315  {
6316  Werror("Invalid perturbation degree.\n");
6317  return NULL;
6318  }
6319 
6320  BOOLEAN endwalks = FALSE;
6321 
6322  ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
6323  ring newRing, oldRing, TargetRing;
6324  intvec* iv_M;
6325  intvec* iv_M_dp;
6326  intvec* iv_M_lp;
6327  intvec* exivlp = Mivlp(nV);
6328  intvec* curr_weight = new intvec(nV);
6329  intvec* target_weight = new intvec(nV);
6330  for(i=0; i<nV; i++)
6331  {
6332  (*curr_weight)[i] = (*orig_M)[i];
6333  (*target_weight)[i] = (*target_M)[i];
6334  }
6335  intvec* orig_target = target_weight;
6336  intvec* pert_target_vector = target_weight;
6337  intvec* ivNull = new intvec(nV);
6338  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
6339 #ifndef BUCHBERGER_ALG
6340  intvec* hilb_func;
6341 #endif
6342  intvec* next_weight;
6343 
6344  // to avoid (1,0,...,0) as the target vector
6345  intvec* last_omega = new intvec(nV);
6346  for(i=nV-1; i>0; i--)
6347  (*last_omega)[i] = 1;
6348  (*last_omega)[0] = 10000;
6349 
6350  ring XXRing = currRing;
6351 
6352  // perturbs the original vector
6353  if(orig_M->length() == nV)
6354  {
6355  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
6356  {
6357 #ifdef TIME_TEST
6358  to = clock();
6359 #endif
6360  G = MstdCC(Go);
6361 #ifdef TIME_TEST
6362  tostd = clock()-to;
6363 #endif
6364  if(op_deg != 1)
6365  {
6366  iv_M_dp = MivMatrixOrderdp(nV);
6367  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
6368  }
6369  }
6370  else
6371  {
6372  //define ring order := (a(curr_weight),lp);
6373  if (rParameter(currRing) != NULL)
6374  DefRingPar(curr_weight);
6375  else
6376  rChangeCurrRing(VMrDefault(curr_weight));
6377 
6378  G = idrMoveR(Go, XXRing,currRing);
6379 #ifdef TIME_TEST
6380  to = clock();
6381 #endif
6382  G = MstdCC(G);
6383 #ifdef TIME_TEST
6384  tostd = clock()-to;
6385 #endif
6386  if(op_deg != 1)
6387  {
6388  iv_M_dp = MivMatrixOrder(curr_weight);
6389  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
6390  }
6391  }
6392  }
6393  else
6394  {
6395  rChangeCurrRing(VMatrDefault(orig_M));
6396  G = idrMoveR(Go, XXRing,currRing);
6397 #ifdef TIME_TEST
6398  to = clock();
6399 #endif
6400  G = MstdCC(G);
6401 #ifdef TIME_TEST
6402  tostd = clock()-to;
6403 #endif
6404  if(op_deg != 1)
6405  {
6406  curr_weight = MPertVectors(G, orig_M, op_deg);
6407  }
6408  }
6409 
6410  delete iv_dp;
6411  if(op_deg != 1) delete iv_M_dp;
6412 
6413  ring HelpRing = currRing;
6414 
6415  // perturbs the target weight vector
6416  if(target_M->length() == nV)
6417  {
6418  if(tp_deg > 1 && tp_deg <= nV)
6419  {
6420  if (rParameter(currRing) != NULL)
6421  DefRingPar(target_weight);
6422  else
6423  rChangeCurrRing(VMrDefault(target_weight));
6424 
6425  TargetRing = currRing;
6426  ssG = idrMoveR(G,HelpRing,currRing);
6427  if(MivSame(target_weight, exivlp) == 1)
6428  {
6429  iv_M_lp = MivMatrixOrderlp(nV);
6430  target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
6431  }
6432  else
6433  {
6434  iv_M_lp = MivMatrixOrder(target_weight);
6435  target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
6436  }
6437  delete iv_M_lp;
6438  pert_target_vector = target_weight;
6439  rChangeCurrRing(HelpRing);
6440  G = idrMoveR(ssG, TargetRing,currRing);
6441  }
6442  }
6443  else
6444  {
6445  if(tp_deg > 1 && tp_deg <= nV)
6446  {
6447  rChangeCurrRing(VMatrDefault(target_M));
6448  TargetRing = currRing;
6449  ssG = idrMoveR(G,HelpRing,currRing);
6450  target_weight = MPertVectors(ssG, target_M, tp_deg);
6451  }
6452  }
6453  if(printout > 0)
6454  {
6455  Print("\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
6456  ivString(curr_weight, "//** Mprwalk: new current weight");
6457  ivString(target_weight, "//** Mprwalk: new target weight");
6458  }
6459 
6460 #ifdef TIME_TEST
6461  to = clock();
6462 #endif
6463  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
6464 #ifdef TIME_TEST
6465  tif = tif + clock()-to; //time for computing initial form ideal
6466 #endif
6467 
6468  while(1)
6469  {
6470  nstep ++;
6471 #ifdef CHECK_IDEAL_MWALK
6472  if(printout > 1)
6473  {
6474  idString(Gomega,"//** Mprwalk: Gomega");
6475  }
6476 #endif
6477 
6478  if(reduction == 0 && nstep > 1)
6479  {
6480  FF = middleOfCone(G,Gomega);
6481  if(FF != NULL)
6482  {
6483  idDelete(&G);
6484  G = idCopy(FF);
6485  idDelete(&FF);
6486  goto NEXT_VECTOR;
6487  }
6488  }
6489 
6490 #ifdef ENDWALKS
6491  if(endwalks == TRUE)
6492  {
6493  if(printout > 0)
6494  {
6495  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6496  //idElements(G, "G");
6497  //headidString(G, "G");
6498  }
6499  }
6500 #endif
6501 
6502 #ifndef BUCHBERGER_ALG
6503  if(isNolVector(curr_weight) == 0)
6504  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
6505  else
6506  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
6507 #endif // BUCHBERGER_ALG
6508 
6509  oldRing = currRing;
6510 
6511  if(target_M->length() == nV)
6512  {/*
6513  // define a new ring with ordering "(a(curr_weight),lp)
6514  if (rParameter(currRing) != NULL)
6515  DefRingPar(curr_weight);
6516  else
6517  rChangeCurrRing(VMrDefault(curr_weight));
6518 */
6519  rChangeCurrRing(VMrRefine(target_M,curr_weight));
6520  }
6521  else
6522  {
6523  rChangeCurrRing(VMatrRefine(target_M,curr_weight));
6524  }
6525  newRing = currRing;
6526  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
6527 #ifdef ENDWALKS
6528  if(endwalks == TRUE)
6529  {
6530  if(printout > 0)
6531  {
6532  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6533 
6534  //idElements(Gomega1, "Gw");
6535  //headidString(Gomega1, "headGw");
6536 
6537  PrintS("\n// compute a rGB of Gw:\n");
6538  }
6539 #ifndef BUCHBERGER_ALG
6540  ivString(hilb_func, "w");
6541 #endif
6542  }
6543 #endif
6544 #ifdef TIME_TEST
6545  tim = clock();
6546  to = clock();
6547 #endif
6548  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
6549 #ifdef BUCHBERGER_ALG
6550  M = MstdhomCC(Gomega1);
6551 #else
6552  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
6553  delete hilb_func;
6554 #endif
6555 #ifdef CHECK_IDEAL_MWALK
6556  if(printout > 2)
6557  {
6558  idString(M,"//** Mprwalk: M");
6559  }
6560 #endif
6561 #ifdef TIME_TEST
6562  if(endwalks == TRUE)
6563  {
6564  xtstd = xtstd+clock()-to;
6565 #ifdef ENDWALKS
6566  Print("\n// time for the last std(Gw) = %.2f sec\n",
6567  ((double) clock())/1000000 -((double)tim) /1000000);
6568 #endif
6569  }
6570  else
6571  tstd=tstd+clock()-to;
6572 #endif
6573  /* change the ring to oldRing */
6574  rChangeCurrRing(oldRing);
6575  M1 = idrMoveR(M, newRing,currRing);
6576  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
6577 #ifdef TIME_TEST
6578  to=clock();
6579 #endif
6580  /* compute a representation of the generators of submod (M)
6581  with respect to those of mod (Gomega).
6582  Gomega is a reduced Groebner basis w.r.t. the current ring */
6583  F = MLifttwoIdeal(Gomega2, M1, G);
6584 #ifdef TIME_TEST
6585  if(endwalks == FALSE)
6586  tlift = tlift+clock()-to;
6587  else
6588  xtlift=clock()-to;
6589 #endif
6590 #ifdef CHECK_IDEAL_MWALK
6591  if(printout > 2)
6592  {
6593  idString(F,"//** Mprwalk: F");
6594  }
6595 #endif
6596 
6597  idDelete(&M1);
6598  idDelete(&Gomega2);
6599  idDelete(&G);
6600 
6601  // change the ring to newRing
6602  rChangeCurrRing(newRing);
6603  if(reduction == 0)
6604  {
6605  G = idrMoveR(F,oldRing,currRing);
6606  }
6607  else
6608  {
6609  F1 = idrMoveR(F, oldRing,currRing);
6610  if(printout > 2)
6611  {
6612  PrintS("\n //** Mprwalk: reduce the Groebner basis.\n");
6613  }
6614 #ifdef TIME_TEST
6615  to=clock();
6616 #endif
6617  G = kInterRedCC(F1, NULL);
6618 #ifdef TIME_TEST
6619  if(endwalks == FALSE)
6620  tred = tred+clock()-to;
6621  else
6622  xtred=clock()-to;
6623 #endif
6624  idDelete(&F1);
6625  }
6626 
6627  if(endwalks == TRUE)
6628  break;
6629 
6630  NEXT_VECTOR:
6631 #ifdef TIME_TEST
6632  to = clock();
6633 #endif
6634  next_weight = next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
6635 #ifdef TIME_TEST
6636  tnw = tnw + clock() - to;
6637 #endif
6638 
6639 #ifdef TIME_TEST
6640  to = clock();
6641 #endif
6642  // compute an initial form ideal of <G> w.r.t. "next_vector"
6643  Gomega = MwalkInitialForm(G, next_weight);
6644 #ifdef TIME_TEST
6645  tif = tif + clock()-to; //time for computing initial form ideal
6646 #endif
6647 
6648  //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
6649  if(lengthpoly(Gomega) > 0)
6650  {
6651  if(printout > 1)
6652  {
6653  Print("\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
6654  }
6655  // low-dimensional facet of the cone
6656  delete next_weight;
6657  if(target_M->length() == nV)
6658  {
6659  iv_M = MivMatrixOrder(curr_weight);
6660  }
6661  else
6662  {
6663  iv_M = MivMatrixOrderRefine(curr_weight,target_M);
6664  }
6665 #ifdef TIME_TEST
6666  to = clock();
6667 #endif
6668  next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, op_deg);
6669 #ifdef TIME_TEST
6670  tnw = tnw + clock() - to;
6671 #endif
6672  idDelete(&Gomega);
6673 #ifdef TIME_TEST
6674  to = clock();
6675 #endif
6676  Gomega = MwalkInitialForm(G, next_weight);
6677 #ifdef TIME_TEST
6678  tif = tif + clock()-to; //time for computing initial form ideal
6679 #endif
6680  delete iv_M;
6681  }
6682 
6683 #ifdef PRINT_VECTORS
6684  if(printout > 0)
6685  {
6686  MivString(curr_weight, target_weight, next_weight);
6687  }
6688 #endif
6689 
6690  if(Overflow_Error == TRUE)
6691  {
6692  ntwC = 0;
6693  //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6694  //idElements(G, "G");
6695  delete next_weight;
6696  goto FINISH_160302;
6697  }
6698  if(MivComp(next_weight, ivNull) == 1){
6699  newRing = currRing;
6700  delete next_weight;
6701  //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6702  break;
6703  }
6704  if(MivComp(next_weight, target_weight) == 1)
6705  endwalks = TRUE;
6706 
6707  for(i=nV-1; i>=0; i--)
6708  (*curr_weight)[i] = (*next_weight)[i];
6709 
6710  delete next_weight;
6711  }// end of while-loop
6712 
6713  if(tp_deg != 1)
6714  {
6715  FINISH_160302:
6716  if(target_M->length() == nV)
6717  {
6718  if(MivSame(orig_target, exivlp) == 1)
6719  if (rParameter(currRing) != NULL)
6720  DefRingParlp();
6721  else
6722  VMrDefaultlp();
6723  else
6724  if (rParameter(currRing) != NULL)
6725  DefRingPar(orig_target);
6726  else
6727  rChangeCurrRing(VMrDefault(orig_target));
6728  }
6729  else
6730  {
6731  rChangeCurrRing(VMatrDefault(target_M));
6732  }
6733  TargetRing=currRing;
6734  F1 = idrMoveR(G, newRing,currRing);
6735 
6736  // check whether the pertubed target vector stays in the correct cone
6737  if(ntwC != 0)
6738  {
6739  ntestw = test_w_in_ConeCC(F1, pert_target_vector);
6740  }
6741  if(ntestw != 1 || ntwC == 0)
6742  {
6743  if(ntestw != 1 && printout > 2)
6744  {
6745 #ifdef PRINT_VECTORS
6746  ivString(pert_target_vector, "tau");
6747 #endif
6748  PrintS("\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
6749  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6750  //idElements(F1, "G");
6751  }
6752  // LastGB is "better" than the kStd subroutine
6753 #ifdef TIME_TEST
6754  to=clock();
6755 #endif
6756  ideal eF1;
6757  if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1 || target_M->length() != nV)
6758  {
6759  if(printout > 2)
6760  {
6761  PrintS("\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
6762  }
6763  eF1 = MstdCC(F1);
6764  idDelete(&F1);
6765  }
6766  else
6767  {
6768  if(printout > 2)
6769  {
6770  PrintS("\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
6771  }
6772  rChangeCurrRing(newRing);
6773  ideal F2 = idrMoveR(F1, TargetRing,currRing);
6774  eF1 = LastGB(F2, curr_weight, tp_deg-1);
6775  F2=NULL;
6776  }
6777 #ifdef TIME_TEST
6778  xtextra=clock()-to;
6779 #endif
6780  ring exTargetRing = currRing;
6781 
6782  rChangeCurrRing(XXRing);
6783  Eresult = idrMoveR(eF1, exTargetRing,currRing);
6784  }
6785  else
6786  {
6787  rChangeCurrRing(XXRing);
6788  Eresult = idrMoveR(F1, TargetRing,currRing);
6789  }
6790  }
6791  else
6792  {
6793  rChangeCurrRing(XXRing);
6794  Eresult = idrMoveR(G, newRing,currRing);
6795  }
6796  si_opt_1 = save1; //set original options, e. g. option(RedSB)
6797  delete ivNull;
6798  if(tp_deg != 1)
6799  delete target_weight;
6800 
6801  if(op_deg != 1 )
6802  delete curr_weight;
6803 
6804  delete exivlp;
6805  delete last_omega;
6806 
6807 #ifdef TIME_TEST
6808  TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6809  tnw+xtnw);
6810 
6811  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
6812  //Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
6813 #endif
6814 
6815  if(printout > 0)
6816  {
6817  Print("\n//** Mprwalk: Perturbation Walk took %d steps.\n", nstep);
6818  }
6819  return(Eresult);
6820 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:969
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:791
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
char * rString(ring r)
Definition: ring.cc:644
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2797
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
Definition: walk.cc:989
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition: walk.cc:3150
clock_t xtred
Definition: walk.cc:99
#define TRUE
Definition: auxiliary.h:144
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:2221
int length() const
Definition: intvec.h:86
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2848
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:97
static void VMrDefaultlp(void)
Definition: walk.cc:2905
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1094
static ideal MstdhomCC(ideal G)
Definition: walk.cc:953
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
Definition: walk.cc:4471
ideal idCopy(ideal A)
Definition: ideals.h:73
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2995
static int isNolVector(intvec *hilb)
Definition: walk.cc:3050
static ideal MstdCC(ideal G)
Definition: walk.cc:938
int nstep
kstd2.cc
Definition: walk.cc:89
static int lengthpoly(ideal G)
Definition: walk.cc:3425
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2946
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3084
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1082
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:276
static void idString(ideal L, const char *st)
Definition: walk.cc:432
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1423
clock_t xtlift
Definition: walk.cc:99
intvec * MivUnit(int nV)
Definition: walk.cc:1502
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
static void ivString(intvec *iv, const char *ch)
Definition: walk.cc:500
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2738
int BOOLEAN
Definition: auxiliary.h:131
clock_t xtextra
Definition: walk.cc:100
void Werror(const char *fmt,...)
Definition: reporter.cc:199
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1407
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2577
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 5848 of file walk.cc.

5850 {
5851  BITSET save1 = si_opt_1; // save current options
5852  if(reduction == 0)
5853  {
5854  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5855  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5856  }
5857  Set_Error(FALSE );
5859  //Print("// pSetm_Error = (%d)", ErrorCheck());
5860 #ifdef TIME_TEST
5861  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5862  xtextra=0;
5863  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5864  tinput = clock();
5865 
5866  clock_t tim;
5867 #endif
5868  nstep = 0;
5869  int i, ntwC=1, ntestw=1, nV = currRing->N;
5870 
5871  //check that perturbation degree is valid
5872  if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
5873  {
5874  Werror("Invalid perturbation degree.\n");
5875  return NULL;
5876  }
5877 
5878  BOOLEAN endwalks = FALSE;
5879  ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5880  ring newRing, oldRing, TargetRing;
5881  intvec* iv_M_dp;
5882  intvec* iv_M_lp;
5883  intvec* exivlp = Mivlp(nV);
5884  intvec* orig_target = target_weight;
5885  intvec* pert_target_vector = target_weight;
5886  intvec* ivNull = new intvec(nV);
5887  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
5888 #ifndef BUCHBERGER_ALG
5889  intvec* hilb_func;
5890 #endif
5891  intvec* next_weight;
5892 
5893  // to avoid (1,0,...,0) as the target vector
5894  intvec* last_omega = new intvec(nV);
5895  for(i=nV-1; i>0; i--)
5896  (*last_omega)[i] = 1;
5897  (*last_omega)[0] = 10000;
5898 
5899  ring XXRing = currRing;
5900 #ifdef TIME_TEST
5901  to = clock();
5902 #endif
5903  // perturbs the original vector
5904  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
5905  {
5906  G = MstdCC(Go);
5907 #ifdef TIME_TEST
5908  tostd = clock()-to;
5909 #endif
5910  if(op_deg != 1){
5911  iv_M_dp = MivMatrixOrderdp(nV);
5912  //ivString(iv_M_dp, "iv_M_dp");
5913  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
5914  }
5915  }
5916  else
5917  {
5918  //define ring order := (a(curr_weight),lp);
5919 /*
5920  if (rParameter(currRing) != NULL)
5921  DefRingPar(curr_weight);
5922  else
5923  rChangeCurrRing(VMrDefault(curr_weight));
5924 */
5925  rChangeCurrRing(VMrRefine(target_weight,curr_weight));
5926 
5927  G = idrMoveR(Go, XXRing,currRing);
5928  G = MstdCC(G);
5929 #ifdef TIME_TEST
5930  tostd = clock()-to;
5931 #endif
5932  if(op_deg != 1){
5933  iv_M_dp = MivMatrixOrder(curr_weight);
5934  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
5935  }
5936  }
5937  delete iv_dp;
5938  if(op_deg != 1) delete iv_M_dp;
5939 
5940  ring HelpRing = currRing;
5941 
5942  // perturbs the target weight vector
5943  if(tp_deg > 1 && tp_deg <= nV)
5944  {
5945 /*
5946  if (rParameter(currRing) != NULL)
5947  DefRingPar(target_weight);
5948  else
5949  rChangeCurrRing(VMrDefault(target_weight));
5950 */
5951  rChangeCurrRing(VMrRefine(target_weight,curr_weight));
5952 
5953  TargetRing = currRing;
5954  ssG = idrMoveR(G,HelpRing,currRing);
5955  if(MivSame(target_weight, exivlp) == 1)
5956  {
5957  iv_M_lp = MivMatrixOrderlp(nV);
5958  target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
5959  }
5960  else
5961  {
5962  iv_M_lp = MivMatrixOrder(target_weight);
5963  target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
5964  }
5965  delete iv_M_lp;
5966  pert_target_vector = target_weight;
5967  rChangeCurrRing(HelpRing);
5968  G = idrMoveR(ssG, TargetRing,currRing);
5969  }
5970  if(printout > 0)
5971  {
5972  Print("\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
5973 #ifdef PRINT_VECTORS
5974  ivString(curr_weight, "//** Mpwalk: new current weight");
5975  ivString(target_weight, "//** Mpwalk: new target weight");
5976 #endif
5977  }
5978  while(1)
5979  {
5980  nstep ++;
5981 #ifdef TIME_TEST
5982  to = clock();
5983 #endif
5984  // compute an initial form ideal of <G> w.r.t. the weight vector
5985  // "curr_weight"
5986  Gomega = MwalkInitialForm(G, curr_weight);
5987 #ifdef TIME_TEST
5988  tif = tif + clock()-to;
5989 #endif
5990 #ifdef CHECK_IDEAL_MWALK
5991  if(printout > 1)
5992  {
5993  idString(Gomega,"//** Mpwalk: Gomega");
5994  }
5995 #endif
5996  if(reduction == 0 && nstep > 1)
5997  {
5998  FF = middleOfCone(G,Gomega);
5999  if(FF != NULL)
6000  {
6001  idDelete(&G);
6002  G = idCopy(FF);
6003  idDelete(&FF);
6004  goto NEXT_VECTOR;
6005  }
6006  }
6007 
6008 #ifdef ENDWALKS
6009  if(endwalks == TRUE)
6010  {
6011  if(printout > 0)
6012  {
6013  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6014  }
6015  //idElements(G, "G");
6016  //headidString(G, "G");
6017  }
6018 #endif
6019 
6020 #ifndef BUCHBERGER_ALG
6021  if(isNolVector(curr_weight) == 0)
6022  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
6023  else
6024  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
6025 #endif // BUCHBERGER_ALG
6026 
6027  oldRing = currRing;
6028 
6029  // define a new ring with ordering "(a(curr_weight),lp)
6030 /*
6031  if (rParameter(currRing) != NULL)
6032  DefRingPar(curr_weight);
6033  else
6034  rChangeCurrRing(VMrDefault(curr_weight));
6035 */
6036  rChangeCurrRing(VMrRefine(target_weight,curr_weight));
6037 
6038  newRing = currRing;
6039  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
6040 
6041 #ifdef ENDWALKS
6042  if(endwalks==TRUE)
6043  {
6044  if(printout > 0)
6045  {
6046  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6047  //idElements(Gomega1, "Gw");
6048  //headidString(Gomega1, "headGw");
6049  PrintS("\n// compute a rGB of Gw:\n");
6050  }
6051 #ifndef BUCHBERGER_ALG
6052  ivString(hilb_func, "w");
6053 #endif
6054  }
6055 #endif
6056 #ifdef TIME_TEST
6057  tim = clock();
6058  to = clock();
6059 #endif
6060  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
6061 #ifdef BUCHBERGER_ALG
6062  M = MstdhomCC(Gomega1);
6063 #else
6064  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
6065  delete hilb_func;
6066 #endif
6067 
6068  if(endwalks == TRUE)
6069  {
6070 #ifdef TIME_TEST
6071  xtstd = xtstd+clock()-to;
6072 #endif
6073 #ifdef ENDWALKS
6074  if(printout > 1)
6075  {
6076  Print("\n// time for the last std(Gw) = %.2f sec\n",
6077  ((double) clock())/1000000 -((double)tim) /1000000);
6078  }
6079 #endif
6080  }
6081  else
6082  {
6083 #ifdef TIME_TEST
6084  tstd=tstd+clock()-to;
6085 #endif
6086  }
6087 #ifdef CHECK_IDEAL_MWALK
6088  if(printout > 2)
6089  {
6090  idString(M,"//** Mpwalk: M");
6091  }
6092 #endif
6093  // change the ring to oldRing
6094  rChangeCurrRing(oldRing);
6095  M1 = idrMoveR(M, newRing,currRing);
6096  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
6097 #ifdef TIME_TEST
6098  to=clock();
6099 #endif
6100  /* compute a representation of the generators of submod (M)
6101  with respect to those of mod (Gomega).
6102  Gomega is a reduced Groebner basis w.r.t. the current ring */
6103  F = MLifttwoIdeal(Gomega2, M1, G);
6104 #ifdef TIME_TEST
6105  if(endwalks == FALSE)
6106  tlift = tlift+clock()-to;
6107  else
6108  xtlift=clock()-to;
6109 #endif
6110 #ifdef CHECK_IDEAL_MWALK
6111  if(printout > 2)
6112  {
6113  idString(F,"//** Mpwalk: F");
6114  }
6115 #endif
6116 
6117  idDelete(&M1);
6118  idDelete(&Gomega2);
6119  idDelete(&G);
6120 
6121  // change the ring to newRing
6122  rChangeCurrRing(newRing);
6123  if(reduction == 0)
6124  {
6125  G = idrMoveR(F,oldRing,currRing);
6126  }
6127  else
6128  {
6129  F1 = idrMoveR(F, oldRing,currRing);
6130  if(printout > 2)
6131  {
6132  PrintS("\n //** Mpwalk: reduce the Groebner basis.\n");
6133  }
6134 #ifdef TIME_TEST
6135  to=clock();
6136 #endif
6137  G = kInterRedCC(F1, NULL);
6138 #ifdef TIME_TEST
6139  if(endwalks == FALSE)
6140  tred = tred+clock()-to;
6141  else
6142  xtred=clock()-to;
6143 #endif
6144  idDelete(&F1);
6145  }
6146  if(endwalks == TRUE)
6147  break;
6148 
6149  NEXT_VECTOR:
6150 #ifdef TIME_TEST
6151  to=clock();
6152 #endif
6153  // compute a next weight vector
6154  next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
6155 #ifdef TIME_TEST
6156  tnw=tnw+clock()-to;
6157 #endif
6158 #ifdef PRINT_VECTORS
6159  if(printout > 0)
6160  {
6161  MivString(curr_weight, target_weight, next_weight);
6162  }
6163 #endif
6164 
6165  if(Overflow_Error == TRUE)
6166  {
6167  ntwC = 0;
6168  //ntestomega = 1;
6169  //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6170  //idElements(G, "G");
6171  delete next_weight;
6172  goto FINISH_160302;
6173  }
6174  if(MivComp(next_weight, ivNull) == 1){
6175  newRing = currRing;
6176  delete next_weight;
6177  //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6178  break;
6179  }
6180  if(MivComp(next_weight, target_weight) == 1)
6181  endwalks = TRUE;
6182 
6183  for(i=nV-1; i>=0; i--)
6184  (*curr_weight)[i] = (*next_weight)[i];
6185 
6186  delete next_weight;
6187  }//end of while-loop
6188 
6189  if(tp_deg != 1)
6190  {
6191  FINISH_160302:
6192  if(MivSame(orig_target, exivlp) == 1) {
6193  /* if (rParameter(currRing) != NULL)
6194  DefRingParlp();
6195  else
6196  VMrDefaultlp();
6197  else
6198  if (rParameter(currRing) != NULL)
6199  DefRingPar(orig_target);
6200  else*/
6201  rChangeCurrRing(VMrDefault(orig_target));
6202  }
6203  TargetRing=currRing;
6204  F1 = idrMoveR(G, newRing,currRing);
6205 /*
6206 #ifdef CHECK_IDEAL_MWALK
6207  headidString(G, "G");
6208 #endif
6209 */
6210 
6211  // check whether the pertubed target vector stays in the correct cone
6212  if(ntwC != 0){
6213  ntestw = test_w_in_ConeCC(F1, pert_target_vector);
6214  }
6215 
6216  if( ntestw != 1 || ntwC == 0)
6217  {
6218  if(ntestw != 1 && printout >2)
6219  {
6220  ivString(pert_target_vector, "tau");
6221  PrintS("\n// ** perturbed target vector doesn't stay in cone!!");
6222  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6223  //idElements(F1, "G");
6224  }
6225  // LastGB is "better" than the kStd subroutine
6226  to=clock();
6227  ideal eF1;
6228  if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1){
6229  // PrintS("\n// ** calls \"std\" to compute a GB");
6230  eF1 = MstdCC(F1);
6231  idDelete(&F1);
6232  }
6233  else {
6234  // PrintS("\n// ** calls \"LastGB\" to compute a GB");
6235  rChangeCurrRing(newRing);
6236  ideal F2 = idrMoveR(F1, TargetRing,currRing);
6237  eF1 = LastGB(F2, curr_weight, tp_deg-1);
6238  F2=NULL;
6239  }
6240  xtextra=clock()-to;
6241  ring exTargetRing = currRing;
6242 
6243  rChangeCurrRing(XXRing);
6244  Eresult = idrMoveR(eF1, exTargetRing,currRing);
6245  }
6246  else{
6247  rChangeCurrRing(XXRing);
6248  Eresult = idrMoveR(F1, TargetRing,currRing);
6249  }
6250  }
6251  else {
6252  rChangeCurrRing(XXRing);
6253  Eresult = idrMoveR(G, newRing,currRing);
6254  }
6255  si_opt_1 = save1; //set original options, e. g. option(RedSB)
6256  delete ivNull;
6257  if(tp_deg != 1)
6258  delete target_weight;
6259 
6260  if(op_deg != 1 )
6261  delete curr_weight;
6262 
6263  delete exivlp;
6264  delete last_omega;
6265 
6266 #ifdef TIME_TEST
6267  TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6268  tnw+xtnw);
6269 
6270  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
6271  //Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
6272 #endif
6273  if(printout > 0)
6274  {
6275  Print("\n//** Mpwalk: Perturbation Walk took %d steps.\n", nstep);
6276  }
6277  return(Eresult);
6278 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:969
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:791
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
char * rString(ring r)
Definition: ring.cc:644
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition: walk.cc:3150
clock_t xtred
Definition: walk.cc:99
#define TRUE
Definition: auxiliary.h:144
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:2221
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:97
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1094
static ideal MstdhomCC(ideal G)
Definition: walk.cc:953
ideal idCopy(ideal A)
Definition: ideals.h:73
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static int isNolVector(intvec *hilb)
Definition: walk.cc:3050
static ideal MstdCC(ideal G)
Definition: walk.cc:938
int nstep
kstd2.cc
Definition: walk.cc:89
#define NULL
Definition: omList.c:10
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3084
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1082
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:276
static void idString(ideal L, const char *st)
Definition: walk.cc:432
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1423
clock_t xtlift
Definition: walk.cc:99
intvec * MivUnit(int nV)
Definition: walk.cc:1502
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
static void ivString(intvec *iv, const char *ch)
Definition: walk.cc:500
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2738
int BOOLEAN
Definition: auxiliary.h:131
clock_t xtextra
Definition: walk.cc:100
void Werror(const char *fmt,...)
Definition: reporter.cc:199
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1407
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2577
ideal Mrwalk ( ideal  Go,
intvec orig_M,
intvec target_M,
int  weight_rad,
int  pert_deg,
int  reduction,
int  printout 
)

Definition at line 5503 of file walk.cc.

5505 {
5506  BITSET save1 = si_opt_1; // save current options
5507  if(reduction == 0)
5508  {
5509  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5510  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5511  }
5512 
5513  Set_Error(FALSE);
5515  BOOLEAN endwalks = FALSE;
5516 #ifdef TIME_TEST
5517  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5518  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5519  tinput = clock();
5520  clock_t tim;
5521 #endif
5522  nstep=0;
5523  int i,nwalk;//polylength;
5524  int nV = currRing->N;
5525 
5526  //check that weight radius is valid
5527  if(weight_rad < 0)
5528  {
5529  Werror("Invalid radius.\n");
5530  return NULL;
5531  }
5532 
5533  //check that perturbation degree is valid
5534  if(pert_deg > nV || pert_deg < 1)
5535  {
5536  Werror("Invalid perturbation degree.\n");
5537  return NULL;
5538  }
5539 
5540  ideal Gomega, M, F,FF, Gomega1, Gomega2, M1;
5541  ring newRing;
5542  ring targetRing;
5543  ring baseRing = currRing;
5544  ring XXRing = currRing;
5545  intvec* iv_M;
5546  intvec* ivNull = new intvec(nV);
5547  intvec* curr_weight = new intvec(nV);
5548  intvec* target_weight = new intvec(nV);
5549  intvec* next_weight= new intvec(nV);
5550 
5551  for(i=0; i<nV; i++)
5552  {
5553  (*curr_weight)[i] = (*orig_M)[i];
5554  (*target_weight)[i] = (*target_M)[i];
5555  }
5556 
5557 #ifndef BUCHBERGER_ALG
5558  intvec* hilb_func;
5559  // to avoid (1,0,...,0) as the target vector
5560  intvec* last_omega = new intvec(nV);
5561  for(i=nV-1; i>0; i--)
5562  {
5563  (*last_omega)[i] = 1;
5564  }
5565  (*last_omega)[0] = 10000;
5566 #endif
5568 
5569  if(target_M->length() == nV)
5570  {
5571  targetRing = VMrDefault(target_weight); // define the target ring
5572  }
5573  else
5574  {
5575  targetRing = VMatrDefault(target_M);
5576  }
5577  if(orig_M->length() == nV)
5578  {
5579  //newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5580  newRing=VMrRefine(target_weight, curr_weight);
5581  }
5582  else
5583  {
5584  newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5585  }
5586  rChangeCurrRing(newRing);
5587 #ifdef TIME_TEST
5588  to = clock();
5589 #endif
5590  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5591 #ifdef TIME_TEST
5592  tostd = clock()-to;
5593 #endif
5594  baseRing = currRing;
5595  nwalk = 0;
5596 
5597 #ifdef TIME_TEST
5598  to = clock();
5599 #endif
5600  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5601 #ifdef TIME_TEST
5602  tif = tif + clock()-to; //time for computing initial form ideal
5603 #endif
5604 
5605  while(1)
5606  {
5607  nwalk ++;
5608  nstep ++;
5609 #ifdef CHECK_IDEAL_MWALK
5610  if(printout > 1)
5611  {
5612  idString(Gomega,"//** Mrwalk: Gomega");
5613  }
5614 #endif
5615  if(reduction == 0)
5616  {
5617  FF = middleOfCone(G,Gomega);
5618  if(FF != NULL)
5619  {
5620  idDelete(&G);
5621  G = idCopy(FF);
5622  idDelete(&FF);
5623  goto NEXT_VECTOR;
5624  }
5625  }
5626 #ifndef BUCHBERGER_ALG
5627  if(isNolVector(curr_weight) == 0)
5628  {
5629  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5630  }
5631  else
5632  {
5633  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5634  }
5635 #endif
5636  if(nwalk == 1)
5637  {
5638  if(orig_M->length() == nV)
5639  {
5640  /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
5641  newRing=VMrRefine(target_weight, curr_weight);
5642  }
5643  else
5644  {
5645  newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5646  }
5647  }
5648  else
5649  {
5650  if(target_M->length() == nV)
5651  {
5652  /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
5653  newRing=VMrRefine(target_weight, curr_weight);
5654  }
5655  else
5656  {
5657  newRing = VMatrRefine(target_M,curr_weight);
5658  }
5659  }
5660  rChangeCurrRing(newRing);
5661  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5662  idDelete(&Gomega);
5663  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5664 #ifdef TIME_TEST
5665  to = clock();
5666 #endif
5667 #ifndef BUCHBERGER_ALG
5668  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5669  delete hilb_func;
5670 #else
5671  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5672 #endif
5673 #ifdef TIME_TEST
5674  tstd = tstd + clock() - to;
5675 #endif
5676  idSkipZeroes(M);
5677 #ifdef CHECK_IDEAL_MWALK
5678  if(printout > 2)
5679  {
5680  idString(M, "//** Mrwalk: M");
5681  }
5682 #endif
5683  //change the ring to baseRing
5684  rChangeCurrRing(baseRing);
5685  M1 = idrMoveR(M, newRing,currRing);
5686  idDelete(&M);
5687  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5688  idDelete(&Gomega1);
5689 #ifdef TIME_TEST
5690  to = clock();
5691 #endif
5692  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
5693  // where Gomega is a reduced Groebner basis w.r.t. the current ring
5694  F = MLifttwoIdeal(Gomega2, M1, G);
5695 #ifdef TIME_TEST
5696  tlift = tlift + clock() - to;
5697 #endif
5698 #ifdef CHECK_IDEAL_MWALK
5699  if(printout > 2)
5700  {
5701  idString(F,"//** Mrwalk: F");
5702  }
5703 #endif
5704  idDelete(&Gomega2);
5705  idDelete(&M1);
5706  rChangeCurrRing(newRing); // change the ring to newRing
5707  G = idrMoveR(F,baseRing,currRing);
5708  idDelete(&F);
5709  baseRing = currRing;
5710 #ifdef TIME_TEST
5711  to = clock();
5712  tstd = tstd + clock() - to;
5713 #endif
5714  idSkipZeroes(G);
5715 #ifdef CHECK_IDEAL_MWALK
5716  if(printout > 2)
5717  {
5718  idString(G,"//** Mrwalk: G");
5719  }
5720 #endif
5721 
5722  rChangeCurrRing(targetRing);
5723  G = idrMoveR(G,newRing,currRing);
5724 
5725  // test whether target cone is reached
5726  if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
5727  {
5728  baseRing = currRing;
5729  break;
5730  }
5731 
5732  rChangeCurrRing(newRing);
5733  G = idrMoveR(G,targetRing,currRing);
5734  baseRing = currRing;
5735 
5736  NEXT_VECTOR:
5737 #ifdef TIME_TEST
5738  to = clock();
5739 #endif
5740  next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5741 #ifdef TIME_TEST
5742  tnw = tnw + clock() - to;
5743 #endif
5744 
5745 #ifdef TIME_TEST
5746  to = clock();
5747 #endif
5748  Gomega = MwalkInitialForm(G, next_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5749 #ifdef TIME_TEST
5750  tif = tif + clock()-to; //time for computing initial form ideal
5751 #endif
5752 
5753  //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
5754  //polylength = lengthpoly(Gomega);
5755  if(lengthpoly(Gomega) > 0)
5756  {
5757  //there is a polynomial in Gomega with at least 3 monomials,
5758  //low-dimensional facet of the cone
5759  delete next_weight;
5760  if(target_M->length() == nV)
5761  {
5762  //iv_M = MivMatrixOrder(curr_weight);
5763  iv_M = MivMatrixOrderRefine(curr_weight,target_M);
5764  }
5765  else
5766  {
5767  iv_M = MivMatrixOrderRefine(curr_weight,target_M);
5768  }
5769 #ifdef TIME_TEST
5770  to = clock();
5771 #endif
5772  next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, pert_deg);
5773 #ifdef TIME_TEST
5774  tnw = tnw + clock() - to;
5775 #endif
5776  idDelete(&Gomega);
5777 #ifdef TIME_TEST
5778  to = clock();
5779 #endif
5780  Gomega = MwalkInitialForm(G, next_weight);
5781 #ifdef TIME_TEST
5782  tif = tif + clock()-to; //time for computing initial form ideal
5783 #endif
5784  delete iv_M;
5785  }
5786 
5787  // test whether target weight vector is reached
5788  if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)
5789  {
5790  baseRing = currRing;
5791  delete next_weight;
5792  break;
5793  }
5794  if(reduction ==0)
5795  {
5796  if(MivComp(curr_weight,next_weight)==1)
5797  {
5798  break;
5799  }
5800  }
5801 #ifdef PRINT_VECTORS
5802  if(printout > 0)
5803  {
5804  MivString(curr_weight, target_weight, next_weight);
5805  }
5806 #endif
5807 
5808  for(i=nV-1; i>=0; i--)
5809  {
5810  (*curr_weight)[i] = (*next_weight)[i];
5811  }
5812  delete next_weight;
5813  }
5814  baseRing = currRing;
5815  rChangeCurrRing(XXRing);
5816  ideal result = idrMoveR(G,baseRing,currRing);
5817  idDelete(&G);
5818  delete ivNull;
5819 #ifndef BUCHBERGER_ALG
5820  delete last_omega;
5821 #endif
5822  if(printout > 0)
5823  {
5824  Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
5825  }
5826 #ifdef TIME_TEST
5827  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5828  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5829  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5830 #endif
5831  si_opt_1 = save1; //set original options
5832  return(result);
5833 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:791
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2797
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
Definition: walk.cc:989
clock_t xtred
Definition: walk.cc:99
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:2221
int length() const
Definition: intvec.h:86
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2848
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:97
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
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:3436
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2235
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
Definition: walk.cc:4471
ideal idCopy(ideal A)
Definition: ideals.h:73
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static int isNolVector(intvec *hilb)
Definition: walk.cc:3050
static ideal MstdCC(ideal G)
Definition: walk.cc:938
int nstep
kstd2.cc
Definition: walk.cc:89
static int lengthpoly(ideal G)
Definition: walk.cc:3425
#define NULL
Definition: omList.c:10
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3084
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1082
static void idString(ideal L, const char *st)
Definition: walk.cc:432
clock_t xtlift
Definition: walk.cc:99
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2738
int BOOLEAN
Definition: auxiliary.h:131
void Werror(const char *fmt,...)
Definition: reporter.cc:199
return result
Definition: facAbsBiFact.cc:76
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
intvec* MSimpleIV ( intvec iv)
ideal Mwalk ( ideal  Go,
intvec orig_M,
intvec target_M,
ring  baseRing,
int  reduction,
int  printout 
)

Definition at line 5202 of file walk.cc.

5204 {
5205  // save current options
5206  BITSET save1 = si_opt_1;
5207  if(reduction == 0)
5208  {
5209  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5210  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5211  }
5212  Set_Error(FALSE);
5214  //BOOLEAN endwalks = FALSE;
5215 #ifdef TIME_TEST
5216  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5217  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5218  tinput = clock();
5219  clock_t tim;
5220 #endif
5221  nstep=0;
5222  int i,nwalk;
5223  int nV = baseRing->N;
5224 
5225  ideal Gomega, M, F, FF, Gomega1, Gomega2, M1;
5226  ring newRing;
5227  ring XXRing = baseRing;
5228  ring targetRing;
5229  intvec* ivNull = new intvec(nV);
5230  intvec* curr_weight = new intvec(nV);
5231  intvec* target_weight = new intvec(nV);
5232  intvec* exivlp = Mivlp(nV);
5233 /*
5234  intvec* tmp_weight = new intvec(nV);
5235  for(i=0; i<nV; i++)
5236  {
5237  (*tmp_weight)[i] = (*orig_M)[i];
5238  }
5239 */
5240  for(i=0; i<nV; i++)
5241  {
5242  (*curr_weight)[i] = (*orig_M)[i];
5243  (*target_weight)[i] = (*target_M)[i];
5244  }
5245 #ifndef BUCHBERGER_ALG
5246  intvec* hilb_func;
5247  // to avoid (1,0,...,0) as the target vector
5248  intvec* last_omega = new intvec(nV);
5249  for(i=nV-1; i>0; i--)
5250  {
5251  (*last_omega)[i] = 1;
5252  }
5253  (*last_omega)[0] = 10000;
5254 #endif
5256 #ifdef CHECK_IDEAL_MWALK
5257  if(printout > 2)
5258  {
5259  idString(Go,"//** Mwalk: Go");
5260  }
5261 #endif
5262 
5263  if(target_M->length() == nV)
5264  {
5265  // define the target ring
5266  targetRing = VMrDefault(target_weight);
5267  }
5268  else
5269  {
5270  targetRing = VMatrDefault(target_M);
5271  }
5272  if(orig_M->length() == nV)
5273  {
5274  // define a new ring with ordering "(a(curr_weight),lp)
5275  //newRing = VMrDefault(curr_weight);
5276  newRing=VMrRefine(target_weight, curr_weight);
5277  }
5278  else
5279  {
5280  newRing = VMatrRefine(target_M,curr_weight); //newRing = VMatrDefault(orig_M);
5281  }
5282  rChangeCurrRing(newRing);
5283  if(printout > 2)
5284  {
5285  Print("\n//** Mrwalk: Current ring r = %s;\n", rString(currRing));
5286  }
5287 #ifdef TIME_TEST
5288  to = clock();
5289 #endif
5290  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5291 #ifdef TIME_TEST
5292  tostd = clock()-to;
5293 #endif
5294 
5295  baseRing = currRing;
5296  nwalk = 0;
5297 
5298  while(1)
5299  {
5300  nwalk ++;
5301  nstep ++;
5302  //compute an initial form ideal of <G> w.r.t. "curr_vector"
5303 #ifdef TIME_TEST
5304  to = clock();
5305 #endif
5306  Gomega = MwalkInitialForm(G, curr_weight);
5307 #ifdef TIME_TEST
5308  tif = tif + clock()-to;
5309 #endif
5310 
5311 #ifdef CHECK_IDEAL_MWALK
5312  if(printout > 1)
5313  {
5314  idString(Gomega,"//** Mwalk: Gomega");
5315  }
5316 #endif
5317 
5318  if(reduction == 0)
5319  {
5320  FF = middleOfCone(G,Gomega);
5321  if(FF != NULL)
5322  {
5323  PrintS("middle of Cone");
5324  idDelete(&G);
5325  G = idCopy(FF);
5326  idDelete(&FF);
5327  goto NEXT_VECTOR;
5328  }
5329  }
5330 
5331 #ifndef BUCHBERGER_ALG
5332  if(isNolVector(curr_weight) == 0)
5333  {
5334  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5335  }
5336  else
5337  {
5338  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5339  }
5340 #endif
5341 
5342  if(nwalk == 1)
5343  {
5344  if(orig_M->length() == nV)
5345  {
5346  // define a new ring with ordering "(a(curr_weight),lp)
5347  //newRing = VMrDefault(curr_weight);
5348  newRing=VMrRefine(target_weight, curr_weight);
5349  }
5350  else
5351  {
5352  newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
5353  }
5354  }
5355  else
5356  {
5357  if(target_M->length() == nV)
5358  {
5359  //define a new ring with ordering "(a(curr_weight),lp)"
5360  //newRing = VMrDefault(curr_weight);
5361  newRing=VMrRefine(target_weight, curr_weight);
5362  }
5363  else
5364  {
5365  //define a new ring with matrix ordering
5366  newRing = VMatrRefine(target_M,curr_weight);
5367  }
5368  }
5369  rChangeCurrRing(newRing);
5370  if(printout > 2)
5371  {
5372  Print("\n// Current ring r = %s;\n", rString(currRing));
5373  }
5374  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5375  idDelete(&Gomega);
5376  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5377 #ifdef TIME_TEST
5378  to = clock();
5379 #endif
5380 #ifndef BUCHBERGER_ALG
5381  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5382  delete hilb_func;
5383 #else
5384  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5385 #endif
5386 #ifdef TIME_TEST
5387  tstd = tstd + clock() - to;
5388 #endif
5389  idSkipZeroes(M);
5390 #ifdef CHECK_IDEAL_MWALK
5391  if(printout > 2)
5392  {
5393  idString(M, "//** Mwalk: M");
5394  }
5395 #endif
5396  //change the ring to baseRing
5397  rChangeCurrRing(baseRing);
5398  M1 = idrMoveR(M, newRing,currRing);
5399  idDelete(&M);
5400  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5401  idDelete(&Gomega1);
5402 #ifdef TIME_TEST
5403  to = clock();
5404 #endif
5405  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
5406  // where Gomega is a reduced Groebner basis w.r.t. the current ring
5407  F = MLifttwoIdeal(Gomega2, M1, G);
5408 #ifdef TIME_TEST
5409  tlift = tlift + clock() - to;
5410 #endif
5411 #ifdef CHECK_IDEAL_MWALK
5412  if(printout > 2)
5413  {
5414  idString(F, "//** Mwalk: F");
5415  }
5416 #endif
5417  idDelete(&Gomega2);
5418  idDelete(&M1);
5419 
5420  rChangeCurrRing(newRing); // change the ring to newRing
5421  G = idrMoveR(F,baseRing,currRing);
5422  idDelete(&F);
5423  idSkipZeroes(G);
5424 
5425 #ifdef CHECK_IDEAL_MWALK
5426  if(printout > 2)
5427  {
5428  idString(G, "//** Mwalk: G");
5429  }
5430 #endif
5431 
5432  rChangeCurrRing(targetRing);
5433  G = idrMoveR(G,newRing,currRing);
5434  // test whether target cone is reached
5435  if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
5436  {
5437  baseRing = currRing;
5438  break;
5439  //endwalks = TRUE;
5440  }
5441 
5442  rChangeCurrRing(newRing);
5443  G = idrMoveR(G,targetRing,currRing);
5444  baseRing = currRing;
5445 
5446  NEXT_VECTOR:
5447 #ifdef TIME_TEST
5448  to = clock();
5449 #endif
5450  intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5451 #ifdef TIME_TEST
5452  tnw = tnw + clock() - to;
5453 #endif
5454 #ifdef PRINT_VECTORS
5455  if(printout > 0)
5456  {
5457  MivString(curr_weight, target_weight, next_weight);
5458  }
5459 #endif
5460  if(reduction ==0)
5461  {
5462  if(MivComp(curr_weight,next_weight)==1)
5463  {
5464  break;
5465  }
5466  }
5467  if(MivComp(target_weight,curr_weight) == 1)
5468  {
5469  break;
5470  }
5471 
5472  for(i=nV-1; i>=0; i--)
5473  {
5474  //(*tmp_weight)[i] = (*curr_weight)[i];
5475  (*curr_weight)[i] = (*next_weight)[i];
5476  }
5477  delete next_weight;
5478  }
5479  rChangeCurrRing(XXRing);
5480  ideal result = idrMoveR(G,baseRing,currRing);
5481  idDelete(&Go);
5482  idDelete(&G);
5483  //delete tmp_weight;
5484  delete ivNull;
5485  delete exivlp;
5486 #ifndef BUCHBERGER_ALG
5487  delete last_omega;
5488 #endif
5489 #ifdef TIME_TEST
5490  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5491  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5492  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5493 #endif
5494  if(printout > 0)
5495  {
5496  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
5497  }
5498  si_opt_1 = save1; //set original options
5499  return(result);
5500 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:791
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
char * rString(ring r)
Definition: ring.cc:644
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2797
clock_t xtred
Definition: walk.cc:99
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:2221
int length() const
Definition: intvec.h:86
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2848
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:97
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
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:3436
#define OPT_REDTAIL
Definition: options.h:86
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2235
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
clock_t xtstd
Definition: walk.cc:99
clock_t xtnw
Definition: walk.cc:99
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
ideal idCopy(ideal A)
Definition: ideals.h:73
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static int isNolVector(intvec *hilb)
Definition: walk.cc:3050
static ideal MstdCC(ideal G)
Definition: walk.cc:938
int nstep
kstd2.cc
Definition: walk.cc:89
#define NULL
Definition: omList.c:10
static ideal middleOfCone(ideal G, ideal Gomega)
Definition: walk.cc:3084
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1082
static void idString(ideal L, const char *st)
Definition: walk.cc:432
clock_t xtlift
Definition: walk.cc:99
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2738
return result
Definition: facAbsBiFact.cc:76
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
clock_t xtif
Definition: walk.cc:99
ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 767 of file walk.cc.

768 {
769  BOOLEAN nError = Overflow_Error;
771 
772  int i, nG = IDELEMS(G);
773  ideal Gomega = idInit(nG, 1);
774 
775  for(i=nG-1; i>=0; i--)
776  {
777  Gomega->m[i] = MpolyInitialForm(G->m[i], ivw);
778  }
779  if(Overflow_Error == FALSE)
780  {
781  Overflow_Error = nError;
782  }
783  return Gomega;
784 }
#define FALSE
Definition: auxiliary.h:140
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition: walk.cc:728
static TreeM * G
Definition: janet.cc:38
BOOLEAN Overflow_Error
Definition: walk.cc:97
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
int BOOLEAN
Definition: auxiliary.h:131
intvec* MwalkNextWeight ( intvec curr_weight,
intvec target_weight,
ideal  G 
)
ideal TranMImprovwalk ( ideal  Go,
intvec curr_weight,
intvec target_weight,
int  nP 
)

Definition at line 8288 of file walk.cc.

8289 {
8290 #ifdef TIME_TEST
8291  clock_t mtim = clock();
8292 #endif
8293  Set_Error(FALSE );
8295  //Print("// pSetm_Error = (%d)", ErrorCheck());
8296  //Print("\n// ring ro = %s;", rString(currRing));
8297 
8298  clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
8299 #ifdef TIME_TEST
8300  clock_t tinput = clock();
8301 #endif
8302  int nsteppert=0, i, nV = currRing->N, nwalk=0, npert_tmp=0;
8303  int *npert=(int*)omAlloc(2*nV*sizeof(int));
8304  ideal Gomega, M,F, G1, Gomega1, Gomega2, M1, F1;
8305  //ring endRing;
8306  ring newRing, oldRing, lpRing;
8307  intvec* next_weight;
8308  intvec* ivNull = new intvec(nV); //define (0,...,0)
8309  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
8310  intvec* iv_lp = Mivlp(nV); //define (1,0,...,0)
8311  ideal H0;
8312  //ideal H1;
8313  ideal H2, Glp;
8314  int nGB, endwalks = 0, nwalkpert=0, npertstep=0;
8315  intvec* Mlp = MivMatrixOrderlp(nV);
8316  intvec* vector_tmp = new intvec(nV);
8317 #ifndef BUCHBERGER_ALG
8318  intvec* hilb_func;
8319 #endif
8320  // to avoid (1,0,...,0) as the target vector
8321  intvec* last_omega = new intvec(nV);
8322  for(i=nV-1; i>0; i--)
8323  (*last_omega)[i] = 1;
8324  (*last_omega)[0] = 10000;
8325 
8326  // intvec* extra_curr_weight = new intvec(nV);
8327  intvec* target_weight = new intvec(nV);
8328  for(i=nV-1; i>=0; i--)
8329  (*target_weight)[i] = (*target_tmp)[i];
8330 
8331  ring XXRing = currRing;
8332  newRing = currRing;
8333 
8334  to=clock();
8335  // compute a red. GB w.r.t. the help ring
8336  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) = "dp"
8337  G = MstdCC(G);
8338  else
8339  {
8340  //rOrdStr(currRing) = (a(.c_w..),lp,C)
8341  if (rParameter(currRing) != NULL)
8342  DefRingPar(curr_weight);
8343  else
8344  rChangeCurrRing(VMrDefault(curr_weight));
8345  G = idrMoveR(G, XXRing,currRing);
8346  G = MstdCC(G);
8347  }
8348  tostd=clock()-to;
8349 
8350 #ifdef REPRESENTATION_OF_SIGMA
8351  ideal Gw = MwalkInitialForm(G, curr_weight);
8352 
8353  if(islengthpoly2(Gw)==1)
8354  {
8355  intvec* MDp;
8356  if(MivComp(curr_weight, iv_dp) == 1)
8357  MDp = MatrixOrderdp(nV); //MivWeightOrderlp(iv_dp);
8358  else
8359  MDp = MivWeightOrderlp(curr_weight);
8360 
8361  curr_weight = RepresentationMatrix_Dp(G, MDp);
8362 
8363  delete MDp;
8364 
8365  ring exring = currRing;
8366 
8367  if (rParameter(currRing) != NULL)
8368  DefRingPar(curr_weight);
8369  else
8370  rChangeCurrRing(VMrDefault(curr_weight));
8371  to=clock();
8372  Gw = idrMoveR(G, exring,currRing);
8373  G = MstdCC(Gw);
8374  Gw = NULL;
8375  tostd=tostd+clock()-to;
8376  //ivString(curr_weight,"rep. sigma");
8377  goto COMPUTE_NEW_VECTOR;
8378  }
8379 
8380  idDelete(&Gw);
8381  delete iv_dp;
8382 #endif
8383 
8384 
8385  while(1)
8386  {
8387  to=clock();
8388  /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
8389  Gomega = MwalkInitialForm(G, curr_weight);
8390  tif=tif+clock()-to;
8391 
8392 #ifndef BUCHBERGER_ALG
8393  if(isNolVector(curr_weight) == 0)
8394  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
8395  else
8396  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
8397 #endif // BUCHBERGER_ALG
8398 
8399  oldRing = currRing;
8400 
8401  /* define a new ring that its ordering is "(a(curr_weight),lp) */
8402  if (rParameter(currRing) != NULL)
8403  DefRingPar(curr_weight);
8404  else
8405  rChangeCurrRing(VMrDefault(curr_weight));
8406 
8407  newRing = currRing;
8408  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
8409 
8410  to=clock();
8411  /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
8412 #ifdef BUCHBERGER_ALG
8413  M = MstdhomCC(Gomega1);
8414 #else
8415  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
8416  delete hilb_func;
8417 #endif // BUCHBERGER_ALG
8418  tstd=tstd+clock()-to;
8419 
8420  /* change the ring to oldRing */
8421  rChangeCurrRing(oldRing);
8422  M1 = idrMoveR(M, newRing,currRing);
8423  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
8424 
8425  to=clock();
8426  /* compute a representation of the generators of submod (M)
8427  with respect to those of mod (Gomega).
8428  Gomega is a reduced Groebner basis w.r.t. the current ring */
8429  F = MLifttwoIdeal(Gomega2, M1, G);
8430  tlift=tlift+clock()-to;
8431 
8432  idDelete(&M1);
8433  idDelete(&Gomega2);
8434  idDelete(&G);
8435 
8436  /* change the ring to newRing */
8437  rChangeCurrRing(newRing);
8438  F1 = idrMoveR(F, oldRing,currRing);
8439 
8440  to=clock();
8441  /* reduce the Groebner basis <G> w.r.t. new ring */
8442  G = kInterRedCC(F1, NULL);
8443  tred=tred+clock()-to;
8444  idDelete(&F1);
8445 
8446 
8447  COMPUTE_NEW_VECTOR:
8448  newRing = currRing;
8449  nwalk++;
8450  nwalkpert++;
8451  to=clock();
8452  // compute a next weight vector
8453  next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
8454  tnw=tnw+clock()-to;
8455 #ifdef PRINT_VECTORS
8456  MivString(curr_weight, target_weight, next_weight);
8457 #endif
8458 
8459  /* check whether the computed intermediate weight vector is in
8460  the correct cone; sometimes it is very big e.g. s7, cyc7.
8461  If it is NOT in the correct cone, then compute directly
8462  a reduced Groebner basis with respect to the lexicographic ordering
8463  for the known Groebner basis that it is computed in the last step.
8464  */
8465  //if(test_w_in_ConeCC(G, next_weight) != 1)
8466  if(Overflow_Error == TRUE)
8467  {
8468  OMEGA_OVERFLOW_TRAN_NEW:
8469  //Print("\n// takes %d steps!", nwalk-1);
8470  //Print("\n//ring lastRing = %s;", rString(currRing));
8471 #ifdef TEST_OVERFLOW
8472  goto BE_FINISH;
8473 #endif
8474 /*
8475 #ifdef CHECK_IDEAL_MWALK
8476  idElements(G, "G");
8477  //headidString(G, "G");
8478 #endif
8479 */
8480  if(MivSame(target_tmp, iv_lp) == 1)
8481  if (rParameter(currRing) != NULL)
8482  DefRingParlp();
8483  else
8484  VMrDefaultlp();
8485  else
8486  if (rParameter(currRing) != NULL)
8487  DefRingPar(target_tmp);
8488  else
8489  rChangeCurrRing(VMrDefault(target_tmp));
8490 
8491  lpRing = currRing;
8492  G1 = idrMoveR(G, newRing,currRing);
8493 
8494  to=clock();
8495  /*apply kStd or LastGB to compute a lex. red. Groebner basis of <G>*/
8496  if(nP == 0 || MivSame(target_tmp, iv_lp) == 0){
8497  //Print("\n\n// calls \"std in ring r_%d = %s;", nwalk, rString(currRing));
8498  G = MstdCC(G1);//no result for qnt1
8499  }
8500  else {
8501  rChangeCurrRing(newRing);
8502  G1 = idrMoveR(G1, lpRing,currRing);
8503 
8504  //Print("\n\n// calls \"LastGB\" (%d) to compute a GB", nV-1);
8505  G = LastGB(G1, curr_weight, nV-1); //no result for kats7
8506 
8507  rChangeCurrRing(lpRing);
8508  G = idrMoveR(G, newRing,currRing);
8509  }
8510  textra=clock()-to;
8511  npert[endwalks]=nwalk-npert_tmp;
8512  npert_tmp = nwalk;
8513  endwalks ++;
8514  break;
8515  }
8516 
8517  /* check whether the computed Groebner basis is really a Groebner basis.
8518  If not, we perturb the target vector with the maximal "perturbation"
8519  degree.*/
8520  if(MivComp(next_weight, target_weight) == 1 ||
8521  MivComp(next_weight, curr_weight) == 1 )
8522  {
8523  //Print("\n//ring r_%d = %s;", nwalk, rString(currRing));
8524 
8525 
8526  //compute the number of perturbations and its step
8527  npert[endwalks]=nwalk-npert_tmp;
8528  npert_tmp = nwalk;
8529 
8530  endwalks ++;
8531 
8532  /*it is very important if the walk only uses one step, e.g. Fate, liu*/
8533  if(endwalks == 1 && MivComp(next_weight, curr_weight) == 1){
8534  rChangeCurrRing(XXRing);
8535  G = idrMoveR(G, newRing,currRing);
8536  goto FINISH;
8537  }
8538  H0 = id_Head(G,currRing);
8539 
8540  if(MivSame(target_tmp, iv_lp) == 1)
8541  if (rParameter(currRing) != NULL)
8542  DefRingParlp();
8543  else
8544  VMrDefaultlp();
8545  else
8546  if (rParameter(currRing) != NULL)
8547  DefRingPar(target_tmp);
8548  else
8549  rChangeCurrRing(VMrDefault(target_tmp));
8550 
8551  lpRing = currRing;
8552  Glp = idrMoveR(G, newRing,currRing);
8553  H2 = idrMoveR(H0, newRing,currRing);
8554 
8555  /* Apply Lemma 2.2 in Collart et. al (1997) to check whether
8556  cone(k-1) is equal to cone(k) */
8557  nGB = 1;
8558  for(i=IDELEMS(Glp)-1; i>=0; i--)
8559  {
8560  poly t;
8561  if((t=pSub(pHead(Glp->m[i]), pCopy(H2->m[i]))) != NULL)
8562  {
8563  pDelete(&t);
8564  idDelete(&H2);//5.5.02
8565  nGB = 0; //i.e. Glp is no reduced Groebner basis
8566  break;
8567  }
8568  pDelete(&t);
8569  }
8570 
8571  idDelete(&H2);//5.5.02
8572 
8573  if(nGB == 1)
8574  {
8575  G = Glp;
8576  Glp = NULL;
8577  break;
8578  }
8579 
8580  /* perturb the target weight vector, if the vector target_tmp
8581  stays in many cones */
8582  poly p;
8583  BOOLEAN plength3 = FALSE;
8584  for(i=IDELEMS(Glp)-1; i>=0; i--)
8585  {
8586  p = MpolyInitialForm(Glp->m[i], target_tmp);
8587  if(p->next != NULL &&
8588  p->next->next != NULL &&
8589  p->next->next->next != NULL)
8590  {
8592 
8593  for(i=0; i<nV; i++)
8594  (*vector_tmp)[i] = (*target_weight)[i];
8595 
8596  delete target_weight;
8597  target_weight = MPertVectors(Glp, Mlp, nV);
8598 
8599  if(MivComp(vector_tmp, target_weight)==1)
8600  {
8601  //PrintS("\n// The old and new representaion vector are the same!!");
8602  G = Glp;
8603  newRing = currRing;
8604  goto OMEGA_OVERFLOW_TRAN_NEW;
8605  }
8606 
8607  if(Overflow_Error == TRUE)
8608  {
8609  rChangeCurrRing(newRing);
8610  G = idrMoveR(Glp, lpRing,currRing);
8611  goto OMEGA_OVERFLOW_TRAN_NEW;
8612  }
8613 
8614  plength3 = TRUE;
8615  pDelete(&p);
8616  break;
8617  }
8618  pDelete(&p);
8619  }
8620 
8621  if(plength3 == FALSE)
8622  {
8623  rChangeCurrRing(newRing);
8624  G = idrMoveR(Glp, lpRing,currRing);
8625  goto TRAN_LIFTING;
8626  }
8627 
8628 
8629  npertstep = nwalk;
8630  nwalkpert = 1;
8631  nsteppert ++;
8632 
8633  /*
8634  Print("\n// Subroutine needs (%d) steps.", nwalk);
8635  idElements(Glp, "last G in walk:");
8636  PrintS("\n// ****************************************");
8637  Print("\n// Perturb the original target vector (%d): ", nsteppert);
8638  ivString(target_weight, "new target");
8639  PrintS("\n// ****************************************\n");
8640  */
8641  rChangeCurrRing(newRing);
8642  G = idrMoveR(Glp, lpRing,currRing);
8643 
8644  delete next_weight;
8645 
8646  //Print("\n// ring rNEW = %s;", rString(currRing));
8647  goto COMPUTE_NEW_VECTOR;
8648  }
8649 
8650  TRAN_LIFTING:
8651  for(i=nV-1; i>=0; i--)
8652  (*curr_weight)[i] = (*next_weight)[i];
8653 
8654  delete next_weight;
8655  }//while
8656 #ifdef TEST_OVERFLOW
8657  BE_FINISH:
8658 #endif
8659  rChangeCurrRing(XXRing);
8660  G = idrMoveR(G, lpRing,currRing);
8661 
8662  FINISH:
8663  delete ivNull;
8664  delete next_weight;
8665  delete iv_lp;
8666  omFree(npert);
8667 /*
8668 #ifdef TIME_TEST
8669  Print("\n// Computation took %d steps and %.2f sec",
8670  nwalk, ((double) (clock()-mtim)/1000000));
8671 
8672  TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
8673 
8674  // Print("\n// pSetm_Error = (%d)", ErrorCheck());
8675  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8676 #endif
8677 */
8678  return(G);
8679 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1728
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1805
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1442
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition: walk.cc:3150
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition: walk.cc:728
#define TRUE
Definition: auxiliary.h:144
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:2221
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:899
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:95
#define omAlloc(size)
Definition: omAllocDecl.h:210
BOOLEAN Overflow_Error
Definition: walk.cc:97
static void VMrDefaultlp(void)
Definition: walk.cc:2905
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:100
Definition: intvec.h:16
#define pSub(a, b)
Definition: polys.h:258
static int islengthpoly2(ideal G)
Definition: walk.cc:3462
#define omFree(addr)
Definition: omAllocDecl.h:261
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:2235
int i
Definition: cfEzgcd.cc:123
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1094
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL ...
Definition: polys.h:67
#define IDELEMS(i)
Definition: simpleideals.h:24
static ideal MstdhomCC(ideal G)
Definition: walk.cc:953
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2995
static int isNolVector(intvec *hilb)
Definition: walk.cc:3050
static ideal MstdCC(ideal G)
Definition: walk.cc:938
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2946
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:276
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
#define pDelete(p_ptr)
Definition: polys.h:157
intvec * MivUnit(int nV)
Definition: walk.cc:1502
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
polyrec * poly
Definition: hilb.h:10
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:767
int BOOLEAN
Definition: auxiliary.h:131
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1407
intvec * Mivlp(int nR)
Definition: walk.cc:1028
static ring VMrDefault(intvec *va)
Definition: walk.cc:2687
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
intvec* TranMPertVectorslp ( ideal  G)