Changeset ffd4a9 in git


Ignore:
Timestamp:
Jul 29, 2014, 2:00:54 PM (10 years ago)
Author:
Stephan Oberfranz <oberfran@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '8a337797cc4177aa8747d661d5c4214ea2095dac')
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:
6 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/modwalk.lib

    • Property mode changed from 100644 to 100755
    rc311064 rffd4a9  
    8282
    8383//-------------------------  make i homogeneous  -----------------------------
    84 
    85   if(!hasMixedOrdering() && !h)
     84/*  if(!mixedTest() && !h)
    8685  {
    8786    if(!((find(ordstr_R0, "M") > 0) || (find(ordstr_R0, "a") > 0) || neg))
     
    106105    }
    107106  }
    108 
     107*/
    109108//-------------------------  compute a standard basis mod p  -----------------------------
    110109
     
    147146    if(size(#) == 2)
    148147    {
    149       trwalk(i,radius,pert_deg,#);
     148      i=fwalk(i,#);
    150149    }
    151150    else
    152151    {
    153       trwalk(i,radius,pert_deg);
    154     }
    155   }
    156   if(!hasMixedOrdering() && !h)
     152      i=fwalk(i);
     153    }
     154  }
     155  if(variant == 5)
     156  {
     157    if(size(#) == 2)
     158    {
     159     i=prwalk(i,radius,pert_deg,pert_deg,#);
     160    }
     161    else
     162    {
     163      i=prwalk(i,radius,pert_deg,pert_deg);
     164    }
     165  }
     166  if(variant == 6)
     167  {
     168    if(size(#) == 2)
     169    {
     170      i=pwalk(i,pert_deg,pert_deg,#);
     171    }
     172    else
     173    {
     174      i=pwalk(i,pert_deg,pert_deg);
     175    }
     176  }
     177  /*
     178  if(!mixedTest() && !h)
    157179  {
    158180    if(!((find(ordstr_R0, "M") > 0) || (find(ordstr_R0, "a") > 0) || neg))
     
    168190      }
    169191    }
    170   }
     192  }*/
    171193  setring R0;
    172194  return(list(fetch(@r,i),p));
     
    180202  intvec a = 2,1,3,4;
    181203  intvec b = 1,9,1,1;
    182   ring ra = 0,(w,x,y,z),(a(a),lp);
     204  ring ra = 0,x(1..4),(a(a),lp);
    183205  ideal I = std(cyclic(4));
    184   ring rb = 0,(w,x,y,z),(a(b),lp);
     206  ring rb = 0,x(1..4),(a(b),lp);
    185207  ideal I = imap(ra,I);
    186208  modpWalk(I,p,1,a,b);
     
    214236proc modWalk(def II, int variant, list #)
    215237"USAGE:  modWalk(II); II ideal or list(ideal,int)
    216 ASSUME:  If variant = 1 the random walk algorithm with radius II[2] is applied
    217          to II[1] if II = list(ideal, int). It is applied to II with radius 2
    218          if II is an ideal. If variant = 2, the Groebner walk algorithm is
    219          applied to II[1] or to II, respectively.
     238ASSUME:  If variant =
     239@*       - 1 the Random Walk algorithm with radius II[2] is applied
     240           to II[1] if II = list(ideal, int). It is applied to II with radius 2
     241           if II is an ideal.
     242@*       - 2, the Groebner Walk algorithm is applied to II[1] or to II, respectively.
     243@*       - 3, the Fractal Walk algorithm with random element is applied to II[1] or II,
     244           respectively.
     245@*       - 4, the Fractal Walk algorithm is applied to II[1] or II, respectively.
     246@*       - 5, the Perturbation Walk algorithm with random element is applied to II[1]
     247           or II, respectively, with radius II[3] and perturbation degree II[2].
     248@*       - 6, the Perturbation Walk algorithm is applied to II[1] or II, respectively,
     249           with perturbation degree II[3].
    220250         If size(#) > 0, then # contains either 1, 2 or 4 integers such that
    221251@*       - #[1] is the number of available processors for the computation,
     
    468498//-------------------------  Save current options  -----------------------------
    469499  intvec opt = option(get);
    470   option(redSB);
     500  //option(redSB);
    471501
    472502//--------------------  Initialize the list of primes  -------------------------
     
    527557    }
    528558    H = chinrem(T1,T2);
    529     //J = parallelFarey(H,N,n1);
    530     J=farey(H,N);
     559    J = parallelFarey(H,N,n1);
     560    //J=farey(H,N);
    531561    if(printlevel >= 10)
    532562    {
     
    538568
    539569    tt = timer; rt = rtimer;
    540     //pTest = pTestSB(I,J,L,variant);
    541     pTest = primeTestSB(I,J,L,variant);
     570    pTest = pTestSB(I,J,L,variant);
     571    //pTest = primeTestSB(I,J,L,variant);
    542572    if(printlevel >= 10)
    543573    {
     
    593623    tt = timer; rt = rtimer;
    594624    L = primeList(I,n3,L,n1);
    595 L;
    596625    if(printlevel >= 10)
    597626    {
     
    644673  ideal I=-x+y2z-z,xz+1,x2+y2-1;
    645674  // I is a standard basis in dp
    646   modWalk(I,1);
    647   modWalk(I,2,2,0);
     675  ideal J = modWalk(I,1);
     676  J;
     677/*  modWalk(I,2,2,0);
    648678  modWalk(I,3,system("cpu"),0);
    649679  std(I);
     
    654684  ideal i=fetch(r0,i0);
    655685  modWalk(i,1,system("cpu"),0);
    656   modWalk(i,3);
     686  modWalk(i,3);*/
    657687}
    658688
  • Singular/LIB/rwalk.lib

    • Property mode changed from 100644 to 100755
    rc311064 rffd4a9  
    1 /////////////////////////////////////////////////
    2 version="version rwalk.lib 4.0.0.0 Jun_2013 "; // $Id$
     1<<<<<<< HEAD
     2=======
     3//
     4>>>>>>> 92644b759d66f085c842e4284d78c2e203291b67
     5version="$Id$";
    36category="Commutative Algebra";
    47
     
    1417 * Argument string for Random Walk *
    1518 ***********************************/
    16 static proc OrderStringalp_NP(string Wpal,list #)
     19proc OrderStringalp_NP(string Wpal,list #)
    1720{
    1821  int n= nvars(basering);
     
    3538        if(Wpal == "al"){
    3639          order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
     40        }
     41        if(Wpal == "M"){
     42          order_str = "(M("+string(#[1])+"),C)";
    3743        }
    3844        else {
     
    6167           order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
    6268         }
     69         if(Wpal == "M"){
     70          order_str = "(M("+string(#[1])+"),C)";
     71         }
    6372         else {
    6473           order_str = "(Wp("+string(#[1])+"),C)";
     
    7382             order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
    7483           }
     84           if(Wpal == "M"){
     85             order_str = "(M("+string(#[1])+"),C)";
     86           }
    7587           else {
    7688             order_str = "(Wp("+string(#[1])+"),C)";
     89           //  order_str = "(a("+string(#[1])+"),C)";
    7790           }
    7891         }
     
    95108             order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
    96109           }
     110           if(Wpal == "M"){
     111             order_str = "(M("+string(#[1])+"),C)";
     112           }
    97113           else {
    98114             order_str = "(Wp("+string(#[1])+"),C)";
     
    122138}
    123139
    124 /************************************
    125  * Random Walk with perturbation    *
    126  ************************************/
     140/****************
     141 * Random Walk *
     142 ****************/
    127143proc rwalk(ideal Go, int radius, int pert_deg, list #)
    128144"SYNTAX: rwalk(ideal i, int radius);
    129          rwalk(ideal i, int radius, intvec v, intvec w);
     145         if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w);
    130146TYPE:    ideal
    131147PURPOSE: compute the standard basis of the ideal, calculated via
     
    138154{
    139155//--------------------  Initialize parameters  ------------------------
    140 list OSCTW = OrderStringalp_NP("al", #);
     156int n= nvars(basering);
     157list OSCTW = OrderStringalp_NP("al",#);
     158if(size(#)>1)
     159  {
     160  if(size(#[2]) == n*n)
     161    {
     162    OSCTW= OrderStringalp_NP("M", #);
     163    }
     164  }
     165else
     166  {
     167  OSCTW= OrderStringalp_NP("al", #);
     168  }
    141169string ord_str = OSCTW[2];
    142170intvec curr_weight = OSCTW[3]; // original weight vector
    143171intvec target_weight = OSCTW[4]; // target weight vector
    144172kill OSCTW;
    145 option(redSB);
    146173
    147174//--------------------  Initialize parameters  ------------------------
    148175def xR = basering;
    149 execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
     176execute("ring ostR = "+charstr(xR)+",("+varstr(xR)+"),"+ord_str+";");
    150177def old_ring = basering;
    151178
    152179ideal G = fetch(xR, Go);
    153 G = system("Mrwalk", G, curr_weight, target_weight, radius, pert_deg);
     180G = system("Mrwalk", G, curr_weight, target_weight, radius, pert_deg, basering);
    154181
    155182setring xR;
     
    170197  int perturb_deg = 2;
    171198  rwalk(I,radius,perturb_deg);
     199}
     200
     201/*****************************************
     202 * Perturbation Walk with random element *
     203 *****************************************/
     204proc prwalk(ideal Go, int radius, int o_pert_deg, int t_pert_deg, list #)
     205"SYNTAX: rwalk(ideal i, int radius);
     206         if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w);
     207TYPE:    ideal
     208PURPOSE: compute the standard basis of the ideal, calculated via
     209         the Random walk algorithm  from the ordering
     210         \"(a(v),lp)\", \"dp\" or \"Dp\"
     211         to the ordering  \"(a(w),lp)\" or \"(a(1,0,...,0),lp)\".
     212SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, twalk, awalk1, awalk2
     213KEYWORDS: Groebner walk
     214EXAMPLE: example rwalk; shows an example"
     215{
     216//--------------------  Initialize parameters  ------------------------
     217list OSCTW = OrderStringalp_NP("al", #);
     218string ord_str = OSCTW[2];
     219intvec curr_weight = OSCTW[3]; // original weight vector
     220intvec target_weight = OSCTW[4]; // target weight vector
     221kill OSCTW;
     222
     223//--------------------  Initialize parameters  ------------------------
     224def xR = basering;
     225execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
     226def old_ring = basering;
     227
     228ideal G = fetch(xR, Go);
     229G = system("Mprwalk", G, curr_weight, target_weight, radius, o_pert_deg, t_pert_deg, basering);
     230
     231setring xR;
     232kill Go;
     233
     234keepring basering;
     235ideal result = fetch(old_ring, G);
     236attrib(result,"isSB",1);
     237return (result);
     238}
     239example
     240{
     241  "EXAMPLE:"; echo = 2;
     242  // compute a Groebner basis of I w.r.t. lp.
     243  ring r = 32003,(z,y,x), lp;
     244  ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z;
     245  int radius = 1;
     246  int o_perturb_deg = 2;
     247  int t_perturb_deg = 2;
     248  prwalk(I,radius,o_perturb_deg,t_perturb_deg);
    172249}
    173250
     
    190267
    191268   string ord_str =   OSCTW[2];
    192    intvec curr_weight   =   OSCTW[3]; /* original weight vector */
     269   intvec curr_weight   =   OSCTW[3]; /* current weight vector */
    193270   intvec target_weight =   OSCTW[4]; /* target weight vector */
    194271   kill OSCTW;
    195    option(redSB);
    196272   def xR = basering;
    197273
     
    200276   //print("//** help ring = " + string(basering));
    201277   ideal G = fetch(xR, Go);
    202 
    203    G = system("Mfrwalk", G, curr_weight, target_weight, radius);
     278   int pert_deg = 2;
     279   G = system("Mfrwalk", G, curr_weight, target_weight, pert_deg, radius, basering);
    204280
    205281   setring xR;
     
    242318  kill L;
    243319
    244   option(redSB);
    245320  def xR = basering;
    246321
  • Singular/LIB/swalk.lib

    • Property mode changed from 100644 to 100755
    rc311064 rffd4a9  
    2323
    2424LIB "sagbi.lib";
     25LIB "crypto.lib";
     26LIB "atkins.lib";
     27LIB "random.lib";
    2528//////////////////////////////////////////////////////////////////////////////
    2629proc swalk(ideal Gox, list #)
    2730"USAGE:  swalk(i[,v,w]); i ideal, v,w int vectors
     31RETURN: The sagbi basis of the subalgebra defined by the generators of i,
     32        calculated via the Sagbi walk algorithm from the ordering dp to lp
     33        if v,w are not given (resp. from the ordering (a(v),lp) to the
     34        ordering (a(w),lp) if v and w are given).
     35EXAMPLE: example swalk; shows an example
     36"
     37{
     38  /* we use ring with ordering (a(...),lp,C) */
     39  list OSCTW    = OrderStringalp_NP("al", #);//"dp"
     40  string ord_str =   OSCTW[2];
     41  intvec icurr_weight   =   OSCTW[3]; /* original weight vector */
     42  intvec itarget_weight =   OSCTW[4]; /* terget weight vector */
     43  kill OSCTW;
     44      option(redSB);
     45  def xR = basering;
     46  list rl=ringlist(xR);
     47  if(size(#) == 0)
     48  {
     49    rl[3][1][1]="dp";
     50  }
     51  def ostR=ring(rl);
     52  setring ostR;
     53  def new_ring = basering;
     54  ideal Gnew = fetch(xR, Gox);
     55  Gnew=sagbi(Gnew,1);
     56  Gnew=interreduceSd(Gnew);
     57  vector curr_weight=changeTypeInt(icurr_weight);
     58  vector target_weight=changeTypeInt(itarget_weight);
     59  curr_weight;
     60  ideal Gold;
     61  list l;
     62  intvec v;
     63  int n=0;
     64  while(n==0)
     65    {
     66       Gold=Gnew;
     67       def old_ring=new_ring;
     68       setring old_ring;
     69       number ulast;
     70       kill new_ring;
     71       if(curr_weight==target_weight){n=1;}
     72       else {
     73              l=collectDiffExpo(Gold);
     74              ulast=last(curr_weight, target_weight, l);
     75              vector new_weight=(1-ulast)*curr_weight+ulast*target_weight;
     76              vector w=cleardenom(new_weight);
     77              v=changeType(w);
     78              list p= ringlist(old_ring);
     79              p[3][1][2]= v;
     80              def new_ring=ring(p);
     81              setring new_ring;
     82              ideal Gold=fetch(old_ring,Gold);
     83              vector curr_weight=fetch(old_ring,new_weight);
     84              vector target_weight=fetch(old_ring,target_weight);
     85              kill old_ring;
     86              ideal Gnew=Convert(Gold);
     87              Gnew=interreduceSd(Gnew);
     88         }
     89    }
     90   setring xR;
     91   ideal result = fetch(old_ring, Gnew);
     92   kill old_ring;
     93   attrib(result,"isSB",1);
     94   return (result);
     95}
     96example
     97{
     98  "EXAMPLE:";echo = 2;
     99  ring r = 0,(x,y), lp;
     100  ideal I =x2,y2,xy+y,2xy2+y3;
     101  swalk(I);
     102}
     103//////////////////////////////////////////////////////////////////////////////
     104proc rswalk(ideal Gox, int weight_rad, int pdeg, list #)
     105"USAGE:  rswalk(i[,v,w]); i ideal, v,w int vectors
    28106RETURN: The sagbi basis of the subalgebra defined by the generators of i,
    29107        calculated via the Sagbi walk algorithm from the ordering dp to lp
     
    60138       def old_ring=new_ring;
    61139       setring old_ring;
    62        number ulast;
     140       
    63141       kill new_ring;
    64142       if(curr_weight==target_weight){n=1;}
    65143       else {
    66               l=collectDiffExpo(Gold);
    67               ulast=last(curr_weight, target_weight, l);
    68               vector new_weight=(1-ulast)*curr_weight+ulast*target_weight;
     144              l=collectDiffExpo(Gold);
     145              vector new_weight=RandomNextWeight(Gold, l, curr_weight, target_weight, weight_rad, pdeg);
    69146              vector w=cleardenom(new_weight);
    70147              v=changeType(w);
     
    91168  ring r = 0,(x,y), lp;
    92169  ideal I =x2,y2,xy+y,2xy2+y3;
    93   swalk(I);
    94 }
    95 
     170  swalk(I,7);
     171}
    96172//////////////////////////////////////////////////////////////////////////////
    97173static proc inprod(vector v,vector w)
     
    211287
    212288//////////////////////////////////////////////////////////////////////////////
     289static proc test_in_cone(vector w, list l)
     290{
     291 int i,j,k;
     292 vector v;
     293 poly n;
     294 number a;
     295 for(i=1;i<=size(l);i++)
     296 {
     297    for(j=1;j<=size(l[i]);j++)
     298    {
     299        v=0;
     300        for(k=1;k<=size(l[i][j]);k++)
     301        {
     302            v=v+l[i][j][k]*gen(k);
     303        }
     304        n = inprod(w,v);
     305        a = leadcoef(n);
     306        if(a<0)
     307        {
     308           return(0);
     309        }
     310    }
     311 }
     312 return(1);
     313}
     314
     315
     316//////////////////////////////////////////////////////////////////////////////
    213317static proc last( vector c, vector t,list l)
    214318"USAGE: last(c,t,l); c,t vectors, l list
     
    221325 number ul=1;
    222326 int i,j,k;
    223  number u;
     327 number a,b,z,u;
     328 poly n,q;
    224329 vector v;
    225330 for(i=1;i<=size(l);i++)
     
    232337            v=v+l[i][j][k]*gen(k);
    233338        }
    234         poly n= inprod(c,v);
    235         poly q= inprod(t,v);
    236         number a=leadcoef(n);
    237         number b=leadcoef(q);
    238         number z=a-b;
     339        n= inprod(c,v);
     340        q= inprod(t,v);
     341        a=leadcoef(n);
     342        b=leadcoef(q);
     343        z=a-b;
    239344        if(b<0)
    240         {
     345            {
    241346            u=a/z;
    242             if(u<ul) {ul=u;}
    243         }
    244         kill a,b,z,n,q ;
    245     }
    246  }
     347            if(u<ul)
     348            {
     349               ul=u;
     350             }
     351        }
     352    }
     353 }~
     354 kill a,b,z,n,q,u;
    247355 return(ul);
    248356}
     
    340448   Lift(In,InG,Gold);
    341449}
     450//////////////////////////////////////////////////////////////////////////////
     451static proc PertVectors(ideal Gold, vector target_weight, int pdeg)
     452{
     453int nV = nvars(basering);
     454int nG = size(Gold);
     455int i;
     456number ntemp, maxAi, maxA;
     457if(pdeg > nV || pdeg <= 0)
     458  {
     459    intvec v_null=0;
     460    return v_null;
     461  }
     462if(pdeg == 1)
     463  {
     464    return target_weight;
     465  }
     466maxAi=0;
     467for(i=1; i<=nV; i++)
     468  {
     469    ntemp = leadcoef(inprod(target_weight,gen(i)));
     470    if(ntemp < 0)
     471      {
     472        ntemp = -ntemp;
     473      }
     474    if(maxAi < ntemp)
     475      {
     476        maxAi = ntemp;
     477      }
     478  }
     479maxA = maxAi+pdeg-1;
     480number epsilon = maxA*deg(Gold)+1;
     481vector pert_weight = epsilon^(pdeg-1)*target_weight;
     482for(i=2; i<=pdeg; i++)
     483  {
     484    pert_weight = pert_weight + epsilon^(pdeg-i)*gen(i);
     485  }
     486return(pert_weight);
     487}
     488
     489
     490//////////////////////////////////////////////////////////////////////////////
     491static proc RandomNextWeight(ideal Gold, list L, vector curr_weight, vector target_weight,int weight_rad, int pdeg)
     492"USAGE: RandomNextWeight(Gold, L, curr_weight, target_weight);
     493RETURN: Intermediate next weight vector
     494EXAMPLE: example RandomNextWeight; shows an example
     495"
     496{
     497  int i,n1,n2,n3;
     498  number norm, weight_norm;
     499  def Rold = basering;
     500  int nV = nvars(basering);
     501  number ulast=last(curr_weight, target_weight, L);
     502  vector new_weight=(1-ulast)*curr_weight+ulast*target_weight;
     503  vector w1=cleardenom(new_weight);
     504  intvec v1=changeType(w1);
     505  list p= ringlist(Rold);
     506  p[3][1][2]= v1;
     507  def new_ring=ring(p);
     508  setring new_ring;
     509  ideal Gold = fetch(Rold, Gold);
     510  n1=size(Initial(Gold));
     511  setring Rold;
     512  intvec next_weight;
     513  kill new_ring;
     514  while(1)
     515  {
     516    weight_norm = 0;
     517    while(weight_norm == 0)
     518    {
     519      for(i=1; i<=nV; i++)
     520      {
     521        next_weight[i] = random(1,10000)-5000;
     522        weight_norm = weight_norm + next_weight[i]^2;
     523      }
     524      norm = 0;
     525      while(norm^2 < weight_norm)
     526      {
     527         norm=norm+1;
     528      }
     529      weight_norm = 1+norm;
     530    }
     531    new_weight = 0;
     532    for(i=1; i<=nV;i++)
     533    {
     534      if(next_weight[i] < 0)
     535      {
     536        new_weight = new_weight + (1 + round(weight_rad*leadcoef(next_weight[i])/weight_norm))*gen(i);
     537      }
     538      else
     539      {
     540        new_weight = new_weight + ( round(weight_rad*leadcoef(next_weight[i])/weight_norm))*gen(i);
     541      }
     542    }
     543    new_weight = new_weight + curr_weight;
     544    if(test_in_cone(new_weight, L)==1)
     545    {
     546      break;
     547    }
     548  }
     549  kill next_weight;
     550  kill norm;
     551  vector w2=cleardenom(new_weight);
     552  intvec v2=changeType(w2);
     553  p[3][1][2]= v2;
     554  def new_ring=ring(p);
     555  setring new_ring;
     556  ideal Gold = fetch(Rold, Gold);
     557  n2=size(Initial(Gold));
     558  setring Rold;
     559  kill new_ring;
     560
     561  vector w3=cleardenom(PertVectors(Gold,target_weight,pdeg));
     562  intvec v3=changeType(w3);
     563  p[3][1][2]= v1;
     564  def new_ring=ring(p);
     565  setring new_ring;
     566  ideal Gold = fetch(Rold, Gold);
     567  n3=size(Initial(Gold));
     568  setring Rold;
     569  kill new_ring;
     570  kill p;
     571
     572  if(n2<n1)
     573  {
     574    if(n3<n2)
     575    {
     576      // n3<n2<n1
     577      return(w3);
     578    }
     579    else
     580    {
     581      // n2<n1 und n2<=n3
     582      return(w2);
     583    }
     584  }
     585  else
     586  {
     587    if(n3<n1)
     588    {
     589      //n3<n1<=n2
     590      return(w3);
     591    }
     592    else
     593    {
     594      // n1<=n3 und n1<=n2
     595      return(w1);
     596    }
     597  }
     598}
    342599
    343600//////////////////////////////////////////////////////////////////////////////
     
    349606{
    350607 ideal In=Initial(Gold);
    351  ideal InG=sagbi(In,1)+In;
     608 ideal InG=sagbi(In); //+In;
    352609 ideal Gnew=Lift(In,InG,Gold);
    353610 return(Gnew);
     
    380637     for(i=1;i<=size(M);i++)
    381638     { B[i]=M[i];}
    382      f=sagbiNF(f,B,1);
     639     f=sagbiNF(f,B,1)[1];
    383640     J=J+f;
    384641  }
     
    598855
    599856///////////////////////////////////////////////////////////////////////////////*
    600 Further examples
     857/*Further examples
    601858ring r=0,(x,y,z),lp;
    602859
  • Singular/extra.cc

    • Property mode changed from 100644 to 100755
    rc311064 rffd4a9  
    88#define HAVE_WALK 1
    99
    10 
    11 
    12 
     10#ifdef HAVE_CONFIG_H
     11#include "singularconfig.h"
     12#endif /* HAVE_CONFIG_H */
    1313#include <kernel/mod2.h>
    1414#include <misc/auxiliary.h>
    15 #include <misc/sirandom.h>
    16 
     15
     16#define SI_DONT_HAVE_GLOBAL_VARS
    1717#include <factory/factory.h>
    1818
     
    5555
    5656
    57 #include <resources/feResource.h>
    5857#include <polys/monomials/ring.h>
    5958#include <kernel/polys.h>
     
    6968#include <kernel/fast_mult.h>
    7069#include <kernel/digitech.h>
    71 #include <kernel/GBEngine/stairc.h>
     70#include <kernel/stairc.h>
     71#include <kernel/febase.h>
    7272#include <kernel/ideals.h>
    73 #include <kernel/GBEngine/kstd1.h>
    74 #include <kernel/GBEngine/syz.h>
    75 #include <kernel/GBEngine/kutil.h>
    76 
    77 #include <kernel/GBEngine/shiftgb.h>
    78 #include <kernel/linear_algebra/linearAlgebra.h>
    79 
    80 #include <kernel/combinatorics/hutil.h>
     73#include <kernel/kstd1.h>
     74#include <kernel/syz.h>
     75#include <kernel/kutil.h>
     76
     77#include <kernel/shiftgb.h>
     78#include <kernel/linearAlgebra.h>
    8179
    8280// for tests of t-rep-GB
    83 #include <kernel/GBEngine/tgb.h>
    84 
    85 #include <kernel/linear_algebra/minpoly.h>
    86 
    87 #include <numeric/mpr_base.h>
     81#include <kernel/tgb.h>
     82
    8883
    8984#include "tok.h"
     
    9792#include "distrib.h"
    9893
     94#include "minpoly.h"
    9995#include "misc_ip.h"
    10096
     
    109105
    110106#ifdef HAVE_RINGS
    111 #include <kernel/GBEngine/ringgb.h>
     107#include <kernel/ringgb.h>
    112108#endif
    113109
    114110#ifdef HAVE_F5
    115 #include <kernel/GBEngine/f5gb.h>
     111#include <kernel/f5gb.h>
    116112#endif
    117113
     
    122118
    123119#ifdef HAVE_SPECTRUM
    124 #include <kernel/spectrum/spectrum.h>
     120#include <kernel/spectrum.h>
    125121#endif
    126122
     
    129125#include <polys/nc/ncSAMult.h> // for CMultiplier etc classes
    130126#include <polys/nc/sca.h>
    131 #include <kernel/GBEngine/nc.h>
     127#include <kernel/nc.h>
    132128#include "ipconv.h"
    133129#ifdef HAVE_RATGRING
    134 #include <kernel/GBEngine/ratgring.h>
     130#include <kernel/ratgring.h>
    135131#endif
    136132#endif
     
    151147
    152148#include <polys/clapconv.h>
    153 #include <kernel/GBEngine/kstdfac.h>
     149#include <kernel/kstdfac.h>
    154150
    155151#include <polys/clapsing.h>
     
    189185static BOOLEAN jjEXTENDED_SYSTEM(leftv res, leftv h);
    190186#endif
     187
     188extern BOOLEAN jjJanetBasis(leftv res, leftv v);
    191189
    192190#ifdef ix86_Win  /* PySingular initialized? */
     
    19081906        if (h == NULL || h->Typ() != IDEAL_CMD ||
    19091907            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    1910             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
    1911         {
    1912           Werror("system(\"Mwalk\", ideal, intvec, intvec) expected");
    1913           return TRUE;
    1914         }
    1915 
    1916         if (((intvec*) h->next->Data())->length() != currRing->N &&
    1917             ((intvec*) h->next->next->Data())->length() != currRing->N )
    1918         {
    1919           Werror("system(\"Mwalk\" ...) intvecs not of length %d\n",
    1920                  currRing->N);
    1921           return TRUE;
    1922         }
     1908            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
     1909            h->next->next->next == NULL || h->next->next->next->Typ() != RING_CMD)
     1910        {
     1911          Werror("system(\"Mwalk\", ideal, intvec, intvec, ring) expected");
     1912          return TRUE;
     1913        }
     1914
     1915        if ((((intvec*) h->next->Data())->length() != currRing->N &&
     1916            ((intvec*) h->next->next->Data())->length() != currRing->N ) &&
     1917            (((intvec*) h->next->Data())->length() != (currRing->N)*(currRing->N) &&
     1918            ((intvec*) h->next->next->Data())->length() != (currRing->N)*(currRing->N) ))
     1919        {
     1920          Werror("system(\"Mwalk\" ...) intvecs not of length %d or %d\n",
     1921                 currRing->N,(currRing->N)*(currRing->N));
     1922          return TRUE;
     1923        }
    19231924        ideal arg1 = (ideal) h->Data();
    19241925        intvec* arg2 = (intvec*) h->next->Data();
    19251926        intvec* arg3   =  (intvec*) h->next->next->Data();
    1926 
    1927 
    1928         ideal result = (ideal) Mwalk(arg1, arg2, arg3);
     1927        ring arg4 = (ring) h->next->next->next->Data();
     1928
     1929        ideal result = (ideal) Mwalk(arg1, arg2, arg3, arg4);
    19291930
    19301931        res->rtyp = IDEAL_CMD;
     
    19751976      {
    19761977        if (h == NULL || h->Typ() != IDEAL_CMD ||
    1977             h->next == NULL || h->next->Typ() != INT_CMD ||
    1978             h->next->next == NULL || h->next->next->Typ() != INT_CMD ||
    1979             h->next->next->next == NULL ||
    1980               h->next->next->next->Typ() != INTVEC_CMD ||
    1981             h->next->next->next->next == NULL ||
    1982               h->next->next->next->next->Typ() != INTVEC_CMD||
    1983             h->next->next->next->next->next == NULL ||
    1984               h->next->next->next->next->next->Typ() != INT_CMD)
    1985         {
    1986           Werror("system(\"Mpwalk\", ideal, int, int, intvec, intvec, int) expected");
    1987           return TRUE;
    1988         }
    1989 
    1990         if (((intvec*) h->next->next->next->Data())->length() != currRing->N &&
    1991             ((intvec*) h->next->next->next->next->Data())->length()!=currRing->N)
    1992         {
    1993           Werror("system(\"Mpwalk\" ...) intvecs not of length %d\n",
    1994                  currRing->N);
     1978            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
     1979            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
     1980            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
     1981            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD||
     1982            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != RING_CMD)
     1983        {
     1984          Werror("system(\"Mpwalk\", ideal, intvec, intvec, int, int, ring) expected");
     1985          return TRUE;
     1986        }
     1987
     1988        if (((intvec*) h->next->Data())->length() != currRing->N &&
     1989            ((intvec*) h->next->next->Data())->length()!=currRing->N)
     1990        {
     1991          Werror("system(\"Mpwalk\" ...) intvecs not of length %d\n",currRing->N);
    19951992          return TRUE;
    19961993        }
    19971994        ideal arg1 = (ideal) h->Data();
    1998         int arg2 = (int) ((long)(h->next->Data()));
    1999         int arg3 = (int) ((long)(h->next->next->Data()));
    2000         intvec* arg4 = (intvec*) h->next->next->next->Data();
    2001         intvec* arg5   =  (intvec*) h->next->next->next->next->Data();
    2002         int arg6   =  (int) ((long)(h->next->next->next->next->next->Data()));
    2003 
     1995        intvec* arg2 = (intvec*) h->next->Data();
     1996        intvec* arg3 = (intvec*) h->next->next->Data();
     1997        int arg4 = (int) (long) h->next->next->next->Data();
     1998        int arg5 = (int) (long) h->next->next->next->next->Data();
     1999        ring arg6 = (ring) h->next->next->next->next->next->Data();
    20042000
    20052001        ideal result = (ideal) Mpwalk(arg1, arg2, arg3, arg4, arg5, arg6);
     
    20122008      else
    20132009      if (strcmp(sys_cmd, "Mrwalk") == 0)
    2014       { // Random Walk
     2010      {
    20152011        if (h == NULL || h->Typ() != IDEAL_CMD ||
    20162012            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    20172013            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
    20182014            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
    2019             h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD)
    2020         {
    2021           Werror("system(\"Mrwalk\", ideal, intvec, intvec, int, int) expected");
    2022           return TRUE;
    2023         }
    2024 
    2025         if (((intvec*) h->next->Data())->length() != currRing->N &&
    2026             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2027         {
    2028           Werror("system(\"Mrwalk\" ...) intvecs not of length %d\n",
    2029                  currRing->N);
     2015            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
     2016            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != RING_CMD)
     2017        {
     2018          Werror("system(\"Mrwalk\", ideal, intvec, intvec, int, int, ring) expected");
     2019          return TRUE;
     2020        }
     2021
     2022        if ((((intvec*) h->next->Data())->length() != currRing->N &&
     2023            ((intvec*) h->next->next->Data())->length() != currRing->N ) &&
     2024            (((intvec*) h->next->Data())->length() != (currRing->N)*(currRing->N) &&
     2025            ((intvec*) h->next->next->Data())->length() != (currRing->N)*(currRing->N) ))
     2026        {
     2027          Werror("system(\"Mrwalk\" ...) intvecs not of length %d or %d\n",
     2028                 currRing->N,(currRing->N)*(currRing->N));
    20302029          return TRUE;
    20312030        }
     
    20352034        int arg4 = (int)(long) h->next->next->next->Data();
    20362035        int arg5 = (int)(long) h->next->next->next->next->Data();
    2037 
    2038 
    2039         ideal result = (ideal) Mrwalk(arg1, arg2, arg3, arg4, arg5);
     2036        ring arg6 = (ring) h->next->next->next->next->next->Data();
     2037
     2038
     2039        ideal result = (ideal) Mrwalk(arg1, arg2, arg3, arg4, arg5, arg6);
    20402040
    20412041        res->rtyp = IDEAL_CMD;
     
    21182118        if (h == NULL || h->Typ() != IDEAL_CMD ||
    21192119            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    2120             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
    2121         {
    2122           Werror("system(\"Mfwalk\", ideal, intvec, intvec) expected");
    2123           return TRUE;
    2124         }
    2125 
     2120            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
     2121            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
     2122            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != RING_CMD)
     2123        {
     2124          Werror("system(\"Mfwalk\", ideal, intvec, intvec, int, ring) expected");
     2125          return TRUE;
     2126        }
    21262127        if (((intvec*) h->next->Data())->length() != currRing->N &&
    2127             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2128         {
    2129           Werror("system(\"Mfwalk\" ...) intvecs not of length %d\n",
    2130                  currRing->N);
    2131           return TRUE;
    2132         }
    2133         ideal arg1 = (ideal) h->Data();
    2134         intvec* arg2 = (intvec*) h->next->Data();
    2135         intvec* arg3   =  (intvec*) h->next->next->Data();
    2136 
    2137         ideal result = (ideal) Mfwalk(arg1, arg2, arg3);
     2128            ((intvec*) h->next->next->Data())->length() != currRing->N)
     2129        {
     2130          Werror("system(\"Mfwalk\" ...) intvecs not of length %d\n",currRing->N);
     2131          return TRUE;
     2132        }
     2133        ideal arg1      =       (ideal) h->Data();
     2134        intvec* arg2    =       (intvec*) h->next->Data();
     2135        intvec* arg3    =       (intvec*) h->next->next->Data();
     2136        int arg4        =       (int)(long) h->next->next->next->Data();
     2137        ring arg5       =       (ring) h->next->next->next->next->Data();
     2138        ideal result    =       (ideal) Mfwalk(arg1, arg2, arg3, arg4, arg5);
    21382139
    21392140        res->rtyp = IDEAL_CMD;
     
    21442145      else
    21452146      if (strcmp(sys_cmd, "Mfrwalk") == 0)
    2146       {
    2147         if (h == NULL || h->Typ() != IDEAL_CMD ||
    2148             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    2149             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
    2150             h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD)
    2151         {
    2152           Werror("system(\"Mfrwalk\", ideal, intvec, intvec, int) expected");
    2153           return TRUE;
    2154         }
    2155 
    2156         if (((intvec*) h->next->Data())->length() != currRing->N &&
    2157             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2158         {
    2159           Werror("system(\"Mfrwalk\" ...) intvecs not of length %d\n",
    2160                  currRing->N);
    2161           return TRUE;
    2162         }
    2163         ideal arg1 = (ideal) h->Data();
    2164         intvec* arg2 = (intvec*) h->next->Data();
    2165         intvec* arg3 = (intvec*) h->next->next->Data();
    2166         int arg4 = (int)(long) h->next->next->next->Data();
    2167 
    2168         ideal result = (ideal) Mfrwalk(arg1, arg2, arg3, arg4);
    2169 
    2170         res->rtyp = IDEAL_CMD;
    2171         res->data =  result;
    2172 
    2173         return FALSE;
    2174       }
    2175       else
    2176 
    2177   #ifdef TRAN_Orig
    2178       if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
    2179       {
    2180         if (h == NULL || h->Typ() != IDEAL_CMD ||
    2181             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    2182             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
    2183         {
    2184           Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec) expected");
    2185           return TRUE;
    2186         }
    2187 
    2188         if (((intvec*) h->next->Data())->length() != currRing->N &&
    2189             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2190         {
    2191           Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
    2192                  currRing->N);
    2193           return TRUE;
    2194         }
    2195         ideal arg1 = (ideal) h->Data();
    2196         intvec* arg2 = (intvec*) h->next->Data();
    2197         intvec* arg3   =  (intvec*) h->next->next->Data();
    2198 
    2199 
    2200         ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3);
    2201 
    2202         res->rtyp = IDEAL_CMD;
    2203         res->data =  result;
    2204 
    2205         return FALSE;
    2206       }
    2207       else
    2208   #endif
    2209       if (strcmp(sys_cmd, "MAltwalk2") == 0)
    2210         {
    2211         if (h == NULL || h->Typ() != IDEAL_CMD ||
    2212             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    2213             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
    2214         {
    2215           Werror("system(\"MAltwalk2\", ideal, intvec, intvec) expected");
    2216           return TRUE;
    2217         }
    2218 
    2219         if (((intvec*) h->next->Data())->length() != currRing->N &&
    2220             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2221         {
    2222           Werror("system(\"MAltwalk2\" ...) intvecs not of length %d\n",
    2223                  currRing->N);
    2224           return TRUE;
    2225         }
    2226         ideal arg1 = (ideal) h->Data();
    2227         intvec* arg2 = (intvec*) h->next->Data();
    2228         intvec* arg3   =  (intvec*) h->next->next->Data();
    2229 
    2230 
    2231         ideal result = (ideal) MAltwalk2(arg1, arg2, arg3);
    2232 
    2233         res->rtyp = IDEAL_CMD;
    2234         res->data =  result;
    2235 
    2236         return FALSE;
    2237       }
    2238       else
    2239       if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
    2240       {
    2241         if (h == NULL || h->Typ() != IDEAL_CMD ||
    2242             h->next == NULL || h->next->Typ() != INTVEC_CMD ||
    2243             h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD||
    2244             h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD)
    2245         {
    2246           Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec, int) expected");
    2247           return TRUE;
    2248         }
    2249 
    2250         if (((intvec*) h->next->Data())->length() != currRing->N &&
    2251             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2252         {
    2253           Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
    2254                  currRing->N);
    2255           return TRUE;
    2256         }
    2257         ideal arg1 = (ideal) h->Data();
    2258         intvec* arg2 = (intvec*) h->next->Data();
    2259         intvec* arg3   =  (intvec*) h->next->next->Data();
    2260         int arg4   =  (int) ((long)(h->next->next->next->Data()));
    2261 
    2262         ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3, arg4);
    2263 
    2264         res->rtyp = IDEAL_CMD;
    2265         res->data =  result;
    2266 
    2267         return FALSE;
    2268       }
    2269       else
    2270       if (strcmp(sys_cmd, "TranMrImprovwalk") == 0)
    22712147      {
    22722148        if (h == NULL || h->Typ() != IDEAL_CMD ||
     
    22742150            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
    22752151            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
    2276             h->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
    2277             h->next->next->next == NULL || h->next->next->next->next->next->Typ() != INT_CMD)
    2278         {
    2279           Werror("system(\"TranMrImprovwalk\", ideal, intvec, intvec) expected");
    2280           return TRUE;
    2281         }
    2282 
     2152            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
     2153            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != RING_CMD)
     2154        {
     2155          Werror("system(\"Mfrwalk\", ideal, intvec, intvec, int, int, ring) expected");
     2156          return TRUE;
     2157        }
    22832158        if (((intvec*) h->next->Data())->length() != currRing->N &&
    2284             ((intvec*) h->next->next->Data())->length() != currRing->N )
    2285         {
    2286           Werror("system(\"TranMrImprovwalk\" ...) intvecs not of length %d\n", currRing->N);
     2159            ((intvec*) h->next->next->Data())->length() != currRing->N)
     2160        {
     2161          Werror("system(\"Mfrwalk\" ...) intvecs not of length %d\n",currRing->N);
    22872162          return TRUE;
    22882163        }
     
    22922167        int arg4 = (int)(long) h->next->next->next->Data();
    22932168        int arg5 = (int)(long) h->next->next->next->next->Data();
    2294         int arg6 = (int)(long) h->next->next->next->next->next->Data();
    2295 
    2296         ideal result = (ideal) TranMrImprovwalk(arg1, arg2, arg3, arg4, arg5, arg6);
     2169        ring arg6 = (ring) h->next->next->next->next->next->Data();
     2170
     2171        ideal result = (ideal) Mfrwalk(arg1, arg2, arg3, arg4, arg5, arg6);
    22972172
    22982173        res->rtyp = IDEAL_CMD;
     
    23022177      }
    23032178      else
    2304 
    2305   #endif
     2179      if (strcmp(sys_cmd, "Mprwalk") == 0)
     2180      {
     2181        if (h == NULL || h->Typ() != IDEAL_CMD ||
     2182            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
     2183            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD ||
     2184            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD ||
     2185            h->next->next->next->next == NULL || h->next->next->next->next->Typ() != INT_CMD ||
     2186            h->next->next->next->next->next == NULL || h->next->next->next->next->next->Typ() != INT_CMD ||
     2187            h->next->next->next->next->next->next == NULL || h->next->next->next->next->next->next->Typ() != RING_CMD)
     2188        {
     2189          Werror("system(\"Mprwalk\", ideal, intvec, intvec, int, int, int, ring) expected");
     2190          return TRUE;
     2191        }
     2192        if (((intvec*) h->next->Data())->length() != currRing->N &&
     2193            ((intvec*) h->next->next->Data())->length() != currRing->N )
     2194        {
     2195          Werror("system(\"Mrwalk\" ...) intvecs not of length %d\n",
     2196                 currRing->N);
     2197          return TRUE;
     2198        }
     2199        ideal arg1 = (ideal) h->Data();
     2200        intvec* arg2 = (intvec*) h->next->Data();
     2201        intvec* arg3 =  (intvec*) h->next->next->Data();
     2202        int arg4 = (int)(long) h->next->next->next->Data();
     2203        int arg5 = (int)(long) h->next->next->next->next->Data();
     2204        int arg6 = (int)(long) h->next->next->next->next->next->Data();
     2205        ring arg7 = (ring) h->next->next->next->next->next->next->Data();
     2206
     2207
     2208        ideal result = (ideal) Mprwalk(arg1, arg2, arg3, arg4, arg5, arg6, arg7);
     2209
     2210        res->rtyp = IDEAL_CMD;
     2211        res->data =  result;
     2212
     2213        return FALSE;
     2214      }
     2215      else
     2216
     2217  #ifdef TRAN_Orig
     2218      if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
     2219      {
     2220        if (h == NULL || h->Typ() != IDEAL_CMD ||
     2221            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
     2222            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
     2223        {
     2224          Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec) expected");
     2225          return TRUE;
     2226        }
     2227
     2228        if (((intvec*) h->next->Data())->length() != currRing->N &&
     2229            ((intvec*) h->next->next->Data())->length() != currRing->N )
     2230        {
     2231          Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
     2232                 currRing->N);
     2233          return TRUE;
     2234        }
     2235        ideal arg1 = (ideal) h->Data();
     2236        intvec* arg2 = (intvec*) h->next->Data();
     2237        intvec* arg3   =  (intvec*) h->next->next->Data();
     2238
     2239
     2240        ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3);
     2241
     2242        res->rtyp = IDEAL_CMD;
     2243        res->data =  result;
     2244
     2245        return FALSE;
     2246      }
     2247      else
     2248  #endif
     2249      if (strcmp(sys_cmd, "MAltwalk2") == 0)
     2250        {
     2251        if (h == NULL || h->Typ() != IDEAL_CMD ||
     2252            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
     2253            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD)
     2254        {
     2255          Werror("system(\"MAltwalk2\", ideal, intvec, intvec) expected");
     2256          return TRUE;
     2257        }
     2258
     2259        if (((intvec*) h->next->Data())->length() != currRing->N &&
     2260            ((intvec*) h->next->next->Data())->length() != currRing->N )
     2261        {
     2262          Werror("system(\"MAltwalk2\" ...) intvecs not of length %d\n",
     2263                 currRing->N);
     2264          return TRUE;
     2265        }
     2266        ideal arg1 = (ideal) h->Data();
     2267        intvec* arg2 = (intvec*) h->next->Data();
     2268        intvec* arg3   =  (intvec*) h->next->next->Data();
     2269
     2270
     2271        ideal result = (ideal) MAltwalk2(arg1, arg2, arg3);
     2272
     2273        res->rtyp = IDEAL_CMD;
     2274        res->data =  result;
     2275
     2276        return FALSE;
     2277      }
     2278      else
     2279      if (strcmp(sys_cmd, "TranMImprovwalk") == 0)
     2280      {
     2281        if (h == NULL || h->Typ() != IDEAL_CMD ||
     2282            h->next == NULL || h->next->Typ() != INTVEC_CMD ||
     2283            h->next->next == NULL || h->next->next->Typ() != INTVEC_CMD||
     2284            h->next->next->next == NULL || h->next->next->next->Typ() != INT_CMD)
     2285        {
     2286          Werror("system(\"TranMImprovwalk\", ideal, intvec, intvec, int) expected");
     2287          return TRUE;
     2288        }
     2289
     2290        if (((intvec*) h->next->Data())->length() != currRing->N &&
     2291            ((intvec*) h->next->next->Data())->length() != currRing->N )
     2292        {
     2293          Werror("system(\"TranMImprovwalk\" ...) intvecs not of length %d\n",
     2294                 currRing->N);
     2295          return TRUE;
     2296        }
     2297        ideal arg1 = (ideal) h->Data();
     2298        intvec* arg2 = (intvec*) h->next->Data();
     2299        intvec* arg3   =  (intvec*) h->next->next->Data();
     2300        int arg4   =  (int) ((long)(h->next->next->next->Data()));
     2301
     2302        ideal result = (ideal) TranMImprovwalk(arg1, arg2, arg3, arg4);
     2303
     2304        res->rtyp = IDEAL_CMD;
     2305        res->data =  result;
     2306
     2307        return FALSE;
     2308      }
     2309      else
     2310#endif
    23062311  /*================= Extended system call ========================*/
    23072312     {
     
    23192324#ifdef HAVE_EXTENDED_SYSTEM
    23202325  // You can put your own system calls here
    2321 #  include <kernel/fglm/fglmcomb.cc>
    2322 #  include <kernel/fglm/fglm.h>
     2326#  include <kernel/fglmcomb.cc>
     2327#  include <kernel/fglm.h>
    23232328#  ifdef HAVE_NEWTON
    23242329#    include <hc_newton.h>
     
    23262331#  include <polys/mod_raw.h>
    23272332#  include <polys/monomials/ring.h>
    2328 #  include <kernel/GBEngine/shiftgb.h>
     2333#  include <kernel/shiftgb.h>
    23292334
    23302335static BOOLEAN jjEXTENDED_SYSTEM(leftv res, leftv h)
     
    26822687//       }
    26832688//       else
     2689  /*==================== isSqrFree =============================*/
     2690      if(strcmp(sys_cmd,"isSqrFree")==0)
     2691      {
     2692        if ((h!=NULL) &&(h->Typ()==POLY_CMD))
     2693        {
     2694          res->rtyp=INT_CMD;
     2695          res->data=(void *)(long) singclap_isSqrFree((poly)h->Data(), currRing);
     2696          return FALSE;
     2697        }
     2698        else
     2699          WerrorS("poly expected");
     2700      }
     2701      else
    26842702  /*==================== pDivStat =============================*/
    26852703  #if defined(PDEBUG) || defined(PDIV_DEBUG)
     
    31423160      else
    31433161  #endif
    3144   /*==================== Roune Hilb  =================*/
    3145        if (strcmp(sys_cmd, "hilbroune") == 0)
    3146        {
    3147          ideal I;
    3148          if ((h!=NULL) && (h->Typ()==IDEAL_CMD))
    3149          {
    3150            I=(ideal)h->CopyD();
    3151            slicehilb(I);
    3152          }
    3153          else return TRUE;
    3154          return FALSE;
    3155        }
    31563162  /*==================== minor =================*/
    31573163      if (strcmp(sys_cmd, "minor")==0)
     
    35913597        {
    35923598#ifdef HAVE_PLURAL
     3599          Print("NTL_0:%d (use NTL for gcd of polynomials in char 0)\n",isOn(SW_USE_NTL_GCD_0));
     3600          Print("NTL_p:%d (use NTL for gcd of polynomials in char p)\n",isOn(SW_USE_NTL_GCD_P));
    35933601          Print("EZGCD:%d (use EZGCD for gcd of polynomials in char 0)\n",isOn(SW_USE_EZGCD));
    35943602          Print("EZGCD_P:%d (use EZGCD_P for gcd of polynomials in char p)\n",isOn(SW_USE_EZGCD_P));
     
    36063614          char *s=(char *)h->Data();
    36073615#ifdef HAVE_PLURAL
     3616          if (strcmp(s,"NTL_0")==0) { if (d) On(SW_USE_NTL_GCD_0); else Off(SW_USE_NTL_GCD_0); } else
     3617          if (strcmp(s,"NTL_p")==0) { if (d) On(SW_USE_NTL_GCD_P); else Off(SW_USE_NTL_GCD_P); } else
    36083618          if (strcmp(s,"EZGCD")==0) { if (d) On(SW_USE_EZGCD); else Off(SW_USE_EZGCD); } else
    36093619          if (strcmp(s,"EZGCD_P")==0) { if (d) On(SW_USE_EZGCD_P); else Off(SW_USE_EZGCD_P); } else
     
    38683878  if (strcmp(sys_cmd,"reservedLink")==0)
    38693879  {
    3870     extern si_link ssiCommandLink();
     3880    si_link ssiCommandLink();
    38713881    res->rtyp=LINK_CMD;
    38723882    si_link p=ssiCommandLink();
  • Singular/walk.cc

    • Property mode changed from 100644 to 100755
    rc311064 rffd4a9  
    1818//#define CHECK_IDEAL
    1919//#define CHECK_IDEAL_MWALK
     20//#define CHECK_IDEAL_MFRWALK
    2021
    2122//#define NEXT_VECTORS_CC
     
    3536/* includes */
    3637
    37 #include <kernel/mod2.h>
    38 #include <misc/intvec.h>
    39 #include <Singular/cntrlc.h>
    40 #include <misc/options.h>
    41 #include <omalloc/omalloc.h>
    42 #include <Singular/ipshell.h>
    43 #include <Singular/ipconv.h>
    44 #include <coeffs/ffields.h>
    45 #include <coeffs/coeffs.h>
    46 #include <Singular/subexpr.h>
    47 #include <polys/templates/p_Procs.h>
    48 
    49 #include <polys/monomials/maps.h>
    50 
    51 /* include Hilbert-function */
    52 #include <kernel/GBEngine/stairc.h>
    53 
    54 /** kstd2.cc */
    55 #include <kernel/GBEngine/kutil.h>
    56 #include <kernel/GBEngine/khstd.h>
    57 
    58 #include <Singular/walk.h>
    59 #include <kernel/polys.h>
    60 #include <kernel/ideals.h>
    61 #include <Singular/ipid.h>
    62 #include <Singular/tok.h>
    63 #include <coeffs/numbers.h>
    64 #include <Singular/ipid.h>
    65 #include <polys/monomials/ring.h>
    66 #include <kernel/GBEngine/kstd1.h>
    67 #include <polys/matpol.h>
    68 #include <polys/weight.h>
    69 #include <misc/intvec.h>
    70 #include <kernel/GBEngine/syz.h>
    71 #include <Singular/lists.h>
    72 #include <polys/prCopy.h>
    73 #include <polys/monomials/ring.h>
    74 //#include <polys/ext_fields/longalg.h>
    75 #include <polys/clapsing.h>
    76 
    77 #include <coeffs/mpr_complex.h>
    78 
    7938#include <stdio.h>
     39#include <stdlib.h>
    8040// === Zeit & System (Holger Croeni ===
    8141#include <time.h>
     
    8848#include <sys/types.h>
    8949
     50
     51//#include "config.h"
     52#include <kernel/mod2.h>
     53#include <misc/intvec.h>
     54#include <Singular/cntrlc.h>
     55#include <misc/options.h>
     56#include <omalloc/omalloc.h>
     57#include <kernel/febase.h>
     58#include <Singular/ipshell.h>
     59#include <Singular/ipconv.h>
     60#include <coeffs/ffields.h>
     61#include <coeffs/coeffs.h>
     62#include <Singular/subexpr.h>
     63#include <polys/templates/p_Procs.h>
     64
     65#include <polys/monomials/maps.h>
     66
     67/* include Hilbert-function */
     68#include <kernel/stairc.h>
     69
     70/** kstd2.cc */
     71#include <kernel/kutil.h>
     72#include <kernel/khstd.h>
     73
     74#include <Singular/walk.h>
     75#include <kernel/polys.h>
     76#include <kernel/ideals.h>
     77#include <Singular/ipid.h>
     78#include <Singular/tok.h>
     79#include <kernel/febase.h>
     80#include <coeffs/numbers.h>
     81#include <Singular/ipid.h>
     82#include <polys/monomials/ring.h>
     83#include <kernel/kstd1.h>
     84#include <polys/matpol.h>
     85#include <polys/weight.h>
     86#include <misc/intvec.h>
     87#include <kernel/syz.h>
     88#include <Singular/lists.h>
     89#include <polys/prCopy.h>
     90#include <polys/monomials/ring.h>
     91//#include <polys/ext_fields/longalg.h>
     92#ifdef HAVE_FACTORY
     93#include <polys/clapsing.h>
     94#endif
     95
     96#include <coeffs/mpr_complex.h>
     97
    9098int nstep;
    9199
     
    118126}
    119127
    120 /************************************
    121  * construct the set s from F u {P} *
    122  ************************************/
    123 // unused
    124 #if 0
    125 static void initSSpecialCC (ideal F, ideal Q, ideal P,kStrategy strat)
    126 {
    127   int   i,pos;
    128 
    129   if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
    130   else i=setmaxT;
    131 
    132   strat->ecartS=initec(i);
    133   strat->sevS=initsevS(i);
    134   strat->S_2_R=initS_2_R(i);
    135   strat->fromQ=NULL;
    136   strat->Shdl=idInit(i,F->rank);
    137   strat->S=strat->Shdl->m;
    138 
    139   // - put polys into S -
    140   if (Q!=NULL)
    141   {
    142     strat->fromQ=initec(i);
    143     memset(strat->fromQ,0,i*sizeof(int));
    144     for (i=0; i<IDELEMS(Q); i++)
    145     {
    146       if (Q->m[i]!=NULL)
    147       {
    148         LObject h;
    149         h.p = pCopy(Q->m[i]);
    150         //if (TEST_OPT_INTSTRATEGY)
    151         //{
    152         //  //pContent(h.p);
    153         //  h.pCleardenom(); // also does a pContent
    154         //}
    155         //else
    156         //{
    157         //  h.pNorm();
    158         //}
    159         strat->initEcart(&h);
    160         if (rHasLocalOrMixedOrdering_currRing())
    161         {
    162           deleteHC(&h,strat);
    163         }
    164         if (h.p!=NULL)
    165         {
    166           if (strat->sl==-1)
    167             pos =0;
    168           else
    169           {
    170             pos = posInS(strat,strat->sl,h.p,h.ecart);
    171           }
    172           h.sev = pGetShortExpVector(h.p);
    173           h.SetpFDeg();
    174           strat->enterS(h,pos,strat, strat->tl+1);
    175           enterT(h, strat);
    176           strat->fromQ[pos]=1;
    177         }
    178       }
    179     }
    180   }
    181   //- put polys into S -
    182   for (i=0; i<IDELEMS(F); i++)
    183   {
    184     if (F->m[i]!=NULL)
    185     {
    186       LObject h;
    187       h.p = pCopy(F->m[i]);
    188       if (rHasGlobalOrdering(currRing))
    189       {
    190         //h.p=redtailBba(h.p,strat->sl,strat);
    191         h.p=redtailBba(h.p,strat->sl,strat);
    192       }
    193       else
    194       {
    195         deleteHC(&h,strat);
    196       }
    197       strat->initEcart(&h);
    198       if (h.p!=NULL)
    199       {
    200         if (strat->sl==-1)
    201           pos =0;
    202         else
    203           pos = posInS(strat,strat->sl,h.p,h.ecart);
    204         h.sev = pGetShortExpVector(h.p);
    205         strat->enterS(h,pos,strat, strat->tl+1);
    206         h.length = pLength(h.p);
    207         h.SetpFDeg();
    208         enterT(h,strat);
    209       }
    210     }
    211   }
    212 #ifdef INITSSPECIAL
    213   for (i=0; i<IDELEMS(P); i++)
    214   {
    215     if (P->m[i]!=NULL)
    216     {
    217       LObject h;
    218       h.p=pCopy(P->m[i]);
    219       strat->initEcart(&h);
    220       h.length = pLength(h.p);
    221       if (TEST_OPT_INTSTRATEGY)
    222       {
    223         h.pCleardenom();
    224       }
    225       else
    226       {
    227         h.pNorm();
    228       }
    229       if(strat->sl>=0)
    230       {
    231         if (rHasGlobalOrdering(currRing))
    232         {
    233           h.p=redBba(h.p,strat->sl,strat);
    234           if (h.p!=NULL)
    235             h.p=redtailBba(h.p,strat->sl,strat);
    236         }
    237         else
    238         {
    239           h.p=redMora(h.p,strat->sl,strat);
    240           strat->initEcart(&h);
    241         }
    242         if(h.p!=NULL)
    243         {
    244           if (TEST_OPT_INTSTRATEGY)
    245           {
    246             h.pCleardenom();
    247           }
    248           else
    249           {
    250             h.is_normalized = 0;
    251             h.pNorm();
    252           }
    253           h.sev = pGetShortExpVector(h.p);
    254           h.SetpFDeg();
    255           pos = posInS(strat->S,strat->sl,h.p,h.ecart);
    256           enterpairsSpecial(h.p,strat->sl,h.ecart,pos,strat,strat->tl+1);
    257           strat->enterS(h,pos,strat, strat->tl+1);
    258           enterT(h,strat);
    259         }
    260       }
    261       else
    262       {
    263         h.sev = pGetShortExpVector(h.p);
    264         h.SetpFDeg();
    265         strat->enterS(h,0,strat, strat->tl+1);
    266         enterT(h,strat);
    267       }
    268     }
    269   }
    270 #endif
    271 }
    272 #endif
    273 
    274128/*****************
    275129 *interreduce F  *
     
    280134  kStrategy strat = new skStrategy;
    281135
    282 //  if (TEST_OPT_PROT)
    283 //  {
    284 //    writeTime("start InterRed:");
    285 //    mflush();
    286 //  }
    287136  //strat->syzComp     = 0;
    288137  strat->kHEdgeFound = (currRing->ppNoether) != NULL;
     
    312161  initS(F,Q,strat);
    313162
    314   /*
    315   timetmp=clock();//22.01.02
    316   initSSpecialCC(F,Q,NULL,strat);
    317   tininitS=tininitS+clock()-timetmp;//22.01.02
    318   */
    319163  if(TEST_OPT_REDSB)
    320164  {
     
    348192    strat->fromQ = NULL;
    349193  }
    350 //  if (TEST_OPT_PROT)
    351 //  {
    352 //    writeTime("end Interred:");
    353 //    mflush();
    354 //  }
    355194  ideal shdl=strat->Shdl;
    356195  idSkipZeroes(shdl);
     
    360199}
    361200
    362 //unused
    363 #if 0
     201#ifdef TIME_TEST
    364202static void TimeString(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
    365203                       clock_t tlf,clock_t tred, clock_t tnw, int step)
     
    401239#endif
    402240
    403 //unused
    404 #if 0
     241#ifdef TIME_TEST
    405242static void TimeStringFractal(clock_t tinput, clock_t tostd, clock_t tif,clock_t tstd,
    406243                       clock_t textra, clock_t tlf,clock_t tred, clock_t tnw)
     
    431268#endif
    432269
    433 #ifdef CHECK_IDEAL_MWALK
    434270static void idString(ideal L, const char* st)
    435271{
     
    443279  Print(" %s;", pString(L->m[nL-1]));
    444280}
    445 #endif
    446 
    447 #if defined(CHECK_IDEAL_MWALK) || defined(ENDWALKS)
     281
    448282static void headidString(ideal L, char* st)
    449283{
     
    457291  Print(" %s;", pString(pHead(L->m[nL-1])));
    458292}
    459 #endif
    460 
    461 #if defined(CHECK_IDEAL_MWALK) || defined(ENDWALKS)
     293
    462294static void idElements(ideal L, char* st)
    463295{
     
    471303  }
    472304  int j, nsame;
    473   // int  nk=0;
    474305  for(i=0; i<nL; i++)
    475306  {
     
    497328  omFree(K);
    498329}
    499 #endif
    500 
    501330
    502331static void ivString(intvec* iv, const char* ch)
     
    512341}
    513342
    514 //unused
    515 //#if 0
    516343static void MivString(intvec* iva, intvec* ivb, intvec* ivc)
    517344{
     
    536363  Print("%d)", (*ivc)[nV]);
    537364}
    538 //#endif
    539365
    540366/********************************************************************
     
    577403  mpz_clear(g);
    578404}
    579 
    580 //unused
    581 #if 0
    582 static int isVectorNeg(intvec* omega)
    583 {
    584   int i;
    585 
    586   for(i=omega->length(); i>=0; i--)
    587   {
    588     if((*omega)[i]<0)
    589     {
    590       return 1;
    591     }
    592   }
    593   return 0;
    594 }
    595 #endif
    596405
    597406/********************************************************************
     
    627436    {
    628437      PrintLn();
    629       PrintS("\n// ** OVERFLOW in \"MwalkInitialForm\": ");
     438      PrintS("\n//** MLmWeightedDegree: OVERFLOW: ");
    630439      mpz_out_str( stdout, 10, zsum);
    631       PrintS(" is greater than 2147483647 (max. integer representation)");
     440      PrintS(" is greater than 2147483647 (max. integer representation).\n");
    632441      Overflow_Error = TRUE;
    633442    }
     
    764573  if(G->m[0] == NULL)
    765574  {
    766     PrintS("//** the result may be WRONG, i.e. 0!!\n");
    767     return 0;
     575    idString(G,"G");
     576    WerrorS("//** test_w_in_ConeCC: the result may be wrong, i.e. equal zero.\n");
    768577  }
    769578
     
    941750{
    942751  int i, nR = iv->length();
    943 
     752 
    944753  intvec* ivm = new intvec(nR*nR);
    945754
     
    951760  {
    952761    (*ivm)[i*nR+i-1] = 1;
     762  }
     763  return ivm;
     764}
     765
     766/*****************************************************************************
     767* create a weight matrix order as intvec of an extra weight vector (a(iv),lp)*
     768******************************************************************************/
     769intvec* MivMatrixOrderRefine(intvec* iv, intvec* iw)
     770{
     771  assume(iv->length() == iw->length());
     772  int i, nR = iv->length();
     773 
     774  intvec* ivm = new intvec(nR*nR);
     775
     776  for(i=0; i<nR; i++)
     777  {
     778    (*ivm)[i] = (*iv)[i];
     779    (*ivm)[i+nR] = (*iw)[i];
     780  }
     781  for(i=2; i<nR; i++)
     782  {
     783    (*ivm)[i*nR+i-2] = 1;
    953784  }
    954785  return ivm;
     
    981812}
    982813
    983 //unused
    984 /*****************************************************************************
    985  * print the max total degree and the max coefficient of G                   *
    986  *****************************************************************************/
    987 #if 0
    988 static void checkComplexity(ideal G, char* cG)
    989 {
    990   int nV = currRing->N;
    991   int nG = IDELEMS(G);
    992   intvec* ivUnit = Mivdp(nV);
    993   int i, tmpdeg, maxdeg=0;
    994   number tmpcoeff , maxcoeff=currRing->cf->nNULL;
    995   poly p;
    996   for(i=nG-1; i>=0; i--)
    997   {
    998     tmpdeg = MwalkWeightDegree(G->m[i], ivUnit);
    999     if(tmpdeg > maxdeg )
    1000     {
    1001       maxdeg = tmpdeg;
    1002     }
    1003   }
    1004 
    1005   for(i=nG-1; i>=0; i--)
    1006   {
    1007     p = pCopy(G->m[i]);
    1008     while(p != NULL)
    1009     {
    1010       //tmpcoeff = pGetCoeff(pHead(p));
    1011       tmpcoeff = pGetCoeff(p);
    1012       if(nGreater(tmpcoeff,maxcoeff))
    1013       {
    1014          maxcoeff = nCopy(tmpcoeff);
    1015       }
    1016       pIter(p);
    1017     }
    1018     pDelete(&p);
    1019   }
    1020   p = pNSet(maxcoeff);
    1021   char* pStr = pString(p);
    1022   delete ivUnit;
    1023   Print("// max total degree of %s = %d\n",cG, maxdeg);
    1024   Print("// max coefficient of %s  = %s", cG, pStr);//ing(p));
    1025   Print(" which consists of %d digits", (int)strlen(pStr));
    1026   PrintLn();
    1027 }
    1028 #endif
    1029 
     814/**********************************************
     815 * Look for the smallest absolut value in vec *
     816 **********************************************/
     817static int MivAbsMax(intvec* vec)
     818{
     819  int i,k;
     820  if((*vec)[0] < 0)
     821  {
     822    k = -(*vec)[0];
     823  }
     824  else
     825  {
     826    k = (*vec)[0];
     827  }
     828  for(i=1; i < (vec->length()); i++)
     829  {
     830    if((*vec)[i] < 0)
     831    {
     832      if(-(*vec)[i] > k)
     833      {
     834        k = -(*vec)[i];
     835      }
     836    }
     837    else
     838    {
     839      if((*vec)[i] > k)
     840      {
     841        k = (*vec)[i];
     842      }
     843    }
     844  }
     845  return k;
     846}
    1030847/*****************************************************************************
    1031848* If target_ord = intmat(A1, ..., An) then calculate the perturbation        *
     
    1041858intvec* MPertVectors(ideal G, intvec* ivtarget, int pdeg)
    1042859{
    1043   // ivtarget is a matrix order of a degree reverse lex. order
    1044   int nV = currRing->N;
    1045   //assume(pdeg <= nV && pdeg >= 0);
    1046 
    1047   int i, j, nG = IDELEMS(G);
     860  int nV = currRing->N, i=0, j=0, nG = IDELEMS(G);
    1048861  intvec* v_null =  new intvec(nV);
    1049 
    1050862
    1051863  // Check that the perturbed degree is valid
    1052864  if(pdeg > nV || pdeg <= 0)
    1053865  {
    1054     WerrorS("//** The perturbed degree is wrong!!");
     866    WerrorS("\n//** MPertVectors: The perturbed degree is wrong.\n");
    1055867    return v_null;
    1056868  }
     
    1062874  }
    1063875  mpz_t *pert_vector = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
    1064   //mpz_t *pert_vector1 = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
    1065876
    1066877  for(i=0; i<nV; i++)
    1067878  {
    1068879    mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
    1069    // mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
    1070   }
    1071   // Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
    1072   // where the Ai are the i-te rows of the matrix target_ord.
     880  }
     881  // 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.
    1073882  int ntemp, maxAi, maxA=0;
    1074883  for(i=1; i<pdeg; i++)
     
    1094903  }
    1095904
    1096   // Calculate inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.
    1097 
    1098   intvec* ivUnit = Mivdp(nV);
    1099 
     905  // Compute inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.
    1100906  mpz_t tot_deg; mpz_init(tot_deg);
    1101907  mpz_t maxdeg; mpz_init(maxdeg);
    1102908  mpz_t inveps; mpz_init(inveps);
    1103909
    1104 
    1105910  for(i=nG-1; i>=0; i--)
    1106911  {
    1107      mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
     912     mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], Mivdp(nV)));
    1108913     if (mpz_cmp(maxdeg,  tot_deg) > 0 )
    1109914     {
    1110915       mpz_set(tot_deg, maxdeg);
    1111      }
    1112   }
    1113 
    1114   delete ivUnit;
     916     }
     917  }
    1115918  mpz_mul_ui(inveps, tot_deg, maxA);
    1116919  mpz_add_ui(inveps, inveps, 1);
     
    1121924  if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
    1122925  {
    1123     //  Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", mpz_get_si(inveps), pdeg);
    1124926    mpz_fdiv_q_ui(inveps, inveps, pdeg);
    1125     // mpz_out_str(stdout, 10, inveps);
    1126927  }
    1127928#else
    1128   // PrintS("\n// the \"big\" inverse epsilon: ");
     929  PrintS("\n//** MPertVectors: the \"big\" inverse epsilon: ");
    1129930  mpz_out_str(stdout, 10, inveps);
    1130931#endif
    1131932
    1132   // pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg,
    1133   // pert_vector := A1
    1134   for( i=1; i < pdeg; i++ )
     933  // pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg, pert_vector := A1
     934  for(i=1; i<pdeg; i++)
    1135935  {
    1136936    for(j=0; j<nV; j++)
     
    1167967
    1168968  intvec *pert_vector1= new intvec(nV);
    1169   j = 0;
     969
    1170970  for(i=0; i<nV; i++)
    1171971  {
    1172972    (* pert_vector1)[i] = mpz_get_si(pert_vector[i]);
    1173     (* pert_vector1)[i] = 0.1*(* pert_vector1)[i];
    1174     (* pert_vector1)[i] = floor((* pert_vector1)[i] + 0.5);
    1175     if((* pert_vector1)[i] == 0)
    1176     {
    1177       j++;
    1178     }
    1179   }
    1180   if(j > nV - 1)
    1181   {
    1182     // Print("\n//  MPertVectors: geaenderter vector gleich Null! \n");
    1183     delete pert_vector1;
    1184     goto CHECK_OVERFLOW;
    1185   }
     973  }
     974  while(MivAbsMax(pert_vector1)>100000)
     975  {
     976    j = 0;
     977    for(i=0; i<nV; i++)
     978    {
     979      (* pert_vector1)[i] = 0.1*(* pert_vector1)[i];
     980      (* pert_vector1)[i] = floor((* pert_vector1)[i] + 0.5);
     981      if((* pert_vector1)[i] == 0)
     982      {
     983        j++;
     984      }
     985    }
     986    if(j > nV - 1)
     987    {
     988      break;
     989    }
    1186990
    1187991// check that the perturbed weight vector lies in the Groebner cone
    1188   if(test_w_in_ConeCC(G,pert_vector1) != 0)
    1189   {
    1190     // Print("\n//  MPertVectors: geaenderter vector liegt in Groebnerkegel! \n");
    1191     for(i=0; i<nV; i++)
    1192     {
    1193       mpz_set_si(pert_vector[i], (*pert_vector1)[i]);
    1194     }
    1195   }
    1196   else
    1197   {
    1198     //Print("\n// MpertVectors: geaenderter vector liegt nicht in Groebnerkegel! \n");
     992    if(test_w_in_ConeCC(G,pert_vector1) != 0)
     993    {
     994      for(i=0; i<nV; i++)
     995      {
     996        mpz_set_si(pert_vector[i], (*pert_vector1)[i]);
     997      }
     998    }
     999    else
     1000    {
     1001      break;
     1002    }
    11991003  }
    12001004  delete pert_vector1;
    12011005
    1202   CHECK_OVERFLOW:
     1006  //CHECK_OVERFLOW:
    12031007  intvec* result = new intvec(nV);
    12041008
    1205   /* 2147483647 is max. integer representation in SINGULAR */
     1009// 2147483647 is max. integer representation in SINGULAR
    12061010  mpz_t sing_int;
    12071011  mpz_init_set_ui(sing_int,  2147483647);
    12081012
    1209   int ntrue=0;
    12101013  for(i=0; i<nV; i++)
    12111014  {
     
    12131016    if(mpz_cmp(pert_vector[i], sing_int)>=0)
    12141017    {
    1215       ntrue++;
    12161018      if(Overflow_Error == FALSE)
    12171019      {
    12181020        Overflow_Error = TRUE;
    1219         PrintS("\n// ** OVERFLOW in \"MPertvectors\": ");
     1021        PrintS("\n//** MPertvectors: OVERFLOW: ");
    12201022        mpz_out_str( stdout, 10, pert_vector[i]);
    1221         PrintS(" is greater than 2147483647 (max. integer representation)");
    1222         Print("\n//  So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
    1223       }
    1224     }
    1225   }
    1226 
    1227   if(Overflow_Error == TRUE)
    1228   {
    1229     ivString(result, "pert_vector");
    1230     Print("\n// %d element(s) of it is overflow!!", ntrue);
     1023        PrintS(" is greater than 2147483647 (max. integer representation).\n");
     1024        Print("\n//** MPertvectors: So vector[%d] := %d may be wrong.\n", i+1, (*result)[i]);
     1025      }
     1026    }
    12311027  }
    12321028
     
    12341030  mpz_clear(sing_int);
    12351031  omFree(pert_vector);
    1236   //omFree(pert_vector1);
     1032
    12371033  mpz_clear(tot_deg);
    12381034  mpz_clear(maxdeg);
     
    12691065  if(pdeg > nV || pdeg <= 0)
    12701066  {
    1271     WerrorS("//** The perturbed degree is wrong!!");
     1067    WerrorS("\n//** MPertVectorslp: The perturbed degree is wrong.\n");
    12721068    return pert_vector;
    12731069  }
     
    13221118  // Print(" %d", inveps);
    13231119#else
    1324   PrintS("\n// the \"big\" inverse epsilon %d", inveps);
     1120  PrintS("\n//** MPertVectorslp: the \"big\" inverse epsilon %d.\n", inveps);
    13251121#endif
    13261122
     
    14341230  return(ivM);
    14351231}
    1436 
    1437 //unused
    1438 #if 0
    1439 static intvec* MatrixOrderdp(int nV)
    1440 {
    1441   int i;
    1442   intvec* ivM = new intvec(nV*nV);
    1443 
    1444   for(i=0; i<nV; i++)
    1445   {
    1446     (*ivM)[i] = 1;
    1447   }
    1448   for(i=1; i<nV; i++)
    1449   {
    1450     (*ivM)[(i+1)*nV - i] = -1;
    1451   }
    1452   return(ivM);
    1453 }
    1454 #endif
    14551232
    14561233intvec* MivUnit(int nV)
     
    15761353  BOOLEAN nflow = FALSE;
    15771354
    1578   // computes gcd
     1355  // compute gcd
    15791356  mpz_set(ztmp, pert_vector[0]);
    15801357  for(i=0; i<niv; i++)
     
    16061383  if(j > nV - 1)
    16071384  {
    1608     // Print("\n//  MfPertwalk: geaenderter vector gleich Null! \n");
    16091385    delete result1;
    16101386    goto CHECK_OVERFLOW;
    16111387  }
    16121388
    1613 // check that the perturbed weight vector lies in the Groebner cone
     1389  // check whether or not the perturbed weight vector lies in the Groebner cone
    16141390  if(test_w_in_ConeCC(G,result1) != 0)
    16151391  {
    1616     // Print("\n//  MfPertwalk: geaenderter vector liegt in Groebnerkegel! \n");
    16171392    delete result;
    16181393    result = result1;
     
    16251400  {
    16261401    delete result1;
    1627     // Print("\n// Mfpertwalk: geaenderter vector liegt nicht in Groebnerkegel! \n");
    16281402  }
    16291403
     
    16401414        Overflow_Error = TRUE;
    16411415        Print("\n// Xlev = %d and the %d-th element is", Xnlev,  i+1);
    1642         PrintS("\n// ** OVERFLOW in \"Mfpertvector\": ");
     1416        PrintS("\n//** Mfpertvector: OVERFLOW: ");
    16431417        mpz_out_str( stdout, 10, pert_vector[i]);
    1644         PrintS(" is greater than 2147483647 (max. integer representation)");
    1645         Print("\n//  So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
     1418        PrintS(" is greater than 2147483647 (max. integer representation).\n");
     1419        Print("\n//** Mfpertvector: So vector[%d] := %d may be wrong.\n", i+1, (*result)[i]);
    16461420      }
    16471421    }
     
    17061480}
    17071481
    1708 /*********************************************************************
    1709  * G is a red. Groebner basis w.r.t. <_1                             *
    1710  * Gomega is an initial form ideal of <G> w.r.t. a weight vector w   *
    1711  * M is a subideal of <Gomega> and M selft is a red. Groebner basis  *
    1712  *    of the ideal <Gomega> w.r.t. <_w                               *
    1713  * Let m_i = h1.gw1 + ... + hs.gws for each m_i in M; gwi in Gomega  *
    1714  * return F with n(F) = n(M) and f_i = h1.g1 + ... + hs.gs for each i*
    1715  ********************************************************************/
     1482
     1483/*********************************************************
     1484* Let Gomega be the inital form ideal of G.              *
     1485* Let be M = {m_1,...,m_s} be the reduced GB of Gomega.  *
     1486* Hence, mi=sum(h_ij.in_g_j) for suitable hij, i=1,...,s *
     1487* Compute F = {f_1,...,f_s} with f_i=sum h_ij.g_j        *
     1488**********************************************************/
    17161489static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
    17171490{
    1718   ideal Mtmp = idLift(Gw, M, NULL, FALSE, TRUE, TRUE, NULL);
    1719 
    1720   // If Gw is a GB, then isSB = TRUE, otherwise FALSE
    1721   // So, it is better, if one tests whether Gw is a GB
    1722   // in ideals.cc:
    1723   // idLift (ideal mod, ideal submod,ideal * rest, BOOLEAN goodShape,
    1724   //           BOOLEAN isSB,BOOLEAN divide,matrix * unit)
    1725 
    1726   // Let be Mtmp = {m1,...,ms}, where mi=sum hij.in_gj, for all i=1,...,s
    1727   // We compute F = {f1,...,fs}, where fi=sum hij.gj
    1728   int i, j, nM = IDELEMS(Mtmp);
     1491  ideal M_temp = idLift(Gw, M, NULL, FALSE, TRUE, TRUE, NULL);
     1492  idSkipZeroes(M_temp);
     1493  int i, j, nM = IDELEMS(M_temp);
    17291494  ideal idpol, idLG;
    17301495  ideal F = idInit(nM, 1);
    1731 
    17321496  for(i=0; i<nM; i++)
    17331497  {
    1734      idpol = idVec2Ideal(Mtmp->m[i]);
    1735      idLG = MidMult(idpol, G);
    1736      idpol = NULL;
     1498     //idpol = idVec2Ideal(M_temp->m[i]);
     1499     //idLG = MidMult(idpol, G);
     1500     //idpol = NULL;
     1501     idLG = MidMult(idVec2Ideal(M_temp->m[i]), G);
     1502    // PrintS("uups");
    17371503     F->m[i] = NULL;
    17381504     for(j=IDELEMS(idLG)-1; j>=0; j--)
     
    17401506       F->m[i] = pAdd(F->m[i], idLG->m[j]);
    17411507       idLG->m[j]=NULL;
     1508       idSkipZeroes(idLG);
    17421509     }
    17431510     idDelete(&idLG);
    17441511  }
    1745   idDelete(&Mtmp);
    1746   return F;
     1512  //PrintS("aaps");
     1513  //idDelete(&idpol);
     1514  idDelete(&M_temp);
     1515  //F=kStd(F,NULL,testHomog,NULL,NULL,0,NULL,NULL);
     1516  return(F);
    17471517}
    17481518
     
    18051575}
    18061576
    1807 /**********************************************
    1808  * Look for the smallest absolut value in vec *
    1809  **********************************************/
    1810 static int MivAbsMax(intvec* vec)
    1811 {
    1812   int i,k;
    1813   if((*vec)[0] < 0)
    1814   {
    1815     k = -(*vec)[0];
    1816   }
    1817   else
    1818   {
    1819     k = (*vec)[0];
    1820   }
    1821   for(i=1; i < (vec->length()); i++)
    1822   {
    1823     if((*vec)[i] < 0)
    1824     {
    1825       if(-(*vec)[i] > k)
    1826       {
    1827         k = -(*vec)[i];
    1828       }
    1829     }
    1830     else
    1831     {
    1832       if((*vec)[i] > k)
    1833       {
    1834         k = (*vec)[i];
    1835       }
    1836     }
    1837   }
    1838   return k;
    1839 }
     1577/*****************************************************************************
     1578 * compute the gcd of the entries of the vectors curr_weight and diff_weight *
     1579 *****************************************************************************/
     1580static int simplify_gcd(intvec* curr_weight, intvec* diff_weight)
     1581{
     1582  int j;
     1583  int nRing = currRing->N;
     1584  int gcd_tmp = (*curr_weight)[0];
     1585  for (j=1; j<nRing; j++)
     1586  {
     1587    gcd_tmp = gcd(gcd_tmp, (*curr_weight)[j]);
     1588    if(gcd_tmp == 1)
     1589    {
     1590      break;
     1591    }
     1592  }
     1593  if(gcd_tmp != 1)
     1594  {
     1595    for (j=0; j<nRing; j++)
     1596    {
     1597    gcd_tmp = gcd(gcd_tmp, (*diff_weight)[j]);
     1598    if(gcd_tmp == 1)
     1599      {
     1600        break;
     1601      }
     1602    }
     1603  }
     1604  return gcd_tmp;
     1605}
     1606
    18401607
    18411608/**********************************************************************
     
    18491616  Overflow_Error = FALSE;
    18501617
    1851   assume(currRing != NULL && curr_weight != NULL &&
    1852          target_weight != NULL && G != NULL);
     1618  assume(currRing != NULL && curr_weight != NULL && target_weight != NULL && G != NULL);
    18531619
    18541620  int nRing = currRing->N;
    1855   int checkRed, j, kkk, nG = IDELEMS(G);
     1621  int nG = IDELEMS(G);
     1622  int checkRed, j;
    18561623  intvec* ivtemp;
    18571624
     
    18701637  mpz_set_si(sing_int,  2147483647);
    18711638
    1872   mpz_t sing_int_half;
    1873   mpz_init(sing_int_half);
    1874   mpz_set_si(sing_int_half,  3*(1073741824/2));
    1875 
    18761639  mpz_t deg_w0_p1, deg_d0_p1;
    18771640  mpz_init(deg_w0_p1);
     
    18841647  mpz_t t_null;
    18851648  mpz_init(t_null);
     1649  mpz_set_si(t_null,0);
    18861650
    18871651  mpz_t ggt;
     
    18911655  mpz_init(dcw);
    18921656
    1893   //int tn0, tn1, tz1, ncmp, gcd_tmp, ntmp;
    18941657  int gcd_tmp;
    18951658  intvec* diff_weight = MivSub(target_weight, curr_weight);
    1896 
    18971659  intvec* diff_weight1 = MivSub(target_weight, curr_weight);
    18981660  poly g;
    1899   //poly g, gw;
     1661#ifdef  NEXT_VECTORS_CC
     1662  ivString(diff_weight, "//** MwalkNextWeightCC: diff_weight");
     1663#endif
    19001664  for (j=0; j<nG; j++)
    19011665  {
     
    19061670      mpz_set_si(deg_w0_p1, MivDotProduct(ivtemp, curr_weight));
    19071671      mpz_set_si(deg_d0_p1, MivDotProduct(ivtemp, diff_weight));
     1672#ifdef  NEXT_VECTORS_CC
     1673      ivString(ivtemp, "//** MwalkNextWeightCC: ivtemp");
     1674      PrintS("\n//** MwalkNextWeightCC: weighted degree w. r. t. curr_weight: ");
     1675      mpz_out_str( stdout, 10, deg_w0_p1);
     1676      PrintS("\n//** MwalkNextWeightCC: weighted degree w. r. t. diff_weight: ");
     1677      mpz_out_str( stdout, 10, deg_d0_p1);
     1678#endif
    19081679      delete ivtemp;
    19091680
     
    19141685        mpz_set_si(MwWd, MivDotProduct(ivtemp, curr_weight));
    19151686        mpz_sub(s_zaehler, deg_w0_p1, MwWd);
    1916 
    1917         if(mpz_cmp(s_zaehler, t_null) != 0)
     1687#ifdef NEXT_VECTORS_CC
     1688        PrintS("\n//** MwalkNextWeightCC: Grad bzgl. curr_weight: ");
     1689        mpz_out_str( stdout, 10, MwWd);
     1690        PrintS("\n//** MwalkNextWeightCC: s_zaehler: ");
     1691        mpz_out_str( stdout, 10, s_zaehler);
     1692#endif
     1693        if(mpz_cmp(s_zaehler,t_null) != 0)
    19181694        {
    19191695          mpz_set_si(MwWd, MivDotProduct(ivtemp, diff_weight));
    19201696          mpz_sub(s_nenner, MwWd, deg_d0_p1);
    1921 
     1697#ifdef NEXT_VECTORS_CC
     1698          PrintS("\n//** MwalkNextWeightCC: Grad bzgl. diff_weight: ");
     1699          mpz_out_str( stdout, 10, MwWd);
     1700          PrintS("\n//** MwalkNextWeightCC: s_nenner: ");
     1701          mpz_out_str( stdout, 10, s_nenner);
     1702#endif
    19221703          // check for 0 < s <= 1
    1923           if( (mpz_cmp(s_zaehler,t_null) > 0 &&
    1924                mpz_cmp(s_nenner, s_zaehler)>=0) ||
    1925               (mpz_cmp(s_zaehler, t_null) < 0 &&
    1926                mpz_cmp(s_nenner, s_zaehler)<=0))
     1704          if((mpz_cmp_si(s_zaehler,0) > 0 && mpz_cmp(s_nenner,s_zaehler)>=0) ||
     1705             (mpz_cmp_si(s_zaehler,0) < 0 && mpz_cmp(s_nenner,s_zaehler)<=0))
    19271706          {
    19281707            // make both positive
    1929             if (mpz_cmp(s_zaehler, t_null) < 0)
     1708            if(mpz_cmp_si(s_zaehler,0) < 0)
    19301709            {
    19311710              mpz_neg(s_zaehler, s_zaehler);
     
    19361715            cancel(s_zaehler, s_nenner);
    19371716
    1938             if(mpz_cmp(t_nenner, t_null) != 0)
     1717            if(mpz_cmp_si(t_nenner,0) != 0)
    19391718            {
    19401719              mpz_mul(sztn, s_zaehler, t_nenner);
    19411720              mpz_mul(sntz, s_nenner, t_zaehler);
    1942 
     1721#ifdef NEXT_VECTORS_CC
     1722              PrintS("\n//** MwalkNextWeightCC: sntz: ");
     1723              mpz_out_str( stdout, 10, sntz);
     1724              PrintS("\n//** MwalkNextWeightCC: sztn: ");
     1725              mpz_out_str( stdout, 10, sztn);
     1726#endif
    19431727              if(mpz_cmp(sztn,sntz) < 0)
    19441728              {
    1945                 mpz_add(t_nenner, t_null, s_nenner);
    1946                 mpz_add(t_zaehler,t_null, s_zaehler);
     1729                mpz_add(t_nenner,s_nenner,t_null);
     1730                mpz_add(t_zaehler,s_zaehler,t_null);
     1731#ifdef NEXT_VECTORS_CC
     1732                PrintS("\n//** MwalkNextWeightCC: t_nenner: ");
     1733                mpz_out_str( stdout, 10, t_nenner);
     1734                PrintS("\n//** MwalkNextWeightCC: t_zaehler: ");
     1735                mpz_out_str( stdout, 10, t_zaehler);
     1736#endif
    19471737              }
    19481738            }
    19491739            else
    19501740            {
    1951               mpz_add(t_nenner, t_null, s_nenner);
    1952               mpz_add(t_zaehler,t_null, s_zaehler);
     1741              mpz_add(t_nenner,s_nenner,t_null);
     1742              mpz_add(t_zaehler,s_zaehler,t_null);
     1743#ifdef NEXT_VECTORS_CC
     1744              PrintS("\n//** MwalkNextWeightCC: t_nenner: ");
     1745              mpz_out_str( stdout, 10, t_nenner);
     1746              PrintS("\n//** MwalkNextWeightCC: t_zaehler: ");
     1747              mpz_out_str( stdout, 10, t_zaehler);
     1748#endif
    19531749            }
    19541750          }
     
    19591755    }
    19601756  }
    1961 //Print("\n// Alloc Size = %d \n", nRing*sizeof(mpz_t));
    19621757  mpz_t *vec=(mpz_t*)omAlloc(nRing*sizeof(mpz_t));
    1963 
    1964 
    1965   // there is no 0<t<1 and define the next weight vector that is equal to the current weight vector
     1758 
     1759
     1760  // there is no 0<t<=1, so define the next weight vector to be equal to the current weight vector
    19661761  if(mpz_cmp(t_nenner, t_null) == 0)
    19671762  {
    1968     #ifndef SING_NDEBUG
    1969     Print("\n//MwalkNextWeightCC: t_nenner ist Null!");
    1970     #endif
     1763#ifdef NEXT_VECTORS_CC
     1764    Print("\n//** MwalkNextWeightCC: t_nenner equals zero.\n");
     1765#endif
    19711766    delete diff_weight;
    1972     diff_weight = ivCopy(curr_weight);//take memory
     1767    diff_weight = ivCopy(curr_weight);
    19731768    goto FINISH;
    19741769  }
    19751770
    1976   // define the target vector as the next weight vector, if t = 1
     1771  // t = 1, so define the next weight vector to be equal to the target vector
    19771772  if(mpz_cmp_si(t_nenner, 1)==0 && mpz_cmp_si(t_zaehler,1)==0)
    19781773  {
    19791774    delete diff_weight;
    1980     diff_weight = ivCopy(target_weight); //this takes memory
     1775    diff_weight = ivCopy(target_weight);
    19811776    goto FINISH;
    19821777  }
    19831778
    1984    checkRed = 0;
    1985 
    1986   SIMPLIFY_GCD:
    1987 
    19881779  // simplify the vectors curr_weight and diff_weight (C-int)
    1989   gcd_tmp = (*curr_weight)[0];
    1990 
    1991   for (j=1; j<nRing; j++)
    1992   {
    1993     gcd_tmp = gcd(gcd_tmp, (*curr_weight)[j]);
    1994     if(gcd_tmp == 1)
    1995     {
    1996       break;
    1997     }
    1998   }
     1780  gcd_tmp = simplify_gcd(curr_weight,diff_weight);
    19991781  if(gcd_tmp != 1)
    20001782  {
    20011783    for (j=0; j<nRing; j++)
    20021784    {
    2003       gcd_tmp = gcd(gcd_tmp, (*diff_weight)[j]);
    2004       if(gcd_tmp == 1)
    2005       {
    2006         break;
    2007       }
    2008     }
    2009   }
    2010   if(gcd_tmp != 1)
    2011   {
    2012     for (j=0; j<nRing; j++)
    2013     {
    2014       (*curr_weight)[j] =  (*curr_weight)[j]/gcd_tmp;
    2015       (*diff_weight)[j] =  (*diff_weight)[j]/gcd_tmp;
    2016     }
    2017   }
    2018   if(checkRed > 0)
    2019   {
    2020     for (j=0; j<nRing; j++)
    2021     {
    2022       mpz_set_si(vec[j], (*diff_weight)[j]);
    2023     }
    2024     goto TEST_OVERFLOW;
     1785    (*curr_weight)[j] =  (*curr_weight)[j]/gcd_tmp;
     1786    (*diff_weight)[j] =  (*diff_weight)[j]/gcd_tmp;
     1787    }
    20251788  }
    20261789
    20271790#ifdef  NEXT_VECTORS_CC
    2028   Print("\n// gcd of the weight vectors (current and target) = %d", gcd_tmp);
    2029   ivString(curr_weight, "new cw");
    2030   ivString(diff_weight, "new dw");
    2031 
    2032   PrintS("\n// t_zaehler: ");  mpz_out_str( stdout, 10, t_zaehler);
    2033   PrintS(", t_nenner: ");  mpz_out_str( stdout, 10, t_nenner);
    2034 #endif
    2035 
    2036   //  BOOLEAN isdwpos;
     1791  Print("\n//** MwalkNextWeightCC: gcd of the weight vectors (current and target) = %d", gcd_tmp);
     1792  ivString(curr_weight, "new curr_weight");
     1793  ivString(diff_weight, "new diff_weight");
     1794  PrintS("\n//** MwalkNextWeightCC: t_zaehler: ");
     1795  mpz_out_str( stdout, 10, t_zaehler);
     1796  PrintS(", t_nenner: ");
     1797  mpz_out_str( stdout, 10, t_nenner);
     1798#endif
    20371799
    20381800  // construct a new weight vector
     
    20411803    mpz_set_si(dcw, (*curr_weight)[j]);
    20421804    mpz_mul(s_nenner, t_nenner, dcw);
    2043 
    2044     if( (*diff_weight)[j]>0)
    2045     {
    2046       mpz_mul_ui(s_zaehler, t_zaehler, (*diff_weight)[j]);
    2047     }
    2048     else
    2049     {
    2050       mpz_mul_ui(s_zaehler, t_zaehler, -(*diff_weight)[j]);
    2051       mpz_neg(s_zaehler, s_zaehler);
    2052     }
     1805    mpz_mul_si(s_zaehler, t_zaehler, (*diff_weight)[j]);
    20531806    mpz_add(sntz, s_nenner, s_zaehler);
    20541807    mpz_init_set(vec[j], sntz);
    2055 
     1808   
    20561809#ifdef NEXT_VECTORS_CC
    2057     Print("\n//   j = %d ==> ", j);
     1810    Print("\n//** MwalkNextWeightCC:  j = %d ==> ", j);
    20581811    PrintS("(");
    20591812    mpz_out_str( stdout, 10, t_nenner);
     
    20821835
    20831836#ifdef  NEXT_VECTORS_CC
    2084   PrintS("\n// gcd of elements of the vector: ");
     1837  PrintS("\n//** MwalkNextWeightCC: gcd of elements of the vector: ");
    20851838  mpz_out_str( stdout, 10, ggt);
    20861839#endif
    20871840
    2088 /**********************************************************************
    2089 * construct a new weight vector and check whether vec[j] is overflow, *
    2090 * i.e. vec[j] > 2^31.                                                 *
    2091 * If vec[j] doesn't overflow, define a weight vector. Otherwise,      *
    2092 * report that overflow appears. In the second case, test whether the  *
    2093 * the correctness of the new vector plays an important role           *
    2094 **********************************************************************/
    2095   kkk=0;
    2096   for(j=0; j<nRing; j++)
    2097     {
    2098     if(mpz_cmp(vec[j], sing_int_half) >= 0)
    2099       {
    2100       goto REDUCTION;
    2101       }
    2102     }
    2103   checkRed = 1;
     1841
     1842  // check whether vec[j]>2147483647, reduce it
     1843
    21041844  for (j=0; j<nRing; j++)
    2105     {
    2106       (*diff_weight)[j] = mpz_get_si(vec[j]);
    2107     }
    2108   goto SIMPLIFY_GCD;
    2109 
    2110   REDUCTION:
     1845  {
     1846    (*diff_weight)[j] = mpz_get_si(vec[j]);
     1847  }
     1848  while(MivAbsMax(diff_weight) > 100000000)
     1849  {
     1850    for (j=0; j<nRing; j++)
     1851    {
     1852      if(mpz_cmp_si(ggt,1)==0)
     1853      {
     1854        (*diff_weight1)[j] = floor(0.001*(*diff_weight)[j] + 0.5);
     1855#ifdef  NEXT_VECTORS_CC
     1856        Print("\n//** MwalkNextWeightCC: vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
     1857#endif
     1858      }
     1859      else
     1860      {
     1861        mpz_divexact(vec[j], vec[j], ggt);
     1862        (*diff_weight1)[j] = floor(0.001*(*diff_weight)[j] + 0.5);
     1863#ifdef  NEXT_VECTORS_CC
     1864        Print("\n//** MwalkNextWeightCC: vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
     1865#endif
     1866      }
     1867    }
     1868
     1869    if(test_w_in_ConeCC(G,diff_weight1) != 0)
     1870    {
     1871#ifdef  NEXT_VECTORS_CC
     1872      Print("\n//** MwalkNextWeightCC: changed weight vector in correct cone.\n");
     1873#endif
     1874      for (j=0; j<nRing; j++)
     1875      {
     1876        (*diff_weight)[j] = (*diff_weight1)[j];
     1877      }
     1878
     1879      // simplify the vectors curr_weight and diff_weight (C-int)
     1880      gcd_tmp = simplify_gcd(curr_weight,diff_weight);
     1881      if(gcd_tmp != 1)
     1882      {
     1883        for (j=0; j<nRing; j++)
     1884        {
     1885          (*curr_weight)[j] =  (*curr_weight)[j]/gcd_tmp;
     1886          (*diff_weight)[j] =  (*diff_weight)[j]/gcd_tmp;
     1887          mpz_set_si(vec[j],(*diff_weight)[j]);
     1888        }
     1889      }
     1890    }
     1891    else
     1892    {
     1893#ifdef  NEXT_VECTORS_CC
     1894      Print("\n//** MwalkNextWeightCC: changed weight vector not in correct cone.\n");
     1895#endif
     1896
     1897      for (j=0; j<nRing; j++)
     1898      {
     1899        (*diff_weight)[j] = mpz_get_si(vec[j]);
     1900      }
     1901      break;
     1902    }
     1903  }
     1904
    21111905  for (j=0; j<nRing; j++)
    21121906  {
    2113     (*diff_weight)[j] = mpz_get_si(vec[j]);
    2114   }
    2115   while(MivAbsMax(diff_weight) >= 5)
    2116   {
    2117     for (j=0; j<nRing; j++)
    2118     {
    2119       if(mpz_cmp_si(ggt,1)==0)
    2120       {
    2121         (*diff_weight1)[j] = floor(0.1*(*diff_weight)[j] + 0.5);
    2122         // Print("\n//  vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
    2123       }
    2124       else
    2125       {
    2126         mpz_divexact(vec[j], vec[j], ggt);
    2127         (*diff_weight1)[j] = floor(0.1*(*diff_weight)[j] + 0.5);
    2128         // Print("\n//  vector[%d] = %d \n",j+1, (*diff_weight1)[j]);
    2129       }
    2130 /*
    2131       if((*diff_weight1)[j] == 0)
    2132       {
    2133         kkk = kkk + 1;
    2134       }
    2135 */
    2136     }
    2137 
    2138 
    2139 /*
    2140     if(kkk > nRing - 1)
    2141     {
    2142       // diff_weight was reduced to zero
    2143       // Print("\n // MwalkNextWeightCC: geaenderter Vector gleich Null! \n");
    2144       goto TEST_OVERFLOW;
    2145     }
    2146 */
    2147 
    2148     if(test_w_in_ConeCC(G,diff_weight1) != 0)
    2149     {
    2150       Print("\n// MwalkNextWeightCC: geaenderter vector liegt in Groebnerkegel! \n");
    2151       for (j=0; j<nRing; j++)
    2152       {
    2153         (*diff_weight)[j] = (*diff_weight1)[j];
    2154       }
    2155       if(MivAbsMax(diff_weight) < 5)
    2156       {
    2157         checkRed = 1;
    2158         goto SIMPLIFY_GCD;
    2159       }
    2160     }
    2161     else
    2162     {
    2163       // Print("\n// MwalkNextWeightCC: geaenderter vector liegt nicht in Groebnerkegel! \n");
    2164       break;
    2165     }
    2166   }
    2167 
    2168  TEST_OVERFLOW:
    2169 
    2170   for (j=0; j<nRing; j++)
    2171   {
    2172     if(mpz_cmp(vec[j], sing_int)>=0)
     1907    if((mpz_cmp(vec[j], sing_int)>=0) && ((*diff_weight)[j] > 2147483647))
    21731908    {
    21741909      if(Overflow_Error == FALSE)
    21751910      {
    21761911        Overflow_Error = TRUE;
    2177         PrintS("\n// ** OVERFLOW in \"MwalkNextWeightCC\": ");
     1912        PrintS("\n//** MwalkNextWeightCC: OVERFLOW: ");
    21781913        mpz_out_str( stdout, 10, vec[j]);
    2179         PrintS(" is greater than 2147483647 (max. integer representation)\n");
    2180         //Print("//  So vector[%d] := %d is wrong!!\n",j+1, vec[j]);// vec[j] is mpz_t
     1914        PrintS(" is greater than 2147483647 (max. integer representation)");
     1915        Print("\n//  So vector[%d] := %d may be wrong.\n",j+1, vec[j]);
    21811916      }
    21821917    }
     
    21841919
    21851920 FINISH:
    2186    delete diff_weight1;
    2187    mpz_clear(t_zaehler);
    2188    mpz_clear(t_nenner);
    2189    mpz_clear(s_zaehler);
    2190    mpz_clear(s_nenner);
    2191    mpz_clear(sntz);
    2192    mpz_clear(sztn);
    2193    mpz_clear(temp);
    2194    mpz_clear(MwWd);
    2195    mpz_clear(deg_w0_p1);
    2196    mpz_clear(deg_d0_p1);
    2197    mpz_clear(ggt);
    2198    omFree(vec);
    2199    mpz_clear(sing_int_half);
    2200    mpz_clear(sing_int);
    2201    mpz_clear(dcw);
    2202    mpz_clear(t_null);
    2203 
    2204 
    2205 
     1921  delete diff_weight1;
     1922  mpz_clear(t_zaehler);
     1923  mpz_clear(t_nenner);
     1924  mpz_clear(s_zaehler);
     1925  mpz_clear(s_nenner);
     1926  mpz_clear(sntz);
     1927  mpz_clear(sztn);
     1928  mpz_clear(temp);
     1929  mpz_clear(MwWd);
     1930  mpz_clear(deg_w0_p1);
     1931  mpz_clear(deg_d0_p1);
     1932  mpz_clear(ggt);
     1933  omFree(vec);
     1934  mpz_clear(sing_int);
     1935  mpz_clear(dcw);
     1936  mpz_clear(t_null);
     1937 
    22061938  if(Overflow_Error == FALSE)
    22071939  {
    22081940    Overflow_Error = nError;
    22091941  }
    2210  rComplete(currRing);
    2211   for(kkk=0; kkk<IDELEMS(G);kkk++)
    2212   {
    2213     poly p=G->m[kkk];
     1942  rComplete(currRing);
     1943  for(j=0; j<IDELEMS(G); j++)
     1944  {
     1945    poly p=G->m[j];
    22141946    while(p!=NULL)
    22151947    {
     
    22511983}
    22521984
    2253 /**************************************************************
    2254  * define and execute a new ring which order is (a(vb),a(va),lp,C) *
    2255  * ************************************************************/
    2256 static void VMrHomogeneous(intvec* va, intvec* vb)
     1985/*****************************************************
     1986 * define and execute a new ring with ordering (M,C) *
     1987 *****************************************************/
     1988static ring VMatrDefault(intvec* va)
    22571989{
    22581990
     
    22722004  r->cf  = currRing->cf;
    22732005  r->N   = currRing->N;
     2006
    22742007  int nb = 4;
    2275 
    22762008
    22772009  //names
     
    22842016  }
    22852017
     2018  /*weights: entries for 3 blocks: NULL Made:???*/
     2019  r->wvhdl = (int **)omAlloc0(nb * sizeof(int_ptr));
     2020  r->wvhdl[0] = (int*) omAlloc(nv*nv*sizeof(int));
     2021  r->wvhdl[1] =NULL; // (int*) omAlloc(nv*sizeof(int));
     2022  r->wvhdl[2]=NULL;
     2023  r->wvhdl[3]=NULL;
     2024  for(i=0; i<nv*nv; i++)
     2025    r->wvhdl[0][i] = (*va)[i];
     2026
     2027  /* order: a,lp,C,0 */
     2028  r->order = (int *) omAlloc(nb * sizeof(int *));
     2029  r->block0 = (int *)omAlloc0(nb * sizeof(int *));
     2030  r->block1 = (int *)omAlloc0(nb * sizeof(int *));
     2031
     2032  // ringorder a for the first block: var 1..nv
     2033  r->order[0]  = ringorder_M;
     2034  r->block0[0] = 1;
     2035  r->block1[0] = nv;
     2036
     2037  // ringorder C for the second block
     2038  r->order[1]  = ringorder_C;
     2039  r->block0[1] = 1;
     2040  r->block1[1] = nv;
     2041
     2042
     2043// ringorder C for the third block: var 1..nv
     2044  r->order[2]  = ringorder_C;
     2045  r->block0[2] = 1;
     2046  r->block1[2] = nv;
     2047
     2048
     2049  // the last block: everything is 0
     2050  r->order[3]  = 0;
     2051
     2052  // polynomial ring
     2053  r->OrdSgn    = 1;
     2054
     2055  // complete ring intializations
     2056
     2057  rComplete(r);
     2058
     2059  //rChangeCurrRing(r);
     2060  return r;
     2061}
     2062
     2063/***********************************************************
     2064 * define and execute a new ring with ordering (a(vb),M,C) *
     2065 ***********************************************************/
     2066static ring VMatrRefine(intvec* va, intvec* vb)
     2067{
     2068
     2069  if ((currRing->ppNoether)!=NULL)
     2070  {
     2071    pDelete(&(currRing->ppNoether));
     2072  }
     2073  if (((sLastPrinted.rtyp>BEGIN_RING) && (sLastPrinted.rtyp<END_RING)) ||
     2074      ((sLastPrinted.rtyp==LIST_CMD)&&(lRingDependend((lists)sLastPrinted.data))))
     2075  {
     2076    sLastPrinted.CleanUp();
     2077  }
     2078
     2079  ring r = (ring) omAlloc0Bin(sip_sring_bin);
     2080  int i, nv = currRing->N;
     2081  int nvs = nv*nv;
     2082  r->cf  = currRing->cf;
     2083  r->N   = currRing->N;
     2084
     2085  int nb = 4;
     2086
     2087  //names
     2088  char* Q; // In order to avoid the corrupted memory, do not change.
     2089  r->names = (char **) omAlloc0(nv * sizeof(char_ptr));
     2090  for(i=0; i<nv; i++)
     2091  {
     2092    Q = currRing->names[i];
     2093    r->names[i]  = omStrDup(Q);
     2094  }
     2095
     2096  /*weights: entries for 3 blocks: NULL Made:???*/
     2097  r->wvhdl = (int **)omAlloc0(nb * sizeof(int_ptr));
     2098  r->wvhdl[0] = (int*) omAlloc(nv*sizeof(int));
     2099  r->wvhdl[1] = (int*) omAlloc(nvs*sizeof(int));
     2100  r->wvhdl[2]=NULL;
     2101  r->wvhdl[3]=NULL;
     2102  for(i=0; i<nvs; i++)
     2103  {
     2104    r->wvhdl[1][i] = (*va)[i];
     2105  }
     2106  for(i=0; i<nv; i++)
     2107  {
     2108    r->wvhdl[0][i] = (*vb)[i];
     2109  }
     2110  /* order: a,lp,C,0 */
     2111  r->order = (int *) omAlloc(nb * sizeof(int *));
     2112  r->block0 = (int *)omAlloc0(nb * sizeof(int *));
     2113  r->block1 = (int *)omAlloc0(nb * sizeof(int *));
     2114
     2115  // ringorder a for the first block: var 1..nv
     2116  r->order[0]  = ringorder_a;
     2117  r->block0[0] = 1;
     2118  r->block1[0] = nv;
     2119
     2120  // ringorder M for the second block: var 1..nv
     2121  r->order[1]  = ringorder_M;
     2122  r->block0[1] = 1;
     2123  r->block1[1] = nv;
     2124
     2125  // ringorder C for the third block: var 1..nv
     2126  r->order[2]  = ringorder_C;
     2127  r->block0[2] = 1;
     2128  r->block1[2] = nv;
     2129
     2130
     2131  // the last block: everything is 0
     2132  r->order[3]  = 0;
     2133
     2134  // polynomial ring
     2135  r->OrdSgn    = 1;
     2136
     2137  // complete ring intializations
     2138
     2139  rComplete(r);
     2140
     2141  //rChangeCurrRing(r);
     2142  return r;
     2143}
     2144
     2145/****************************************************************
     2146 * define and execute a new ring with ordering (a(va),Wp(vb),C) *
     2147 * **************************************************************/
     2148
     2149static ring VMrRefine(intvec* va, intvec* vb)
     2150{
     2151
     2152  if ((currRing->ppNoether)!=NULL)
     2153  {
     2154    pDelete(&(currRing->ppNoether));
     2155  }
     2156  if (((sLastPrinted.rtyp>BEGIN_RING) && (sLastPrinted.rtyp<END_RING)) ||
     2157      ((sLastPrinted.rtyp==LIST_CMD)&&(lRingDependend((lists)sLastPrinted.data))))
     2158  {
     2159    sLastPrinted.CleanUp();
     2160  }
     2161
     2162  ring r = (ring) omAlloc0Bin(sip_sring_bin);
     2163  int i, nv = currRing->N;
     2164
     2165  r->cf  = currRing->cf;
     2166  r->N   = currRing->N;
     2167  //int nb = nBlocks(currRing)  + 1;
     2168  int nb = 4;
     2169
     2170  //names
     2171  char* Q; // In order to avoid the corrupted memory, do not change.
     2172  r->names = (char **) omAlloc0(nv * sizeof(char_ptr));
     2173  for(i=0; i<nv; i++)
     2174  {
     2175    Q = currRing->names[i];
     2176    r->names[i]  = omStrDup(Q);
     2177  }
     2178
    22862179  //weights: entries for 3 blocks: NULL Made:???
    22872180  r->wvhdl = (int **)omAlloc0(nb * sizeof(int_ptr));
    22882181  r->wvhdl[0] = (int*) omAlloc(nv*sizeof(int));
    2289   r->wvhdl[1] = (int*) omAlloc((nv-1)*sizeof(int));
    2290 
    2291   for(i=0; i<nv-1; i++)
    2292   {
     2182  r->wvhdl[1] = (int*) omAlloc(nv*sizeof(int));
     2183
     2184  for(i=0; i<nv; i++)
     2185  {
     2186    r->wvhdl[0][i] = (*va)[i];
    22932187    r->wvhdl[1][i] = (*vb)[i];
    2294     r->wvhdl[0][i] = (*va)[i];
    2295   }
    2296   r->wvhdl[0][nv] = (*va)[nv];
     2188  }
     2189  r->wvhdl[2]=NULL;
     2190  r->wvhdl[3]=NULL;
    22972191
    22982192  // order: (1..1),a,lp,C
     
    23062200  r->block1[0] = nv;
    23072201
    2308  // ringorder a for the second block: var 2..nv
    2309   r->order[1]  = ringorder_a;
    2310   r->block0[1] = 2;
     2202 // ringorder Wp for the second block: var 1..nv
     2203  r->order[1]  = ringorder_Wp;
     2204  r->block0[1] = 1;
    23112205  r->block1[1] = nv;
    23122206
    2313   // ringorder lp for the third block: var 2..nv
    2314   r->order[2]  = ringorder_lp;
    2315   r->block0[2] = 2;
     2207  // ringorder lp for the third block: var 1..nv
     2208  r->order[2]  = ringorder_C;
     2209  r->block0[2] = 1;
    23162210  r->block1[2] = nv;
    23172211
     
    23202214  // especially, by ring syz_ring=rCurrRingAssure_SyzComp();
    23212215  // therefore, nb  must be (nBlocks(currRing)  + 1)
    2322   r->order[3]  = ringorder_C;
     2216  r->order[3]  = 0;
    23232217
    23242218  // polynomial ring
     
    23262220
    23272221  // complete ring intializations
    2328 
     2222 
    23292223  rComplete(r);
    23302224
    2331   rChangeCurrRing(r);
    2332 }
    2333 
     2225  //rChangeCurrRing(r);
     2226  return r;
     2227}
    23342228
    23352229/**************************************************************
    23362230 * define and execute a new ring which order is (a(va),lp,C)  *
    23372231 * ************************************************************/
    2338 static void VMrDefault(intvec* va)
     2232//static void VMrDefault(intvec* va)
     2233static ring VMrDefault(intvec* va)
    23392234{
    23402235
     
    24002295
    24012296  // complete ring intializations
    2402 
     2297 
    24032298  rComplete(r);
    24042299
    2405   rChangeCurrRing(r);
     2300  //rChangeCurrRing(r);
     2301  return r;
    24062302}
    24072303
     
    24632359
    24642360  /* complete ring intializations */
    2465 
     2361 
    24662362  rComplete(r);
    24672363
     
    25922488  r->OrdSgn    = 1;
    25932489
    2594 
    2595 //   if (rParameter(currRing)!=NULL)
    2596 //   {
    2597 //     r->cf->extRing->qideal->m[0]=p_Copy(currRing->cf->extRing->qideal->m[0], currRing->cf->extRing);
    2598 //     int l=rPar(currRing);
    2599 //     r->cf->extRing->names=(char **)omAlloc(l*sizeof(char_ptr));
    2600 //
    2601 //     for(i=l-1;i>=0;i--)
    2602 //     {
    2603 //       rParameter(r)[i]=omStrDup(rParameter(currRing)[i]);
    2604 //     }
    2605 //   }
    2606 
    26072490  // complete ring intializations
    2608 
     2491 
    26092492  rComplete(r);
    26102493
     
    26192502}
    26202503
    2621 //unused
    2622 /**************************************************************
    2623  * check wheather one or more components of a vector are zero *
    2624  **************************************************************/
    2625 //#if 0
    2626 static int isNolVector(intvec* hilb)
    2627 {
    2628   int i;
    2629   for(i=hilb->length()-1; i>=0; i--)
    2630   {
    2631     if((* hilb)[i]==0)
    2632     {
    2633       return 1;
    2634     }
    2635   }
    2636   return 0;
    2637 }
    2638 //#endif
     2504
    26392505
    26402506/******************************  Februar 2002  ****************************
     
    29252791  for(i=IDELEMS(G)-1; i>=0; i--)
    29262792  {
    2927 #if 0
    2928     if(pLength(G->m[i])>2)
    2929     {
    2930       return 1;
    2931     }
    2932 #else
    29332793    if((G->m[i]!=NULL) /* len >=0 */
    29342794       && (G->m[i]->next!=NULL) /* len >=1 */
     
    29382798       )
    29392799    {
    2940     return 1;
    2941     }
    2942 #endif
     2800      return 1;
     2801    }
    29432802  }
    29442803  return 0;
     
    30132872  for(i=nG-1; i>=0; i--)
    30142873  {
    3015 #if 0
    3016     poly t;
    3017     if((t=pSub(pCopy(H0->m[i]), pCopy(H1->m[i]))) != NULL)
    3018     {
    3019       pDelete(&t);
     2874    if(!pEqualPolys(H0->m[i],H1->m[i]))
     2875    {
    30202876      return 0;
    30212877    }
    3022     pDelete(&t);
    3023 #else
    3024     if(!pEqualPolys(H0->m[i],H1->m[i]))
    3025     {
    3026       return 0;
    3027     }
    3028 #endif
    30292878  }
    30302879  return 1;
     
    30562905  return result;
    30572906}
    3058 #endif
    3059 
    3060 //unused
     2907
     2908
     2909
    30612910/************************************************************************
    30622911 * perturb the weight vector iva w.r.t. the ideal G.                    *
     
    30662915 *  d := (2*maxdeg*maxdeg + (nV+1)*maxdeg)*m;                           *
    30672916 ************************************************************************/
    3068 #if 0
    30692917static intvec* TranPertVector(ideal G, intvec* iva)
    30702918{
     
    31242972#ifdef INVEPS_SMALL_IN_TRAN
    31252973  if(mpz_cmp_ui(ndeg, nV)>0 && nV > 3)
    3126   {
     2974  { 
    31272975    mpz_cdiv_q_ui(ndeg, ndeg, nV);
    31282976  }
     
    32073055  return repr_vector;
    32083056}
    3209 #endif
    3210 
    3211 //unused
    3212 #if 0
     3057
     3058
     3059
     3060
    32133061static intvec* TranPertVector_lp(ideal G)
    32143062{
     
    33033151  return repr_vector;
    33043152}
    3305 #endif
    3306 
    3307 //unused
    3308 #if 0
     3153
     3154
    33093155static intvec* RepresentationMatrix_Dp(ideal G, intvec* M)
    33103156{
     
    34043250 *****************************************************************************/
    34053251
    3406 //unused
    3407 #if 0
    3408 static int testnegintvec(intvec* v)
    3409 {
    3410   int n = v->length();
    3411   int i;
    3412   for(i=0; i<n; i++)
    3413   {
    3414     if((*v)[i]<0)
    3415     {
    3416       return(1);
    3417     }
    3418   }
    3419   return(0);
    3420 }
    3421 #endif
    3422 
    3423 // npwinc = 0, if curr_weight doesn't stay in the correct Groebner cone
    34243252static ideal Rec_LastGB(ideal G, intvec* curr_weight,
    34253253                        intvec* orig_target_weight, int tp_deg, int npwinc)
     
    37873615    nstep ++;
    37883616    to = clock();
    3789     /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
     3617    // compute an initial form ideal of <G> w.r.t. "curr_vector"
    37903618    Gomega = MwalkInitialForm(G, curr_weight);
    37913619    xtif=xtif+clock()-to;
    3792 #if 0
    3793     if(Overflow_Error == TRUE)
    3794     {
    3795       for(i=nV-1; i>=0; i--)
    3796         (*curr_weight)[i] = (*extra_curr_weight)[i];
    3797       delete extra_curr_weight;
    3798       goto LAST_GB_ALT2;
    3799     }
    3800 #endif
     3620
    38013621    oldRing = currRing;
    38023622
    3803     /* define a new ring that its ordering is "(a(curr_weight),lp) */
     3623    // define a new ring that its ordering is "(a(curr_weight),lp)
    38043624    if (rParameter(currRing) != NULL)
    38053625    {
     
    38543674    if(Overflow_Error == TRUE)
    38553675    {
    3856       /*
    3857         ivString(next_weight, "omega");
    3858         PrintS("\n// ** The weight vector does NOT stay in Cone!!\n");
    3859       */
    38603676#ifdef TEST_OVERFLOW
    38613677      goto  TEST_OVERFLOW_OI;
    38623678#endif
    3863 
    38643679      newRing = currRing;
    38653680      if (rParameter(currRing) != NULL)
     
    39223737  TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
    39233738
    3924   Print("\n// pSetm_Error = (%d)", ErrorCheck());
     3739  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
    39253740  //Print("\n// Overflow_Error? (%d)", nOverflow_Error);
    39263741  Print("\n// Awalk2 took %d steps!!", nstep);
     
    39563771{
    39573772  int i, weight_norm;
     3773  //int randCount=0;
    39583774  int nV = currRing->N;
    39593775  intvec* next_weight2;
    39603776  intvec* next_weight22 = new intvec(nV);
     3777  intvec* result = new intvec(nV);
     3778
     3779  //compute a perturbed next weight vector "next_weight1"
     3780  intvec* next_weight1 = MkInterRedNextWeight(MPertVectors(G,MivMatrixOrderRefine(curr_weight,target_weight),pert_deg),target_weight,G);
     3781  //compute a random next weight vector "next_weight2"
     3782  while(1)
     3783  {
     3784    weight_norm = 0;
     3785    while(weight_norm == 0)
     3786    {
     3787      for(i=0; i<nV; i++)
     3788      {
     3789        (*next_weight22)[i] = rand() % 60000 - 30000;
     3790        weight_norm = weight_norm + (*next_weight22)[i]*(*next_weight22)[i];
     3791      }
     3792      weight_norm = 1 + floor(sqrt(weight_norm));
     3793    }
     3794    for(i=0; i<nV; i++)
     3795    {
     3796      if((*next_weight22)[i] < 0)
     3797      {
     3798        (*next_weight22)[i] = 1 + (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
     3799      }
     3800      else
     3801      {
     3802        (*next_weight22)[i] = (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
     3803      }
     3804    }
     3805    if(test_w_in_ConeCC(G, next_weight22) == 1)
     3806    {
     3807      next_weight2 = MkInterRedNextWeight(next_weight22,target_weight,G);
     3808      delete next_weight22;
     3809      break;
     3810    }
     3811  }
     3812  // compute "usual" next weight vector
    39613813  intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
    3962   if(MivComp(next_weight, target_weight) == 1)
    3963   {
    3964     return(next_weight);
    3965   }
    3966   else
    3967   {
    3968     //compute a perturbed next weight vector "next_weight1"
    3969     intvec* next_weight1 = MkInterRedNextWeight(MPertVectors(G, MivMatrixOrder(curr_weight), pert_deg), target_weight, G);
    3970     //Print("\n // size of next_weight1 = %d", sizeof((*next_weight1)));
    3971 
    3972     //compute a random next weight vector "next_weight2"
    3973     while(1)
    3974     {
    3975       weight_norm = 0;
    3976       while(weight_norm == 0)
    3977       {
    3978         for(i=0; i<nV; i++)
    3979         {
    3980           //Print("\n//  next_weight[%d]  = %d", i, (*next_weight)[i]);
    3981           (*next_weight22)[i] = rand() % 60000 - 30000;
    3982           weight_norm = weight_norm + (*next_weight22)[i]*(*next_weight22)[i];
    3983         }
    3984         weight_norm = 1 + floor(sqrt(weight_norm));
    3985       }
    3986 
    3987       for(i=nV-1; i>=0; i--)
    3988       {
    3989         if((*next_weight22)[i] < 0)
    3990         {
    3991           (*next_weight22)[i] = 1 + (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
    3992         }
    3993         else
    3994         {
    3995           (*next_weight22)[i] = (*curr_weight)[i] + floor(weight_rad*(*next_weight22)[i]/weight_norm);
    3996         }
    3997       //Print("\n//  next_weight22[%d]  = %d", i, (*next_weight22)[i]);
    3998       }
    3999 
    4000       if(test_w_in_ConeCC(G, next_weight22) == 1)
    4001       {
    4002         //Print("\n//MWalkRandomNextWeight: next_weight2 im Kegel\n");
    4003         next_weight2 = MkInterRedNextWeight(next_weight22, target_weight, G);
    4004         delete next_weight22;
    4005         break;
    4006       }
    4007     }
    4008     intvec* result = new intvec(nV);
    4009     ideal G_test = MwalkInitialForm(G, next_weight);
     3814  ideal G_test = MwalkInitialForm(G, next_weight);
     3815  ideal G_test2 = MwalkInitialForm(G, next_weight2);
     3816
     3817  // compare next weights
     3818  if(Overflow_Error == FALSE)
     3819  {
    40103820    ideal G_test1 = MwalkInitialForm(G, next_weight1);
    4011     ideal G_test2 = MwalkInitialForm(G, next_weight2);
    4012 
    4013     // compare next_weights
    40143821    if(IDELEMS(G_test1) < IDELEMS(G_test))
    40153822    {
    4016       if(IDELEMS(G_test2) <= IDELEMS(G_test1)) // |G_test2| <= |G_test1| < |G_test|
    4017       {
     3823      if(IDELEMS(G_test2) < IDELEMS(G_test1))
     3824      {
     3825        // |G_test2| < |G_test1| < |G_test|
    40183826        for(i=0; i<nV; i++)
    40193827        {
     
    40213829        }
    40223830      }
    4023       else // |G_test1| < |G_test|, |G_test1| < |G_test2|
    4024       {
     3831      else
     3832      {
     3833        // |G_test1| < |G_test|, |G_test1| <= |G_test2|
    40253834        for(i=0; i<nV; i++)
    40263835        {
    40273836          (*result)[i] = (*next_weight1)[i];
    40283837        }
    4029       }
     3838      }   
    40303839    }
    40313840    else
    40323841    {
    4033       if(IDELEMS(G_test2) <= IDELEMS(G_test)) // |G_test2| <= |G_test| <= |G_test1|
     3842      if(IDELEMS(G_test2) < IDELEMS(G_test)) // |G_test2| < |G_test| <= |G_test1|
    40343843      {
    40353844        for(i=0; i<nV; i++)
     
    40383847        }
    40393848      }
    4040       else // |G_test| <= |G_test1|, |G_test| < |G_test2|
    4041       {
     3849      else
     3850      {
     3851        // |G_test| < |G_test1|, |G_test| <= |G_test2|
    40423852        for(i=0; i<nV; i++)
    40433853        {
     
    40463856      }
    40473857    }
     3858    idDelete(&G_test1);
     3859  }
     3860  else
     3861  {
     3862    Overflow_Error = FALSE;
     3863    if(IDELEMS(G_test2) < IDELEMS(G_test))
     3864    {
     3865      for(i=1; i<nV; i++)
     3866      {
     3867        (*result)[i] = (*next_weight2)[i];
     3868      }
     3869    }
     3870    else
     3871    {
     3872      for(i=0; i<nV; i++)
     3873      {
     3874        (*result)[i] = (*next_weight)[i];
     3875      }
     3876    }
     3877  }
     3878  idDelete(&G_test);
     3879  idDelete(&G_test2);
     3880  if(test_w_in_ConeCC(G, result) == 1)
     3881  {
     3882    delete next_weight2;
    40483883    delete next_weight;
    40493884    delete next_weight1;
    4050     idDelete(&G_test);
    4051     idDelete(&G_test1);
    4052     idDelete(&G_test2);
    4053     if(test_w_in_ConeCC(G, result) == 1)
    4054     {
    4055       delete next_weight2;
    4056       return result;
    4057     }
    4058     else
    4059     {
    4060       delete result;
    4061       return next_weight2;
    4062     }
     3885    return result;
     3886  }
     3887  else
     3888  {
     3889    delete result;
     3890    delete next_weight2;
     3891    delete next_weight1;
     3892    return next_weight;
    40633893  }
    40643894}
     
    40663896
    40673897/***************************************************************************
    4068  * The procedur REC_GB_Mwalk computes a GB for <G> w.r.t. the weight order *
     3898 * The procedure REC_GB_Mwalk computes a GB for <G> w.r.t. the weight order*
    40693899 * otw, where G is a reduced GB w.r.t. the weight order cw.                *
    40703900 * The new procedur Mwalk calls REC_GB.                                    *
     
    41173947    if(test_G_GB_walk(H0_tmp,H1)==1)
    41183948    {
    4119       //Print("\n//REC_GB_Mwalk: input in %d-th recursive is a GB!\n",tp_deg);
     3949      Print("\n//REC_GB_Mwalk: input in %d-th recursive is a GB!\n",tp_deg);
    41203950      idDelete(&H0_tmp);
    41213951      idDelete(&H1);
     
    41513981      goto NEXT_STEP;
    41523982    }
    4153     //Print("\n//REC_GB_Mwalk: Entering the %d-th step in the %d-th recursive:\n",nwalk,tp_deg);
     3983    Print("\n//REC_GB_Mwalk: Entering the %d-th step in the %d-th recursive:\n",nwalk,tp_deg);
    41543984    to = clock();
    41553985    // compute an initial form ideal of <G> w.r.t. "curr_vector"
     
    42264056    // compute a next weight vector
    42274057    intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
    4228 
     4058 
    42294059
    42304060    xtnw = xtnw + clock() - to;
     
    42364066    if(Overflow_Error == TRUE)
    42374067    {
    4238       //PrintS("\n//REC_GB_Mwalk: The computed vector does NOT stay in the correct cone!!\n");
     4068      PrintS("\n//REC_GB_Mwalk: The computed vector does NOT stay in the correct cone!!\n");
    42394069      nnwinC = 0;
    42404070      if(tp_deg == nV)
     
    43514181}
    43524182
    4353 
    4354 // THE NEW GROEBNER WALK ALGORITHM
    4355 // Groebnerwalk with a recursive "second" alternative GW, called REC_GB_Mwalk that only computes the last reduced GB
    4356 ideal Mwalk(ideal Go, intvec* curr_weight, intvec* target_weight)
    4357 {
     4183/*******************************
     4184 * THE GROEBNER WALK ALGORITHM *
     4185 *******************************/
     4186ideal Mwalk(ideal Go, intvec* orig_M, intvec* target_M, ring baseRing)
     4187{
     4188  BITSET save1 = si_opt_1; // save current options
     4189  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
     4190  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
     4191  //si_opt_1|=(Sy_bit(OPT_REDTAIL)|Sy_bit(OPT_REDSB));
    43584192  Set_Error(FALSE);
    43594193  Overflow_Error = FALSE;
    4360   //Print("// pSetm_Error = (%d)", ErrorCheck());
    4361 
     4194#ifdef TIME_TEST
    43624195  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
    43634196  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
    43644197  tinput = clock();
    43654198  clock_t tim;
    4366   nstep=0;
    4367   int i;
    4368   int nV = currRing->N;
    4369   int nwalk=0;
    4370   int endwalks=0;
    4371 
    4372   ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
    4373   //ideal G1;
    4374   //ring endRing;
    4375   ring newRing, oldRing;
    4376   intvec* ivNull = new intvec(nV);
    4377   intvec* exivlp = Mivlp(nV);
    4378 #ifndef BUCHBERGER_ALG
    4379   intvec* hilb_func;
    4380 #endif
    4381   intvec* tmp_weight = new intvec(nV);
    4382   for(i=nV-1; i>=0; i--)
    4383     (*tmp_weight)[i] = (*curr_weight)[i];
    4384 
    4385    // to avoid (1,0,...,0) as the target vector
    4386   intvec* last_omega = new intvec(nV);
    4387   for(i=nV-1; i>0; i--)
    4388     (*last_omega)[i] = 1;
    4389   (*last_omega)[0] = 10000;
    4390 
    4391   ring XXRing = currRing;
    4392 
    4393   to = clock();
    4394   // the monomial ordering of this current ring would be "dp"
    4395   G = MstdCC(Go);
    4396   tostd = clock()-to;
    4397 
    4398   if(currRing->order[0] == ringorder_a)
    4399     goto NEXT_VECTOR;
    4400 
    4401   while(1)
    4402   {
    4403     nwalk ++;
    4404     nstep ++;
    4405     to = clock();
    4406     // compute an initial form ideal of <G> w.r.t. "curr_vector"
    4407     Gomega = MwalkInitialForm(G, curr_weight);
    4408     tif = tif + clock()-to;
    4409     oldRing = currRing;
    4410 
    4411     if(endwalks == 1)
    4412     {
    4413       /* compute a reduced Groebner basis of Gomega w.r.t. >>_cw by
    4414          the recursive changed perturbation walk alg. */
    4415       tim = clock();
    4416       /*
    4417         Print("\n// **** Grï¿œbnerwalk took %d steps and ", nwalk);
    4418         PrintS("\n// **** call the rec. Pert. Walk to compute a red GB of:");
    4419         idElements(Gomega, "G_omega");
    4420       */
    4421 
    4422       if(MivSame(exivlp, target_weight)==1)
    4423         M = REC_GB_Mwalk(idCopy(Gomega), tmp_weight, curr_weight, 2,1);
    4424       else
    4425         goto NORMAL_GW;
    4426       /*
    4427         Print("\n//  time for the last std(Gw)  = %.2f sec",
    4428         ((double) (clock()-tim)/1000000));
    4429         PrintS("\n// ***************************************************\n");
    4430       */
    4431 #ifdef CHECK_IDEAL_MWALK
    4432       idElements(Gomega, "G_omega");
    4433       headidString(Gomega, "Gw");
    4434       idElements(M, "M");
    4435       //headidString(M, "M");
    4436 #endif
    4437       to = clock();
    4438       F = MLifttwoIdeal(Gomega, M, G);
    4439       xtlift = xtlift + clock() - to;
    4440 
    4441       idDelete(&Gomega);
    4442       idDelete(&M);
    4443       idDelete(&G);
    4444 
    4445       oldRing = currRing;
    4446 
    4447       /* create a new ring newRing */
    4448        if (rParameter(currRing) != NULL)
    4449        {
    4450          DefRingPar(curr_weight);
    4451        }
    4452        else
    4453        {
    4454          VMrDefault(curr_weight);
    4455        }
    4456       newRing = currRing;
    4457       F1 = idrMoveR(F, oldRing,currRing);
    4458     }
    4459     else
    4460     {
    4461     NORMAL_GW:
    4462 #ifndef  BUCHBERGER_ALG
    4463       if(isNolVector(curr_weight) == 0)
    4464       {
    4465         hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    4466       }
    4467       else
    4468       {
    4469         hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    4470       }
    4471 #endif // BUCHBERGER_ALG
    4472 
    4473       // define a new ring that its ordering is "(a(curr_weight),lp)
    4474       if (rParameter(currRing) != NULL)
    4475       {
    4476         DefRingPar(curr_weight);
    4477       }
    4478       else
    4479       {
    4480         VMrDefault(curr_weight);
    4481       }
    4482       newRing = currRing;
    4483       Gomega1 = idrMoveR(Gomega, oldRing,currRing);
    4484 
    4485       to = clock();
    4486       // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
    4487 #ifdef  BUCHBERGER_ALG
    4488       M = MstdhomCC(Gomega1);
    4489 #else
    4490       M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    4491       delete hilb_func;
    4492 #endif // BUCHBERGER_ALG
    4493       tstd = tstd + clock() - to;
    4494 
    4495       // change the ring to oldRing
    4496       rChangeCurrRing(oldRing);
    4497       M1 =  idrMoveR(M, newRing,currRing);
    4498       Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
    4499 
    4500       to = clock();
    4501       // 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.
    4502       F = MLifttwoIdeal(Gomega2, M1, G);
    4503       tlift = tlift + clock() - to;
    4504 
    4505       idDelete(&M1);
    4506       idDelete(&Gomega2);
    4507       idDelete(&G);
    4508 
    4509       // change the ring to newRing
    4510       rChangeCurrRing(newRing);
    4511       F1 = idrMoveR(F, oldRing,currRing);
    4512     }
    4513 
    4514     to = clock();
    4515     // reduce the Groebner basis <G> w.r.t. new ring
    4516     G = kInterRedCC(F1, NULL);
    4517     if(endwalks != 1)
    4518     {
    4519       tred = tred + clock() - to;
    4520     }
    4521     else
    4522     {
    4523       xtred = xtred + clock() - to;
    4524     }
    4525     idDelete(&F1);
    4526     if(endwalks == 1)
    4527     {
    4528       break;
    4529     }
    4530   NEXT_VECTOR:
    4531     to = clock();
    4532     // compute a next weight vector
    4533     intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
    4534     tnw = tnw + clock() - to;
    4535 #ifdef PRINT_VECTORS
    4536     MivString(curr_weight, target_weight, next_weight);
    4537 #endif
    4538 
    4539     //if(test_w_in_ConeCC(G, next_weight) != 1)
    4540     if(Overflow_Error == TRUE)
    4541     {
    4542       newRing = currRing;
    4543       PrintS("\n// ** The computed vector does NOT stay in Cone!!\n");
    4544 
    4545       if (rParameter(currRing) != NULL)
    4546       {
    4547         DefRingPar(target_weight);
    4548       }
    4549       else
    4550       {
    4551         VMrDefault(target_weight);
    4552       }
    4553       F1 = idrMoveR(G, newRing,currRing);
    4554       G = MstdCC(F1);
    4555       idDelete(&F1);
    4556 
    4557       newRing = currRing;
    4558       break;
    4559     }
    4560 
    4561     if(MivComp(next_weight, ivNull) == 1)
    4562     {
    4563       newRing = currRing;
    4564       delete next_weight;
    4565       break;
    4566     }
    4567     if(MivComp(next_weight, target_weight) == 1)
    4568     {
    4569       endwalks = 1;
    4570     }
    4571     for(i=nV-1; i>=0; i--)
    4572     {
    4573       (*tmp_weight)[i] = (*curr_weight)[i];
    4574       (*curr_weight)[i] = (*next_weight)[i];
    4575     }
    4576     delete next_weight;
    4577   }
    4578   rChangeCurrRing(XXRing);
    4579   G = idrMoveR(G, newRing,currRing);
    4580 
    4581   delete tmp_weight;
    4582   delete ivNull;
    4583   delete exivlp;
    4584 
    4585 #ifdef TIME_TEST
    4586   TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
    4587 
    4588   Print("\n// pSetm_Error = (%d)", ErrorCheck());
    4589   Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
    4590 #endif
    4591   return(G);
    4592 }
    4593 
    4594 // 07.11.2012
    4595 // THE RANDOM WALK ALGORITHM
    4596 ideal Mrwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int pert_deg)
    4597 {
    4598   Set_Error(FALSE);
    4599   Overflow_Error = FALSE;
    4600   //Print("// pSetm_Error = (%d)", ErrorCheck());
    4601 
    4602   clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
    4603   xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
    4604   tinput = clock();
    4605   clock_t tim;
     4199#endif
    46064200  nstep=0;
    46074201  int i,nwalk,endwalks = 0;
    4608   int nV = currRing->N;
    4609 
    4610   ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
    4611   //ideal G1;
    4612   //ring endRing;
    4613   ring newRing, oldRing;
     4202  int nV = baseRing->N;
     4203
     4204  ideal Gomega, M, F, Gomega1, Gomega2, M1; //, F1;
     4205  ring newRing;
     4206  ring XXRing = baseRing;
    46144207  intvec* ivNull = new intvec(nV);
     4208  intvec* curr_weight = new intvec(nV);
     4209  intvec* target_weight = new intvec(nV);
    46154210  intvec* exivlp = Mivlp(nV);
    46164211  intvec* tmp_weight = new intvec(nV);
    4617   for(i=nV-1; i>=0; i--)
    4618   {
    4619     (*tmp_weight)[i] = (*curr_weight)[i];
     4212  for(i=0; i<nV; i++)
     4213  {
     4214    (*tmp_weight)[i] = (*target_M)[i];
     4215  }
     4216  for(i=0; i<nV; i++)
     4217  {
     4218    (*curr_weight)[i] = (*orig_M)[i];
     4219    (*target_weight)[i] = (*target_M)[i];
    46204220  }
    46214221#ifndef BUCHBERGER_ALG
     
    46294229  (*last_omega)[0] = 10000;
    46304230#endif
    4631   ring XXRing = currRing;
    4632 
     4231  rComplete(currRing);
     4232#ifdef CHECK_IDEAL_MWALK
     4233    idString(Go,"Go");
     4234#endif
     4235#ifdef TIME_TEST
    46334236  to = clock();
    4634   G = MstdCC(Go);
     4237#endif
     4238     if(orig_M->length() == nV)
     4239      {
     4240        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4241      }
     4242      else
     4243      {
     4244        newRing = VMatrDefault(orig_M);
     4245      }
     4246  rChangeCurrRing(newRing);
     4247  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
     4248  baseRing = currRing;
     4249#ifdef TIME_TEST
    46354250  tostd = clock()-to;
    4636 
    4637   //if(currRing->order[0] == ringorder_a)
    4638   //  goto NEXT_VECTOR;
    4639 nwalk = 0;
     4251#endif
     4252
     4253  nwalk = 0;
    46404254  while(1)
    46414255  {
    46424256    nwalk ++;
    46434257    nstep ++;
     4258#ifdef TIME_TEST
    46444259    to = clock();
     4260#endif
    46454261#ifdef CHECK_IDEAL_MWALK
    46464262    idString(G,"G");
    46474263#endif
    4648     Gomega = MwalkInitialForm(G, curr_weight);// compute an initial form ideal of <G> w.r.t. "curr_vector"
    4649     tif = tif + clock()-to;
    4650     oldRing = currRing;
     4264    Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
     4265#ifdef TIME_TEST
     4266    tif = tif + clock()-to; //time for computing initial form ideal
     4267#endif
    46514268#ifdef CHECK_IDEAL_MWALK
    4652     idString(Gomega,"G_omega");
    4653 #endif
    4654     if(endwalks == 1)
    4655     {
    4656       // compute a reduced Groebner basis of Gomega w.r.t. >>_cw by the recursive changed perturbation walk alg.
    4657       tim = clock();
    4658       Print("\n//Mrwalk: Groebnerwalk took %d steps.\n", nwalk);
    4659       //PrintS("\n//Mrwalk: call the rec. Pert. Walk to compute a red GB of:");
    4660       //idString(Gomega, "G_omega");
    4661       M = REC_GB_Mwalk(idCopy(Gomega), tmp_weight, curr_weight,pert_deg,1);
    4662       Print("\n//Mrwalk: time for the last std(Gw)  = %.2f sec\n",((double) (clock()-tim)/1000000));
    4663 
     4269    idString(Gomega,"Gomega");
     4270#endif
     4271#ifndef  BUCHBERGER_ALG
     4272    if(isNolVector(curr_weight) == 0)
     4273    {
     4274      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
     4275    }   
     4276    else
     4277    {
     4278      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
     4279    }
     4280#endif
     4281    if(nwalk == 1)
     4282    {
     4283      if(orig_M->length() == nV)
     4284      {
     4285        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4286      }
     4287      else
     4288      {
     4289        newRing = VMatrDefault(orig_M);
     4290      }
     4291    }
     4292    else
     4293    {
     4294     if(target_M->length() == nV)
     4295     {
     4296       newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
     4297     }
     4298     else
     4299     {
     4300       newRing = VMatrRefine(target_M,curr_weight);
     4301     }
     4302    }
     4303    rChangeCurrRing(newRing);
     4304    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
     4305    idDelete(&Gomega);
     4306    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
     4307#ifdef TIME_TEST
     4308    to = clock();
     4309#endif
     4310#ifndef  BUCHBERGER_ALG
     4311    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
     4312    delete hilb_func;
     4313#else
     4314    M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     4315#endif
     4316#ifdef TIME_TEST
     4317    tstd = tstd + clock() - to;
     4318#endif
     4319    idSkipZeroes(M);
    46644320#ifdef CHECK_IDEAL_MWALK
    4665       idString(Gomega, "G_omega");
    4666       idString(M, "M");
    4667 #endif
    4668       to = clock();
    4669       F = MLifttwoIdeal(Gomega, M, G);
    4670       xtlift = xtlift + clock() - to;
    4671 
     4321    PrintS("\n//** Mwalk: computed M.\n");
     4322    idString(M, "M");
     4323#endif
     4324    //change the ring to baseRing
     4325    rChangeCurrRing(baseRing);
     4326    M1 =  idrMoveR(M, newRing,currRing);
     4327    idDelete(&M);
     4328    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     4329    idDelete(&Gomega1);
     4330#ifdef TIME_TEST
     4331    to = clock();
     4332#endif
     4333    // 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
     4334    F = MLifttwoIdeal(Gomega2, M1, G);
     4335#ifdef TIME_TEST
     4336    tlift = tlift + clock() - to;
     4337#endif
     4338#ifdef CHECK_IDEAL_MWALK
     4339    idString(F, "F");
     4340#endif
     4341    idDelete(&Gomega2);
     4342    idDelete(&M1);
     4343    rChangeCurrRing(newRing); // change the ring to newRing
     4344    G = idrMoveR(F,baseRing,currRing);
     4345    idDelete(&F);
     4346    baseRing = currRing;
     4347#ifdef TIME_TEST
     4348    to = clock();
     4349#endif
     4350    //G = kStd(F1,NULL,testHomog,NULL,NULL,0,0,NULL);
     4351#ifdef TIME_TEST
     4352    tstd = tstd + clock() - to;
     4353#endif
     4354    idSkipZeroes(G);
     4355#ifdef CHECK_IDEAL_MWALK
     4356    idString(G, "G");
     4357#endif
     4358#ifdef TIME_TEST
     4359    to = clock();
     4360#endif
     4361    intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
     4362#ifdef TIME_TEST
     4363    tnw = tnw + clock() - to;
     4364#endif
     4365#ifdef PRINT_VECTORS
     4366    MivString(curr_weight, target_weight, next_weight);
     4367#endif
     4368    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)
     4369    {
     4370#ifdef CHECK_IDEAL_MWALK
     4371      PrintS("\n//** Mwalk: entering last cone.\n");
     4372#endif
     4373      Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
     4374      if(target_M->length() == nV)
     4375      {
     4376        newRing = VMrDefault(target_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4377      }
     4378      else
     4379      {
     4380        newRing = VMatrDefault(target_M);
     4381      }
     4382      rChangeCurrRing(newRing);
     4383      Gomega1 = idrMoveR(Gomega, baseRing,currRing);
    46724384      idDelete(&Gomega);
     4385#ifdef CHECK_IDEAL_MWALK
     4386      idString(Gomega1, "Gomega");
     4387#endif
     4388      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     4389#ifdef CHECK_IDEAL_MWALK
     4390      idString(M,"M");
     4391#endif
     4392      rChangeCurrRing(baseRing);
     4393      M1 =  idrMoveR(M, newRing,currRing);
    46734394      idDelete(&M);
    4674       idDelete(&G);
    4675 
    4676       oldRing = currRing;
    4677       VMrDefault(curr_weight); //define a new ring with ordering "(a(curr_weight),lp)
    4678 
    4679        /*if (rParameter(currRing) != NULL)
    4680        {
    4681          DefRingPar(curr_weight);
    4682        }
    4683        else
    4684        {
    4685          VMrDefault(curr_weight);
    4686        }*/
    4687       newRing = currRing;
    4688       F1 = idrMoveR(F, oldRing,currRing);
    4689     }
    4690     else
    4691     {
    4692 #ifndef  BUCHBERGER_ALG
    4693       if(isNolVector(curr_weight) == 0)
    4694       {
    4695         hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
    4696       }
    4697       else
    4698       {
    4699         hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    4700       }
    4701 #endif
    4702 /*
    4703       if (rParameter(currRing) != NULL)
    4704       {
    4705         DefRingPar(curr_weight);
    4706       }
    4707       else
    4708       {
    4709         VMrDefault(curr_weight);
    4710       }*/
    4711 
    4712       VMrDefault(curr_weight); //define a new ring with ordering "(a(curr_weight),lp)
    4713       newRing = currRing;
    4714       Gomega1 = idrMoveR(Gomega, oldRing,currRing);
    4715 #ifdef CHECK_IDEAL_MWALK
    4716       idString(Gomega1, "G_omega1");
    4717 #endif
    4718       // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
    4719       to = clock();
    4720 #ifndef  BUCHBERGER_ALG
    4721       M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    4722       delete hilb_func;
    4723 #else
    4724       //M = MstdhomCC(Gomega1);
    4725       //M = MstdCC(Gomega1);
    4726       //M = kStd(Gomega1, NULL, testHomog,NULL, NULL,0,0,curr_weight);
    4727       M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
    4728 #endif
    4729       tstd = tstd + clock() - to;
    4730 #ifdef CHECK_IDEAL_MWALK
    4731       idString(M, "M");
    4732 #endif
    4733       //change the ring to oldRing
    4734       rChangeCurrRing(oldRing);
    4735       M1 =  idrMoveR(M, newRing,currRing);
    4736 #ifdef CHECK_IDEAL_MWALK
    4737       idString(M1, "M1");
    4738 #endif
    4739       Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
    4740 
    4741       to = clock();
    4742       // 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
     4395      Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     4396      idDelete(&Gomega1);
    47434397      F = MLifttwoIdeal(Gomega2, M1, G);
    47444398#ifdef CHECK_IDEAL_MWALK
    4745       idString(F, "F");
    4746 #endif
    4747       tlift = tlift + clock() - to;
    4748 
     4399      idString(F,"F");
     4400#endif
     4401      idDelete(&Gomega2);
    47494402      idDelete(&M1);
    4750       idDelete(&Gomega2);
    4751       idDelete(&G);
    4752 
    47534403      rChangeCurrRing(newRing); // change the ring to newRing
    4754       F1 = idrMoveR(F,oldRing,currRing);
    4755     }
    4756 
    4757     to = clock();
    4758     G = kInterRedCC(F1, NULL); //reduce the Groebner basis <G> w.r.t. new ring
    4759 #ifdef CHECK_IDEAL_MWALK
    4760     idString(G, "G");
    4761 #endif
    4762     idDelete(&F1);
    4763     if(endwalks == 1)
    4764     {
    4765       xtred = xtred + clock() - to;
    4766       break;
    4767     }
    4768     else
    4769     {
     4404      G = idrMoveR(F,baseRing,currRing);
     4405      idDelete(&F);
     4406      baseRing = currRing;
     4407      si_opt_1 = save1; //set original options, e. g. option(RedSB)
     4408      idSkipZeroes(G);
     4409#ifdef TIME_TEST
     4410      to = clock();
     4411#endif
     4412      if(si_opt_1 == (Sy_bit(OPT_REDSB)))
     4413      {
     4414        G = kInterRedCC(G,NULL); //reduce the Groebner basis <G> w.r.t. currRing, if option(redSB) is set
     4415      }
     4416#ifdef TIME_TEST
    47704417      tred = tred + clock() - to;
    4771     }
    4772 
    4773   //NEXT_VECTOR:
    4774     to = clock();
    4775     //intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
    4776    intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, pert_deg);
    4777 
    4778   tnw = tnw + clock() - to;
    4779 //#ifdef PRINT_VECTORS
    4780   MivString(curr_weight, target_weight, next_weight);
    4781 //#endif
    4782     if(Overflow_Error == TRUE)
    4783     {
    4784       newRing = currRing;
    4785       PrintS("\n//Mrwalk: The computed vector does NOT stay in Cone!!\n");
    4786 
    4787       if (rParameter(currRing) != NULL)
    4788       {
    4789         DefRingPar(target_weight);
    4790       }
    4791       else
    4792       {
    4793         VMrDefault(target_weight);  //define a new ring with ordering "(a(curr_weight),lp)
    4794       }
    4795       F1 = idrMoveR(G, newRing,currRing);
    4796       G = MstdCC(F1);
    4797       idDelete(&F1);
    4798 
    4799       newRing = currRing;
    4800       break;
    4801     }
    4802 
    4803     if(MivComp(next_weight, ivNull) == 1)
    4804     {
    4805       newRing = currRing;
     4418#endif
     4419      idSkipZeroes(G);
    48064420      delete next_weight;
    48074421      break;
    4808     }
    4809     if(MivComp(next_weight, target_weight) == 1)
    4810     {
    4811       endwalks = 1;
    4812     }
     4422#ifdef CHECK_IDEAL_MWALK
     4423      PrintS("\n//** Mwalk: last cone.\n");
     4424#endif
     4425    }
     4426#ifdef CHECK_IDEAL_MWALK
     4427    PrintS("\n//** Mwalk: update weight vectors.\n");
     4428#endif
    48134429    for(i=nV-1; i>=0; i--)
    48144430    {
     
    48194435  }
    48204436  rChangeCurrRing(XXRing);
    4821   G = idrMoveR(G, newRing,currRing);
    4822 
     4437  ideal result = idrMoveR(G,baseRing,currRing);
     4438  idDelete(&G);
     4439/*#ifdef CHECK_IDEAL_MWALK
     4440  pDelete(&p);
     4441#endif*/
    48234442  delete tmp_weight;
    48244443  delete ivNull;
     
    48284447#endif
    48294448#ifdef TIME_TEST
     4449  Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
    48304450  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
    4831 
    4832   Print("\n// pSetm_Error = (%d)", ErrorCheck());
    4833   Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
    4834 #endif
    4835   return(G);
    4836 }
    4837 
    4838 //unused
    4839 #if 0
    4840 ideal Mwalk_tst(ideal Go, intvec* curr_weight, intvec* target_weight)
    4841 {
    4842   //clock_t tinput=clock();
    4843   //idString(Go,"Ginp");
    4844   int i, nV = currRing->N;
    4845   int nwalk=0, endwalks=0;
    4846 
    4847   ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
    4848   // ideal G1; ring endRing;
    4849   ring newRing, oldRing;
     4451  Print("\n//** Mwalk: Ergebnis.\n");
     4452  //Print("\n// pSetm_Error = (%d)", ErrorCheck());
     4453  //Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
     4454#endif
     4455  return(result);
     4456}
     4457
     4458/*****************************
     4459 * THE RANDOM WALK ALGORITHM *
     4460 *****************************/
     4461ideal Mrwalk(ideal Go, intvec* orig_M, intvec* target_M, int weight_rad, int pert_deg, ring baseRing)
     4462{
     4463  BITSET save1 = si_opt_1; // save current options
     4464  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
     4465  si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
     4466  //si_opt_1|=(Sy_bit(OPT_REDTAIL)|Sy_bit(OPT_REDSB));
     4467  Set_Error(FALSE);
     4468  Overflow_Error = FALSE;
     4469#ifdef TIME_TEST
     4470  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
     4471  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
     4472  tinput = clock();
     4473  clock_t tim;
     4474#endif
     4475  nstep=0;
     4476  int i,nwalk,endwalks = 0;
     4477  int nV = baseRing->N;
     4478
     4479  ideal Gomega, M, F, Gomega1, Gomega2, M1; //, F1;
     4480  ring newRing;
     4481  ring XXRing = baseRing;
    48504482  intvec* ivNull = new intvec(nV);
    4851   ring XXRing = currRing;
    4852 
     4483  intvec* curr_weight = new intvec(nV);
     4484  intvec* target_weight = new intvec(nV);
     4485  intvec* exivlp = Mivlp(nV);
    48534486  intvec* tmp_weight = new intvec(nV);
    4854   for(i=nV-1; i>=0; i--)
    4855   {
    4856     (*tmp_weight)[i] = (*curr_weight)[i];
    4857   }
    4858   /* the monomial ordering of this current ring would be "dp" */
    4859   G = MstdCC(Go);
     4487#ifdef CHECK_IDEAL_MWALK
     4488  poly p;
     4489#endif
     4490  for(i=0; i<nV; i++)
     4491  {
     4492    (*tmp_weight)[i] = (*target_M)[i];
     4493  }
     4494  for(i=0; i<nV; i++)
     4495  {
     4496    (*curr_weight)[i] = (*orig_M)[i];
     4497    (*target_weight)[i] = (*target_M)[i];
     4498  }
    48604499#ifndef BUCHBERGER_ALG
    48614500  intvec* hilb_func;
    4862 #endif
    4863   /* to avoid (1,0,...,0) as the target vector */
     4501   // to avoid (1,0,...,0) as the target vector
    48644502  intvec* last_omega = new intvec(nV);
    48654503  for(i=nV-1; i>0; i--)
     4504  {
    48664505    (*last_omega)[i] = 1;
     4506  }
    48674507  (*last_omega)[0] = 10000;
    4868 
     4508#endif
     4509  rComplete(currRing);
     4510#ifdef CHECK_IDEAL_MWALK
     4511  for(i=0; i<IDELEMS(Go); i++)
     4512  {
     4513    poly p=Go->m[i];
     4514    while(p!=NULL)
     4515    {
     4516      p_Setm(p,currRing);
     4517      pIter(p);
     4518    }
     4519    pDelete(&p);
     4520  }
     4521    idString(Go,"Go");
     4522#endif
     4523#ifdef TIME_TEST
     4524  to = clock();
     4525#endif
     4526     if(orig_M->length() == nV)
     4527      {
     4528        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4529      }
     4530      else
     4531      {
     4532        newRing = VMatrDefault(orig_M);
     4533      }
     4534  rChangeCurrRing(newRing);
     4535  ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
     4536  baseRing = currRing;
     4537#ifdef TIME_TEST
     4538  tostd = clock()-to;
     4539#endif
     4540
     4541  nwalk = 0;
    48694542  while(1)
    48704543  {
    48714544    nwalk ++;
    4872     //Print("\n// Entering the %d-th step:", nwalk);
    4873     //Print("\n// ring r[%d] = %s;", nwalk, rString(currRing));
     4545    nstep ++;
     4546#ifdef TIME_TEST
     4547    to = clock();
     4548#endif
     4549#ifdef CHECK_IDEAL_MWALK
    48744550    idString(G,"G");
    4875     /* compute an initial form ideal of <G> w.r.t. "curr_vector" */
    4876     Gomega = MwalkInitialForm(G, curr_weight);
    4877     //ivString(curr_weight, "omega");
    4878     idString(Gomega,"Gw");
    4879 
     4551#endif
     4552    Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
     4553#ifdef TIME_TEST
     4554    tif = tif + clock()-to; //time for computing initial form ideal
     4555#endif
     4556#ifdef CHECK_IDEAL_MWALK
     4557    idString(Gomega,"Gomega");
     4558#endif
    48804559#ifndef  BUCHBERGER_ALG
    48814560    if(isNolVector(curr_weight) == 0)
     4561    {
    48824562      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
     4563    }   
    48834564    else
     4565    {
    48844566      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    4885 #endif // BUCHBERGER_ALG
    4886 
    4887 
    4888     oldRing = currRing;
    4889 
    4890     /* define a new ring that its ordering is "(a(curr_weight),lp) */
    4891     VMrDefault(curr_weight);
    4892     newRing = currRing;
    4893 
    4894     Gomega1 = idrMoveR(Gomega, oldRing,currRing);
    4895 
    4896     /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
    4897 #ifdef  BUCHBERGER_ALG
    4898     M = MstdhomCC(Gomega1);
    4899 #else
     4567    }
     4568#endif
     4569    if(nwalk == 1)
     4570    {
     4571      if(orig_M->length() == nV)
     4572      {
     4573        newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4574      }
     4575      else
     4576      {
     4577        newRing = VMatrDefault(orig_M);
     4578      }
     4579    }
     4580    else
     4581    {
     4582     if(target_M->length() == nV)
     4583     {
     4584       newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
     4585     }
     4586     else
     4587     {
     4588       newRing = VMatrRefine(target_M,curr_weight);
     4589     }
     4590    }
     4591    rChangeCurrRing(newRing);
     4592    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
     4593    idDelete(&Gomega);
     4594    // compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
     4595#ifdef TIME_TEST
     4596    to = clock();
     4597#endif
     4598#ifndef  BUCHBERGER_ALG
    49004599    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    49014600    delete hilb_func;
    4902 #endif // BUCHBERGER_ALG
    4903 
    4904     idString(M,"M");
    4905 
    4906       /* change the ring to oldRing */
    4907     rChangeCurrRing(oldRing);
     4601#else
     4602    M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     4603#endif
     4604#ifdef TIME_TEST
     4605    tstd = tstd + clock() - to;
     4606#endif
     4607    idSkipZeroes(M);
     4608#ifdef CHECK_IDEAL_MWALK
     4609    idString(M, "M");
     4610#endif
     4611    //change the ring to baseRing
     4612    rChangeCurrRing(baseRing);
    49084613    M1 =  idrMoveR(M, newRing,currRing);
    4909     Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
    4910 
    4911       /* compute a representation of the generators of submod (M)
    4912          with respect to those of mod (Gomega).
    4913          Gomega is a reduced Groebner basis w.r.t. the current ring */
     4614    idDelete(&M);
     4615    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     4616    idDelete(&Gomega1);
     4617#ifdef TIME_TEST
     4618    to = clock();
     4619#endif
     4620    // 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
    49144621    F = MLifttwoIdeal(Gomega2, M1, G);
     4622#ifdef CHECK_IDEAL_MWALK
     4623    idString(F,"F");
     4624#endif
     4625#ifdef TIME_TEST
     4626    tlift = tlift + clock() - to;
     4627#endif
     4628    idDelete(&Gomega2);
    49154629    idDelete(&M1);
    4916     idDelete(&Gomega2);
    4917     idDelete(&G);
    4918     idString(F,"F");
    4919 
    4920     /* change the ring to newRing */
    4921     rChangeCurrRing(newRing);
    4922     F1 = idrMoveR(F, oldRing,currRing);
    4923 
    4924     /* reduce the Groebner basis <G> w.r.t. new ring */
    4925     G = kInterRedCC(F1, NULL);
    4926     //idSkipZeroes(G);//done by kInterRed
    4927     idDelete(&F1);
    4928     idString(G,"G");
    4929     if(endwalks == 1)
    4930       break;
    4931 
    4932     /* compute a next weight vector */
    4933     intvec* next_weight = MkInterRedNextWeight(curr_weight,target_weight,G);
     4630    rChangeCurrRing(newRing); // change the ring to newRing
     4631    G = idrMoveR(F,baseRing,currRing);
     4632    idDelete(&F);
     4633    baseRing = currRing;
     4634    idSkipZeroes(G);
     4635#ifdef CHECK_IDEAL_MWALK
     4636    idString(G, "G");
     4637#endif
     4638#ifdef TIME_TEST
     4639    to = clock();
     4640#endif
     4641    intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, pert_deg);
     4642#ifdef TIME_TEST
     4643    tnw = tnw + clock() - to;
     4644#endif
    49344645#ifdef PRINT_VECTORS
    49354646    MivString(curr_weight, target_weight, next_weight);
    49364647#endif
    49374648
    4938     if(MivComp(next_weight, ivNull) == 1)
    4939     {
     4649    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)
     4650    {
     4651#ifdef CHECK_IDEAL_MWALK
     4652      PrintS("\n//** Mrwalk: entering last cone.\n");
     4653#endif
     4654      Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
     4655      if(target_M->length() == nV)
     4656      {
     4657        newRing = VMrDefault(target_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4658      }
     4659      else
     4660      {
     4661        newRing = VMatrDefault(target_M);
     4662      }
     4663      rChangeCurrRing(newRing);
     4664      Gomega1 = idrMoveR(Gomega, baseRing,currRing);
     4665      idDelete(&Gomega);
     4666      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     4667      rChangeCurrRing(baseRing);
     4668      M1 =  idrMoveR(M, newRing,currRing);
     4669      idDelete(&M);
     4670      Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     4671      idDelete(&Gomega1);
     4672      F = MLifttwoIdeal(Gomega2, M1, G);
     4673      idDelete(&Gomega2);
     4674      idDelete(&M1);
     4675      rChangeCurrRing(newRing); // change the ring to newRing
     4676      G = idrMoveR(F,baseRing,currRing);
     4677      idDelete(&F);
     4678      baseRing = currRing;
     4679      si_opt_1 = save1; //set original options, e. g. option(RedSB)
     4680      idSkipZeroes(G);
     4681#ifdef TIME_TEST
     4682      to = clock();
     4683#endif
     4684      if(si_opt_1 == (Sy_bit(OPT_REDSB)))
     4685      {
     4686        G = kInterRedCC(G,NULL); //reduce the Groebner basis <G> w.r.t. currRing, if option(redSB) is set
     4687      }
     4688#ifdef TIME_TEST
     4689      tred = tred + clock() - to;
     4690#endif
     4691      idSkipZeroes(G);
    49404692      delete next_weight;
    49414693      break;
    49424694    }
    4943     if(MivComp(next_weight, target_weight) == 1)
    4944       endwalks = 1;
    4945 
    49464695    for(i=nV-1; i>=0; i--)
     4696    {
    49474697      (*tmp_weight)[i] = (*curr_weight)[i];
    4948 
    4949     /* 06.11.01 to free the memory: NOT Changed!!*/
    4950     for(i=nV-1; i>=0; i--)
    49514698      (*curr_weight)[i] = (*next_weight)[i];
     4699    }
    49524700    delete next_weight;
    49534701  }
    49544702  rChangeCurrRing(XXRing);
    4955   G = idrMoveR(G, newRing,currRing);
    4956 
     4703  ideal result = idrMoveR(G,baseRing,currRing);
     4704  idDelete(&G);
     4705#ifdef CHECK_IDEAL_MWALK
     4706  pDelete(&p);
     4707#endif
    49574708  delete tmp_weight;
    49584709  delete ivNull;
    4959   PrintLn();
    4960   return(G);
    4961 }
    4962 #endif
    4963 
    4964 /**************************************************************/
    4965 /*     Implementation of the perturbation walk algorithm      */
    4966 /**************************************************************/
    4967 /* If the perturbed target weight vector or an intermediate weight vector
    4968    doesn't stay in the correct Groebner cone, we have only
    4969    a reduced Groebner basis for the given ideal with respect to
    4970    a monomial order which differs to the given order.
    4971    Then we have to compute the wanted  reduced Groebner basis for it.
    4972    For this, we can use
    4973    1) the improved Buchberger algorithm or
    4974    2) the changed perturbation walk algorithm with a decreased degree.
    4975 */
    4976 // use kStd, if nP = 0, else call LastGB
    4977 ideal Mpwalk(ideal Go, int op_deg, int tp_deg,intvec* curr_weight,
    4978              intvec* target_weight, int nP)
    4979 {
    4980   Set_Error(FALSE  );
     4710  delete exivlp;
     4711#ifndef BUCHBERGER_ALG
     4712  delete last_omega;
     4713#endif
     4714#ifdef TIME_TEST
     4715  Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
     4716  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
     4717#endif
     4718  return(result);
     4719}
     4720
     4721/**************************************************************************
     4722 * Implementation of the perturbation walk algorithm                      *
     4723 *                                                                        *
     4724 * If the perturbed target weight vector or an intermediate weight vector *
     4725 * doesn't stay in the correct Groebner cone, we have only                *
     4726 * a reduced Groebner basis for the given ideal with respect to           *
     4727 * a monomial order which differs to the given order.                     *
     4728 * Then we have to compute the wanted  reduced Groebner basis for it.     *
     4729 * For this, we can use                                                   *
     4730 * 1) the improved Buchberger algorithm or                                *
     4731 * 2) the changed perturbation walk algorithm with a decreased degree.    *
     4732 **************************************************************************/
     4733
     4734/***********************************
     4735 * THE PERTURBATION WALK ALGORITHM *
     4736 ***********************************/
     4737ideal Mpwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int op_deg, int tp_deg, ring baseRing)
     4738{
     4739  BITSET save1 = si_opt_1; // save current options
     4740  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
     4741  Set_Error(FALSE);
    49814742  Overflow_Error = FALSE;
    4982   //Print("// pSetm_Error = (%d)", ErrorCheck());
    4983 
    4984   clock_t  tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
    4985   xtextra=0;
     4743#ifdef TIME_TEST
     4744  clock_t tinput=0, tostd=0, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
    49864745  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
    49874746  tinput = clock();
    4988 
    49894747  clock_t tim;
    4990 
    4991   nstep = 0;
    4992   int i, ntwC=1, ntestw=1,  nV = currRing->N;
    4993   int endwalks=0;
    4994 
    4995   ideal Gomega, M, F, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
    4996   ring newRing, oldRing, TargetRing;
    4997   intvec* iv_M_dp;
    4998   intvec* iv_M_lp;
     4748#endif
     4749  int i,nwalk,nV = baseRing->N;
     4750  ideal G, Gomega, M, F, Gomega1, Gomega2, M1;
     4751  ring newRing;
     4752  ring XXRing = baseRing;
    49994753  intvec* exivlp = Mivlp(nV);
    50004754  intvec* orig_target = target_weight;
    50014755  intvec* pert_target_vector = target_weight;
    50024756  intvec* ivNull = new intvec(nV);
    5003   intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
     4757  intvec* tmp_weight = new intvec(nV);
     4758#ifdef CHECK_IDEAL_MWALK
     4759  poly p;
     4760#endif
     4761  for(i=0; i<nV; i++)
     4762  {
     4763    (*tmp_weight)[i] = (*curr_weight)[i];
     4764  }
    50044765#ifndef BUCHBERGER_ALG
    50054766  intvec* hilb_func;
    5006 #endif
    5007   intvec* next_weight;
    5008 
    5009   // to avoid (1,0,...,0) as the target vector
     4767   // to avoid (1,0,...,0) as the target vector
    50104768  intvec* last_omega = new intvec(nV);
    5011   for(i=nV-1; i>0; i--)
     4769  for(i=0 i<nV; i++)
     4770  {
    50124771    (*last_omega)[i] = 1;
     4772  }
    50134773  (*last_omega)[0] = 10000;
    5014 
    5015   ring XXRing = currRing;
    5016 
    5017 
     4774#endif
     4775  idString(Go,"Go");
     4776  baseRing = currRing;
     4777  newRing = VMrDefault(curr_weight);
     4778  rChangeCurrRing(newRing);
     4779  G = idrMoveR(Go,baseRing,currRing);
     4780#ifdef TIME_TEST
    50184781  to = clock();
    5019   /* perturbs the original vector */
    5020   if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
    5021   {
    5022     G = MstdCC(Go);
    5023     tostd = clock()-to;
    5024     if(op_deg != 1){
    5025       iv_M_dp = MivMatrixOrderdp(nV);
    5026       //ivString(iv_M_dp, "iv_M_dp");
    5027       curr_weight = MPertVectors(G, iv_M_dp, op_deg);
    5028     }
    5029   }
    5030   else
    5031   {
    5032     //define ring order := (a(curr_weight),lp);
    5033     if (rParameter(currRing) != NULL)
    5034       DefRingPar(curr_weight);
    5035     else
    5036       VMrDefault(curr_weight);
    5037 
    5038     G = idrMoveR(Go, XXRing,currRing);
    5039     G = MstdCC(G);
    5040     tostd = clock()-to;
    5041     if(op_deg != 1){
    5042       iv_M_dp = MivMatrixOrder(curr_weight);
    5043       curr_weight = MPertVectors(G, iv_M_dp, op_deg);
    5044     }
    5045   }
    5046   delete iv_dp;
    5047   if(op_deg != 1) delete iv_M_dp;
    5048 
    5049   ring HelpRing = currRing;
    5050 
    5051   /* perturbs the target weight vector */
     4782#endif
     4783  G = kStd(G,NULL,testHomog,NULL,NULL,0,0,NULL);
     4784  idSkipZeroes(G);
     4785#ifdef TIME_TEST
     4786  tostd = tostd + to - clock();
     4787#endif
     4788#ifdef CHECK_IDEAL_MWALK
     4789  idString(G,"G");
     4790#endif
     4791  if(op_deg >1)
     4792  {
     4793    if(MivComp(curr_weight,MivUnit(nV)) == 1) //ring order is "dp"
     4794    {
     4795      curr_weight = MPertVectors(G, MivMatrixOrderdp(nV), op_deg);
     4796    }
     4797    else //ring order is not "dp"
     4798    {
     4799      curr_weight = MPertVectors(G, MivMatrixOrder(curr_weight), op_deg);
     4800    }
     4801  }
     4802  baseRing = currRing;
    50524803  if(tp_deg > 1 && tp_deg <= nV)
    50534804  {
    5054     if (rParameter(currRing) != NULL)
    5055       DefRingPar(target_weight);
    5056     else
    5057       VMrDefault(target_weight);
    5058 
    5059     TargetRing = currRing;
    5060     ssG = idrMoveR(G,HelpRing,currRing);
    5061     if(MivSame(target_weight, exivlp) == 1)
    5062     {
    5063       iv_M_lp = MivMatrixOrderlp(nV);
    5064       //ivString(iv_M_lp, "iv_M_lp");
    5065       //target_weight = MPertVectorslp(ssG, iv_M_lp, tp_deg);
    5066       target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
    5067     }
    5068     else
    5069     {
    5070       iv_M_lp = MivMatrixOrder(target_weight);
    5071       //target_weight = MPertVectorslp(ssG, iv_M_lp, tp_deg);
    5072       target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
    5073     }
    5074     delete iv_M_lp;
    50754805    pert_target_vector = target_weight;
    5076     rChangeCurrRing(HelpRing);
    5077     G = idrMoveR(ssG, TargetRing,currRing);
    5078   }
    5079   /*
    5080     Print("\n// Perturbationwalkalg. vom Gradpaar (%d,%d):",op_deg,tp_deg);
    5081     ivString(curr_weight, "new sigma");
    5082     ivString(target_weight, "new tau");
    5083   */
     4806  }
     4807#ifdef TIME_TEST
     4808  Print("\n//** Mpwalk: perturbation walk with degrees (%d,%d):",op_deg,tp_deg);
     4809  ivString(curr_weight, "new curr_weight");
     4810  ivString(target_weight, "new target_weight");
     4811#endif
     4812  nwalk = 0;
    50844813  while(1)
    50854814  {
    5086     nstep ++;
     4815    nwalk ++;
     4816#ifdef CHECK_IDEAL_MWALK
     4817    idString(G,"G");
     4818#endif
     4819#ifdef TIME_TEST
    50874820    to = clock();
    5088     /* compute an initial form ideal of <G> w.r.t. the weight vector
    5089        "curr_weight" */
    5090     Gomega = MwalkInitialForm(G, curr_weight);
    5091 
    5092 
    5093 #ifdef ENDWALKS
    5094     if(endwalks == 1){
    5095       Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
    5096       idElements(G, "G");
    5097       // idElements(Gomega, "Gw");
    5098       headidString(G, "G");
    5099       //headidString(Gomega, "Gw");
    5100     }
    5101 #endif
    5102 
    5103     tif = tif + clock()-to;
    5104 
     4821#endif
     4822    Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
     4823#ifdef TIME_TEST
     4824    tif = tif + clock()-to; //time for computing initial form ideal
     4825#endif
     4826#ifdef CHECK_IDEAL_MWALK
     4827    idString(Gomega,"G_omega");
     4828#endif
    51054829#ifndef  BUCHBERGER_ALG
    51064830    if(isNolVector(curr_weight) == 0)
     4831    {
    51074832      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
     4833    }   
    51084834    else
     4835    {
    51094836      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    5110 #endif // BUCHBERGER_ALG
    5111 
    5112     oldRing = currRing;
    5113 
    5114     // define a new ring with ordering "(a(curr_weight),lp)
    5115     if (rParameter(currRing) != NULL)
    5116       DefRingPar(curr_weight);
     4837    }
     4838#endif
     4839    if(nwalk == 1)
     4840    {
     4841      newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
     4842    }
    51174843    else
    5118       VMrDefault(curr_weight);
    5119 
    5120     newRing = currRing;
    5121     Gomega1 = idrMoveR(Gomega, oldRing,currRing);
    5122 
    5123 #ifdef ENDWALKS
    5124     if(endwalks==1)
    5125     {
    5126       Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
    5127       idElements(Gomega1, "Gw");
    5128       headidString(Gomega1, "headGw");
    5129       PrintS("\n// compute a rGB of Gw:\n");
    5130 
     4844    {
     4845      newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
     4846    }
     4847    rChangeCurrRing(newRing);
     4848    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
     4849    idDelete(&Gomega);
     4850#ifdef CHECK_IDEAL_MWALK
     4851    idString(Gomega1, "Gomega1");
     4852#endif
     4853    // compute a Groebner basis of <Gomega> w.r.t. "newRing"
     4854#ifdef TIME_TEST
     4855    to = clock();
     4856#endif
    51314857#ifndef  BUCHBERGER_ALG
    5132       ivString(hilb_func, "w");
    5133 #endif
    5134     }
    5135 #endif
    5136 
    5137     tim = clock();
    5138     to = clock();
    5139     /* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
    5140 #ifdef  BUCHBERGER_ALG
    5141     M = MstdhomCC(Gomega1);
    5142 #else
    51434858    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
    51444859    delete hilb_func;
    5145 #endif // BUCHBERGER_ALG
    5146 
    5147     if(endwalks == 1){
    5148       xtstd = xtstd+clock()-to;
    5149 #ifdef ENDWALKS
    5150       Print("\n// time for the last std(Gw)  = %.2f sec\n",
    5151             ((double) clock())/1000000 -((double)tim) /1000000);
    5152 #endif
    5153     }
    5154     else
    5155       tstd=tstd+clock()-to;
    5156 
    5157     /* change the ring to oldRing */
    5158     rChangeCurrRing(oldRing);
     4860#else
     4861    M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     4862#endif
     4863    idSkipZeroes(M);
     4864#ifdef TIME_TEST
     4865    tstd = tstd + clock() - to;
     4866#endif
     4867#ifdef CHECK_IDEAL_MWALK
     4868    idString(M, "M");
     4869#endif
     4870    //change the ring to baseRing
     4871    rChangeCurrRing(baseRing);
    51594872    M1 =  idrMoveR(M, newRing,currRing);
    5160     Gomega2 =  idrMoveR(Gomega1, newRing,currRing);
    5161 
    5162     //if(endwalks==1)  PrintS("\n// Lifting is working:..");
    5163 
    5164     to=clock();
    5165     /* compute a representation of the generators of submod (M)
    5166        with respect to those of mod (Gomega).
    5167        Gomega is a reduced Groebner basis w.r.t. the current ring */
     4873    idDelete(&M);
     4874#ifdef CHECK_IDEAL_MWALK
     4875    idString(M1, "M1");
     4876#endif
     4877    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     4878    idDelete(&Gomega1);
     4879#ifdef CHECK_IDEAL_MWALK
     4880    idString(Gomega2, "G_omega2");
     4881#endif
     4882    to = clock();
     4883    // 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
    51684884    F = MLifttwoIdeal(Gomega2, M1, G);
    5169     if(endwalks != 1)
    5170       tlift = tlift+clock()-to;
    5171     else
    5172       xtlift=clock()-to;
    5173 
    5174     idDelete(&M1);
    5175     idDelete(&Gomega2);
    5176     idDelete(&G);
    5177 
    5178     /* change the ring to newRing */
    5179     rChangeCurrRing(newRing);
    5180     F1 = idrMoveR(F, oldRing,currRing);
    5181 
    5182     //if(endwalks==1)PrintS("\n// InterRed is working now:");
    5183 
    5184     to=clock();
    5185     /* reduce the Groebner basis <G> w.r.t. new ring */
    5186     G = kInterRedCC(F1, NULL);
    5187     if(endwalks != 1)
    5188       tred = tred+clock()-to;
    5189     else
    5190       xtred=clock()-to;
    5191 
    5192     idDelete(&F1);
    5193 
    5194     if(endwalks == 1)
    5195       break;
    5196 
    5197     to=clock();
    5198     /* compute a next weight vector */
    5199     next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
    5200     tnw=tnw+clock()-to;
     4885    idSkipZeroes(F);
     4886#ifdef TIME_TEST
     4887    tlift = tlift + clock() - to;
     4888#endif
     4889#ifdef CHECK_IDEAL_MWALK
     4890    idString(F,"F");
     4891#endif
     4892    rChangeCurrRing(newRing); // change the ring to newRing
     4893    G = idrMoveR(F,baseRing,currRing);
     4894    idDelete(&F);
     4895    baseRing = currRing; // set baseRing equal to newRing
     4896#ifdef CHECK_IDEAL_MWALK
     4897    idString(G,"G");
     4898#endif
     4899#ifdef TIME_TEST
     4900    to = clock();
     4901#endif
     4902    intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
     4903#ifdef TIME_TEST
     4904    tnw = tnw + clock() - to;
     4905#endif
    52014906#ifdef PRINT_VECTORS
    52024907    MivString(curr_weight, target_weight, next_weight);
    52034908#endif
    5204 
    52054909    if(Overflow_Error == TRUE)
    52064910    {
    5207       ntwC = 0;
    5208       //ntestomega = 1;
    5209       //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
    5210       //idElements(G, "G");
     4911      PrintS("\n//**Mpwalk: OVERFLOW! The computed vector does not stay in cone, the result may be wrong.\n");
    52114912      delete next_weight;
    5212       goto FINISH_160302;
    5213     }
    5214     if(MivComp(next_weight, ivNull) == 1){
    5215       newRing = currRing;
     4913      break;
     4914    }
     4915    if(test_w_in_ConeCC(G,target_weight) == 1 || MivComp(next_weight, ivNull) == 1)
     4916    {
    52164917      delete next_weight;
    5217       //Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
    52184918      break;
    52194919    }
    5220     if(MivComp(next_weight, target_weight) == 1)
    5221       endwalks = 1;
    5222 
     4920    //update tmp_weight and curr_weight
    52234921    for(i=nV-1; i>=0; i--)
     4922    {
     4923      (*tmp_weight)[i] = (*curr_weight)[i];
    52244924      (*curr_weight)[i] = (*next_weight)[i];
    5225 
     4925    }
    52264926    delete next_weight;
    5227   }//while
    5228 
    5229   if(tp_deg != 1)
    5230   {
    5231   FINISH_160302:
    5232     if(MivSame(orig_target, exivlp) == 1)
    5233       if (rParameter(currRing) != NULL)
    5234         DefRingParlp();
    5235       else
    5236         VMrDefaultlp();
     4927  } //end of while-loop
     4928  Print("\n// Mpwalk took %d steps. Ring= %s;\n", nwalk, rString(currRing));
     4929  idSkipZeroes(G);
     4930  si_opt_1 = save1; //set original options, e. g. option(RedSB)
     4931  baseRing = currRing;
     4932  rChangeCurrRing(XXRing);
     4933  ideal Res = idrMoveR(G,baseRing,currRing);
     4934  delete tmp_weight;
     4935  delete ivNull;
     4936  delete exivlp;
     4937#ifndef BUCHBERGER_ALG
     4938  delete last_omega;
     4939#endif
     4940#ifdef TIME_TEST
     4941  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
     4942#endif
     4943
     4944  return(Res);
     4945}
     4946
     4947/*******************************************************
     4948 * THE PERTURBATION WALK ALGORITHM WITH RANDOM ELEMENT *
     4949 *******************************************************/
     4950ideal Mprwalk(ideal Go, intvec* curr_weight, intvec* target_weight, int weight_rad, int op_deg, int tp_deg, ring baseRing)
     4951{
     4952  BITSET save1 = si_opt_1; // save current options
     4953  si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
     4954  Set_Error(FALSE);
     4955  Overflow_Error = FALSE;
     4956#ifdef TIME_TEST
     4957  clock_t tinput=0, tostd=0, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
     4958  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
     4959  tinput = clock();
     4960  clock_t tim;
     4961#endif
     4962  int i,nwalk,nV = baseRing->N;
     4963
     4964  ideal G, Gomega, M, F, Gomega1, Gomega2, M1;
     4965  ring newRing;
     4966  ring XXRing = baseRing;
     4967  intvec* exivlp = Mivlp(nV);
     4968  intvec* orig_target = target_weight;
     4969  intvec* pert_target_vector = target_weight;
     4970  intvec* ivNull = new intvec(nV);
     4971  intvec* tmp_weight = new intvec(nV);
     4972#ifdef CHECK_IDEAL_MWALK
     4973  poly p;
     4974#endif
     4975  for(i=0; i<nV; i++)
     4976  {
     4977    (*tmp_weight)[i] = (*curr_weight)[i];
     4978  }
     4979#ifndef BUCHBERGER_ALG
     4980  intvec* hilb_func;
     4981   // to avoid (1,0,...,0) as the target vector
     4982  intvec* last_omega = new intvec(nV);
     4983  for(i=0 i<nV; i++)
     4984  {
     4985    (*last_omega)[i] = 1;
     4986  }
     4987  (*last_omega)[0] = 10000;
     4988#endif
     4989  baseRing = currRing;
     4990  newRing = VMrDefault(curr_weight);
     4991  rChangeCurrRing(newRing);
     4992  G = idrMoveR(Go,baseRing,currRing);
     4993#ifdef TIME_TEST
     4994  to = clock();
     4995#endif
     4996  G = kStd(G,NULL,testHomog,NULL,NULL,0,0,NULL);
     4997  idSkipZeroes(G);
     4998#ifdef TIME_TEST
     4999  tostd = tostd + to - clock();
     5000#endif
     5001#ifdef CHECK_IDEAL_MWALK
     5002  idString(G,"G");
     5003#endif
     5004  if(op_deg >1)
     5005  {
     5006    if(MivComp(curr_weight,MivUnit(nV)) == 1) //ring order is "dp"
     5007    {
     5008      curr_weight = MPertVectors(G, MivMatrixOrderdp(nV), op_deg);
     5009    }
     5010    else //ring order is not "dp"
     5011    {
     5012      curr_weight = MPertVectors(G, MivMatrixOrder(curr_weight), op_deg);
     5013    }
     5014  }
     5015  baseRing = currRing;
     5016  if(tp_deg > 1 && tp_deg <= nV)
     5017  {
     5018    pert_target_vector = target_weight;
     5019  }
     5020#ifdef CHECK_IDEAL_MWALK
     5021  ivString(curr_weight, "new curr_weight");
     5022  ivString(target_weight, "new target_weight");
     5023#endif
     5024  nwalk = 0;
     5025  while(1)
     5026  {
     5027    nwalk ++;
     5028#ifdef TIME_TEST
     5029    to = clock();
     5030#endif
     5031    Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
     5032#ifdef TIME_TEST
     5033    tif = tif + clock()-to; //time for computing initial form ideal
     5034#endif
     5035#ifdef CHECK_IDEAL_MWALK
     5036    idString(Gomega,"Gomega");
     5037#endif
     5038#ifndef  BUCHBERGER_ALG
     5039    if(isNolVector(curr_weight) == 0)
     5040    {
     5041      hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
     5042    }   
    52375043    else
    5238       if (rParameter(currRing) != NULL)
    5239         DefRingPar(orig_target);
    5240       else
    5241         VMrDefault(orig_target);
    5242 
    5243     TargetRing=currRing;
    5244     F1 = idrMoveR(G, newRing,currRing);
    5245 #ifdef CHECK_IDEAL
    5246       headidString(G, "G");
    5247 #endif
    5248 
    5249 
    5250     // check whether the pertubed target vector stays in the correct cone
    5251     if(ntwC != 0){
    5252       ntestw = test_w_in_ConeCC(F1, pert_target_vector);
    5253     }
    5254 
    5255     if( ntestw != 1 || ntwC == 0)
    5256     {
    5257       /*
    5258       if(ntestw != 1){
    5259         ivString(pert_target_vector, "tau");
    5260         PrintS("\n// ** perturbed target vector doesn't stay in cone!!");
    5261         Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
    5262         idElements(F1, "G");
    5263       }
    5264       */
    5265       // LastGB is "better" than the kStd subroutine
    5266       to=clock();
    5267       ideal eF1;
    5268       if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1){
    5269         // PrintS("\n// ** calls \"std\" to compute a GB");
    5270         eF1 = MstdCC(F1);
    5271         idDelete(&F1);
    5272       }
    5273       else {
    5274         // PrintS("\n// ** calls \"LastGB\" to compute a GB");
    5275         rChangeCurrRing(newRing);
    5276         ideal F2 = idrMoveR(F1, TargetRing,currRing);
    5277         eF1 = LastGB(F2, curr_weight, tp_deg-1);
    5278         F2=NULL;
    5279       }
    5280       xtextra=clock()-to;
    5281       ring exTargetRing = currRing;
    5282 
    5283       rChangeCurrRing(XXRing);
    5284       Eresult = idrMoveR(eF1, exTargetRing,currRing);
    5285     }
    5286     else{
    5287       rChangeCurrRing(XXRing);
    5288       Eresult = idrMoveR(F1, TargetRing,currRing);
    5289     }
    5290   }
    5291   else {
    5292     rChangeCurrRing(XXRing);
    5293     Eresult = idrMoveR(G, newRing,currRing);
    5294   }
     5044    {
     5045      hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
     5046    }
     5047#endif
     5048    if(nwalk == 1)
     5049    {
     5050      newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
     5051    }
     5052    else
     5053    {
     5054      newRing = VMrRefine(curr_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
     5055    }
     5056    rChangeCurrRing(newRing);
     5057    Gomega1 = idrMoveR(Gomega, baseRing,currRing);
     5058    idDelete(&Gomega);
     5059    // compute a Groebner basis of <Gomega> w.r.t. "newRing"
     5060#ifdef TIME_TEST
     5061    to = clock();
     5062#endif
     5063#ifndef  BUCHBERGER_ALG
     5064    M=kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
     5065    delete hilb_func;
     5066#else
     5067    M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     5068#endif
     5069    idSkipZeroes(M);
     5070#ifdef TIME_TEST
     5071    tstd = tstd + clock() - to;
     5072#endif
     5073#ifdef CHECK_IDEAL_MWALK
     5074    idString(M, "M");
     5075#endif
     5076    //change the ring to baseRing
     5077    rChangeCurrRing(baseRing);
     5078    M1 =  idrMoveR(M, newRing,currRing);
     5079    idDelete(&M);
     5080    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     5081    idDelete(&Gomega1);
     5082    to = clock();
     5083    // 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
     5084    F = MLifttwoIdeal(Gomega2, M1, G);
     5085    idSkipZeroes(F);
     5086#ifdef TIME_TEST
     5087    tlift = tlift + clock() - to;
     5088#endif
     5089#ifdef CHECK_IDEAL_MWALK
     5090    idString(F,"F");
     5091#endif
     5092    rChangeCurrRing(newRing); // change the ring to newRing
     5093    G = idrMoveR(F,baseRing,currRing);
     5094    idDelete(&F);
     5095    baseRing = currRing; // set baseRing equal to newRing
     5096#ifdef CHECK_IDEAL_MWALK
     5097    idString(G,"G");
     5098#endif
     5099#ifdef TIME_TEST
     5100    to = clock();
     5101#endif
     5102    intvec* next_weight = MWalkRandomNextWeight(G, curr_weight, target_weight, weight_rad, op_deg);
     5103#ifdef TIME_TEST
     5104    tnw = tnw + clock() - to;
     5105#endif
     5106#ifdef PRINT_VECTORS
     5107    MivString(curr_weight, target_weight, next_weight);
     5108#endif
     5109    if(Overflow_Error == TRUE)
     5110    {
     5111      PrintS("\n//**Mprwalk: OVERFLOW: The computed vector does not stay in cone, the result may be wrong.\n");
     5112      delete next_weight;
     5113      break;
     5114    }
     5115
     5116    if(test_w_in_ConeCC(G,target_weight) == 1 || MivComp(next_weight, ivNull) == 1)
     5117    {
     5118      delete next_weight;
     5119      break;
     5120    }
     5121    //update tmp_weight and curr_weight
     5122    for(i=nV-1; i>=0; i--)
     5123    {
     5124      (*tmp_weight)[i] = (*curr_weight)[i];
     5125      (*curr_weight)[i] = (*next_weight)[i];
     5126    }
     5127    delete next_weight;
     5128  } //end of while-loop
     5129  Print("\n// Mprwalk took %d steps. Ring= %s;\n", nwalk, rString(currRing));
     5130  idSkipZeroes(G);
     5131  si_opt_1 = save1; //set original options, e. g. option(RedSB)
     5132  baseRing = currRing;
     5133  rChangeCurrRing(XXRing);
     5134  ideal Res = idrMoveR(G,baseRing,currRing);
     5135  delete tmp_weight;
    52955136  delete ivNull;
    5296   if(tp_deg != 1)
    5297     delete target_weight;
    5298 
    5299   if(op_deg != 1 )
    5300     delete curr_weight;
    5301 
    53025137  delete exivlp;
     5138#ifndef BUCHBERGER_ALG
    53035139  delete last_omega;
    5304 
    5305 #ifdef TIME_TEST
    5306   TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
    5307              tnw+xtnw);
    5308 
    5309   Print("\n// pSetm_Error = (%d)", ErrorCheck());
    5310   Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep,  Overflow_Error);
    5311 #endif
    5312   return(Eresult);
     5140#endif
     5141#ifdef TIME_TEST
     5142  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
     5143#endif
     5144  return(Res);
     5145}
     5146
     5147poly div_with_remainder( poly f, poly g, ring r)
     5148{
     5149return singclap_pdivide ( f, g, r );
    53135150}
    53145151
     
    53325169int Xngleich;
    53335170
    5334 /***********************************************************************
    5335  * Perturb the start weight vector at the top level, i.e. nlev = 1     *
    5336  ***********************************************************************/
    5337 static ideal rec_fractal_call(ideal G, int nlev, intvec* omtmp)
    5338 {
    5339   Overflow_Error =  FALSE;
    5340   //Print("\n\n// Entering the %d-th recursion:", nlev);
    5341 
    5342   int i, nV = currRing->N;
    5343   ring new_ring, testring;
    5344   //ring extoRing;
    5345   ideal Gomega, Gomega1, Gomega2, F, F1, Gresult, Gresult1, G1, Gt;
    5346   int nwalks = 0;
    5347   intvec* Mwlp;
    5348 #ifndef BUCHBERGER_ALG
    5349   intvec* hilb_func;
    5350 #endif
    5351 //  intvec* extXtau;
    5352   intvec* next_vect;
    5353   intvec* omega2 = new intvec(nV);
    5354   intvec* altomega = new intvec(nV);
    5355 
    5356   //BOOLEAN isnewtarget = FALSE;
    5357 
    5358   // to avoid (1,0,...,0) as the target vector (Hans)
    5359   intvec* last_omega = new intvec(nV);
    5360   for(i=nV-1; i>0; i--)
    5361     (*last_omega)[i] = 1;
    5362   (*last_omega)[0] = 10000;
    5363 
    5364   intvec* omega = new intvec(nV);
    5365   for(i=0; i<nV; i++) {
    5366     if(Xsigma->length() == nV)
    5367       (*omega)[i] =  (*Xsigma)[i];
     5171/******************************
     5172 * THE FRACTAL WALK ALGORITHM *
     5173 ******************************/
     5174ideal Mfwalk(ideal Go, intvec* curr_weight, intvec* orig_target_weight, int pert_deg, ring XXRing)
     5175{
     5176  Set_Error(FALSE);
     5177  Overflow_Error = FALSE;
     5178#ifdef TIME_TEST
     5179  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
     5180  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
     5181  tinput = clock();
     5182  clock_t tim;
     5183#endif
     5184  nstep=0;
     5185  ring newRing;
     5186  ring baseRing = currRing;
     5187  rChangeCurrRing(XXRing);
     5188  Go = idrMoveR(Go,baseRing,currRing);
     5189  int i,nwalk,endwalks = 0;
     5190  int nV = currRing->N;
     5191  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1;
     5192  intvec* ivNull = new intvec(nV);
     5193  intvec* next_weight = new intvec(nV);
     5194  intvec* tmp_weight = new intvec(nV);
     5195#ifdef TIME_TEST
     5196  to = clock();
     5197#endif
     5198  ideal G = MstdCC(Go);
     5199#ifdef TIME_TEST
     5200  tostd = clock()-to;
     5201#endif
     5202#ifdef CHECK_IDEAL_MWALK
     5203    idString(Go,"Go");
     5204#endif
     5205  intvec* target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
     5206  for(i=0; i<nV; i++)
     5207  {
     5208    (*tmp_weight)[i] = (*target_weight)[i];
     5209  }
     5210  nwalk = 0;
     5211  while(1)
     5212  {
     5213    nwalk++;
     5214    baseRing = currRing;
     5215    Gomega = MwalkInitialForm(G, curr_weight);
     5216#ifdef CHECK_IDEAL_MWALK
     5217    idString(Gomega,"Gomega");
     5218#endif
     5219    next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
     5220    MivString(curr_weight, target_weight, tmp_weight);
     5221    if(MivSame(curr_weight,target_weight) ==1)
     5222    {
     5223      break;
     5224    }
     5225    if( MivSame(tmp_weight, curr_weight) == 1 )
     5226    {
     5227      if(test_w_in_ConeCC(G, target_weight) == 1)
     5228      {
     5229        break;
     5230      }
     5231      else
     5232      {
     5233        pert_deg++;
     5234        target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
     5235        next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
     5236      }
     5237    }
     5238    for(i=0; i<nV; i++)
     5239    {
     5240      (*tmp_weight)[i] = (*curr_weight)[i];
     5241      (*curr_weight)[i] = (*next_weight)[i];
     5242    }
     5243    MivString(curr_weight, target_weight, tmp_weight);
     5244    newRing = VMrRefine(tmp_weight,target_weight); //define a new ring with ordering "(a(curr_weight),Wp(target_weight))"
     5245    rChangeCurrRing(newRing); // change the ring to newRing
     5246    Gomega1 =  idrMoveR(Gomega, baseRing,currRing);
     5247    idDelete(&Gomega);
     5248    if(pert_deg >= nV)
     5249    {
     5250      M = kStd(Gomega1,NULL,testHomog,NULL,NULL,0,0,NULL);
     5251    }
    53685252    else
    5369       (*omega)[i] = (*Xsigma)[(nV*(nlev-1))+i];
    5370 
    5371     (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
    5372   }
    5373 
    5374    if(nlev == 1)  Xcall = 1;
    5375    else Xcall = 0;
    5376 
    5377   ring oRing = currRing;
    5378 
    5379   while(1)
    5380   {
    5381 #ifdef FIRST_STEP_FRACTAL
    5382     // perturb the current weight vector only on the top level or
    5383     // after perturbation of the both vectors, nlev = 2 as the top level
    5384     if((nlev == 1 && Xcall == 0) || (nlev == 2 && Xngleich == 1))
    5385       if(islengthpoly2(G) == 1)
    5386       {
    5387         Mwlp = MivWeightOrderlp(omega);
    5388         Xsigma = Mfpertvector(G, Mwlp);
    5389         delete Mwlp;
    5390         Overflow_Error = FALSE;
    5391       }
    5392 #endif
    5393     nwalks ++;
    5394     NEXT_VECTOR_FRACTAL:
    5395     to=clock();
    5396     /* determine the next border */
    5397     next_vect = MkInterRedNextWeight(omega,omega2,G);
    5398     xtnw=xtnw+clock()-to;
    5399 #ifdef PRINT_VECTORS
    5400     MivString(omega, omega2, next_vect);
    5401 #endif
    5402     oRing = currRing;
    5403 
    5404     /* We only perturb the current target vector at the recursion  level 1 */
    5405     if(Xngleich == 0 && nlev == 1) //(ngleich == 0) important, e.g. ex2, ex3
    5406       if (MivComp(next_vect, omega2) == 1)
    5407       {
    5408         /* to dispense with taking initial (and lifting/interreducing
    5409            after the call of recursion */
    5410         //Print("\n\n// ** Perturb the both vectors with degree %d with",nlev);
    5411         //idElements(G, "G");
    5412 
    5413         Xngleich = 1;
    5414         nlev +=1;
    5415 
    5416         if (rParameter(currRing) != NULL)
    5417           DefRingPar(omtmp);
    5418         else
    5419           VMrDefault(omtmp);
    5420 
    5421         testring = currRing;
    5422         Gt = idrMoveR(G, oRing,currRing);
    5423 
    5424         /* perturb the original target vector w.r.t. the current GB */
    5425         delete Xtau;
    5426         Xtau = NewVectorlp(Gt);
    5427 
    5428         rChangeCurrRing(oRing);
    5429         G = idrMoveR(Gt, testring,currRing);
    5430 
    5431         /* perturb the current vector w.r.t. the current GB */
    5432         Mwlp = MivWeightOrderlp(omega);
    5433         Xsigma = Mfpertvector(G, Mwlp);
    5434         delete Mwlp;
    5435 
    5436         for(i=nV-1; i>=0; i--) {
    5437           (*omega2)[i] = (*Xtau)[nV+i];
    5438           (*omega)[i] = (*Xsigma)[nV+i];
    5439         }
    5440 
    5441         delete next_vect;
    5442         to=clock();
    5443 
    5444         /* to avoid the value of Overflow_Error that occur in Mfpertvector*/
    5445         Overflow_Error = FALSE;
    5446 
    5447         next_vect = MkInterRedNextWeight(omega,omega2,G);
    5448         xtnw=xtnw+clock()-to;
    5449 
    5450 #ifdef PRINT_VECTORS
    5451         MivString(omega, omega2, next_vect);
    5452 #endif
    5453       }
    5454 
    5455 
    5456     /* check whether the the computed vector is in the correct cone */
    5457     /* If no, the reduced GB of an omega-homogeneous ideal will be
    5458        computed by Buchberger algorithm and stop this recursion step*/
    5459     //if(test_w_in_ConeCC(G, next_vect) != 1) //e.g. Example s7, cyc6
    5460     if(Overflow_Error == TRUE)
    5461     {
    5462       delete next_vect;
    5463       if (rParameter(currRing) != NULL)
    5464       {
    5465         DefRingPar(omtmp);
    5466       }
    5467       else
    5468       {
    5469         VMrDefault(omtmp);
    5470       }
    5471 #ifdef TEST_OVERFLOW
    5472       Gt = idrMoveR(G, oRing,currRing);
    5473       Gt = NULL; return(Gt);
    5474 #endif
    5475 
    5476       //Print("\n\n// apply BB's alg. in ring r = %s;", rString(currRing));
    5477       to=clock();
    5478       Gt = idrMoveR(G, oRing,currRing);
    5479       G1 = MstdCC(Gt);
    5480       xtextra=xtextra+clock()-to;
    5481       Gt = NULL;
    5482 
    5483       delete omega2;
    5484       delete altomega;
    5485 
    5486       //Print("\n// Leaving the %d-th recursion with %d steps", nlev, nwalks);
    5487       //Print("  ** Overflow_Error? (%d)", Overflow_Error);
    5488       nnflow ++;
    5489 
    5490       Overflow_Error = FALSE;
    5491       return (G1);
    5492     }
    5493 
    5494 
    5495     /* If the perturbed target vector stays in the correct cone,
    5496        return the current GB,
    5497        otherwise, return the computed  GB by the Buchberger-algorithm.
    5498        Then we update the perturbed target vectors w.r.t. this GB. */
    5499 
    5500     /* the computed vector is equal to the origin vector, since
    5501        t is not defined */
    5502     if (MivComp(next_vect, XivNull) == 1)
    5503     {
    5504       if (rParameter(currRing) != NULL)
    5505         DefRingPar(omtmp);
    5506       else
    5507         VMrDefault(omtmp);
    5508 
    5509       testring = currRing;
    5510       Gt = idrMoveR(G, oRing,currRing);
    5511 
    5512       if(test_w_in_ConeCC(Gt, omega2) == 1) {
    5513         delete omega2;
    5514         delete next_vect;
    5515         delete altomega;
    5516         //Print("\n// Leaving the %d-th recursion with %d steps ",nlev, nwalks);
    5517         //Print(" ** Overflow_Error? (%d)", Overflow_Error);
    5518 
    5519         return (Gt);
    5520       }
    5521       else
    5522       {
    5523         //ivString(omega2, "tau'");
    5524         //Print("\n//  tau' doesn't stay in the correct cone!!");
    5525 
    5526 #ifndef  MSTDCC_FRACTAL
    5527         //07.08.03
    5528         //ivString(Xtau, "old Xtau");
    5529         intvec* Xtautmp = Mfpertvector(Gt, MivMatrixOrder(omtmp));
    5530 #ifdef TEST_OVERFLOW
    5531       if(Overflow_Error == TRUE)
    5532       Gt = NULL; return(Gt);
    5533 #endif
    5534 
    5535         if(MivSame(Xtau, Xtautmp) == 1)
    5536         {
    5537           //PrintS("\n// Update vectors are equal to the old vectors!!");
    5538           delete Xtautmp;
    5539           goto FRACTAL_MSTDCC;
    5540         }
    5541 
    5542         Xtau = Xtautmp;
    5543         Xtautmp = NULL;
    5544         //ivString(Xtau, "new  Xtau");
    5545 
    5546         for(i=nV-1; i>=0; i--)
    5547           (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
    5548 
    5549         //Print("\n//  ring tau = %s;", rString(currRing));
    5550         rChangeCurrRing(oRing);
    5551         G = idrMoveR(Gt, testring,currRing);
    5552 
    5553         goto NEXT_VECTOR_FRACTAL;
    5554 #endif
    5555 
    5556       FRACTAL_MSTDCC:
    5557         //Print("\n//  apply BB-Alg in ring = %s;", rString(currRing));
    5558         to=clock();
    5559         G = MstdCC(Gt);
    5560         xtextra=xtextra+clock()-to;
    5561 
    5562         oRing = currRing;
    5563 
    5564         // update the original target vector w.r.t. the current GB
    5565         if(MivSame(Xivinput, Xivlp) == 1)
    5566           if (rParameter(currRing) != NULL)
    5567             DefRingParlp();
    5568           else
    5569             VMrDefaultlp();
    5570         else
    5571           if (rParameter(currRing) != NULL)
    5572             DefRingPar(Xivinput);
    5573           else
    5574             VMrDefault(Xivinput);
    5575 
    5576         testring = currRing;
    5577         Gt = idrMoveR(G, oRing,currRing);
    5578 
    5579         delete Xtau;
    5580         Xtau = NewVectorlp(Gt);
    5581 
    5582         rChangeCurrRing(oRing);
    5583         G = idrMoveR(Gt, testring,currRing);
    5584 
    5585         delete omega2;
    5586         delete next_vect;
    5587         delete altomega;
    5588         /*
    5589           Print("\n// Leaving the %d-th recursion with %d steps,", nlev,nwalks);
    5590           Print(" ** Overflow_Error? (%d)", Overflow_Error);
    5591         */
    5592         if(Overflow_Error == TRUE)
    5593           nnflow ++;
    5594 
    5595         Overflow_Error = FALSE;
    5596         return(G);
    5597       }
    5598     }
    5599 
    5600     for(i=nV-1; i>=0; i--) {
    5601       (*altomega)[i] = (*omega)[i];
    5602       (*omega)[i] = (*next_vect)[i];
    5603     }
    5604     delete next_vect;
    5605 
    5606     to=clock();
    5607     /* Take the initial form of <G> w.r.t. omega */
    5608     Gomega = MwalkInitialForm(G, omega);
    5609     xtif=xtif+clock()-to;
    5610 
    5611 #ifndef  BUCHBERGER_ALG
    5612     if(isNolVector(omega) == 0)
    5613       hilb_func = hFirstSeries(Gomega,NULL,NULL,omega,currRing);
    5614     else
    5615       hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    5616 #endif // BUCHBERGER_ALG
    5617 
    5618     if (rParameter(currRing) != NULL)
    5619       DefRingPar(omega);
    5620     else
    5621       VMrDefault(omega);
    5622 
    5623     Gomega1 = idrMoveR(Gomega, oRing,currRing);
    5624 
    5625     /* Maximal recursion depth, to compute a red. GB */
    5626     /* Fractal walk with the alternative recursion */
    5627     /* alternative recursion */
    5628     // if(nlev == nV || lengthpoly(Gomega1) == 0)
    5629     if(nlev == Xnlev || lengthpoly(Gomega1) == 0)
    5630       //if(nlev == nV) // blind recursion
    5631     {
    5632       /*
    5633       if(Xnlev != nV)
    5634       {
    5635         Print("\n// ** Xnlev = %d", Xnlev);
    5636         ivString(Xtau, "Xtau");
    5637       }
    5638       */
    5639       to=clock();
    5640 #ifdef  BUCHBERGER_ALG
    5641       Gresult = MstdhomCC(Gomega1);
    5642 #else
    5643       Gresult =kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,omega);
    5644       delete hilb_func;
    5645 #endif // BUCHBERGER_ALG
    5646       xtstd=xtstd+clock()-to;
    5647     }
    5648     else {
    5649       rChangeCurrRing(oRing);
    5650       Gomega1 = idrMoveR(Gomega1, oRing,currRing);
    5651       Gresult = rec_fractal_call(idCopy(Gomega1),nlev+1,omega);
    5652     }
    5653 
    5654     //convert a Groebner basis from a ring to another ring,
    5655     new_ring = currRing;
    5656 
    5657     rChangeCurrRing(oRing);
    5658     Gresult1 = idrMoveR(Gresult, new_ring,currRing);
    5659     Gomega2 = idrMoveR(Gomega1, new_ring,currRing);
    5660 
    5661     to=clock();
    5662     /* Lifting process */
    5663     F = MLifttwoIdeal(Gomega2, Gresult1, G);
    5664     xtlift=xtlift+clock()-to;
    5665     idDelete(&Gresult1);
     5253    {
     5254      M = idCopy(Mwalk(idCopy(Gomega1), tmp_weight, curr_weight, currRing));
     5255    }
     5256    idSkipZeroes(M);
     5257#ifdef CHECK_IDEAL_MWALK
     5258    idString(M,"M");
     5259#endif
     5260    rChangeCurrRing(baseRing); //change ring to baseRing
     5261    M1 =  idrMoveR(M, newRing,currRing);
     5262    Gomega2 = idrMoveR(Gomega1, newRing,currRing);
     5263    idDelete(&M);
     5264    idDelete(&Gomega1);
     5265    F = MLifttwoIdeal(Gomega2, M1, G);
    56665266    idDelete(&Gomega2);
    5667     idDelete(&G);
    5668 
    5669     rChangeCurrRing(new_ring);
    5670     F1 = idrMoveR(F, oRing,currRing);
    5671 
    5672     to=clock();
    5673     /* Interreduce G */
    5674     G = kInterRedCC(F1, NULL);
    5675     xtred=xtred+clock()-to;
    5676     idDelete(&F1);
    5677   }
    5678 }
    5679 
    5680 /************************************************************************
    5681  * Perturb the start weight vector at the top level with random element *
    5682  ************************************************************************/
    5683 static ideal rec_r_fractal_call(ideal G, int nlev, intvec* omtmp, int weight_rad)
    5684 {
    5685   Overflow_Error =  FALSE;
    5686   //Print("\n\n// Entering the %d-th recursion:", nlev);
    5687 
    5688   int i,k,weight_norm;
    5689   int nV = currRing->N;
    5690   ring new_ring, testring;
    5691   //ring extoRing;
    5692   ideal Gomega, Gomega1, Gomega2, F, F1, Gresult, Gresult1, G1, Gt;
    5693   int nwalks = 0;
    5694   intvec* Mwlp;
    5695 #ifndef BUCHBERGER_ALG
    5696   intvec* hilb_func;
    5697 #endif
    5698   //intvec* extXtau;
    5699   intvec* next_vect;
    5700   intvec* omega2 = new intvec(nV);
    5701   intvec* altomega = new intvec(nV);
    5702 
    5703   //BOOLEAN isnewtarget = FALSE;
    5704 
    5705   // to avoid (1,0,...,0) as the target vector (Hans)
    5706   intvec* last_omega = new intvec(nV);
    5707   for(i=nV-1; i>0; i--)
    5708     (*last_omega)[i] = 1;
    5709   (*last_omega)[0] = 10000;
    5710 
    5711   intvec* omega = new intvec(nV);
    5712   for(i=0; i<nV; i++) {
    5713     if(Xsigma->length() == nV)
    5714       (*omega)[i] =  (*Xsigma)[i];
    5715     else
    5716       (*omega)[i] = (*Xsigma)[(nV*(nlev-1))+i];
    5717 
    5718     (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
    5719   }
    5720 
    5721    if(nlev == 1)  Xcall = 1;
    5722    else Xcall = 0;
    5723 
    5724   ring oRing = currRing;
    5725 
    5726   while(1)
    5727   {
    5728 #ifdef FIRST_STEP_FRACTAL
    5729     // perturb the current weight vector only on the top level or
    5730     // after perturbation of the both vectors, nlev = 2 as the top level
    5731     if((nlev == 1 && Xcall == 0) || (nlev == 2 && Xngleich == 1))
    5732       if(islengthpoly2(G) == 1)
    5733       {
    5734         Mwlp = MivWeightOrderlp(omega);
    5735         Xsigma = Mfpertvector(G, Mwlp);
    5736         delete Mwlp;
    5737         Overflow_Error = FALSE;
    5738       }
    5739 #endif
    5740     nwalks ++;
    5741     NEXT_VECTOR_FRACTAL:
    5742     to=clock();
    5743     /* determine the next border */
    5744     next_vect = MkInterRedNextWeight(omega,omega2,G);
    5745     xtnw=xtnw+clock()-to;
    5746 #ifdef PRINT_VECTORS
    5747     MivString(omega, omega2, next_vect);
    5748 #endif
    5749     oRing = currRing;
    5750 
    5751     /* We only perturb the current target vector at the recursion  level 1 */
    5752     if(Xngleich == 0 && nlev == 1) //(ngleich == 0) important, e.g. ex2, ex3
    5753     {
    5754       if (MivComp(next_vect, omega2) == 1)
    5755       {
    5756         /* to dispense with taking initial (and lifting/interreducing
    5757            after the call of recursion */
    5758         //Print("\n\n// ** Perturb the both vectors with degree %d with",nlev);
    5759         //idElements(G, "G");
    5760 
    5761         Xngleich = 1;
    5762         nlev +=1;
    5763 
    5764         if (rParameter(currRing) != NULL)
    5765           DefRingPar(omtmp);
    5766         else
    5767           VMrDefault(omtmp);
    5768 
    5769         testring = currRing;
    5770         Gt = idrMoveR(G, oRing,currRing);
    5771 
    5772         /* perturb the original target vector w.r.t. the current GB */
    5773         delete Xtau;
    5774         Xtau = NewVectorlp(Gt);
    5775 
    5776         rChangeCurrRing(oRing);
    5777         G = idrMoveR(Gt, testring,currRing);
    5778 
    5779         /* perturb the current vector w.r.t. the current GB */
    5780         Mwlp = MivWeightOrderlp(omega);
    5781         Xsigma = Mfpertvector(G, Mwlp);
    5782         delete Mwlp;
    5783 
    5784         for(i=nV-1; i>=0; i--) {
    5785           (*omega2)[i] = (*Xtau)[nV+i];
    5786           (*omega)[i] = (*Xsigma)[nV+i];
    5787         }
    5788 
    5789         delete next_vect;
    5790         to=clock();
    5791 
    5792         /* to avoid the value of Overflow_Error that occur in Mfpertvector*/
    5793         Overflow_Error = FALSE;
    5794 
    5795         next_vect = MkInterRedNextWeight(omega,omega2,G);
    5796         xtnw=xtnw+clock()-to;
    5797 
    5798 #ifdef PRINT_VECTORS
    5799         MivString(omega, omega2, next_vect);
    5800 #endif
    5801       }
    5802       else
    5803       {
    5804         // compute a perturbed next weight vector "next_vect1"
    5805         intvec* next_vect11 = MPertVectors(G, MivMatrixOrder(omega), nlev);
    5806         intvec* next_vect1 = MkInterRedNextWeight(next_vect11, omega2, G);
    5807         // Print("\n//  size of next_vect  = %d", sizeof((*next_vect)));
    5808         // Print("\n//  size of next_vect1  = %d", sizeof((*next_vect1)));
    5809         // Print("\n//  size of next_vect11  = %d", sizeof((*next_vect11)));
    5810         delete next_vect11;
    5811 
    5812         // compare next_vect and next_vect1
    5813         ideal G_test = MwalkInitialForm(G, next_vect);
    5814         ideal G_test1 = MwalkInitialForm(G, next_vect1);
    5815         // Print("\n// G_test, G_test 1 erzeugt");
    5816         if(IDELEMS(G_test1) <= IDELEMS(G_test))
    5817           {
    5818           next_vect = ivCopy(next_vect1);
    5819           }
    5820         delete next_vect1;
    5821         // compute a random next weight vector "next_vect2"
    5822         intvec* next_vect22 = ivCopy(omega2);
    5823         // Print("\n//  size of next_vect22  = %d", sizeof((*next_vect22)));
    5824         k = 0;
    5825         while(test_w_in_ConeCC(G, next_vect22) == 0)
    5826         {
    5827           k = k + 1;
    5828           if(k>10)
    5829           {
    5830             break;
    5831           }
    5832           weight_norm = 0;
    5833           while(weight_norm == 0)
    5834           {
    5835             for(i=nV-1; i>=0; i--)
    5836             {
    5837               (*next_vect22)[i] = rand() % 60000 - 30000;
    5838               weight_norm = weight_norm + (*next_vect22)[i]*(*next_vect22)[i];
    5839             }
    5840             weight_norm = 1 + floor(sqrt(weight_norm));
    5841           }
    5842           for(i=nV-1; i>=0; i--)
    5843           {
    5844             if((*next_vect22)[i] < 0)
    5845             {
    5846               (*next_vect22)[i] = 1 + (*omega)[i] + floor(weight_rad*(*next_vect22)[i]/weight_norm);
    5847             }
    5848             else
    5849             {
    5850               (*next_vect22)[i] = (*omega)[i] + floor(weight_rad*(*next_vect22)[i]/weight_norm);
    5851             }
    5852           }
    5853         }
    5854         if(test_w_in_ConeCC(G, next_vect22) == 1)
    5855         {
    5856           //compare next_weight and next_vect2
    5857           intvec* next_vect2 = MkInterRedNextWeight(next_vect22, omega2, G);
    5858           // Print("\n//  size of next_vect2  = %d", sizeof((*next_vect2)));
    5859           ideal G_test2 = MwalkInitialForm(G, next_vect2);
    5860           if(IDELEMS(G_test2) <= IDELEMS(G_test))
    5861           {
    5862             if(IDELEMS(G_test2) <= IDELEMS(G_test1))
    5863             {
    5864               next_vect = ivCopy(next_vect2);
    5865             }
    5866           }
    5867           idDelete(&G_test2);
    5868           delete next_vect2;
    5869         }
    5870         delete next_vect22;
    5871         idDelete(&G_test);
    5872         idDelete(&G_test1);
    5873 #ifdef PRINT_VECTORS
    5874         MivString(omega, omega2, next_vect);
    5875 #endif
    5876       }
    5877     }
    5878 
    5879 
    5880     /* check whether the the computed vector is in the correct cone */
    5881     /* If no, the reduced GB of an omega-homogeneous ideal will be
    5882        computed by Buchberger algorithm and stop this recursion step*/
    5883     //if(test_w_in_ConeCC(G, next_vect) != 1) //e.g. Example s7, cyc6
    5884     if(Overflow_Error == TRUE)
    5885     {
    5886       delete next_vect;
    5887 
    5888     //OVERFLOW_IN_NEXT_VECTOR:
    5889       if (rParameter(currRing) != NULL)
    5890         DefRingPar(omtmp);
    5891       else
    5892         VMrDefault(omtmp);
    5893 
    5894 #ifdef TEST_OVERFLOW
    5895       Gt = idrMoveR(G, oRing,currRing);
    5896       Gt = NULL; return(Gt);
    5897 #endif
    5898 
    5899       //Print("\n\n// apply BB's alg. in ring r = %s;", rString(currRing));
    5900       to=clock();
    5901       Gt = idrMoveR(G, oRing,currRing);
    5902       G1 = MstdCC(Gt);
    5903       xtextra=xtextra+clock()-to;
    5904       Gt = NULL;
    5905 
    5906       delete omega2;
    5907       delete altomega;
    5908 
    5909       //Print("\n// Leaving the %d-th recursion with %d steps", nlev, nwalks);
    5910       //Print("  ** Overflow_Error? (%d)", Overflow_Error);
    5911       nnflow ++;
    5912 
    5913       Overflow_Error = FALSE;
    5914       return (G1);
    5915     }
    5916 
    5917 
    5918     /* If the perturbed target vector stays in the correct cone,
    5919        return the current GB,
    5920        otherwise, return the computed  GB by the Buchberger-algorithm.
    5921        Then we update the perturbed target vectors w.r.t. this GB. */
    5922 
    5923     /* the computed vector is equal to the origin vector, since
    5924        t is not defined */
    5925     if (MivComp(next_vect, XivNull) == 1)
    5926     {
    5927       if (rParameter(currRing) != NULL)
    5928         DefRingPar(omtmp);
    5929       else
    5930         VMrDefault(omtmp);
    5931 
    5932       testring = currRing;
    5933       Gt = idrMoveR(G, oRing,currRing);
    5934 
    5935       if(test_w_in_ConeCC(Gt, omega2) == 1) {
    5936         delete omega2;
    5937         delete next_vect;
    5938         delete altomega;
    5939         //Print("\n// Leaving the %d-th recursion with %d steps ",nlev, nwalks);
    5940         //Print(" ** Overflow_Error? (%d)", Overflow_Error);
    5941 
    5942         return (Gt);
    5943       }
    5944       else
    5945       {
    5946         //ivString(omega2, "tau'");
    5947         //Print("\n//  tau' doesn't stay in the correct cone!!");
    5948 
    5949 #ifndef  MSTDCC_FRACTAL
    5950         //07.08.03
    5951         //ivString(Xtau, "old Xtau");
    5952         intvec* Xtautmp = Mfpertvector(Gt, MivMatrixOrder(omtmp));
    5953 #ifdef TEST_OVERFLOW
    5954       if(Overflow_Error == TRUE)
    5955       Gt = NULL; return(Gt);
    5956 #endif
    5957 
    5958         if(MivSame(Xtau, Xtautmp) == 1)
    5959         {
    5960           //PrintS("\n// Update vectors are equal to the old vectors!!");
    5961           delete Xtautmp;
    5962           goto FRACTAL_MSTDCC;
    5963         }
    5964 
    5965         Xtau = Xtautmp;
    5966         Xtautmp = NULL;
    5967         //ivString(Xtau, "new  Xtau");
    5968 
    5969         for(i=nV-1; i>=0; i--)
    5970           (*omega2)[i] = (*Xtau)[(nlev-1)*nV+i];
    5971 
    5972         //Print("\n//  ring tau = %s;", rString(currRing));
    5973         rChangeCurrRing(oRing);
    5974         G = idrMoveR(Gt, testring,currRing);
    5975 
    5976         goto NEXT_VECTOR_FRACTAL;
    5977 #endif
    5978 
    5979       FRACTAL_MSTDCC:
    5980         //Print("\n//  apply BB-Alg in ring = %s;", rString(currRing));
    5981         to=clock();
    5982         G = MstdCC(Gt);
    5983         xtextra=xtextra+clock()-to;
    5984 
    5985         oRing = currRing;
    5986 
    5987         // update the original target vector w.r.t. the current GB
    5988         if(MivSame(Xivinput, Xivlp) == 1)
    5989           if (rParameter(currRing) != NULL)
    5990             DefRingParlp();
    5991           else
    5992             VMrDefaultlp();
    5993         else
    5994           if (rParameter(currRing) != NULL)
    5995             DefRingPar(Xivinput);
    5996           else
    5997             VMrDefault(Xivinput);
    5998 
    5999         testring = currRing;
    6000         Gt = idrMoveR(G, oRing,currRing);
    6001 
    6002         delete Xtau;
    6003         Xtau = NewVectorlp(Gt);
    6004 
    6005         rChangeCurrRing(oRing);
    6006         G = idrMoveR(Gt, testring,currRing);
    6007 
    6008         delete omega2;
    6009         delete next_vect;
    6010         delete altomega;
    6011         /*
    6012           Print("\n// Leaving the %d-th recursion with %d steps,", nlev,nwalks);
    6013           Print(" ** Overflow_Error? (%d)", Overflow_Error);
    6014         */
    6015         if(Overflow_Error == TRUE)
    6016           nnflow ++;
    6017 
    6018         Overflow_Error = FALSE;
    6019         return(G);
    6020       }
    6021     }
    6022 
    6023     for(i=nV-1; i>=0; i--) {
    6024       (*altomega)[i] = (*omega)[i];
    6025       (*omega)[i] = (*next_vect)[i];
    6026     }
    6027     delete next_vect;
    6028 
    6029     to=clock();
    6030     /* Take the initial form of <G> w.r.t. omega */
    6031     Gomega = MwalkInitialForm(G, omega);
    6032     xtif=xtif+clock()-to;
    6033 
    6034 #ifndef  BUCHBERGER_ALG
    6035     if(isNolVector(omega) == 0)
    6036       hilb_func = hFirstSeries(Gomega,NULL,NULL,omega,currRing);
    6037     else
    6038       hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
    6039 #endif // BUCHBERGER_ALG
    6040 
    6041     if (rParameter(currRing) != NULL)
    6042       DefRingPar(omega);
    6043     else
    6044       VMrDefault(omega);
    6045 
    6046     Gomega1 = idrMoveR(Gomega, oRing,currRing);
    6047 
    6048     /* Maximal recursion depth, to compute a red. GB */
    6049     /* Fractal walk with the alternative recursion */
    6050     /* alternative recursion */
    6051     // if(nlev == nV || lengthpoly(Gomega1) == 0)
    6052     if(nlev == Xnlev || lengthpoly(Gomega1) == 0)
    6053       //if(nlev == nV) // blind recursion
    6054     {
    6055       /*
    6056       if(Xnlev != nV)
    6057       {
    6058         Print("\n// ** Xnlev = %d", Xnlev);
    6059         ivString(Xtau, "Xtau");
    6060       }
    6061       */
    6062       to=clock();
    6063 #ifdef  BUCHBERGER_ALG
    6064       Gresult = MstdhomCC(Gomega1);
    6065 #else
    6066       Gresult =kStd(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,omega);
    6067       delete hilb_func;
    6068 #endif // BUCHBERGER_ALG
    6069       xtstd=xtstd+clock()-to;
    6070     }
    6071     else {
    6072       rChangeCurrRing(oRing);
    6073       Gomega1 = idrMoveR(Gomega1, oRing,currRing);
    6074       Gresult = rec_fractal_call(idCopy(Gomega1),nlev+1,omega);
    6075     }
    6076 
    6077     //convert a Groebner basis from a ring to another ring,
    6078     new_ring = currRing;
    6079 
    6080     rChangeCurrRing(oRing);
    6081     Gresult1 = idrMoveR(Gresult, new_ring,currRing);
    6082     Gomega2 = idrMoveR(Gomega1, new_ring,currRing);
    6083 
    6084     to=clock();
    6085     /* Lifting process */
    6086     F = MLifttwoIdeal(Gomega2, Gresult1, G);
    6087     xtlift=xtlift+clock()-to;
    6088     idDelete(&Gresult1);
    6089     idDelete(&Gomega2);
    6090     idDelete(&G);
    6091 
    6092     rChangeCurrRing(new_ring);
    6093     F1 = idrMoveR(F, oRing,currRing);
    6094 
    6095     to=clock();
    6096     /* Interreduce G */
    6097     G = kInterRedCC(F1, NULL);
    6098     xtred=xtred+clock()-to;
    6099     idDelete(&F1);
    6100   }
    6101 }
    6102 
    6103 
    6104 
    6105 /*******************************************************************************
    6106  * The implementation of the fractal walk algorithm                            *
    6107  *                                                                             *
    6108  * The main procedur Mfwalk calls the recursive Subroutine                     *
    6109  * rec_fractal_call to compute the wanted Grï¿œbner basis.                       *
    6110  * At the main procedur we compute the reduced Grï¿œbner basis w.r.t. a "fast"   *
    6111  * order, e.g. "dp" and a sequence of weight vectors which are row vectors     *
    6112  * of a matrix. This matrix defines the given monomial order, e.g. "lp"        *
    6113  *******************************************************************************/
    6114 ideal Mfwalk(ideal G, intvec* ivstart, intvec* ivtarget)
     5267    idSkipZeroes(F);
     5268#ifdef CHECK_IDEAL_MWALK
     5269    idString(F,"F");
     5270#endif
     5271    rChangeCurrRing(newRing); // change the ring to newRing
     5272    G = idrMoveR(F,baseRing,currRing);
     5273    idDelete(&F);
     5274    baseRing = currRing;
     5275    if(MivComp(next_weight, ivNull) == 1)
     5276    {
     5277      delete next_weight;
     5278      break;
     5279    }
     5280  }
     5281  delete next_weight;
     5282  if(test_w_in_ConeCC(G, orig_target_weight) != 1)
     5283  {
     5284    newRing = VMrDefault(orig_target_weight);  //define a new ring with ordering "(a(target_weight),lp)
     5285    rChangeCurrRing(newRing);
     5286    G = idrMoveR(G,baseRing,currRing);
     5287    M = idCopy(Mwalk(idCopy(G), tmp_weight, orig_target_weight, currRing));
     5288    idSkipZeroes(G);
     5289    baseRing = currRing;
     5290  }
     5291  ENDE:
     5292  rChangeCurrRing(XXRing);
     5293  G = idrMoveR(G,baseRing,currRing);
     5294  delete tmp_weight;
     5295  delete ivNull;
     5296#ifdef TIME_TEST
     5297  TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
     5298#endif
     5299  return(G);
     5300}
     5301
     5302/***********************************************
     5303THE FRACTAL WALK ALGORITHM WITH RANDOM ELEMENT *
     5304************************************************/
     5305ideal Mfrwalk(ideal Go, intvec* curr_weight, intvec* orig_target_weight, int pert_deg, int weight_rad, ring XXRing)
    61155306{
    61165307  Set_Error(FALSE);
    61175308  Overflow_Error = FALSE;
    61185309  //Print("// pSetm_Error = (%d)", ErrorCheck());
    6119   //Print("\n// ring ro = %s;", rString(currRing));
    6120 
    6121   nnflow = 0;
    6122   Xngleich = 0;
    6123   Xcall = 0;
    6124   xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
    6125   xftinput = clock();
    6126 
    6127   ring  oldRing = currRing;
    6128   int i, nV = currRing->N;
    6129   XivNull = new intvec(nV);
    6130   Xivinput = ivtarget;
    6131   ngleich = 0;
    6132   to=clock();
    6133   ideal I = MstdCC(G);
    6134   G = NULL;
    6135   xftostd=clock()-to;
    6136   Xsigma = ivstart;
    6137 
    6138   Xnlev=nV;
    6139 
    6140 #ifdef FIRST_STEP_FRACTAL
    6141   ideal Gw = MwalkInitialForm(I, ivstart);
    6142   for(i=IDELEMS(Gw)-1; i>=0; i--)
    6143   {
    6144     if((Gw->m[i]!=NULL) // len >=0
    6145     && (Gw->m[i]->next!=NULL) // len >=1
    6146     && (Gw->m[i]->next->next!=NULL)) // len >=2
    6147     {
    6148       intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
    6149       intvec* Mdp;
    6150 
    6151       if(MivSame(ivstart, iv_dp) != 1)
    6152         Mdp = MivWeightOrderdp(ivstart);
     5310#ifdef TIME_TEST
     5311  clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
     5312  xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
     5313  tinput = clock();
     5314  clock_t tim;
     5315#endif
     5316  nstep=0;
     5317  ring newRing;
     5318  ring baseRing = currRing;
     5319  rChangeCurrRing(XXRing);
     5320  Go = idrMoveR(Go,baseRing,currRing);
     5321  int i,nwalk,endwalks = 0;
     5322  int nV = currRing->N;
     5323  ideal Gomega, M, F, Gomega1, Gomega2, M1, F1;
     5324  intvec* ivNull = new intvec(nV);
     5325  intvec* next_weight = new intvec(nV);
     5326  intvec* tmp_weight = new intvec(nV);
     5327#ifdef TIME_TEST
     5328  to = clock();
     5329#endif
     5330  ideal G = MstdCC(Go);
     5331#ifdef TIME_TEST
     5332  tostd = clock()-to;
     5333#endif
     5334  intvec* target_weight = MPertVectors(G, MivMatrixOrder(orig_target_weight), pert_deg);
     5335  for(i=0; i<nV; i++)
     5336  {
     5337    (*tmp_weight)[i] = (*target_weight)[i];
     5338  }