Functions
walk.h File Reference
#include <kernel/structs.h>

Go to the source code of this file.

Functions

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

Function Documentation

§ M3ivSame()

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

Definition at line 921 of file walk.cc.

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

§ MAltwalk1()

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

Definition at line 9473 of file walk.cc.

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

§ MAltwalk2()

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

Definition at line 4238 of file walk.cc.

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

§ Mfpertvector()

intvec* Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1519 of file walk.cc.

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

§ Mfrwalk()

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

Definition at line 8107 of file walk.cc.

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

§ Mfwalk()

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

Definition at line 7926 of file walk.cc.

7928 {
7929  BITSET save1 = si_opt_1; // save current options
7930  if(reduction == 0)
7931  {
7932  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
7933  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
7934  }
7935  Set_Error(FALSE);
7937  //Print("// pSetm_Error = (%d)", ErrorCheck());
7938  //Print("\n// ring ro = %s;", rString(currRing));
7939 
7940  nnflow = 0;
7941  Xngleich = 0;
7942  Xcall = 0;
7943 #ifdef TIME_TEST
7944  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
7945  xftinput = clock();
7946 #endif
7947  ring oldRing = currRing;
7948  int i, nV = currRing->N;
7949  XivNull = new intvec(nV);
7950  Xivinput = ivtarget;
7951  ngleich = 0;
7952 #ifdef TIME_TEST
7953  to=clock();
7954 #endif
7955  ideal I = MstdCC(G);
7956  G = NULL;
7957 #ifdef TIME_TEST
7958  xftostd=clock()-to;
7959 #endif
7960  Xsigma = ivstart;
7961 
7962  Xnlev=nV;
7963 
7964 #ifdef FIRST_STEP_FRACTAL
7965  ideal Gw = MwalkInitialForm(I, ivstart);
7966  for(i=IDELEMS(Gw)-1; i>=0; i--)
7967  {
7968  if((Gw->m[i]!=NULL) // len >=0
7969  && (Gw->m[i]->next!=NULL) // len >=1
7970  && (Gw->m[i]->next->next!=NULL)) // len >=2
7971  {
7972  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
7973  intvec* Mdp;
7974  if(ivstart->length() == nV)
7975  {
7976  if(MivSame(ivstart, iv_dp) != 1)
7977  Mdp = MivWeightOrderdp(ivstart);
7978  else
7979  Mdp = MivMatrixOrderdp(nV);
7980  }
7981  else
7982  {
7983  Mdp = ivstart;
7984  }
7985 
7986  Xsigma = Mfpertvector(I, Mdp);
7988 
7989  delete Mdp;
7990  delete iv_dp;
7991  break;
7992  }
7993  }
7994  idDelete(&Gw);
7995 #endif
7996 
7997  ideal I1;
7998  intvec* Mlp;
7999  Xivlp = Mivlp(nV);
8000 
8001  if(ivtarget->length() == nV)
8002  {
8003  if(MivComp(ivtarget, Xivlp) != 1)
8004  {
8005  if (rParameter(currRing) != NULL)
8006  DefRingPar(ivtarget);
8007  else
8008  rChangeCurrRing(VMrDefault(ivtarget));
8009 
8010  I1 = idrMoveR(I, oldRing,currRing);
8011  Mlp = MivWeightOrderlp(ivtarget);
8012  Xtau = Mfpertvector(I1, Mlp);
8013  }
8014  else
8015  {
8016  if (rParameter(currRing) != NULL)
8017  DefRingParlp();
8018  else
8019  VMrDefaultlp();
8020 
8021  I1 = idrMoveR(I, oldRing,currRing);
8022  Mlp = MivMatrixOrderlp(nV);
8023  Xtau = Mfpertvector(I1, Mlp);
8024  }
8025  }
8026  else
8027  {
8028  rChangeCurrRing(VMatrDefault(ivtarget));
8029  I1 = idrMoveR(I,oldRing,currRing);
8030  Mlp = ivtarget;
8031  Xtau = Mfpertvector(I1, Mlp);
8032  }
8033  delete Mlp;
8035 
8036  //ivString(Xsigma, "Xsigma");
8037  //ivString(Xtau, "Xtau");
8038 
8039  id_Delete(&I, oldRing);
8040  ring tRing = currRing;
8041  if(ivtarget->length() == nV)
8042  {
8043 /*
8044  if (rParameter(currRing) != NULL)
8045  DefRingPar(ivstart);
8046  else
8047  rChangeCurrRing(VMrDefault(ivstart));
8048 */
8049  rChangeCurrRing(VMrRefine(ivtarget,ivstart));
8050  }
8051  else
8052  {
8053  //rChangeCurrRing(VMatrDefault(ivstart));
8054  rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
8055  }
8056 
8057  I = idrMoveR(I1,tRing,currRing);
8058 #ifdef TIME_TEST
8059  to=clock();
8060 #endif
8061  ideal J = MstdCC(I);
8062  idDelete(&I);
8063 #ifdef TIME_TEST
8064  xftostd=xftostd+clock()-to;
8065 #endif
8066  ideal resF;
8067  ring helpRing = currRing;
8068 
8069  J = rec_fractal_call(J,1,ivtarget,reduction,printout);
8070  //idString(J,"//** Mfwalk: J");
8071  rChangeCurrRing(oldRing);
8072  //Print("\n//Mfwalk: (2)\n");
8073  resF = idrMoveR(J, helpRing,currRing);
8074  //Print("\n//Mfwalk: (3)\n");
8075  idSkipZeroes(resF);
8076  //Print("\n//Mfwalk: (4)\n");
8077 
8078  si_opt_1 = save1; //set original options, e. g. option(RedSB)
8079  delete Xivlp;
8080  //delete Xsigma;
8081  delete Xtau;
8082  delete XivNull;
8083  //Print("\n//Mfwalk: (5)\n");
8084 #ifdef TIME_TEST
8085  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
8086  xtlift, xtred, xtnw);
8087 
8088 
8089  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
8090  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
8091  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
8092 #endif
8093  //Print("\n//Mfwalk: (6)\n");
8094  //idString(resF,"//** Mfwalk: resF");
8095  return(idCopy(resF));
8096 }
#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:1519
intvec * Xivlp
Definition: walk.cc:4468
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1806
#define idDelete(H)
delete an ideal
Definition: ideals.h:31
intvec * Xivinput
Definition: walk.cc:4467
int nnflow
Definition: walk.cc:6842
int ngleich
Definition: walk.cc:4463
int Xngleich
Definition: walk.cc:6844
#define FALSE
Definition: auxiliary.h:97
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1443
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2798
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:98
intvec * Xsigma
Definition: walk.cc:4464
int Xnlev
Definition: walk.cc:1518
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:900
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1463
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:613
intvec * Xtau
Definition: walk.cc:4465
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2849
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:18
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2906
int Xcall
Definition: walk.cc:6843
clock_t xftostd
Definition: walk.cc:99
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
clock_t to
Definition: walk.cc:99
Definition: intvec.h:14
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:99
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:98
clock_t xtnw
Definition: walk.cc:98
#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:6849
ideal idCopy(ideal A)
Definition: ideals.h:62
void rChangeCurrRing(ring r)
Definition: polys.cc:12
static void DefRingParlp(void)
Definition: walk.cc:2996
static ideal MstdCC(ideal G)
Definition: walk.cc:939
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2947
int length() const
Definition: intvec.h:86
void reduction(LList *sPolyList, CListOld *critPairs, LList *gPrev, RList *rules, LTagList *lTag, RTagList *rTag, ideal gbPrev, PList *rejectedGBList, int plus)
Definition: f5gb.cc:1093
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1424
clock_t xtlift
Definition: walk.cc:98
intvec * MivUnit(int nV)
Definition: walk.cc:1503
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:768
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2739
clock_t xtextra
Definition: walk.cc:99
intvec * XivNull
Definition: walk.cc:6825
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1408
intvec * Mivlp(int nR)
Definition: walk.cc:1029
static ring VMrDefault(intvec *va)
Definition: walk.cc:2688
clock_t xtif
Definition: walk.cc:98

