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

Go to the source code of this file.

Functions

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

Function Documentation

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

Definition at line 922 of file walk.cc.

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

Definition at line 9474 of file walk.cc.

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

Definition at line 4239 of file walk.cc.

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

Definition at line 1520 of file walk.cc.

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

Definition at line 8108 of file walk.cc.

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

Definition at line 7927 of file walk.cc.

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

Definition at line 1015 of file walk.cc.

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

Definition at line 1030 of file walk.cc.

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

Definition at line 971 of file walk.cc.

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

Definition at line 1425 of file walk.cc.

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

Definition at line 1409 of file walk.cc.

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

Definition at line 901 of file walk.cc.

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

Definition at line 1504 of file walk.cc.

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

Definition at line 1464 of file walk.cc.

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

Definition at line 1444 of file walk.cc.

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

Definition at line 2579 of file walk.cc.

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

Definition at line 1096 of file walk.cc.

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

Definition at line 1307 of file walk.cc.

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

Definition at line 6287 of file walk.cc.

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

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

Definition at line 5507 of file walk.cc.

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

Definition at line 5206 of file walk.cc.

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

Definition at line 769 of file walk.cc.

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

Definition at line 8292 of file walk.cc.

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