| 1 | ///////////////////////////////////////////////// |
|---|
| 2 | version="version rwalk.lib 4.1.2.0 Feb_2019 "; // $Id$ |
|---|
| 3 | category="Commutative Algebra"; |
|---|
| 4 | |
|---|
| 5 | info=" |
|---|
| 6 | LIBRARY: rwalk.lib Groebner Walk Conversion Algorithms |
|---|
| 7 | AUTHOR: Stephan Oberfranz |
|---|
| 8 | |
|---|
| 9 | PROCEDURES: |
|---|
| 10 | prwalk(ideal,int,int[,intvec,intvec]); standard basis of ideal via Random Perturbation Walk algorithm |
|---|
| 11 | rwalk(ideal,int[,intvec,intvec]); standard basis of ideal via Random Walk algorithm |
|---|
| 12 | frandwalk(ideal,int[,intvec,intvec]); standard basis of ideal via Random Fractal Walk algorithm |
|---|
| 13 | |
|---|
| 14 | KEYWORDS: walk, groebner;Groebnerwalk |
|---|
| 15 | SEE ALSO: grwalk_lib; swalk_lib |
|---|
| 16 | "; |
|---|
| 17 | |
|---|
| 18 | /*********************************** |
|---|
| 19 | * Argument string for Random Walk * |
|---|
| 20 | ***********************************/ |
|---|
| 21 | static proc OrderStringalp_NP(string Wpal,list #) |
|---|
| 22 | { |
|---|
| 23 | int n= nvars(basering); |
|---|
| 24 | string order_str = "dp"; |
|---|
| 25 | |
|---|
| 26 | int nP = 1; |
|---|
| 27 | |
|---|
| 28 | //Default: if size(#)=0, the Groebnerwalk algorithm and its developments compute |
|---|
| 29 | //a Groebner basis from "dp" to "lp" |
|---|
| 30 | |
|---|
| 31 | intvec curr_weight = system("Mivdp",n); //define (1,1,...,1) |
|---|
| 32 | intvec target_weight = system("Mivlp",n); //define (1,0,...,0) |
|---|
| 33 | |
|---|
| 34 | // check if the target ring has a weighted lp ordering |
|---|
| 35 | list rl = ringlist(basering); |
|---|
| 36 | if (rl[3][1][1] == "a" and rl[3][2][1] == "lp") { |
|---|
| 37 | target_weight = rl[3][1][2]; |
|---|
| 38 | } |
|---|
| 39 | |
|---|
| 40 | if(size(#) != 0) |
|---|
| 41 | { |
|---|
| 42 | if(size(#) == 1) |
|---|
| 43 | { |
|---|
| 44 | if(typeof(#[1]) == "intvec") { |
|---|
| 45 | curr_weight = #[1]; |
|---|
| 46 | |
|---|
| 47 | if(Wpal == "al"){ |
|---|
| 48 | order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)"; |
|---|
| 49 | } |
|---|
| 50 | else { |
|---|
| 51 | order_str = "(Wp("+string(#[1])+"),C)"; |
|---|
| 52 | } |
|---|
| 53 | } |
|---|
| 54 | else { |
|---|
| 55 | if(typeof(#[1]) == "int"){ |
|---|
| 56 | nP = #[1]; |
|---|
| 57 | } |
|---|
| 58 | else { |
|---|
| 59 | if(typeof(#[1]) == "string") |
|---|
| 60 | { |
|---|
| 61 | if(#[1] == "Dp") { |
|---|
| 62 | order_str = "Dp"; |
|---|
| 63 | } |
|---|
| 64 | else { |
|---|
| 65 | order_str = "dp"; |
|---|
| 66 | } |
|---|
| 67 | } |
|---|
| 68 | else { |
|---|
| 69 | print("// ** the input must be \"(ideal, intvec)\" or "); |
|---|
| 70 | print("// ** \"(ideal, string)\" or "); |
|---|
| 71 | print("// ** \"(ideal, string,intvec)\" or "); |
|---|
| 72 | print("// ** \"(ideal, intvec,intvec)\"."); |
|---|
| 73 | print("// ** a lex. GB will be computed from \"dp\" to \"lp\"."); |
|---|
| 74 | } |
|---|
| 75 | } |
|---|
| 76 | } |
|---|
| 77 | } |
|---|
| 78 | else { |
|---|
| 79 | if(size(#) == 2) { |
|---|
| 80 | if(typeof(#[1]) == "intvec" and typeof(#[2]) == "int") { |
|---|
| 81 | curr_weight = #[1]; |
|---|
| 82 | order_str = "(Wp("+string(#[1])+"),C)"; |
|---|
| 83 | if(Wpal == "al") { |
|---|
| 84 | order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)"; |
|---|
| 85 | } |
|---|
| 86 | if(Wpal == "M") { |
|---|
| 87 | order_str = "(M("+string(#[1])+"),C)"; |
|---|
| 88 | } |
|---|
| 89 | } |
|---|
| 90 | else { |
|---|
| 91 | if(typeof(#[1]) == "intvec" and typeof(#[2]) == "intvec") { |
|---|
| 92 | curr_weight = #[1]; |
|---|
| 93 | target_weight = #[2]; |
|---|
| 94 | order_str = "(Wp("+string(#[1])+"),C)"; |
|---|
| 95 | if(Wpal == "al") { |
|---|
| 96 | order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)"; |
|---|
| 97 | } |
|---|
| 98 | if(Wpal == "M"){ |
|---|
| 99 | order_str = "(M("+string(#[1])+"),C)"; |
|---|
| 100 | } |
|---|
| 101 | } |
|---|
| 102 | else { |
|---|
| 103 | if(typeof(#[1]) == "string" and typeof(#[2]) == "intvec") { |
|---|
| 104 | target_weight = #[2]; |
|---|
| 105 | if(#[1] == "Dp") { |
|---|
| 106 | order_str = "Dp"; |
|---|
| 107 | } |
|---|
| 108 | else { |
|---|
| 109 | order_str = "dp"; |
|---|
| 110 | } |
|---|
| 111 | } |
|---|
| 112 | else { |
|---|
| 113 | print("// ** the input must be \"(ideal, intvec)\" or "); |
|---|
| 114 | print("// ** \"(ideal, string)\" or "); |
|---|
| 115 | print("// ** \"(ideal, string,intvec)\" or "); |
|---|
| 116 | print("// ** \"(ideal, intvec,intvec)\"."); |
|---|
| 117 | print("// ** a lex. GB will be computed from \"dp\" to \"lp\"."); |
|---|
| 118 | } |
|---|
| 119 | } |
|---|
| 120 | } |
|---|
| 121 | } |
|---|
| 122 | else { |
|---|
| 123 | if(size(#) == 3) { |
|---|
| 124 | if(typeof(#[1]) == "intvec" and typeof(#[2]) == "intvec" and |
|---|
| 125 | typeof(#[3]) == "int") { |
|---|
| 126 | curr_weight = #[1]; |
|---|
| 127 | target_weight = #[2]; |
|---|
| 128 | nP = #[3]; |
|---|
| 129 | order_str = "(Wp("+string(#[1])+"),C)"; |
|---|
| 130 | if(Wpal == "al") { |
|---|
| 131 | order_str = "(a("+string(#[1])+"),lp("+string(n) + "),C)"; |
|---|
| 132 | } |
|---|
| 133 | if(Wpal == "M") { |
|---|
| 134 | order_str = "(M("+string(#[1])+"),C)"; |
|---|
| 135 | } |
|---|
| 136 | } |
|---|
| 137 | else { |
|---|
| 138 | if(typeof(#[1]) == "string" and typeof(#[2]) == "intvec" and |
|---|
| 139 | typeof(#[3]) == "int") { |
|---|
| 140 | target_weight = #[2]; |
|---|
| 141 | nP = #[3]; |
|---|
| 142 | if(#[1] == "Dp") { |
|---|
| 143 | order_str = "Dp"; |
|---|
| 144 | } |
|---|
| 145 | else { |
|---|
| 146 | order_str = "dp"; |
|---|
| 147 | } |
|---|
| 148 | } |
|---|
| 149 | else { |
|---|
| 150 | print("// ** the input must be \"(ideal,intvec,intvec,int)\""); |
|---|
| 151 | print("// ** and a lex. GB will be computed from \"dp\" to \"lp\""); |
|---|
| 152 | } |
|---|
| 153 | } |
|---|
| 154 | } |
|---|
| 155 | else { |
|---|
| 156 | print("// ** The given input is wrong"); |
|---|
| 157 | print("// ** and a lex. GB will be computed from \"dp\" to \"lp\""); |
|---|
| 158 | } |
|---|
| 159 | } |
|---|
| 160 | } |
|---|
| 161 | } |
|---|
| 162 | |
|---|
| 163 | list result; |
|---|
| 164 | result[1] = nP; |
|---|
| 165 | result[2] = order_str; |
|---|
| 166 | result[3] = curr_weight; |
|---|
| 167 | result[4] = target_weight; |
|---|
| 168 | |
|---|
| 169 | return(result); |
|---|
| 170 | } |
|---|
| 171 | |
|---|
| 172 | /**************** |
|---|
| 173 | * Random Walk * |
|---|
| 174 | ****************/ |
|---|
| 175 | proc rwalk(ideal Go, int radius, int pert_deg, list #) |
|---|
| 176 | "SYNTAX: rwalk(ideal i, int radius); |
|---|
| 177 | if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w); |
|---|
| 178 | intermediate Groebner bases are not reduced if reduction = 0 |
|---|
| 179 | TYPE: ideal |
|---|
| 180 | PURPOSE: compute the standard basis of the ideal, calculated via |
|---|
| 181 | the Random walk algorithm from the ordering |
|---|
| 182 | \"(a(v),lp)\", \"dp\", \"Dp\" or \"M\" |
|---|
| 183 | to the ordering \"(a(w),lp)\", \"(a(1,0,...,0),lp)\" or \"M\". |
|---|
| 184 | SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, twalk, awalk1, awalk2 |
|---|
| 185 | KEYWORDS: Groebner walk |
|---|
| 186 | EXAMPLE: example rwalk; shows an example" |
|---|
| 187 | { |
|---|
| 188 | //-------------------- Initialize parameters ------------------------ |
|---|
| 189 | int n= nvars(basering); |
|---|
| 190 | list OSCTW = OrderStringalp_NP("al",#); |
|---|
| 191 | if(size(#)>1) |
|---|
| 192 | { |
|---|
| 193 | if(size(#[2]) == n*n) |
|---|
| 194 | { |
|---|
| 195 | OSCTW= OrderStringalp_NP("M", #); |
|---|
| 196 | } |
|---|
| 197 | } |
|---|
| 198 | else |
|---|
| 199 | { |
|---|
| 200 | OSCTW= OrderStringalp_NP("al", #); |
|---|
| 201 | } |
|---|
| 202 | string ord_str = OSCTW[2]; |
|---|
| 203 | intvec curr_weight = OSCTW[3]; // original weight vector |
|---|
| 204 | intvec target_weight = OSCTW[4]; // target weight vector |
|---|
| 205 | kill OSCTW; |
|---|
| 206 | |
|---|
| 207 | //-------------------- Initialize parameters ------------------------ |
|---|
| 208 | int reduction=1; |
|---|
| 209 | int printout=0; |
|---|
| 210 | def xR = basering; |
|---|
| 211 | execute("ring ostR = "+charstr(xR)+",("+varstr(xR)+"),"+ord_str+";"); |
|---|
| 212 | def old_ring = basering; |
|---|
| 213 | |
|---|
| 214 | ideal G = fetch(xR, Go); |
|---|
| 215 | G = system("Mrwalk", G, curr_weight, target_weight, radius, pert_deg, reduction, printout); |
|---|
| 216 | |
|---|
| 217 | setring xR; |
|---|
| 218 | kill Go; |
|---|
| 219 | |
|---|
| 220 | keepring basering; |
|---|
| 221 | ideal result = fetch(old_ring, G); |
|---|
| 222 | attrib(result,"isSB",1); |
|---|
| 223 | return (result); |
|---|
| 224 | } |
|---|
| 225 | example |
|---|
| 226 | { |
|---|
| 227 | "EXAMPLE:"; echo = 2; |
|---|
| 228 | // compute a Groebner basis of I w.r.t. lp. |
|---|
| 229 | ring r = 32003,(z,y,x), lp; |
|---|
| 230 | ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z; |
|---|
| 231 | int radius = 1; |
|---|
| 232 | int perturb_deg = 2; |
|---|
| 233 | rwalk(I,radius,perturb_deg); |
|---|
| 234 | } |
|---|
| 235 | |
|---|
| 236 | /***************************************** |
|---|
| 237 | * Perturbation Walk with random element * |
|---|
| 238 | *****************************************/ |
|---|
| 239 | proc prwalk(ideal Go, int radius, int o_pert_deg, int t_pert_deg, list #) |
|---|
| 240 | "SYNTAX: rwalk(ideal i, int radius); |
|---|
| 241 | if size(#)>0 then rwalk(ideal i, int radius, intvec v, intvec w); |
|---|
| 242 | TYPE: ideal |
|---|
| 243 | PURPOSE: compute the standard basis of the ideal, calculated via |
|---|
| 244 | the Random Perturbation Walk algorithm from the ordering |
|---|
| 245 | \"(a(v),lp)\", \"dp\", \"Dp\" or \"M\" |
|---|
| 246 | to the ordering \"(a(w),lp)\", \"(a(1,0,...,0),lp)\" or \"M\". |
|---|
| 247 | SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, fwalk, twalk, awalk1, awalk2 |
|---|
| 248 | KEYWORDS: Groebner walk |
|---|
| 249 | EXAMPLE: example prwalk; shows an example" |
|---|
| 250 | { |
|---|
| 251 | //-------------------- Initialize parameters ------------------------ |
|---|
| 252 | list OSCTW = OrderStringalp_NP("al", #); |
|---|
| 253 | int nP = OSCTW[1]; |
|---|
| 254 | string ord_str = OSCTW[2]; |
|---|
| 255 | intvec curr_weight = OSCTW[3]; // original weight vector |
|---|
| 256 | intvec target_weight = OSCTW[4]; // target weight vector |
|---|
| 257 | kill OSCTW; |
|---|
| 258 | |
|---|
| 259 | //-------------------- Initialize parameters ------------------------ |
|---|
| 260 | int reduction=1; |
|---|
| 261 | int printout=0; |
|---|
| 262 | def xR = basering; |
|---|
| 263 | execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";"); |
|---|
| 264 | def old_ring = basering; |
|---|
| 265 | |
|---|
| 266 | ideal G = fetch(xR, Go); |
|---|
| 267 | G = system("Mprwalk", G, curr_weight, target_weight, radius, o_pert_deg, t_pert_deg, |
|---|
| 268 | nP, reduction, printout); |
|---|
| 269 | |
|---|
| 270 | setring xR; |
|---|
| 271 | kill Go; |
|---|
| 272 | |
|---|
| 273 | keepring basering; |
|---|
| 274 | ideal result = fetch(old_ring, G); |
|---|
| 275 | attrib(result,"isSB",1); |
|---|
| 276 | return (result); |
|---|
| 277 | } |
|---|
| 278 | example |
|---|
| 279 | { |
|---|
| 280 | "EXAMPLE:"; echo = 2; |
|---|
| 281 | // compute a Groebner basis of I w.r.t. lp. |
|---|
| 282 | ring r = 32003,(z,y,x), lp; |
|---|
| 283 | ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z; |
|---|
| 284 | int radius = 1; |
|---|
| 285 | int o_perturb_deg = 2; |
|---|
| 286 | int t_perturb_deg = 2; |
|---|
| 287 | prwalk(I,radius,o_perturb_deg,t_perturb_deg); |
|---|
| 288 | } |
|---|
| 289 | |
|---|
| 290 | /************************************ |
|---|
| 291 | * Fractal Walk with random element * |
|---|
| 292 | ************************************/ |
|---|
| 293 | proc frandwalk(ideal Go, int radius, list #) |
|---|
| 294 | "SYNTAX: frwalk(ideal i, int radius); |
|---|
| 295 | frwalk(ideal i, int radius, intvec v, intvec w); |
|---|
| 296 | TYPE: ideal |
|---|
| 297 | PURPOSE: compute the standard basis of the ideal w.r.t. the |
|---|
| 298 | lexicographical ordering or a weighted-lex ordering, |
|---|
| 299 | calculated via the Random Fractal walk algorithm. |
|---|
| 300 | SEE ALSO: std, stdfglm, groebner, gwalk, pwalk, twalk, awalk1, awalk2 |
|---|
| 301 | KEYWORDS: The fractal walk algorithm |
|---|
| 302 | EXAMPLE: example frandwalk; shows an example" |
|---|
| 303 | { |
|---|
| 304 | // we use ring with ordering (a(...),lp,C) |
|---|
| 305 | list OSCTW = OrderStringalp_NP("al", #); |
|---|
| 306 | string ord_str = OSCTW[2]; |
|---|
| 307 | intvec curr_weight = OSCTW[3]; /* current weight vector */ |
|---|
| 308 | intvec target_weight = OSCTW[4]; /* target weight vector */ |
|---|
| 309 | kill OSCTW; |
|---|
| 310 | def xR = basering; |
|---|
| 311 | |
|---|
| 312 | execute("ring ostR = ("+charstr(xR)+"),("+varstr(xR)+"),"+ord_str+";"); |
|---|
| 313 | def old_ring = basering; |
|---|
| 314 | //print("//** help ring = " + string(basering)); |
|---|
| 315 | ideal G = fetch(xR, Go); |
|---|
| 316 | int reduction=1; |
|---|
| 317 | int printout=0; |
|---|
| 318 | |
|---|
| 319 | G = system("Mfrwalk", G, curr_weight, target_weight, radius, reduction, printout); |
|---|
| 320 | |
|---|
| 321 | setring xR; |
|---|
| 322 | //kill Go; |
|---|
| 323 | |
|---|
| 324 | keepring basering; |
|---|
| 325 | ideal result = fetch(old_ring, G); |
|---|
| 326 | attrib(result,"isSB",1); |
|---|
| 327 | return (result); |
|---|
| 328 | } |
|---|
| 329 | example |
|---|
| 330 | { |
|---|
| 331 | "EXAMPLE:"; echo = 2; |
|---|
| 332 | ring r = 0,(z,y,x), lp; |
|---|
| 333 | ideal I = y3+xyz+y2z+xz3, 3+xy+x2y+y2z; |
|---|
| 334 | int reduction = 0; |
|---|
| 335 | frandwalk(I,2); |
|---|
| 336 | } |
|---|