§ MidLift()

ideal MidLift ( ideal  Gomega,
ideal  M 
)

§ Mivdp()

intvec* Mivdp ( int  nR)

Definition at line 1014 of file walk.cc.

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

§ Mivlp()

intvec* Mivlp ( int  nR)

Definition at line 1029 of file walk.cc.

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

§ MivMatrixOrder()

intvec* MivMatrixOrder ( intvec iv)

Definition at line 970 of file walk.cc.

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

§ MivMatrixOrderdp()

intvec* MivMatrixOrderdp ( int  iv)

Definition at line 1424 of file walk.cc.

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

§ MivMatrixOrderlp()

intvec* MivMatrixOrderlp ( int  nV)

Definition at line 1408 of file walk.cc.

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

§ Mivperttarget()

intvec* Mivperttarget ( ideal  G,
int  ndeg 
)

§ MivSame()

int MivSame ( intvec u,
intvec v 
)

Definition at line 900 of file walk.cc.

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

§ MivUnit()

intvec* MivUnit ( int  nV)

Definition at line 1503 of file walk.cc.

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

§ MivWeightOrderdp()

intvec* MivWeightOrderdp ( intvec ivstart)

Definition at line 1463 of file walk.cc.

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

§ MivWeightOrderlp()

intvec* MivWeightOrderlp ( intvec ivstart)

Definition at line 1443 of file walk.cc.

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

§ MkInterRedNextWeight()

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

Definition at line 2578 of file walk.cc.

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

§ MLiftLmalG()

ideal MLiftLmalG ( ideal  L,
ideal  G 
)

§ MLiftLmalGMin()

ideal MLiftLmalGMin ( ideal  L,
ideal  G 
)

§ MLiftLmalGNew()

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

§ MPertNextWeight()

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

§ MPertVectors()

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

Definition at line 1095 of file walk.cc.

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

§ MPertVectorslp()

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

Definition at line 1306 of file walk.cc.

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

§ Mprwalk()

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

Definition at line 6286 of file walk.cc.

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

§ Mpwalk()

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

Definition at line 5851 of file walk.cc.

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

§ Mrwalk()

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

Definition at line 5506 of file walk.cc.

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

§ MSimpleIV()

intvec* MSimpleIV ( intvec iv)

§ Mwalk()

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

Definition at line 5205 of file walk.cc.

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

§ MwalkInitialForm()

ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 768 of file walk.cc.

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

§ MwalkNextWeight()

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

§ TranMImprovwalk()

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

Definition at line 8291 of file walk.cc.

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

§ TranMPertVectorslp()

intvec* TranMPertVectorslp ( ideal  G)