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)
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)
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 889 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 8444 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)); // Aenderung 16
        }
        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)); // Aenderung 17
    }
    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);

    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)); // Aenderung 18
      }
      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 4075 of file walk.cc.

{
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //BOOLEAN nOverflow_Error = FALSE;
  //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 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;
#if 0
  intvec* extra_curr_weight = new intvec(nV);
#endif
  //intvec* hilb_func;
  intvec* exivlp = Mivlp(nV);

  ring XXRing = currRing;

  //Print("\n// ring r_input = %s;", rString(currRing));
  to = clock();
  /* 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);
  tostd=clock()-to;

  /*
  Print("\n// Computation of the first std took = %.2f sec",
        ((double) tostd)/1000000);
  */
  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;
      goto LAST_GB_ALT2;
    }
#endif
    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)); // Aenderung
    }
    newRing = currRing;
    Gomega1 = idrMoveR(Gomega, oldRing,currRing);
    to = clock();
    /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
    M = MstdhomCC(Gomega1);
    xtstd=xtstd+clock()-to;
    /* change the ring to oldRing */
    rChangeCurrRing(oldRing);
    M1 =  idrMoveR(M, newRing,currRing);
    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);

    to = clock();
    /* compute the reduced Groebner basis of <G> w.r.t. "newRing"
       by the liftig 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);

    to = clock();
    /* reduce the Groebner basis <G> w.r.t. newRing */
    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)
    {
      /*
        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;
        tproc = clock()-xftinput;
        //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 1492 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);
  }
  //PrintS("\n// 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]);
  }

  j = 0;
  for(i=0; i<nV; i++)
  {
    (* result1)[i] = mpz_get_si(pert_vector[i]);
    (* result1)[i] = 0.1*(* result1)[i];
    (* result1)[i] = floor((* result1)[i] + 0.5);
    if((* result1)[i] == 0)
    {
      j++;
    }
  }
  if(j > nV - 1)
  {
    // Print("\n//  MfPertwalk: geaenderter vector gleich Null! \n");
    delete result1;
    goto CHECK_OVERFLOW;
  }

// check that the perturbed weight vector lies in the Groebner cone
  if(test_w_in_ConeCC(G,result1) != 0)
  {
    // Print("\n//  MfPertwalk: geaenderter vector liegt in Groebnerkegel! \n");
    delete result;
    result = result1;
    for(i=0; i<nV; i++)
    {
      mpz_set_si(pert_vector[i], (*result1)[i]);
    }
  }
  else
  {
    delete result1;
    // Print("\n// Mfpertwalk: geaenderter vector liegt nicht in Groebnerkegel! \n");
  }

  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
	)

Definition at line 6938 of file walk.cc.

{
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// ring ro = %s;", rString(currRing));

  nnflow = 0;
  Xngleich = 0;
  Xcall = 0;
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
  xftinput = clock();

  ring  oldRing = currRing;
  int i, nV = currRing->N;
  XivNull = new intvec(nV);
  Xivinput = ivtarget;
  ngleich = 0;
  to=clock();
  ideal I = MstdCC(G);
  G = NULL;
  xftostd=clock()-to;
  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(MivSame(ivstart, iv_dp) != 1)
        Mdp = MivWeightOrderdp(ivstart);
      else
        Mdp = MivMatrixOrderdp(nV);

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

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

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

  if(MivComp(ivtarget, Xivlp)  != 1)
  {
    if (rParameter(currRing) != NULL)
      DefRingPar(ivtarget);
    else
      rChangeCurrRing(VMrDefault1(ivtarget)); //Aenderung1

    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);
  }
  delete Mlp;
  Overflow_Error = FALSE;

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

  id_Delete(&I, oldRing);
  ring tRing = currRing;

  if (rParameter(currRing) != NULL)
    DefRingPar(ivstart);
  else
    rChangeCurrRing(VMrDefault1(ivstart)); //Aenderung2

  I = idrMoveR(I1,tRing,currRing);
  to=clock();
  ideal J = MstdCC(I);
  idDelete(&I);
  xftostd=xftostd+clock()-to;

  ideal resF;
  ring helpRing = currRing;
//ideal G, int nlev, intvec* omtmp, int weight_rad)
  J = rec_r_fractal_call(J, 1, ivtarget,weight_rad);

  rChangeCurrRing(oldRing);
  resF = idrMoveR(J, helpRing,currRing);
  idSkipZeroes(resF);

  delete Xivlp;
  delete Xsigma;
  delete Xtau;
  delete XivNull;

#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

  return(resF);
}

ideal Mfwalk	(	ideal	G,
		intvec *	ivstart,
		intvec *	ivtarget
	)

Definition at line 6812 of file walk.cc.

{
  Set_Error(FALSE);
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// ring ro = %s;", rString(currRing));

  nnflow = 0;
  Xngleich = 0;
  Xcall = 0;
  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
  xftinput = clock();

  ring  oldRing = currRing;
  int i, nV = currRing->N;
  XivNull = new intvec(nV);
  Xivinput = ivtarget;
  ngleich = 0;
  to=clock();
  ideal I = MstdCC(G);
  G = NULL;
  xftostd=clock()-to;
  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(MivSame(ivstart, iv_dp) != 1)
        Mdp = MivWeightOrderdp(ivstart);
      else
        Mdp = MivMatrixOrderdp(nV);

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

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

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

  if(MivComp(ivtarget, Xivlp)  != 1)
  {
    if (rParameter(currRing) != NULL)
      DefRingPar(ivtarget);
    else
      rChangeCurrRing(VMrDefault1(ivtarget)); //Aenderung1

    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);
  }
  delete Mlp;
  Overflow_Error = FALSE;

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

  id_Delete(&I, oldRing);
  ring tRing = currRing;

  if (rParameter(currRing) != NULL)
    DefRingPar(ivstart);
  else
    rChangeCurrRing(VMrDefault1(ivstart)); //Aenderung2

  I = idrMoveR(I1,tRing,currRing);
  to=clock();
  ideal J = MstdCC(I);
  idDelete(&I);
  xftostd=xftostd+clock()-to;

  ideal resF;
  ring helpRing = currRing;

  J = rec_fractal_call(J, 1, ivtarget);

  rChangeCurrRing(oldRing);
  resF = idrMoveR(J, helpRing,currRing);
  idSkipZeroes(resF);

  delete Xivlp;
  delete Xsigma;
  delete Xtau;
  delete XivNull;

#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

  return(resF);
}

ideal MidLift	(	ideal	Gomega,
		ideal	M
	)

intvec* Mivdp

(

int

nR

)

Definition at line 980 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 995 of file walk.cc.

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

  return ivm;
}

intvec* MivMatrixOrder

(

intvec *

iv

)

Definition at line 938 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 1397 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 1381 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 868 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 1476 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 1436 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 1416 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 2248 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 1061 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]);
      }
    }
  }
  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);
    }
  }

  intvec *pert_vector1= new intvec(nV);
  j = 0;
  for(i=0; i<nV; i++)
  {
    (* pert_vector1)[i] = mpz_get_si(pert_vector[i]);
    (* pert_vector1)[i] = 0.1*(* pert_vector1)[i];
    (* pert_vector1)[i] = floor((* pert_vector1)[i] + 0.5);
    if((* pert_vector1)[i] == 0)
    {
      j++;
    }
  }
  if(j > nV - 1)
  {
    // Print("\n//  MPertVectors: geaenderter vector gleich Null! \n");
    delete pert_vector1;
    goto CHECK_OVERFLOW;
  }

// check that the perturbed weight vector lies in the Groebner cone
  if(test_w_in_ConeCC(G,pert_vector1) != 0)
  {
    // Print("\n//  MPertVectors: geaenderter vector liegt in Groebnerkegel! \n");
    for(i=0; i<nV; i++)
    {
      mpz_set_si(pert_vector[i], (*pert_vector1)[i]);
    }
  }
  else
  {
    //Print("\n// MpertVectors: geaenderter vector liegt nicht in Groebnerkegel! \n");
  }
  delete pert_vector1;

  CHECK_OVERFLOW:
  intvec* result = new intvec(nV);

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

  int 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);
  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 1279 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 *	curr_weight,
		intvec *	target_weight,
		int	weight_rad,
		int	op_deg,
		int	tp_deg,
		ring	baseRing
	)

Definition at line 8244 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
  Set_Error(FALSE);
  Overflow_Error = FALSE;
#ifdef TIME_TEST
  clock_t tinput=0, tostd=0, 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
  int i,nwalk,nV = baseRing->N;

  ideal G, Gomega, M, F, Gomega1, Gomega2, M1;
  ring newRing;
  ring XXRing = baseRing;
  intvec* exivlp = Mivlp(nV);
  intvec* orig_target = target_weight;
  intvec* pert_target_vector = target_weight;
  intvec* ivNull = new intvec(nV);
  intvec* tmp_weight = new intvec(nV);
#ifdef CHECK_IDEAL_MWALK
  poly p;
#endif
  for(i=0; i<nV; i++)
  {
    (*tmp_weight)[i] = (*curr_weight)[i];
  }
#ifndef BUCHBERGER_ALG
  intvec* hilb_func;
   // to avoid (1,0,...,0) as the target vector
  intvec* last_omega = new intvec(nV);
  for(i=0 i<nV; i++)
  {
    (*last_omega)[i] = 1;
  }
  (*last_omega)[0] = 10000;
#endif
  baseRing = currRing;
  newRing = VMrDefault(curr_weight);
  rChangeCurrRing(newRing);
  G = idrMoveR(Go,baseRing,currRing);
#ifdef TIME_TEST
  to = clock();
#endif
  G = kStd(G,NULL,testHomog,NULL,NULL,0,0,NULL);
  idSkipZeroes(G);
#ifdef TIME_TEST
  tostd = tostd + to - clock();
#endif
#ifdef CHECK_IDEAL_MWALK
  idString(G,"G");
#endif
  if(op_deg >1)
  {
    if(MivComp(curr_weight,MivUnit(nV)) == 1) //ring order is "dp"
    {
      curr_weight = MPertVectors(G, MivMatrixOrderdp(nV), op_deg);
    }
    else //ring order is not "dp"
    {
      curr_weight = MPertVectors(G, MivMatrixOrder(curr_weight), op_deg);
    }
  }
  baseRing = currRing;
  if(tp_deg > 1 && tp_deg <= nV)
  {
    pert_target_vector = target_weight;
  }
#ifdef CHECK_IDEAL_MWALK
  ivString(curr_weight, "new curr_weight");
  ivString(target_weight, "new target_weight");
#endif
  nwalk = 0;
  while(1)
  {
    nwalk ++;
#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
#ifdef CHECK_IDEAL_MWALK
    idString(Gomega,"Gomega");
#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
    if(nwalk == 1)
    {
      newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
    }
    else
    {
      newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
    }
    rChangeCurrRing(newRing);
    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
    idDelete(&Gomega);
    // compute a 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
    idSkipZeroes(M);
#ifdef TIME_TEST
    tstd = tstd + clock() - to;
#endif
#ifdef CHECK_IDEAL_MWALK
    idString(M, "M");
#endif
    //change the ring to baseRing
    rChangeCurrRing(baseRing);
    M1 =  idrMoveR(M, newRing,currRing);
    idDelete(&M);
    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
    idDelete(&Gomega1);
    to = clock();
    // 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);
    idSkipZeroes(F);
#ifdef TIME_TEST
    tlift = tlift + clock() - to;
#endif
#ifdef CHECK_IDEAL_MWALK
    idString(F,"F");
#endif
    rChangeCurrRing(newRing); // change the ring to newRing
    G = idrMoveR(F,baseRing,currRing);
    idDelete(&F);
    baseRing = currRing; // set baseRing equal to newRing
#ifdef CHECK_IDEAL_MWALK
    idString(G,"G");
#endif
#ifdef TIME_TEST
    to = clock();
#endif
    intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, op_deg);
#ifdef TIME_TEST
    tnw = tnw + clock() - to;
#endif
#ifdef PRINT_VECTORS
    MivString(curr_weight, target_weight, next_weight);
#endif
    if(Overflow_Error == TRUE)
    {
      PrintS("\n//**Mprwalk: OVERFLOW: The computed vector does not stay in cone, the result may be wrong.\n");
      delete next_weight;
      break;
    }

    if(test_w_in_ConeCC(G,target_weight) == 1 || MivComp(next_weight, ivNull) == 1)
    {
      delete next_weight;
      break;
    }
    //update tmp_weight and curr_weight
    for(i=nV-1; i>=0; i--)
    {
      (*tmp_weight)[i] = (*curr_weight)[i];
      (*curr_weight)[i] = (*next_weight)[i];
    }
    delete next_weight;
  } //end of while-loop
  Print("\n// Mprwalk took %d steps. Ring= %s;\n", nwalk, rString(currRing));
  idSkipZeroes(G);
  si_opt_1 = save1; //set original options, e. g. option(RedSB)
  baseRing = currRing;
  rChangeCurrRing(XXRing);
  ideal Res = idrMoveR(G,baseRing,currRing);
  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);
#endif
  return(Res);
}

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

Definition at line 5750 of file walk.cc.

{
  Set_Error(FALSE  );
  Overflow_Error = FALSE;
  //Print("// pSetm_Error = (%d)", ErrorCheck());

  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;

  nstep = 0;
  int i, ntwC=1, ntestw=1,  nV = currRing->N;
  int endwalks=0;

  ideal Gomega, M, F, 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;


  to = clock();
  /* perturbs the original vector */
  if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
  {
    G = MstdCC(Go);
    tostd = clock()-to;
    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)); //Aenderung 1

    G = idrMoveR(Go, XXRing,currRing);
    G = MstdCC(G);
    tostd = clock()-to;
    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)); // Aenderung 2

    TargetRing = currRing;
    ssG = idrMoveR(G,HelpRing,currRing);
    if(MivSame(target_weight, exivlp) == 1)
    {
      iv_M_lp = MivMatrixOrderlp(nV);
      //ivString(iv_M_lp, "iv_M_lp");
      //target_weight = MPertVectorslp(ssG, iv_M_lp, tp_deg);
      target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
    }
    else
    {
      iv_M_lp = MivMatrixOrder(target_weight);
      //target_weight = MPertVectorslp(ssG, iv_M_lp, tp_deg);
      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);
  }
  /*
    Print("\n// Perturbationwalkalg. vom Gradpaar (%d,%d):",op_deg,tp_deg);
    ivString(curr_weight, "new sigma");
    ivString(target_weight, "new tau");
  */
  while(1)
  {
    nstep ++;
    to = clock();
    /* compute an initial form ideal of <G> w.r.t. the weight vector
       "curr_weight" */
    Gomega = MwalkInitialForm(G, curr_weight);


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

    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 with ordering "(a(curr_weight),lp)
    if (rParameter(currRing) != NULL)
      DefRingPar(curr_weight);
    else
      rChangeCurrRing(VMrDefault(curr_weight)); //Aenderung 3

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

#ifdef ENDWALKS
    if(endwalks==1)
    {
      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

    tim = clock();
    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

    if(endwalks == 1){
      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;

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

    //if(endwalks==1)  PrintS("\n// Lifting is working:..");

    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);
    if(endwalks != 1)
      tlift = tlift+clock()-to;
    else
      xtlift=clock()-to;

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

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

    //if(endwalks==1)PrintS("\n// InterRed is working now:");

    to=clock();
    /* reduce the Groebner basis <G> w.r.t. new ring */
    G = kInterRedCC(F1, NULL);
    if(endwalks != 1)
      tred = tred+clock()-to;
    else
      xtred=clock()-to;

    idDelete(&F1);

    if(endwalks == 1)
      break;

    to=clock();
    /* compute a next weight vector */
    next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
    tnw=tnw+clock()-to;
#ifdef PRINT_VECTORS
    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 = 1;

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

    delete next_weight;
  }//while

  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)); //Aenderung

    TargetRing=currRing;
    F1 = idrMoveR(G, newRing,currRing);
