walk.h File Reference

#include <kernel/structs.h>

Go to the source code of this file.

Functions
ideal	MwalkInitialForm (ideal G, intvec *curr_weight)
intvec *	MwalkNextWeight (intvec *curr_weight, intvec *target_weight, ideal G)
int	MivSame (intvec *u, intvec *v)
int	M3ivSame (intvec *next_weight, intvec *u, intvec *v)
intvec *	Mivdp (int nR)
intvec *	Mivlp (int nR)
intvec *	MivMatrixOrder (intvec *iv)
intvec *	MivMatrixOrderdp (int iv)
intvec *	MPertVectors (ideal G, intvec *ivtarget, int pdeg)
intvec *	MPertVectorslp (ideal G, intvec *ivtarget, int pdeg)
intvec *	MivMatrixOrderlp (int nV)
intvec *	Mfpertvector (ideal G, intvec *iv)
intvec *	MivUnit (int nV)
intvec *	MivWeightOrderlp (intvec *ivstart)
intvec *	MivWeightOrderdp (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)
intvec *	MkInterRedNextWeight (intvec *iva, intvec *ivb, ideal G)
intvec *	MPertNextWeight (intvec *iva, ideal G, int deg)
intvec *	Mivperttarget (ideal G, int ndeg)
intvec *	MSimpleIV (intvec *iv)
ideal	Mwalk (ideal Go, intvec *orig_M, intvec *target_M, ring baseRing, int reduction, int printout)
ideal	Mrwalk (ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int pert_deg, int reduction, int printout)
ideal	Mpwalk (ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP, int reduction, int printout)
ideal	Mprwalk (ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int op_deg, int tp_deg, int nP, int reduction, int printout)
ideal	Mfwalk (ideal G, intvec *ivstart, intvec *ivtarget, int reduction, int printout)
ideal	Mfrwalk (ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad, int reduction, int printout)
intvec *	TranMPertVectorslp (ideal G)
ideal	TranMImprovwalk (ideal Go, intvec *curr_weight, intvec *target_weight, int nP)
ideal	MAltwalk1 (ideal G, int op, int tp, intvec *curr_weight, intvec *target_weight)
ideal	MAltwalk2 (ideal G, intvec *curr_weight, intvec *target_weight)

Function Documentation

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

Definition at line 920 of file walk.cc.

{
  assume(temp->length() == u->length() && u->length() == v->length());

  if((MivSame(temp, u)) == 1)
  {
    return 0;
  }
  if((MivSame(temp, v)) == 1)
  {
    return 1;
  }
  return 2;
}

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

Definition at line 9470 of file walk.cc.

{
  Set_Error(FALSE  );
  Overflow_Error = FALSE;
#ifdef TIME_TEST
  BOOLEAN nOverflow_Error = FALSE;
#endif
  // Print("// pSetm_Error = (%d)", ErrorCheck());

  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
  xftinput = clock();
  clock_t tostd, tproc;

  nstep = 0;
  int i, nV = currRing->N;
  int nwalk=0, endwalks=0;
  int op_tmp = op_deg;
  ideal Gomega, M, F, G, Gomega1, Gomega2, M1, F1;
  ring newRing, oldRing;
  intvec* next_weight;
  intvec* iv_M_dp;
  intvec* ivNull = new intvec(nV);
  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
  intvec* exivlp = Mivlp(nV);
  //intvec* extra_curr_weight = new intvec(nV);
#ifndef  BUCHBERGER_ALG
  intvec* hilb_func;
#endif
  intvec* cw_tmp = curr_weight;

  // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=nV-1; i>0; i--)
  {
    (*last_omega)[i] = 1;
  }
  (*last_omega)[0] = 10000;

  ring XXRing = currRing;

  to=clock();
  /* compute a pertubed weight vector of the original weight vector.
     The perturbation degree is recursive decrease until that vector
     stays inn the correct cone. */
  while(1)
  {
    if(Overflow_Error == FALSE)
    {
      if(MivComp(curr_weight, iv_dp) == 1)
      {
      //rOrdStr(currRing) = "dp"
        if(op_tmp == op_deg)
        {
          G = MstdCC(Go);
          if(op_deg != 1)
          {
            iv_M_dp = MivMatrixOrderdp(nV);
          }
        }
      }
    }
    else
    {
      if(op_tmp == op_deg)
      {
        //rOrdStr(currRing) = (a(...),lp,C)
        if (rParameter(currRing) != NULL)
        {
          DefRingPar(cw_tmp);
        }
        else
        {
          rChangeCurrRing(VMrDefault(cw_tmp));
        }
        G = idrMoveR(Go, XXRing,currRing);
        G = MstdCC(G);
        if(op_deg != 1)
          iv_M_dp = MivMatrixOrder(cw_tmp);
      }
    }
    Overflow_Error = FALSE;
    if(op_deg != 1)
    {
      curr_weight = MPertVectors(G, iv_M_dp, op_deg);
    }
    else
    {
      curr_weight =  cw_tmp;
      break;
    }
    if(Overflow_Error == FALSE)
    {
      break;
    }
    Overflow_Error = TRUE;
    op_deg --;
  }
  tostd=clock()-to;

  if(op_tmp != 1 )
    delete iv_M_dp;
  delete iv_dp;

  if(currRing->order[0] == ringorder_a)
    goto NEXT_VECTOR;

  while(1)
  {
    nwalk ++;
    nstep ++;

    to = clock();
    // compute an initial form ideal of <G> w.r.t. "curr_vector"
    Gomega = MwalkInitialForm(G, curr_weight);
    xtif=xtif+clock()-to;
#if 0
    if(Overflow_Error == TRUE)
    {
      for(i=nV-1; i>=0; i--)
        (*curr_weight)[i] = (*extra_curr_weight)[i];
      delete extra_curr_weight;

      newRing = currRing;
      goto MSTD_ALT1;
    }
#endif
#ifndef  BUCHBERGER_ALG
    if(isNolVector(curr_weight) == 0)
    {
      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    }
    else
    {
      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    }
#endif // BUCHBERGER_ALG

    oldRing = currRing;

    // define a new ring which ordering is "(a(curr_weight),lp)
    if (rParameter(currRing) != NULL)
    {
      DefRingPar(curr_weight);
    }
    else
    {
      rChangeCurrRing(VMrDefault(curr_weight));
    }
    newRing = currRing;
    Gomega1 = idrMoveR(Gomega, oldRing,currRing);

    to=clock();
    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef  BUCHBERGER_ALG
    M = MstdhomCC(Gomega1);
#else
    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    delete hilb_func;
#endif // BUCHBERGER_ALG
    xtstd=xtstd+clock()-to;

    // change the ring to oldRing
    rChangeCurrRing(oldRing);
    M1 =  idrMoveR(M, newRing,currRing);
    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);

    to=clock();
    // compute a reduced Groebner basis of <G> w.r.t. "newRing" by the lifting process
    F = MLifttwoIdeal(Gomega2, M1, G);
    xtlift=xtlift+clock()-to;

    idDelete(&M1);
    idDelete(&Gomega2);
    idDelete(&G);

    // change the ring to newRing
    rChangeCurrRing(newRing);
    F1 = idrMoveR(F, oldRing,currRing);
    if (oldRing!=IDRING(currRingHdl)) rDelete(oldRing); // do not delete the global currRing
    oldRing=NULL;

    to=clock();
    // reduce the Groebner basis <G> w.r.t. new ring
    G = kInterRedCC(F1, NULL);
    xtred=xtred+clock()-to;
    idDelete(&F1);

    if(endwalks == 1)
    {
      break;
    }
  NEXT_VECTOR:
    to=clock();
    // compute a next weight vector
    next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
    xtnw=xtnw+clock()-to;
#ifdef PRINT_VECTORS
    MivString(curr_weight, target_weight, next_weight);
#endif
    if(Overflow_Error == TRUE)
    {
      newRing = currRing;

      if (rParameter(currRing) != NULL)
      {
        DefRingPar(target_weight);
      }
      else
      {
        rChangeCurrRing(VMrDefault(target_weight));
      }
      F1 = idrMoveR(G, newRing,currRing);
      G = MstdCC(F1);
      idDelete(&F1);
      newRing = currRing;
      break; //for while
    }


    /* G is the wanted Groebner basis if next_weight == curr_weight */
    if(MivComp(next_weight, ivNull) == 1)
    {
      newRing = currRing;
      delete next_weight;
      break; //for while
    }

    if(MivComp(next_weight, target_weight) == 1)
    {
      if(tp_deg == 1 || MivSame(target_weight, exivlp) == 0)
        endwalks = 1;
      else
      {
       // MSTD_ALT1:
#ifdef TIME_TEST
        nOverflow_Error = Overflow_Error;
#endif
        tproc = clock()-xftinput;

        //Print("\n//  main routine takes %d steps and calls \"Mpwalk\" (1,%d):", nwalk,  tp_deg);

        // compute the red. GB of <G> w.r.t. the lex order by the "recursive-modified" perturbation walk alg (1,tp_deg)
        G = Mpwalk_MAltwalk1(G, curr_weight, tp_deg);
        delete next_weight;
        break; // for while
      }
    }

    //NOT Changed, to free memory
    for(i=nV-1; i>=0; i--)
    {
      //(*extra_curr_weight)[i] = (*curr_weight)[i];
      (*curr_weight)[i] = (*next_weight)[i];
    }
    delete next_weight;
  }//while

  rChangeCurrRing(XXRing);
  ideal result = idrMoveR(G, newRing,currRing);
  id_Delete(&G, newRing);

  delete ivNull;
  if(op_deg != 1 )
  {
    delete curr_weight;
  }
  delete exivlp;
#ifdef TIME_TEST
/*
  Print("\n// \"Main procedure\"  took %d steps, %.2f sec. and Overflow_Error(%d)",
        nwalk, ((double) tproc)/1000000, nOverflow_Error);

  TimeStringFractal(xftinput, tostd, xtif, xtstd,xtextra, xtlift, xtred, xtnw);
*/
 // Print("\n// pSetm_Error = (%d)", ErrorCheck());
 // Print("\n// Overflow_Error? (%d)", Overflow_Error);
 // Print("\n// Awalk1 took %d steps.\n", nstep);
#endif
  return(result);
}

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

Definition at line 4235 of file walk.cc.

