Changeset ffd4a9 in git

Timestamp:

Jul 29, 2014, 2:00:54 PM (10 years ago)

Author:

Stephan Oberfranz <oberfran@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

a0e7db5bccc63a9fe9ea7898cd864a561f0656cc

Parents:

c311064c2b37f0ffc421b75995c94179b5b9a0ea

git-author:

Stephan Oberfranz <oberfran@mathematik.uni-kl.de>2014-07-29 14:00:54+02:00

git-committer:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2014-08-07 16:12:11+02:00

Message:

Groebner Walk, Sagbi Walk

Location:

Singular

Files:

• LIB/modwalk.lib (modified) (12 diffs, 1 prop)
• LIB/rwalk.lib (modified) (12 diffs, 1 prop)
• LIB/swalk.lib (modified) (10 diffs, 1 prop)
• extra.cc (modified) (25 diffs, 1 prop)
• walk.cc (modified) (94 diffs, 1 prop)
• walk.h (modified) (3 diffs, 1 prop)

Singular/LIB/modwalk.lib

@@ -82 +82 @@
 
 //-------------------------  make i homogeneous  -----------------------------
-
-  if(!hasMixedOrdering() && !h)
+/*  if(!mixedTest() && !h)
   {
     if(!((find(ordstr_R0, "M") > 0) || (find(ordstr_R0, "a") > 0) || neg))
@@ -106 +105 @@
     }
   }
-
+*/
 //-------------------------  compute a standard basis mod p  -----------------------------
 
