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)
 
ideal Mrwalk (ideal Go, intvec *curr_weight, intvec *target_weight, int weight_rad, int pert_deg, ring baseRing)
 
ideal Mpwalk (ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP)
 
ideal Mprwalk (ideal Go, intvec *curr_weight, intvec *target_weight, int weight_rad, int op_deg, int tp_deg, ring baseRing)
 
ideal Mfwalk (ideal G, intvec *ivstart, intvec *ivtarget)
 
ideal Mfrwalk (ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad)
 
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 889 of file walk.cc.

890 {
891  assume(temp->length() == u->length() && u->length() == v->length());
892 
893  if((MivSame(temp, u)) == 1)
894  {
895  return 0;
896  }
897  if((MivSame(temp, v)) == 1)
898  {
899  return 1;
900  }
901  return 2;
902 }
int length() const
Definition: intvec.h:86
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
#define assume(x)
Definition: mod2.h:405
ideal MAltwalk1 ( ideal  G,
int  op,
int  tp,
intvec curr_weight,
intvec target_weight 
)

Definition at line 8446 of file walk.cc.

8448 {
8449  Set_Error(FALSE );
8451 #ifdef TIME_TEST
8452  BOOLEAN nOverflow_Error = FALSE;
8453 #endif
8454  // Print("// pSetm_Error = (%d)", ErrorCheck());
8455 
8456  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
8457  xftinput = clock();
8458  clock_t tostd, tproc;
8459 
8460  nstep = 0;
8461  int i, nV = currRing->N;
8462  int nwalk=0, endwalks=0;
8463  int op_tmp = op_deg;
8464  ideal Gomega, M, F, G, Gomega1, Gomega2, M1, F1;
8465  ring newRing, oldRing;
8466  intvec* next_weight;
8467  intvec* iv_M_dp;
8468  intvec* ivNull = new intvec(nV);
8469  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
8470  intvec* exivlp = Mivlp(nV);
8471  //intvec* extra_curr_weight = new intvec(nV);
8472 #ifndef BUCHBERGER_ALG
8473  intvec* hilb_func;
8474 #endif
8475  intvec* cw_tmp = curr_weight;
8476 
8477  // to avoid (1,0,...,0) as the target vector
8478  intvec* last_omega = new intvec(nV);
8479  for(i=nV-1; i>0; i--)
8480  {
8481  (*last_omega)[i] = 1;
8482  }
8483  (*last_omega)[0] = 10000;
8484 
8485  ring XXRing = currRing;
8486 
8487  to=clock();
8488  /* compute a pertubed weight vector of the original weight vector.
8489  The perturbation degree is recursive decrease until that vector
8490  stays inn the correct cone. */
8491  while(1)
8492  {
8493  if(Overflow_Error == FALSE)
8494  {
8495  if(MivComp(curr_weight, iv_dp) == 1)
8496  {
8497  //rOrdStr(currRing) = "dp"
8498  if(op_tmp == op_deg)
8499  {
8500  G = MstdCC(Go);
8501  if(op_deg != 1)
8502  {
8503  iv_M_dp = MivMatrixOrderdp(nV);
8504  }
8505  }
8506  }
8507  }
8508  else
8509  {
8510  if(op_tmp == op_deg)
8511  {
8512  //rOrdStr(currRing) = (a(...),lp,C)
8513  if (rParameter(currRing) != NULL)
8514  {
8515  DefRingPar(cw_tmp);
8516  }
8517  else
8518  {
8519  rChangeCurrRing(VMrDefault(cw_tmp)); // Aenderung 16
8520  }
8521  G = idrMoveR(Go, XXRing,currRing);
8522  G = MstdCC(G);
8523  if(op_deg != 1)
8524  iv_M_dp = MivMatrixOrder(cw_tmp);
8525  }
8526  }
8528  if(op_deg != 1)
8529  {
8530  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
8531  }
8532  else
8533  {
8534  curr_weight = cw_tmp;
8535  break;
8536  }
8537  if(Overflow_Error == FALSE)
8538  {
8539  break;
8540  }
8541  Overflow_Error = TRUE;
8542  op_deg --;
8543  }
8544  tostd=clock()-to;
8545 
8546  if(op_tmp != 1 )
8547  delete iv_M_dp;
8548  delete iv_dp;
8549 
8550  if(currRing->order[0] == ringorder_a)
8551  goto NEXT_VECTOR;
8552 
8553  while(1)
8554  {
8555  nwalk ++;
8556  nstep ++;
8557 
8558  to = clock();
8559  // compute an initial form ideal of <G> w.r.t. "curr_vector"
8560  Gomega = MwalkInitialForm(G, curr_weight);
8561  xtif=xtif+clock()-to;
8562 #if 0
8563  if(Overflow_Error == TRUE)
8564  {
8565  for(i=nV-1; i>=0; i--)
8566  (*curr_weight)[i] = (*extra_curr_weight)[i];
8567  delete extra_curr_weight;
8568 
8569  newRing = currRing;
8570  goto MSTD_ALT1;
8571  }
8572 #endif
8573 #ifndef BUCHBERGER_ALG
8574  if(isNolVector(curr_weight) == 0)
8575  {
8576  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
8577  }
8578  else
8579  {
8580  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
8581  }
8582 #endif // BUCHBERGER_ALG
8583 
8584  oldRing = currRing;
8585 
8586  // define a new ring which ordering is "(a(curr_weight),lp)
8587  if (rParameter(currRing) != NULL)
8588  {
8589  DefRingPar(curr_weight);
8590  }
8591  else
8592  {
8593  rChangeCurrRing(VMrDefault(curr_weight)); // Aenderung 17
8594  }
8595  newRing = currRing;
8596  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
8597 
8598  to=clock();
8599  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
8600 #ifdef BUCHBERGER_ALG
8601  M = MstdhomCC(Gomega1);
8602 #else
8603  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
8604  delete hilb_func;
8605 #endif // BUCHBERGER_ALG
8606  xtstd=xtstd+clock()-to;
8607 
8608  // change the ring to oldRing
8609  rChangeCurrRing(oldRing);
8610  M1 = idrMoveR(M, newRing,currRing);
8611  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
8612 
8613  to=clock();
8614  // compute a reduced Groebner basis of <G> w.r.t. "newRing" by the lifting process
8615  F = MLifttwoIdeal(Gomega2, M1, G);
8616  xtlift=xtlift+clock()-to;
8617 
8618  idDelete(&M1);
8619  idDelete(&Gomega2);
8620  idDelete(&G);
8621 
8622  // change the ring to newRing
8623  rChangeCurrRing(newRing);
8624  F1 = idrMoveR(F, oldRing,currRing);
8625 
8626  to=clock();
8627  // reduce the Groebner basis <G> w.r.t. new ring
8628  G = kInterRedCC(F1, NULL);
8629  xtred=xtred+clock()-to;
8630  idDelete(&F1);
8631 
8632  if(endwalks == 1)
8633  {
8634  break;
8635  }
8636  NEXT_VECTOR:
8637  to=clock();
8638  // compute a next weight vector
8639  next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
8640  xtnw=xtnw+clock()-to;
8641 #ifdef PRINT_VECTORS
8642  MivString(curr_weight, target_weight, next_weight);
8643 #endif
8644 
8645  if(Overflow_Error == TRUE)
8646  {
8647  newRing = currRing;
8648 
8649  if (rParameter(currRing) != NULL)
8650  {
8651  DefRingPar(target_weight);
8652  }
8653  else
8654  {
8655  rChangeCurrRing(VMrDefault(target_weight)); // Aenderung 18
8656  }
8657  F1 = idrMoveR(G, newRing,currRing);
8658  G = MstdCC(F1);
8659  idDelete(&F1);
8660  newRing = currRing;
8661  break; //for while
8662  }
8663 
8664 
8665  /* G is the wanted Groebner basis if next_weight == curr_weight */
8666  if(MivComp(next_weight, ivNull) == 1)
8667  {
8668  newRing = currRing;
8669  delete next_weight;
8670  break; //for while
8671  }
8672 
8673  if(MivComp(next_weight, target_weight) == 1)
8674  {
8675  if(tp_deg == 1 || MivSame(target_weight, exivlp) == 0)
8676  endwalks = 1;
8677  else
8678  {
8679  // MSTD_ALT1:
8680 #ifdef TIME_TEST
8681  nOverflow_Error = Overflow_Error;
8682 #endif
8683  tproc = clock()-xftinput;
8684 
8685  //Print("\n// main routine takes %d steps and calls \"Mpwalk\" (1,%d):", nwalk, tp_deg);
8686 
8687  // compute the red. GB of <G> w.r.t. the lex order by the "recursive-modified" perturbation walk alg (1,tp_deg)
8688  G = Mpwalk_MAltwalk1(G, curr_weight, tp_deg);
8689  delete next_weight;
8690  break; // for while
8691  }
8692  }
8693 
8694  //NOT Changed, to free memory
8695  for(i=nV-1; i>=0; i--)
8696  {
8697  //(*extra_curr_weight)[i] = (*curr_weight)[i];
8698  (*curr_weight)[i] = (*next_weight)[i];
8699  }
8700  delete next_weight;
8701  }//while
8702 
8703  rChangeCurrRing(XXRing);
8704  ideal result = idrMoveR(G, newRing,currRing);
8705  id_Delete(&G, newRing);
8706 
8707  delete ivNull;
8708  if(op_deg != 1 )
8709  {
8710  delete curr_weight;
8711  }
8712  delete exivlp;
8713 #ifdef TIME_TEST
8714 
8715  Print("\n// \"Main procedure\" took %d steps, %.2f sec. and Overflow_Error(%d)",
8716  nwalk, ((double) tproc)/1000000, nOverflow_Error);
8717 
8718  TimeStringFractal(xftinput, tostd, xtif, xtstd,xtextra, xtlift, xtred, xtnw);
8719 
8720  Print("\n// pSetm_Error = (%d)", ErrorCheck());
8721  Print("\n// Overflow_Error? (%d)", Overflow_Error);
8722  Print("\n// Awalk1 took %d steps.\n", nstep);
8723 #endif
8724  return(result);
8725 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
BOOLEAN ErrorCheck()
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:938
#define Print
Definition: emacs.cc:83
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#define FALSE
Definition: auxiliary.h:140
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:98
#define TRUE
Definition: auxiliary.h:144
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:99
static ideal Mpwalk_MAltwalk1(ideal Go, intvec *curr_weight, int tp_deg)
Definition: walk.cc:7990
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:98
clock_t xtnw
Definition: walk.cc:98
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1061
static ideal MstdhomCC(ideal G)
Definition: walk.cc:922
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static ideal MstdCC(ideal G)
Definition: walk.cc:907
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2811
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:275
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1397
clock_t xtlift
Definition: walk.cc:98
intvec * MivUnit(int nV)
Definition: walk.cc:1476
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:736
int BOOLEAN
Definition: auxiliary.h:131
clock_t xtextra
Definition: walk.cc:99
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
return result
Definition: facAbsBiFact.cc:76
intvec * Mivlp(int nR)
Definition: walk.cc:995
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
clock_t xtif
Definition: walk.cc:98
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2248
ideal MAltwalk2 ( ideal  G,
intvec curr_weight,
intvec target_weight 
)

Definition at line 4077 of file walk.cc.

4078 {
4079  Set_Error(FALSE);
4081  //BOOLEAN nOverflow_Error = FALSE;
4082  //Print("// pSetm_Error = (%d)", ErrorCheck());
4083 
4084  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
4085  xftinput = clock();
4086  clock_t tostd, tproc;
4087 
4088  nstep = 0;
4089  int i, nV = currRing->N;
4090  int nwalk=0, endwalks=0;
4091  // int nhilb = 1;
4092  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
4093  //ideal G1;
4094  //ring endRing;
4095  ring newRing, oldRing;
4096  intvec* ivNull = new intvec(nV);
4097  intvec* next_weight;
4098 #if 0
4099  intvec* extra_curr_weight = new intvec(nV);
4100 #endif
4101  //intvec* hilb_func;
4102  intvec* exivlp = Mivlp(nV);
4103 
4104  ring XXRing = currRing;
4105 
4106  //Print("\n// ring r_input = %s;", rString(currRing));
4107  to = clock();
4108  /* compute the reduced Groebner basis of the given ideal w.r.t.
4109  a "fast" monomial order, e.g. degree reverse lex. order (dp) */
4110  G = MstdCC(Go);
4111  tostd=clock()-to;
4112 
4113  /*
4114  Print("\n// Computation of the first std took = %.2f sec",
4115  ((double) tostd)/1000000);
4116  */
4117  if(currRing->order[0] == ringorder_a)
4118  {
4119  goto NEXT_VECTOR;
4120  }
4121  while(1)
4122  {
4123  nwalk ++;
4124  nstep ++;
4125  to = clock();
4126  /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
4127  Gomega = MwalkInitialForm(G, curr_weight);
4128  xtif=xtif+clock()-to;
4129 #if 0
4130  if(Overflow_Error == TRUE)
4131  {
4132  for(i=nV-1; i>=0; i--)
4133  (*curr_weight)[i] = (*extra_curr_weight)[i];
4134  delete extra_curr_weight;
4135  goto LAST_GB_ALT2;
4136  }
4137 #endif
4138  oldRing = currRing;
4139 
4140  /* define a new ring that its ordering is "(a(curr_weight),lp) */
4141  if (rParameter(currRing) != NULL)
4142  {
4143  DefRingPar(curr_weight);
4144  }
4145  else
4146  {
4147  rChangeCurrRing(VMrDefault(curr_weight)); // Aenderung
4148  }
4149  newRing = currRing;
4150  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
4151  to = clock();
4152  /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
4153  M = MstdhomCC(Gomega1);
4154  xtstd=xtstd+clock()-to;
4155  /* change the ring to oldRing */
4156  rChangeCurrRing(oldRing);
4157  M1 = idrMoveR(M, newRing,currRing);
4158  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
4159 
4160  to = clock();
4161  /* compute the reduced Groebner basis of <G> w.r.t. "newRing"
4162  by the liftig process */
4163  F = MLifttwoIdeal(Gomega2, M1, G);
4164  xtlift=xtlift+clock()-to;
4165  idDelete(&M1);
4166  idDelete(&Gomega2);
4167  idDelete(&G);
4168 
4169  /* change the ring to newRing */
4170  rChangeCurrRing(newRing);
4171  F1 = idrMoveR(F, oldRing,currRing);
4172 
4173  to = clock();
4174  /* reduce the Groebner basis <G> w.r.t. newRing */
4175  G = kInterRedCC(F1, NULL);
4176  xtred=xtred+clock()-to;
4177  idDelete(&F1);
4178 
4179  if(endwalks == 1)
4180  break;
4181 
4182  NEXT_VECTOR:
4183  to = clock();
4184  /* compute a next weight vector */
4185  next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
4186  xtnw=xtnw+clock()-to;
4187 #ifdef PRINT_VECTORS
4188  MivString(curr_weight, target_weight, next_weight);
4189 #endif
4190 
4191  if(Overflow_Error == TRUE)
4192  {
4193  /*
4194  ivString(next_weight, "omega");
4195  PrintS("\n// ** The weight vector does NOT stay in Cone!!\n");
4196  */
4197 #ifdef TEST_OVERFLOW
4198  goto TEST_OVERFLOW_OI;
4199 #endif
4200 
4201  newRing = currRing;
4202  if (rParameter(currRing) != NULL)
4203  {
4204  DefRingPar(target_weight);
4205  }
4206  else
4207  {
4208  rChangeCurrRing(VMrDefault(target_weight)); // Aenderung
4209  }
4210  F1 = idrMoveR(G, newRing,currRing);
4211  G = MstdCC(F1);
4212  idDelete(&F1);
4213  newRing = currRing;
4214  break;
4215  }
4216 
4217  if(MivComp(next_weight, ivNull) == 1)
4218  {
4219  newRing = currRing;
4220  delete next_weight;
4221  break;
4222  }
4223 
4224  if(MivComp(next_weight, target_weight) == 1)
4225  {
4226  if(MivSame(target_weight, exivlp)==1)
4227  {
4228  // LAST_GB_ALT2:
4229  //nOverflow_Error = Overflow_Error;
4230  tproc = clock()-xftinput;
4231  //Print("\n// takes %d steps and calls the recursion of level 2:", nwalk);
4232  /* call the changed perturbation walk algorithm with degree 2 */
4233  G = Rec_LastGB(G, curr_weight, target_weight, 2,1);
4234  newRing = currRing;
4235  delete next_weight;
4236  break;
4237  }
4238  endwalks = 1;
4239  }
4240 
4241  for(i=nV-1; i>=0; i--)
4242  {
4243  //(*extra_curr_weight)[i] = (*curr_weight)[i];
4244  (*curr_weight)[i] = (*next_weight)[i];
4245  }
4246  delete next_weight;
4247  }
4248 #ifdef TEST_OVERFLOW
4249  TEST_OVERFLOW_OI:
4250 #endif
4251  rChangeCurrRing(XXRing);
4252  G = idrMoveR(G, newRing,currRing);
4253  delete ivNull;
4254  delete exivlp;
4255 
4256 #ifdef TIME_TEST
4257  // Print("\n// \"Main procedure\" took %d steps dnd %.2f sec. Overflow_Error (%d)", nwalk, ((double) tproc)/1000000, nOverflow_Error);
4258 
4259  TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
4260 
4261  Print("\n// pSetm_Error = (%d)", ErrorCheck());
4262  //Print("\n// Overflow_Error? (%d)", nOverflow_Error);
4263  Print("\n// Awalk2 took %d steps!!", nstep);
4264 #endif
4265 
4266  return(G);
4267 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
BOOLEAN ErrorCheck()
#define Print
Definition: emacs.cc:83
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#define FALSE
Definition: auxiliary.h:140
clock_t xtred
Definition: walk.cc:98
#define TRUE
Definition: auxiliary.h:144
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:99
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:98
static ideal Rec_LastGB(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
Definition: walk.cc:3761
clock_t xtnw
Definition: walk.cc:98
static ideal MstdhomCC(ideal G)
Definition: walk.cc:922
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static ideal MstdCC(ideal G)
Definition: walk.cc:907
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2811
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:275
clock_t xtlift
Definition: walk.cc:98
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:736
clock_t xtextra
Definition: walk.cc:99
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
intvec * Mivlp(int nR)
Definition: walk.cc:995
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
clock_t xtif
Definition: walk.cc:98
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2248
intvec* Mfpertvector ( ideal  G,
intvec iv 
)

Definition at line 1492 of file walk.cc.

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

Definition at line 6940 of file walk.cc.

6941 {
6942  Set_Error(FALSE);
6944  //Print("// pSetm_Error = (%d)", ErrorCheck());
6945  //Print("\n// ring ro = %s;", rString(currRing));
6946 
6947  nnflow = 0;
6948  Xngleich = 0;
6949  Xcall = 0;
6950  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
6951  xftinput = clock();
6952 
6953  ring oldRing = currRing;
6954  int i, nV = currRing->N;
6955  XivNull = new intvec(nV);
6956  Xivinput = ivtarget;
6957  ngleich = 0;
6958  to=clock();
6959  ideal I = MstdCC(G);
6960  G = NULL;
6961  xftostd=clock()-to;
6962  Xsigma = ivstart;
6963 
6964  Xnlev=nV;
6965 
6966 #ifdef FIRST_STEP_FRACTAL
6967  ideal Gw = MwalkInitialForm(I, ivstart);
6968  for(i=IDELEMS(Gw)-1; i>=0; i--)
6969  {
6970  if((Gw->m[i]!=NULL) // len >=0
6971  && (Gw->m[i]->next!=NULL) // len >=1
6972  && (Gw->m[i]->next->next!=NULL)) // len >=2
6973  {
6974  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
6975  intvec* Mdp;
6976 
6977  if(MivSame(ivstart, iv_dp) != 1)
6978  Mdp = MivWeightOrderdp(ivstart);
6979  else
6980  Mdp = MivMatrixOrderdp(nV);
6981 
6982  Xsigma = Mfpertvector(I, Mdp);
6984 
6985  delete Mdp;
6986  delete iv_dp;
6987  break;
6988  }
6989  }
6990  idDelete(&Gw);
6991 #endif
6992 
6993  ideal I1;
6994  intvec* Mlp;
6995  Xivlp = Mivlp(nV);
6996 
6997  if(MivComp(ivtarget, Xivlp) != 1)
6998  {
6999  if (rParameter(currRing) != NULL)
7000  DefRingPar(ivtarget);
7001  else
7002  rChangeCurrRing(VMrDefault1(ivtarget)); //Aenderung1
7003 
7004  I1 = idrMoveR(I, oldRing,currRing);
7005  Mlp = MivWeightOrderlp(ivtarget);
7006  Xtau = Mfpertvector(I1, Mlp);
7007  }
7008  else
7009  {
7010  if (rParameter(currRing) != NULL)
7011  DefRingParlp();
7012  else
7013  VMrDefaultlp();
7014 
7015  I1 = idrMoveR(I, oldRing,currRing);
7016  Mlp = MivMatrixOrderlp(nV);
7017  Xtau = Mfpertvector(I1, Mlp);
7018  }
7019  delete Mlp;
7021 
7022  //ivString(Xsigma, "Xsigma");
7023  //ivString(Xtau, "Xtau");
7024 
7025  id_Delete(&I, oldRing);
7026  ring tRing = currRing;
7027 
7028  if (rParameter(currRing) != NULL)
7029  DefRingPar(ivstart);
7030  else
7031  rChangeCurrRing(VMrDefault1(ivstart)); //Aenderung2
7032 
7033  I = idrMoveR(I1,tRing,currRing);
7034  to=clock();
7035  ideal J = MstdCC(I);
7036  idDelete(&I);
7037  xftostd=xftostd+clock()-to;
7038 
7039  ideal resF;
7040  ring helpRing = currRing;
7041 //ideal G, int nlev, intvec* omtmp, int weight_rad)
7042  J = rec_r_fractal_call(J, 1, ivtarget,weight_rad);
7043 
7044  rChangeCurrRing(oldRing);
7045  resF = idrMoveR(J, helpRing,currRing);
7046  idSkipZeroes(resF);
7047 
7048  delete Xivlp;
7049  delete Xsigma;
7050  delete Xtau;
7051  delete XivNull;
7052 
7053 #ifdef TIME_TEST
7054  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
7055  xtlift, xtred, xtnw);
7056 
7057 
7058  Print("\n// pSetm_Error = (%d)", ErrorCheck());
7059  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
7060  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
7061 #endif
7062 
7063  return(resF);
7064 }
BOOLEAN ErrorCheck()
#define Print
Definition: emacs.cc:83
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1492
intvec * Xivlp
Definition: walk.cc:4287
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
intvec * Xivinput
Definition: walk.cc:4286
int nnflow
Definition: walk.cc:6105
static ring VMrDefault1(intvec *va)
Definition: walk.cc:2430
int ngleich
Definition: walk.cc:4282
int Xngleich
Definition: walk.cc:6107
#define FALSE
Definition: auxiliary.h:140
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1416
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:98
intvec * Xsigma
Definition: walk.cc:4283
int Xnlev
Definition: walk.cc:1491
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1436
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
intvec * Xtau
Definition: walk.cc:4284
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2748
int Xcall
Definition: walk.cc:6106
clock_t xftostd
Definition: walk.cc:99
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:99
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:98
clock_t xtnw
Definition: walk.cc:98
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2881
static ideal MstdCC(ideal G)
Definition: walk.cc:907
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *omtmp, int weight_rad)
Definition: walk.cc:6458
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2811
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1397
clock_t xtlift
Definition: walk.cc:98
intvec * MivUnit(int nV)
Definition: walk.cc:1476
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:736
clock_t xtextra
Definition: walk.cc:99
intvec * XivNull
Definition: walk.cc:6090
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1381
intvec * Mivlp(int nR)
Definition: walk.cc:995
clock_t xtif
Definition: walk.cc:98
ideal Mfwalk ( ideal  G,
intvec ivstart,
intvec ivtarget 
)

Definition at line 6814 of file walk.cc.

6815 {
6816  Set_Error(FALSE);
6818  //Print("// pSetm_Error = (%d)", ErrorCheck());
6819  //Print("\n// ring ro = %s;", rString(currRing));
6820 
6821  nnflow = 0;
6822  Xngleich = 0;
6823  Xcall = 0;
6824  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
6825  xftinput = clock();
6826 
6827  ring oldRing = currRing;
6828  int i, nV = currRing->N;
6829  XivNull = new intvec(nV);
6830  Xivinput = ivtarget;
6831  ngleich = 0;
6832  to=clock();
6833  ideal I = MstdCC(G);
6834  G = NULL;
6835  xftostd=clock()-to;
6836  Xsigma = ivstart;
6837 
6838  Xnlev=nV;
6839 
6840 #ifdef FIRST_STEP_FRACTAL
6841  ideal Gw = MwalkInitialForm(I, ivstart);
6842  for(i=IDELEMS(Gw)-1; i>=0; i--)
6843  {
6844  if((Gw->m[i]!=NULL) // len >=0
6845  && (Gw->m[i]->next!=NULL) // len >=1
6846  && (Gw->m[i]->next->next!=NULL)) // len >=2
6847  {
6848  intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
6849  intvec* Mdp;
6850 
6851  if(MivSame(ivstart, iv_dp) != 1)
6852  Mdp = MivWeightOrderdp(ivstart);
6853  else
6854  Mdp = MivMatrixOrderdp(nV);
6855 
6856  Xsigma = Mfpertvector(I, Mdp);
6858 
6859  delete Mdp;
6860  delete iv_dp;
6861  break;
6862  }
6863  }
6864  idDelete(&Gw);
6865 #endif
6866 
6867  ideal I1;
6868  intvec* Mlp;
6869  Xivlp = Mivlp(nV);
6870 
6871  if(MivComp(ivtarget, Xivlp) != 1)
6872  {
6873  if (rParameter(currRing) != NULL)
6874  DefRingPar(ivtarget);
6875  else
6876  rChangeCurrRing(VMrDefault1(ivtarget)); //Aenderung1
6877 
6878  I1 = idrMoveR(I, oldRing,currRing);
6879  Mlp = MivWeightOrderlp(ivtarget);
6880  Xtau = Mfpertvector(I1, Mlp);
6881  }
6882  else
6883  {
6884  if (rParameter(currRing) != NULL)
6885  DefRingParlp();
6886  else
6887  VMrDefaultlp();
6888 
6889  I1 = idrMoveR(I, oldRing,currRing);
6890  Mlp = MivMatrixOrderlp(nV);
6891  Xtau = Mfpertvector(I1, Mlp);
6892  }
6893  delete Mlp;
6895 
6896  //ivString(Xsigma, "Xsigma");
6897  //ivString(Xtau, "Xtau");
6898 
6899  id_Delete(&I, oldRing);
6900  ring tRing = currRing;
6901 
6902  if (rParameter(currRing) != NULL)
6903  DefRingPar(ivstart);
6904  else
6905  rChangeCurrRing(VMrDefault1(ivstart)); //Aenderung2
6906 
6907  I = idrMoveR(I1,tRing,currRing);
6908  to=clock();
6909  ideal J = MstdCC(I);
6910  idDelete(&I);
6911  xftostd=xftostd+clock()-to;
6912 
6913  ideal resF;
6914  ring helpRing = currRing;
6915 
6916  J = rec_fractal_call(J, 1, ivtarget);
6917 
6918  rChangeCurrRing(oldRing);
6919  resF = idrMoveR(J, helpRing,currRing);
6920  idSkipZeroes(resF);
6921 
6922  delete Xivlp;
6923  delete Xsigma;
6924  delete Xtau;
6925  delete XivNull;
6926 
6927 #ifdef TIME_TEST
6928  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
6929  xtlift, xtred, xtnw);
6930 
6931 
6932  Print("\n// pSetm_Error = (%d)", ErrorCheck());
6933  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
6934  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
6935 #endif
6936 
6937  return(resF);
6938 }
BOOLEAN ErrorCheck()
#define Print
Definition: emacs.cc:83
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition: walk.cc:1492
intvec * Xivlp
Definition: walk.cc:4287
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
intvec * Xivinput
Definition: walk.cc:4286
int nnflow
Definition: walk.cc:6105
static ring VMrDefault1(intvec *va)
Definition: walk.cc:2430
int ngleich
Definition: walk.cc:4282
int Xngleich
Definition: walk.cc:6107
#define FALSE
Definition: auxiliary.h:140
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1416
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
clock_t xtred
Definition: walk.cc:98
intvec * Xsigma
Definition: walk.cc:4283
int Xnlev
Definition: walk.cc:1491
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
intvec * MivWeightOrderdp(intvec *ivstart)
Definition: walk.cc:1436
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
intvec * Xtau
Definition: walk.cc:4284
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2748
int Xcall
Definition: walk.cc:6106
clock_t xftostd
Definition: walk.cc:99
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:249
clock_t xftinput
Definition: walk.cc:99
int i
Definition: cfEzgcd.cc:123
clock_t xtstd
Definition: walk.cc:98
clock_t xtnw
Definition: walk.cc:98
#define IDELEMS(i)
Definition: simpleideals.h:24
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2881
static ideal MstdCC(ideal G)
Definition: walk.cc:907
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2811
static ideal rec_fractal_call(ideal G, int nlev, intvec *omtmp)
Definition: walk.cc:6112
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1397
clock_t xtlift
Definition: walk.cc:98
intvec * MivUnit(int nV)
Definition: walk.cc:1476
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:736
clock_t xtextra
Definition: walk.cc:99
intvec * XivNull
Definition: walk.cc:6090
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1381
intvec * Mivlp(int nR)
Definition: walk.cc:995
clock_t xtif
Definition: walk.cc:98
ideal MidLift ( ideal  Gomega,
ideal  M 
)
intvec* Mivdp ( int  nR)