{
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //BOOLEAN nOverflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
  xftinput = clock();
  clock_t tostd, tproc;
#endif
  nstep = 0;
  int i, nV = currRing->N;
  int nwalk=0, endwalks=0;
  // int nhilb = 1;
  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
  //ideal  G1;
  //ring endRing;
  ring newRing, oldRing;
  intvec* ivNull = new intvec(nV);
  intvec* next_weight;
  //intvec* extra_curr_weight = new intvec(nV);
  //intvec* hilb_func;
  intvec* exivlp = Mivlp(nV);
  ring XXRing = currRing;

  //Print("\n// ring r_input = %s;", rString(currRing));
#ifdef TIME_TEST
  to = clock();
#endif
  /* compute the reduced Groebner basis of the given ideal w.r.t.
     a "fast" monomial order, e.g. degree reverse lex. order (dp) */
  G = MstdCC(Go);
#ifdef TIME_TEST
  tostd=clock()-to;

  Print("\n// Computation of the first std took = %.2f sec",
        ((double) tostd)/1000000);
#endif
  if(currRing->order[0] == ringorder_a)
  {
    goto NEXT_VECTOR;
  }
  while(1)
  {
    nwalk ++;
    nstep ++;
#ifdef TIME_TEST
    to = clock();
#endif
    /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
    Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
    xtif=xtif+clock()-to;
#endif
/*
    if(Overflow_Error == TRUE)
    {
      for(i=nV-1; i>=0; i--)
        (*curr_weight)[i] = (*extra_curr_weight)[i];
      delete extra_curr_weight;
      goto LAST_GB_ALT2;
    }
*/
    oldRing = currRing;

    /* define a new ring that its ordering is "(a(curr_weight),lp) */
    if (rParameter(currRing) != NULL)
    {
      DefRingPar(curr_weight);
    }
    else
    {
      rChangeCurrRing(VMrDefault(curr_weight));
    }
    newRing = currRing;
    Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef TIME_TEST
    to = clock();
#endif
    /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
    M = MstdhomCC(Gomega1);
#ifdef TIME_TEST
    xtstd=xtstd+clock()-to;
#endif
    /* change the ring to oldRing */
    rChangeCurrRing(oldRing);
    M1 =  idrMoveR(M, newRing,currRing);
    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
    to = clock();
#endif
    /* compute the reduced Groebner basis of <G> w.r.t. "newRing"
       by the liftig process */
    F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
    xtlift=xtlift+clock()-to;
#endif
    idDelete(&M1);
    idDelete(&Gomega2);
    idDelete(&G);

    /* change the ring to newRing */
    rChangeCurrRing(newRing);
    F1 = idrMoveR(F, oldRing,currRing);
#ifdef TIME_TEST
    to = clock();
#endif
    /* reduce the Groebner basis <G> w.r.t. newRing */
    G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
    xtred=xtred+clock()-to;
#endif
    idDelete(&F1);

    if(endwalks == 1)
      break;

  NEXT_VECTOR:
#ifdef TIME_TEST
    to = clock();
#endif
    /* compute a next weight vector */
    next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
    xtnw=xtnw+clock()-to;
#endif
#ifdef PRINT_VECTORS
    MivString(curr_weight, target_weight, next_weight);
#endif

    if(Overflow_Error == TRUE)
    {
      /*
        ivString(next_weight, "omega");
        PrintS("\n// ** The weight vector does NOT stay in Cone!!\n");
      */
#ifdef TEST_OVERFLOW
      goto  TEST_OVERFLOW_OI;
#endif

      newRing = currRing;
      if (rParameter(currRing) != NULL)
      {
        DefRingPar(target_weight);
      }
      else
      {
        rChangeCurrRing(VMrDefault(target_weight)); // Aenderung
      }
      F1 = idrMoveR(G, newRing,currRing);
      G = MstdCC(F1);
      idDelete(&F1);
      newRing = currRing;
      break;
    }

    if(MivComp(next_weight, ivNull) == 1)
    {
      newRing = currRing;
      delete next_weight;
      break;
    }

    if(MivComp(next_weight, target_weight) == 1)
    {
      if(MivSame(target_weight, exivlp)==1)
      {
     // LAST_GB_ALT2:
        //nOverflow_Error = Overflow_Error;
#ifdef TIME_TEST
        tproc = clock()-xftinput;
#endif
        //Print("\n// takes %d steps and calls the recursion of level 2:",  nwalk);
        /* call the changed perturbation walk algorithm with degree 2 */
        G = Rec_LastGB(G, curr_weight, target_weight, 2,1);
        newRing = currRing;
        delete next_weight;
        break;
      }
      endwalks = 1;
    }

    for(i=nV-1; i>=0; i--)
    {
      //(*extra_curr_weight)[i] = (*curr_weight)[i];
      (*curr_weight)[i] = (*next_weight)[i];
    }
    delete next_weight;
  }
#ifdef TEST_OVERFLOW
 TEST_OVERFLOW_OI:
#endif
  rChangeCurrRing(XXRing);
  G = idrMoveR(G, newRing,currRing);
  delete ivNull;
  delete exivlp;

#ifdef TIME_TEST
  /*Print("\n// \"Main procedure\"  took %d steps dnd %.2f sec. Overflow_Error (%d)",
        nwalk, ((double) tproc)/1000000, nOverflow_Error);
*/
  TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);

  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// Overflow_Error? (%d)", nOverflow_Error);
  //Print("\n// Awalk2 took %d steps!!", nstep);
#endif

  return(G);
}

intvec* Mfpertvector	(	ideal	G,
		intvec *	iv
	)

Definition at line 1518 of file walk.cc.

{
  int i, j, nG = IDELEMS(G);
  int nV = currRing->N;
  int niv = nV*nV;


  // Calculate maxA = Max(A2) + Max(A3) + ... + Max(AnV),
  // where the Ai are the i-te rows of the matrix 'targer_ord'.
  int ntemp, maxAi, maxA=0;
  for(i=1; i<nV; i++)
  {
    maxAi = (*ivtarget)[i*nV];
    if(maxAi<0)
    {
      maxAi = -maxAi;
    }
    for(j=i*nV+1; j<(i+1)*nV; j++)
    {
      ntemp = (*ivtarget)[j];
      if(ntemp < 0)
      {
        ntemp = -ntemp;
      }
      if(ntemp > maxAi)
      {
        maxAi = ntemp;
      }
    }
    maxA = maxA + maxAi;
  }
  intvec* ivUnit = Mivdp(nV);

  // Calculate inveps = 1/eps, where 1/eps > deg(p)*maxA for all p in G.
  mpz_t tot_deg; mpz_init(tot_deg);
  mpz_t maxdeg; mpz_init(maxdeg);
  mpz_t inveps; mpz_init(inveps);


  for(i=nG-1; i>=0; i--)
  {
    mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
    if (mpz_cmp(maxdeg,  tot_deg) > 0 )
    {
      mpz_set(tot_deg, maxdeg);
    }
  }

  delete ivUnit;
  //inveps = (tot_deg * maxA) + 1;
  mpz_mul_ui(inveps, tot_deg, maxA);
  mpz_add_ui(inveps, inveps, 1);

  // takes  "small" inveps
#ifdef INVEPS_SMALL_IN_FRACTAL
  if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
  {
    mpz_cdiv_q_ui(inveps, inveps, nV);
  }
  // choose the small inverse epsilon
#endif

  // PrintLn();  mpz_out_str(stdout, 10, inveps);

  // Calculate the perturbed target orders:
  mpz_t *ivtemp=(mpz_t *)omAlloc(nV*sizeof(mpz_t));
  mpz_t *pert_vector=(mpz_t *)omAlloc(niv*sizeof(mpz_t));

  for(i=0; i < nV; i++)
  {
    mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
    mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
  }

  mpz_t ztmp; mpz_init(ztmp);
  // BOOLEAN isneg = FALSE;

  for(i=1; i<nV; i++)
  {
    for(j=0; j<nV; j++)
    {
      mpz_mul(ztmp, inveps, ivtemp[j]);
      if((*ivtarget)[i*nV+j]<0)
      {
        mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
      }
      else
      {
        mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
      }
    }

    for(j=0; j<nV; j++)
    {
      mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
    }
  }

  // 2147483647 is max. integer representation in SINGULAR
  mpz_t sing_int;
  mpz_init_set_ui(sing_int,  2147483647);

  intvec* result = new intvec(niv);
  intvec* result1 = new intvec(niv);
  BOOLEAN nflow = FALSE;

  // computes gcd
  mpz_set(ztmp, pert_vector[0]);
  for(i=0; i<niv; i++)
  {
    mpz_gcd(ztmp, ztmp, pert_vector[i]);
    if(mpz_cmp_si(ztmp, 1)==0)
    {
      break;
    }
  }

  for(i=0; i<niv; i++)
  {
    mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
    (* result)[i] = mpz_get_si(pert_vector[i]);
  }

  CHECK_OVERFLOW:

  for(i=0; i<niv; i++)
  {
    if(mpz_cmp(pert_vector[i], sing_int)>0)
    {
      if(nflow == FALSE)
      {
        Xnlev = i / nV;
        nflow = TRUE;
        Overflow_Error = TRUE;
        Print("\n// Xlev = %d and the %d-th element is", Xnlev,  i+1);
        PrintS("\n// ** OVERFLOW in \"Mfpertvector\": ");
        mpz_out_str( stdout, 10, pert_vector[i]);
        PrintS(" is greater than 2147483647 (max. integer representation)");
        Print("\n//  So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
      }
    }
  }
  if(Overflow_Error == TRUE)
  {
    ivString(result, "new_vector");
  }
  omFree(pert_vector);
  omFree(ivtemp);
  mpz_clear(ztmp);
  mpz_clear(tot_deg);
  mpz_clear(maxdeg);
  mpz_clear(inveps);
  mpz_clear(sing_int);

  rComplete(currRing);
  for(j=0; j<IDELEMS(G); j++)
  {
    poly p=G->m[j];
    while(p!=NULL)
    {
      p_Setm(p,currRing);
      pIter(p);
    }
  }
  return result;
}

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

Definition at line 8104 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  //check that weight radius is valid
  if(weight_rad < 0)
  {
    Werror("Invalid radius.\n");
    return NULL;
  }
  if(reduction == 0)
  {
    si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
    si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  }
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// ring ro = %s;", rString(currRing));

  nnflow = 0;
  Xngleich = 0;
  Xcall = 0;
#ifdef TIME_TEST
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
  xftinput = clock();
#endif
  ring  oldRing = currRing;
  int i, nV = currRing->N;
  XivNull = new intvec(nV);
  Xivinput = ivtarget;
  ngleich = 0;
#ifdef TIME_TEST
  to=clock();
#endif
  ideal I = MstdCC(G);
  G = NULL;
#ifdef TIME_TEST
  xftostd=clock()-to;
#endif
  Xsigma = ivstart;

  Xnlev=nV;

#ifdef FIRST_STEP_FRACTAL
  ideal Gw = MwalkInitialForm(I, ivstart);
  for(i=IDELEMS(Gw)-1; i>=0; i--)
  {
    if((Gw->m[i]!=NULL) // len >=0
    && (Gw->m[i]->next!=NULL) // len >=1
    && (Gw->m[i]->next->next!=NULL)) // len >=2
    {
      intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
      intvec* Mdp;
      if(ivstart->length() == nV)
      {
        if(MivSame(ivstart, iv_dp) != 1)
          Mdp = MivWeightOrderdp(ivstart);
        else
          Mdp = MivMatrixOrderdp(nV);
      }
      else
      {
        Mdp = ivstart;
      }

      Xsigma = Mfpertvector(I, Mdp);
      Overflow_Error = FALSE;

      delete Mdp;
      delete iv_dp;
      break;
    }
  }
  idDelete(&Gw);
#endif

  ideal I1;
  intvec* Mlp;
  Xivlp = Mivlp(nV);

  if(ivtarget->length() == nV)
  {
    if(MivComp(ivtarget, Xivlp)  != 1)
    {
      if (rParameter(currRing) != NULL)
        DefRingPar(ivtarget);
      else
        rChangeCurrRing(VMrDefault(ivtarget));

      I1 = idrMoveR(I, oldRing,currRing);
      Mlp = MivWeightOrderlp(ivtarget);
      Xtau = Mfpertvector(I1, Mlp);
    }
    else
    {
      if (rParameter(currRing) != NULL)
        DefRingParlp();
      else
        VMrDefaultlp();

      I1 = idrMoveR(I, oldRing,currRing);
      Mlp =  MivMatrixOrderlp(nV);
      Xtau = Mfpertvector(I1, Mlp);
    }
  }
  else
  {
    rChangeCurrRing(VMatrDefault(ivtarget));
    I1 = idrMoveR(I,oldRing,currRing);
    Mlp =  ivtarget;
    Xtau = Mfpertvector(I1, Mlp);
  }
  delete Mlp;
  Overflow_Error = FALSE;

  //ivString(Xsigma, "Xsigma");
  //ivString(Xtau, "Xtau");

  id_Delete(&I, oldRing);
  ring tRing = currRing;
  if(ivtarget->length() == nV)
  {
/*
    if (rParameter(currRing) != NULL)
      DefRingPar(ivstart);
    else
      rChangeCurrRing(VMrDefault(ivstart));
*/
    rChangeCurrRing(VMrRefine(ivtarget,ivstart));
  }
  else
  {
    //rChangeCurrRing(VMatrDefault(ivstart));
    rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
  }

  I = idrMoveR(I1,tRing,currRing);
#ifdef TIME_TEST
  to=clock();
#endif
  ideal J = MstdCC(I);
  idDelete(&I);
#ifdef TIME_TEST
  xftostd=xftostd+clock()-to;
#endif
  ideal resF;
  ring helpRing = currRing;

  J = rec_r_fractal_call(J,1,ivtarget,weight_rad,reduction,printout);
  //idString(J,"//*** Mfrwalk: J");
  //Print("\n//** Mfrwalk hier (1)\n");
  rChangeCurrRing(oldRing);
  //Print("\n//** Mfrwalk hier (2)\n");
  resF = idrMoveR(J, helpRing,currRing);
  //Print("\n//** Mfrwalk hier (3)\n");
  //idSkipZeroes(resF);
  //Print("\n//** Mfrwalk hier (4)\n");
  si_opt_1 = save1; //set original options, e. g. option(RedSB)
  delete Xivlp;
  //delete Xsigma;
  delete Xtau;
  delete XivNull;
  //Print("\n//** Mfrwalk hier (5)\n");
#ifdef TIME_TEST
  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
                    xtlift, xtred, xtnw);


 // Print("\n// pSetm_Error = (%d)", ErrorCheck());
  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