@@ -147 +146 @@
     if(size(#) == 2)
     {
-      trwalk(i,radius,pert_deg,#);
+      i=fwalk(i,#);
     }
     else
     {
-      trwalk(i,radius,pert_deg);
-    }
-  }
-  if(!hasMixedOrdering() && !h)
+      i=fwalk(i);
+    }
+  }
+  if(variant == 5)
+  {
+    if(size(#) == 2)
+    {
+     i=prwalk(i,radius,pert_deg,pert_deg,#);
+    }
+    else
+    {
+      i=prwalk(i,radius,pert_deg,pert_deg);
+    }
+  }
+  if(variant == 6)
+  {
+    if(size(#) == 2)
+    {
+      i=pwalk(i,pert_deg,pert_deg,#);
+    }
+    else
+    {
+      i=pwalk(i,pert_deg,pert_deg);
+    }
+  }
+  /*
+  if(!mixedTest() && !h)
   {
     if(!((find(ordstr_R0, "M") > 0) || (find(ordstr_R0, "a") > 0) || neg))
@@ -168 +190 @@
       }
     }
-  }
+  }*/
   setring R0;
   return(list(fetch(@r,i),p));
@@ -180 +202 @@
   intvec a = 2,1,3,4;
   intvec b = 1,9,1,1;
-  ring ra = 0,(w,x,y,z),(a(a),lp);
+  ring ra = 0,x(1..4),(a(a),lp);
   ideal I = std(cyclic(4));
-  ring rb = 0,(w,x,y,z),(a(b),lp);
+  ring rb = 0,x(1..4),(a(b),lp);
   ideal I = imap(ra,I);
   modpWalk(I,p,1,a,b);
@@ -214 +236 @@
 proc modWalk(def II, int variant, list #)
 "USAGE:  modWalk(II); II ideal or list(ideal,int)
-ASSUME:  If variant = 1 the random walk algorithm with radius II[2] is applied
-         to II[1] if II = list(ideal, int). It is applied to II with radius 2
-         if II is an ideal. If variant = 2, the Groebner walk algorithm is
-         applied to II[1] or to II, respectively.
+ASSUME:  If variant = 
+@*       - 1 the Random Walk algorithm with radius II[2] is applied
+           to II[1] if II = list(ideal, int). It is applied to II with radius 2
+           if II is an ideal.
+@*       - 2, the Groebner Walk algorithm is applied to II[1] or to II, respectively.
+@*       - 3, the Fractal Walk algorithm with random element is applied to II[1] or II,
+           respectively.
+@*       - 4, the Fractal Walk algorithm is applied to II[1] or II, respectively.
+@*       - 5, the Perturbation Walk algorithm with random element is applied to II[1]
+           or II, respectively, with radius II[3] and perturbation degree II[2].
+@*       - 6, the Perturbation Walk algorithm is applied to II[1] or II, respectively,
+           with perturbation degree II[3].
          If size(#) > 0, then # contains either 1, 2 or 4 integers such that
 @*       - #[1] is the number of available processors for the computation,
@@ -468 +498 @@
 //-------------------------  Save current options  -----------------------------
   intvec opt = option(get);
-  option(redSB);
+  //option(redSB);
 
 //--------------------  Initialize the list of primes  -------------------------
@@ -527 +557 @@
     }
     H = chinrem(T1,T2);
-    //J = parallelFarey(H,N,n1);
-    J=farey(H,N);
+    J = parallelFarey(H,N,n1);
+    //J=farey(H,N);
     if(printlevel >= 10)
     {
@@ -538 +568 @@
 
     tt = timer; rt = rtimer;
-    //pTest = pTestSB(I,J,L,variant);
-    pTest = primeTestSB(I,J,L,variant);
+    pTest = pTestSB(I,J,L,variant);
+    //pTest = primeTestSB(I,J,L,variant);
     if(printlevel >= 10)
     {
@@ -593 +623 @@
     tt = timer; rt = rtimer;
     L = primeList(I,n3,L,n1);
-L;
     if(printlevel >= 10)
     {
@@ -644 +673 @@
   ideal I=-x+y2z-z,xz+1,x2+y2-1;
   // I is a standard basis in dp
-  modWalk(I,1);
-  modWalk(I,2,2,0);
+  ideal J = modWalk(I,1);
+  J;
+/*  modWalk(I,2,2,0);
   modWalk(I,3,system("cpu"),0);
   std(I);
@@ -654 +684 @@
   ideal i=fetch(r0,i0);
   modWalk(i,1,system("cpu"),0);
-  modWalk(i,3);
+  modWalk(i,3);*/
 }
 

Singular/LIB/rwalk.lib

@@ -1 @@
-/////////////////////////////////////////////////
-version="version rwalk.lib 4.0.0.0 Jun_2013 "; // $Id$
+<<<<<<< HEAD
+=======
+//
+>>>>>>> 92644b759d66f085c842e4284d78c2e203291b67
+version="$Id$";
 category="Commutative Algebra";
 
@@ -14 +17 @@
  * Argument string for Random Walk *
  ***********************************/
-static proc OrderStringalp_NP(string Wpal,list #)
+proc OrderStringalp_NP(string Wpal,list #)
 {
   int n= nvars(basering);
@@ -35 +38 @@
         if(Wpal == "al"){
           order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
+        }
+        if(Wpal == "M"){
+          order_str = "(M("+string(#[1])+"),C)";
         }
         else {
@@ -61 +67 @@
            order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
          }
+         if(Wpal == "M"){
+          order_str = "(M("+string(#[1])+"),C)";
+         }
          else {
            order_str = "(Wp("+string(#[1])+"),C)";
@@ -73 +82 @@
              order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
            }
+           if(Wpal == "M"){
+             order_str = "(M("+string(#[1])+"),C)";
+           }
            else {
              order_str = "(Wp("+string(#[1])+"),C)";
+           //  order_str = "(a("+string(#[1])+"),C)";
            }
          }
@@ -95 +108 @@
              order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
            }
+           if(Wpal == "M"){
+             order_str = "(M("+string(#[1])+"),C)";
+           }
            else {
              order_str = "(Wp("+string(#[1])+"),C)";
@@ -122 +138 @@
 }
 
-/************************************
- * Random Walk with perturbation    *
- ************************************/
+/****************
+ * Random Walk  *
+ ****************/
 proc rwalk(ideal Go, int radius, int pert_deg, list #)
 "SYNTAX: rwalk(ideal i, int radius);
-         rwalk(ideal i, int radius, intvec v, intvec w);
+         if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w);
 TYPE:    ideal
 PURPOSE: compute the standard basis of the ideal, calculated via
@@ -138 +154 @@
 {
 //--------------------  Initialize parameters  ------------------------
-list OSCTW = OrderStringalp_NP("al", #);
+int n= nvars(basering);
+list OSCTW = OrderStringalp_NP("al",#);
+if(size(#)>1)
+  {
+  if(size(#[2]) == n*n)
+    {
+    OSCTW= OrderStringalp_NP("M", #);
+    }
+  }
+else
+  {
+  OSCTW= OrderStringalp_NP("al", #);
+  }
 string ord_str = OSCTW[2];
 intvec curr_weight = OSCTW[3]; // original weight vector
 intvec target_weight = OSCTW[4]; // target weight vector
 kill OSCTW;
-option(redSB);
 
 //--------------------  Initialize parameters  ------------------------
 def xR = basering;
-execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
+execute("ring ostR = "+charstr(xR)+",("+varstr(xR)+"),"+ord_str+";");
 def old_ring = basering;
 
 ideal G = fetch(xR, Go);
-G = system("Mrwalk", G, curr_weight, target_weight, radius, pert_deg);
+G = system("Mrwalk", G, curr_weight, target_weight, radius, pert_deg, basering);
 
 setring xR;
@@ -170 +197 @@
   int perturb_deg = 2;
   rwalk(I,radius,perturb_deg);
+}
+
+/*****************************************
+ * Perturbation Walk with random element *
+ *****************************************/
+proc prwalk(ideal Go, int radius, int o_pert_deg, int t_pert_deg, list #)
+"SYNTAX: rwalk(ideal i, int radius);
+         if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w);
+TYPE:    ideal
+PURPOSE: compute the standard basis of the ideal, calculated via
+         the Random walk algorithm  from the ordering
+         \"(a(v),lp)\", \"dp\" or \"Dp\"
+         to the ordering  \"(a(w),lp)\" or \"(a(1,0,...,0),lp)\".
+SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, twalk, awalk1, awalk2
+KEYWORDS: Groebner walk
+EXAMPLE: example rwalk; shows an example"
+{
+//--------------------  Initialize parameters  ------------------------
+list OSCTW = OrderStringalp_NP("al", #);
+string ord_str = OSCTW[2];
+intvec curr_weight = OSCTW[3]; // original weight vector
+intvec target_weight = OSCTW[4]; // target weight vector
+kill OSCTW;
+
+//--------------------  Initialize parameters  ------------------------
+def xR = basering;
+execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
+def old_ring = basering;
+
+ideal G = fetch(xR, Go);
+G = system("Mprwalk", G, curr_weight, target_weight, radius, o_pert_deg, t_pert_deg, basering);
+
+setring xR;
+kill Go;
+
+keepring basering;
+ideal result = fetch(old_ring, G);
+attrib(result,"isSB",1);
+return (result);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  // compute a Groebner basis of I w.r.t. lp.
+  ring r = 32003,(z,y,x), lp;
+  ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z;
+  int radius = 1;
+  int o_perturb_deg = 2;
+  int t_perturb_deg = 2;
+  prwalk(I,radius,o_perturb_deg,t_perturb_deg);
 }
 
@@ -190 +267 @@
 
    string ord_str =   OSCTW[2];
-   intvec curr_weight   =   OSCTW[3]; /* original weight vector */
+   intvec curr_weight   =   OSCTW[3]; /* current weight vector */
    intvec target_weight =   OSCTW[4]; /* target weight vector */
    kill OSCTW;
-   option(redSB);
    def xR = basering;
 
@@ -200 +276 @@
    //print("//** help ring = " + string(basering));
    ideal G = fetch(xR, Go);
-
-   G = system("Mfrwalk", G, curr_weight, target_weight, radius);
+   int pert_deg = 2;
+   G = system("Mfrwalk", G, curr_weight, target_weight, pert_deg, radius, basering);
 
    setring xR;
@@ -242 +318 @@
   kill L;
 
-  option(redSB);
   def xR = basering;
 

Singular/LIB/swalk.lib

@@ -23 +23 @@
 
 LIB "sagbi.lib";
+LIB "crypto.lib";
+LIB "atkins.lib";
+LIB "random.lib";
 //////////////////////////////////////////////////////////////////////////////
 proc swalk(ideal Gox, list #)
 "USAGE:  swalk(i[,v,w]); i ideal, v,w int vectors
+RETURN: The sagbi basis of the subalgebra defined by the generators of i,
+        calculated via the Sagbi walk algorithm from the ordering dp to lp
+        if v,w are not given (resp. from the ordering (a(v),lp) to the
+        ordering (a(w),lp) if v and w are given).
+EXAMPLE: example swalk; shows an example
+"
+{
+  /* we use ring with ordering (a(...),lp,C) */
+  list OSCTW    = OrderStringalp_NP("al", #);//"dp"
+  string ord_str =   OSCTW[2];
+  intvec icurr_weight   =   OSCTW[3]; /* original weight vector */
+  intvec itarget_weight =   OSCTW[4]; /* terget weight vector */
+  kill OSCTW;
+      option(redSB);
+  def xR = basering;
+  list rl=ringlist(xR);
+  if(size(#) == 0)
+  {
+    rl[3][1][1]="dp";
+  }
+  def ostR=ring(rl);
+  setring ostR;
+  def new_ring = basering;
+  ideal Gnew = fetch(xR, Gox);
+  Gnew=sagbi(Gnew,1);
+  Gnew=interreduceSd(Gnew);
+  vector curr_weight=changeTypeInt(icurr_weight);
+  vector target_weight=changeTypeInt(itarget_weight);
+  curr_weight;
+  ideal Gold;
+  list l;
+  intvec v;
+  int n=0;
+  while(n==0)
+    {
+       Gold=Gnew;
+       def old_ring=new_ring;
+       setring old_ring;
+       number ulast;
+       kill new_ring;
+       if(curr_weight==target_weight){n=1;}
+       else {
+              l=collectDiffExpo(Gold);
+              ulast=last(curr_weight, target_weight, l);
+              vector new_weight=(1-ulast)*curr_weight+ulast*target_weight;
+              vector w=cleardenom(new_weight);
+              v=changeType(w);
+              list p= ringlist(old_ring);
+              p[3][1][2]= v;
+              def new_ring=ring(p);
+              setring new_ring;
+              ideal Gold=fetch(old_ring,Gold);
+              vector curr_weight=fetch(old_ring,new_weight);
+              vector target_weight=fetch(old_ring,target_weight);
+              kill old_ring;
+              ideal Gnew=Convert(Gold);
+              Gnew=interreduceSd(Gnew);
+         }
+    }
+   setring xR;
+   ideal result = fetch(old_ring, Gnew);
+   kill old_ring;
+   attrib(result,"isSB",1);
+   return (result);
+}
+example
+{
+  "EXAMPLE:";echo = 2;
+  ring r = 0,(x,y), lp;
+  ideal I =x2,y2,xy+y,2xy2+y3;
+  swalk(I);
+}
+//////////////////////////////////////////////////////////////////////////////
+proc rswalk(ideal Gox, int weight_rad, int pdeg, list #)
+"USAGE:  rswalk(i[,v,w]); i ideal, v,w int vectors
 RETURN: The sagbi basis of the subalgebra defined by the generators of i,
         calculated via the Sagbi walk algorithm from the ordering dp to lp
@@ -60 +138 @@
        def old_ring=new_ring;
        setring old_ring;
-       number ulast;
+       
        kill new_ring;
        if(curr_weight==target_weight){n=1;}
        else {
-              l=collectDiffExpo(Gold);
-              ulast=last(curr_weight, target_weight, l);
-              vector new_weight=(1-ulast)*curr_weight+ulast*target_weight;
+              l=collectDiffExpo(Gold); 
+              vector new_weight=RandomNextWeight(Gold, l, curr_weight, target_weight, weight_rad, pdeg);
               vector w=cleardenom(new_weight);
               v=changeType(w);
@@ -91 +168 @@
   ring r = 0,(x,y), lp;
   ideal I =x2,y2,xy+y,2xy2+y3;
-  swalk(I);
-}
-
+  swalk(I,7);
+}
 //////////////////////////////////////////////////////////////////////////////
 static proc inprod(vector v,vector w)
@@ -211 +287 @@
 
 //////////////////////////////////////////////////////////////////////////////
+static proc test_in_cone(vector w, list l)
+{
+ int i,j,k;
+ vector v;
+ poly n;
+ number a;
+ for(i=1;i<=size(l);i++)
+ {
+    for(j=1;j<=size(l[i]);j++)
+    {
+        v=0;
+        for(k=1;k<=size(l[i][j]);k++)
+        {
+            v=v+l[i][j][k]*gen(k);
+        }
+        n = inprod(w,v);
+        a = leadcoef(n);
+        if(a<0)
+        {
+           return(0);
+        }
+    }
+ }
+ return(1);
+}
+
+
+//////////////////////////////////////////////////////////////////////////////
 static proc last( vector c, vector t,list l)
 "USAGE: last(c,t,l); c,t vectors, l list
@@ -221 +325 @@
  number ul=1;
  int i,j,k;
- number u;
+ number a,b,z,u;
+ poly n,q;
  vector v;
  for(i=1;i<=size(l);i++)
@@ -232 +337 @@
             v=v+l[i][j][k]*gen(k);
         }
-        poly n= inprod(c,v);
-        poly q= inprod(t,v);
-        number a=leadcoef(n);
-        number b=leadcoef(q);
-        number z=a-b;
+        n= inprod(c,v);
+        q= inprod(t,v);
+        a=leadcoef(n);
+        b=leadcoef(q);
+        z=a-b;
         if(b<0)
-        {
+            {
             u=a/z;
-            if(u<ul) {ul=u;}
-        }
-        kill a,b,z,n,q ;
-    }
- }
+            if(u<ul)
+            {
+               ul=u;
+             }
+        }
+    }
+ }~
+ kill a,b,z,n,q,u;
  return(ul);
 }
@@ -340 +448 @@
    Lift(In,InG,Gold);
 }
+//////////////////////////////////////////////////////////////////////////////
+static proc PertVectors(ideal Gold, vector target_weight, int pdeg)
+{
+int nV = nvars(basering);
+int nG = size(Gold);
+int i;
+number ntemp, maxAi, maxA;
+if(pdeg > nV || pdeg <= 0)
+  {
+    intvec v_null=0;
+    return v_null;
+  }
+if(pdeg == 1)
+  {
+    return target_weight;
+  }
+maxAi=0;
+for(i=1; i<=nV; i++)
+  {
+    ntemp = leadcoef(inprod(target_weight,gen(i)));
+    if(ntemp < 0)
+      {
+        ntemp = -ntemp;
+      }
+    if(maxAi < ntemp)
+      {
+        maxAi = ntemp;
+      }
+  }
+maxA = maxAi+pdeg-1;
+number epsilon = maxA*deg(Gold)+1;
+vector pert_weight = epsilon^(pdeg-1)*target_weight;
+for(i=2; i<=pdeg; i++)
+  {
+    pert_weight = pert_weight + epsilon^(pdeg-i)*gen(i);
+  }
+return(pert_weight);
+}
+
+
+//////////////////////////////////////////////////////////////////////////////
+static proc RandomNextWeight(ideal Gold, list L, vector curr_weight, vector target_weight,int weight_rad, int pdeg)
+"USAGE: RandomNextWeight(Gold, L, curr_weight, target_weight);
+RETURN: Intermediate next weight vector
+EXAMPLE: example RandomNextWeight; shows an example
+"
+{
+  int i,n1,n2,n3;
+  number norm, weight_norm;
+  def Rold = basering;
+  int nV = nvars(basering);
+  number ulast=last(curr_weight, target_weight, L);
+  vector new_weight=(1-ulast)*curr_weight+ulast*target_weight;
+  vector w1=cleardenom(new_weight);
+  intvec v1=changeType(w1);
+  list p= ringlist(Rold);
+  p[3][1][2]= v1;
+  def new_ring=ring(p);
+  setring new_ring;
+  ideal Gold = fetch(Rold, Gold);
+  n1=size(Initial(Gold));
+  setring Rold;
+  intvec next_weight;
+  kill new_ring;
+  while(1)
+  {
+    weight_norm = 0;
+    while(weight_norm == 0)
+    {
+      for(i=1; i<=nV; i++)
+      {
+        next_weight[i] = random(1,10000)-5000;
+        weight_norm = weight_norm + next_weight[i]^2;
+      }
+      norm = 0;
+      while(norm^2 < weight_norm)
+      {
+         norm=norm+1;
+      }
+      weight_norm = 1+norm;
+    }
+    new_weight = 0;
+    for(i=1; i<=nV;i++)
+    {
+      if(next_weight[i] < 0)
+      {
+        new_weight = new_weight + (1 + round(weight_rad*leadcoef(next_weight[i])/weight_norm))*gen(i);
+      }
+      else
+      {
+        new_weight = new_weight + ( round(weight_rad*leadcoef(next_weight[i])/weight_norm))*gen(i);
+      }
+    }
+    new_weight = new_weight + curr_weight;
+    if(test_in_cone(new_weight, L)==1)
+    {
+      break;
+    }
+  }
+  kill next_weight;
+  kill norm;
+  vector w2=cleardenom(new_weight);
+  intvec v2=changeType(w2);
+  p[3][1][2]= v2;
+  def new_ring=ring(p);
+  setring new_ring;
+  ideal Gold = fetch(Rold, Gold);
+  n2=size(Initial(Gold));
+  setring Rold;
+  kill new_ring;
+
+  vector w3=cleardenom(PertVectors(Gold,target_weight,pdeg));
+  intvec v3=changeType(w3);
+  p[3][1][2]= v1;
+  def new_ring=ring(p);
+  setring new_ring;
+  ideal Gold = fetch(Rold, Gold);
+  n3=size(Initial(Gold));
+  setring Rold;
+  kill new_ring;
+  kill p;
+
+  if(n2<n1)
+  {
+    if(n3<n2)
+    {
+      // n3<n2<n1
+      return(w3);
+    }
+    else
+    {
+      // n2<n1 und n2<=n3
+      return(w2);
+    }
+  }
+  else
+  {
+    if(n3<n1)
+    {
+      //n3<n1<=n2
+      return(w3);
+    }
+    else
+    {
+      // n1<=n3 und n1<=n2
+      return(w1);
+    }
+  }
+}
 
 //////////////////////////////////////////////////////////////////////////////
@@ -349 +606 @@
 {
  ideal In=Initial(Gold);
- ideal InG=sagbi(In,1)+In;
+ ideal InG=sagbi(In); //+In;
  ideal Gnew=Lift(In,InG,Gold);
  return(Gnew);
@@ -380 +637 @@
      for(i=1;i<=size(M);i++)
      { B[i]=M[i];}
-     f=sagbiNF(f,B,1);
+     f=sagbiNF(f,B,1)[1];
      J=J+f;
   }
@@ -598 +855 @@
 
 ///////////////////////////////////////////////////////////////////////////////*
-Further examples
+/*Further examples
 ring r=0,(x,y,z),lp;
 

Singular/extra.cc

@@ -8 +8 @@
 #define HAVE_WALK 1
 
-
-
-
+#ifdef HAVE_CONFIG_H
+#include "singularconfig.h"
+#endif /* HAVE_CONFIG_H */
 #include <kernel/mod2.h>
 #include <misc/auxiliary.h>
-#include <misc/sirandom.h>
-
+
+#define SI_DONT_HAVE_GLOBAL_VARS
 #include <factory/factory.h>
 
@@ -55 +55 @@
 
 
-#include <resources/feResource.h>
 #include <polys/monomials/ring.h>
 #include <kernel/polys.h>
@@ -69 +68 @@
 #include <kernel/fast_mult.h>
 #include <kernel/digitech.h>
-#include <kernel/GBEngine/stairc.h>
+#include <kernel/stairc.h>
+#include <kernel/febase.h>
 #include <kernel/ideals.h>
-#include <kernel/GBEngine/kstd1.h>
-#include <kernel/GBEngine/syz.h>
-#include <kernel/GBEngine/kutil.h>
-
-#include <kernel/GBEngine/shiftgb.h>
-#include <kernel/linear_algebra/linearAlgebra.h>
-
-#include <kernel/combinatorics/hutil.h>
+#include <kernel/kstd1.h>
+#include <kernel/syz.h>
+#include <kernel/kutil.h>
+
+#include <kernel/shiftgb.h>
+#include <kernel/linearAlgebra.h>
 
 // for tests of t-rep-GB
-#include <kernel/GBEngine/tgb.h>
-
-#include <kernel/linear_algebra/minpoly.h>
-
-#include <numeric/mpr_base.h>
+#include <kernel/tgb.h>
+
 
 #include "tok.h"
@@ -97 +92 @@
 #include "distrib.h"
 
+#include "minpoly.h"
 #include "misc_ip.h"
 
@@ -109 +105 @@
 
 #ifdef HAVE_RINGS
-#include <kernel/GBEngine/ringgb.h>
+#include <kernel/ringgb.h>
 #endif
 
 #ifdef HAVE_F5
-#include <kernel/GBEngine/f5gb.h>
+#include <kernel/f5gb.h>
 #endif
 
@@ -122 +118 @@
 
 #ifdef HAVE_SPECTRUM
-#include <kernel/spectrum/spectrum.h>
+#include <kernel/spectrum.h>
 #endif
 
@@ -129 +125 @@
 #include <polys/nc/ncSAMult.h> // for CMultiplier etc classes
 #include <polys/nc/sca.h>
-#include <kernel/GBEngine/nc.h>
+#include <kernel/nc.h>
 #include "ipconv.h"
 #ifdef HAVE_RATGRING
-#include <kernel/GBEngine/ratgring.h>
+#include <kernel/ratgring.h>
 #endif
 #endif
@@ -151 +147 @@
 
 #include <polys/clapconv.h>
-#include <kernel/GBEngine/kstdfac.h>
+#include <kernel/kstdfac.h>
 
 #include <polys/clapsing.h>
@@ -189 +185 @@
 static BOOLEAN jjEXTENDED_SYSTEM(leftv res, leftv h);
 #endif
+
+extern BOOLEAN jjJanetBasis(leftv res, leftv v);
 
 #ifdef ix86_Win  /* PySingular initialized? */
@@ -1908 +1906 @@
         if (h == NULL || h->Typ() != IDEAL_CMD ||
             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
-        {
-          Werror("system(\"Mwalk\", ideal, intvec, intvec) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"Mwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
-          return TRUE;
-        }
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
+            h->next->next->next == NULL || h->next->next->next->Typ() != RING_CMD)
+        {
+          Werror("system(\"Mwalk\", ideal, intvec, intvec, ring) expected");
+          return TRUE;
+        }
+
+        if ((((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length() != currRing->N ) &&
+            (((intvec*) h->next->Data())->length() != (currRing->N)*(currRing->N) &&
+            ((intvec*) h->next->next->Data())->length() != (currRing->N)*(currRing->N) ))
+        {
+          Werror("system(\"Mwalk\" ...) intvecs not of length %d or %d\n",
+                 currRing->N,(currRing->N)*(currRing->N));
+          return TRUE;
+        }
         ideal arg1 = (ideal) h->Data();
         intvec* arg2 = (intvec*) h->next->Data();
         intvec* arg3   =  (intvec*) h->next->next->Data();
-
-
-        ideal result = (ideal) Mwalk(arg1, arg2, arg3);
+        ring arg4 = (ring) h->next->next->next->Data();
+
+        ideal result = (ideal) Mwalk(arg1, arg2, arg3, arg4);
 
         res->rtyp = IDEAL_CMD;
@@ -1975 +1976 @@
       {
         if (h == NULL || h->Typ() != IDEAL_CMD ||
-            h->next == NULL || h->next->Typ() != INT_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INT_CMD ||
-            h->next->next->next == NULL ||
-              h->next->next->next->Typ() != INTVEC_CMD ||
-            h->next->next->next->next == NULL ||
-              h->next->next->next->next->Typ() != INTVEC_CMD||
-            h->next->next->next->next->next == NULL ||
-              h->next->next->next->next->next->Typ() != INT_CMD)
-        {
-          Werror("system(\"Mpwalk\", ideal, int, int, intvec, intvec, int) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->next->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->next->next->Data())->length()!=currRing->N)
-        {
-          Werror("system(\"Mpwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
+            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
+            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD||
+            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != RING_CMD)
+        {
+          Werror("system(\"Mpwalk\", ideal, intvec, intvec, int, int, ring) expected");
+          return TRUE;
+        }
+
+        if (((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length()!=currRing->N)
+        {
+          Werror("system(\"Mpwalk\" ...) intvecs not of length %d\n",currRing->N);
           return TRUE;
         }
         ideal arg1 = (ideal) h->Data();
-        int arg2 = (int) ((long)(h->next->Data()));
-        int arg3 = (int) ((long)(h->next->next->Data()));
-        intvec* arg4 = (intvec*) h->next->next->next->Data();
-        intvec* arg5   =  (intvec*) h->next->next->next->next->Data();
-        int arg6   =  (int) ((long)(h->next->next->next->next->next->Data()));
-
+        intvec* arg2 = (intvec*) h->next->Data();
+        intvec* arg3 = (intvec*) h->next->next->Data();
+        int arg4 = (int) (long) h->next->next->next->Data();
+        int arg5 = (int) (long) h->next->next->next->next->Data();
+        ring arg6 = (ring) h->next->next->next->next->next->Data();
 
         ideal result = (ideal) Mpwalk(arg1, arg2, arg3, arg4, arg5, arg6);
@@ -2012 +2008 @@
       else
       if (strcmp(sys_cmd, "Mrwalk") == 0)
-      { // Random Walk
+      {
         if (h == NULL || h->Typ() != IDEAL_CMD ||
             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
             h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
-            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD)
-        {
-          Werror("system(\"Mrwalk\", ideal, intvec, intvec, int, int) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"Mrwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
+            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != RING_CMD)
+        {
+          Werror("system(\"Mrwalk\", ideal, intvec, intvec, int, int, ring) expected");
+          return TRUE;
+        }
+
+        if ((((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length() != currRing->N ) &&
+            (((intvec*) h->next->Data())->length() != (currRing->N)*(currRing->N) &&
+            ((intvec*) h->next->next->Data())->length() != (currRing->N)*(currRing->N) ))
+        {
+          Werror("system(\"Mrwalk\" ...) intvecs not of length %d or %d\n",
+                 currRing->N,(currRing->N)*(currRing->N));
           return TRUE;
         }
@@ -2035 +2034 @@
         int arg4 = (int)(long) h->next->next->next->Data();
         int arg5 = (int)(long) h->next->next->next->next->Data();
-
-
-        ideal result = (ideal) Mrwalk(arg1, arg2, arg3, arg4, arg5);
+        ring arg6 = (ring) h->next->next->next->next->next->Data();
+
+
+        ideal result = (ideal) Mrwalk(arg1, arg2, arg3, arg4, arg5, arg6);
 
         res->rtyp = IDEAL_CMD;
@@ -2118 +2118 @@
         if (h == NULL || h->Typ() != IDEAL_CMD ||
             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
-        {
-          Werror("system(\"Mfwalk\", ideal, intvec, intvec) expected");
-          return TRUE;
-        }
-
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
+            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != RING_CMD)
+        {
+          Werror("system(\"Mfwalk\", ideal, intvec, intvec, int, ring) expected");
+          return TRUE;
+        }
         if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"Mfwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
-          return TRUE;
-        }
-        ideal arg1 = (ideal) h->Data();
-        intvec* arg2 = (intvec*) h->next->Data();
-        intvec* arg3   =  (intvec*) h->next->next->Data();
-
-        ideal result = (ideal) Mfwalk(arg1, arg2, arg3);
+            ((intvec*) h->next->next->Data())->length() != currRing->N)
+        {
+          Werror("system(\"Mfwalk\" ...) intvecs not of length %d\n",currRing->N);
+          return TRUE;
+        }
+        ideal arg1      =       (ideal) h->Data();
+        intvec* arg2    =       (intvec*) h->next->Data();
+        intvec* arg3    =       (intvec*) h->next->next->Data();
+        int arg4        =       (int)(long) h->next->next->next->Data();
+        ring arg5       =       (ring) h->next->next->next->next->Data();
+        ideal result    =       (ideal) Mfwalk(arg1, arg2, arg3, arg4, arg5);
 
         res->rtyp = IDEAL_CMD;
@@ -2144 +2145 @@
       else
       if (strcmp(sys_cmd, "Mfrwalk") == 0)
-      {
-        if (h == NULL || h->Typ() != IDEAL_CMD ||
-            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
-            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD)
-        {
-          Werror("system(\"Mfrwalk\", ideal, intvec, intvec, int) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"Mfrwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
-          return TRUE;
-        }
-        ideal arg1 = (ideal) h->Data();
-        intvec* arg2 = (intvec*) h->next->Data();
-        intvec* arg3 = (intvec*) h->next->next->Data();
-        int arg4 = (int)(long) h->next->next->next->Data();
-
-        ideal result = (ideal) Mfrwalk(arg1, arg2, arg3, arg4);
-
-        res->rtyp = IDEAL_CMD;
-        res->data =  result;
-
-        return FALSE;
-      }
-      else
-
-  #ifdef TRAN_Orig
-      if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
-      {
-        if (h == NULL || h->Typ() != IDEAL_CMD ||
-            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
-        {
-          Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
-          return TRUE;
-        }
-        ideal arg1 = (ideal) h->Data();
-        intvec* arg2 = (intvec*) h->next->Data();
-        intvec* arg3   =  (intvec*) h->next->next->Data();
-
-
-        ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3);
-
-        res->rtyp = IDEAL_CMD;
-        res->data =  result;
-
-        return FALSE;
-      }
-      else
-  #endif
-      if (strcmp(sys_cmd, "MAltwalk2") == 0)
-        {
-        if (h == NULL || h->Typ() != IDEAL_CMD ||
-            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
-        {
-          Werror("system(\"MAltwalk2\", ideal, intvec, intvec) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"MAltwalk2\" ...) intvecs not of length %d\n",
-                 currRing->N);
-          return TRUE;
-        }
-        ideal arg1 = (ideal) h->Data();
-        intvec* arg2 = (intvec*) h->next->Data();
-        intvec* arg3   =  (intvec*) h->next->next->Data();
-
-
-        ideal result = (ideal) MAltwalk2(arg1, arg2, arg3);
-
-        res->rtyp = IDEAL_CMD;
-        res->data =  result;
-
-        return FALSE;
-      }
-      else
-      if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
-      {
-        if (h == NULL || h->Typ() != IDEAL_CMD ||
-            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
-            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD||
-            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD)
-        {
-          Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec, int) expected");
-          return TRUE;
-        }
-
-        if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
-                 currRing->N);
-          return TRUE;
-        }
-        ideal arg1 = (ideal) h->Data();
-        intvec* arg2 = (intvec*) h->next->Data();
-        intvec* arg3   =  (intvec*) h->next->next->Data();
-        int arg4   =  (int) ((long)(h->next->next->next->Data()));
-
-        ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3, arg4);
-
-        res->rtyp = IDEAL_CMD;
-        res->data =  result;
-
-        return FALSE;
-      }
-      else
-      if (strcmp(sys_cmd, "TranMrImprovwalk") == 0)
       {
         if (h == NULL || h->Typ() != IDEAL_CMD ||
@@ -2274 +2150 @@
             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
             h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
-            h->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
-            h->next->next->next == NULL || h->next->next->next->next->next->Typ() != INT_CMD)
-        {
-          Werror("system(\"TranMrImprovwalk\", ideal, intvec, intvec) expected");
-          return TRUE;
-        }
-
+            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != RING_CMD)
+        {
+          Werror("system(\"Mfrwalk\", ideal, intvec, intvec, int, int, ring) expected");
+          return TRUE;
+        }
         if (((intvec*) h->next->Data())->length() != currRing->N &&
-            ((intvec*) h->next->next->Data())->length() != currRing->N )
-        {
-          Werror("system(\"TranMrImprovwalk\" ...) intvecs not of length %d\n", currRing->N);
+            ((intvec*) h->next->next->Data())->length() != currRing->N)
+        {
+          Werror("system(\"Mfrwalk\" ...) intvecs not of length %d\n",currRing->N);
           return TRUE;
         }
@@ -2292 +2167 @@
         int arg4 = (int)(long) h->next->next->next->Data();
         int arg5 = (int)(long) h->next->next->next->next->Data();
-        int arg6 = (int)(long) h->next->next->next->next->next->Data();
-
-        ideal result = (ideal) TranMrImprovwalk(arg1, arg2, arg3, arg4, arg5, arg6);
+        ring arg6 = (ring) h->next->next->next->next->next->Data();
+
+        ideal result = (ideal) Mfrwalk(arg1, arg2, arg3, arg4, arg5, arg6);
 
         res->rtyp = IDEAL_CMD;
@@ -2302 +2177 @@
       }
       else
-
-  #endif
+      if (strcmp(sys_cmd, "Mprwalk") == 0)
+      {
+        if (h == NULL || h->Typ() != IDEAL_CMD ||
+            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
+            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != INT_CMD ||
+            h->next->next->next->next->next->next == NULL || h->next->next->next->next->next->next->Typ() != RING_CMD)
+        {
+          Werror("system(\"Mprwalk\", ideal, intvec, intvec, int, int, int, ring) expected");
+          return TRUE;
+        }
+        if (((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length() != currRing->N )
+        {
+          Werror("system(\"Mrwalk\" ...) intvecs not of length %d\n",
+                 currRing->N);
+          return TRUE;
+        }
+        ideal arg1 = (ideal) h->Data();
+        intvec* arg2 = (intvec*) h->next->Data();
+        intvec* arg3 =  (intvec*) h->next->next->Data();
+        int arg4 = (int)(long) h->next->next->next->Data();
+        int arg5 = (int)(long) h->next->next->next->next->Data();
+        int arg6 = (int)(long) h->next->next->next->next->next->Data();
+        ring arg7 = (ring) h->next->next->next->next->next->next->Data();
+
+
+        ideal result = (ideal) Mprwalk(arg1, arg2, arg3, arg4, arg5, arg6, arg7);
+
+        res->rtyp = IDEAL_CMD;
+        res->data =  result;
+
+        return FALSE;
+      }
+      else
+
+  #ifdef TRAN_Orig
+      if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
+      {
+        if (h == NULL || h->Typ() != IDEAL_CMD ||
+            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
+        {
+          Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec) expected");
+          return TRUE;
+        }
+
+        if (((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length() != currRing->N )
+        {
+          Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
+                 currRing->N);
+          return TRUE;
+        }
+        ideal arg1 = (ideal) h->Data();
+        intvec* arg2 = (intvec*) h->next->Data();
+        intvec* arg3   =  (intvec*) h->next->next->Data();
+
+
+        ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3);
+
+        res->rtyp = IDEAL_CMD;
+        res->data =  result;
+
+        return FALSE;
+      }
+      else
+  #endif
+      if (strcmp(sys_cmd, "MAltwalk2") == 0)
+        {
+        if (h == NULL || h->Typ() != IDEAL_CMD ||
+            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
+        {
+          Werror("system(\"MAltwalk2\", ideal, intvec, intvec) expected");
+          return TRUE;
+        }
+
+        if (((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length() != currRing->N )
+        {
+          Werror("system(\"MAltwalk2\" ...) intvecs not of length %d\n",
+                 currRing->N);
+          return TRUE;
+        }
+        ideal arg1 = (ideal) h->Data();
+        intvec* arg2 = (intvec*) h->next->Data();
+        intvec* arg3   =  (intvec*) h->next->next->Data();
+
+
+        ideal result = (ideal) MAltwalk2(arg1, arg2, arg3);
+
+        res->rtyp = IDEAL_CMD;
+        res->data =  result;
+
+        return FALSE;
+      }
+      else
+      if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
+      {
+        if (h == NULL || h->Typ() != IDEAL_CMD ||
+            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
+            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD||
+            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD)
+        {
+          Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec, int) expected");
+          return TRUE;
+        }
+
+        if (((intvec*) h->next->Data())->length() != currRing->N &&
+            ((intvec*) h->next->next->Data())->length() != currRing->N )
+        {
+          Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
+                 currRing->N);
+          return TRUE;
+        }
+        ideal arg1 = (ideal) h->Data();
+        intvec* arg2 = (intvec*) h->next->Data();
+        intvec* arg3   =  (intvec*) h->next->next->Data();
+        int arg4   =  (int) ((long)(h->next->next->next->Data()));
+
+        ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3, arg4);
+
+        res->rtyp = IDEAL_CMD;
+        res->data =  result;
+
+        return FALSE;
+      }
+      else
+#endif
   /*================= Extended system call ========================*/
      {
@@ -2319 +2324 @@
 #ifdef HAVE_EXTENDED_SYSTEM
   // You can put your own system calls here
-#  include <kernel/fglm/fglmcomb.cc>
-#  include <kernel/fglm/fglm.h>
+#  include <kernel/fglmcomb.cc>
+#  include <kernel/fglm.h>
 #  ifdef HAVE_NEWTON
 #    include <hc_newton.h>
@@ -2326 +2331 @@
 #  include <polys/mod_raw.h>
 #  include <polys/monomials/ring.h>
-#  include <kernel/GBEngine/shiftgb.h>
+#  include <kernel/shiftgb.h>
 
 static BOOLEAN jjEXTENDED_SYSTEM(leftv res, leftv h)
@@ -2682 +2687 @@
 //       }
 //       else
+  /*==================== isSqrFree =============================*/
+      if(strcmp(sys_cmd,"isSqrFree")==0)
+      {
+        if ((h!=NULL) &&(h->Typ()==POLY_CMD))
+        {
+          res->rtyp=INT_CMD;
+          res->data=(void *)(long) singclap_isSqrFree((poly)h->Data(), currRing);
+          return FALSE;
+        }
+        else
+          WerrorS("poly expected");
+      }
+      else
   /*==================== pDivStat =============================*/
   #if defined(PDEBUG) || defined(PDIV_DEBUG)
@@ -3142 +3160 @@
       else
   #endif
-  /*==================== Roune Hilb  =================*/
-       if (strcmp(sys_cmd, "hilbroune") == 0)
-       {
-         ideal I;
-         if ((h!=NULL) && (h->Typ()==IDEAL_CMD))
-         {
-           I=(ideal)h->CopyD();
-           slicehilb(I);
-         }
-         else return TRUE;
-         return FALSE;
-       }
   /*==================== minor =================*/
       if (strcmp(sys_cmd, "minor")==0)
@@ -3591 +3597 @@
         {
 #ifdef HAVE_PLURAL
+          Print("NTL_0:%d (use NTL for gcd of polynomials in char 0)\n",isOn(SW_USE_NTL_GCD_0));
+          Print("NTL_p:%d (use NTL for gcd of polynomials in char p)\n",isOn(SW_USE_NTL_GCD_P));
           Print("EZGCD:%d (use EZGCD for gcd of polynomials in char 0)\n",isOn(SW_USE_EZGCD));
           Print("EZGCD_P:%d (use EZGCD_P for gcd of polynomials in char p)\n",isOn(SW_USE_EZGCD_P));
@@ -3606 +3614 @@
           char *s=(char *)h->Data();
 #ifdef HAVE_PLURAL
+          if (strcmp(s,"NTL_0")==0) { if (d) On(SW_USE_NTL_GCD_0); else Off(SW_USE_NTL_GCD_0); } else
+          if (strcmp(s,"NTL_p")==0) { if (d) On(SW_USE_NTL_GCD_P); else Off(SW_USE_NTL_GCD_P); } else
           if (strcmp(s,"EZGCD")==0) { if (d) On(SW_USE_EZGCD); else Off(SW_USE_EZGCD); } else
           if (strcmp(s,"EZGCD_P")==0) { if (d) On(SW_USE_EZGCD_P); else Off(SW_USE_EZGCD_P); } else
@@ -3868 +3878 @@
   if (strcmp(sys_cmd,"reservedLink")==0)
   {
-    extern si_link ssiCommandLink();
+    si_link ssiCommandLink();
     res->rtyp=LINK_CMD;
     si_link p=ssiCommandLink();

Singular/walk.cc

@@ -18 +18 @@
 //#define CHECK_IDEAL
 //#define CHECK_IDEAL_MWALK
+//#define CHECK_IDEAL_MFRWALK
 
 //#define NEXT_VECTORS_CC
@@ -35 +36 @@
 /* includes */
 
-#include <kernel/mod2.h>
-#include <misc/intvec.h>
-#include <Singular/cntrlc.h>
-#include <misc/options.h>
-#include <omalloc/omalloc.h>
-#include <Singular/ipshell.h>
-#include <Singular/ipconv.h>
-#include <coeffs/ffields.h>
-#include <coeffs/coeffs.h>
-#include <Singular/subexpr.h>
-#include <polys/templates/p_Procs.h>
-
-#include <polys/monomials/maps.h>
-
-/* include Hilbert-function */
-#include <kernel/GBEngine/stairc.h>
-
-/** kstd2.cc */
-#include <kernel/GBEngine/kutil.h>
-#include <kernel/GBEngine/khstd.h>
-
-#include <Singular/walk.h>
-#include <kernel/polys.h>
-#include <kernel/ideals.h>
-#include <Singular/ipid.h>
-#include <Singular/tok.h>
-#include <coeffs/numbers.h>
-#include <Singular/ipid.h>
-#include <polys/monomials/ring.h>
-#include <kernel/GBEngine/kstd1.h>
-#include <polys/matpol.h>
-#include <polys/weight.h>
-#include <misc/intvec.h>
-#include <kernel/GBEngine/syz.h>
-#include <Singular/lists.h>
-#include <polys/prCopy.h>
-#include <polys/monomials/ring.h>
-//#include <polys/ext_fields/longalg.h>
-#include <polys/clapsing.h>
-
-#include <coeffs/mpr_complex.h>
-
 #include <stdio.h>
+#include <stdlib.h>
 // === Zeit & System (Holger Croeni ===
 #include <time.h>
@@ -88 +48 @@
 #include <sys/types.h>
 
+
+//#include "config.h"
+#include <kernel/mod2.h>
+#include <misc/intvec.h>
+#include <Singular/cntrlc.h>
+#include <misc/options.h>
+#include <omalloc/omalloc.h>
+#include <kernel/febase.h>
+#include <Singular/ipshell.h>
+#include <Singular/ipconv.h>
+#include <coeffs/ffields.h>
+#include <coeffs/coeffs.h>
+#include <Singular/subexpr.h>
+#include <polys/templates/p_Procs.h>
+
+#include <polys/monomials/maps.h>
+
+/* include Hilbert-function */
+#include <kernel/stairc.h>
+
+/** kstd2.cc */
+#include <kernel/kutil.h>
+#include <kernel/khstd.h>
+
+#include <Singular/walk.h>
+#include <kernel/polys.h>
+#include <kernel/ideals.h>
+#include <Singular/ipid.h>
+#include <Singular/tok.h>
+#include <kernel/febase.h>
+#include <coeffs/numbers.h>
+#include <Singular/ipid.h>
+#include <polys/monomials/ring.h>
+#include <kernel/kstd1.h>
+#include <polys/matpol.h>
+#include <polys/weight.h>
+#include <misc/intvec.h>
+#include <kernel/syz.h>
+#include <Singular/lists.h>
+#include <polys/prCopy.h>
+#include <polys/monomials/ring.h>
+//#include <polys/ext_fields/longalg.h>
+#ifdef HAVE_FACTORY
+#include <polys/clapsing.h>
+#endif
+
+#include <coeffs/mpr_complex.h>
+
 int nstep;
 
@@ -118 +126 @@
 }
 
-/************************************
- * construct the set s from F u {P} *
- ************************************/
-// unused
-#if 0
-static void initSSpecialCC (ideal F, ideal Q, ideal P,kStrategy strat)
-{
-  int   i,pos;
-
-  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
-  else i=setmaxT;
-
-  strat->ecartS=initec(i);
-  strat->sevS=initsevS(i);
-  strat->S_2_R=initS_2_R(i);
-  strat->fromQ=NULL;
-  strat->Shdl=idInit(i,F->rank);
-  strat->S=strat->Shdl->m;
-
-  // - put polys into S -
-  if (Q!=NULL)
-  {
-    strat->fromQ=initec(i);
-    memset(strat->fromQ,0,i*sizeof(int));
-    for (i=0; i<IDELEMS(Q); i++)
-    {
-      if (Q->m[i]!=NULL)
-      {
-        LObject h;
-        h.p = pCopy(Q->m[i]);
-        //if (TEST_OPT_INTSTRATEGY)
-        //{
-        //  //pContent(h.p);
-        //  h.pCleardenom(); // also does a pContent
-        //}
-        //else
-        //{
-        //  h.pNorm();
-        //}
-        strat->initEcart(&h);
-        if (rHasLocalOrMixedOrdering_currRing())
-        {
-          deleteHC(&h,strat);
-        }
-        if (h.p!=NULL)
-        {
-          if (strat->sl==-1)
-            pos =0;
-          else
-          {
-            pos = posInS(strat,strat->sl,h.p,h.ecart);
-          }
-          h.sev = pGetShortExpVector(h.p);
-          h.SetpFDeg();
-          strat->enterS(h,pos,strat, strat->tl+1);
-          enterT(h, strat);
-          strat->fromQ[pos]=1;
-        }
-      }
-    }
-  }
-  //- put polys into S -
-  for (i=0; i<IDELEMS(F); i++)
-  {
-    if (F->m[i]!=NULL)
-    {
-      LObject h;
-      h.p = pCopy(F->m[i]);
-      if (rHasGlobalOrdering(currRing))
-      {
-        //h.p=redtailBba(h.p,strat->sl,strat);
-        h.p=redtailBba(h.p,strat->sl,strat);
-      }
-      else
-      {
-        deleteHC(&h,strat);
-      }
-      strat->initEcart(&h);
-      if (h.p!=NULL)
-      {
-        if (strat->sl==-1)
-          pos =0;
-        else
-          pos = posInS(strat,strat->sl,h.p,h.ecart);
-        h.sev = pGetShortExpVector(h.p);
-        strat->enterS(h,pos,strat, strat->tl+1);
-        h.length = pLength(h.p);
-        h.SetpFDeg();
-        enterT(h,strat);
-      }
-    }
-  }
-#ifdef INITSSPECIAL
-  for (i=0; i<IDELEMS(P); i++)
-  {
-    if (P->m[i]!=NULL)
-    {
-      LObject h;
-      h.p=pCopy(P->m[i]);
-      strat->initEcart(&h);
-      h.length = pLength(h.p);
-      if (TEST_OPT_INTSTRATEGY)
-      {
-        h.pCleardenom();
-      }
-      else
-      {
-        h.pNorm();
-      }
-      if(strat->sl>=0)
-      {
-        if (rHasGlobalOrdering(currRing))
-        {
-          h.p=redBba(h.p,strat->sl,strat);
-          if (h.p!=NULL)
-            h.p=redtailBba(h.p,strat->sl,strat);
-        }
-        else
-        {
-          h.p=redMora(h.p,strat->sl,strat);
-          strat->initEcart(&h);
-        }
-        if(h.p!=NULL)
-        {
-          if (TEST_OPT_INTSTRATEGY)
-          {
-            h.pCleardenom();
-          }
-          else
-          {
-            h.is_normalized = 0;
-            h.pNorm();
-          }
-          h.sev = pGetShortExpVector(h.p);
-          h.SetpFDeg();
-          pos = posInS(strat->S,strat->sl,h.p,h.ecart);
-          enterpairsSpecial(h.p,strat->sl,h.ecart,pos,strat,strat->tl+1);
-          strat->enterS(h,pos,strat, strat->tl+1);
-          enterT(h,strat);
-        }
-      }
-      else
-      {
-        h.sev = pGetShortExpVector(h.p);
-        h.SetpFDeg();
-        strat->enterS(h,0,strat, strat->tl+1);
-        enterT(h,strat);
-      }
-    }
-  }
-#endif
-}
-#endif
-
 /*****************
  *interreduce F  *
@@ -280 +134 @@
   kStrategy strat = new skStrategy;
 
-//  if (TEST_OPT_PROT)
-//  {
-//    writeTime("start InterRed:");
-//    mflush();
-//  }
   //strat->syzComp     = 0;
   strat->kHEdgeFound = (currRing->ppNoether) != NULL;
@@ -312 +161 @@
   initS(F,Q,strat);
 
-  /*
-  timetmp=clock();//22.01.02
-  initSSpecialCC(F,Q,NULL,strat);
-  tininitS=tininitS+clock()-timetmp;//22.01.02
-  */
   if(TEST_OPT_REDSB)
   {
@@ -348 +192 @@
     strat->fromQ = NULL;
   }
-//  if (TEST_OPT_PROT)
-//  {
-//    writeTime("end Interred:");
-//    mflush();
-//  }
   ideal shdl=strat->Shdl;
   idSkipZeroes(shdl);
@@ -360 +199 @@
 }
 
-//unused
-#if 0
+#ifdef TIME_TEST
 static void TimeString(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
                        clock_t tlf,clock_t tred, clock_t tnw, int step)
@@ -401 +239 @@
 #endif
 
-//unused
-#if 0
+#ifdef TIME_TEST
 static void TimeStringFractal(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
                        clock_t textra, clock_t tlf,clock_t tred, clock_t tnw)
@@ -431 +268 @@
 #endif
 
-#ifdef CHECK_IDEAL_MWALK
 static void idString(ideal L, const char* st)
 {
@@ -443 +279 @@
   Print(" %s;", pString(L->m[nL-1]));
 }
-#endif
-
-#if defined(CHECK_IDEAL_MWALK) || defined(ENDWALKS)
+
 static void headidString(ideal L, char* st)
 {
@@ -457 +291 @@
   Print(" %s;", pString(pHead(L->m[nL-1])));
 }
-#endif
-
-#if defined(CHECK_IDEAL_MWALK) || defined(ENDWALKS)
+
 static void idElements(ideal L, char* st)
 {
@@ -471 +303 @@
   }
   int j, nsame;
-  // int  nk=0;
   for(i=0; i<nL; i++)
   {
@@ -497 +328 @@
   omFree(K);
 }
-#endif
-
 
 static void ivString(intvec* iv, const char* ch)
@@ -512 +341 @@
 }
 
-//unused
-//#if 0
 static void MivString(intvec* iva, intvec* ivb, intvec* ivc)
 {
@@ -536 +363 @@
   Print("%d)", (*ivc)[nV]);
 }
-//#endif
 
 /********************************************************************
@@ -577 +403 @@
   mpz_clear(g);
 }
-
-//unused
-#if 0
-static int isVectorNeg(intvec* omega)
-{
-  int i;
-
-  for(i=omega->length(); i>=0; i--)
-  {
-    if((*omega)[i]<0)
-    {
-      return 1;
-    }
-  }
-  return 0;
-}
-#endif
 
 /********************************************************************
@@ -627 +436 @@
     {
       PrintLn();
-      PrintS("\n// ** OVERFLOW in \"MwalkInitialForm\": ");
+      PrintS("\n//** MLmWeightedDegree: OVERFLOW: ");
       mpz_out_str( stdout, 10, zsum);
-      PrintS(" is greater than 2147483647 (max. integer representation)");
+      PrintS(" is greater than 2147483647 (max. integer representation).\n");
       Overflow_Error = TRUE;
     }
@@ -764 +573 @@
   if(G->m[0] == NULL)
   {
-    PrintS("//** the result may be WRONG, i.e. 0!!\n");
-    return 0;
+    idString(G,"G");
+    WerrorS("//** test_w_in_ConeCC: the result may be wrong, i.e. equal zero.\n");
   }
 
@@ -941 +750 @@
 {
   int i, nR = iv->length();
-
+  
   intvec* ivm = new intvec(nR*nR);
 
@@ -951 +760 @@
   {
     (*ivm)[i*nR+i-1] = 1;
+  }
+  return ivm;
+}
+
+/*****************************************************************************
+* create a weight matrix order as intvec of an extra weight vector (a(iv),lp)*
+******************************************************************************/
+intvec* MivMatrixOrderRefine(intvec* iv, intvec* iw)
+{
+  assume(iv->length() == iw->length());
+  int i, nR = iv->length();
+  
+  intvec* ivm = new intvec(nR*nR);
+
+  for(i=0; i<nR; i++)
+  {
+    (*ivm)[i] = (*iv)[i];
+    (*ivm)[i+nR] = (*iw)[i];
+  }
+  for(i=2; i<nR; i++)
+  {
+    (*ivm)[i*nR+i-2] = 1;
   }
   return ivm;
@@ -981 +812 @@
 }
 
-//unused
-/*****************************************************************************
- * print the max total degree and the max coefficient of G                   *
- *****************************************************************************/
-#if 0
-static void checkComplexity(ideal G, char* cG)
-{
-  int nV = currRing->N;
-  int nG = IDELEMS(G);
-  intvec* ivUnit = Mivdp(nV);
-  int i, tmpdeg, maxdeg=0;
-  number tmpcoeff , maxcoeff=currRing->cf->nNULL;
-  poly p;
-  for(i=nG-1; i>=0; i--)
-  {
-    tmpdeg = MwalkWeightDegree(G->m[i], ivUnit);
-    if(tmpdeg > maxdeg )
-    {
-      maxdeg = tmpdeg;
-    }
-  }
-
-  for(i=nG-1; i>=0; i--)
-  {
-    p = pCopy(G->m[i]);
-    while(p != NULL)
-    {
-      //tmpcoeff = pGetCoeff(pHead(p));
-      tmpcoeff = pGetCoeff(p);
-      if(nGreater(tmpcoeff,maxcoeff))
-      {
-         maxcoeff = nCopy(tmpcoeff);
-      }
-      pIter(p);
-    }
-    pDelete(&p);
-  }
-  p = pNSet(maxcoeff);
-  char* pStr = pString(p);
-  delete ivUnit;
-  Print("// max total degree of %s = %d\n",cG, maxdeg);
-  Print("// max coefficient of %s  = %s", cG, pStr);//ing(p));
-  Print(" which consists of %d digits", (int)strlen(pStr));
-  PrintLn();
-}
-#endif
-
+/**********************************************
+ * Look for the smallest absolut value in vec *
+ **********************************************/
+static int MivAbsMax(intvec* vec)
+{
+  int i,k;
+  if((*vec)[0] < 0)
+  {
+    k = -(*vec)[0];
+  }
+  else
+  {
+    k = (*vec)[0];
+  }
+  for(i=1; i < (vec->length()); i++)
+  {
+    if((*vec)[i] < 0)
+    {
+      if(-(*vec)[i] > k)
+      {
+        k = -(*vec)[i];
+      }
+    }
+    else
+    {
+      if((*vec)[i] > k)
+      {
+        k = (*vec)[i];
+      }
+    }
+  }
+  return k;
+}
 /*****************************************************************************
 * If target_ord = intmat(A1, ..., An) then calculate the perturbation        *
@@ -1041 +858 @@
 intvec* MPertVectors(ideal G, intvec* ivtarget, int pdeg)
 {
-  // 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);
+  int nV = currRing->N, i=0, j=0, 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!!");
+    WerrorS("\n//** MPertVectors: The perturbed degree is wrong.\n");
     return v_null;
   }
@@ -1062 +874 @@
   }
   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.
+  }
+  // Compute max1 = Max(A_2)+Max(A_3)+...+Max(A_pdeg), where the A_i is the i-th row of the matrix target_ord.
   int ntemp, maxAi, maxA=0;
   for(i=1; i<pdeg; i++)
@@ -1094 +903 @@
   }
 
-  // Calculate inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.
-
-  intvec* ivUnit = Mivdp(nV);
-
+  // Compute inveps = 1/eps, where 1/eps > totaldeg(p)*max1 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));
+     mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], Mivdp(nV)));
      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);
@@ -1121 +924 @@
   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: ");
+  PrintS("\n//** MPertVectors: 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++ )
+  // 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++)
@@ -1167 +967 @@
 
   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;
-  }
+  }
+  while(MivAbsMax(pert_vector1)>100000)
+  {
+    j = 0;
+    for(i=0; i<nV; 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)
+    {
+      break;
+    }
 
 // 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");
+    if(test_w_in_ConeCC(G,pert_vector1) != 0)
+    {
+      for(i=0; i<nV; i++)
+      {
+        mpz_set_si(pert_vector[i], (*pert_vector1)[i]);
+      }
+    }
+    else
+    {
+      break;
+    }
   }
   delete pert_vector1;
 
-  CHECK_OVERFLOW:
+  //CHECK_OVERFLOW:
   intvec* result = new intvec(nV);
 
-  /* 2147483647 is max. integer representation in SINGULAR */
+// 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++)
   {
@@ -1213 +1016 @@
     if(mpz_cmp(pert_vector[i], sing_int)>=0)
     {
-      ntrue++;
       if(Overflow_Error == FALSE)
       {
         Overflow_Error = TRUE;
-        PrintS("\n// ** OVERFLOW in \"MPertvectors\": ");
+        PrintS("\n//** MPertvectors: OVERFLOW: ");
         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);
+        PrintS(" is greater than 2147483647 (max. integer representation).\n");
+        Print("\n//** MPertvectors: So vector[%d] := %d may be wrong.\n", i+1, (*result)[i]);
+      }
+    }
   }
 
@@ -1234 +1030 @@
   mpz_clear(sing_int);
   omFree(pert_vector);
-  //omFree(pert_vector1);
+
   mpz_clear(tot_deg);
   mpz_clear(maxdeg);
@@ -1269 +1065 @@
   if(pdeg > nV || pdeg <= 0)
   {
-    WerrorS("//** The perturbed degree is wrong!!");
+    WerrorS("\n//** MPertVectorslp: The perturbed degree is wrong.\n");
     return pert_vector;
   }
@@ -1322 +1118 @@
   // Print(" %d", inveps);
 #else
-  PrintS("\n// the \"big\" inverse epsilon %d", inveps);
+  PrintS("\n//** MPertVectorslp: the \"big\" inverse epsilon %d.\n", inveps);
 #endif
 
@@ -1434 +1230 @@
   return(ivM);
 }
-
-//unused
-#if 0
-static intvec* MatrixOrderdp(int nV)
-{
-  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);
-}
-#endif
 
 intvec* MivUnit(int nV)
@@ -1576 +1353 @@
   BOOLEAN nflow = FALSE;
 
-  // computes gcd
+  // compute gcd
   mpz_set(ztmp, pert_vector[0]);
   for(i=0; i<niv; i++)
@@ -1606 +1383 @@
   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
+  // check whether or not 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;
@@ -1625 +1400 @@
   {
     delete result1;
-    // Print("\n// Mfpertwalk: geaenderter vector liegt nicht in Groebnerkegel! \n");
   }
 
@@ -1640 +1414 @@
         Overflow_Error = TRUE;
         Print("\n// Xlev = %d and the %d-th element is", Xnlev,  i+1);
-        PrintS("\n// ** OVERFLOW in \"Mfpertvector\": ");
+        PrintS("\n//** Mfpertvector: OVERFLOW: ");
         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]);
+        PrintS(" is greater than 2147483647 (max. integer representation).\n");
+        Print("\n//** Mfpertvector: So vector[%d] := %d may be wrong.\n", i+1, (*result)[i]);
       }
     }
@@ -1706 +1480 @@
 }
 
-/*********************************************************************
- * G is a red. Groebner basis w.r.t. <_1                             *
- * Gomega is an initial form ideal of <G> w.r.t. a weight vector w   *
- * M is a subideal of <Gomega> and M selft is a red. Groebner basis  *
- *    of the ideal <Gomega> w.r.t. <_w                               *
- * Let m_i = h1.gw1 + ... + hs.gws for each m_i in M; gwi in Gomega  *
- * return F with n(F) = n(M) and f_i = h1.g1 + ... + hs.gs for each i*
- ********************************************************************/
+
+/*********************************************************
+* Let Gomega be the inital form ideal of G.              *
+* Let be M = {m_1,...,m_s} be the reduced GB of Gomega.  *
+* Hence, mi=sum(h_ij.in_g_j) for suitable hij, i=1,...,s *
+* Compute F = {f_1,...,f_s} with f_i=sum h_ij.g_j        *
+**********************************************************/
 static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
 {
-  ideal Mtmp = idLift(Gw, M, NULL, FALSE, TRUE, TRUE, NULL);
-
-  // If Gw is a GB, then isSB = TRUE, otherwise FALSE
-  // So, it is better, if one tests whether Gw is a GB
-  // in ideals.cc:
-  // idLift (ideal mod, ideal submod,ideal * rest, BOOLEAN goodShape,
-  //           BOOLEAN isSB,BOOLEAN divide,matrix * unit)
-
-  // Let be Mtmp = {m1,...,ms}, where mi=sum hij.in_gj, for all i=1,...,s
-  // We compute F = {f1,...,fs}, where fi=sum hij.gj
-  int i, j, nM = IDELEMS(Mtmp);
+  ideal M_temp = idLift(Gw, M, NULL, FALSE, TRUE, TRUE, NULL);
+  idSkipZeroes(M_temp);
+  int i, j, nM = IDELEMS(M_temp);
   ideal idpol, idLG;
   ideal F = idInit(nM, 1);
-
   for(i=0; i<nM; i++)
   {
-     idpol = idVec2Ideal(Mtmp->m[i]);
-     idLG = MidMult(idpol, G);
-     idpol = NULL;
+     //idpol = idVec2Ideal(M_temp->m[i]);
+     //idLG = MidMult(idpol, G);
+     //idpol = NULL;
+     idLG = MidMult(idVec2Ideal(M_temp->m[i]), G);
+    // PrintS("uups");
      F->m[i] = NULL;
      for(j=IDELEMS(idLG)-1; j>=0; j--)
@@ -1740 +1506 @@
        F->m[i] = pAdd(F->m[i], idLG->m[j]);
        idLG->m[j]=NULL;
+       idSkipZeroes(idLG);
      }
      idDelete(&idLG);
   }
-  idDelete(&Mtmp);
-  return F;
+  //PrintS("aaps");
+  //idDelete(&idpol);
+  idDelete(&M_temp);
+  //F=kStd(F,NULL,testHomog,NULL,NULL,0,NULL,NULL);
+  return(F);
 }
 
@@ -1805 +1575 @@
 }
 
-/**********************************************
- * Look for the smallest absolut value in vec *
- **********************************************/
-static int MivAbsMax(intvec* vec)
-{
-  int i,k;
-  if((*vec)[0] < 0)
-  {
-    k = -(*vec)[0];
-  }
-  else
-  {
-    k = (*vec)[0];
-  }
-  for(i=1; i < (vec->length()); i++)
-  {
-    if((*vec)[i] < 0)
-    {
-      if(-(*vec)[i] > k)
-      {
-        k = -(*vec)[i];
-      }
-    }
-    else
-    {
-      if((*vec)[i] > k)
-      {
-        k = (*vec)[i];
-      }
-    }
-  }
-  return k;
-}
+/*****************************************************************************
+ * compute the gcd of the entries of the vectors curr_weight and diff_weight *
+ *****************************************************************************/
+static int simplify_gcd(intvec* curr_weight, intvec* diff_weight)
+{
+  int j;
+  int nRing = currRing->N;
+  int gcd_tmp = (*curr_weight)[0];
+  for (j=1; j<nRing; j++)
+  {
+    gcd_tmp = gcd(gcd_tmp, (*curr_weight)[j]);
+    if(gcd_tmp == 1)
+    {
+      break;
+    }
+  }
+  if(gcd_tmp != 1)
+  {
+    for (j=0; j<nRing; j++)
+    {
+    gcd_tmp = gcd(gcd_tmp, (*diff_weight)[j]);
+    if(gcd_tmp == 1)
+      {
+        break;
+      }
+    }
+  }
+  return gcd_tmp;
+}
+
 
 /**********************************************************************
@@ -1849 +1616 @@
   Overflow_Error = FALSE;
 
-  assume(currRing != NULL && curr_weight != NULL &&
-         target_weight != NULL && G != NULL);
+  assume(currRing != NULL && curr_weight != NULL && target_weight != NULL && G != NULL);
 
   int nRing = currRing->N;
-  int checkRed, j, kkk, nG = IDELEMS(G);
+  int nG = IDELEMS(G);
+  int checkRed, j;
   intvec* ivtemp;
 
@@ -1870 +1637 @@
   mpz_set_si(sing_int,  2147483647);
 
-  mpz_t sing_int_half;
-  mpz_init(sing_int_half);
-  mpz_set_si(sing_int_half,  3*(1073741824/2));
-
   mpz_t deg_w0_p1, deg_d0_p1;
   mpz_init(deg_w0_p1);
@@ -1884 +1647 @@
   mpz_t t_null;
   mpz_init(t_null);
+  mpz_set_si(t_null,0);
 
   mpz_t ggt;
@@ -1891 +1655 @@
   mpz_init(dcw);
 
-  //int tn0, tn1, tz1, ncmp, gcd_tmp, ntmp;
   int gcd_tmp;
   intvec* diff_weight = MivSub(target_weight, curr_weight);
-
   intvec* diff_weight1 = MivSub(target_weight, curr_weight);
   poly g;
-  //poly g, gw;
+#ifdef  NEXT_VECTORS_CC
+  ivString(diff_weight, "//** MwalkNextWeightCC: diff_weight");
+#endif
   for (j=0; j<nG; j++)
   {
@@ -1906 +1670 @@
       mpz_set_si(deg_w0_p1, MivDotProduct(ivtemp, curr_weight));
       mpz_set_si(deg_d0_p1, MivDotProduct(ivtemp, diff_weight));
+#ifdef  NEXT_VECTORS_CC
+      ivString(ivtemp, "//** MwalkNextWeightCC: ivtemp");
+      PrintS("\n//** MwalkNextWeightCC: weighted degree w. r. t. curr_weight: ");
+      mpz_out_str( stdout, 10, deg_w0_p1);
+      PrintS("\n//** MwalkNextWeightCC: weighted degree w. r. t. diff_weight: ");
+      mpz_out_str( stdout, 10, deg_d0_p1);
+#endif
       delete ivtemp;
 
@@ -1914 +1685 @@
         mpz_set_si(MwWd, MivDotProduct(ivtemp, curr_weight));
         mpz_sub(s_zaehler, deg_w0_p1, MwWd);
-
-        if(mpz_cmp(s_zaehler, t_null) != 0)
+#ifdef NEXT_VECTORS_CC
+        PrintS("\n//** MwalkNextWeightCC: Grad bzgl. curr_weight: ");
+        mpz_out_str( stdout, 10, MwWd);
+        PrintS("\n//** MwalkNextWeightCC: s_zaehler: ");
+        mpz_out_str( stdout, 10, s_zaehler);
+#endif
+        if(mpz_cmp(s_zaehler,t_null) != 0)
         {
           mpz_set_si(MwWd, MivDotProduct(ivtemp, diff_weight));
           mpz_sub(s_nenner, MwWd, deg_d0_p1);
-
+#ifdef NEXT_VECTORS_CC
+          PrintS("\n//** MwalkNextWeightCC: Grad bzgl. diff_weight: ");
+          mpz_out_str( stdout, 10, MwWd);
+          PrintS("\n//** MwalkNextWeightCC: s_nenner: ");
+          mpz_out_str( stdout, 10, s_nenner);
+#endif
           // check for 0 < s <= 1
-          if( (mpz_cmp(s_zaehler,t_null) > 0 &&
-               mpz_cmp(s_nenner, s_zaehler)>=0) ||
-              (mpz_cmp(s_zaehler, t_null) < 0 &&
-               mpz_cmp(s_nenner, s_zaehler)<=0))
+          if((mpz_cmp_si(s_zaehler,0) > 0 && mpz_cmp(s_nenner,s_zaehler)>=0) ||
+             (mpz_cmp_si(s_zaehler,0) < 0 && mpz_cmp(s_nenner,s_zaehler)<=0))
           {
             // make both positive
-            if (mpz_cmp(s_zaehler, t_null) < 0)
+            if(mpz_cmp_si(s_zaehler,0) < 0)
             {
               mpz_neg(s_zaehler, s_zaehler);
@@ -1936 +1715 @@
             cancel(s_zaehler, s_nenner);
 
-            if(mpz_cmp(t_nenner, t_null) != 0)
+            if(mpz_cmp_si(t_nenner,0) != 0)
             {
               mpz_mul(sztn, s_zaehler, t_nenner);
               mpz_mul(sntz, s_nenner, t_zaehler);
-
+#ifdef NEXT_VECTORS_CC
+              PrintS("\n//** MwalkNextWeightCC: sntz: ");
+              mpz_out_str( stdout, 10, sntz);
+              PrintS("\n//** MwalkNextWeightCC: sztn: ");
+              mpz_out_str( stdout, 10, sztn);
+#endif
               if(mpz_cmp(sztn,sntz) < 0)
               {
-                mpz_add(t_nenner, t_null, s_nenner);
-                mpz_add(t_zaehler,t_null, s_zaehler);
+                mpz_add(t_nenner,s_nenner,t_null);
+                mpz_add(t_zaehler,s_zaehler,t_null);
+#ifdef NEXT_VECTORS_CC
+                PrintS("\n//** MwalkNextWeightCC: t_nenner: ");
+                mpz_out_str( stdout, 10, t_nenner);
+                PrintS("\n//** MwalkNextWeightCC: t_zaehler: ");
+                mpz_out_str( stdout, 10, t_zaehler);
+#endif
               }
             }
             else
             {
-              mpz_add(t_nenner, t_null, s_nenner);
-              mpz_add(t_zaehler,t_null, s_zaehler);
+              mpz_add(t_nenner,s_nenner,t_null);
+              mpz_add(t_zaehler,s_zaehler,t_null);
+#ifdef NEXT_VECTORS_CC
+              PrintS("\n//** MwalkNextWeightCC: t_nenner: ");
+              mpz_out_str( stdout, 10, t_nenner);
+              PrintS("\n//** MwalkNextWeightCC: t_zaehler: ");
+              mpz_out_str( stdout, 10, t_zaehler);
+#endif
             }
           }
@@ -1959 +1755 @@
     }
   }
-//Print("\n// Alloc Size = %d \n", nRing*sizeof(mpz_t));
   mpz_t *vec=(mpz_t*)omAlloc(nRing*sizeof(mpz_t));
-
-
-  // there is no 0<t<1 and define the next weight vector that is equal to the current weight vector
+  
+
+  // there is no 0<t<=1, so define the next weight vector to be equal to the current weight vector
   if(mpz_cmp(t_nenner, t_null) == 0)
   {
-    #ifndef SING_NDEBUG
-    Print("\n//MwalkNextWeightCC: t_nenner ist Null!");
-    #endif
+#ifdef NEXT_VECTORS_CC
+    Print("\n//** MwalkNextWeightCC: t_nenner equals zero.\n");
+#endif
     delete diff_weight;
-    diff_weight = ivCopy(curr_weight);//take memory
+    diff_weight = ivCopy(curr_weight);
     goto FINISH;
   }
 
-  // define the target vector as the next weight vector, if t = 1
+  // t = 1, so define the next weight vector to be equal to the target vector
   if(mpz_cmp_si(t_nenner, 1)==0 && mpz_cmp_si(t_zaehler,1)==0)
   {
     delete diff_weight;
-    diff_weight = ivCopy(target_weight); //this takes memory
+    diff_weight = ivCopy(target_weight);
     goto FINISH;
   }
 
-   checkRed = 0;
-
-  SIMPLIFY_GCD:
-
   // simplify the vectors curr_weight and diff_weight (C-int)
-  gcd_tmp = (*curr_weight)[0];
-
-  for (j=1; j<nRing; j++)
-  {
-    gcd_tmp = gcd(gcd_tmp, (*curr_weight)[j]);
-    if(gcd_tmp == 1)
-    {
-      break;
-    }
-  }
+  gcd_tmp = simplify_gcd(curr_weight,diff_weight);
   if(gcd_tmp != 1)
   {
     for (j=0; j<nRing; j++)
     {
-      gcd_tmp = gcd(gcd_tmp, (*diff_weight)[j]);
-      if(gcd_tmp == 1)
-      {
-        break;
-      }
-    }
-  }
-  if(gcd_tmp != 1)
-  {
-    for (j=0; j<nRing; j++)
-    {
-      (*curr_weight)[j] =  (*curr_weight)[j]/gcd_tmp;
-      (*diff_weight)[j] =  (*diff_weight)[j]/gcd_tmp;
-    }
-  }
-  if(checkRed > 0)
-  {
-    for (j=0; j<nRing; j++)
-    {
-      mpz_set_si(vec[j], (*diff_weight)[j]);
-    }
-    goto TEST_OVERFLOW;
+    (*curr_weight)[j] =  (*curr_weight)[j]/gcd_tmp;
+    (*diff_weight)[j] =  (*diff_weight)[j]/gcd_tmp;
+    }
   }
 
 #ifdef  NEXT_VECTORS_CC
-  Print("\n// gcd of the weight vectors (current and target) = %d", gcd_tmp);
-  ivString(curr_weight, "new cw");
-  ivString(diff_weight, "new dw");
-
-  PrintS("\n// t_zaehler: ");  mpz_out_str( stdout, 10, t_zaehler);
-  PrintS(", t_nenner: ");  mpz_out_str( stdout, 10, t_nenner);
-#endif
-
-  //  BOOLEAN isdwpos;
+  Print("\n//** MwalkNextWeightCC: gcd of the weight vectors (current and target) = %d", gcd_tmp);
+  ivString(curr_weight, "new curr_weight");
+  ivString(diff_weight, "new diff_weight");
+  PrintS("\n//** MwalkNextWeightCC: t_zaehler: ");
+  mpz_out_str( stdout, 10, t_zaehler);
+  PrintS(", t_nenner: ");
+  mpz_out_str( stdout, 10, t_nenner);
+#endif
 
   // construct a new weight vector
@@ -2041 +1803 @@
     mpz_set_si(dcw, (*curr_weight)[j]);
     mpz_mul(s_nenner, t_nenner, dcw);
-
-    if( (*diff_weight)[j]>0)
-    {
-      mpz_mul_ui(s_zaehler, t_zaehler, (*diff_weight)[j]);
-    }
-    else
-    {
-      mpz_mul_ui(s_zaehler, t_zaehler, -(*diff_weight)[j]);
-      mpz_neg(s_zaehler, s_zaehler);
-    }
+    mpz_mul_si(s_zaehler, t_zaehler, (*diff_weight)[j]);
     mpz_add(sntz, s_nenner, s_zaehler);
     mpz_init_set(vec[j], sntz);
-
+   
 #ifdef NEXT_VECTORS_CC
-    Print("\n//   j = %d ==> ", j);
+    Print("\n//** MwalkNextWeightCC:  j = %d ==> ", j);
     PrintS("(");
     mpz_out_str( stdout, 10, t_nenner);
@@ -2082 +1835 @@
 
 #ifdef  NEXT_VECTORS_CC
-  PrintS("\n// gcd of elements of the vector: ");
+  PrintS("\n//** MwalkNextWeightCC: gcd of elements of the vector: ");
   mpz_out_str( stdout, 10, ggt);
 #endif
 
-/**********************************************************************
-* construct a new weight vector and check whether vec[j] is overflow, *
-* i.e. vec[j] > 2^31.                                                 *
-* If vec[j] doesn't overflow, define a weight vector. Otherwise,      *
-* report that overflow appears. In the second case, test whether the  *
-* the correctness of the new vector plays an important role           *
-**********************************************************************/
-  kkk=0;
-  for(j=0; j<nRing; j++)
-    {
-    if(mpz_cmp(vec[j], sing_int_half) >= 0)
-      {
-      goto REDUCTION;
-      }
-    }
-  checkRed = 1;
+
+  // check whether vec[j]>2147483647, reduce it
+
   for (j=0; j<nRing; j++)
-    {
-      (*diff_weight)[j] = mpz_get_si(vec[j]);
-    }
-  goto SIMPLIFY_GCD;
-
-  REDUCTION:
+  {
+    (*diff_weight)[j] = mpz_get_si(vec[j]);
+  }
+  while(MivAbsMax(diff_weight) > 100000000)
+  {
+    for (j=0; j<nRing; j++)
+    {
+      if(mpz_cmp_si(ggt,1)==0)
+      {
+        (*diff_weight1)[j] = floor(0.001*(*diff_weight)[j] + 0.5);
+#ifdef  NEXT_VECTORS_CC
+        Print("\n//** MwalkNextWeightCC: vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
+#endif
+      }
+      else
+      {
+        mpz_divexact(vec[j], vec[j], ggt);
+        (*diff_weight1)[j] = floor(0.001*(*diff_weight)[j] + 0.5);
+#ifdef  NEXT_VECTORS_CC
+        Print("\n//** MwalkNextWeightCC: vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
+#endif
+      }
+    }
+
+    if(test_w_in_ConeCC(G,diff_weight1) != 0)
+    {
+#ifdef  NEXT_VECTORS_CC
+      Print("\n//** MwalkNextWeightCC: changed weight vector in correct cone.\n");
+#endif
+      for (j=0; j<nRing; j++)
+      {
+        (*diff_weight)[j] = (*diff_weight1)[j];
+      }
+
+      // simplify the vectors curr_weight and diff_weight (C-int)
+      gcd_tmp = simplify_gcd(curr_weight,diff_weight);
+      if(gcd_tmp != 1)
+      {
+        for (j=0; j<nRing; j++)
+        {
+          (*curr_weight)[j] =  (*curr_weight)[j]/gcd_tmp;
+          (*diff_weight)[j] =  (*diff_weight)[j]/gcd_tmp;
+          mpz_set_si(vec[j],(*diff_weight)[j]);
+        }
+      }
+    }
+    else
+    {
+#ifdef  NEXT_VECTORS_CC
+      Print("\n//** MwalkNextWeightCC: changed weight vector not in correct cone.\n");
+#endif
+
+      for (j=0; j<nRing; j++)
+      {
+        (*diff_weight)[j] = mpz_get_si(vec[j]);
+      }
+      break;
+    }
+  }
+
   for (j=0; j<nRing; j++)
   {
-    (*diff_weight)[j] = mpz_get_si(vec[j]);
-  }
-  while(MivAbsMax(diff_weight) >= 5)
-  {
-    for (j=0; j<nRing; j++)
-    {
-      if(mpz_cmp_si(ggt,1)==0)
-      {
-        (*diff_weight1)[j] = floor(0.1*(*diff_weight)[j] + 0.5);
-        // Print("\n//  vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
-      }
-      else
-      {
-        mpz_divexact(vec[j], vec[j], ggt);
-        (*diff_weight1)[j] = floor(0.1*(*diff_weight)[j] + 0.5);
-        // Print("\n//  vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
-      }
-/*
-      if((*diff_weight1)[j] == 0)
-      {
-        kkk = kkk + 1;
-      }
-*/
-    }
-
-
-/*
-    if(kkk > nRing - 1)
-    {
-      // diff_weight was reduced to zero
-      // Print("\n // MwalkNextWeightCC: geaenderter Vector gleich Null! \n");
-      goto TEST_OVERFLOW;
-    }
-*/
-
-    if(test_w_in_ConeCC(G,diff_weight1) != 0)
-    {
-      Print("\n// MwalkNextWeightCC: geaenderter vector liegt in Groebnerkegel! \n");
-      for (j=0; j<nRing; j++)
-      {
-        (*diff_weight)[j] = (*diff_weight1)[j];
-      }
-      if(MivAbsMax(diff_weight) < 5)
-      {
-        checkRed = 1;
-        goto SIMPLIFY_GCD;
-      }
-    }
-    else
-    {
-      // Print("\n// MwalkNextWeightCC: geaenderter vector liegt nicht in Groebnerkegel! \n");
-      break;
-    }
-  }
-
- TEST_OVERFLOW:
-
-  for (j=0; j<nRing; j++)
-  {
-    if(mpz_cmp(vec[j], sing_int)>=0)
+    if((mpz_cmp(vec[j], sing_int)>=0) && ((*diff_weight)[j] > 2147483647))
     {
       if(Overflow_Error == FALSE)
       {
         Overflow_Error = TRUE;
-        PrintS("\n// ** OVERFLOW in \"MwalkNextWeightCC\": ");
+        PrintS("\n//** MwalkNextWeightCC: OVERFLOW: ");
         mpz_out_str( stdout, 10, vec[j]);
-        PrintS(" is greater than 2147483647 (max. integer representation)\n");
-        //Print("//  So vector[%d] := %d is wrong!!\n",j+1, vec[j]);// vec[j] is mpz_t
+        PrintS(" is greater than 2147483647 (max. integer representation)");
+        Print("\n//  So vector[%d] := %d may be wrong.\n",j+1, vec[j]);
       }
     }
@@ -2184 +1919 @@
 
  FINISH:
-   delete diff_weight1;
-   mpz_clear(t_zaehler);
-   mpz_clear(t_nenner);
-   mpz_clear(s_zaehler);
-   mpz_clear(s_nenner);
-   mpz_clear(sntz);
-   mpz_clear(sztn);
-   mpz_clear(temp);
-   mpz_clear(MwWd);
-   mpz_clear(deg_w0_p1);
-   mpz_clear(deg_d0_p1);
-   mpz_clear(ggt);
-   omFree(vec);
-   mpz_clear(sing_int_half);
-   mpz_clear(sing_int);
-   mpz_clear(dcw);
-   mpz_clear(t_null);
-
-
-
+  delete diff_weight1;
+  mpz_clear(t_zaehler);
+  mpz_clear(t_nenner);
+  mpz_clear(s_zaehler);
+  mpz_clear(s_nenner);
+  mpz_clear(sntz);
+  mpz_clear(sztn);
+  mpz_clear(temp);
+  mpz_clear(MwWd);
+  mpz_clear(deg_w0_p1);
+  mpz_clear(deg_d0_p1);
+  mpz_clear(ggt);
+  omFree(vec);
+  mpz_clear(sing_int);
+  mpz_clear(dcw);
+  mpz_clear(t_null);
+ 
   if(Overflow_Error == FALSE)
   {
     Overflow_Error = nError;
   }
- rComplete(currRing);
-  for(kkk=0; kkk<IDELEMS(G);kkk++)
-  {
-    poly p=G->m[kkk];
+  rComplete(currRing);
+  for(j=0; j<IDELEMS(G); j++)
+  {
+    poly p=G->m[j];
     while(p!=NULL)
     {
@@ -2251 +1983 @@
 }
 
-/**************************************************************
- * define and execute a new ring which order is (a(vb),a(va),lp,C)  *
- * ************************************************************/
-static void VMrHomogeneous(intvec* va, intvec* vb)
+/*****************************************************
+ * define and execute a new ring with ordering (M,C) *
+ *****************************************************/
+static ring VMatrDefault(intvec* va)
 {
 
@@ -2272 +2004 @@
   r->cf  = currRing->cf;
   r->N   = currRing->N;
+
   int nb = 4;
-
 
   //names
@@ -2284 +2016 @@
   }
 
+  /*weights: entries for 3 blocks: NULL Made:???*/
+  r->wvhdl = (int **)omAlloc0(nb * sizeof(int_ptr));
+  r->wvhdl[0] = (int*) omAlloc(nv*nv*sizeof(int));
+  r->wvhdl[1] =NULL; // (int*) omAlloc(nv*sizeof(int));
+  r->wvhdl[2]=NULL;
+  r->wvhdl[3]=NULL;
+  for(i=0; i<nv*nv; i++)
+    r->wvhdl[0][i] = (*va)[i];
+
+  /* order: a,lp,C,0 */
+  r->order = (int *) omAlloc(nb * sizeof(int *));
+  r->block0 = (int *)omAlloc0(nb * sizeof(int *));
+  r->block1 = (int *)omAlloc0(nb * sizeof(int *));
+
+  // ringorder a for the first block: var 1..nv
+  r->order[0]  = ringorder_M;
+  r->block0[0] = 1;
+  r->block1[0] = nv;
+
+  // ringorder C for the second block
+  r->order[1]  = ringorder_C;
+  r->block0[1] = 1;
+  r->block1[1] = nv;
+
+
+// ringorder C for the third block: var 1..nv
+  r->order[2]  = ringorder_C;
+  r->block0[2] = 1;
+  r->block1[2] = nv;
+
+
+  // the last block: everything is 0
+  r->order[3]  = 0;
+
+  // polynomial ring
+  r->OrdSgn    = 1;
+
+  // complete ring intializations
+
+  rComplete(r);
+
+  //rChangeCurrRing(r);
+  return r;
+}
+
+/***********************************************************
+ * define and execute a new ring with ordering (a(vb),M,C) *
+ ***********************************************************/
+static ring VMatrRefine(intvec* va, intvec* vb)
+{
+
+  if ((currRing->ppNoether)!=NULL)
+  {
+    pDelete(&(currRing->ppNoether));
+  }
+  if (((sLastPrinted.rtyp>BEGIN_RING) && (sLastPrinted.rtyp<END_RING)) ||
+      ((sLastPrinted.rtyp==LIST_CMD)&&(lRingDependend((lists)sLastPrinted.data))))
+  {
+    sLastPrinted.CleanUp();
+  }
+
+  ring r = (ring) omAlloc0Bin(sip_sring_bin);
+  int i, nv = currRing->N;
+  int nvs = nv*nv;
+  r->cf  = currRing->cf;
+  r->N   = currRing->N;
+
+  int nb = 4;
+
+  //names
+  char* Q; // In order to avoid the corrupted memory, do not change.
+  r->names = (char **) omAlloc0(nv * sizeof(char_ptr));
+  for(i=0; i<nv; i++)
+  {
+    Q = currRing->names[i];
+    r->names[i]  = omStrDup(Q);
+  }
+
+  /*weights: entries for 3 blocks: NULL Made:???*/
+  r->wvhdl = (int **)omAlloc0(nb * sizeof(int_ptr));
+  r->wvhdl[0] = (int*) omAlloc(nv*sizeof(int));
+  r->wvhdl[1] = (int*) omAlloc(nvs*sizeof(int));
+  r->wvhdl[2]=NULL;
+  r->wvhdl[3]=NULL;
+  for(i=0; i<nvs; i++)
+  {
+    r->wvhdl[1][i] = (*va)[i];
+  }
+  for(i=0; i<nv; i++)
+  {
+    r->wvhdl[0][i] = (*vb)[i];
+  }
+  /* order: a,lp,C,0 */
+  r->order = (int *) omAlloc(nb * sizeof(int *));
+  r->block0 = (int *)omAlloc0(nb * sizeof(int *));
+  r->block1 = (int *)omAlloc0(nb * sizeof(int *));
+
+  // ringorder a for the first block: var 1..nv
+  r->order[0]  = ringorder_a;
+  r->block0[0] = 1;
+  r->block1[0] = nv;
+
+  // ringorder M for the second block: var 1..nv
+  r->order[1]  = ringorder_M;
+  r->block0[1] = 1;
+  r->block1[1] = nv;
+
+  // ringorder C for the third block: var 1..nv
+  r->order[2]  = ringorder_C;
+  r->block0[2] = 1;
+  r->block1[2] = nv;
+
+
+  // the last block: everything is 0
+  r->order[3]  = 0;
+
+  // polynomial ring
+  r->OrdSgn    = 1;
+
+  // complete ring intializations
+
+  rComplete(r);
+
+  //rChangeCurrRing(r);
+  return r;
+}
+
+/****************************************************************
+ * define and execute a new ring with ordering (a(va),Wp(vb),C) *
+ * **************************************************************/
+
+static ring VMrRefine(intvec* va, intvec* vb)
+{
+
+  if ((currRing->ppNoether)!=NULL)
+  {
+    pDelete(&(currRing->ppNoether));
+  }
+  if (((sLastPrinted.rtyp>BEGIN_RING) && (sLastPrinted.rtyp<END_RING)) ||
+      ((sLastPrinted.rtyp==LIST_CMD)&&(lRingDependend((lists)sLastPrinted.data))))
+  {
+    sLastPrinted.CleanUp();
+  }
+
+  ring r = (ring) omAlloc0Bin(sip_sring_bin);
+  int i, nv = currRing->N;
+
+  r->cf  = currRing->cf;
+  r->N   = currRing->N;
+  //int nb = nBlocks(currRing)  + 1;
+  int nb = 4;
+
+  //names
+  char* Q; // In order to avoid the corrupted memory, do not change.
+  r->names = (char **) omAlloc0(nv * sizeof(char_ptr));
+  for(i=0; i<nv; i++)
+  {
+    Q = currRing->names[i];
+    r->names[i]  = omStrDup(Q);
+  }
+
   //weights: entries for 3 blocks: NULL Made:???
   r->wvhdl = (int **)omAlloc0(nb * sizeof(int_ptr));
   r->wvhdl[0] = (int*) omAlloc(nv*sizeof(int));
-  r->wvhdl[1] = (int*) omAlloc((nv-1)*sizeof(int));
-
-  for(i=0; i<nv-1; i++)
-  {
+  r->wvhdl[1] = (int*) omAlloc(nv*sizeof(int));
+
+  for(i=0; i<nv; i++)
+  {
+    r->wvhdl[0][i] = (*va)[i];
     r->wvhdl[1][i] = (*vb)[i];
-    r->wvhdl[0][i] = (*va)[i];
-  }
-  r->wvhdl[0][nv] = (*va)[nv];
+  }
+  r->wvhdl[2]=NULL;
+  r->wvhdl[3]=NULL;
 
   // order: (1..1),a,lp,C
@@ -2306 +2200 @@
   r->block1[0] = nv;
 
- // ringorder a for the second block: var 2..nv
-  r->order[1]  = ringorder_a;
-  r->block0[1] = 2;
+ // ringorder Wp for the second block: var 1..nv
+  r->order[1]  = ringorder_Wp;
+  r->block0[1] = 1;
   r->block1[1] = nv;
 
-  // ringorder lp for the third block: var 2..nv
-  r->order[2]  = ringorder_lp;
-  r->block0[2] = 2;
+  // ringorder lp for the third block: var 1..nv
+  r->order[2]  = ringorder_C;
+  r->block0[2] = 1;
   r->block1[2] = nv;
 
@@ -2320 +2214 @@
   // especially, by ring syz_ring=rCurrRingAssure_SyzComp();
   // therefore, nb  must be (nBlocks(currRing)  + 1)
-  r->order[3]  = ringorder_C;
+  r->order[3]  = 0;
 
   // polynomial ring
@@ -2326 +2220 @@
 
   // complete ring intializations
-
+  
   rComplete(r);
 
-  rChangeCurrRing(r);
-}
-
+  //rChangeCurrRing(r);
+  return r;
+}
 
 /**************************************************************
  * define and execute a new ring which order is (a(va),lp,C)  *
  * ************************************************************/
-static void VMrDefault(intvec* va)
+//static void VMrDefault(intvec* va)
+static ring VMrDefault(intvec* va)
 {
 
@@ -2400 +2295 @@
 
   // complete ring intializations
-
+  
   rComplete(r);
 
-  rChangeCurrRing(r);
+  //rChangeCurrRing(r);
+  return r;
 }
 
@@ -2463 +2359 @@
 
   /* complete ring intializations */
-
+  
   rComplete(r);
 
@@ -2592 +2488 @@
   r->OrdSgn    = 1;
 
-
-//   if (rParameter(currRing)!=NULL)
-//   {
-//     r->cf->extRing->qideal->m[0]=p_Copy(currRing->cf->extRing->qideal->m[0], currRing->cf->extRing);
-//     int l=rPar(currRing);
-//     r->cf->extRing->names=(char **)omAlloc(l*sizeof(char_ptr));
-//
-//     for(i=l-1;i>=0;i--)
-//     {
-//       rParameter(r)[i]=omStrDup(rParameter(currRing)[i]);
-//     }
-//   }
-
   // complete ring intializations
-
+  
   rComplete(r);
 
@@ -2619 +2502 @@
 }
 
-//unused
-/**************************************************************
- * check wheather one or more components of a vector are zero *
- **************************************************************/
-//#if 0
-static int isNolVector(intvec* hilb)
-{
-  int i;
-  for(i=hilb->length()-1; i>=0; i--)
-  {
-    if((* hilb)[i]==0)
-    {
-      return 1;
-    }
-  }
-  return 0;
-}
-//#endif
+
 
 /******************************  Februar 2002  ****************************
@@ -2925 +2791 @@
   for(i=IDELEMS(G)-1; i>=0; i--)
   {
-#if 0
-    if(pLength(G->m[i])>2)
-    {
-      return 1;
-    }
-#else
     if((G->m[i]!=NULL) /* len >=0 */
        && (G->m[i]->next!=NULL) /* len >=1 */
@@ -2938 +2798 @@
        )
     {
-    return 1;
-    }
-#endif
+      return 1;
+    }
   }
   return 0;
@@ -3013 +2872 @@
   for(i=nG-1; i>=0; i--)
   {
-#if 0
-    poly t;
-    if((t=pSub(pCopy(H0->m[i]), pCopy(H1->m[i]))) != NULL)
-    {
-      pDelete(&t);
+    if(!pEqualPolys(H0->m[i],H1->m[i]))
+    {
       return 0;
     }
-    pDelete(&t);
-#else
-    if(!pEqualPolys(H0->m[i],H1->m[i]))
-    {
-      return 0;
-    }
-#endif
   }
   return 1;
@@ -3056 +2905 @@
   return result;
 }
-#endif
-
-//unused
+
+
+
 /************************************************************************
  * perturb the weight vector iva w.r.t. the ideal G.                    *
@@ -3066 +2915 @@
  *  d := (2*maxdeg*maxdeg + (nV+1)*maxdeg)*m;                           *
  ************************************************************************/
-#if 0
 static intvec* TranPertVector(ideal G, intvec* iva)
 {
@@ -3124 +2972 @@
 #ifdef INVEPS_SMALL_IN_TRAN
   if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
-  {
+  { 
     mpz_cdiv_q_ui(ndeg, ndeg, nV);
   }
@@ -3207 +3055 @@
   return repr_vector;
 }
-#endif
-
-//unused
-#if 0
+
+
+
+
 static intvec* TranPertVector_lp(ideal G)
 {
@@ -3303 +3151 @@
   return repr_vector;
 }
-#endif
-
-//unused
-#if 0
+
+
 static intvec* RepresentationMatrix_Dp(ideal G, intvec* M)
 {
@@ -3404 +3250 @@
  *****************************************************************************/
 
-//unused
-#if 0
-static int testnegintvec(intvec* v)
-{
-  int n = v->length();
-  int i;
-  for(i=0; i<n; i++)
-  {
-    if((*v)[i]<0)
-    {
-      return(1);
-    }
-  }
-  return(0);
-}
-#endif
-
-// npwinc = 0, if curr_weight doesn't stay in the correct Groebner cone
 static ideal Rec_LastGB(ideal G, intvec* curr_weight,
                         intvec* orig_target_weight, int tp_deg, int npwinc)
@@ -3787 +3615 @@
     nstep ++;
     to = clock();
-    /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
+    // 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) */
+    // define a new ring that its ordering is "(a(curr_weight),lp)
     if (rParameter(currRing) != NULL)
     {
@@ -3854 +3674 @@
     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)
@@ -3922 +3737 @@
   TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
 
-  Print("\n// pSetm_Error = (%d)", ErrorCheck());
+  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
   //Print("\n// Overflow_Error? (%d)", nOverflow_Error);
   Print("\n// Awalk2 took %d steps!!", nstep);
@@ -3956 +3771 @@
 {
   int i, weight_norm;
+  //int randCount=0;
   int nV = currRing->N;
   intvec* next_weight2;
   intvec* next_weight22 = new intvec(nV);
+  intvec* result = new intvec(nV);
+
+  //compute a perturbed next weight vector "next_weight1"
+  intvec* next_weight1 = MkInterRedNextWeight(MPertVectors(G,MivMatrixOrderRefine(curr_weight,target_weight),pert_deg),target_weight,G);
+  //compute a random next weight vector "next_weight2"
+  while(1)
+  {
+    weight_norm = 0;
+    while(weight_norm == 0)
+    {
+      for(i=0; i<nV; i++)
+      {
+        (*next_weight22)[i] = rand() % 60000 - 30000;
+        weight_norm = weight_norm + (*next_weight22)[i]*(*next_weight22)[i];
+      }
+      weight_norm = 1 + floor(sqrt(weight_norm));
+    }
+    for(i=0; i<nV; i++)
+    {
+      if((*next_weight22)[i] < 0)
+      {
+        (*next_weight22)[i] = 1 + (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
+      }
+      else
+      {
+        (*next_weight22)[i] = (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
+      }
+    }
+    if(test_w_in_ConeCC(G, next_weight22) == 1)
+    {
+      next_weight2 = MkInterRedNextWeight(next_weight22,target_weight,G);
+      delete next_weight22;
+      break;
+    }
+  }
+  // compute "usual" next weight vector
   intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
-  if(MivComp(next_weight, target_weight) == 1)
-  {
-    return(next_weight);
-  }
-  else
-  {
-    //compute a perturbed next weight vector "next_weight1"
-    intvec* next_weight1 = MkInterRedNextWeight(MPertVectors(G, MivMatrixOrder(curr_weight), pert_deg), target_weight, G);
-    //Print("\n // size of next_weight1 = %d", sizeof((*next_weight1)));
-
-    //compute a random next weight vector "next_weight2"
-    while(1)
-    {
-      weight_norm = 0;
-      while(weight_norm == 0)
-      {
-        for(i=0; i<nV; i++)
-        {
-          //Print("\n//  next_weight[%d]  = %d", i, (*next_weight)[i]);
-          (*next_weight22)[i] = rand() % 60000 - 30000;
-          weight_norm = weight_norm + (*next_weight22)[i]*(*next_weight22)[i];
-        }
-        weight_norm = 1 + floor(sqrt(weight_norm));
-      }
-
-      for(i=nV-1; i>=0; i--)
-      {
-        if((*next_weight22)[i] < 0)
-        {
-          (*next_weight22)[i] = 1 + (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
-        }
-        else
-        {
-          (*next_weight22)[i] = (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
-        }
-      //Print("\n//  next_weight22[%d]  = %d", i, (*next_weight22)[i]);
-      }
-
-      if(test_w_in_ConeCC(G, next_weight22) == 1)
-      {
-        //Print("\n//MWalkRandomNextWeight: next_weight2 im Kegel\n");
-        next_weight2 = MkInterRedNextWeight(next_weight22, target_weight, G);
-        delete next_weight22;
-        break;
-      }
-    }
-    intvec* result = new intvec(nV);
-    ideal G_test = MwalkInitialForm(G, next_weight);
+  ideal G_test = MwalkInitialForm(G, next_weight);
+  ideal G_test2 = MwalkInitialForm(G, next_weight2);
+
+  // compare next weights
+  if(Overflow_Error == FALSE)
+  {
     ideal G_test1 = MwalkInitialForm(G, next_weight1);
-    ideal G_test2 = MwalkInitialForm(G, next_weight2);
-
-    // compare next_weights
     if(IDELEMS(G_test1) < IDELEMS(G_test))
     {
-      if(IDELEMS(G_test2) <= IDELEMS(G_test1)) // |G_test2| <= |G_test1| < |G_test|
-      {
+      if(IDELEMS(G_test2) < IDELEMS(G_test1))
+      {
+        // |G_test2| < |G_test1| < |G_test|
         for(i=0; i<nV; i++)
         {
@@ -4021 +3829 @@
         }
       }
-      else // |G_test1| < |G_test|, |G_test1| < |G_test2|
-      {
+      else
+      {
+        // |G_test1| < |G_test|, |G_test1| <= |G_test2|
         for(i=0; i<nV; i++)
         {
           (*result)[i] = (*next_weight1)[i];
         }
-      }
+      }    
     }
     else
     {
-      if(IDELEMS(G_test2) <= IDELEMS(G_test)) // |G_test2| <= |G_test| <= |G_test1|
+      if(IDELEMS(G_test2) < IDELEMS(G_test)) // |G_test2| < |G_test| <= |G_test1|
       {
         for(i=0; i<nV; i++)
@@ -4038 +3847 @@
         }
       }
-      else // |G_test| <= |G_test1|, |G_test| < |G_test2|
-      {
+      else
+      {
+        // |G_test| < |G_test1|, |G_test| <= |G_test2|
         for(i=0; i<nV; i++)
         {
@@ -4046 +3856 @@
       }
     }
+    idDelete(&G_test1);
+  }
+  else
+  {
+    Overflow_Error = FALSE;
+    if(IDELEMS(G_test2) < IDELEMS(G_test))
+    {
+      for(i=1; i<nV; i++)
+      {
+        (*result)[i] = (*next_weight2)[i];
+      }
+    }
+    else
+    {
+      for(i=0; i<nV; i++)
+      {
+        (*result)[i] = (*next_weight)[i];
+      }
+    }
+  }
+  idDelete(&G_test);
+  idDelete(&G_test2);
+  if(test_w_in_ConeCC(G, result) == 1)
+  {
+    delete next_weight2;
     delete next_weight;
     delete next_weight1;
-    idDelete(&G_test);
-    idDelete(&G_test1);
-    idDelete(&G_test2);
-    if(test_w_in_ConeCC(G, result) == 1)
-    {
-      delete next_weight2;
-      return result;
-    }
-    else
-    {
-      delete result;
-      return next_weight2;
-    }
+    return result;
+  }
+  else
+  {
+    delete result;
+    delete next_weight2;
+    delete next_weight1;
+    return next_weight;
   }
 }
@@ -4066 +3896 @@
 
 /***************************************************************************
- * The procedur REC_GB_Mwalk computes a GB for <G> w.r.t. the weight order *
+ * The procedure REC_GB_Mwalk computes a GB for <G> w.r.t. the weight order*
  * otw, where G is a reduced GB w.r.t. the weight order cw.                *
  * The new procedur Mwalk calls REC_GB.                                    *
@@ -4117 +3947 @@
     if(test_G_GB_walk(H0_tmp,H1)==1)
     {
-      //Print("\n//REC_GB_Mwalk: input in %d-th recursive is a GB!\n",tp_deg);
+      Print("\n//REC_GB_Mwalk: input in %d-th recursive is a GB!\n",tp_deg);
       idDelete(&H0_tmp);
       idDelete(&H1);
@@ -4151 +3981 @@
       goto NEXT_STEP;
     }
-    //Print("\n//REC_GB_Mwalk: Entering the %d-th step in the %d-th recursive:\n",nwalk,tp_deg);
+    Print("\n//REC_GB_Mwalk: Entering the %d-th step in the %d-th recursive:\n",nwalk,tp_deg);
     to = clock();
     // compute an initial form ideal of <G> w.r.t. "curr_vector"
@@ -4226 +4056 @@
     // compute a next weight vector
     intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
-
+  
 
     xtnw = xtnw + clock() - to;
@@ -4236 +4066 @@
     if(Overflow_Error == TRUE)
     {
-      //PrintS("\n//REC_GB_Mwalk: The computed vector does NOT stay in the correct cone!!\n");
+      PrintS("\n//REC_GB_Mwalk: The computed vector does NOT stay in the correct cone!!\n");
       nnwinC = 0;
       if(tp_deg == nV)
@@ -4351 +4181 @@
 }
 
-
-// THE NEW GROEBNER WALK ALGORITHM
-// Groebnerwalk with a recursive "second" alternative GW, called REC_GB_Mwalk that only computes the last reduced GB
-ideal Mwalk(ideal Go, intvec* curr_weight, intvec* target_weight)
-{
+/*******************************
+ * THE GROEBNER WALK ALGORITHM *
+ *******************************/
+ideal Mwalk(ideal Go, intvec* orig_M, intvec* target_M, ring baseRing)
+{
+  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;
-  //Print("// pSetm_Error = (%d)", ErrorCheck());
-
+#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;
-  nstep=0;
-  int i;
-  int nV = currRing->N;
-  int nwalk=0;
-  int endwalks=0;
-
-  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
-  //ideal G1;
-  //ring endRing;
-  ring newRing, oldRing;
-  intvec* ivNull = new intvec(nV);
-  intvec* exivlp = Mivlp(nV);
-#ifndef BUCHBERGER_ALG
-  intvec* hilb_func;
-#endif
-  intvec* tmp_weight = new intvec(nV);
-  for(i=nV-1; i>=0; i--)
-    (*tmp_weight)[i] = (*curr_weight)[i];
-
-   // 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();
-  // the monomial ordering of this current ring would be "dp"
-  G = MstdCC(Go);
-  tostd = clock()-to;
-
-  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);
-    tif = tif + clock()-to;
-    oldRing = currRing;
-
-    if(endwalks == 1)
-    {
-      /* compute a reduced Groebner basis of Gomega w.r.t. >>_cw by
-         the recursive changed perturbation walk alg. */
-      tim = clock();
-      /*
-        Print("\n// **** Grï¿œbnerwalk took %d steps and ", nwalk);
-        PrintS("\n// **** call the rec. Pert. Walk to compute a red GB of:");
-        idElements(Gomega, "G_omega");
-      */
-
-      if(MivSame(exivlp, target_weight)==1)
-        M = REC_GB_Mwalk(idCopy(Gomega), tmp_weight, curr_weight, 2,1);
-      else
-        goto NORMAL_GW;
-      /*
-        Print("\n//  time for the last std(Gw)  = %.2f sec",
-        ((double) (clock()-tim)/1000000));
-        PrintS("\n// ***************************************************\n");
-      */
-#ifdef CHECK_IDEAL_MWALK
-      idElements(Gomega, "G_omega");
-      headidString(Gomega, "Gw");
-      idElements(M, "M");
-      //headidString(M, "M");
-#endif
-      to = clock();
-      F = MLifttwoIdeal(Gomega, M, G);
-      xtlift = xtlift + clock() - to;
-
-      idDelete(&Gomega);
-      idDelete(&M);
-      idDelete(&G);
-
-      oldRing = currRing;
-
-      /* create a new ring newRing */
-       if (rParameter(currRing) != NULL)
-       {
-         DefRingPar(curr_weight);
-       }
-       else
-       {
-         VMrDefault(curr_weight);
-       }
-      newRing = currRing;
-      F1 = idrMoveR(F, oldRing,currRing);
-    }
-    else
-    {
-    NORMAL_GW:
-#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
-
-      // define a new ring that its ordering is "(a(curr_weight),lp)
-      if (rParameter(currRing) != NULL)
-      {
-        DefRingPar(curr_weight);
-      }
-      else
-      {
-        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);
-    if(endwalks != 1)
-    {
-      tred = tred + clock() - to;
-    }
-    else
-    {
-      xtred = xtred + clock() - to;
-    }
-    idDelete(&F1);
-    if(endwalks == 1)
-    {
-      break;
-    }
-  NEXT_VECTOR:
-    to = clock();
-    // compute a next weight vector
-    intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
-    tnw = tnw + clock() - to;
-#ifdef PRINT_VECTORS
-    MivString(curr_weight, target_weight, next_weight);
-#endif
-
-    //if(test_w_in_ConeCC(G, next_weight) != 1)
-    if(Overflow_Error == TRUE)
-    {
-      newRing = currRing;
-      PrintS("\n// ** The computed vector does NOT stay in Cone!!\n");
-
-      if (rParameter(currRing) != NULL)
-      {
-        DefRingPar(target_weight);
-      }
-      else
-      {
-        VMrDefault(target_weight);
-      }
-      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)
-    {
-      endwalks = 1;
-    }
-    for(i=nV-1; i>=0; i--)
-    {
-      (*tmp_weight)[i] = (*curr_weight)[i];
-      (*curr_weight)[i] = (*next_weight)[i];
-    }
-    delete next_weight;
-  }
-  rChangeCurrRing(XXRing);
-  G = idrMoveR(G, newRing,currRing);
-
-  delete tmp_weight;
-  delete ivNull;
-  delete exivlp;
-
-#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
-  return(G);
-}
-
-// 07.11.2012
-// THE RANDOM WALK ALGORITHM
-ideal Mrwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int pert_deg)
-{
-  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;
-  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 = currRing->N;
-
-  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
-  //ideal G1;
-  //ring endRing;
-  ring newRing, oldRing;
+  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=nV-1; i>=0; i--)
-  {
-    (*tmp_weight)[i] = (*curr_weight)[i];
+  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
@@ -4629 +4229 @@
   (*last_omega)[0] = 10000;
 #endif
-  ring XXRing = currRing;
-
+  rComplete(currRing);
+#ifdef CHECK_IDEAL_MWALK
+    idString(Go,"Go");
+#endif
+#ifdef TIME_TEST
   to = clock();
-  G = MstdCC(Go);
+#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;
-
-  //if(currRing->order[0] == ringorder_a)
-  //  goto NEXT_VECTOR;
-nwalk = 0;
+#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"
-    tif = tif + clock()-to;
-    oldRing = currRing;
+    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,"G_omega");
-#endif
-    if(endwalks == 1)
-    {
-      // compute a reduced Groebner basis of Gomega w.r.t. >>_cw by the recursive changed perturbation walk alg.
-      tim = clock();
-      Print("\n//Mrwalk: Groebnerwalk took %d steps.\n", nwalk);
-      //PrintS("\n//Mrwalk: call the rec. Pert. Walk to compute a red GB of:");
-      //idString(Gomega, "G_omega");
-      M = REC_GB_Mwalk(idCopy(Gomega), tmp_weight, curr_weight,pert_deg,1);
-      Print("\n//Mrwalk: time for the last std(Gw)  = %.2f sec\n",((double) (clock()-tim)/1000000));
-
+    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
-      idString(Gomega, "G_omega");
-      idString(M, "M");
-#endif
-      to = clock();
-      F = MLifttwoIdeal(Gomega, M, G);
-      xtlift = xtlift + clock() - to;
-
+    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 || test_w_in_ConeCC(G, target_weight) == 1 || MivComp(target_weight,curr_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);
-      idDelete(&G);
-
-      oldRing = currRing;
-      VMrDefault(curr_weight); //define a new ring with ordering "(a(curr_weight),lp)
-
-       /*if (rParameter(currRing) != NULL)
-       {
-         DefRingPar(curr_weight);
-       }
-       else
-       {
-         VMrDefault(curr_weight);
-       }*/
-      newRing = currRing;
-      F1 = idrMoveR(F, oldRing,currRing);
-    }
-    else
-    {
-#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 (rParameter(currRing) != NULL)
-      {
-        DefRingPar(curr_weight);
-      }
-      else
-      {
-        VMrDefault(curr_weight);
-      }*/
-
-      VMrDefault(curr_weight); //define a new ring with ordering "(a(curr_weight),lp)
-      newRing = currRing;
-      Gomega1 = idrMoveR(Gomega, oldRing,currRing);
-#ifdef CHECK_IDEAL_MWALK
-      idString(Gomega1, "G_omega1");
-#endif
-      // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
-      to = clock();
-#ifndef  BUCHBERGER_ALG
-      M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
-      delete hilb_func;
-#else
-      //M = MstdhomCC(Gomega1);
-      //M = MstdCC(Gomega1);
-      //M = kStd(Gomega1, NULL, testHomog,NULL, NULL,0,0,curr_weight);
-      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
-#endif
-      tstd = tstd + clock() - to;
-#ifdef CHECK_IDEAL_MWALK
-      idString(M, "M");
-#endif
-      //change the ring to oldRing
-      rChangeCurrRing(oldRing);
-      M1 =  idrMoveR(M, newRing,currRing);
-#ifdef CHECK_IDEAL_MWALK
-      idString(M1, "M1");
-#endif
-      Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
-
-      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
+      Gomega2 = idrMoveR(Gomega1, newRing,currRing);
+      idDelete(&Gomega1);
       F = MLifttwoIdeal(Gomega2, M1, G);
 #ifdef CHECK_IDEAL_MWALK
-      idString(F, "F");
-#endif
-      tlift = tlift + clock() - to;
-
+      idString(F,"F");
+#endif
+      idDelete(&Gomega2);
       idDelete(&M1);
-      idDelete(&Gomega2);
-      idDelete(&G);
-
       rChangeCurrRing(newRing); // change the ring to newRing
-      F1 = idrMoveR(F,oldRing,currRing);
-    }
-
-    to = clock();
-    G = kInterRedCC(F1, NULL); //reduce the Groebner basis <G> w.r.t. new ring
-#ifdef CHECK_IDEAL_MWALK
-    idString(G, "G");
-#endif
-    idDelete(&F1);
-    if(endwalks == 1)
-    {
-      xtred = xtred + clock() - to;
-      break;
-    }
-    else
-    {
+      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;
-    }
-
-  //NEXT_VECTOR:
-    to = clock();
-    //intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
-   intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, pert_deg);
-
-  tnw = tnw + clock() - to;
-//#ifdef PRINT_VECTORS
-  MivString(curr_weight, target_weight, next_weight);
-//#endif
-    if(Overflow_Error == TRUE)
-    {
-      newRing = currRing;
-      PrintS("\n//Mrwalk: The computed vector does NOT stay in Cone!!\n");
-
-      if (rParameter(currRing) != NULL)
-      {
-        DefRingPar(target_weight);
-      }
-      else
-      {
-        VMrDefault(target_weight);  //define a new ring with ordering "(a(curr_weight),lp)
-      }
-      F1 = idrMoveR(G, newRing,currRing);
-      G = MstdCC(F1);
-      idDelete(&F1);
-
-      newRing = currRing;
-      break;
-    }
-
-    if(MivComp(next_weight, ivNull) == 1)
-    {
-      newRing = currRing;
+#endif
+      idSkipZeroes(G);
       delete next_weight;
       break;
-    }
-    if(MivComp(next_weight, target_weight) == 1)
-    {
-      endwalks = 1;
-    }
+#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--)
     {
@@ -4819 +4435 @@
   }
   rChangeCurrRing(XXRing);
-  G = idrMoveR(G, newRing,currRing);
-
+  ideal result = idrMoveR(G,baseRing,currRing);
+  idDelete(&G);
+/*#ifdef CHECK_IDEAL_MWALK
+  pDelete(&p);
+#endif*/
   delete tmp_weight;
   delete ivNull;
@@ -4828 +4447 @@
 #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// pSetm_Error = (%d)", ErrorCheck());
-  Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
-#endif
-  return(G);
-}
-
-//unused
-#if 0
-ideal Mwalk_tst(ideal Go, intvec* curr_weight, intvec* target_weight)
-{
-  //clock_t tinput=clock();
-  //idString(Go,"Ginp");
-  int i, nV = currRing->N;
-  int nwalk=0, endwalks=0;
-
-  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
-  // ideal G1; ring endRing;
-  ring newRing, oldRing;
+  Print("\n//** Mwalk: Ergebnis.\n");
+  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
+  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
+#endif
+  return(result);
+}
+
+/*****************************
+ * THE RANDOM WALK ALGORITHM *
+ *****************************/
+ideal Mrwalk(ideal Go, intvec* orig_M, intvec* target_M, int weight_rad, int pert_deg, ring baseRing)
+{
+  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);
-  ring XXRing = currRing;
-
+  intvec* curr_weight = new intvec(nV);
+  intvec* target_weight = new intvec(nV);
+  intvec* exivlp = Mivlp(nV);
   intvec* tmp_weight = new intvec(nV);
-  for(i=nV-1; i>=0; i--)
-  {
-    (*tmp_weight)[i] = (*curr_weight)[i];
-  }
-  /* the monomial ordering of this current ring would be "dp" */
-  G = MstdCC(Go);
+#ifdef CHECK_IDEAL_MWALK
+  poly p;
+#endif
+  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;
-#endif
-  /* to avoid (1,0,...,0) as the target vector */
+   // 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
+  for(i=0; i<IDELEMS(Go); i++)
+  {
+    poly p=Go->m[i];
+    while(p!=NULL)
+    {
+      p_Setm(p,currRing);
+      pIter(p);
+    }
+    pDelete(&p);
+  }
+    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 ++;
-    //Print("\n// Entering the %d-th step:", nwalk);
-    //Print("\n// ring r[%d] = %s;", nwalk, rString(currRing));
+    nstep ++;
+#ifdef TIME_TEST
+    to = clock();
+#endif
+#ifdef CHECK_IDEAL_MWALK
     idString(G,"G");
-    /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
-    Gomega = MwalkInitialForm(G, curr_weight);
-    //ivString(curr_weight, "omega");
-    idString(Gomega,"Gw");
-
+#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 // BUCHBERGER_ALG
-
-
-    oldRing = currRing;
-
-    /* define a new ring that its ordering is "(a(curr_weight),lp) */
-    VMrDefault(curr_weight);
-    newRing = currRing;
-
-    Gomega1 = idrMoveR(Gomega, oldRing,currRing);
-
-    /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
-#ifdef  BUCHBERGER_ALG
-    M = MstdhomCC(Gomega1);
-#else
+    }
+#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;
-#endif // BUCHBERGER_ALG
-
-    idString(M,"M");
-
-      /* change the ring to oldRing */
-    rChangeCurrRing(oldRing);
+#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
+    idString(M, "M");
+#endif
+    //change the ring to baseRing
+    rChangeCurrRing(baseRing);
     M1 =  idrMoveR(M, newRing,currRing);
-    Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
-
-      /* 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 */
+    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 CHECK_IDEAL_MWALK
+    idString(F,"F");
+#endif
+#ifdef TIME_TEST
+    tlift = tlift + clock() - to;
+#endif
+    idDelete(&Gomega2);
     idDelete(&M1);
-    idDelete(&Gomega2);
-    idDelete(&G);
-    idString(F,"F");
-
-    /* change the ring to newRing */
-    rChangeCurrRing(newRing);
-    F1 = idrMoveR(F, oldRing,currRing);
-
-    /* reduce the Groebner basis <G> w.r.t. new ring */
-    G = kInterRedCC(F1, NULL);
-    //idSkipZeroes(G);//done by kInterRed
-    idDelete(&F1);
-    idString(G,"G");
-    if(endwalks == 1)
-      break;
-
-    /* compute a next weight vector */
-    intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
+    rChangeCurrRing(newRing); // change the ring to newRing
+    G = idrMoveR(F,baseRing,currRing);
+    idDelete(&F);
+    baseRing = currRing;
+    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);
+#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)
-    {
+    if(MivComp(next_weight, ivNull) == 1 || test_w_in_ConeCC(G, target_weight) == 1 || MivComp(target_weight,curr_weight) == 1 || MivComp(next_weight,curr_weight) == 1)
+    {
+#ifdef CHECK_IDEAL_MWALK
+      PrintS("\n//** Mrwalk: 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);
+      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
+      rChangeCurrRing(baseRing);
+      M1 =  idrMoveR(M, newRing,currRing);
+      idDelete(&M);
+      Gomega2 = idrMoveR(Gomega1, newRing,currRing);
+      idDelete(&Gomega1);
+      F = MLifttwoIdeal(Gomega2, M1, G);
+      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;
     }
-    if(MivComp(next_weight, target_weight) == 1)
-      endwalks = 1;
-
     for(i=nV-1; i>=0; i--)
+    {
       (*tmp_weight)[i] = (*curr_weight)[i];
-
-    /* 06.11.01 to free the memory: NOT Changed!!*/
-    for(i=nV-1; i>=0; i--)
       (*curr_weight)[i] = (*next_weight)[i];
+    }
     delete next_weight;
   }
   rChangeCurrRing(XXRing);
-  G = idrMoveR(G, newRing,currRing);
-
+  ideal result = idrMoveR(G,baseRing,currRing);
+  idDelete(&G);
+#ifdef CHECK_IDEAL_MWALK
+  pDelete(&p);
+#endif
   delete tmp_weight;
   delete ivNull;
-  PrintLn();
-  return(G);
-}
-#endif
-
-/**************************************************************/
-/*     Implementation of the perturbation walk algorithm      */
-/**************************************************************/
-/* If the perturbed target weight vector or an intermediate weight vector
-   doesn't stay in the correct Groebner cone, we have only
-   a reduced Groebner basis for the given ideal with respect to
-   a monomial order which differs to the given order.
-   Then we have to compute the wanted  reduced Groebner basis for it.
-   For this, we can use
-   1) the improved Buchberger algorithm or
-   2) the changed perturbation walk algorithm with a decreased degree.
-*/
-// use kStd, if nP = 0, else call LastGB
-ideal Mpwalk(ideal Go, int op_deg, int tp_deg,intvec* curr_weight,
-             intvec* target_weight, int nP)
-{
-  Set_Error(FALSE  );
+  delete exivlp;
+#ifndef BUCHBERGER_ALG
+  delete last_omega;
+#endif
+#ifdef TIME_TEST
+  Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
+  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
+#endif
+  return(result);
+}
+
+/**************************************************************************
+ * Implementation of the perturbation walk algorithm                      *
+ *                                                                        *
+ * If the perturbed target weight vector or an intermediate weight vector *
+ * doesn't stay in the correct Groebner cone, we have only                *
+ * a reduced Groebner basis for the given ideal with respect to           *
+ * a monomial order which differs to the given order.                     *
+ * Then we have to compute the wanted  reduced Groebner basis for it.     *
+ * For this, we can use                                                   *
+ * 1) the improved Buchberger algorithm or                                *
+ * 2) the changed perturbation walk algorithm with a decreased degree.    *
+ **************************************************************************/
+
+/***********************************
+ * THE PERTURBATION WALK ALGORITHM *
+ ***********************************/
+ideal Mpwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int op_deg, int tp_deg, ring baseRing)
+{
+  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;
-  //Print("// pSetm_Error = (%d)", ErrorCheck());
-
-  clock_t  tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
-  xtextra=0;
+#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;
-
-  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;
+#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* iv_dp = MivUnit(nV);// define (1,1,...,1)
+  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;
-#endif
-  intvec* next_weight;
-
-  // to avoid (1,0,...,0) as the target vector
+   // to avoid (1,0,...,0) as the target vector
   intvec* last_omega = new intvec(nV);
-  for(i=nV-1; i>0; i--)
+  for(i=0 i<nV; i++)
+  {
     (*last_omega)[i] = 1;
+  }
   (*last_omega)[0] = 10000;
-
-  ring XXRing = currRing;
-
-
+#endif
+  idString(Go,"Go");
+  baseRing = currRing;
+  newRing = VMrDefault(curr_weight);
+  rChangeCurrRing(newRing);
+  G = idrMoveR(Go,baseRing,currRing);
+#ifdef TIME_TEST
   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
-      VMrDefault(curr_weight);
-
-    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 */
+#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)
   {
-    if (rParameter(currRing) != NULL)
-      DefRingPar(target_weight);
-    else
-      VMrDefault(target_weight);
-
-    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");
-  */
+  }
+#ifdef TIME_TEST
+  Print("\n//** Mpwalk: perturbation walk with degrees (%d,%d):",op_deg,tp_deg);
+  ivString(curr_weight, "new curr_weight");
+  ivString(target_weight, "new target_weight");
+#endif
+  nwalk = 0;
   while(1)
   {
-    nstep ++;
+    nwalk ++;
+#ifdef CHECK_IDEAL_MWALK
+    idString(G,"G");
+#endif
+#ifdef TIME_TEST
     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;
-
+#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,"G_omega");
+#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);
+    }
+#endif
+    if(nwalk == 1)
+    {
+      newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
+    }
     else
-      VMrDefault(curr_weight);
-
-    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");
-
+    {
+      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);
+#ifdef CHECK_IDEAL_MWALK
+    idString(Gomega1, "Gomega1");
+#endif
+    // compute a Groebner basis of <Gomega> w.r.t. "newRing"
+#ifdef TIME_TEST
+    to = clock();
+#endif
 #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);
+#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);
-    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 */
+    idDelete(&M);
+#ifdef CHECK_IDEAL_MWALK
+    idString(M1, "M1");
+#endif
+    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
+    idDelete(&Gomega1);
+#ifdef CHECK_IDEAL_MWALK
+    idString(Gomega2, "G_omega2");
+#endif
+    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);
-    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;
+    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 = 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(Overflow_Error == TRUE)
     {
-      ntwC = 0;
-      //ntestomega = 1;
-      //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
-      //idElements(G, "G");
+      PrintS("\n//**Mpwalk: OVERFLOW! The computed vector does not stay in cone, the result may be wrong.\n");
       delete next_weight;
-      goto FINISH_160302;
-    }
-    if(MivComp(next_weight, ivNull) == 1){
-      newRing = currRing;
+      break;
+    }
+    if(test_w_in_ConeCC(G,target_weight) == 1 || MivComp(next_weight, ivNull) == 1)
+    {
       delete next_weight;
-      //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
       break;
     }
-    if(MivComp(next_weight, target_weight) == 1)
-      endwalks = 1;
-
+    //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;
-  }//while
-
-  if(tp_deg != 1)
-  {
-  FINISH_160302:
-    if(MivSame(orig_target, exivlp) == 1)
-      if (rParameter(currRing) != NULL)
-        DefRingParlp();
-      else
-        VMrDefaultlp();
+  } //end of while-loop
+  Print("\n// Mpwalk 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);
+}
+
+/*******************************************************
+ * THE PERTURBATION WALK ALGORITHM WITH RANDOM ELEMENT *
+ *******************************************************/
+ideal Mprwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int op_deg, int tp_deg, ring baseRing)
+{
+  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
-      if (rParameter(currRing) != NULL)
-        DefRingPar(orig_target);
-      else
-        VMrDefault(orig_target);
-
-    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);
-  }
+    {
+      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;
-  if(tp_deg != 1)
-    delete target_weight;
-
-  if(op_deg != 1 )
-    delete curr_weight;
-
   delete exivlp;
+#ifndef BUCHBERGER_ALG
   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);
+#endif
+#ifdef TIME_TEST
+  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
+#endif
+  return(Res);
+}
+
+poly div_with_remainder( poly f, poly g, ring r)
+{
+return singclap_pdivide ( f, g, r );
 }
 
@@ -5332 +5169 @@
 int Xngleich;
 
-/***********************************************************************
- * Perturb the start weight vector at the top level, i.e. nlev = 1     *
- ***********************************************************************/
-static ideal rec_fractal_call(ideal G, int nlev, intvec* omtmp)
-{
-  Overflow_Error =  FALSE;
-  //Print("\n\n// Entering the %d-th recursion:", nlev);
-
-  int i, nV = currRing->N;
-  ring new_ring, testring;
-  //ring extoRing;
-  ideal Gomega, Gomega1, Gomega2, F, F1, Gresult, Gresult1, G1, Gt;
-  int nwalks = 0;
-  intvec* Mwlp;
-#ifndef BUCHBERGER_ALG
-  intvec* hilb_func;
-#endif
-//  intvec* extXtau;
-  intvec* next_vect;
-  intvec* omega2 = new intvec(nV);
-  intvec* altomega = new intvec(nV);
-
-  //BOOLEAN isnewtarget = FALSE;
-
-  // to avoid (1,0,...,0) as the target vector (Hans)
-  intvec* last_omega = new intvec(nV);
-  for(i=nV-1; i>0; i--)
-    (*last_omega)[i] = 1;
-  (*last_omega)[0] = 10000;
-
-  intvec* omega = new intvec(nV);
-  for(i=0; i<nV; i++) {
-    if(Xsigma->length() == nV)
-      (*omega)[i] =  (*Xsigma)[i];
+/******************************
+ * THE FRACTAL WALK ALGORITHM *
+ ******************************/
+ideal Mfwalk(ideal Go, intvec* curr_weight, intvec* orig_target_weight, int pert_deg, ring XXRing)
+{
+  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;
+  ring newRing;
+  ring baseRing = currRing;
+  rChangeCurrRing(XXRing);
+  Go = idrMoveR(Go,baseRing,currRing);
+  int i,nwalk,endwalks = 0;
+  int nV = currRing->N;
+  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1;
+  intvec* ivNull = new intvec(nV);
+  intvec* next_weight = new intvec(nV);
+  intvec* tmp_weight = new intvec(nV);
+#ifdef TIME_TEST
+  to = clock();
+#endif
+  ideal G = MstdCC(Go);
+#ifdef TIME_TEST
+  tostd = clock()-to;
+#endif
+#ifdef CHECK_IDEAL_MWALK
+    idString(Go,"Go");
+#endif
+  intvec* target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
+  for(i=0; i<nV; i++)
+  {
+    (*tmp_weight)[i] = (*target_weight)[i];
+  }
+  nwalk = 0;
+  while(1)
+  {
+    nwalk++;
+    baseRing = currRing;
+    Gomega = MwalkInitialForm(G, curr_weight);
+#ifdef CHECK_IDEAL_MWALK
+    idString(Gomega,"Gomega");
+#endif
+    next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
+    MivString(curr_weight, target_weight, tmp_weight);
+    if(MivSame(curr_weight,target_weight) ==1)
+    {
+      break;
+    }
+    if( MivSame(tmp_weight, curr_weight) == 1 )
+    {
+      if(test_w_in_ConeCC(G, target_weight) == 1)
+      {
+        break;
+      }
+      else
+      {
+        pert_deg++;
+        target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
+        next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
+      }
+    }
+    for(i=0; i<nV; i++)
+    {
+      (*tmp_weight)[i] = (*curr_weight)[i];
+      (*curr_weight)[i] = (*next_weight)[i];
+    }
+    MivString(curr_weight, target_weight, tmp_weight);
+    newRing = VMrRefine(tmp_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
+    rChangeCurrRing(newRing); // change the ring to newRing
+    Gomega1 =  idrMoveR(Gomega, baseRing,currRing);
+    idDelete(&Gomega);
+    if(pert_deg >= nV)
+    {
+      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
+    }
     else
-      (*omega)[i] = (*Xsigma)[(nV*(nlev-1))+i];
-
-    (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
-  }
-
-   if(nlev == 1)  Xcall = 1;
-   else Xcall = 0;
-
-  ring oRing = currRing;
-
-  while(1)
-  {
-#ifdef FIRST_STEP_FRACTAL
-    // perturb the current weight vector only on the top level or
-    // after perturbation of the both vectors, nlev = 2 as the top level
-    if((nlev == 1 && Xcall == 0) || (nlev == 2 && Xngleich == 1))
-      if(islengthpoly2(G) == 1)
-      {
-        Mwlp = MivWeightOrderlp(omega);
-        Xsigma = Mfpertvector(G, Mwlp);
-        delete Mwlp;
-        Overflow_Error = FALSE;
-      }
-#endif
-    nwalks ++;
-    NEXT_VECTOR_FRACTAL:
-    to=clock();
-    /* determine the next border */
-    next_vect = MkInterRedNextWeight(omega,omega2,G);
-    xtnw=xtnw+clock()-to;
-#ifdef PRINT_VECTORS
-    MivString(omega, omega2, next_vect);
-#endif
-    oRing = currRing;
-
-    /* We only perturb the current target vector at the recursion  level 1 */
-    if(Xngleich == 0 && nlev == 1) //(ngleich == 0) important, e.g. ex2, ex3
-      if (MivComp(next_vect, omega2) == 1)
-      {
-        /* to dispense with taking initial (and lifting/interreducing
-           after the call of recursion */
-        //Print("\n\n// ** Perturb the both vectors with degree %d with",nlev);
-        //idElements(G, "G");
-
-        Xngleich = 1;
-        nlev +=1;
-
-        if (rParameter(currRing) != NULL)
-          DefRingPar(omtmp);
-        else
-          VMrDefault(omtmp);
-
-        testring = currRing;
-        Gt = idrMoveR(G, oRing,currRing);
-
-        /* perturb the original target vector w.r.t. the current GB */
-        delete Xtau;
-        Xtau = NewVectorlp(Gt);
-
-        rChangeCurrRing(oRing);
-        G = idrMoveR(Gt, testring,currRing);
-
-        /* perturb the current vector w.r.t. the current GB */
-        Mwlp = MivWeightOrderlp(omega);
-        Xsigma = Mfpertvector(G, Mwlp);
-        delete Mwlp;
-
-        for(i=nV-1; i>=0; i--) {
-          (*omega2)[i] = (*Xtau)[nV+i];
-          (*omega)[i] = (*Xsigma)[nV+i];
-        }
-
-        delete next_vect;
-        to=clock();
-
-        /* to avoid the value of Overflow_Error that occur in Mfpertvector*/
-        Overflow_Error = FALSE;
-
-        next_vect = MkInterRedNextWeight(omega,omega2,G);
-        xtnw=xtnw+clock()-to;
-
-#ifdef PRINT_VECTORS
-        MivString(omega, omega2, next_vect);
-#endif
-      }
-
-
-    /* check whether the the computed vector is in the correct cone */
-    /* If no, the reduced GB of an omega-homogeneous ideal will be
-       computed by Buchberger algorithm and stop this recursion step*/
-    //if(test_w_in_ConeCC(G, next_vect) != 1) //e.g. Example s7, cyc6
-    if(Overflow_Error == TRUE)
-    {
-      delete next_vect;
-      if (rParameter(currRing) != NULL)
-      {
-        DefRingPar(omtmp);
-      }
-      else
-      {
-        VMrDefault(omtmp);
-      }
-#ifdef TEST_OVERFLOW
-      Gt = idrMoveR(G, oRing,currRing);
-      Gt = NULL; return(Gt);
-#endif
-
-      //Print("\n\n// apply BB's alg. in ring r = %s;", rString(currRing));
-      to=clock();
-      Gt = idrMoveR(G, oRing,currRing);
-      G1 = MstdCC(Gt);
-      xtextra=xtextra+clock()-to;
-      Gt = NULL;
-
-      delete omega2;
-      delete altomega;
-
-      //Print("\n// Leaving the %d-th recursion with %d steps", nlev, nwalks);
-      //Print("  ** Overflow_Error? (%d)", Overflow_Error);
-      nnflow ++;
-
-      Overflow_Error = FALSE;
-      return (G1);
-    }
-
-
-    /* If the perturbed target vector stays in the correct cone,
-       return the current GB,
-       otherwise, return the computed  GB by the Buchberger-algorithm.
-       Then we update the perturbed target vectors w.r.t. this GB. */
-
-    /* the computed vector is equal to the origin vector, since
-       t is not defined */
-    if (MivComp(next_vect, XivNull) == 1)
-    {
-      if (rParameter(currRing) != NULL)
-        DefRingPar(omtmp);
-      else
-        VMrDefault(omtmp);
-
-      testring = currRing;
-      Gt = idrMoveR(G, oRing,currRing);
-
-      if(test_w_in_ConeCC(Gt, omega2) == 1) {
-        delete omega2;
-        delete next_vect;
-        delete altomega;
-        //Print("\n// Leaving the %d-th recursion with %d steps ",nlev, nwalks);
-        //Print(" ** Overflow_Error? (%d)", Overflow_Error);
-
-        return (Gt);
-      }
-      else
-      {
-        //ivString(omega2, "tau'");
-        //Print("\n//  tau' doesn't stay in the correct cone!!");
-
-#ifndef  MSTDCC_FRACTAL
-        //07.08.03
-        //ivString(Xtau, "old Xtau");
-        intvec* Xtautmp = Mfpertvector(Gt, MivMatrixOrder(omtmp));
-#ifdef TEST_OVERFLOW
-      if(Overflow_Error == TRUE)
-      Gt = NULL; return(Gt);
-#endif
-
-        if(MivSame(Xtau, Xtautmp) == 1)
-        {
-          //PrintS("\n// Update vectors are equal to the old vectors!!");
-          delete Xtautmp;
-          goto FRACTAL_MSTDCC;
-        }
-
-        Xtau = Xtautmp;
-        Xtautmp = NULL;
-        //ivString(Xtau, "new  Xtau");
-
-        for(i=nV-1; i>=0; i--)
-          (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
-
-        //Print("\n//  ring tau = %s;", rString(currRing));
-        rChangeCurrRing(oRing);
-        G = idrMoveR(Gt, testring,currRing);
-
-        goto NEXT_VECTOR_FRACTAL;
-#endif
-
-      FRACTAL_MSTDCC:
-        //Print("\n//  apply BB-Alg in ring = %s;", rString(currRing));
-        to=clock();
-        G = MstdCC(Gt);
-        xtextra=xtextra+clock()-to;
-
-        oRing = currRing;
-
-        // update the original target vector w.r.t. the current GB
-        if(MivSame(Xivinput, Xivlp) == 1)
-          if (rParameter(currRing) != NULL)
-            DefRingParlp();
-          else
-            VMrDefaultlp();
-        else
-          if (rParameter(currRing) != NULL)
-            DefRingPar(Xivinput);
-          else
-            VMrDefault(Xivinput);
-
-        testring = currRing;
-        Gt = idrMoveR(G, oRing,currRing);
-
-        delete Xtau;
-        Xtau = NewVectorlp(Gt);
-
-        rChangeCurrRing(oRing);
-        G = idrMoveR(Gt, testring,currRing);
-
-        delete omega2;
-        delete next_vect;
-        delete altomega;
-        /*
-          Print("\n// Leaving the %d-th recursion with %d steps,", nlev,nwalks);
-          Print(" ** Overflow_Error? (%d)", Overflow_Error);
-        */
-        if(Overflow_Error == TRUE)
-          nnflow ++;
-
-        Overflow_Error = FALSE;
-        return(G);
-      }
-    }
-
-    for(i=nV-1; i>=0; i--) {
-      (*altomega)[i] = (*omega)[i];
-      (*omega)[i] = (*next_vect)[i];
-    }
-    delete next_vect;
-
-    to=clock();
-    /* Take the initial form of <G> w.r.t. omega */
-    Gomega = MwalkInitialForm(G, omega);
-    xtif=xtif+clock()-to;
-
-#ifndef  BUCHBERGER_ALG
-    if(isNolVector(omega) == 0)
-      hilb_func = hFirstSeries(Gomega,NULL,NULL,omega,currRing);
-    else
-      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
-#endif // BUCHBERGER_ALG
-
-    if (rParameter(currRing) != NULL)
-      DefRingPar(omega);
-    else
-      VMrDefault(omega);
-
-    Gomega1 = idrMoveR(Gomega, oRing,currRing);
-
-    /* Maximal recursion depth, to compute a red. GB */
-    /* Fractal walk with the alternative recursion */
-    /* alternative recursion */
-    // if(nlev == nV || lengthpoly(Gomega1) == 0)
-    if(nlev == Xnlev || lengthpoly(Gomega1) == 0)
-      //if(nlev == nV) // blind recursion
-    {
-      /*
-      if(Xnlev != nV)
-      {
-        Print("\n// ** Xnlev = %d", Xnlev);
-        ivString(Xtau, "Xtau");
-      }
-      */
-      to=clock();
-#ifdef  BUCHBERGER_ALG
-      Gresult = MstdhomCC(Gomega1);
-#else
-      Gresult =kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,omega);
-      delete hilb_func;
-#endif // BUCHBERGER_ALG
-      xtstd=xtstd+clock()-to;
-    }
-    else {
-      rChangeCurrRing(oRing);
-      Gomega1 = idrMoveR(Gomega1, oRing,currRing);
-      Gresult = rec_fractal_call(idCopy(Gomega1),nlev+1,omega);
-    }
-
-    //convert a Groebner basis from a ring to another ring,
-    new_ring = currRing;
-
-    rChangeCurrRing(oRing);
-    Gresult1 = idrMoveR(Gresult, new_ring,currRing);
-    Gomega2 = idrMoveR(Gomega1, new_ring,currRing);
-
-    to=clock();
-    /* Lifting process */
-    F = MLifttwoIdeal(Gomega2, Gresult1, G);
-    xtlift=xtlift+clock()-to;
-    idDelete(&Gresult1);
+    {
+      M = idCopy(Mwalk(idCopy(Gomega1), tmp_weight, curr_weight, currRing));
+    }
+    idSkipZeroes(M);
+#ifdef CHECK_IDEAL_MWALK
+    idString(M,"M");
+#endif
+    rChangeCurrRing(baseRing); //change ring to baseRing
+    M1 =  idrMoveR(M, newRing,currRing);
+    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
+    idDelete(&M);
+    idDelete(&Gomega1);
+    F = MLifttwoIdeal(Gomega2, M1, G);
     idDelete(&Gomega2);
-    idDelete(&G);
-
-    rChangeCurrRing(new_ring);
-    F1 = idrMoveR(F, oRing,currRing);
-
-    to=clock();
-    /* Interreduce G */
-    G = kInterRedCC(F1, NULL);
-    xtred=xtred+clock()-to;
-    idDelete(&F1);
-  }
-}
-
-/************************************************************************
- * Perturb the start weight vector at the top level with random element *
- ************************************************************************/
-static ideal rec_r_fractal_call(ideal G, int nlev, intvec* omtmp, int weight_rad)
-{
-  Overflow_Error =  FALSE;
-  //Print("\n\n// Entering the %d-th recursion:", nlev);
-
-  int i,k,weight_norm;
-  int nV = currRing->N;
-  ring new_ring, testring;
-  //ring extoRing;
-  ideal Gomega, Gomega1, Gomega2, F, F1, Gresult, Gresult1, G1, Gt;
-  int nwalks = 0;
-  intvec* Mwlp;
-#ifndef BUCHBERGER_ALG
-  intvec* hilb_func;
-#endif
-  //intvec* extXtau;
-  intvec* next_vect;
-  intvec* omega2 = new intvec(nV);
-  intvec* altomega = new intvec(nV);
-
-  //BOOLEAN isnewtarget = FALSE;
-
-  // to avoid (1,0,...,0) as the target vector (Hans)
-  intvec* last_omega = new intvec(nV);
-  for(i=nV-1; i>0; i--)
-    (*last_omega)[i] = 1;
-  (*last_omega)[0] = 10000;
-
-  intvec* omega = new intvec(nV);
-  for(i=0; i<nV; i++) {
-    if(Xsigma->length() == nV)
-      (*omega)[i] =  (*Xsigma)[i];
-    else
-      (*omega)[i] = (*Xsigma)[(nV*(nlev-1))+i];
-
-    (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
-  }
-
-   if(nlev == 1)  Xcall = 1;
-   else Xcall = 0;
-
-  ring oRing = currRing;
-
-  while(1)
-  {
-#ifdef FIRST_STEP_FRACTAL
-    // perturb the current weight vector only on the top level or
-    // after perturbation of the both vectors, nlev = 2 as the top level
-    if((nlev == 1 && Xcall == 0) || (nlev == 2 && Xngleich == 1))
-      if(islengthpoly2(G) == 1)
-      {
-        Mwlp = MivWeightOrderlp(omega);
-        Xsigma = Mfpertvector(G, Mwlp);
-        delete Mwlp;
-        Overflow_Error = FALSE;
-      }
-#endif
-    nwalks ++;
-    NEXT_VECTOR_FRACTAL:
-    to=clock();
-    /* determine the next border */
-    next_vect = MkInterRedNextWeight(omega,omega2,G);
-    xtnw=xtnw+clock()-to;
-#ifdef PRINT_VECTORS
-    MivString(omega, omega2, next_vect);
-#endif
-    oRing = currRing;
-
-    /* We only perturb the current target vector at the recursion  level 1 */
-    if(Xngleich == 0 && nlev == 1) //(ngleich == 0) important, e.g. ex2, ex3
-    {
-      if (MivComp(next_vect, omega2) == 1)
-      {
-        /* to dispense with taking initial (and lifting/interreducing
-           after the call of recursion */
-        //Print("\n\n// ** Perturb the both vectors with degree %d with",nlev);
-        //idElements(G, "G");
-
-        Xngleich = 1;
-        nlev +=1;
-
-        if (rParameter(currRing) != NULL)
-          DefRingPar(omtmp);
-        else
-          VMrDefault(omtmp);
-
-        testring = currRing;
-        Gt = idrMoveR(G, oRing,currRing);
-
-        /* perturb the original target vector w.r.t. the current GB */
-        delete Xtau;
-        Xtau = NewVectorlp(Gt);
-
-        rChangeCurrRing(oRing);
-        G = idrMoveR(Gt, testring,currRing);
-
-        /* perturb the current vector w.r.t. the current GB */
-        Mwlp = MivWeightOrderlp(omega);
-        Xsigma = Mfpertvector(G, Mwlp);
-        delete Mwlp;
-
-        for(i=nV-1; i>=0; i--) {
-          (*omega2)[i] = (*Xtau)[nV+i];
-          (*omega)[i] = (*Xsigma)[nV+i];
-        }
-
-        delete next_vect;
-        to=clock();
-
-        /* to avoid the value of Overflow_Error that occur in Mfpertvector*/
-        Overflow_Error = FALSE;
-
-        next_vect = MkInterRedNextWeight(omega,omega2,G);
-        xtnw=xtnw+clock()-to;
-
-#ifdef PRINT_VECTORS
-        MivString(omega, omega2, next_vect);
-#endif
-      }
-      else
-      {
-        // compute a perturbed next weight vector "next_vect1"
-        intvec* next_vect11 = MPertVectors(G, MivMatrixOrder(omega), nlev);
-        intvec* next_vect1 = MkInterRedNextWeight(next_vect11, omega2, G);
-        // Print("\n//  size of next_vect  = %d", sizeof((*next_vect)));
-        // Print("\n//  size of next_vect1  = %d", sizeof((*next_vect1)));
-        // Print("\n//  size of next_vect11  = %d", sizeof((*next_vect11)));
-        delete next_vect11;
-
-        // compare next_vect and next_vect1
-        ideal G_test = MwalkInitialForm(G, next_vect);
-        ideal G_test1 = MwalkInitialForm(G, next_vect1);
-        // Print("\n// G_test, G_test 1 erzeugt");
-        if(IDELEMS(G_test1) <= IDELEMS(G_test))
-          {
-          next_vect = ivCopy(next_vect1);
-          }
-        delete next_vect1;
-        // compute a random next weight vector "next_vect2"
-        intvec* next_vect22 = ivCopy(omega2);
-        // Print("\n//  size of next_vect22  = %d", sizeof((*next_vect22)));
-        k = 0;
-        while(test_w_in_ConeCC(G, next_vect22) == 0)
-        {
-          k = k + 1;
-          if(k>10)
-          {
-            break;
-          }
-          weight_norm = 0;
-          while(weight_norm == 0)
-          {
-            for(i=nV-1; i>=0; i--)
-            {
-              (*next_vect22)[i] = rand() % 60000 - 30000;
-              weight_norm = weight_norm + (*next_vect22)[i]*(*next_vect22)[i];
-            }
-            weight_norm = 1 + floor(sqrt(weight_norm));
-          }
-          for(i=nV-1; i>=0; i--)
-          {
-            if((*next_vect22)[i] < 0)
-            {
-              (*next_vect22)[i] = 1 + (*omega)[i] + floor(weight_rad*(*next_vect22)[i]/weight_norm);
-            }
-            else
-            {
-              (*next_vect22)[i] = (*omega)[i] + floor(weight_rad*(*next_vect22)[i]/weight_norm);
-            }
-          }
-        }
-        if(test_w_in_ConeCC(G, next_vect22) == 1)
-        {
-          //compare next_weight and next_vect2
-          intvec* next_vect2 = MkInterRedNextWeight(next_vect22, omega2, G);
-          // Print("\n//  size of next_vect2  = %d", sizeof((*next_vect2)));
-          ideal G_test2 = MwalkInitialForm(G, next_vect2);
-          if(IDELEMS(G_test2) <= IDELEMS(G_test))
-          {
-            if(IDELEMS(G_test2) <= IDELEMS(G_test1))
-            {
-              next_vect = ivCopy(next_vect2);
-            }
-          }
-          idDelete(&G_test2);
-          delete next_vect2;
-        }
-        delete next_vect22;
-        idDelete(&G_test);
-        idDelete(&G_test1);
-#ifdef PRINT_VECTORS
-        MivString(omega, omega2, next_vect);
-#endif
-      }
-    }
-
-
-    /* check whether the the computed vector is in the correct cone */
-    /* If no, the reduced GB of an omega-homogeneous ideal will be
-       computed by Buchberger algorithm and stop this recursion step*/
-    //if(test_w_in_ConeCC(G, next_vect) != 1) //e.g. Example s7, cyc6
-    if(Overflow_Error == TRUE)
-    {
-      delete next_vect;
-
-    //OVERFLOW_IN_NEXT_VECTOR:
-      if (rParameter(currRing) != NULL)
-        DefRingPar(omtmp);
-      else
-        VMrDefault(omtmp);
-
-#ifdef TEST_OVERFLOW
-      Gt = idrMoveR(G, oRing,currRing);
-      Gt = NULL; return(Gt);
-#endif
-
-      //Print("\n\n// apply BB's alg. in ring r = %s;", rString(currRing));
-      to=clock();
-      Gt = idrMoveR(G, oRing,currRing);
-      G1 = MstdCC(Gt);
-      xtextra=xtextra+clock()-to;
-      Gt = NULL;
-
-      delete omega2;
-      delete altomega;
-
-      //Print("\n// Leaving the %d-th recursion with %d steps", nlev, nwalks);
-      //Print("  ** Overflow_Error? (%d)", Overflow_Error);
-      nnflow ++;
-
-      Overflow_Error = FALSE;
-      return (G1);
-    }
-
-
-    /* If the perturbed target vector stays in the correct cone,
-       return the current GB,
-       otherwise, return the computed  GB by the Buchberger-algorithm.
-       Then we update the perturbed target vectors w.r.t. this GB. */
-
-    /* the computed vector is equal to the origin vector, since
-       t is not defined */
-    if (MivComp(next_vect, XivNull) == 1)
-    {
-      if (rParameter(currRing) != NULL)
-        DefRingPar(omtmp);
-      else
-        VMrDefault(omtmp);
-
-      testring = currRing;
-      Gt = idrMoveR(G, oRing,currRing);
-
-      if(test_w_in_ConeCC(Gt, omega2) == 1) {
-        delete omega2;
-        delete next_vect;
-        delete altomega;
-        //Print("\n// Leaving the %d-th recursion with %d steps ",nlev, nwalks);
-        //Print(" ** Overflow_Error? (%d)", Overflow_Error);
-
-        return (Gt);
-      }
-      else
-      {
-        //ivString(omega2, "tau'");
-        //Print("\n//  tau' doesn't stay in the correct cone!!");
-
-#ifndef  MSTDCC_FRACTAL
-        //07.08.03
-        //ivString(Xtau, "old Xtau");
-        intvec* Xtautmp = Mfpertvector(Gt, MivMatrixOrder(omtmp));
-#ifdef TEST_OVERFLOW
-      if(Overflow_Error == TRUE)
-      Gt = NULL; return(Gt);
-#endif
-
-        if(MivSame(Xtau, Xtautmp) == 1)
-        {
-          //PrintS("\n// Update vectors are equal to the old vectors!!");
-          delete Xtautmp;
-          goto FRACTAL_MSTDCC;
-        }
-
-        Xtau = Xtautmp;
-        Xtautmp = NULL;
-        //ivString(Xtau, "new  Xtau");
-
-        for(i=nV-1; i>=0; i--)
-          (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
-
-        //Print("\n//  ring tau = %s;", rString(currRing));
-        rChangeCurrRing(oRing);
-        G = idrMoveR(Gt, testring,currRing);
-
-        goto NEXT_VECTOR_FRACTAL;
-#endif
-
-      FRACTAL_MSTDCC:
-        //Print("\n//  apply BB-Alg in ring = %s;", rString(currRing));
-        to=clock();
-        G = MstdCC(Gt);
-        xtextra=xtextra+clock()-to;
-
-        oRing = currRing;
-
-        // update the original target vector w.r.t. the current GB
-        if(MivSame(Xivinput, Xivlp) == 1)
-          if (rParameter(currRing) != NULL)
-            DefRingParlp();
-          else
-            VMrDefaultlp();
-        else
-          if (rParameter(currRing) != NULL)
-            DefRingPar(Xivinput);
-          else
-            VMrDefault(Xivinput);
-
-        testring = currRing;
-        Gt = idrMoveR(G, oRing,currRing);
-
-        delete Xtau;
-        Xtau = NewVectorlp(Gt);
-
-        rChangeCurrRing(oRing);
-        G = idrMoveR(Gt, testring,currRing);
-
-        delete omega2;
-        delete next_vect;
-        delete altomega;
-        /*
-          Print("\n// Leaving the %d-th recursion with %d steps,", nlev,nwalks);
-          Print(" ** Overflow_Error? (%d)", Overflow_Error);
-        */
-        if(Overflow_Error == TRUE)
-          nnflow ++;
-
-        Overflow_Error = FALSE;
-        return(G);
-      }
-    }
-
-    for(i=nV-1; i>=0; i--) {
-      (*altomega)[i] = (*omega)[i];
-      (*omega)[i] = (*next_vect)[i];
-    }
-    delete next_vect;
-
-    to=clock();
-    /* Take the initial form of <G> w.r.t. omega */
-    Gomega = MwalkInitialForm(G, omega);
-    xtif=xtif+clock()-to;
-
-#ifndef  BUCHBERGER_ALG
-    if(isNolVector(omega) == 0)
-      hilb_func = hFirstSeries(Gomega,NULL,NULL,omega,currRing);
-    else
-      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
-#endif // BUCHBERGER_ALG
-
-    if (rParameter(currRing) != NULL)
-      DefRingPar(omega);
-    else
-      VMrDefault(omega);
-
-    Gomega1 = idrMoveR(Gomega, oRing,currRing);
-
-    /* Maximal recursion depth, to compute a red. GB */
-    /* Fractal walk with the alternative recursion */
-    /* alternative recursion */
-    // if(nlev == nV || lengthpoly(Gomega1) == 0)
-    if(nlev == Xnlev || lengthpoly(Gomega1) == 0)
-      //if(nlev == nV) // blind recursion
-    {
-      /*
-      if(Xnlev != nV)
-      {
-        Print("\n// ** Xnlev = %d", Xnlev);
-        ivString(Xtau, "Xtau");
-      }
-      */
-      to=clock();
-#ifdef  BUCHBERGER_ALG
-      Gresult = MstdhomCC(Gomega1);
-#else
-      Gresult =kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,omega);
-      delete hilb_func;
-#endif // BUCHBERGER_ALG
-      xtstd=xtstd+clock()-to;
-    }
-    else {
-      rChangeCurrRing(oRing);
-      Gomega1 = idrMoveR(Gomega1, oRing,currRing);
-      Gresult = rec_fractal_call(idCopy(Gomega1),nlev+1,omega);
-    }
-
-    //convert a Groebner basis from a ring to another ring,
-    new_ring = currRing;
-
-    rChangeCurrRing(oRing);
-    Gresult1 = idrMoveR(Gresult, new_ring,currRing);
-    Gomega2 = idrMoveR(Gomega1, new_ring,currRing);
-
-    to=clock();
-    /* Lifting process */
-    F = MLifttwoIdeal(Gomega2, Gresult1, G);
-    xtlift=xtlift+clock()-to;
-    idDelete(&Gresult1);
-    idDelete(&Gomega2);
-    idDelete(&G);
-
-    rChangeCurrRing(new_ring);
-    F1 = idrMoveR(F, oRing,currRing);
-
-    to=clock();
-    /* Interreduce G */
-    G = kInterRedCC(F1, NULL);
-    xtred=xtred+clock()-to;
-    idDelete(&F1);
-  }
-}
-
-
-
-/*******************************************************************************
- * The implementation of the fractal walk algorithm                            *
- *                                                                             *
- * The main procedur Mfwalk calls the recursive Subroutine                     *
- * rec_fractal_call to compute the wanted Grï¿œbner basis.                       *
- * At the main procedur we compute the reduced Grï¿œbner basis w.r.t. a "fast"   *
- * order, e.g. "dp" and a sequence of weight vectors which are row vectors     *
- * of a matrix. This matrix defines the given monomial order, e.g. "lp"        *
- *******************************************************************************/
-ideal Mfwalk(ideal G, intvec* ivstart, intvec* ivtarget)
+    idSkipZeroes(F);
+#ifdef CHECK_IDEAL_MWALK
+    idString(F,"F");
+#endif
+    rChangeCurrRing(newRing); // change the ring to newRing
+    G = idrMoveR(F,baseRing,currRing);
+    idDelete(&F);
+    baseRing = currRing;
+    if(MivComp(next_weight, ivNull) == 1)
+    {
+      delete next_weight;
+      break;
+    }
+  }
+  delete next_weight;
+  if(test_w_in_ConeCC(G, orig_target_weight) != 1)
+  {
+    newRing = VMrDefault(orig_target_weight);  //define a new ring with ordering "(a(target_weight),lp)
+    rChangeCurrRing(newRing);
+    G = idrMoveR(G,baseRing,currRing);
+    M = idCopy(Mwalk(idCopy(G), tmp_weight, orig_target_weight, currRing));
+    idSkipZeroes(G);
+    baseRing = currRing;
+  }
+  ENDE:
+  rChangeCurrRing(XXRing);
+  G = idrMoveR(G,baseRing,currRing);
+  delete tmp_weight;
+  delete ivNull;
+#ifdef TIME_TEST
+  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
+#endif
+  return(G);
+}
+
+/***********************************************
+THE FRACTAL WALK ALGORITHM WITH RANDOM ELEMENT *
+************************************************/
+ideal Mfrwalk(ideal Go, intvec* curr_weight, intvec* orig_target_weight, int pert_deg, int weight_rad, ring XXRing)
 {
   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);
+#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;
+  ring newRing;
+  ring baseRing = currRing;
+  rChangeCurrRing(XXRing);
+  Go = idrMoveR(Go,baseRing,currRing);
+  int i,nwalk,endwalks = 0;
+  int nV = currRing->N;
+  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1;
+  intvec* ivNull = new intvec(nV);
+  intvec* next_weight = new intvec(nV);
+  intvec* tmp_weight = new intvec(nV);
+#ifdef TIME_TEST
+  to = clock();
+#endif
+  ideal G = MstdCC(Go);
+#ifdef TIME_TEST
+  tostd = clock()-to;
+#endif
+  intvec* target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
+  for(i=0; i<nV; i++)
+  {
+    (*tmp_weight)[i] = (*target_weight)[i];
+  }
+  nwalk = 0;
+  while(1)
+  {
+    nwalk++;
+    baseRing = currRing;
+    Gomega = MwalkInitialForm(G, curr_weight);
+#ifdef CHECK_IDEAL_MWALK
+    idString(Gomega,"Gomega");
+#endif
+    next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
+    MivString(curr_weight, target_weight, tmp_weight);
+    if(MivSame(curr_weight,target_weight) ==1)
+    {
+      break;
+    }
+    if( MivSame(tmp_weight, curr_weight) == 1 )
+    {
+      if(test_w_in_ConeCC(G, target_weight) == 1)
+      {
+        break;
+      }
       else
-        Mdp = MivMatrixOrderdp(nV);
-
-      Xsigma = Mfpertvector(I, Mdp);
-      Overflow_Error = FALSE;
-
-      delete Mdp;
-      delete iv_dp;
+      {
+        pert_deg++;
+        target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
+        next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
+      }
+    }
+    for(i=0; i<nV; i++)
+    {
+      (*tmp_weight)[i] = (*curr_weight)[i];
+      (*curr_weight)[i] = (*next_weight)[i];
+    }
+    MivString(curr_weight, target_weight, tmp_weight);
+    newRing = VMrRefine(tmp_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
+    rChangeCurrRing(newRing); // change the ring to newRing
+    Gomega1 =  idrMoveR(Gomega, baseRing,currRing);
+    idDelete(&Gomega);
+    if(pert_deg >= nV)
+    {
+      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
+    }
+    else
+    {
+      M = idCopy(Mrwalk(idCopy(Gomega1), tmp_weight,curr_weight,weight_rad,pert_deg+1,currRing));
+    }
+    idSkipZeroes(M);
+#ifdef CHECK_IDEAL_MWALK
+    idString(M,"M");
+#endif
+    rChangeCurrRing(baseRing); //change ring to baseRing
+    M1 =  idrMoveR(M, newRing,currRing);
+    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
+    idDelete(&M);
+    idDelete(&Gomega1);
+    F = MLifttwoIdeal(Gomega2, M1, G);
+    idDelete(&Gomega2);
+    idSkipZeroes(F);
+#ifdef CHECK_IDEAL_MWALK
+    idString(F,"F");
+#endif
+    rChangeCurrRing(newRing); // change the ring to newRing
+    G = idrMoveR(F,baseRing,currRing);
+    idDelete(&F);
+    baseRing = currRing;
+    if(MivComp(next_weight, ivNull) == 1)
+    {
+      delete next_weight;
       break;
     }
   }
-  idDelete(&Gw);
-#endif
-
-  ideal I1;
-  intvec* Mlp;
-  Xivlp = Mivlp(nV);
-
-  if(MivComp(ivtarget, Xivlp)  != 1)
-  {
-    if (rParameter(currRing) != NULL)
-      DefRingPar(ivtarget);
-    else
-      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);
-  }
-  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
-    VMrDefault(ivstart);
-
-  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 Mfrwalk(ideal G, intvec* ivstart, intvec* ivtarget,int weight_rad)
-{
-  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
-      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);
-  }
-  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
-    VMrDefault(ivstart);
-
-  I = idrMoveR(I1,tRing,currRing);
-  to=clock();
-  ideal J = MstdCC(I);
-  idDelete(&I);
-  xftostd=xftostd+clock()-to;
-
-  ideal resF;
-  ring helpRing = currRing;
-  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);
+  delete next_weight;
+  if(test_w_in_ConeCC(G, orig_target_weight) != 1)
+  {
+    newRing = VMrDefault(orig_target_weight);  //define a new ring with ordering "(a(target_weight),lp)
+    rChangeCurrRing(newRing);
+    G = idrMoveR(G,baseRing,currRing);
+    G = idCopy(Mrwalk(idCopy(G), tmp_weight,orig_target_weight,weight_rad,pert_deg,currRing));
+    idSkipZeroes(G);
+    baseRing = currRing;
+  }
+  ENDE:
+  rChangeCurrRing(XXRing);
+  G = idrMoveR(G,baseRing,currRing);
+  delete tmp_weight;
+  delete ivNull;
+#ifdef TIME_TEST
+  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
+#endif
+  return(G);
 }
 
@@ -6757 +5821 @@
   TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
 
-  Print("\n// pSetm_Error = (%d)", ErrorCheck());
+ // Print("\n// pSetm_Error = (%d)", ErrorCheck());
   Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
 #endif
@@ -6764 +5828 @@
 }
 
-/*******************************************************
- * Tran's algorithm with random element                *
- *                                                     *
- * use kStd, if nP = 0, else call Ab_Rec_Pert (LastGB) *
- *******************************************************/
-ideal TranMrImprovwalk(ideal G,intvec* curr_weight,intvec* target_tmp, int nP, int weight_rad, int pert_deg)
-{
-#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 weight_norm, 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
-    {
-      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
-    {
-      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 with ordering "(a(curr_weight),lp)
-    if (rParameter(currRing) != NULL)
-    {
-      DefRingPar(curr_weight);
-    }
-    else
-    {
-      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
-    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);
-    next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, pert_deg);
-/*
-    next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
-
-    if(MivComp(next_weight, target_weight) != 1)
-    {
-      // compute a perturbed next weight vector "next_weight1"
-      intvec* next_weight1 = MkInterRedNextWeight(MPertVectors(G, MivMatrixOrder(curr_weight), pert_deg), target_weight, G);
-
-      // compare next_weight and next_weight1
-      ideal G_test = MwalkInitialForm(G, next_weight);
-      ideal G_test1 = MwalkInitialForm(G, next_weight1);
-      if(IDELEMS(G_test1) <= IDELEMS(G_test))
-      {
-        next_weight = ivCopy(next_weight1);
-      }
-      delete next_weight1;
-      // compute a random next weight vector "next_weight2"
-      intvec* next_weight22 = ivCopy(target_weight);
-      // Print("\n//  size of target_weight  = %d", sizeof((*target_weight)));
-      k = 0;
-
-      while(test_w_in_ConeCC(G, next_weight22) == 0 && k < 11)
-      {
-        k++;
-        if(k>10)
-        {
-          break;
-        }
-        weight_norm = 0;
-        while(weight_norm == 0)
-        {
-          for(i=nV-1; i>=0; i--)
-          {
-            // Print("\n//  next_weight[%d]  = %d", i, (*next_weight)[i]);
-            (*next_weight22)[i] = rand() % 60000 - 30000;
-            weight_norm = weight_norm + (*next_weight22)[i]*(*next_weight22)[i];
-          }
-          weight_norm = 1 + floor(sqrt(weight_norm));
-        }
-        for(i=nV-1; i>=0; i--)
-        {
-          if((*next_weight22)[i] < 0)
-          {
-            (*next_weight22)[i] = 1 + (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
-          }
-          else
-          {
-            (*next_weight22)[i] = (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
-          }
-          // Print("\n//  next_weight22[%d]  = %d", i, (*next_weight22)[i]);
-        }
-      }
-
-      if(test_w_in_ConeCC(G, next_weight22) == 1)
-      {
-        // compare next_weight and next_weight2
-        // Print("\n// ZUFALL IM KEGEL");
-        intvec* next_weight2 = MkInterRedNextWeight(next_weight22, target_weight, G);
-
-        ideal G_test2 = MwalkInitialForm(G, next_weight2);
-        if(IDELEMS(G_test2) <= IDELEMS(G_test))
-        {
-          if(IDELEMS(G_test2) <= IDELEMS(G_test1))
-          {
-             // Print("\n// ZUFALL BENUTZT!\n");
-            next_weight = ivCopy(next_weight2);
-          }
-        }
-        idDelete(&G_test2);
-        delete next_weight2;
-      }
-      delete next_weight22;
-      idDelete(&G_test);
-      idDelete(&G_test1);
-    }*/
-
-    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
-        {
-          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
-        {
-          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;
-  } // end of 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);
-}
 
 
@@ -7544 +6089 @@
  * Implementation of the first alternative Groebner Walk Algorithm *
  *******************************************************************/
-ideal MAltwalk1(ideal Go, int op_deg, int tp_deg, intvec* curr_weight,
-                intvec* target_weight)
+ideal MAltwalk1(ideal Go, int op_deg, int tp_deg, intvec* curr_weight, intvec* target_weight)
 {
   Set_Error(FALSE  );
@@ -7552 +6096 @@
   BOOLEAN nOverflow_Error = FALSE;
 #endif
-  // Print("// pSetm_Error = (%d)", ErrorCheck());
-
   xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
   xftinput = clock();
@@ -7593 +6135 @@
     if(Overflow_Error == FALSE)
     {
-      if(MivComp(curr_weight, iv_dp) == 1)
-      {
-      //rOrdStr(currRing) = "dp"
+      if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) = "dp"
+      {
         if(op_tmp == op_deg)
         {
@@ -7660 +6201 @@
     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)
@@ -7782 +6312 @@
 #endif
         tproc = clock()-xftinput;
-
-        //Print("\n//  main routine takes %d steps and calls \"Mpwalk\" (1,%d):", nwalk,  tp_deg);
-
+        
+        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);
@@ -7818 +6348 @@
   TimeStringFractal(xftinput, tostd, xtif, xtstd,xtextra, xtlift, xtred, xtnw);
 
-  Print("\n// pSetm_Error = (%d)", ErrorCheck());
+  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
   Print("\n// Overflow_Error? (%d)", Overflow_Error);
   Print("\n// Awalk1 took %d steps.\n", nstep);

Singular/walk.h

@@ -24 +24 @@
 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* 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* Mfpertvector(ideal G, intvec* iv);  
 intvec* MivUnit(int nV);
 
-intvec* MivWeightOrderlp(intvec* ivstart);
-intvec* MivWeightOrderdp(intvec* ivstart);
+intvec* MivWeightOrderlp(intvec* ivstart);  
+intvec* MivWeightOrderdp(intvec* ivstart);  
 
-ideal MidLift(ideal Gomega, ideal M);
+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);
+ideal MLiftLmalGNew(ideal Gomega, ideal M, ideal G);  
+ideal MLiftLmalGMin(ideal L, ideal G);  
 
 
@@ -52 +52 @@
 
 /* Okt -- Nov'01 */
-// compute a Groebner basis of an ideal G w.r.t. lexicographic order
-ideal Mwalk(ideal G, intvec* curr_weight, intvec* target_weight);
-
+// compute a Groebner basis of an ideal G w.r.t. lexicographic order 
+ideal Mwalk(ideal Go, intvec* orig_M, intvec* target_M, ring baseRing);
 // random walk algorithm to compute a Groebner basis
-ideal Mrwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int pert_deg);
+ideal Mrwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int pert_deg, ring baseRing);
 
 /* the perturbation walk algorithm */
-ideal Mpwalk(ideal G,int op,int tp,intvec* curr_weight,intvec* target_weight, int nP);
+
+ideal Mpwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int op_deg, int tp_deg, ring baseRing);
+/* the perturbation walk algorithm with random element */
+
+ideal Mprwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int op_deg, int tp_deg, ring baseRing);
 
 /* The fractal walk algorithm */
-ideal Mfwalk(ideal G, intvec* ivstart, intvec* ivtarget);
+ideal Mfwalk(ideal Go, intvec* curr_weight, intvec* orig_target_weight, int pert_deg, ring XXRing);
 
 /* The fractal walk algorithm with random element */
-ideal Mfrwalk(ideal G, intvec* ivstart, intvec* ivtarget,int weight_rad);
+ideal Mfrwalk(ideal Go, intvec* curr_weight, intvec* orig_target_weight, int pert_deg, int weight_rad, ring baseRing);
 
 /* Implement Tran's idea */
@@ -75 +78 @@
 
 /* the first alternative algorithm */
-ideal MAltwalk1(ideal G,int op,int tp,intvec* curr_weight,intvec* target_weight);
+ideal MAltwalk1(ideal G,int op,int tp,intvec* curr_weight,intvec* target_weight); 
 
 /* the second alternative algorithm */
-ideal MAltwalk2(ideal G, intvec* curr_weight, intvec* target_weight);
+ideal MAltwalk2(ideal G, intvec* curr_weight, intvec* target_weight); 
 
 #endif  //WALK_H