Definition at line 980 of file walk.cc.

981 {
982  int i;
983  intvec* ivm = new intvec(nR);
984 
985  for(i=nR-1; i>=0; i--)
986  {
987  (*ivm)[i] = 1;
988  }
989  return ivm;
990 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* Mivlp ( int  nR)

Definition at line 995 of file walk.cc.

996 {
997  intvec* ivm = new intvec(nR);
998  (*ivm)[0] = 1;
999 
1000  return ivm;
1001 }
Definition: intvec.h:16
intvec* MivMatrixOrder ( intvec iv)

Definition at line 938 of file walk.cc.

939 {
940  int i, nR = iv->length();
941 
942  intvec* ivm = new intvec(nR*nR);
943 
944  for(i=0; i<nR; i++)
945  {
946  (*ivm)[i] = (*iv)[i];
947  }
948  for(i=1; i<nR; i++)
949  {
950  (*ivm)[i*nR+i-1] = 1;
951  }
952  return ivm;
953 }
int length() const
Definition: intvec.h:86
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MivMatrixOrderdp ( int  iv)

Definition at line 1397 of file walk.cc.

1398 {
1399  int i;
1400  intvec* ivM = new intvec(nV*nV);
1401 
1402  for(i=0; i<nV; i++)
1403  {
1404  (*ivM)[i] = 1;
1405  }
1406  for(i=1; i<nV; i++)
1407  {
1408  (*ivM)[(i+1)*nV - i] = -1;
1409  }
1410  return(ivM);
1411 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MivMatrixOrderlp ( int  nV)

Definition at line 1381 of file walk.cc.

1382 {
1383  int i;
1384  intvec* ivM = new intvec(nV*nV);
1385 
1386  for(i=0; i<nV; i++)
1387  {
1388  (*ivM)[i*nV + i] = 1;
1389  }
1390  return(ivM);
1391 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* Mivperttarget ( ideal  G,
int  ndeg 
)
int MivSame ( intvec u,
intvec v 
)

Definition at line 868 of file walk.cc.

869 {
870  assume(u->length() == v->length());
871 
872  int i, niv = u->length();
873 
874  for (i=0; i<niv; i++)
875  {
876  if ((*u)[i] != (*v)[i])
877  {
878  return 0;
879  }
880  }
881  return 1;
882 }
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 1476 of file walk.cc.

1477 {
1478  int i;
1479  intvec* ivM = new intvec(nV);
1480  for(i=nV-1; i>=0; i--)
1481  {
1482  (*ivM)[i] = 1;
1483  }
1484  return(ivM);
1485 }
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MivWeightOrderdp ( intvec ivstart)

Definition at line 1436 of file walk.cc.

1437 {
1438  int i;
1439  int nV = ivstart->length();
1440  intvec* ivM = new intvec(nV*nV);
1441 
1442  for(i=0; i<nV; i++)
1443  {
1444  (*ivM)[i] = (*ivstart)[i];
1445  }
1446  for(i=0; i<nV; i++)
1447  {
1448  (*ivM)[nV+i] = 1;
1449  }
1450  for(i=2; i<nV; i++)
1451  {
1452  (*ivM)[(i+1)*nV - i] = -1;
1453  }
1454  return(ivM);
1455 }
int length() const
Definition: intvec.h:86
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MivWeightOrderlp ( intvec ivstart)

Definition at line 1416 of file walk.cc.

1417 {
1418  int i;
1419  int nV = ivstart->length();
1420  intvec* ivM = new intvec(nV*nV);
1421 
1422  for(i=0; i<nV; i++)
1423  {
1424  (*ivM)[i] = (*ivstart)[i];
1425  }
1426  for(i=1; i<nV; i++)
1427  {
1428  (*ivM)[i*nV + i-1] = 1;
1429  }
1430  return(ivM);
1431 }
int length() const
Definition: intvec.h:86
Definition: intvec.h:16
int i
Definition: cfEzgcd.cc:123
intvec* MkInterRedNextWeight ( intvec iva,
intvec ivb,
ideal  G 
)

Definition at line 2248 of file walk.cc.

2249 {
2250  intvec* tmp = new intvec(iva->length());
2251  intvec* result;
2252 
2253  if(G == NULL)
2254  {
2255  return tmp;
2256  }
2257  if(MivComp(iva, ivb) == 1)
2258  {
2259  return tmp;
2260  }
2261  result = MwalkNextWeightCC(iva, ivb, G);
2262 
2263  if(MivComp(result, iva) == 1)
2264  {
2265  delete result;
2266  return tmp;
2267  }
2268 
2269  delete tmp;
2270  return result;
2271 }
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
int length() const
Definition: intvec.h:86
static TreeM * G
Definition: janet.cc:38
Definition: intvec.h:16
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition: walk.cc:1865
#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 1061 of file walk.cc.

1062 {
1063  // ivtarget is a matrix order of a degree reverse lex. order
1064  int nV = currRing->N;
1065  //assume(pdeg <= nV && pdeg >= 0);
1066 
1067  int i, j, nG = IDELEMS(G);
1068  intvec* v_null = new intvec(nV);
1069 
1070 
1071  // Check that the perturbed degree is valid
1072  if(pdeg > nV || pdeg <= 0)
1073  {
1074  WerrorS("//** The perturbed degree is wrong!!");
1075  return v_null;
1076  }
1077  delete v_null;
1078 
1079  if(pdeg == 1)
1080  {
1081  return ivtarget;
1082  }
1083  mpz_t *pert_vector = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
1084  //mpz_t *pert_vector1 = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
1085 
1086  for(i=0; i<nV; i++)
1087  {
1088  mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
1089  // mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
1090  }
1091  // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
1092  // where the Ai are the i-te rows of the matrix target_ord.
1093  int ntemp, maxAi, maxA=0;
1094  for(i=1; i<pdeg; i++)
1095  {
1096  maxAi = (*ivtarget)[i*nV];
1097  if(maxAi<0)
1098  {
1099  maxAi = -maxAi;
1100  }
1101  for(j=i*nV+1; j<(i+1)*nV; j++)
1102  {
1103  ntemp = (*ivtarget)[j];
1104  if(ntemp < 0)
1105  {
1106  ntemp = -ntemp;
1107  }
1108  if(ntemp > maxAi)
1109  {
1110  maxAi = ntemp;
1111  }
1112  }
1113  maxA += maxAi;
1114  }
1115 
1116  // Calculate inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.
1117 
1118  intvec* ivUnit = Mivdp(nV);
1119 
1120  mpz_t tot_deg; mpz_init(tot_deg);
1121  mpz_t maxdeg; mpz_init(maxdeg);
1122  mpz_t inveps; mpz_init(inveps);
1123 
1124 
1125  for(i=nG-1; i>=0; i--)
1126  {
1127  mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
1128  if (mpz_cmp(maxdeg, tot_deg) > 0 )
1129  {
1130  mpz_set(tot_deg, maxdeg);
1131  }
1132  }
1133 
1134  delete ivUnit;
1135  mpz_mul_ui(inveps, tot_deg, maxA);
1136  mpz_add_ui(inveps, inveps, 1);
1137 
1138 
1139  // takes "small" inveps
1140 #ifdef INVEPS_SMALL_IN_MPERTVECTOR
1141  if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
1142  {
1143  // Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", mpz_get_si(inveps), pdeg);
1144  mpz_fdiv_q_ui(inveps, inveps, pdeg);
1145  // mpz_out_str(stdout, 10, inveps);
1146  }
1147 #else
1148  // PrintS("\n// the \"big\" inverse epsilon: ");
1149  mpz_out_str(stdout, 10, inveps);
1150 #endif
1151 
1152  // pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg,
1153  // pert_vector := A1
1154  for( i=1; i < pdeg; i++ )
1155  {
1156  for(j=0; j<nV; j++)
1157  {
1158  mpz_mul(pert_vector[j], pert_vector[j], inveps);
1159  if((*ivtarget)[i*nV+j]<0)
1160  {
1161  mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
1162  }
1163  else
1164  {
1165  mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
1166  }
1167  }
1168  }
1169  mpz_t ztemp;
1170  mpz_init(ztemp);
1171  mpz_set(ztemp, pert_vector[0]);
1172  for(i=1; i<nV; i++)
1173  {
1174  mpz_gcd(ztemp, ztemp, pert_vector[i]);
1175  if(mpz_cmp_si(ztemp, 1) == 0)
1176  {
1177  break;
1178  }
1179  }
1180  if(mpz_cmp_si(ztemp, 1) != 0)
1181  {
1182  for(i=0; i<nV; i++)
1183  {
1184  mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
1185  }
1186  }
1187 
1188  intvec *pert_vector1= new intvec(nV);
1189  j = 0;
1190  for(i=0; i<nV; i++)
1191  {
1192  (* pert_vector1)[i] = mpz_get_si(pert_vector[i]);
1193  (* pert_vector1)[i] = 0.1*(* pert_vector1)[i];
1194  (* pert_vector1)[i] = floor((* pert_vector1)[i] + 0.5);
1195  if((* pert_vector1)[i] == 0)
1196  {
1197  j++;
1198  }
1199  }
1200  if(j > nV - 1)
1201  {
1202  // Print("\n// MPertVectors: geaenderter vector gleich Null! \n");
1203  delete pert_vector1;
1204  goto CHECK_OVERFLOW;
1205  }
1206 
1207 // check that the perturbed weight vector lies in the Groebner cone
1208  if(test_w_in_ConeCC(G,pert_vector1) != 0)
1209  {
1210  // Print("\n// MPertVectors: geaenderter vector liegt in Groebnerkegel! \n");
1211  for(i=0; i<nV; i++)
1212  {
1213  mpz_set_si(pert_vector[i], (*pert_vector1)[i]);
1214  }
1215  }
1216  else
1217  {
1218  //Print("\n// MpertVectors: geaenderter vector liegt nicht in Groebnerkegel! \n");
1219  }
1220  delete pert_vector1;
1221 
1222  CHECK_OVERFLOW:
1223  intvec* result = new intvec(nV);
1224 
1225  /* 2147483647 is max. integer representation in SINGULAR */
1226  mpz_t sing_int;
1227  mpz_init_set_ui(sing_int, 2147483647);
1228 
1229  int ntrue=0;
1230  for(i=0; i<nV; i++)
1231  {
1232  (*result)[i] = mpz_get_si(pert_vector[i]);
1233  if(mpz_cmp(pert_vector[i], sing_int)>=0)
1234  {
1235  ntrue++;
1236  if(Overflow_Error == FALSE)
1237  {
1238  Overflow_Error = TRUE;
1239  PrintS("\n// ** OVERFLOW in \"MPertvectors\": ");
1240  mpz_out_str( stdout, 10, pert_vector[i]);
1241  PrintS(" is greater than 2147483647 (max. integer representation)");
1242  Print("\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
1243  }
1244  }
1245  }
1246 
1247  if(Overflow_Error == TRUE)
1248  {
1249  ivString(result, "pert_vector");
1250  Print("\n// %d element(s) of it is overflow!!", ntrue);
1251  }
1252 
1253  mpz_clear(ztemp);
1254  mpz_clear(sing_int);
1255  omFree(pert_vector);
1256  //omFree(pert_vector1);
1257  mpz_clear(tot_deg);
1258  mpz_clear(maxdeg);
1259  mpz_clear(inveps);
1260 
1262  for(j=0; j<IDELEMS(G); j++)
1263  {
1264  poly p=G->m[j];
1265  while(p!=NULL)
1266  {
1267  p_Setm(p,currRing); pIter(p);
1268  }
1269  }
1270  return result;
1271 }
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:760
#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:23
static TreeM * G
Definition: janet.cc:38
#define omAlloc(size)
Definition: omAllocDecl.h:210
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define pIter(p)
Definition: monomials.h:44
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
Definition: intvec.h:16
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3435
int j
Definition: myNF.cc:70
#define omFree(addr)
Definition: omAllocDecl.h:261
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
#define IDELEMS(i)
Definition: simpleideals.h:24
intvec * Mivdp(int nR)
Definition: walk.cc:980
#define NULL
Definition: omList.c:10
static int MwalkWeightDegree(poly p, intvec *weight_vector)
Definition: walk.cc:645
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
polyrec * poly
Definition: hilb.h:10
static void ivString(intvec *iv, const char *ch)
Definition: walk.cc:500
return result
Definition: facAbsBiFact.cc:76
intvec* MPertVectorslp ( ideal  G,
intvec ivtarget,
int  pdeg 
)

Definition at line 1279 of file walk.cc.

1280 {
1281  // ivtarget is a matrix order of the lex. order
1282  int nV = currRing->N;
1283  //assume(pdeg <= nV && pdeg >= 0);
1284 
1285  int i, j, nG = IDELEMS(G);
1286  intvec* pert_vector = new intvec(nV);
1287 
1288  //Checking that the perturbated degree is valid
1289  if(pdeg > nV || pdeg <= 0)
1290  {
1291  WerrorS("//** The perturbed degree is wrong!!");
1292  return pert_vector;
1293  }
1294  for(i=0; i<nV; i++)
1295  {
1296  (*pert_vector)[i]=(*ivtarget)[i];
1297  }
1298  if(pdeg == 1)
1299  {
1300  return pert_vector;
1301  }
1302  // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
1303  // where the Ai are the i-te rows of the matrix target_ord.
1304  int ntemp, maxAi, maxA=0;
1305  for(i=1; i<pdeg; i++)
1306  {
1307  maxAi = (*ivtarget)[i*nV];
1308  for(j=i*nV+1; j<(i+1)*nV; j++)
1309  {
1310  ntemp = (*ivtarget)[j];
1311  if(ntemp > maxAi)
1312  {
1313  maxAi = ntemp;
1314  }
1315  }
1316  maxA += maxAi;
1317  }
1318 
1319  // Calculate inveps := 1/eps, where 1/eps > deg(p)*max1 for all p in G.
1320  int inveps, tot_deg = 0, maxdeg;
1321 
1322  intvec* ivUnit = Mivdp(nV);//19.02
1323  for(i=nG-1; i>=0; i--)
1324  {
1325  // maxdeg = pTotaldegree(G->m[i], currRing); //it's wrong for ex1,2,rose
1326  maxdeg = MwalkWeightDegree(G->m[i], ivUnit);
1327  if (maxdeg > tot_deg )
1328  {
1329  tot_deg = maxdeg;
1330  }
1331  }
1332  delete ivUnit;
1333 
1334  inveps = (tot_deg * maxA) + 1;
1335 
1336 #ifdef INVEPS_SMALL_IN_FRACTAL
1337  // Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", inveps, pdeg);
1338  if(inveps > pdeg && pdeg > 3)
1339  {
1340  inveps = inveps / pdeg;
1341  }
1342  // Print(" %d", inveps);
1343 #else
1344  PrintS("\n// the \"big\" inverse epsilon %d", inveps);
1345 #endif
1346 
1347  // Pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg
1348  for ( i=1; i < pdeg; i++ )
1349  {
1350  for(j=0; j<nV; j++)
1351  {
1352  (*pert_vector)[j] = inveps*((*pert_vector)[j]) + (*ivtarget)[i*nV+j];
1353  }
1354  }
1355 
1356  int temp = (*pert_vector)[0];
1357  for(i=1; i<nV; i++)
1358  {
1359  temp = gcd(temp, (*pert_vector)[i]);
1360  if(temp == 1)
1361  {
1362  break;
1363  }
1364  }
1365  if(temp != 1)
1366  {
1367  for(i=0; i<nV; i++)
1368  {
1369  (*pert_vector)[i] = (*pert_vector)[i] / temp;
1370  }
1371  }
1372 
1373  intvec* result = pert_vector;
1374  delete pert_vector;
1375  return result;
1376 }
void WerrorS(const char *s)
Definition: feFopen.cc:23
static TreeM * G
Definition: janet.cc:38
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
Definition: intvec.h:16
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
#define IDELEMS(i)
Definition: simpleideals.h:24
intvec * Mivdp(int nR)
Definition: walk.cc:980
static long gcd(const long a, const long b)
Definition: walk.cc:541
static int MwalkWeightDegree(poly p, intvec *weight_vector)
Definition: walk.cc:645
return result
Definition: facAbsBiFact.cc:76
ideal Mprwalk ( ideal  Go,
intvec curr_weight,
intvec target_weight,
int  weight_rad,
int  op_deg,
int  tp_deg,
ring  baseRing 
)

Definition at line 8246 of file walk.cc.

8247 {
8248  BITSET save1 = si_opt_1; // save current options
8249  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
8250  Set_Error(FALSE);
8252 #ifdef TIME_TEST
8253  clock_t tinput=0, tostd=0, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
8254  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
8255  tinput = clock();
8256  clock_t tim;
8257 #endif
8258  int i,nwalk,nV = baseRing->N;
8259 
8260  ideal G, Gomega, M, F, Gomega1, Gomega2, M1;
8261  ring newRing;
8262  ring XXRing = baseRing;
8263  intvec* exivlp = Mivlp(nV);
8264  intvec* orig_target = target_weight;
8265  intvec* pert_target_vector = target_weight;
8266  intvec* ivNull = new intvec(nV);
8267  intvec* tmp_weight = new intvec(nV);
8268 #ifdef CHECK_IDEAL_MWALK
8269  poly p;
8270 #endif
8271  for(i=0; i<nV; i++)
8272  {
8273  (*tmp_weight)[i] = (*curr_weight)[i];
8274  }
8275 #ifndef BUCHBERGER_ALG
8276  intvec* hilb_func;
8277  // to avoid (1,0,...,0) as the target vector
8278  intvec* last_omega = new intvec(nV);
8279  for(i=0 i<nV; i++)
8280  {
8281  (*last_omega)[i] = 1;
8282  }
8283  (*last_omega)[0] = 10000;
8284 #endif
8285  baseRing = currRing;
8286  newRing = VMrDefault(curr_weight);
8287  rChangeCurrRing(newRing);
8288  G = idrMoveR(Go,baseRing,currRing);
8289 #ifdef TIME_TEST
8290  to = clock();
8291 #endif
8292  G = kStd(G,NULL,testHomog,NULL,NULL,0,0,NULL);
8293  idSkipZeroes(G);
8294 #ifdef TIME_TEST
8295  tostd = tostd + to - clock();
8296 #endif
8297 #ifdef CHECK_IDEAL_MWALK
8298  idString(G,"G");
8299 #endif
8300  if(op_deg >1)
8301  {
8302  if(MivComp(curr_weight,MivUnit(nV)) == 1) //ring order is "dp"
8303  {
8304  curr_weight = MPertVectors(G, MivMatrixOrderdp(nV), op_deg);
8305  }
8306  else //ring order is not "dp"
8307  {
8308  curr_weight = MPertVectors(G, MivMatrixOrder(curr_weight), op_deg);
8309  }
8310  }
8311  baseRing = currRing;
8312  if(tp_deg > 1 && tp_deg <= nV)
8313  {
8314  pert_target_vector = target_weight;
8315  }
8316 #ifdef CHECK_IDEAL_MWALK
8317  ivString(curr_weight, "new curr_weight");
8318  ivString(target_weight, "new target_weight");
8319 #endif
8320  nwalk = 0;
8321  while(1)
8322  {
8323  nwalk ++;
8324 #ifdef TIME_TEST
8325  to = clock();
8326 #endif
8327  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
8328 #ifdef TIME_TEST
8329  tif = tif + clock()-to; //time for computing initial form ideal
8330 #endif
8331 #ifdef CHECK_IDEAL_MWALK
8332  idString(Gomega,"Gomega");
8333 #endif
8334 #ifndef BUCHBERGER_ALG
8335  if(isNolVector(curr_weight) == 0)
8336  {
8337  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
8338  }
8339  else
8340  {
8341  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
8342  }
8343 #endif
8344  if(nwalk == 1)
8345  {
8346  newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
8347  }
8348  else
8349  {
8350  newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
8351  }
8352  rChangeCurrRing(newRing);
8353  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
8354  idDelete(&Gomega);
8355  // compute a Groebner basis of <Gomega> w.r.t. "newRing"
8356 #ifdef TIME_TEST
8357  to = clock();
8358 #endif
8359 #ifndef BUCHBERGER_ALG
8360  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
8361  delete hilb_func;
8362 #else
8363  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
8364 #endif
8365  idSkipZeroes(M);
8366 #ifdef TIME_TEST
8367  tstd = tstd + clock() - to;
8368 #endif
8369 #ifdef CHECK_IDEAL_MWALK
8370  idString(M, "M");
8371 #endif
8372  //change the ring to baseRing
8373  rChangeCurrRing(baseRing);
8374  M1 = idrMoveR(M, newRing,currRing);
8375  idDelete(&M);
8376  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
8377  idDelete(&Gomega1);
8378  to = clock();
8379  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega), where Gomega is a reduced Groebner basis w.r.t. the current ring
8380  F = MLifttwoIdeal(Gomega2, M1, G);
8381  idSkipZeroes(F);
8382 #ifdef TIME_TEST
8383  tlift = tlift + clock() - to;
8384 #endif
8385 #ifdef CHECK_IDEAL_MWALK
8386  idString(F,"F");
8387 #endif
8388  rChangeCurrRing(newRing); // change the ring to newRing
8389  G = idrMoveR(F,baseRing,currRing);
8390  idDelete(&F);
8391  baseRing = currRing; // set baseRing equal to newRing
8392 #ifdef CHECK_IDEAL_MWALK
8393  idString(G,"G");
8394 #endif
8395 #ifdef TIME_TEST
8396  to = clock();
8397 #endif
8398  intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, op_deg);
8399 #ifdef TIME_TEST
8400  tnw = tnw + clock() - to;
8401 #endif
8402 #ifdef PRINT_VECTORS
8403  MivString(curr_weight, target_weight, next_weight);
8404 #endif
8405  if(Overflow_Error == TRUE)
8406  {
8407  PrintS("\n//**Mprwalk: OVERFLOW: The computed vector does not stay in cone, the result may be wrong.\n");
8408  delete next_weight;
8409  break;
8410  }
8411 
8412  if(test_w_in_ConeCC(G,target_weight) == 1 || MivComp(next_weight, ivNull) == 1)
8413  {
8414  delete next_weight;
8415  break;
8416  }
8417  //update tmp_weight and curr_weight
8418  for(i=nV-1; i>=0; i--)
8419  {
8420  (*tmp_weight)[i] = (*curr_weight)[i];
8421  (*curr_weight)[i] = (*next_weight)[i];
8422  }
8423  delete next_weight;
8424  } //end of while-loop
8425  Print("\n// Mprwalk took %d steps. Ring= %s;\n", nwalk, rString(currRing));
8426  idSkipZeroes(G);
8427  si_opt_1 = save1; //set original options, e. g. option(RedSB)
8428  baseRing = currRing;
8429  rChangeCurrRing(XXRing);
8430  ideal Res = idrMoveR(G,baseRing,currRing);
8431  delete tmp_weight;
8432  delete ivNull;
8433  delete exivlp;
8434 #ifndef BUCHBERGER_ALG
8435  delete last_omega;
8436 #endif
8437 #ifdef TIME_TEST
8438  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
8439 #endif
8440  return(Res);
8441 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
#define OPT_REDSB
Definition: options.h:71
unsigned si_opt_1
Definition: options.c:5
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:938
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:760
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
char * rString(ring r)
Definition: ring.cc:644
clock_t xtred
Definition: walk.cc:98
#define TRUE
Definition: auxiliary.h:144
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define Sy_bit(x)
Definition: options.h:30
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
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:98
clock_t xtnw
Definition: walk.cc:98
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1061
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void rChangeCurrRing(ring r)
Definition: polys.cc:14
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1397
clock_t xtlift
Definition: walk.cc:98
intvec * MivUnit(int nV)
Definition: walk.cc:1476
intvec * hFirstSeries(ideal S, intvec *modulweight, ideal Q, intvec *wdegree, ring tailRing)
Definition: hilb.cc:1299
polyrec * poly
Definition: hilb.h:10
static void ivString(intvec *iv, const char *ch)
Definition: walk.cc:500
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition: walk.cc:736
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2505
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
intvec * Mivlp(int nR)
Definition: walk.cc:995
static intvec * MWalkRandomNextWeight(ideal G, intvec *curr_weight, intvec *target_weight, int weight_rad, int pert_deg)
Definition: walk.cc:4408
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
clock_t xtif
Definition: walk.cc:98
ideal Mpwalk ( ideal  Go,
int  op_deg,
int  tp_deg,
intvec curr_weight,
intvec target_weight,
int  nP 
)

Definition at line 5752 of file walk.cc.

5754 {
5755  Set_Error(FALSE );
5757  //Print("// pSetm_Error = (%d)", ErrorCheck());
5758 
5759  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5760  xtextra=0;
5761  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5762  tinput = clock();
5763 
5764  clock_t tim;
5765 
5766  nstep = 0;
5767  int i, ntwC=1, ntestw=1, nV = currRing->N;
5768  int endwalks=0;
5769 
5770  ideal Gomega, M, F, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
5771  ring newRing, oldRing, TargetRing;
5772  intvec* iv_M_dp;
5773  intvec* iv_M_lp;
5774  intvec* exivlp = Mivlp(nV);
5775  intvec* orig_target = target_weight;
5776  intvec* pert_target_vector = target_weight;
5777  intvec* ivNull = new intvec(nV);
5778  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
5779 #ifndef BUCHBERGER_ALG
5780  intvec* hilb_func;
5781 #endif
5782  intvec* next_weight;
5783 
5784  // to avoid (1,0,...,0) as the target vector
5785  intvec* last_omega = new intvec(nV);
5786  for(i=nV-1; i>0; i--)
5787  (*last_omega)[i] = 1;
5788  (*last_omega)[0] = 10000;
5789 
5790  ring XXRing = currRing;
5791 
5792 
5793  to = clock();
5794  /* perturbs the original vector */
5795  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
5796  {
5797  G = MstdCC(Go);
5798  tostd = clock()-to;
5799  if(op_deg != 1){
5800  iv_M_dp = MivMatrixOrderdp(nV);
5801  //ivString(iv_M_dp, "iv_M_dp");
5802  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
5803  }
5804  }
5805  else
5806  {
5807  //define ring order := (a(curr_weight),lp);
5808  if (rParameter(currRing) != NULL)
5809  DefRingPar(curr_weight);
5810  else
5811  rChangeCurrRing(VMrDefault(curr_weight)); //Aenderung 1
5812 
5813  G = idrMoveR(Go, XXRing,currRing);
5814  G = MstdCC(G);
5815  tostd = clock()-to;
5816  if(op_deg != 1){
5817  iv_M_dp = MivMatrixOrder(curr_weight);
5818  curr_weight = MPertVectors(G, iv_M_dp, op_deg);
5819  }
5820  }
5821  delete iv_dp;
5822  if(op_deg != 1) delete iv_M_dp;
5823 
5824  ring HelpRing = currRing;
5825 
5826  /* perturbs the target weight vector */
5827  if(tp_deg > 1 && tp_deg <= nV)
5828  {
5829  if (rParameter(currRing) != NULL)
5830  DefRingPar(target_weight);
5831  else
5832  rChangeCurrRing(VMrDefault(target_weight)); // Aenderung 2
5833 
5834  TargetRing = currRing;
5835  ssG = idrMoveR(G,HelpRing,currRing);
5836  if(MivSame(target_weight, exivlp) == 1)
5837  {
5838  iv_M_lp = MivMatrixOrderlp(nV);
5839  //ivString(iv_M_lp, "iv_M_lp");
5840  //target_weight = MPertVectorslp(ssG, iv_M_lp, tp_deg);
5841  target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
5842  }
5843  else
5844  {
5845  iv_M_lp = MivMatrixOrder(target_weight);
5846  //target_weight = MPertVectorslp(ssG, iv_M_lp, tp_deg);
5847  target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
5848  }
5849  delete iv_M_lp;
5850  pert_target_vector = target_weight;
5851  rChangeCurrRing(HelpRing);
5852  G = idrMoveR(ssG, TargetRing,currRing);
5853  }
5854  /*
5855  Print("\n// Perturbationwalkalg. vom Gradpaar (%d,%d):",op_deg,tp_deg);
5856  ivString(curr_weight, "new sigma");
5857  ivString(target_weight, "new tau");
5858  */
5859  while(1)
5860  {
5861  nstep ++;
5862  to = clock();
5863  /* compute an initial form ideal of <G> w.r.t. the weight vector
5864  "curr_weight" */
5865  Gomega = MwalkInitialForm(G, curr_weight);
5866 
5867 
5868 #ifdef ENDWALKS
5869  if(endwalks == 1){
5870  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
5871  idElements(G, "G");
5872  // idElements(Gomega, "Gw");
5873  headidString(G, "G");
5874  //headidString(Gomega, "Gw");
5875  }
5876 #endif
5877 
5878  tif = tif + clock()-to;
5879 
5880 #ifndef BUCHBERGER_ALG
5881  if(isNolVector(curr_weight) == 0)
5882  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5883  else
5884  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5885 #endif // BUCHBERGER_ALG
5886 
5887  oldRing = currRing;
5888 
5889  // define a new ring with ordering "(a(curr_weight),lp)
5890  if (rParameter(currRing) != NULL)
5891  DefRingPar(curr_weight);
5892  else
5893  rChangeCurrRing(VMrDefault(curr_weight)); //Aenderung 3
5894 
5895  newRing = currRing;
5896  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
5897 
5898 #ifdef ENDWALKS
5899  if(endwalks==1)
5900  {
5901  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
5902  idElements(Gomega1, "Gw");
5903  headidString(Gomega1, "headGw");
5904  PrintS("\n// compute a rGB of Gw:\n");
5905 
5906 #ifndef BUCHBERGER_ALG
5907  ivString(hilb_func, "w");
5908 #endif
5909  }
5910 #endif
5911 
5912  tim = clock();
5913  to = clock();
5914  /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
5915 #ifdef BUCHBERGER_ALG
5916  M = MstdhomCC(Gomega1);
5917 #else
5918  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5919  delete hilb_func;
5920 #endif // BUCHBERGER_ALG
5921 
5922  if(endwalks == 1){
5923  xtstd = xtstd+clock()-to;
5924 #ifdef ENDWALKS
5925  Print("\n// time for the last std(Gw) = %.2f sec\n",
5926  ((double) clock())/1000000 -((double)tim) /1000000);
5927 #endif
5928  }
5929  else
5930  tstd=tstd+clock()-to;
5931 
5932  /* change the ring to oldRing */
5933  rChangeCurrRing(oldRing);
5934  M1 = idrMoveR(M, newRing,currRing);
5935  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5936 
5937  //if(endwalks==1) PrintS("\n// Lifting is working:..");
5938 
5939  to=clock();
5940  /* compute a representation of the generators of submod (M)
5941  with respect to those of mod (Gomega).
5942  Gomega is a reduced Groebner basis w.r.t. the current ring */
5943  F = MLifttwoIdeal(Gomega2, M1, G);
5944  if(endwalks != 1)
5945  tlift = tlift+clock()-to;
5946  else
5947  xtlift=clock()-to;
5948 
5949  idDelete(&M1);
5950  idDelete(&Gomega2);
5951  idDelete(&G);
5952 
5953  /* change the ring to newRing */
5954  rChangeCurrRing(newRing);
5955  F1 = idrMoveR(F, oldRing,currRing);
5956 
5957  //if(endwalks==1)PrintS("\n// InterRed is working now:");
5958 
5959  to=clock();
5960  /* reduce the Groebner basis <G> w.r.t. new ring */
5961  G = kInterRedCC(F1, NULL);
5962  if(endwalks != 1)
5963  tred = tred+clock()-to;
5964  else
5965  xtred=clock()-to;
5966 
5967  idDelete(&F1);
5968 
5969  if(endwalks == 1)
5970  break;
5971 
5972  to=clock();
5973  /* compute a next weight vector */
5974  next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
5975  tnw=tnw+clock()-to;
5976 #ifdef PRINT_VECTORS
5977  MivString(curr_weight, target_weight, next_weight);
5978 #endif
5979 
5980  if(Overflow_Error == TRUE)
5981  {
5982  ntwC = 0;
5983  //ntestomega = 1;
5984  //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
5985  //idElements(G, "G");
5986  delete next_weight;
5987  goto FINISH_160302;
5988  }
5989  if(MivComp(next_weight, ivNull) == 1){
5990  newRing = currRing;
5991  delete next_weight;
5992  //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
5993  break;
5994  }
5995  if(MivComp(next_weight, target_weight) == 1)
5996  endwalks = 1;
5997 
5998  for(i=nV-1; i>=0; i--)
5999  (*curr_weight)[i] = (*next_weight)[i];
6000 
6001  delete next_weight;
6002  }//while
6003 
6004  if(tp_deg != 1)
6005  {
6006  FINISH_160302:
6007  if(MivSame(orig_target, exivlp) == 1)
6008  if (rParameter(currRing) != NULL)
6009  DefRingParlp();
6010  else
6011  VMrDefaultlp();
6012  else
6013  if (rParameter(currRing) != NULL)
6014  DefRingPar(orig_target);
6015  else
6016  rChangeCurrRing(VMrDefault(orig_target)); //Aenderung
6017 
6018  TargetRing=currRing;
6019  F1 = idrMoveR(G, newRing,currRing);
6020 #ifdef CHECK_IDEAL
6021  headidString(G, "G");
6022 #endif
6023 
6024 
6025  // check whether the pertubed target vector stays in the correct cone
6026  if(ntwC != 0){
6027  ntestw = test_w_in_ConeCC(F1, pert_target_vector);
6028  }
6029 
6030  if( ntestw != 1 || ntwC == 0)
6031  {
6032  /*
6033  if(ntestw != 1){
6034  ivString(pert_target_vector, "tau");
6035  PrintS("\n// ** perturbed target vector doesn't stay in cone!!");
6036  Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
6037  idElements(F1, "G");
6038  }
6039  */
6040  // LastGB is "better" than the kStd subroutine
6041  to=clock();
6042  ideal eF1;
6043  if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1){
6044  // PrintS("\n// ** calls \"std\" to compute a GB");
6045  eF1 = MstdCC(F1);
6046  idDelete(&F1);
6047  }
6048  else {
6049  // PrintS("\n// ** calls \"LastGB\" to compute a GB");
6050  rChangeCurrRing(newRing);
6051  ideal F2 = idrMoveR(F1, TargetRing,currRing);
6052  eF1 = LastGB(F2, curr_weight, tp_deg-1);
6053  F2=NULL;
6054  }
6055  xtextra=clock()-to;
6056  ring exTargetRing = currRing;
6057 
6058  rChangeCurrRing(XXRing);
6059  Eresult = idrMoveR(eF1, exTargetRing,currRing);
6060  }
6061  else{
6062  rChangeCurrRing(XXRing);
6063  Eresult = idrMoveR(F1, TargetRing,currRing);
6064  }
6065  }
6066  else {
6067  rChangeCurrRing(XXRing);
6068  Eresult = idrMoveR(G, newRing,currRing);
6069  }
6070  delete ivNull;
6071  if(tp_deg != 1)
6072  delete target_weight;
6073 
6074  if(op_deg != 1 )
6075  delete curr_weight;
6076 
6077  delete exivlp;
6078  delete last_omega;
6079 
6080 #ifdef TIME_TEST
6081  TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
6082  tnw+xtnw);
6083 
6084  Print("\n// pSetm_Error = (%d)", ErrorCheck());
6085  Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
6086 #endif
6087  return(Eresult);
6088 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
BOOLEAN ErrorCheck()
intvec * MivMatrixOrder(intvec *iv)
Definition: walk.cc:938
#define Print
Definition: emacs.cc:83
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition: walk.cc:760
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#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:2986
clock_t xtred
Definition: walk.cc:98
#define TRUE
Definition: auxiliary.h:144
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2748
#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:99
Definition: intvec.h:16
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:98
clock_t xtnw
Definition: walk.cc:98
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1061
static ideal MstdhomCC(ideal G)
Definition: walk.cc:922
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2881
static ideal MstdCC(ideal G)
Definition: walk.cc:907
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2811
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:275
intvec * MivMatrixOrderdp(int nV)
Definition: walk.cc:1397
clock_t xtlift
Definition: walk.cc:98
intvec * MivUnit(int nV)
Definition: walk.cc:1476
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:736
clock_t xtextra
Definition: walk.cc:99
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1381
intvec * Mivlp(int nR)
Definition: walk.cc:995
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
clock_t xtif
Definition: walk.cc:98
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition: walk.cc:2248
ideal Mrwalk ( ideal  Go,
intvec curr_weight,
intvec target_weight,
int  weight_rad,
int  pert_deg,
ring  baseRing 
)

Definition at line 5341 of file walk.cc.

5342 {
5343  BITSET save1 = si_opt_1; // save current options
5344  //si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5345  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5346  //si_opt_1|=(Sy_bit(OPT_REDTAIL)|Sy_bit(OPT_REDSB));
5347  Set_Error(FALSE);
5349 #ifdef TIME_TEST
5350  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5351  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5352  tinput = clock();
5353  clock_t tim;
5354 #endif
5355  nstep=0;
5356  int i,nwalk,endwalks = 0;
5357  int nV = baseRing->N;
5358 
5359  ideal Gomega, M, F, Gomega1, Gomega2, M1; //, F1;
5360  ring newRing;
5361  ring XXRing = baseRing;
5362  intvec* ivNull = new intvec(nV);
5363  intvec* curr_weight = new intvec(nV);
5364  intvec* target_weight = new intvec(nV);
5365  intvec* exivlp = Mivlp(nV);
5366  intvec* tmp_weight = new intvec(nV);
5367  for(i=0; i<nV; i++)
5368  {
5369  (*tmp_weight)[i] = (*target_M)[i];
5370  }
5371  for(i=0; i<nV; i++)
5372  {
5373  (*curr_weight)[i] = (*orig_M)[i];
5374  (*target_weight)[i] = (*target_M)[i];
5375  }
5376 #ifndef BUCHBERGER_ALG
5377  intvec* hilb_func;
5378  // to avoid (1,0,...,0) as the target vector
5379  intvec* last_omega = new intvec(nV);
5380  for(i=nV-1; i>0; i--)
5381  {
5382  (*last_omega)[i] = 1;
5383  }
5384  (*last_omega)[0] = 10000;
5385 #endif
5387 #ifdef CHECK_IDEAL_MWALK
5388  idString(Go,"Go");
5389 #endif
5390 #ifdef TIME_TEST
5391  to = clock();
5392 #endif
5393  if(orig_M->length() == nV)
5394  {
5395  newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5396  }
5397  else
5398  {
5399  newRing = VMatrDefault(orig_M);
5400  }
5401  rChangeCurrRing(newRing);
5402  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5403  baseRing = currRing;
5404 #ifdef TIME_TEST
5405  tostd = clock()-to;
5406 #endif
5407 
5408  nwalk = 0;
5409  while(1)
5410  {
5411  nwalk ++;
5412  nstep ++;
5413 #ifdef TIME_TEST
5414  to = clock();
5415 #endif
5416 #ifdef CHECK_IDEAL_MWALK
5417  idString(G,"G");
5418 #endif
5419  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5420 #ifdef TIME_TEST
5421  tif = tif + clock()-to; //time for computing initial form ideal
5422 #endif
5423 #ifdef CHECK_IDEAL_MWALK
5424  idString(Gomega,"Gomega");
5425 #endif
5426 #ifndef BUCHBERGER_ALG
5427  if(isNolVector(curr_weight) == 0)
5428  {
5429  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5430  }
5431  else
5432  {
5433  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5434  }
5435 #endif
5436  if(nwalk == 1)
5437  {
5438  if(orig_M->length() == nV)
5439  {
5440  newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5441  }
5442  else
5443  {
5444  newRing = VMatrDefault(orig_M);
5445  }
5446  }
5447  else
5448  {
5449  if(target_M->length() == nV)
5450  {
5451  newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
5452  }
5453  else
5454  {
5455  newRing = VMatrRefine(target_M,curr_weight);
5456  }
5457  }
5458  rChangeCurrRing(newRing);
5459  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5460  idDelete(&Gomega);
5461  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5462 #ifdef TIME_TEST
5463  to = clock();
5464 #endif
5465 #ifndef BUCHBERGER_ALG
5466  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5467  delete hilb_func;
5468 #else
5469  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5470 #endif
5471 #ifdef TIME_TEST
5472  tstd = tstd + clock() - to;
5473 #endif
5474  idSkipZeroes(M);
5475 #ifdef CHECK_IDEAL_MWALK
5476  PrintS("\n//** Mwalk: computed M.\n");
5477  idString(M, "M");
5478 #endif
5479  //change the ring to baseRing
5480  rChangeCurrRing(baseRing);
5481  M1 = idrMoveR(M, newRing,currRing);
5482  idDelete(&M);
5483  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5484  idDelete(&Gomega1);
5485 #ifdef TIME_TEST
5486  to = clock();
5487 #endif
5488  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega), where Gomega is a reduced Groebner basis w.r.t. the current ring
5489  F = MLifttwoIdeal(Gomega2, M1, G);
5490 #ifdef TIME_TEST
5491  tlift = tlift + clock() - to;
5492 #endif
5493 #ifdef CHECK_IDEAL_MWALK
5494  idString(F, "F");
5495 #endif
5496  idDelete(&Gomega2);
5497  idDelete(&M1);
5498  rChangeCurrRing(newRing); // change the ring to newRing
5499  G = idrMoveR(F,baseRing,currRing);
5500  idDelete(&F);
5501  baseRing = currRing;
5502 #ifdef TIME_TEST
5503  to = clock();
5504 #endif
5505  //G = kStd(F1,NULL,testHomog,NULL,NULL,0,0,NULL);
5506 #ifdef TIME_TEST
5507  tstd = tstd + clock() - to;
5508 #endif
5509  idSkipZeroes(G);
5510 #ifdef CHECK_IDEAL_MWALK
5511  idString(G, "G");
5512 #endif
5513 #ifdef TIME_TEST
5514  to = clock();
5515 #endif
5516  intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, pert_deg);//next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5517 #ifdef TIME_TEST
5518  tnw = tnw + clock() - to;
5519 #endif
5520 #ifdef PRINT_VECTORS
5521  MivString(curr_weight, target_weight, next_weight);
5522 #endif
5523  if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)// || test_w_in_ConeCC(G, target_weight) == 1 || MivComp(next_weight,curr_weight) == 1)
5524  {
5525 #ifdef CHECK_IDEAL_MWALK
5526  PrintS("\n//** Mwalk: entering last cone.\n");
5527 #endif
5528  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5529  if(target_M->length() == nV)
5530  {
5531  newRing = VMrDefault(target_weight); // define a new ring with ordering "(a(curr_weight),lp)
5532  }
5533  else
5534  {
5535  newRing = VMatrDefault(target_M);
5536  }
5537  rChangeCurrRing(newRing);
5538  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5539  idDelete(&Gomega);
5540 #ifdef CHECK_IDEAL_MWALK
5541  idString(Gomega1, "Gomega");
5542 #endif
5543  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5544 #ifdef CHECK_IDEAL_MWALK
5545  idString(M,"M");
5546 #endif
5547  rChangeCurrRing(baseRing);
5548  M1 = idrMoveR(M, newRing,currRing);
5549  idDelete(&M);
5550  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5551  idDelete(&Gomega1);
5552  F = MLifttwoIdeal(Gomega2, M1, G);
5553 #ifdef CHECK_IDEAL_MWALK
5554  idString(F,"F");
5555 #endif
5556  idDelete(&Gomega2);
5557  idDelete(&M1);
5558  rChangeCurrRing(newRing); // change the ring to newRing
5559  G = idrMoveR(F,baseRing,currRing);
5560  idDelete(&F);
5561  baseRing = currRing;
5562  si_opt_1 = save1; //set original options, e. g. option(RedSB)
5563  idSkipZeroes(G);
5564 #ifdef TIME_TEST
5565  to = clock();
5566 #endif
5567  // if(si_opt_1 == (Sy_bit(OPT_REDSB)))
5568  // {
5569  //G = kInterRedCC(G,NULL); //reduce the Groebner basis <G> w.r.t. currRing, if option(redSB) is set
5570  // }
5571 #ifdef TIME_TEST
5572  tred = tred + clock() - to;
5573 #endif
5574  idSkipZeroes(G);
5575  delete next_weight;
5576  break;
5577 #ifdef CHECK_IDEAL_MWALK
5578  PrintS("\n//** Mwalk: last cone.\n");
5579 #endif
5580  }
5581 #ifdef CHECK_IDEAL_MWALK
5582  PrintS("\n//** Mwalk: update weight vectors.\n");
5583 #endif
5584  for(i=nV-1; i>=0; i--)
5585  {
5586  (*tmp_weight)[i] = (*curr_weight)[i];
5587  (*curr_weight)[i] = (*next_weight)[i];
5588  }
5589  delete next_weight;
5590  }
5591  rChangeCurrRing(XXRing);
5592  ideal result = idrMoveR(G,baseRing,currRing);
5593  idDelete(&G);
5594 /*#ifdef CHECK_IDEAL_MWALK
5595  pDelete(&p);
5596 #endif*/
5597  delete tmp_weight;
5598  delete ivNull;
5599  delete exivlp;
5600 #ifndef BUCHBERGER_ALG
5601  delete last_omega;
5602 #endif
5603 #ifdef TIME_TEST
5604  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
5605  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5606  Print("\n//** Mwalk: Ergebnis.\n");
5607  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5608  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5609 #endif
5610  return(result);
5611 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#define FALSE
Definition: auxiliary.h:140
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2588
clock_t xtred
Definition: walk.cc:98
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2666
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3435
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:98
clock_t xtnw
Definition: walk.cc:98
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static ideal MstdCC(ideal G)
Definition: walk.cc:907
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
clock_t xtlift
Definition: walk.cc:98
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:736
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2505
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
return result
Definition: facAbsBiFact.cc:76
intvec * Mivlp(int nR)
Definition: walk.cc:995
static intvec * MWalkRandomNextWeight(ideal G, intvec *curr_weight, intvec *target_weight, int weight_rad, int pert_deg)
Definition: walk.cc:4408
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
clock_t xtif
Definition: walk.cc:98
intvec* MSimpleIV ( intvec iv)
ideal Mwalk ( ideal  Go,
intvec orig_M,
intvec target_M,
ring  baseRing 
)