#endif
  //Print("\n//** Mfrwalk hier (6)\n");
  //idString(resF,"resF");
  //Print("\n//** Mfrwalk hier (7)\n");
  return(resF);
}

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

Definition at line 7923 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  if(reduction == 0)
  {
    si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
    //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  }
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// ring ro = %s;", rString(currRing));

  nnflow = 0;
  Xngleich = 0;
  Xcall = 0;
#ifdef TIME_TEST
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
  xftinput = clock();
#endif
  ring  oldRing = currRing;
  int i, nV = currRing->N;
  XivNull = new intvec(nV);
  Xivinput = ivtarget;
  ngleich = 0;
#ifdef TIME_TEST
  to=clock();
#endif
  ideal I = MstdCC(G);
  G = NULL;
#ifdef TIME_TEST
  xftostd=clock()-to;
#endif
  Xsigma = ivstart;

  Xnlev=nV;

#ifdef FIRST_STEP_FRACTAL
  ideal Gw = MwalkInitialForm(I, ivstart);
  for(i=IDELEMS(Gw)-1; i>=0; i--)
  {
    if((Gw->m[i]!=NULL) // len >=0
    && (Gw->m[i]->next!=NULL) // len >=1
    && (Gw->m[i]->next->next!=NULL)) // len >=2
    {
      intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
      intvec* Mdp;
      if(ivstart->length() == nV)
      {
        if(MivSame(ivstart, iv_dp) != 1)
          Mdp = MivWeightOrderdp(ivstart);
        else
          Mdp = MivMatrixOrderdp(nV);
      }
      else
      {
        Mdp = ivstart;
      }

      Xsigma = Mfpertvector(I, Mdp);
      Overflow_Error = FALSE;

      delete Mdp;
      delete iv_dp;
      break;
    }
  }
  idDelete(&Gw);
#endif

  ideal I1;
  intvec* Mlp;
  Xivlp = Mivlp(nV);

  if(ivtarget->length() == nV)
  {
    if(MivComp(ivtarget, Xivlp)  != 1)
    {
      if (rParameter(currRing) != NULL)
        DefRingPar(ivtarget);
      else
        rChangeCurrRing(VMrDefault(ivtarget));

      I1 = idrMoveR(I, oldRing,currRing);
      Mlp = MivWeightOrderlp(ivtarget);
      Xtau = Mfpertvector(I1, Mlp);
    }
    else
    {
      if (rParameter(currRing) != NULL)
        DefRingParlp();
      else
        VMrDefaultlp();

      I1 = idrMoveR(I, oldRing,currRing);
      Mlp =  MivMatrixOrderlp(nV);
      Xtau = Mfpertvector(I1, Mlp);
    }
  }
  else
  {
    rChangeCurrRing(VMatrDefault(ivtarget));
    I1 = idrMoveR(I,oldRing,currRing);
    Mlp =  ivtarget;
    Xtau = Mfpertvector(I1, Mlp);
  }
  delete Mlp;
  Overflow_Error = FALSE;

  //ivString(Xsigma, "Xsigma");
  //ivString(Xtau, "Xtau");

  id_Delete(&I, oldRing);
  ring tRing = currRing;
  if(ivtarget->length() == nV)
  {
/*
    if (rParameter(currRing) != NULL)
      DefRingPar(ivstart);
    else
      rChangeCurrRing(VMrDefault(ivstart));
*/
    rChangeCurrRing(VMrRefine(ivtarget,ivstart));
  }
  else
  {
    //rChangeCurrRing(VMatrDefault(ivstart));
    rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
  }

  I = idrMoveR(I1,tRing,currRing);
#ifdef TIME_TEST
  to=clock();
#endif
  ideal J = MstdCC(I);
  idDelete(&I);
#ifdef TIME_TEST
  xftostd=xftostd+clock()-to;
#endif
  ideal resF;
  ring helpRing = currRing;

  J = rec_fractal_call(J,1,ivtarget,reduction,printout);
  //idString(J,"//** Mfwalk: J");
  rChangeCurrRing(oldRing);
  //Print("\n//Mfwalk: (2)\n");
  resF = idrMoveR(J, helpRing,currRing);
  //Print("\n//Mfwalk: (3)\n");
  idSkipZeroes(resF);
  //Print("\n//Mfwalk: (4)\n");

  si_opt_1 = save1; //set original options, e. g. option(RedSB)
  delete Xivlp;
  //delete Xsigma;
  delete Xtau;
  delete XivNull;
  //Print("\n//Mfwalk: (5)\n");
#ifdef TIME_TEST
  TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
                    xtlift, xtred, xtnw);


  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
  Print("\n// the numbers of Overflow_Error (%d)", nnflow);
#endif
  //Print("\n//Mfwalk: (6)\n");
  //idString(resF,"//** Mfwalk: resF");
  return(idCopy(resF));
}

ideal MidLift	(	ideal	Gomega,
		ideal	M
	)

intvec* Mivdp

(

int

nR

)

Definition at line 1013 of file walk.cc.

{
  int i;
  intvec* ivm = new intvec(nR);

  for(i=nR-1; i>=0; i--)
  {
    (*ivm)[i] = 1;
  }
  return ivm;
}

intvec* Mivlp

(

int

nR

)

Definition at line 1028 of file walk.cc.

{
  intvec* ivm = new intvec(nR);
  (*ivm)[0] = 1;

  return ivm;
}

intvec* MivMatrixOrder

(

intvec *

iv

)

Definition at line 969 of file walk.cc.

{
  int i, nR = iv->length();

  intvec* ivm = new intvec(nR*nR);

  for(i=0; i<nR; i++)
  {
    (*ivm)[i] = (*iv)[i];
  }
  for(i=1; i<nR; i++)
  {
    (*ivm)[i*nR+i-1] = 1;
  }
  return ivm;
}

intvec* MivMatrixOrderdp

(

int

iv

)

Definition at line 1423 of file walk.cc.

{
  int i;
  intvec* ivM = new intvec(nV*nV);

  for(i=0; i<nV; i++)
  {
    (*ivM)[i] = 1;
  }
  for(i=1; i<nV; i++)
  {
    (*ivM)[(i+1)*nV - i] = -1;
  }
  return(ivM);
}

intvec* MivMatrixOrderlp

(

int

nV

)

Definition at line 1407 of file walk.cc.

{
  int i;
  intvec* ivM = new intvec(nV*nV);

  for(i=0; i<nV; i++)
  {
    (*ivM)[i*nV + i] = 1;
  }
  return(ivM);
}

intvec* Mivperttarget	(	ideal	G,
		int	ndeg
	)

int MivSame	(	intvec *	u,
		intvec *	v
	)

Definition at line 899 of file walk.cc.

{
  assume(u->length() == v->length());

  int i, niv = u->length();

  for (i=0; i<niv; i++)
  {
    if ((*u)[i] != (*v)[i])
    {
      return 0;
    }
  }
  return 1;
}

intvec* MivUnit

(

int

nV

)

Definition at line 1502 of file walk.cc.

{
  int i;
  intvec* ivM = new intvec(nV);
  for(i=nV-1; i>=0; i--)
  {
    (*ivM)[i] = 1;
  }
  return(ivM);
}

intvec* MivWeightOrderdp

(

intvec *

ivstart

)

Definition at line 1462 of file walk.cc.

{
  int i;
  int nV = ivstart->length();
  intvec* ivM = new intvec(nV*nV);

  for(i=0; i<nV; i++)
  {
    (*ivM)[i] = (*ivstart)[i];
  }
  for(i=0; i<nV; i++)
  {
    (*ivM)[nV+i] = 1;
  }
  for(i=2; i<nV; i++)
  {
    (*ivM)[(i+1)*nV - i] = -1;
  }
  return(ivM);
}

intvec* MivWeightOrderlp

(

intvec *

ivstart

)

Definition at line 1442 of file walk.cc.

{
  int i;
  int nV = ivstart->length();
  intvec* ivM = new intvec(nV*nV);

  for(i=0; i<nV; i++)
  {
    (*ivM)[i] = (*ivstart)[i];
  }
  for(i=1; i<nV; i++)
  {
    (*ivM)[i*nV + i-1] = 1;
  }
  return(ivM);
}

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

Definition at line 2577 of file walk.cc.

{
  intvec* tmp = new intvec(iva->length());
  intvec* result;

  if(G == NULL)
  {
    return tmp;
  }
  if(MivComp(iva, ivb) == 1)
  {
    return tmp;
  }
  result = MwalkNextWeightCC(iva, ivb, G);

  if(MivComp(result, iva) == 1)
  {
    delete result;
    return tmp;
  }

  delete tmp;
  return result;
}

ideal MLiftLmalG	(	ideal	L,
		ideal	G
	)

ideal MLiftLmalGMin	(	ideal	L,
		ideal	G
	)

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

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

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

Definition at line 1094 of file walk.cc.