#ifdef CHECK_IDEAL
      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){
        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);
  }
  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
  return(Eresult);
}

ideal Mrwalk	(	ideal	Go,
		intvec *	curr_weight,
		intvec *	target_weight,
		int	weight_rad,
		int	pert_deg,
		ring	baseRing
	)

Definition at line 5339 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  //si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  //si_opt_1|=(Sy_bit(OPT_REDTAIL)|Sy_bit(OPT_REDSB));
  Set_Error(FALSE);
  Overflow_Error = 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,endwalks = 0;
  int nV = baseRing->N;

  ideal Gomega, M, F, Gomega1, Gomega2, M1; //, F1;
  ring newRing;
  ring XXRing = baseRing;
  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] = (*target_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
    idString(Go,"Go");
#endif
#ifdef TIME_TEST
  to = clock();
#endif
     if(orig_M->length() == nV)
      {
        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
      }
      else
      {
        newRing = VMatrDefault(orig_M);
      }
  rChangeCurrRing(newRing);
  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
  baseRing = currRing;
#ifdef TIME_TEST
  tostd = clock()-to;
#endif

  nwalk = 0;
  while(1)
  {
    nwalk ++;
    nstep ++;
#ifdef TIME_TEST
    to = clock();
#endif
#ifdef CHECK_IDEAL_MWALK
    idString(G,"G");
#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
#ifdef CHECK_IDEAL_MWALK
    idString(Gomega,"Gomega");
#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
    if(nwalk == 1)
    {
      if(orig_M->length() == nV)
      {
        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
      }
      else
      {
        newRing = VMatrDefault(orig_M);
      }
    }
    else
    {
     if(target_M->length() == nV)
     {
       newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_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
    PrintS("\n//** Mwalk: computed M.\n");
    idString(M, "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
    idString(F, "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();
#endif
    //G = kStd(F1,NULL,testHomog,NULL,NULL,0,0,NULL);
#ifdef TIME_TEST
    tstd = tstd + clock() - to;
#endif
    idSkipZeroes(G);
#ifdef CHECK_IDEAL_MWALK
    idString(G, "G");
#endif
#ifdef TIME_TEST
    to = clock();
#endif
    intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, pert_deg);//next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
#ifdef TIME_TEST
    tnw = tnw + clock() - to;
#endif
#ifdef PRINT_VECTORS
    MivString(curr_weight, target_weight, next_weight);
#endif
    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)
    {
#ifdef CHECK_IDEAL_MWALK
      PrintS("\n//** Mwalk: entering last cone.\n");
#endif
      Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
      if(target_M->length() == nV)
      {
        newRing = VMrDefault(target_weight); // define a new ring with ordering "(a(curr_weight),lp)
      }
      else
      {
        newRing = VMatrDefault(target_M);
      }
      rChangeCurrRing(newRing);
      Gomega1 = idrMoveR(Gomega, baseRing,currRing);
      idDelete(&Gomega);
#ifdef CHECK_IDEAL_MWALK
      idString(Gomega1, "Gomega");
#endif
      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
#ifdef CHECK_IDEAL_MWALK
      idString(M,"M");
#endif
      rChangeCurrRing(baseRing);
      M1 =  idrMoveR(M, newRing,currRing);
      idDelete(&M);
      Gomega2 = idrMoveR(Gomega1, newRing,currRing);
      idDelete(&Gomega1);
      F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef CHECK_IDEAL_MWALK
      idString(F,"F");
#endif
      idDelete(&Gomega2);
      idDelete(&M1);
      rChangeCurrRing(newRing); // change the ring to newRing
      G = idrMoveR(F,baseRing,currRing);
      idDelete(&F);
      baseRing = currRing;
      si_opt_1 = save1; //set original options, e. g. option(RedSB)
      idSkipZeroes(G);
#ifdef TIME_TEST
      to = clock();
#endif
 //     if(si_opt_1 == (Sy_bit(OPT_REDSB)))
  //    {
        //G = kInterRedCC(G,NULL); //reduce the Groebner basis <G> w.r.t. currRing, if option(redSB) is set
  //    }
#ifdef TIME_TEST
      tred = tred + clock() - to;
#endif
      idSkipZeroes(G);
      delete next_weight;
      break;
#ifdef CHECK_IDEAL_MWALK
      PrintS("\n//** Mwalk: last cone.\n");
#endif
    }
#ifdef CHECK_IDEAL_MWALK
    PrintS("\n//** Mwalk: update weight vectors.\n");
#endif
    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(&G);
/*#ifdef CHECK_IDEAL_MWALK
  pDelete(&p);
#endif*/
  delete tmp_weight;
  delete ivNull;
  delete exivlp;
#ifndef BUCHBERGER_ALG
  delete last_omega;
#endif
#ifdef TIME_TEST
  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
  Print("\n//** Mwalk: Ergebnis.\n");
  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
  return(result);
}

intvec* MSimpleIV

(

intvec *

iv

)

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

Definition at line 5065 of file walk.cc.

{
  BITSET save1 = si_opt_1; // save current options
  //si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
  //si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
  //si_opt_1|=(Sy_bit(OPT_REDTAIL)|Sy_bit(OPT_REDSB));
  Set_Error(FALSE);
  Overflow_Error = 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,endwalks = 0;
  int nV = baseRing->N;

  ideal Gomega, M, F, Gomega1, Gomega2, M1; //, F1;
  ring newRing;
  ring XXRing = baseRing;
  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] = (*target_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
    idString(Go,"Go");
#endif
#ifdef TIME_TEST
  to = clock();
#endif
     if(orig_M->length() == nV)
      {
        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
      }
      else
      {
        newRing = VMatrDefault(orig_M);
      }
  rChangeCurrRing(newRing);
  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
  baseRing = currRing;
#ifdef TIME_TEST
  tostd = clock()-to;
#endif

  nwalk = 0;
  while(1)
  {
    nwalk ++;
    nstep ++;
#ifdef TIME_TEST
    to = clock();
#endif
#ifdef CHECK_IDEAL_MWALK
    idString(G,"G");
#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
#ifdef CHECK_IDEAL_MWALK
    idString(Gomega,"Gomega");
#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
    if(nwalk == 1)
    {
      if(orig_M->length() == nV)
      {
        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
      }
      else
      {
        newRing = VMatrDefault(orig_M);
      }
    }
    else
    {
     if(target_M->length() == nV)
     {
       newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_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
    PrintS("\n//** Mwalk: computed M.\n");
    idString(M, "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
    idString(F, "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();
#endif
    //G = kStd(F1,NULL,testHomog,NULL,NULL,0,0,NULL);
#ifdef TIME_TEST
    tstd = tstd + clock() - to;
#endif
    idSkipZeroes(G);
#ifdef CHECK_IDEAL_MWALK
    idString(G, "G");
#endif
#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
    MivString(curr_weight, target_weight, next_weight);
#endif
    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)
    {
#ifdef CHECK_IDEAL_MWALK
      PrintS("\n//** Mwalk: entering last cone.\n");
#endif
      Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
      if(target_M->length() == nV)
      {
        newRing = VMrDefault(target_weight); // define a new ring with ordering "(a(curr_weight),lp)
      }
      else
      {
        newRing = VMatrDefault(target_M);
      }
      rChangeCurrRing(newRing);
      Gomega1 = idrMoveR(Gomega, baseRing,currRing);
      idDelete(&Gomega);
#ifdef CHECK_IDEAL_MWALK
      idString(Gomega1, "Gomega");
#endif
      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
#ifdef CHECK_IDEAL_MWALK
      idString(M,"M");
#endif
      rChangeCurrRing(baseRing);
      M1 =  idrMoveR(M, newRing,currRing);
      idDelete(&M);
      Gomega2 = idrMoveR(Gomega1, newRing,currRing);
      idDelete(&Gomega1);
      F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef CHECK_IDEAL_MWALK
      idString(F,"F");
#endif
      idDelete(&Gomega2);
      idDelete(&M1);
      rChangeCurrRing(newRing); // change the ring to newRing
      G = idrMoveR(F,baseRing,currRing);
      idDelete(&F);
      baseRing = currRing;
      si_opt_1 = save1; //set original options, e. g. option(RedSB)
      idSkipZeroes(G);
#ifdef TIME_TEST
      to = clock();
#endif
 //     if(si_opt_1 == (Sy_bit(OPT_REDSB)))
  //    {
        G = kInterRedCC(G,NULL); //reduce the Groebner basis <G> w.r.t. currRing, if option(redSB) is set
  //    }
#ifdef TIME_TEST
      tred = tred + clock() - to;
#endif
      idSkipZeroes(G);
      delete next_weight;
      break;
#ifdef CHECK_IDEAL_MWALK
      PrintS("\n//** Mwalk: last cone.\n");
#endif
    }
#ifdef CHECK_IDEAL_MWALK
    PrintS("\n//** Mwalk: update weight vectors.\n");
#endif
    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(&G);
/*#ifdef CHECK_IDEAL_MWALK
  pDelete(&p);
#endif*/
  delete tmp_weight;
  delete ivNull;
  delete exivlp;
#ifndef BUCHBERGER_ALG
  delete last_omega;
#endif
#ifdef TIME_TEST
  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
  Print("\n//** Mwalk: Ergebnis.\n");
  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
  return(result);
}

ideal MwalkInitialForm	(	ideal	G,
		intvec *	curr_weight
	)

Definition at line 736 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 7069 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)); // Aenderung 4
    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)); //Aenderung 5
    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)); //Aenderung 6

    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)); // Aenderung 8

      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)); //Aenderung 9

      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

)