source: git/Singular/LIB/rwalk.lib @ ffd4a9

<<<<<<< HEAD
=======
//
>>>>>>> 92644b759d66f085c842e4284d78c2e203291b67
version="$Id$";
category="Commutative Algebra";

info="
LIBRARY: rwalk.lib   Groebner Walk Conversion Algorithms
AUTHOR: Stephan Oberfranz

PROCEDURES:
 rwalk(ideal[,intvec]);   standard basis of ideal via randomwalk algorithm
";

/***********************************
 * Argument string for Random Walk *
 ***********************************/
proc OrderStringalp_NP(string Wpal,list #)
{
  int n= nvars(basering);
  string order_str = "dp";

  int nP = 1;

  //Default: if size(#)=0, the Groebnerwalk algorithm and its developments compute a Groebner basis from "dp" to "lp"

  intvec curr_weight = system("Mivdp",n); //define (1,1,...,1)
  intvec target_weight = system("Mivlp",n); //define (1,0,...,0)

  if(size(#) != 0)
  {
    if(size(#) == 1)
    {
      if(typeof(#[1]) == "intvec") {
        curr_weight = #[1];

        if(Wpal == "al"){
          order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
        }
        if(Wpal == "M"){
          order_str = "(M("+string(#[1])+"),C)";
        }
        else {
          order_str = "(Wp("+string(#[1])+"),C)";
        }
      }
      else {
        if(typeof(#[1]) == "int"){
          nP = #[1];
        }
        else {
          print("// ** the input must be \"(ideal, int)\" or ");
          print("// **                   \"(ideal, intvec)\"");
          print("// ** a lex. GB will be computed from \"dp\" to \"lp\"");
        }
      }
    }
    else
    {
     if(size(#) == 2)
     {
       if(typeof(#[1]) == "intvec" and typeof(#[2]) == "int"){
         curr_weight = #[1];

         if(Wpal == "al"){
           order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
         }
         if(Wpal == "M"){
          order_str = "(M("+string(#[1])+"),C)";
         }
         else {
           order_str = "(Wp("+string(#[1])+"),C)";
         }
       }
       else{
         if(typeof(#[1]) == "intvec" and typeof(#[2]) == "intvec"){
           curr_weight = #[1];
           target_weight = #[2];

           if(Wpal == "al"){
             order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
           }
           if(Wpal == "M"){
             order_str = "(M("+string(#[1])+"),C)";
           }
           else {
             order_str = "(Wp("+string(#[1])+"),C)";
           //  order_str = "(a("+string(#[1])+"),C)";
           }
         }
         else{
           print("// ** the input  must be \"(ideal,intvec,int)\" or ");
           print("// **                    \"(ideal,intvec,intvec)\"");
           print("// ** and a lex. GB will be computed from \"dp\" to \"lp\"");
         }
       }
     }
     else {
       if(size(#) == 3) {
         if(typeof(#[1]) == "intvec" and typeof(#[2]) == "intvec" and
            typeof(#[3]) == "int")
         {
           curr_weight = #[1];
           target_weight = #[2];
           nP = #[3];
           if(Wpal == "al"){
             order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)";
           }
           if(Wpal == "M"){
             order_str = "(M("+string(#[1])+"),C)";
           }
           else {
             order_str = "(Wp("+string(#[1])+"),C)";
           }
         }
         else{
           print("// ** the input must be \"(ideal,intvec,intvec,int)\"");
           print("// ** and a lex. GB will be computed from \"dp\" to \"lp\"");

         }
       }
       else{
         print("// ** The given input is wrong");
         print("// ** and a lex. GB will be computed from \"dp\" to \"lp\"");
       }
     }
    }
  }

  list result;
  result[1] = nP;
  result[2] = order_str;
  result[3] = curr_weight;
  result[4] = target_weight;

  return(result);
}

/****************
 * Random Walk  *
 ****************/
proc rwalk(ideal Go, int radius, int pert_deg, list #)
"SYNTAX: rwalk(ideal i, int radius);
         if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w);
TYPE:    ideal
PURPOSE: compute the standard basis of the ideal, calculated via
         the Random walk algorithm  from the ordering
         \"(a(v),lp)\", \"dp\" or \"Dp\"
         to the ordering  \"(a(w),lp)\" or \"(a(1,0,...,0),lp)\".
SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, twalk, awalk1, awalk2
KEYWORDS: Groebner walk
EXAMPLE: example rwalk; shows an example"
{
//--------------------  Initialize parameters  ------------------------
int n= nvars(basering);
list OSCTW = OrderStringalp_NP("al",#);
if(size(#)>1)
  {
  if(size(#[2]) == n*n)
    {
    OSCTW= OrderStringalp_NP("M", #);
    }
  }
else
  {
  OSCTW= OrderStringalp_NP("al", #);
  }
string ord_str = OSCTW[2];
intvec curr_weight = OSCTW[3]; // original weight vector
intvec target_weight = OSCTW[4]; // target weight vector
kill OSCTW;

//--------------------  Initialize parameters  ------------------------
def xR = basering;
execute("ring ostR = "+charstr(xR)+",("+varstr(xR)+"),"+ord_str+";");
def old_ring = basering;

ideal G = fetch(xR, Go);
G = system("Mrwalk", G, curr_weight, target_weight, radius, pert_deg, basering);

setring xR;
kill Go;

keepring basering;
ideal result = fetch(old_ring, G);
attrib(result,"isSB",1);
return (result);
}
example
{
  "EXAMPLE:"; echo = 2;
  // compute a Groebner basis of I w.r.t. lp.
  ring r = 32003,(z,y,x), lp;
  ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z;
  int radius = 1;
  int perturb_deg = 2;
  rwalk(I,radius,perturb_deg);
}

/*****************************************
 * Perturbation Walk with random element *
 *****************************************/
proc prwalk(ideal Go, int radius, int o_pert_deg, int t_pert_deg, list #)
"SYNTAX: rwalk(ideal i, int radius);
         if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w);
TYPE:    ideal
PURPOSE: compute the standard basis of the ideal, calculated via
         the Random walk algorithm  from the ordering
         \"(a(v),lp)\", \"dp\" or \"Dp\"
         to the ordering  \"(a(w),lp)\" or \"(a(1,0,...,0),lp)\".
SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, twalk, awalk1, awalk2
KEYWORDS: Groebner walk
EXAMPLE: example rwalk; shows an example"
{
//--------------------  Initialize parameters  ------------------------
list OSCTW = OrderStringalp_NP("al", #);
string ord_str = OSCTW[2];
intvec curr_weight = OSCTW[3]; // original weight vector
intvec target_weight = OSCTW[4]; // target weight vector
kill OSCTW;

//--------------------  Initialize parameters  ------------------------
def xR = basering;
execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
def old_ring = basering;

ideal G = fetch(xR, Go);
G = system("Mprwalk", G, curr_weight, target_weight, radius, o_pert_deg, t_pert_deg, basering);

setring xR;
kill Go;

keepring basering;
ideal result = fetch(old_ring, G);
attrib(result,"isSB",1);
return (result);
}
example
{
  "EXAMPLE:"; echo = 2;
  // compute a Groebner basis of I w.r.t. lp.
  ring r = 32003,(z,y,x), lp;
  ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z;
  int radius = 1;
  int o_perturb_deg = 2;
  int t_perturb_deg = 2;
  prwalk(I,radius,o_perturb_deg,t_perturb_deg);
}

/************************************
 * Fractal Walk with random element *
 ************************************/
proc frandwalk(ideal Go, int radius, list #)
"SYNTAX: frwalk(ideal i, int radius);
         frwalk(ideal i, int radius, intvec v, intvec w);
TYPE:    ideal
PURPOSE: compute the standard basis of the ideal w.r.t. the
        lexicographical ordering or a weighted-lex ordering,
        calculated via  the fractal walk algorithm with random element.
SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, twalk, awalk1, awalk2
KEYWORDS: The fractal walk algorithm
EXAMPLE: example frwalk; shows an example"
{
   // we use ring with ordering (a(...),lp,C)
   list OSCTW    = OrderStringalp_NP("al", #);

   string ord_str =   OSCTW[2];
   intvec curr_weight   =   OSCTW[3]; /* current weight vector */
   intvec target_weight =   OSCTW[4]; /* target weight vector */
   kill OSCTW;
   def xR = basering;

   execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
   def old_ring = basering;
   //print("//** help ring = " + string(basering));
   ideal G = fetch(xR, Go);
   int pert_deg = 2;
   G = system("Mfrwalk", G, curr_weight, target_weight, pert_deg, radius, basering);

   setring xR;
   //kill Go;

   keepring basering;
   ideal result = fetch(old_ring, G);
   attrib(result,"isSB",1);
   return (result);
}
example
{
    "EXAMPLE:"; echo = 2;
    ring r = 0,(z,y,x), lp;
    ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z;
    frandwalk(I,2);
}

/*******************************************
 * Tran Walk Algorithm with random element *
 *******************************************/
proc trwalk(ideal Go, int radius, int pert_deg, list #)
"SYNTAX: trwalk(ideal i);
         trwalk(ideal i, intvec v, intvec w);
TYPE:    ideal
PURPOSE: compute the standard basis of the ideal w.r.t.
         the ordering  \"(a(w),lp)\" or \"(a(1,0,...,0),lp)\",
         calculated via the Tran algorithm with random element.
SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, awalk1, awalk2
KEYWORDS: The Tran algorithm
EXAMPLE: example trwalk; shows an example"
{
  list L = OrderStringalp_NP("al", #);
  int nP = L[1];

  // we use ring with ordering (a(...),lp,C)
  string ord_str =   L[2];
  intvec curr_weight   = L[3];
  intvec target_weight =  L[4];
  kill L;

  def xR = basering;

  execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";");
  def old_ring = basering;

  //print("//** help ring = " + string(basering));
  ideal G = fetch(xR, Go);
  G = system("TranMrImprovwalk", G, curr_weight, target_weight, nP, radius, pert_deg);

  setring xR;
   //kill Go;

  keepring basering;
  ideal result = fetch(old_ring, G);
  attrib(result,"isSB",1);
  return (result);
}
example
{
    "EXAMPLE:"; echo = 2;
    ring r = 32003,(z,y,x), lp;
    ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z;
    int radius = 2;
    int perturb_degree = 3;
    trwalk(I,radius,perturb_degree);
}