{
  // ivtarget is a matrix order of a degree reverse lex. order
  int nV = currRing->N;
  //assume(pdeg <= nV && pdeg >= 0);

  int i, j, nG = IDELEMS(G);
  intvec* v_null =  new intvec(nV);

  // Check that the perturbed degree is valid
  if(pdeg > nV || pdeg <= 0)
  {
    WerrorS("//** The perturbed degree is wrong!!");
    return v_null;
  }
  delete v_null;

  if(pdeg == 1)
  {
    return ivtarget;
  }
  mpz_t *pert_vector = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
  mpz_t *pert_vector1 = (mpz_t*)omAlloc(nV*sizeof(mpz_t));

  for(i=0; i<nV; i++)
  {
    mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
    mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
  }
  // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
  // where the Ai are the i-te rows of the matrix target_ord.
  int ntemp, maxAi, maxA=0;
  for(i=1; i<pdeg; i++)
  {
    maxAi = (*ivtarget)[i*nV];
    if(maxAi<0)
    {
      maxAi = -maxAi;
    }
    for(j=i*nV+1; j<(i+1)*nV; j++)
    {
      ntemp = (*ivtarget)[j];
      if(ntemp < 0)
      {
        ntemp = -ntemp;
      }
      if(ntemp > maxAi)
      {
        maxAi = ntemp;
      }
    }
    maxA += maxAi;
  }

  // Calculate inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.

  intvec* ivUnit = Mivdp(nV);

  mpz_t tot_deg; mpz_init(tot_deg);
  mpz_t maxdeg; mpz_init(maxdeg);
  mpz_t inveps; mpz_init(inveps);


  for(i=nG-1; i>=0; i--)
  {
     mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
     if (mpz_cmp(maxdeg,  tot_deg) > 0 )
     {
       mpz_set(tot_deg, maxdeg);
     }
  }

  delete ivUnit;
  mpz_mul_ui(inveps, tot_deg, maxA);
  mpz_add_ui(inveps, inveps, 1);


  // takes  "small" inveps
#ifdef INVEPS_SMALL_IN_MPERTVECTOR
  if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
  {
    //  Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", mpz_get_si(inveps), pdeg);
    mpz_fdiv_q_ui(inveps, inveps, pdeg);
    // mpz_out_str(stdout, 10, inveps);
  }
#else
  // PrintS("\n// the \"big\" inverse epsilon: ");
  mpz_out_str(stdout, 10, inveps);
#endif

  // pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg,
  // pert_vector := A1
  for( i=1; i < pdeg; i++ )
  {
    for(j=0; j<nV; j++)
    {
      mpz_mul(pert_vector[j], pert_vector[j], inveps);
      if((*ivtarget)[i*nV+j]<0)
      {
        mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
      }
      else
      {
        mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
      }
    }
  }

  // 2147483647 is max. integer representation in SINGULAR
  mpz_t sing_int;
  mpz_init_set_ui(sing_int,  2147483647);

  mpz_t check_int;
  mpz_init_set_ui(check_int,  100000);

  mpz_t ztemp;
  mpz_init(ztemp);
  mpz_set(ztemp, pert_vector[0]);
  for(i=1; i<nV; i++)
  {
    mpz_gcd(ztemp, ztemp, pert_vector[i]);
    if(mpz_cmp_si(ztemp, 1)  == 0)
    {
      break;
    }
  }
  if(mpz_cmp_si(ztemp, 1) != 0)
  {
    for(i=0; i<nV; i++)
    {
      mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
    }
  }

  for(i=0; i<nV; i++)
  {
    if(mpz_cmp(pert_vector[i], check_int)>=0)
    {
      for(j=0; j<nV; j++)
      {
        mpz_fdiv_q_ui(pert_vector1[j], pert_vector[j], 100);
      }
    }
  }

  intvec* result = new intvec(nV);

  int ntrue=0;

  for(i=0; i<nV; i++)
  {
    (*result)[i] = mpz_get_si(pert_vector1[i]);
    if(mpz_cmp(pert_vector1[i], sing_int)>=0)
    {
      ntrue++;
    }
  }
  if(ntrue > 0 || test_w_in_ConeCC(G,result)==0)
  {
    ntrue=0;
    for(i=0; i<nV; i++)
    {
      (*result)[i] = mpz_get_si(pert_vector[i]);
      if(mpz_cmp(pert_vector[i], sing_int)>=0)
      {
        ntrue++;
        if(Overflow_Error == FALSE)
        {
          Overflow_Error = TRUE;
          PrintS("\n// ** OVERFLOW in \"MPertvectors\": ");
          mpz_out_str( stdout, 10, pert_vector[i]);
          PrintS(" is greater than 2147483647 (max. integer representation)");
          Print("\n//  So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
        }
      }
    }

    if(Overflow_Error == TRUE)
    {
      ivString(result, "pert_vector");
      Print("\n// %d element(s) of it is overflow!!", ntrue);
    }
  }

  mpz_clear(ztemp);
  mpz_clear(sing_int);
  mpz_clear(check_int);
  omFree(pert_vector);
  omFree(pert_vector1);
  mpz_clear(tot_deg);
  mpz_clear(maxdeg);
  mpz_clear(inveps);

  rComplete(currRing);
  for(j=0; j<IDELEMS(G); j++)
  {
    poly p=G->m[j];
    while(p!=NULL)
    {
      p_Setm(p,currRing); pIter(p);
    }
  }
  return result;
}

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

Definition at line 1305 of file walk.cc.

{
  // ivtarget is a matrix order of the lex. order
  int nV = currRing->N;
  //assume(pdeg <= nV && pdeg >= 0);

  int i, j, nG = IDELEMS(G);
  intvec* pert_vector =  new intvec(nV);

  //Checking that the perturbated degree is valid
  if(pdeg > nV || pdeg <= 0)
  {
    WerrorS("//** The perturbed degree is wrong!!");
    return pert_vector;
  }
  for(i=0; i<nV; i++)
  {
    (*pert_vector)[i]=(*ivtarget)[i];
  }
  if(pdeg == 1)
  {
    return pert_vector;
  }
  // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
  // where the Ai are the i-te rows of the matrix target_ord.
  int ntemp, maxAi, maxA=0;
  for(i=1; i<pdeg; i++)
  {
    maxAi = (*ivtarget)[i*nV];
    for(j=i*nV+1; j<(i+1)*nV; j++)
    {
      ntemp = (*ivtarget)[j];
      if(ntemp > maxAi)
      {
        maxAi = ntemp;
      }
    }
    maxA += maxAi;
  }

  // Calculate inveps := 1/eps, where 1/eps > deg(p)*max1 for all p in G.
  int inveps, tot_deg = 0, maxdeg;

  intvec* ivUnit = Mivdp(nV);//19.02
  for(i=nG-1; i>=0; i--)
  {
    // maxdeg = pTotaldegree(G->m[i], currRing); //it's wrong for ex1,2,rose
    maxdeg = MwalkWeightDegree(G->m[i], ivUnit);
    if (maxdeg > tot_deg )
    {
      tot_deg = maxdeg;
    }
  }
  delete ivUnit;

  inveps = (tot_deg * maxA) + 1;

#ifdef INVEPS_SMALL_IN_FRACTAL
  //  Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", inveps, pdeg);
  if(inveps > pdeg && pdeg > 3)
  {
    inveps = inveps / pdeg;
  }
  // Print(" %d", inveps);
#else
  PrintS("\n// the \"big\" inverse epsilon %d", inveps);
#endif

  // Pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg
  for ( i=1; i < pdeg; i++ )
  {
    for(j=0; j<nV; j++)
    {
      (*pert_vector)[j] = inveps*((*pert_vector)[j]) + (*ivtarget)[i*nV+j];
    }
  }

  int temp = (*pert_vector)[0];
  for(i=1; i<nV; i++)
  {
    temp = gcd(temp, (*pert_vector)[i]);
    if(temp == 1)
    {
      break;
    }
  }
  if(temp != 1)
  {
    for(i=0; i<nV; i++)
    {
      (*pert_vector)[i] = (*pert_vector)[i] / temp;
    }
  }

  intvec* result = pert_vector;
  delete pert_vector;
  return result;
}

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

Definition at line 6283 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  if(reduction == 0)
  {
    si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
    si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  }
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
  clock_t  tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
  xtextra=0;
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
  tinput = clock();

  clock_t tim;
#endif
  nstep = 0;
  int i, ntwC=1, ntestw=1, nV = currRing->N; //polylength

  //check that weight radius is valid
  if(weight_rad < 0)
  {
    Werror("Invalid radius.\n");
    return NULL;
  }

  //check that perturbation degree is valid
  if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
  {
    Werror("Invalid perturbation degree.\n");
    return NULL;
  }

  BOOLEAN endwalks = FALSE;

  ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
  ring newRing, oldRing, TargetRing;
  intvec* iv_M;
  intvec* iv_M_dp;
  intvec* iv_M_lp;
  intvec* exivlp = Mivlp(nV);
  intvec* curr_weight = new intvec(nV);
  intvec* target_weight = new intvec(nV);
  for(i=0; i<nV; i++)
  {
    (*curr_weight)[i] = (*orig_M)[i];
    (*target_weight)[i] = (*target_M)[i];
  }
  intvec* orig_target = target_weight;
  intvec* pert_target_vector = target_weight;
  intvec* ivNull = new intvec(nV);
  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
#ifndef BUCHBERGER_ALG
  intvec* hilb_func;
#endif
  intvec* next_weight;

  // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=nV-1; i>0; i--)
    (*last_omega)[i] = 1;
  (*last_omega)[0] = 10000;

  ring XXRing = currRing;

  // perturbs the original vector
  if(orig_M->length() == nV)
  {
    if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
    {
#ifdef TIME_TEST
  to = clock();
#endif
      G = MstdCC(Go);
#ifdef TIME_TEST
      tostd = clock()-to;
#endif
      if(op_deg != 1)
      {
        iv_M_dp = MivMatrixOrderdp(nV);
        curr_weight = MPertVectors(G, iv_M_dp, op_deg);
      }
    }
    else
    {
      //define ring order := (a(curr_weight),lp);
      if (rParameter(currRing) != NULL)
        DefRingPar(curr_weight);
      else
        rChangeCurrRing(VMrDefault(curr_weight));

      G = idrMoveR(Go, XXRing,currRing);
#ifdef TIME_TEST
  to = clock();
#endif
      G = MstdCC(G);
#ifdef TIME_TEST
      tostd = clock()-to;
#endif
      if(op_deg != 1)
      {
        iv_M_dp = MivMatrixOrder(curr_weight);
        curr_weight = MPertVectors(G, iv_M_dp, op_deg);
      }
    }
  }
  else
  {
    rChangeCurrRing(VMatrDefault(orig_M));
    G = idrMoveR(Go, XXRing,currRing);
#ifdef TIME_TEST
    to = clock();
#endif
    G = MstdCC(G);
#ifdef TIME_TEST
    tostd = clock()-to;
#endif
    if(op_deg != 1)
    {
      curr_weight = MPertVectors(G, orig_M, op_deg);
    }
  }

  delete iv_dp;
  if(op_deg != 1) delete iv_M_dp;

  ring HelpRing = currRing;

  // perturbs the target weight vector
  if(target_M->length() == nV)
  {
    if(tp_deg > 1 && tp_deg <= nV)
    {
      if (rParameter(currRing) != NULL)
        DefRingPar(target_weight);
      else
        rChangeCurrRing(VMrDefault(target_weight));

      TargetRing = currRing;
      ssG = idrMoveR(G,HelpRing,currRing);
      if(MivSame(target_weight, exivlp) == 1)
      {
        iv_M_lp = MivMatrixOrderlp(nV);
        target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
      }
      else
      {
        iv_M_lp = MivMatrixOrder(target_weight);
        target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
      }
      delete iv_M_lp;
      pert_target_vector = target_weight;
      rChangeCurrRing(HelpRing);
      G = idrMoveR(ssG, TargetRing,currRing);
    }
  }
  else
  {
    if(tp_deg > 1 && tp_deg <= nV)
    {
      rChangeCurrRing(VMatrDefault(target_M));
      TargetRing = currRing;
      ssG = idrMoveR(G,HelpRing,currRing);
      target_weight = MPertVectors(ssG, target_M, tp_deg);
    }
  }
  if(printout > 0)
  {
    Print("\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
    ivString(curr_weight, "//** Mprwalk: new current weight");
    ivString(target_weight, "//** Mprwalk: new target weight");
  }

#ifdef TIME_TEST
  to = clock();
#endif
  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
  tif = tif + clock()-to; //time for computing initial form ideal
#endif

  while(1)
  {
    nstep ++;
#ifdef CHECK_IDEAL_MWALK
    if(printout > 1)
    {
      idString(Gomega,"//** Mprwalk: Gomega");
    }
#endif

    if(reduction == 0 && nstep > 1)
    {
      FF = middleOfCone(G,Gomega);
      if(FF != NULL)
      {
        idDelete(&G);
        G = idCopy(FF);
        idDelete(&FF);
        goto NEXT_VECTOR;
      }
    }

#ifdef ENDWALKS
    if(endwalks == TRUE)
    {
      if(printout > 0)
      {
        Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
        //idElements(G, "G");
        //headidString(G, "G");
      }
    }
#endif

#ifndef  BUCHBERGER_ALG
    if(isNolVector(curr_weight) == 0)
      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    else
      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
#endif // BUCHBERGER_ALG

    oldRing = currRing;

    if(target_M->length() == nV)
    {/*
      // define a new ring with ordering "(a(curr_weight),lp)
      if (rParameter(currRing) != NULL)
        DefRingPar(curr_weight);
      else
        rChangeCurrRing(VMrDefault(curr_weight));
*/
      rChangeCurrRing(VMrRefine(target_M,curr_weight));
    }
    else
    {
      rChangeCurrRing(VMatrRefine(target_M,curr_weight));
    }
    newRing = currRing;
    Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef ENDWALKS
    if(endwalks == TRUE)
    {
      if(printout > 0)
      {
        Print("\n// ring r%d = %s;\n", nstep, rString(currRing));

        //idElements(Gomega1, "Gw");
        //headidString(Gomega1, "headGw");

        PrintS("\n// compute a rGB of Gw:\n");
      }
#ifndef  BUCHBERGER_ALG
      ivString(hilb_func, "w");
#endif
    }
#endif
#ifdef TIME_TEST
    tim = clock();
    to = clock();
#endif
    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef  BUCHBERGER_ALG
    M = MstdhomCC(Gomega1);
#else
    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    delete hilb_func;
#endif
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(M,"//** Mprwalk: M");
    }
#endif
#ifdef TIME_TEST
    if(endwalks == TRUE)
    {
      xtstd = xtstd+clock()-to;
#ifdef ENDWALKS
      Print("\n// time for the last std(Gw)  = %.2f sec\n",
            ((double) clock())/1000000 -((double)tim) /1000000);
#endif
    }
    else
      tstd=tstd+clock()-to;
#endif
    /* change the ring to oldRing */
    rChangeCurrRing(oldRing);
    M1 =  idrMoveR(M, newRing,currRing);
    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
    to=clock();
#endif
    /* compute a representation of the generators of submod (M)
       with respect to those of mod (Gomega).
       Gomega is a reduced Groebner basis w.r.t. the current ring */
    F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
    if(endwalks == FALSE)
      tlift = tlift+clock()-to;
    else
      xtlift=clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(F,"//** Mprwalk: F");
    }
#endif

    idDelete(&M1);
    idDelete(&Gomega2);
    idDelete(&G);

    // change the ring to newRing
    rChangeCurrRing(newRing);
    if(reduction == 0)
    {
      G = idrMoveR(F,oldRing,currRing);
    }
    else
    {
      F1 = idrMoveR(F, oldRing,currRing);
      if(printout > 2)
      {
        PrintS("\n //** Mprwalk: reduce the Groebner basis.\n");
      }
#ifdef TIME_TEST
      to=clock();
#endif
      G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
      if(endwalks == FALSE)
        tred = tred+clock()-to;
      else
        xtred=clock()-to;
#endif
      idDelete(&F1);
    }

    if(endwalks == TRUE)
      break;

    NEXT_VECTOR:
#ifdef TIME_TEST
    to = clock();
#endif
    next_weight = next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
    tnw = tnw + clock() - to;
#endif

#ifdef TIME_TEST
    to = clock();
#endif
    // compute an initial form ideal of <G> w.r.t. "next_vector"
    Gomega = MwalkInitialForm(G, next_weight);
#ifdef TIME_TEST
    tif = tif + clock()-to; //time for computing initial form ideal
#endif

    //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
    if(lengthpoly(Gomega) > 0)
    {
      if(printout > 1)
      {
        Print("\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
      }
      // low-dimensional facet of the cone
      delete next_weight;
      if(target_M->length() == nV)
      {
        iv_M = MivMatrixOrder(curr_weight);
      }
      else
      {
        iv_M = MivMatrixOrderRefine(curr_weight,target_M);
      }
#ifdef TIME_TEST
      to = clock();
#endif
      next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, op_deg);
#ifdef TIME_TEST
      tnw = tnw + clock() - to;
#endif
      idDelete(&Gomega);
#ifdef TIME_TEST
      to = clock();
#endif
      Gomega = MwalkInitialForm(G, next_weight);
#ifdef TIME_TEST
      tif = tif + clock()-to; //time for computing initial form ideal
#endif
      delete iv_M;
    }

#ifdef PRINT_VECTORS
    if(printout > 0)
    {
      MivString(curr_weight, target_weight, next_weight);
    }
#endif

    if(Overflow_Error == TRUE)
    {
      ntwC = 0;
      //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
      //idElements(G, "G");
      delete next_weight;
      goto FINISH_160302;
    }
    if(MivComp(next_weight, ivNull) == 1){
      newRing = currRing;
      delete next_weight;
      //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
      break;
    }
    if(MivComp(next_weight, target_weight) == 1)
      endwalks = TRUE;

    for(i=nV-1; i>=0; i--)
      (*curr_weight)[i] = (*next_weight)[i];

    delete next_weight;
  }// end of while-loop

  if(tp_deg != 1)
  {
    FINISH_160302:
    if(target_M->length() == nV)
    {
      if(MivSame(orig_target, exivlp) == 1)
        if (rParameter(currRing) != NULL)
          DefRingParlp();
        else
          VMrDefaultlp();
      else
        if (rParameter(currRing) != NULL)
          DefRingPar(orig_target);
        else
          rChangeCurrRing(VMrDefault(orig_target));
    }
    else
    {
      rChangeCurrRing(VMatrDefault(target_M));
    }
    TargetRing=currRing;
    F1 = idrMoveR(G, newRing,currRing);

    // check whether the pertubed target vector stays in the correct cone
    if(ntwC != 0)
    {
      ntestw = test_w_in_ConeCC(F1, pert_target_vector);
    }
    if(ntestw != 1 || ntwC == 0)
    {
      if(ntestw != 1 && printout > 2)
      {
#ifdef PRINT_VECTORS
        ivString(pert_target_vector, "tau");
#endif
        PrintS("\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
        Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
        //idElements(F1, "G");
      }
      // LastGB is "better" than the kStd subroutine
#ifdef TIME_TEST
      to=clock();
#endif
      ideal eF1;
      if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1 || target_M->length() != nV)
      {
        if(printout > 2)
        {
          PrintS("\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
        }
        eF1 = MstdCC(F1);
        idDelete(&F1);
      }
      else
      {
        if(printout > 2)
        {
          PrintS("\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
        }
        rChangeCurrRing(newRing);
        ideal F2 = idrMoveR(F1, TargetRing,currRing);
        eF1 = LastGB(F2, curr_weight, tp_deg-1);
        F2=NULL;
      }
#ifdef TIME_TEST
      xtextra=clock()-to;
#endif
      ring exTargetRing = currRing;

      rChangeCurrRing(XXRing);
      Eresult = idrMoveR(eF1, exTargetRing,currRing);
    }
    else
    {
      rChangeCurrRing(XXRing);
      Eresult = idrMoveR(F1, TargetRing,currRing);
    }
  }
  else
  {
    rChangeCurrRing(XXRing);
    Eresult = idrMoveR(G, newRing,currRing);
  }
  si_opt_1 = save1; //set original options, e. g. option(RedSB)
  delete ivNull;
  if(tp_deg != 1)
    delete target_weight;

  if(op_deg != 1 )
    delete curr_weight;

  delete exivlp;
  delete last_omega;

#ifdef TIME_TEST
  TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
             tnw+xtnw);

  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep,  Overflow_Error);