Definition at line 5067 of file walk.cc.

5068 {
5069  BITSET save1 = si_opt_1; // save current options
5070  //si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
5071  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
5072  //si_opt_1|=(Sy_bit(OPT_REDTAIL)|Sy_bit(OPT_REDSB));
5073  Set_Error(FALSE);
5075 #ifdef TIME_TEST
5076  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
5077  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
5078  tinput = clock();
5079  clock_t tim;
5080 #endif
5081  nstep=0;
5082  int i,nwalk,endwalks = 0;
5083  int nV = baseRing->N;
5084 
5085  ideal Gomega, M, F, Gomega1, Gomega2, M1; //, F1;
5086  ring newRing;
5087  ring XXRing = baseRing;
5088  intvec* ivNull = new intvec(nV);
5089  intvec* curr_weight = new intvec(nV);
5090  intvec* target_weight = new intvec(nV);
5091  intvec* exivlp = Mivlp(nV);
5092  intvec* tmp_weight = new intvec(nV);
5093  for(i=0; i<nV; i++)
5094  {
5095  (*tmp_weight)[i] = (*target_M)[i];
5096  }
5097  for(i=0; i<nV; i++)
5098  {
5099  (*curr_weight)[i] = (*orig_M)[i];
5100  (*target_weight)[i] = (*target_M)[i];
5101  }
5102 #ifndef BUCHBERGER_ALG
5103  intvec* hilb_func;
5104  // to avoid (1,0,...,0) as the target vector
5105  intvec* last_omega = new intvec(nV);
5106  for(i=nV-1; i>0; i--)
5107  {
5108  (*last_omega)[i] = 1;
5109  }
5110  (*last_omega)[0] = 10000;
5111 #endif
5113 #ifdef CHECK_IDEAL_MWALK
5114  idString(Go,"Go");
5115 #endif
5116 #ifdef TIME_TEST
5117  to = clock();
5118 #endif
5119  if(orig_M->length() == nV)
5120  {
5121  newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5122  }
5123  else
5124  {
5125  newRing = VMatrDefault(orig_M);
5126  }
5127  rChangeCurrRing(newRing);
5128  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
5129  baseRing = currRing;
5130 #ifdef TIME_TEST
5131  tostd = clock()-to;
5132 #endif
5133 
5134  nwalk = 0;
5135  while(1)
5136  {
5137  nwalk ++;
5138  nstep ++;
5139 #ifdef TIME_TEST
5140  to = clock();
5141 #endif
5142 #ifdef CHECK_IDEAL_MWALK
5143  idString(G,"G");
5144 #endif
5145  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5146 #ifdef TIME_TEST
5147  tif = tif + clock()-to; //time for computing initial form ideal
5148 #endif
5149 #ifdef CHECK_IDEAL_MWALK
5150  idString(Gomega,"Gomega");
5151 #endif
5152 #ifndef BUCHBERGER_ALG
5153  if(isNolVector(curr_weight) == 0)
5154  {
5155  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
5156  }
5157  else
5158  {
5159  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
5160  }
5161 #endif
5162  if(nwalk == 1)
5163  {
5164  if(orig_M->length() == nV)
5165  {
5166  newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
5167  }
5168  else
5169  {
5170  newRing = VMatrDefault(orig_M);
5171  }
5172  }
5173  else
5174  {
5175  if(target_M->length() == nV)
5176  {
5177  newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
5178  }
5179  else
5180  {
5181  newRing = VMatrRefine(target_M,curr_weight);
5182  }
5183  }
5184  rChangeCurrRing(newRing);
5185  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5186  idDelete(&Gomega);
5187  // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
5188 #ifdef TIME_TEST
5189  to = clock();
5190 #endif
5191 #ifndef BUCHBERGER_ALG
5192  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
5193  delete hilb_func;
5194 #else
5195  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5196 #endif
5197 #ifdef TIME_TEST
5198  tstd = tstd + clock() - to;
5199 #endif
5200  idSkipZeroes(M);
5201 #ifdef CHECK_IDEAL_MWALK
5202  PrintS("\n//** Mwalk: computed M.\n");
5203  idString(M, "M");
5204 #endif
5205  //change the ring to baseRing
5206  rChangeCurrRing(baseRing);
5207  M1 = idrMoveR(M, newRing,currRing);
5208  idDelete(&M);
5209  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5210  idDelete(&Gomega1);
5211 #ifdef TIME_TEST
5212  to = clock();
5213 #endif
5214  // compute a representation of the generators of submod (M) with respect to those of mod (Gomega), where Gomega is a reduced Groebner basis w.r.t. the current ring
5215  F = MLifttwoIdeal(Gomega2, M1, G);
5216 #ifdef TIME_TEST
5217  tlift = tlift + clock() - to;
5218 #endif
5219 #ifdef CHECK_IDEAL_MWALK
5220  idString(F, "F");
5221 #endif
5222  idDelete(&Gomega2);
5223  idDelete(&M1);
5224  rChangeCurrRing(newRing); // change the ring to newRing
5225  G = idrMoveR(F,baseRing,currRing);
5226  idDelete(&F);
5227  baseRing = currRing;
5228 #ifdef TIME_TEST
5229  to = clock();
5230 #endif
5231  //G = kStd(F1,NULL,testHomog,NULL,NULL,0,0,NULL);
5232 #ifdef TIME_TEST
5233  tstd = tstd + clock() - to;
5234 #endif
5235  idSkipZeroes(G);
5236 #ifdef CHECK_IDEAL_MWALK
5237  idString(G, "G");
5238 #endif
5239 #ifdef TIME_TEST
5240  to = clock();
5241 #endif
5242  intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
5243 #ifdef TIME_TEST
5244  tnw = tnw + clock() - to;
5245 #endif
5246 #ifdef PRINT_VECTORS
5247  MivString(curr_weight, target_weight, next_weight);
5248 #endif
5249  if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)// || test_w_in_ConeCC(G, target_weight) == 1 || MivComp(next_weight,curr_weight) == 1)
5250  {
5251 #ifdef CHECK_IDEAL_MWALK
5252  PrintS("\n//** Mwalk: entering last cone.\n");
5253 #endif
5254  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
5255  if(target_M->length() == nV)
5256  {
5257  newRing = VMrDefault(target_weight); // define a new ring with ordering "(a(curr_weight),lp)
5258  }
5259  else
5260  {
5261  newRing = VMatrDefault(target_M);
5262  }
5263  rChangeCurrRing(newRing);
5264  Gomega1 = idrMoveR(Gomega, baseRing,currRing);
5265  idDelete(&Gomega);
5266 #ifdef CHECK_IDEAL_MWALK
5267  idString(Gomega1, "Gomega");
5268 #endif
5269  M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
5270 #ifdef CHECK_IDEAL_MWALK
5271  idString(M,"M");
5272 #endif
5273  rChangeCurrRing(baseRing);
5274  M1 = idrMoveR(M, newRing,currRing);
5275  idDelete(&M);
5276  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
5277  idDelete(&Gomega1);
5278  F = MLifttwoIdeal(Gomega2, M1, G);
5279 #ifdef CHECK_IDEAL_MWALK
5280  idString(F,"F");
5281 #endif
5282  idDelete(&Gomega2);
5283  idDelete(&M1);
5284  rChangeCurrRing(newRing); // change the ring to newRing
5285  G = idrMoveR(F,baseRing,currRing);
5286  idDelete(&F);
5287  baseRing = currRing;
5288  si_opt_1 = save1; //set original options, e. g. option(RedSB)
5289  idSkipZeroes(G);
5290 #ifdef TIME_TEST
5291  to = clock();
5292 #endif
5293  // if(si_opt_1 == (Sy_bit(OPT_REDSB)))
5294  // {
5295  G = kInterRedCC(G,NULL); //reduce the Groebner basis <G> w.r.t. currRing, if option(redSB) is set
5296  // }
5297 #ifdef TIME_TEST
5298  tred = tred + clock() - to;
5299 #endif
5300  idSkipZeroes(G);
5301  delete next_weight;
5302  break;
5303 #ifdef CHECK_IDEAL_MWALK
5304  PrintS("\n//** Mwalk: last cone.\n");
5305 #endif
5306  }
5307 #ifdef CHECK_IDEAL_MWALK
5308  PrintS("\n//** Mwalk: update weight vectors.\n");
5309 #endif
5310  for(i=nV-1; i>=0; i--)
5311  {
5312  (*tmp_weight)[i] = (*curr_weight)[i];
5313  (*curr_weight)[i] = (*next_weight)[i];
5314  }
5315  delete next_weight;
5316  }
5317  rChangeCurrRing(XXRing);
5318  ideal result = idrMoveR(G,baseRing,currRing);
5319  idDelete(&G);
5320 /*#ifdef CHECK_IDEAL_MWALK
5321  pDelete(&p);
5322 #endif*/
5323  delete tmp_weight;
5324  delete ivNull;
5325  delete exivlp;
5326 #ifndef BUCHBERGER_ALG
5327  delete last_omega;
5328 #endif
5329 #ifdef TIME_TEST
5330  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
5331  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
5332  Print("\n//** Mwalk: Ergebnis.\n");
5333  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
5334  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
5335 #endif
5336  return(result);
5337 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
unsigned si_opt_1
Definition: options.c:5
#define Print
Definition: emacs.cc:83
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#define FALSE
Definition: auxiliary.h:140
static ring VMatrDefault(intvec *va)
Definition: walk.cc:2588
clock_t xtred
Definition: walk.cc:98
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
int length() const
Definition: intvec.h:86
static ring VMatrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2666
static TreeM * G
Definition: janet.cc:38
#define BITSET
Definition: structs.h:17
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
BOOLEAN Overflow_Error
Definition: walk.cc:96
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
clock_t to
Definition: walk.cc:99
Definition: intvec.h:16
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3435
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:1865
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:294
clock_t xtstd
Definition: walk.cc:98
clock_t xtnw
Definition: walk.cc:98
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static ideal MstdCC(ideal G)
Definition: walk.cc:907
int nstep
kstd2.cc
Definition: walk.cc:88
#define NULL
Definition: omList.c:10
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:275
clock_t xtlift
Definition: walk.cc:98
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:736
static ring VMrRefine(intvec *va, intvec *vb)
Definition: walk.cc:2505
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
return result
Definition: facAbsBiFact.cc:76
intvec * Mivlp(int nR)
Definition: walk.cc:995
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
clock_t xtif
Definition: walk.cc:98
ideal MwalkInitialForm ( ideal  G,
intvec curr_weight 
)