#endif

  if(printout > 0)
  {
    Print("\n//** Mprwalk: Perturbation Walk took %d steps.\n", nstep);
  }
  return(Eresult);
}

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

Definition at line 5848 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  if(reduction == 0)
  {
    si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
    si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  }
  Set_Error(FALSE  );
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
  clock_t  tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
  xtextra=0;
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
  tinput = clock();

  clock_t tim;
#endif
  nstep = 0;
  int i, ntwC=1, ntestw=1,  nV = currRing->N;

  //check that perturbation degree is valid
  if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
  {
    Werror("Invalid perturbation degree.\n");
    return NULL;
  }

  BOOLEAN endwalks = FALSE;
  ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
  ring newRing, oldRing, TargetRing;
  intvec* iv_M_dp;
  intvec* iv_M_lp;
  intvec* exivlp = Mivlp(nV);
  intvec* orig_target = target_weight;
  intvec* pert_target_vector = target_weight;
  intvec* ivNull = new intvec(nV);
  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
#ifndef BUCHBERGER_ALG
  intvec* hilb_func;
#endif
  intvec* next_weight;

  // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=nV-1; i>0; i--)
    (*last_omega)[i] = 1;
  (*last_omega)[0] = 10000;

  ring XXRing = currRing;
#ifdef TIME_TEST
  to = clock();
#endif
  // perturbs the original vector
  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
  {
    G = MstdCC(Go);
#ifdef TIME_TEST
    tostd = clock()-to;
#endif
    if(op_deg != 1){
      iv_M_dp = MivMatrixOrderdp(nV);
      //ivString(iv_M_dp, "iv_M_dp");
      curr_weight = MPertVectors(G, iv_M_dp, op_deg);
    }
  }
  else
  {
    //define ring order := (a(curr_weight),lp);
/*
    if (rParameter(currRing) != NULL)
      DefRingPar(curr_weight);
    else
      rChangeCurrRing(VMrDefault(curr_weight));
*/
    rChangeCurrRing(VMrRefine(target_weight,curr_weight));

    G = idrMoveR(Go, XXRing,currRing);
    G = MstdCC(G);
#ifdef TIME_TEST
    tostd = clock()-to;
#endif
    if(op_deg != 1){
      iv_M_dp = MivMatrixOrder(curr_weight);
      curr_weight = MPertVectors(G, iv_M_dp, op_deg);
    }
  }
  delete iv_dp;
  if(op_deg != 1) delete iv_M_dp;

  ring HelpRing = currRing;

  // perturbs the target weight vector
  if(tp_deg > 1 && tp_deg <= nV)
  {
/*
    if (rParameter(currRing) != NULL)
      DefRingPar(target_weight);
    else
      rChangeCurrRing(VMrDefault(target_weight));
*/
    rChangeCurrRing(VMrRefine(target_weight,curr_weight));

    TargetRing = currRing;
    ssG = idrMoveR(G,HelpRing,currRing);
    if(MivSame(target_weight, exivlp) == 1)
    {
      iv_M_lp = MivMatrixOrderlp(nV);
      target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
    }
    else
    {
      iv_M_lp = MivMatrixOrder(target_weight);
      target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
    }
    delete iv_M_lp;
    pert_target_vector = target_weight;
    rChangeCurrRing(HelpRing);
    G = idrMoveR(ssG, TargetRing,currRing);
  }
  if(printout > 0)
  {
    Print("\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
#ifdef PRINT_VECTORS
    ivString(curr_weight, "//** Mpwalk: new current weight");
    ivString(target_weight, "//** Mpwalk: new target weight");
#endif
  }
  while(1)
  {
    nstep ++;
#ifdef TIME_TEST
    to = clock();
#endif
    // compute an initial form ideal of <G> w.r.t. the weight vector
    // "curr_weight"
    Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
    tif = tif + clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
    if(printout > 1)
    {
      idString(Gomega,"//** Mpwalk: Gomega");
    }
#endif
    if(reduction == 0 && nstep > 1)
    {
      FF = middleOfCone(G,Gomega);
      if(FF != NULL)
      {
        idDelete(&G);
        G = idCopy(FF);
        idDelete(&FF);
        goto NEXT_VECTOR;
      }
    }

#ifdef ENDWALKS
    if(endwalks == TRUE)
    {
      if(printout > 0)
      {
        Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
      }
      //idElements(G, "G");
      //headidString(G, "G");
    }
#endif

#ifndef  BUCHBERGER_ALG
    if(isNolVector(curr_weight) == 0)
      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    else
      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
#endif // BUCHBERGER_ALG

    oldRing = currRing;

    // define a new ring with ordering "(a(curr_weight),lp)
/*
    if (rParameter(currRing) != NULL)
      DefRingPar(curr_weight);
    else
      rChangeCurrRing(VMrDefault(curr_weight));
*/
    rChangeCurrRing(VMrRefine(target_weight,curr_weight));

    newRing = currRing;
    Gomega1 = idrMoveR(Gomega, oldRing,currRing);

#ifdef ENDWALKS
    if(endwalks==TRUE)
    {
      if(printout > 0)
      {
        Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
        //idElements(Gomega1, "Gw");
        //headidString(Gomega1, "headGw");
        PrintS("\n// compute a rGB of Gw:\n");
      }
#ifndef  BUCHBERGER_ALG
      ivString(hilb_func, "w");
#endif
    }
#endif
#ifdef TIME_TEST
    tim = clock();
    to = clock();
#endif
    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef  BUCHBERGER_ALG
    M = MstdhomCC(Gomega1);
#else
    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    delete hilb_func;
#endif

    if(endwalks == TRUE)
    {
#ifdef TIME_TEST
      xtstd = xtstd+clock()-to;
#endif
#ifdef ENDWALKS
      if(printout > 1)
      {
        Print("\n// time for the last std(Gw)  = %.2f sec\n",
            ((double) clock())/1000000 -((double)tim) /1000000);
      }
#endif
    }
    else
    {
#ifdef TIME_TEST
      tstd=tstd+clock()-to;
#endif
    }
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(M,"//** Mpwalk: M");
    }
#endif
    // change the ring to oldRing
    rChangeCurrRing(oldRing);
    M1 =  idrMoveR(M, newRing,currRing);
    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
    to=clock();
#endif
    /* compute a representation of the generators of submod (M)
       with respect to those of mod (Gomega).
       Gomega is a reduced Groebner basis w.r.t. the current ring */
    F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
    if(endwalks == FALSE)
      tlift = tlift+clock()-to;
    else
      xtlift=clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(F,"//** Mpwalk: F");
    }
#endif

    idDelete(&M1);
    idDelete(&Gomega2);
    idDelete(&G);

    // change the ring to newRing
    rChangeCurrRing(newRing);
    if(reduction == 0)
    {
      G = idrMoveR(F,oldRing,currRing);
    }
    else
    {
      F1 = idrMoveR(F, oldRing,currRing);
      if(printout > 2)
      {
        PrintS("\n //** Mpwalk: reduce the Groebner basis.\n");
      }
#ifdef TIME_TEST
      to=clock();
#endif
      G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
      if(endwalks == FALSE)
        tred = tred+clock()-to;
      else
        xtred=clock()-to;
#endif
      idDelete(&F1);
    }
    if(endwalks == TRUE)
      break;

    NEXT_VECTOR:
#ifdef TIME_TEST
    to=clock();
#endif
    // compute a next weight vector
    next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
    tnw=tnw+clock()-to;
#endif
#ifdef PRINT_VECTORS
    if(printout > 0)
    {
      MivString(curr_weight, target_weight, next_weight);
    }
#endif

    if(Overflow_Error == TRUE)
    {
      ntwC = 0;
      //ntestomega = 1;
      //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
      //idElements(G, "G");
      delete next_weight;
      goto FINISH_160302;
    }
    if(MivComp(next_weight, ivNull) == 1){
      newRing = currRing;
      delete next_weight;
      //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
      break;
    }
    if(MivComp(next_weight, target_weight) == 1)
      endwalks = TRUE;

    for(i=nV-1; i>=0; i--)
      (*curr_weight)[i] = (*next_weight)[i];

    delete next_weight;
  }//end of while-loop

  if(tp_deg != 1)
  {
  FINISH_160302:
    if(MivSame(orig_target, exivlp) == 1) {
    /*  if (rParameter(currRing) != NULL)
        DefRingParlp();
      else
        VMrDefaultlp();
    else
      if (rParameter(currRing) != NULL)
        DefRingPar(orig_target);
      else*/
        rChangeCurrRing(VMrDefault(orig_target));
    }
    TargetRing=currRing;
    F1 = idrMoveR(G, newRing,currRing);
/*
#ifdef CHECK_IDEAL_MWALK
      headidString(G, "G");
#endif
*/

    // check whether the pertubed target vector stays in the correct cone
    if(ntwC != 0){
      ntestw = test_w_in_ConeCC(F1, pert_target_vector);
    }

    if( ntestw != 1 || ntwC == 0)
    {
      if(ntestw != 1 && printout >2)
      {
        ivString(pert_target_vector, "tau");
        PrintS("\n// ** perturbed target vector doesn't stay in cone!!");
        Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
        //idElements(F1, "G");
      }
      // LastGB is "better" than the kStd subroutine
      to=clock();
      ideal eF1;
      if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1){
        // PrintS("\n// ** calls \"std\" to compute a GB");
        eF1 = MstdCC(F1);
        idDelete(&F1);
      }
      else {
        // PrintS("\n// ** calls \"LastGB\" to compute a GB");
        rChangeCurrRing(newRing);
        ideal F2 = idrMoveR(F1, TargetRing,currRing);
        eF1 = LastGB(F2, curr_weight, tp_deg-1);
        F2=NULL;
      }
      xtextra=clock()-to;
      ring exTargetRing = currRing;

      rChangeCurrRing(XXRing);
      Eresult = idrMoveR(eF1, exTargetRing,currRing);
    }
    else{
      rChangeCurrRing(XXRing);
      Eresult = idrMoveR(F1, TargetRing,currRing);
    }
  }
  else {
    rChangeCurrRing(XXRing);
    Eresult = idrMoveR(G, newRing,currRing);
  }
  si_opt_1 = save1; //set original options, e. g. option(RedSB)
  delete ivNull;
  if(tp_deg != 1)
    delete target_weight;

  if(op_deg != 1 )
    delete curr_weight;

  delete exivlp;
  delete last_omega;

#ifdef TIME_TEST
  TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
             tnw+xtnw);

  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep,  Overflow_Error);
#endif
  if(printout > 0)
  {
    Print("\n//** Mpwalk: Perturbation Walk took %d steps.\n", nstep);
  }
  return(Eresult);
}

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

Definition at line 5503 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  if(reduction == 0)
  {
    si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
    si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  }

  Set_Error(FALSE);
  Overflow_Error = FALSE;
  BOOLEAN endwalks = FALSE;
#ifdef TIME_TEST
  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
  tinput = clock();
  clock_t tim;
#endif
  nstep=0;
  int i,nwalk;//polylength;
  int nV = currRing->N;

  //check that weight radius is valid
  if(weight_rad < 0)
  {
    Werror("Invalid radius.\n");
    return NULL;
  }

  //check that perturbation degree is valid
  if(pert_deg > nV || pert_deg < 1)
  {
    Werror("Invalid perturbation degree.\n");
    return NULL;
  }

  ideal Gomega, M, F,FF, Gomega1, Gomega2, M1;
  ring newRing;
  ring targetRing;
  ring baseRing = currRing;
  ring XXRing = currRing;
  intvec* iv_M;
  intvec* ivNull = new intvec(nV);
  intvec* curr_weight = new intvec(nV);
  intvec* target_weight = new intvec(nV);
  intvec* next_weight= new intvec(nV);

  for(i=0; i<nV; i++)
  {
    (*curr_weight)[i] = (*orig_M)[i];
    (*target_weight)[i] = (*target_M)[i];
  }

#ifndef BUCHBERGER_ALG
  intvec* hilb_func;
   // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=nV-1; i>0; i--)
  {
    (*last_omega)[i] = 1;
  }
  (*last_omega)[0] = 10000;
#endif
  rComplete(currRing);

  if(target_M->length() == nV)
  {
    targetRing = VMrDefault(target_weight); // define the target ring
  }
  else
  {
    targetRing = VMatrDefault(target_M);
  }
  if(orig_M->length() == nV)
  {
    //newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
    newRing=VMrRefine(target_weight, curr_weight);
  }
  else
  {
    newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
  }
  rChangeCurrRing(newRing);
#ifdef TIME_TEST
  to = clock();
#endif
  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
#ifdef TIME_TEST
  tostd = clock()-to;
#endif
  baseRing = currRing;
  nwalk = 0;

#ifdef TIME_TEST
  to = clock();
#endif
  Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
  tif = tif + clock()-to; //time for computing initial form ideal