Definition at line 736 of file walk.cc.

737 {
738  BOOLEAN nError = Overflow_Error;
740 
741  int i, nG = IDELEMS(G);
742  ideal Gomega = idInit(nG, 1);
743 
744  for(i=nG-1; i>=0; i--)
745  {
746  Gomega->m[i] = MpolyInitialForm(G->m[i], ivw);
747  }
748  if(Overflow_Error == FALSE)
749  {
750  Overflow_Error = nError;
751  }
752  return Gomega;
753 }
#define FALSE
Definition: auxiliary.h:140
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition: walk.cc:699
static TreeM * G
Definition: janet.cc:38
BOOLEAN Overflow_Error
Definition: walk.cc:96
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
int BOOLEAN
Definition: auxiliary.h: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 7071 of file walk.cc.

7072 {
7073 #ifdef TIME_TEST
7074  clock_t mtim = clock();
7075 #endif
7076  Set_Error(FALSE );
7078  //Print("// pSetm_Error = (%d)", ErrorCheck());
7079  //Print("\n// ring ro = %s;", rString(currRing));
7080 
7081  clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
7082 #ifdef TIME_TEST
7083  clock_t tinput = clock();
7084 #endif
7085  int nsteppert=0, i, nV = currRing->N, nwalk=0, npert_tmp=0;
7086  int *npert=(int*)omAlloc(2*nV*sizeof(int));
7087  ideal Gomega, M,F, G1, Gomega1, Gomega2, M1, F1;
7088  //ring endRing;
7089  ring newRing, oldRing, lpRing;
7090  intvec* next_weight;
7091  intvec* ivNull = new intvec(nV); //define (0,...,0)
7092  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
7093  intvec* iv_lp = Mivlp(nV); //define (1,0,...,0)
7094  ideal H0;
7095  //ideal H1;
7096  ideal H2, Glp;
7097  int nGB, endwalks = 0, nwalkpert=0, npertstep=0;
7098  intvec* Mlp = MivMatrixOrderlp(nV);
7099  intvec* vector_tmp = new intvec(nV);
7100 #ifndef BUCHBERGER_ALG
7101  intvec* hilb_func;
7102 #endif
7103  /* to avoid (1,0,...,0) as the target vector */
7104  intvec* last_omega = new intvec(nV);
7105  for(i=nV-1; i>0; i--)
7106  (*last_omega)[i] = 1;
7107  (*last_omega)[0] = 10000;
7108 
7109  // intvec* extra_curr_weight = new intvec(nV);
7110  intvec* target_weight = new intvec(nV);
7111  for(i=nV-1; i>=0; i--)
7112  (*target_weight)[i] = (*target_tmp)[i];
7113 
7114  ring XXRing = currRing;
7115  newRing = currRing;
7116 
7117  to=clock();
7118  /* compute a red. GB w.r.t. the help ring */
7119  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) = "dp"
7120  G = MstdCC(G);
7121  else
7122  {
7123  //rOrdStr(currRing) = (a(.c_w..),lp,C)
7124  if (rParameter(currRing) != NULL)
7125  DefRingPar(curr_weight);
7126  else
7127  rChangeCurrRing(VMrDefault(curr_weight)); // Aenderung 4
7128  G = idrMoveR(G, XXRing,currRing);
7129  G = MstdCC(G);
7130  }
7131  tostd=clock()-to;
7132 
7133 #ifdef REPRESENTATION_OF_SIGMA
7134  ideal Gw = MwalkInitialForm(G, curr_weight);
7135 
7136  if(islengthpoly2(Gw)==1)
7137  {
7138  intvec* MDp;
7139  if(MivComp(curr_weight, iv_dp) == 1)
7140  MDp = MatrixOrderdp(nV); //MivWeightOrderlp(iv_dp);
7141  else
7142  MDp = MivWeightOrderlp(curr_weight);
7143 
7144  curr_weight = RepresentationMatrix_Dp(G, MDp);
7145 
7146  delete MDp;
7147 
7148  ring exring = currRing;
7149 
7150  if (rParameter(currRing) != NULL)
7151  DefRingPar(curr_weight);
7152  else
7153  rChangeCurrRing(VMrDefault(curr_weight)); //Aenderung 5
7154  to=clock();
7155  Gw = idrMoveR(G, exring,currRing);
7156  G = MstdCC(Gw);
7157  Gw = NULL;
7158  tostd=tostd+clock()-to;
7159  //ivString(curr_weight,"rep. sigma");
7160  goto COMPUTE_NEW_VECTOR;
7161  }
7162 
7163  idDelete(&Gw);
7164  delete iv_dp;
7165 #endif
7166 
7167 
7168  while(1)
7169  {
7170  to=clock();
7171  /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
7172  Gomega = MwalkInitialForm(G, curr_weight);
7173  tif=tif+clock()-to;
7174 
7175 #ifndef BUCHBERGER_ALG
7176  if(isNolVector(curr_weight) == 0)
7177  hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
7178  else
7179  hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
7180 #endif // BUCHBERGER_ALG
7181 
7182  oldRing = currRing;
7183 
7184  /* define a new ring that its ordering is "(a(curr_weight),lp) */
7185  if (rParameter(currRing) != NULL)
7186  DefRingPar(curr_weight);
7187  else
7188  rChangeCurrRing(VMrDefault(curr_weight)); //Aenderung 6
7189 
7190  newRing = currRing;
7191  Gomega1 = idrMoveR(Gomega, oldRing,currRing);
7192 
7193  to=clock();
7194  /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
7195 #ifdef BUCHBERGER_ALG
7196  M = MstdhomCC(Gomega1);
7197 #else
7198  M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
7199  delete hilb_func;
7200 #endif // BUCHBERGER_ALG
7201  tstd=tstd+clock()-to;
7202 
7203  /* change the ring to oldRing */
7204  rChangeCurrRing(oldRing);
7205  M1 = idrMoveR(M, newRing,currRing);
7206  Gomega2 = idrMoveR(Gomega1, newRing,currRing);
7207 
7208  to=clock();
7209  /* compute a representation of the generators of submod (M)
7210  with respect to those of mod (Gomega).
7211  Gomega is a reduced Groebner basis w.r.t. the current ring */
7212  F = MLifttwoIdeal(Gomega2, M1, G);
7213  tlift=tlift+clock()-to;
7214 
7215  idDelete(&M1);
7216  idDelete(&Gomega2);
7217  idDelete(&G);
7218 
7219  /* change the ring to newRing */
7220  rChangeCurrRing(newRing);
7221  F1 = idrMoveR(F, oldRing,currRing);
7222 
7223  to=clock();
7224  /* reduce the Groebner basis <G> w.r.t. new ring */
7225  G = kInterRedCC(F1, NULL);
7226  tred=tred+clock()-to;
7227  idDelete(&F1);
7228 
7229 
7230  COMPUTE_NEW_VECTOR:
7231  newRing = currRing;
7232  nwalk++;
7233  nwalkpert++;
7234  to=clock();
7235  // compute a next weight vector
7236  next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
7237  tnw=tnw+clock()-to;
7238 #ifdef PRINT_VECTORS
7239  MivString(curr_weight, target_weight, next_weight);
7240 #endif
7241 
7242 
7243  /* check whether the computed intermediate weight vector is in
7244  the correct cone; sometimes it is very big e.g. s7, cyc7.
7245  If it is NOT in the correct cone, then compute directly
7246  a reduced Groebner basis with respect to the lexicographic ordering
7247  for the known Groebner basis that it is computed in the last step.
7248  */
7249  //if(test_w_in_ConeCC(G, next_weight) != 1)
7250  if(Overflow_Error == TRUE)
7251  {
7252  OMEGA_OVERFLOW_TRAN_NEW:
7253  //Print("\n// takes %d steps!", nwalk-1);
7254  //Print("\n//ring lastRing = %s;", rString(currRing));
7255 #ifdef TEST_OVERFLOW
7256  goto BE_FINISH;
7257 #endif
7258 
7259 #ifdef CHECK_IDEAL_MWALK
7260  idElements(G, "G");
7261  //headidString(G, "G");
7262 #endif
7263 
7264  if(MivSame(target_tmp, iv_lp) == 1)
7265  if (rParameter(currRing) != NULL)
7266  DefRingParlp();
7267  else
7268  VMrDefaultlp();
7269  else
7270  if (rParameter(currRing) != NULL)
7271  DefRingPar(target_tmp);
7272  else
7273  rChangeCurrRing(VMrDefault(target_tmp)); // Aenderung 8
7274 
7275  lpRing = currRing;
7276  G1 = idrMoveR(G, newRing,currRing);
7277 
7278  to=clock();
7279  /*apply kStd or LastGB to compute a lex. red. Groebner basis of <G>*/
7280  if(nP == 0 || MivSame(target_tmp, iv_lp) == 0){
7281  //Print("\n\n// calls \"std in ring r_%d = %s;", nwalk, rString(currRing));
7282  G = MstdCC(G1);//no result for qnt1
7283  }
7284  else {
7285  rChangeCurrRing(newRing);
7286  G1 = idrMoveR(G1, lpRing,currRing);
7287 
7288  //Print("\n\n// calls \"LastGB\" (%d) to compute a GB", nV-1);
7289  G = LastGB(G1, curr_weight, nV-1); //no result for kats7
7290 
7291  rChangeCurrRing(lpRing);
7292  G = idrMoveR(G, newRing,currRing);
7293  }
7294  textra=clock()-to;
7295  npert[endwalks]=nwalk-npert_tmp;
7296  npert_tmp = nwalk;
7297  endwalks ++;
7298  break;
7299  }
7300 
7301  /* check whether the computed Groebner basis is really a Groebner basis.
7302  If not, we perturb the target vector with the maximal "perturbation"
7303  degree.*/
7304  if(MivComp(next_weight, target_weight) == 1 ||
7305  MivComp(next_weight, curr_weight) == 1 )
7306  {
7307  //Print("\n//ring r_%d = %s;", nwalk, rString(currRing));
7308 
7309 
7310  //compute the number of perturbations and its step
7311  npert[endwalks]=nwalk-npert_tmp;
7312  npert_tmp = nwalk;
7313 
7314  endwalks ++;
7315 
7316  /*it is very important if the walk only uses one step, e.g. Fate, liu*/
7317  if(endwalks == 1 && MivComp(next_weight, curr_weight) == 1){
7318  rChangeCurrRing(XXRing);
7319  G = idrMoveR(G, newRing,currRing);
7320  goto FINISH;
7321  }
7322  H0 = id_Head(G,currRing);
7323 
7324  if(MivSame(target_tmp, iv_lp) == 1)
7325  if (rParameter(currRing) != NULL)
7326  DefRingParlp();
7327  else
7328  VMrDefaultlp();
7329  else
7330  if (rParameter(currRing) != NULL)
7331  DefRingPar(target_tmp);
7332  else
7333  rChangeCurrRing(VMrDefault(target_tmp)); //Aenderung 9
7334 
7335  lpRing = currRing;
7336  Glp = idrMoveR(G, newRing,currRing);
7337  H2 = idrMoveR(H0, newRing,currRing);
7338 
7339  /* Apply Lemma 2.2 in Collart et. al (1997) to check whether
7340  cone(k-1) is equal to cone(k) */
7341  nGB = 1;
7342  for(i=IDELEMS(Glp)-1; i>=0; i--)
7343  {
7344  poly t;
7345  if((t=pSub(pHead(Glp->m[i]), pCopy(H2->m[i]))) != NULL)
7346  {
7347  pDelete(&t);
7348  idDelete(&H2);//5.5.02
7349  nGB = 0; //i.e. Glp is no reduced Groebner basis
7350  break;
7351  }
7352  pDelete(&t);
7353  }
7354 
7355  idDelete(&H2);//5.5.02
7356 
7357  if(nGB == 1)
7358  {
7359  G = Glp;
7360  Glp = NULL;
7361  break;
7362  }
7363 
7364  /* perturb the target weight vector, if the vector target_tmp
7365  stays in many cones */
7366  poly p;
7367  BOOLEAN plength3 = FALSE;
7368  for(i=IDELEMS(Glp)-1; i>=0; i--)
7369  {
7370  p = MpolyInitialForm(Glp->m[i], target_tmp);
7371  if(p->next != NULL &&
7372  p->next->next != NULL &&
7373  p->next->next->next != NULL)
7374  {
7376 
7377  for(i=0; i<nV; i++)
7378  (*vector_tmp)[i] = (*target_weight)[i];
7379 
7380  delete target_weight;
7381  target_weight = MPertVectors(Glp, Mlp, nV);
7382 
7383  if(MivComp(vector_tmp, target_weight)==1)
7384  {
7385  //PrintS("\n// The old and new representaion vector are the same!!");
7386  G = Glp;
7387  newRing = currRing;
7388  goto OMEGA_OVERFLOW_TRAN_NEW;
7389  }
7390 
7391  if(Overflow_Error == TRUE)
7392  {
7393  rChangeCurrRing(newRing);
7394  G = idrMoveR(Glp, lpRing,currRing);
7395  goto OMEGA_OVERFLOW_TRAN_NEW;
7396  }
7397 
7398  plength3 = TRUE;
7399  pDelete(&p);
7400  break;
7401  }
7402  pDelete(&p);
7403  }
7404 
7405  if(plength3 == FALSE)
7406  {
7407  rChangeCurrRing(newRing);
7408  G = idrMoveR(Glp, lpRing,currRing);
7409  goto TRAN_LIFTING;
7410  }
7411 
7412 
7413  npertstep = nwalk;
7414  nwalkpert = 1;
7415  nsteppert ++;
7416 
7417  /*
7418  Print("\n// Subroutine needs (%d) steps.", nwalk);
7419  idElements(Glp, "last G in walk:");
7420  PrintS("\n// ****************************************");
7421  Print("\n// Perturb the original target vector (%d): ", nsteppert);
7422  ivString(target_weight, "new target");
7423  PrintS("\n// ****************************************\n");
7424  */
7425  rChangeCurrRing(newRing);
7426  G = idrMoveR(Glp, lpRing,currRing);
7427 
7428  delete next_weight;
7429 
7430  //Print("\n// ring rNEW = %s;", rString(currRing));
7431  goto COMPUTE_NEW_VECTOR;
7432  }
7433 
7434  TRAN_LIFTING:
7435  for(i=nV-1; i>=0; i--)
7436  (*curr_weight)[i] = (*next_weight)[i];
7437 
7438  delete next_weight;
7439  }//while
7440 #ifdef TEST_OVERFLOW
7441  BE_FINISH:
7442 #endif
7443  rChangeCurrRing(XXRing);
7444  G = idrMoveR(G, lpRing,currRing);
7445 
7446  FINISH:
7447  delete ivNull;
7448  delete next_weight;
7449  delete iv_lp;
7450  omFree(npert);
7451 
7452 #ifdef TIME_TEST
7453  Print("\n// Computation took %d steps and %.2f sec",
7454  nwalk, ((double) (clock()-mtim)/1000000));
7455 
7456  TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
7457 
7458  Print("\n// pSetm_Error = (%d)", ErrorCheck());
7459  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
7460 #endif
7461 
7462  return(G);
7463 }
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition: walk.cc:1736
BOOLEAN ErrorCheck()
#define Print
Definition: emacs.cc:83
static int MivComp(intvec *iva, intvec *ivb)
Definition: walk.cc:1813
#define FALSE
Definition: auxiliary.h:140
return P p
Definition: myNF.cc:203
intvec * MivWeightOrderlp(intvec *ivstart)
Definition: walk.cc:1416
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition: walk.cc:2986
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition: walk.cc:699
#define TRUE
Definition: auxiliary.h:144
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
int MivSame(intvec *u, intvec *v)
Definition: walk.cc:868
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition: ring.h:573
static TreeM * G
Definition: janet.cc:38
void Set_Error(BOOLEAN f)
Definition: walk.cc:94
#define omAlloc(size)
Definition: omAllocDecl.h:210
BOOLEAN Overflow_Error
Definition: walk.cc:96
static void VMrDefaultlp(void)
Definition: walk.cc:2748
#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:99
Definition: intvec.h:16
#define pSub(a, b)
Definition: polys.h:258
static int islengthpoly2(ideal G)
Definition: walk.cc:3287
#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:1865
int i
Definition: cfEzgcd.cc:123
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition: walk.cc:1061
#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:922
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void DefRingParlp(void)
Definition: walk.cc:2881
static ideal MstdCC(ideal G)
Definition: walk.cc:907
#define NULL
Definition: omList.c:10
static void DefRingPar(intvec *va)
Definition: walk.cc:2811
static ideal kInterRedCC(ideal F, ideal Q)
Definition: walk.cc:275
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
#define pDelete(p_ptr)
Definition: polys.h:157
intvec * MivUnit(int nV)
Definition: walk.cc:1476
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:736
int BOOLEAN
Definition: auxiliary.h:131
void idDelete(ideal *h)
delete an ideal
Definition: ideals.h:31
intvec * MivMatrixOrderlp(int nV)
Definition: walk.cc:1381
intvec * Mivlp(int nR)
Definition: walk.cc:995
static ring VMrDefault(intvec *va)
Definition: walk.cc:2360
#define pCopy(p)
return a copy of the poly
Definition: polys.h:156
intvec* TranMPertVectorslp ( ideal  G)