#endif

  while(1)
  {
    nwalk ++;
    nstep ++;
#ifdef CHECK_IDEAL_MWALK
    if(printout > 1)
    {
      idString(Gomega,"//** Mrwalk: Gomega");
    }
#endif
    if(reduction == 0)
    {
      FF = middleOfCone(G,Gomega);
      if(FF != NULL)
      {
        idDelete(&G);
        G = idCopy(FF);
        idDelete(&FF);
        goto NEXT_VECTOR;
      }
    }
#ifndef  BUCHBERGER_ALG
    if(isNolVector(curr_weight) == 0)
    {
      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    }
    else
    {
      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    }
#endif
    if(nwalk == 1)
    {
      if(orig_M->length() == nV)
      {
        /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
        newRing=VMrRefine(target_weight, curr_weight);
      }
      else
      {
        newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
      }
    }
    else
    {
     if(target_M->length() == nV)
     {
       /*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
       newRing=VMrRefine(target_weight, curr_weight);
     }
     else
     {
       newRing = VMatrRefine(target_M,curr_weight);
     }
    }
    rChangeCurrRing(newRing);
    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
    idDelete(&Gomega);
    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef TIME_TEST
    to = clock();
#endif
#ifndef BUCHBERGER_ALG
    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    delete hilb_func;
#else
    M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
#endif
#ifdef TIME_TEST
    tstd = tstd + clock() - to;
#endif
    idSkipZeroes(M);
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(M, "//** Mrwalk: M");
    }
#endif
    //change the ring to baseRing
    rChangeCurrRing(baseRing);
    M1 =  idrMoveR(M, newRing,currRing);
    idDelete(&M);
    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
    idDelete(&Gomega1);
#ifdef TIME_TEST
    to = clock();
#endif
    // 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
    F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
    tlift = tlift + clock() - to;
#endif
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(F,"//** Mrwalk: F");
    }
#endif
    idDelete(&Gomega2);
    idDelete(&M1);
    rChangeCurrRing(newRing); // change the ring to newRing
    G = idrMoveR(F,baseRing,currRing);
    idDelete(&F);
    baseRing = currRing;
#ifdef TIME_TEST
    to = clock();
    tstd = tstd + clock() - to;
#endif
    idSkipZeroes(G);
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(G,"//** Mrwalk: G");
    }
#endif

    rChangeCurrRing(targetRing);
    G = idrMoveR(G,newRing,currRing);

    // test whether target cone is reached
    if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
    {
      baseRing = currRing;
      break;
    }

    rChangeCurrRing(newRing);
    G = idrMoveR(G,targetRing,currRing);
    baseRing = currRing;

    NEXT_VECTOR:
#ifdef TIME_TEST
    to = clock();
#endif
    next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
#ifdef TIME_TEST
    tnw = tnw + clock() - to;
#endif

#ifdef TIME_TEST
    to = clock();
#endif
    Gomega = MwalkInitialForm(G, next_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
    tif = tif + clock()-to; //time for computing initial form ideal
#endif

    //lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
    //polylength = lengthpoly(Gomega);
    if(lengthpoly(Gomega) > 0)
    {
      //there is a polynomial in Gomega with at least 3 monomials,
      //low-dimensional facet of the cone
      delete next_weight;
      if(target_M->length() == nV)
      {
        //iv_M = MivMatrixOrder(curr_weight);
        iv_M = MivMatrixOrderRefine(curr_weight,target_M);
      }
      else
      {
        iv_M = MivMatrixOrderRefine(curr_weight,target_M);
      }
#ifdef TIME_TEST
      to = clock();
#endif
      next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, pert_deg);
#ifdef TIME_TEST
      tnw = tnw + clock() - to;
#endif
      idDelete(&Gomega);
#ifdef TIME_TEST
      to = clock();
#endif
      Gomega = MwalkInitialForm(G, next_weight);
#ifdef TIME_TEST
      tif = tif + clock()-to; //time for computing initial form ideal
#endif
      delete iv_M;
    }

    // test whether target weight vector is reached
    if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)
    {
      baseRing = currRing;
      delete next_weight;
      break;
    }
    if(reduction ==0)
    {
      if(MivComp(curr_weight,next_weight)==1)
      {
        break;
      }
    }
#ifdef PRINT_VECTORS
    if(printout > 0)
    {
      MivString(curr_weight, target_weight, next_weight);
    }
#endif

    for(i=nV-1; i>=0; i--)
    {
      (*curr_weight)[i] = (*next_weight)[i];
    }
    delete next_weight;
  }
  baseRing = currRing;
  rChangeCurrRing(XXRing);
  ideal result = idrMoveR(G,baseRing,currRing);
  idDelete(&G);
  delete ivNull;
#ifndef BUCHBERGER_ALG
  delete last_omega;
#endif
  if(printout > 0)
  {
    Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
  }
#ifdef TIME_TEST
  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
  si_opt_1 = save1; //set original options
  return(result);
}

intvec* MSimpleIV

(

intvec *

iv

)

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

Definition at line 5202 of file walk.cc.

{
  // save current options
  BITSET save1 = si_opt_1;
  if(reduction == 0)
  {
    si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
    si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  }
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //BOOLEAN endwalks = FALSE;
#ifdef TIME_TEST
  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
  tinput = clock();
  clock_t tim;
#endif
  nstep=0;
  int i,nwalk;
  int nV = baseRing->N;

  ideal Gomega, M, F, FF, Gomega1, Gomega2, M1;
  ring newRing;
  ring XXRing = baseRing;
  ring targetRing;
  intvec* ivNull = new intvec(nV);
  intvec* curr_weight = new intvec(nV);
  intvec* target_weight = new intvec(nV);
  intvec* exivlp = Mivlp(nV);
/*
  intvec* tmp_weight = new intvec(nV);
  for(i=0; i<nV; i++)
  {
    (*tmp_weight)[i] = (*orig_M)[i];
  }
*/
  for(i=0; i<nV; i++)
  {
    (*curr_weight)[i] = (*orig_M)[i];
    (*target_weight)[i] = (*target_M)[i];
  }
#ifndef BUCHBERGER_ALG
  intvec* hilb_func;
   // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=nV-1; i>0; i--)
  {
    (*last_omega)[i] = 1;
  }
  (*last_omega)[0] = 10000;
#endif
  rComplete(currRing);
#ifdef CHECK_IDEAL_MWALK
  if(printout > 2)
  {
    idString(Go,"//** Mwalk: Go");
  }
#endif

  if(target_M->length() == nV)
  {
   // define the target ring
    targetRing = VMrDefault(target_weight);
  }
  else
  {
    targetRing = VMatrDefault(target_M);
  }
  if(orig_M->length() == nV)
  {
    // define a new ring with ordering "(a(curr_weight),lp)
    //newRing = VMrDefault(curr_weight);
    newRing=VMrRefine(target_weight, curr_weight);
  }
  else
  {
    newRing = VMatrRefine(target_M,curr_weight); //newRing = VMatrDefault(orig_M);
  }
  rChangeCurrRing(newRing);
  if(printout > 2)
  {
    Print("\n//** Mrwalk: Current ring r = %s;\n", rString(currRing));
  }
#ifdef TIME_TEST
  to = clock();
#endif
  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
#ifdef TIME_TEST
  tostd = clock()-to;
#endif

  baseRing = currRing;
  nwalk = 0;

  while(1)
  {
    nwalk ++;
    nstep ++;
    //compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
    to = clock();
#endif
    Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
    tif = tif + clock()-to;
#endif

#ifdef CHECK_IDEAL_MWALK
    if(printout > 1)
    {
      idString(Gomega,"//** Mwalk: Gomega");
    }
#endif

    if(reduction == 0)
    {
      FF = middleOfCone(G,Gomega);
      if(FF != NULL)
      {
      PrintS("middle of Cone");
        idDelete(&G);
        G = idCopy(FF);
        idDelete(&FF);
        goto NEXT_VECTOR;
      }
    }

#ifndef  BUCHBERGER_ALG
    if(isNolVector(curr_weight) == 0)
    {
      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    }
    else
    {
      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    }
#endif

    if(nwalk == 1)
    {
      if(orig_M->length() == nV)
      {
        // define a new ring with ordering "(a(curr_weight),lp)
        //newRing = VMrDefault(curr_weight);
        newRing=VMrRefine(target_weight, curr_weight);
      }
      else
      {
        newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
      }
    }
    else
    {
     if(target_M->length() == nV)
     {
       //define a new ring with ordering "(a(curr_weight),lp)"
       //newRing = VMrDefault(curr_weight);
       newRing=VMrRefine(target_weight, curr_weight);
     }
     else
     {
       //define a new ring with matrix ordering
       newRing = VMatrRefine(target_M,curr_weight);
     }
    }
    rChangeCurrRing(newRing);
    if(printout > 2)
    {
      Print("\n// Current ring r = %s;\n", rString(currRing));
    }
    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
    idDelete(&Gomega);
    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef TIME_TEST
    to = clock();
#endif
#ifndef  BUCHBERGER_ALG
    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    delete hilb_func;
#else
    M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
#endif
#ifdef TIME_TEST
    tstd = tstd + clock() - to;
#endif
    idSkipZeroes(M);
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(M, "//** Mwalk: M");
    }
#endif
    //change the ring to baseRing
    rChangeCurrRing(baseRing);
    M1 =  idrMoveR(M, newRing,currRing);
    idDelete(&M);
    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
    idDelete(&Gomega1);
#ifdef TIME_TEST
    to = clock();
#endif
    // 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
    F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
    tlift = tlift + clock() - to;
#endif
#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(F, "//** Mwalk: F");
    }
#endif
    idDelete(&Gomega2);
    idDelete(&M1);

    rChangeCurrRing(newRing); // change the ring to newRing
    G = idrMoveR(F,baseRing,currRing);
    idDelete(&F);
    idSkipZeroes(G);

#ifdef CHECK_IDEAL_MWALK
    if(printout > 2)
    {
      idString(G, "//** Mwalk: G");
    }
#endif

    rChangeCurrRing(targetRing);
    G = idrMoveR(G,newRing,currRing);
    // test whether target cone is reached
    if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
    {
      baseRing = currRing;
      break;
      //endwalks = TRUE;
    }

    rChangeCurrRing(newRing);
    G = idrMoveR(G,targetRing,currRing);
    baseRing = currRing;

    NEXT_VECTOR:
#ifdef TIME_TEST
    to = clock();
#endif
    intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
#ifdef TIME_TEST
    tnw = tnw + clock() - to;
#endif
#ifdef PRINT_VECTORS
    if(printout > 0)
    {
      MivString(curr_weight, target_weight, next_weight);
    }
#endif
    if(reduction ==0)
    {
      if(MivComp(curr_weight,next_weight)==1)
      {
        break;
      }
    }
    if(MivComp(target_weight,curr_weight) == 1)
    {
      break;
    }

    for(i=nV-1; i>=0; i--)
    {
      //(*tmp_weight)[i] = (*curr_weight)[i];
      (*curr_weight)[i] = (*next_weight)[i];
    }
    delete next_weight;
  }
  rChangeCurrRing(XXRing);
  ideal result = idrMoveR(G,baseRing,currRing);
  idDelete(&Go);
  idDelete(&G);
  //delete tmp_weight;
  delete ivNull;
  delete exivlp;
#ifndef BUCHBERGER_ALG
  delete last_omega;
#endif
#ifdef TIME_TEST
  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
  if(printout > 0)
  {
    Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
  }
  si_opt_1 = save1; //set original options
  return(result);
}

ideal MwalkInitialForm	(	ideal	G,
		intvec *	curr_weight
	)

Definition at line 767 of file walk.cc.

{
  BOOLEAN nError =  Overflow_Error;
  Overflow_Error = FALSE;

  int i, nG = IDELEMS(G);
  ideal Gomega = idInit(nG, 1);

  for(i=nG-1; i>=0; i--)
  {
    Gomega->m[i] = MpolyInitialForm(G->m[i], ivw);
  }
  if(Overflow_Error == FALSE)
  {
    Overflow_Error = nError;
  }
  return Gomega;
}

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

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

Definition at line 8288 of file walk.cc.

{
#ifdef TIME_TEST
  clock_t mtim = clock();
#endif
  Set_Error(FALSE  );
  Overflow_Error =  FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// ring ro = %s;", rString(currRing));

  clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
#ifdef TIME_TEST
  clock_t tinput = clock();
#endif
  int nsteppert=0, i, nV = currRing->N, nwalk=0, npert_tmp=0;
  int *npert=(int*)omAlloc(2*nV*sizeof(int));
  ideal Gomega, M,F,  G1, Gomega1, Gomega2, M1, F1;
  //ring endRing;
  ring newRing, oldRing, lpRing;
  intvec* next_weight;
  intvec* ivNull = new intvec(nV); //define (0,...,0)
  intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
  intvec* iv_lp = Mivlp(nV); //define (1,0,...,0)
  ideal H0;
  //ideal  H1;
  ideal H2, Glp;
  int nGB, endwalks = 0,  nwalkpert=0,  npertstep=0;
  intvec* Mlp =  MivMatrixOrderlp(nV);
  intvec* vector_tmp = new intvec(nV);
#ifndef BUCHBERGER_ALG
  intvec* hilb_func;
#endif
  // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=nV-1; i>0; i--)
    (*last_omega)[i] = 1;
  (*last_omega)[0] = 10000;

  //  intvec* extra_curr_weight = new intvec(nV);
  intvec* target_weight = new intvec(nV);
  for(i=nV-1; i>=0; i--)
    (*target_weight)[i] = (*target_tmp)[i];

  ring XXRing = currRing;
  newRing = currRing;

  to=clock();
  // compute a red. GB w.r.t. the help ring
  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) = "dp"
    G = MstdCC(G);
  else
  {
    //rOrdStr(currRing) = (a(.c_w..),lp,C)
    if (rParameter(currRing) != NULL)
      DefRingPar(curr_weight);
    else
      rChangeCurrRing(VMrDefault(curr_weight));
    G = idrMoveR(G, XXRing,currRing);
    G = MstdCC(G);
  }
  tostd=clock()-to;

#ifdef REPRESENTATION_OF_SIGMA
  ideal Gw = MwalkInitialForm(G, curr_weight);

  if(islengthpoly2(Gw)==1)
  {
    intvec* MDp;
    if(MivComp(curr_weight, iv_dp) == 1)
      MDp = MatrixOrderdp(nV); //MivWeightOrderlp(iv_dp);
    else
      MDp = MivWeightOrderlp(curr_weight);

    curr_weight = RepresentationMatrix_Dp(G, MDp);

    delete MDp;

    ring exring = currRing;

    if (rParameter(currRing) != NULL)
      DefRingPar(curr_weight);
    else
      rChangeCurrRing(VMrDefault(curr_weight));
    to=clock();
    Gw = idrMoveR(G, exring,currRing);
    G = MstdCC(Gw);
    Gw = NULL;
    tostd=tostd+clock()-to;
    //ivString(curr_weight,"rep. sigma");
    goto COMPUTE_NEW_VECTOR;
  }

  idDelete(&Gw);
  delete iv_dp;
#endif


  while(1)
  {
    to=clock();
    /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
    Gomega = MwalkInitialForm(G, curr_weight);
    tif=tif+clock()-to;

#ifndef  BUCHBERGER_ALG
    if(isNolVector(curr_weight) == 0)
      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    else
      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
#endif // BUCHBERGER_ALG

    oldRing = currRing;

    /* define a new ring that its ordering is "(a(curr_weight),lp) */
    if (rParameter(currRing) != NULL)
      DefRingPar(curr_weight);
    else
      rChangeCurrRing(VMrDefault(curr_weight));

    newRing = currRing;
    Gomega1 = idrMoveR(Gomega, oldRing,currRing);

    to=clock();
    /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
#ifdef  BUCHBERGER_ALG
    M = MstdhomCC(Gomega1);
#else
    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    delete hilb_func;
#endif // BUCHBERGER_ALG
    tstd=tstd+clock()-to;

    /* change the ring to oldRing */
    rChangeCurrRing(oldRing);
    M1 =  idrMoveR(M, newRing,currRing);
    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);

    to=clock();
    /* compute a representation of the generators of submod (M)
       with respect to those of mod (Gomega).
       Gomega is a reduced Groebner basis w.r.t. the current ring */
    F = MLifttwoIdeal(Gomega2, M1, G);
    tlift=tlift+clock()-to;

    idDelete(&M1);
    idDelete(&Gomega2);
    idDelete(&G);

    /* change the ring to newRing */
    rChangeCurrRing(newRing);
    F1 = idrMoveR(F, oldRing,currRing);

    to=clock();
    /* reduce the Groebner basis <G> w.r.t. new ring */
    G = kInterRedCC(F1, NULL);
    tred=tred+clock()-to;
    idDelete(&F1);


  COMPUTE_NEW_VECTOR:
    newRing = currRing;
    nwalk++;
    nwalkpert++;
    to=clock();
    // compute a next weight vector
    next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
    tnw=tnw+clock()-to;
#ifdef PRINT_VECTORS
    MivString(curr_weight, target_weight, next_weight);
#endif

    /* check whether the computed intermediate weight vector is in
       the correct cone; sometimes it is very big e.g. s7, cyc7.
       If it is NOT in the correct cone, then compute directly
       a reduced Groebner basis with respect to the lexicographic ordering
       for the known Groebner basis that it is computed in the last step.
    */
    //if(test_w_in_ConeCC(G, next_weight) != 1)
    if(Overflow_Error == TRUE)
    {
    OMEGA_OVERFLOW_TRAN_NEW:
      //Print("\n//  takes %d steps!", nwalk-1);
      //Print("\n//ring lastRing = %s;", rString(currRing));
#ifdef TEST_OVERFLOW
      goto  BE_FINISH;
#endif
/*
#ifdef CHECK_IDEAL_MWALK
      idElements(G, "G");
      //headidString(G, "G");
#endif
*/
      if(MivSame(target_tmp, iv_lp) == 1)
        if (rParameter(currRing) != NULL)
          DefRingParlp();
        else
          VMrDefaultlp();
      else
        if (rParameter(currRing) != NULL)
          DefRingPar(target_tmp);
        else
          rChangeCurrRing(VMrDefault(target_tmp));

      lpRing = currRing;
      G1 = idrMoveR(G, newRing,currRing);

      to=clock();
      /*apply kStd or LastGB to compute  a lex. red. Groebner basis of <G>*/
      if(nP == 0 || MivSame(target_tmp, iv_lp) == 0){
        //Print("\n\n// calls \"std in ring r_%d = %s;", nwalk, rString(currRing));
        G = MstdCC(G1);//no result for qnt1
      }
      else {
        rChangeCurrRing(newRing);
        G1 = idrMoveR(G1, lpRing,currRing);

        //Print("\n\n// calls \"LastGB\" (%d) to compute a GB", nV-1);
        G = LastGB(G1, curr_weight, nV-1); //no result for kats7

        rChangeCurrRing(lpRing);
        G = idrMoveR(G, newRing,currRing);
      }
      textra=clock()-to;
      npert[endwalks]=nwalk-npert_tmp;
      npert_tmp = nwalk;
      endwalks ++;
      break;
    }

    /* check whether the computed Groebner basis is really a Groebner basis.
       If not, we perturb the target vector with the maximal "perturbation"
       degree.*/
    if(MivComp(next_weight, target_weight) == 1 ||
       MivComp(next_weight, curr_weight) == 1 )
    {
      //Print("\n//ring r_%d = %s;", nwalk, rString(currRing));


      //compute the number of perturbations and its step
      npert[endwalks]=nwalk-npert_tmp;
      npert_tmp = nwalk;

      endwalks ++;

      /*it is very important if the walk only uses one step, e.g. Fate, liu*/
      if(endwalks == 1 && MivComp(next_weight, curr_weight) == 1){
        rChangeCurrRing(XXRing);
        G = idrMoveR(G, newRing,currRing);
        goto FINISH;
      }
      H0 = id_Head(G,currRing);

      if(MivSame(target_tmp, iv_lp) == 1)
        if (rParameter(currRing) != NULL)
          DefRingParlp();
        else
          VMrDefaultlp();
      else
        if (rParameter(currRing) != NULL)
          DefRingPar(target_tmp);
        else
          rChangeCurrRing(VMrDefault(target_tmp));

      lpRing = currRing;
      Glp = idrMoveR(G, newRing,currRing);
      H2 = idrMoveR(H0, newRing,currRing);

      /* Apply Lemma 2.2 in Collart et. al (1997) to check whether
         cone(k-1) is equal to cone(k) */
      nGB = 1;
      for(i=IDELEMS(Glp)-1; i>=0; i--)
      {
        poly t;
        if((t=pSub(pHead(Glp->m[i]), pCopy(H2->m[i]))) != NULL)
        {
          pDelete(&t);
          idDelete(&H2);//5.5.02
          nGB = 0; //i.e. Glp is no reduced Groebner basis
          break;
        }
        pDelete(&t);
      }

      idDelete(&H2);//5.5.02

      if(nGB == 1)
      {
        G = Glp;
        Glp = NULL;
        break;
      }

       /* perturb the target weight vector, if the vector target_tmp
          stays in many cones */
      poly p;
      BOOLEAN plength3 = FALSE;
      for(i=IDELEMS(Glp)-1; i>=0; i--)
      {
        p = MpolyInitialForm(Glp->m[i], target_tmp);
        if(p->next != NULL &&
           p->next->next != NULL &&
           p->next->next->next != NULL)
        {
          Overflow_Error = FALSE;

          for(i=0; i<nV; i++)
            (*vector_tmp)[i] = (*target_weight)[i];

          delete target_weight;
          target_weight = MPertVectors(Glp, Mlp, nV);

          if(MivComp(vector_tmp, target_weight)==1)
          {
            //PrintS("\n// The old and new representaion vector are the same!!");
            G = Glp;
            newRing = currRing;
            goto OMEGA_OVERFLOW_TRAN_NEW;
           }

          if(Overflow_Error == TRUE)
          {
            rChangeCurrRing(newRing);
            G = idrMoveR(Glp, lpRing,currRing);
            goto OMEGA_OVERFLOW_TRAN_NEW;
          }

          plength3 = TRUE;
          pDelete(&p);
          break;
        }
        pDelete(&p);
      }

      if(plength3 == FALSE)
      {
        rChangeCurrRing(newRing);
        G = idrMoveR(Glp, lpRing,currRing);
        goto TRAN_LIFTING;
      }


      npertstep = nwalk;
      nwalkpert = 1;
      nsteppert ++;

      /*
      Print("\n// Subroutine needs (%d) steps.", nwalk);
      idElements(Glp, "last G in walk:");
      PrintS("\n// ****************************************");
      Print("\n// Perturb the original target vector (%d): ", nsteppert);
      ivString(target_weight, "new target");
      PrintS("\n// ****************************************\n");
      */
      rChangeCurrRing(newRing);
      G = idrMoveR(Glp, lpRing,currRing);

      delete next_weight;

      //Print("\n// ring rNEW = %s;", rString(currRing));
      goto COMPUTE_NEW_VECTOR;
    }

  TRAN_LIFTING:
    for(i=nV-1; i>=0; i--)
      (*curr_weight)[i] = (*next_weight)[i];

    delete next_weight;
  }//while
#ifdef TEST_OVERFLOW
 BE_FINISH:
#endif
  rChangeCurrRing(XXRing);
  G = idrMoveR(G, lpRing,currRing);

 FINISH:
  delete ivNull;
  delete next_weight;
  delete iv_lp;
  omFree(npert);
/*
#ifdef TIME_TEST
  Print("\n// Computation took %d steps and %.2f sec",
        nwalk, ((double) (clock()-mtim)/1000000));

  TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);

 // Print("\n// pSetm_Error = (%d)", ErrorCheck());
  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
*/
  return(G);
}

intvec* TranMPertVectorslp

(

ideal

G

)