1 | ////////////////////////////////////////////////////////////////////////////// |
---|
2 | version="$Id: freegb.lib,v 1.3 2007-06-24 19:13:20 levandov Exp $"; |
---|
3 | category="Noncommutative"; |
---|
4 | info=" |
---|
5 | LIBRARY: ratgb.lib Twosided Noncommutative Groebner bases in Free Algebras |
---|
6 | AUTHOR: Viktor Levandovskyy, levandov@math.rwth-aachen.de |
---|
7 | |
---|
8 | PROCEDURES: |
---|
9 | freegb(list L, int n); compute two-sided Groebner basis of ideal, encoded via L, up to degree n |
---|
10 | lst2str(list L); convert a list (of modules) into polynomials in free algebra |
---|
11 | mod2str(module M); convert a module into a polynomial in free algebra |
---|
12 | " |
---|
13 | |
---|
14 | // this library computes two-sided GB of an ideal |
---|
15 | // in a free associative algebra |
---|
16 | |
---|
17 | // a monomial is encoded via a vector V |
---|
18 | // where V[1] = coefficient |
---|
19 | // V[1+i] = the corresponding symbol |
---|
20 | |
---|
21 | LIB "qhmoduli.lib"; // for Max |
---|
22 | |
---|
23 | proc vct2mono(vector v) |
---|
24 | { |
---|
25 | // produces a monomial in new vars |
---|
26 | // need a ring with new vars!! |
---|
27 | } |
---|
28 | |
---|
29 | proc lshift(module M, int s, string varing, def lpring) |
---|
30 | { |
---|
31 | // FINALLY IMPLEMENTED AS A PART OT THE CODE |
---|
32 | // shifts a poly from the ring @R to s positions |
---|
33 | // M lives in varing, the result in lpring |
---|
34 | // to be run from varing |
---|
35 | int i, j, k, sm, sv; |
---|
36 | vector v; |
---|
37 | // execute("setring "+lpring); |
---|
38 | setring lpring; |
---|
39 | poly @@p; |
---|
40 | ideal I; |
---|
41 | execute("setring "+varing); |
---|
42 | sm = ncols(M); |
---|
43 | for (i=1; i<=s; i++) |
---|
44 | { |
---|
45 | // modules, e.g. free polynomials |
---|
46 | for (j=1; j<=sm; j++) |
---|
47 | { |
---|
48 | //vectors, e.g. free monomials |
---|
49 | v = M[j]; |
---|
50 | sv = size(v); |
---|
51 | sp = "@@p = @@p + "; |
---|
52 | for (k=2; k<=sv; k++) |
---|
53 | { |
---|
54 | sp = sp + string(v[k])+"("+string(k-1+s)+")*"; |
---|
55 | } |
---|
56 | sp = sp + string(v[1])+";"; // coef; |
---|
57 | setring lpring; |
---|
58 | // execute("setring "+lpring); |
---|
59 | execute(sp); |
---|
60 | execute("setring "+varing); |
---|
61 | } |
---|
62 | setring lpring; |
---|
63 | // execute("setring "+lpring); |
---|
64 | I = I,@@p; |
---|
65 | @@p = 0; |
---|
66 | } |
---|
67 | setring lpring; |
---|
68 | //execute("setring "+lpring); |
---|
69 | export(I); |
---|
70 | // setring varing; |
---|
71 | execute("setring "+varing); |
---|
72 | } |
---|
73 | |
---|
74 | proc skip0(vector v) |
---|
75 | { |
---|
76 | // skips zeros in vector |
---|
77 | int sv = nrows(v); |
---|
78 | int sw = size(v); |
---|
79 | if (sv == sw) |
---|
80 | { |
---|
81 | return(v); |
---|
82 | } |
---|
83 | int i; |
---|
84 | int j=1; |
---|
85 | vector w; |
---|
86 | for (i=1; i<=sv; i++) |
---|
87 | { |
---|
88 | if (v[i] != 0) |
---|
89 | { |
---|
90 | w = w + v[i]*gen(j); |
---|
91 | j++; |
---|
92 | } |
---|
93 | } |
---|
94 | return(w); |
---|
95 | } |
---|
96 | |
---|
97 | proc lst2str(list L) |
---|
98 | "USAGE: lst2str(L); L a list of modules |
---|
99 | RETURN: list (of strings) |
---|
100 | PURPOSE: convert a list (of modules) into polynomials in free algebra |
---|
101 | EXAMPLE: example lst2str; shows examples |
---|
102 | " |
---|
103 | { |
---|
104 | // returns a list of strings |
---|
105 | // being sentences in words built from L |
---|
106 | int i; |
---|
107 | int s = size(L); |
---|
108 | list N; |
---|
109 | for(i=1; i<=s; i++) |
---|
110 | { |
---|
111 | if ((typeof(L[i]) == "module") || (typeof(L[i]) == "matrix") ) |
---|
112 | { |
---|
113 | N[i] = mod2str(L[i]); |
---|
114 | } |
---|
115 | else |
---|
116 | { |
---|
117 | "module or matrix expected in the list"; |
---|
118 | return(N); |
---|
119 | } |
---|
120 | } |
---|
121 | return(N); |
---|
122 | } |
---|
123 | example |
---|
124 | { |
---|
125 | "EXAMPLE:"; echo = 2; |
---|
126 | ring r = 0,(x,y,z),(dp(1),dp(2)); |
---|
127 | module M = [-1,x,y],[-7,y,y],[3,x,x]; |
---|
128 | module N = [1,x,y,x,y],[-2,y,x,y,x],[6,x,y,y,x,y]; |
---|
129 | list L; L[1] = M; L[2] = N; |
---|
130 | lst2str(L); |
---|
131 | } |
---|
132 | |
---|
133 | |
---|
134 | proc mod2str(module M) |
---|
135 | "USAGE: mod2str(M); M a module |
---|
136 | RETURN: string |
---|
137 | PURPOSE: convert a modules into a polynomial in free algebra |
---|
138 | EXAMPLE: example mod2str; shows examples |
---|
139 | " |
---|
140 | { |
---|
141 | // returns a string |
---|
142 | // a sentence in words built from M |
---|
143 | int i; |
---|
144 | int s = ncols(M); |
---|
145 | string t; |
---|
146 | string mp; |
---|
147 | for(i=1; i<=s; i++) |
---|
148 | { |
---|
149 | mp = vct2str(M[i]); |
---|
150 | if (mp[1] == "-") |
---|
151 | { |
---|
152 | t = t + mp; |
---|
153 | } |
---|
154 | else |
---|
155 | { |
---|
156 | t = t + "+" + mp; |
---|
157 | } |
---|
158 | } |
---|
159 | if (t[1]=="+") |
---|
160 | { |
---|
161 | t = t[2..size(t)]; // remove first "+" |
---|
162 | } |
---|
163 | return(t); |
---|
164 | } |
---|
165 | example |
---|
166 | { |
---|
167 | "EXAMPLE:"; echo = 2; |
---|
168 | ring r = 0,(x,y,z),(dp); |
---|
169 | module M = [1,x,y,x,y],[-2,y,x,y,x],[6,x,y,y,x,y]; |
---|
170 | mod2str(M); |
---|
171 | } |
---|
172 | |
---|
173 | proc vct2str(vector v) |
---|
174 | { |
---|
175 | int ppl = printlevel-voice+2; |
---|
176 | // for a word, encoded by v |
---|
177 | // produces a string for it |
---|
178 | v = skip0(v); |
---|
179 | number cf = leadcoef(v[1]); |
---|
180 | int s = size(v); |
---|
181 | string vs,vv,vp,err; |
---|
182 | int i,j,p,q; |
---|
183 | for (i=1; i<=s-1; i++) |
---|
184 | { |
---|
185 | p = IsVar(v[i+1]); |
---|
186 | if (p==0) |
---|
187 | { |
---|
188 | err = "Error: monomial expected at" + string(i+1); |
---|
189 | dbprint(ppl,err); |
---|
190 | return("_"); |
---|
191 | } |
---|
192 | if (p==1) |
---|
193 | { |
---|
194 | vs = vs + string(v[i+1]); |
---|
195 | } |
---|
196 | else //power |
---|
197 | { |
---|
198 | vv = string(v[i+1]); |
---|
199 | q = find(vv,"^"); |
---|
200 | if (q==0) |
---|
201 | { |
---|
202 | q = find(vv,string(p)); |
---|
203 | if (q==0) |
---|
204 | { |
---|
205 | err = "error in find for string "+vv; |
---|
206 | dbprint(ppl,err); |
---|
207 | return("_"); |
---|
208 | } |
---|
209 | } |
---|
210 | // q>0 |
---|
211 | vp = vv[1..q-1]; |
---|
212 | for(j=1;j<=p;j++) |
---|
213 | { |
---|
214 | vs = vs + vp; |
---|
215 | } |
---|
216 | } |
---|
217 | } |
---|
218 | string scf; |
---|
219 | if (cf == -1) |
---|
220 | { |
---|
221 | scf = "-"; |
---|
222 | } |
---|
223 | else |
---|
224 | { |
---|
225 | scf = string(cf); |
---|
226 | if (cf == 1) |
---|
227 | { |
---|
228 | scf = ""; |
---|
229 | } |
---|
230 | } |
---|
231 | vs = scf + vs; |
---|
232 | return(vs); |
---|
233 | } |
---|
234 | example |
---|
235 | { |
---|
236 | ring r = (0,a),(x,y3,z(1)),dp; |
---|
237 | vector v = [-7,x,y3^4,x2,z(1)^3]; |
---|
238 | vct2str(v); |
---|
239 | vector w = [-7a^5+6a,x,y3,y3,x,z(1),z(1)]; |
---|
240 | vct2str(w); |
---|
241 | } |
---|
242 | |
---|
243 | proc IsVar(poly p) |
---|
244 | { |
---|
245 | // checks whether p is a variable indeed |
---|
246 | // if it's a power of a variable, returns the power |
---|
247 | if (p==0) { return(0); } //"p=0"; |
---|
248 | poly q = leadmonom(p); |
---|
249 | if ( (p-lead(p)) !=0 ) { return(0); } // "p-lm(p)>0"; |
---|
250 | intvec v = leadexp(p); |
---|
251 | int s = size(v); |
---|
252 | int i=1; |
---|
253 | int cnt = 0; |
---|
254 | int pwr = 0; |
---|
255 | for (i=1; i<=s; i++) |
---|
256 | { |
---|
257 | if (v[i] != 0) |
---|
258 | { |
---|
259 | cnt++; |
---|
260 | pwr = v[i]; |
---|
261 | } |
---|
262 | } |
---|
263 | // "cnt:"; cnt; |
---|
264 | if (cnt==1) { return(pwr); } |
---|
265 | else { return(0); } |
---|
266 | } |
---|
267 | example |
---|
268 | { |
---|
269 | ring r = 0,(x,y),dp; |
---|
270 | poly f = xy+1; |
---|
271 | IsVar(f); |
---|
272 | poly g = xy; |
---|
273 | IsVar(g); |
---|
274 | poly h = y^3; |
---|
275 | IsVar(h); |
---|
276 | poly i = 1; |
---|
277 | IsVar(i); |
---|
278 | } |
---|
279 | |
---|
280 | // given the element -7xy^2x, it is represented as [-7,x,y^2,x] or as [-7,x,y,y,x] |
---|
281 | // use the orig ord on (x,y,z) and expand it blockwise to (x(i),y(i),z(i)) |
---|
282 | |
---|
283 | // the correspondences: |
---|
284 | // monomial in K<x,y,z> <<--->> vector in R |
---|
285 | // polynomial in K<x,y,z> <<--->> list of vectors (matrix/module) in R |
---|
286 | // ideal in K<x,y,z> <<--->> list of matrices/modules in R |
---|
287 | |
---|
288 | |
---|
289 | // 1. form a new ring |
---|
290 | // 2. produce shifted generators |
---|
291 | // 3. compute GB |
---|
292 | // 4. skip shifted elts |
---|
293 | // 5. go back to orig vars, produce strings/modules |
---|
294 | // 6. return the result |
---|
295 | |
---|
296 | proc freegb(list LM, int d) |
---|
297 | "USAGE: freegb(L, d); L a list of modules, d an integer |
---|
298 | RETURN: ring |
---|
299 | PURPOSE: compute the two-sided Groebner basis of an ideal, encoded by L in |
---|
300 | the free associative algebra, up to degree d |
---|
301 | EXAMPLE: example freegb; shows examples |
---|
302 | " |
---|
303 | { |
---|
304 | // d = up to degree, will be shifted to d+1 |
---|
305 | if (d<1) {"bad d"; return(0);} |
---|
306 | |
---|
307 | int ppl = printlevel-voice+2; |
---|
308 | string err = ""; |
---|
309 | |
---|
310 | int i,j,s; |
---|
311 | def save = basering; |
---|
312 | // determine max no of places in the input |
---|
313 | int slm = size(LM); // numbers of polys in the ideal |
---|
314 | int sm; |
---|
315 | intvec iv; |
---|
316 | module M; |
---|
317 | for (i=1; i<=slm; i++) |
---|
318 | { |
---|
319 | // modules, e.g. free polynomials |
---|
320 | M = LM[i]; |
---|
321 | sm = ncols(M); |
---|
322 | for (j=1; j<=sm; j++) |
---|
323 | { |
---|
324 | //vectors, e.g. free monomials |
---|
325 | iv = iv, size(M[j])-1; // 1 place is reserved by the coeff |
---|
326 | } |
---|
327 | } |
---|
328 | int D = Max(iv); // max size of input words |
---|
329 | if (d<D) {"bad d"; return(LM);} |
---|
330 | D = D + d-1; |
---|
331 | // D = d; |
---|
332 | list LR = ringlist(save); |
---|
333 | list L, tmp; |
---|
334 | L[1] = LR[1]; // ground field |
---|
335 | L[4] = LR[4]; // quotient ideal |
---|
336 | tmp = LR[2]; // varnames |
---|
337 | s = size(LR[2]); |
---|
338 | for (i=1; i<=D; i++) |
---|
339 | { |
---|
340 | for (j=1; j<=s; j++) |
---|
341 | { |
---|
342 | tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")"; |
---|
343 | } |
---|
344 | } |
---|
345 | for (i=1; i<=s; i++) |
---|
346 | { |
---|
347 | tmp[i] = string(tmp[i])+"("+string(1)+")"; |
---|
348 | } |
---|
349 | L[2] = tmp; |
---|
350 | list OrigNames = LR[2]; |
---|
351 | // ordering: d blocks of the ord on r |
---|
352 | // try to get whether the ord on r is blockord itself |
---|
353 | s = size(LR[3]); |
---|
354 | if (s==2) |
---|
355 | { |
---|
356 | // not a blockord, 1 block + module ord |
---|
357 | tmp = LR[3][s]; // module ord |
---|
358 | for (i=1; i<=D; i++) |
---|
359 | { |
---|
360 | LR[3][s-1+i] = LR[3][1]; |
---|
361 | } |
---|
362 | LR[3][s+D] = tmp; |
---|
363 | } |
---|
364 | if (s>2) |
---|
365 | { |
---|
366 | // there are s-1 blocks |
---|
367 | int nb = s-1; |
---|
368 | tmp = LR[3][s]; // module ord |
---|
369 | for (i=1; i<=D; i++) |
---|
370 | { |
---|
371 | for (j=1; j<=nb; j++) |
---|
372 | { |
---|
373 | LR[3][i*nb+j] = LR[3][j]; |
---|
374 | } |
---|
375 | } |
---|
376 | // size(LR[3]); |
---|
377 | LR[3][nb*(D+1)+1] = tmp; |
---|
378 | } |
---|
379 | L[3] = LR[3]; |
---|
380 | def @R = ring(L); |
---|
381 | setring @R; |
---|
382 | ideal I; |
---|
383 | poly @p; |
---|
384 | s = size(OrigNames); |
---|
385 | // "s:";s; |
---|
386 | // convert LM to canonical vectors (no powers) |
---|
387 | setring save; |
---|
388 | kill M; // M was defined earlier |
---|
389 | module M; |
---|
390 | slm = size(LM); // numbers of polys in the ideal |
---|
391 | int sv,k,l; |
---|
392 | vector v; |
---|
393 | // poly p; |
---|
394 | string sp; |
---|
395 | setring @R; |
---|
396 | poly @@p=0; |
---|
397 | setring save; |
---|
398 | for (l=1; l<=slm; l++) |
---|
399 | { |
---|
400 | // modules, e.g. free polynomials |
---|
401 | M = LM[l]; |
---|
402 | sm = ncols(M); // in intvec iv the sizes are stored |
---|
403 | for (i=0; i<=d-iv[l]; i++) |
---|
404 | { |
---|
405 | // modules, e.g. free polynomials |
---|
406 | for (j=1; j<=sm; j++) |
---|
407 | { |
---|
408 | //vectors, e.g. free monomials |
---|
409 | v = M[j]; |
---|
410 | sv = size(v); |
---|
411 | // "sv:";sv; |
---|
412 | sp = "@@p = @@p + "; |
---|
413 | for (k=2; k<=sv; k++) |
---|
414 | { |
---|
415 | sp = sp + string(v[k])+"("+string(k-1+i)+")*"; |
---|
416 | } |
---|
417 | sp = sp + string(v[1])+";"; // coef; |
---|
418 | setring @R; |
---|
419 | execute(sp); |
---|
420 | setring save; |
---|
421 | } |
---|
422 | setring @R; |
---|
423 | // "@@p:"; @@p; |
---|
424 | I = I,@@p; |
---|
425 | @@p = 0; |
---|
426 | setring save; |
---|
427 | } |
---|
428 | } |
---|
429 | kill sp; |
---|
430 | // 3. compute GB |
---|
431 | setring @R; |
---|
432 | dbprint(ppl,"computing GB"); |
---|
433 | // ideal J = groebner(I); |
---|
434 | ideal J = slimgb(I); |
---|
435 | dbprint(ppl,J); |
---|
436 | // 4. skip shifted elts |
---|
437 | ideal K = select1(J,1,s); // s = size(OrigNames) |
---|
438 | dbprint(ppl,K); |
---|
439 | dbprint(ppl, "done with GB"); |
---|
440 | // K contains vars x(1),...z(1) = images of originals |
---|
441 | // 5. go back to orig vars, produce strings/modules |
---|
442 | if (K[1] == 0) |
---|
443 | { |
---|
444 | "no reasonable output, GB gives 0"; |
---|
445 | return(0); |
---|
446 | } |
---|
447 | int sk = size(K); |
---|
448 | int sp, sx, a, b; |
---|
449 | intvec x; |
---|
450 | poly p,q; |
---|
451 | poly pn; |
---|
452 | // vars in 'save' |
---|
453 | setring save; |
---|
454 | module N; |
---|
455 | list LN; |
---|
456 | vector V; |
---|
457 | poly pn; |
---|
458 | // test and skip exponents >=2 |
---|
459 | setring @R; |
---|
460 | for(i=1; i<=sk; i++) |
---|
461 | { |
---|
462 | p = K[i]; |
---|
463 | while (p!=0) |
---|
464 | { |
---|
465 | q = lead(p); |
---|
466 | // "processing q:";q; |
---|
467 | x = leadexp(q); |
---|
468 | sx = size(x); |
---|
469 | for(k=1; k<=sx; k++) |
---|
470 | { |
---|
471 | if ( x[k] >= 2 ) |
---|
472 | { |
---|
473 | err = "skip: the value x[k] is " + string(x[k]); |
---|
474 | dbprint(ppl,err); |
---|
475 | // return(0); |
---|
476 | K[i] = 0; |
---|
477 | p = 0; |
---|
478 | q = 0; |
---|
479 | break; |
---|
480 | } |
---|
481 | } |
---|
482 | p = p - q; |
---|
483 | } |
---|
484 | } |
---|
485 | K = simplify(K,2); |
---|
486 | sk = size(K); |
---|
487 | for(i=1; i<=sk; i++) |
---|
488 | { |
---|
489 | // setring save; |
---|
490 | // V = 0; |
---|
491 | setring @R; |
---|
492 | p = K[i]; |
---|
493 | while (p!=0) |
---|
494 | { |
---|
495 | q = lead(p); |
---|
496 | err = "processing q:" + string(q); |
---|
497 | dbprint(ppl,err); |
---|
498 | x = leadexp(q); |
---|
499 | sx = size(x); |
---|
500 | pn = leadcoef(q); |
---|
501 | setring save; |
---|
502 | pn = imap(@R,pn); |
---|
503 | V = V + leadcoef(pn)*gen(1); |
---|
504 | for(k=1; k<=sx; k++) |
---|
505 | { |
---|
506 | if (x[k] ==1) |
---|
507 | { |
---|
508 | a = k / s; // block number=a+1, a!=0 |
---|
509 | b = k % s; // remainder |
---|
510 | // printf("a: %s, b: %s",a,b); |
---|
511 | if (b == 0) |
---|
512 | { |
---|
513 | // that is it's the last var in the block |
---|
514 | b = s; |
---|
515 | a = a-1; |
---|
516 | } |
---|
517 | V = V + var(b)*gen(a+2); |
---|
518 | } |
---|
519 | // else |
---|
520 | // { |
---|
521 | // printf("error: the value x[k] is %s", x[k]); |
---|
522 | // return(0); |
---|
523 | // } |
---|
524 | } |
---|
525 | err = "V: " + string(V); |
---|
526 | dbprint(ppl,err); |
---|
527 | // printf("V: %s", string(V)); |
---|
528 | N = N,V; |
---|
529 | V = 0; |
---|
530 | setring @R; |
---|
531 | p = p - q; |
---|
532 | pn = 0; |
---|
533 | } |
---|
534 | setring save; |
---|
535 | LN[i] = simplify(N,2); |
---|
536 | N = 0; |
---|
537 | } |
---|
538 | setring save; |
---|
539 | return(LN); |
---|
540 | } |
---|
541 | example |
---|
542 | { |
---|
543 | "EXAMPLE:"; echo = 2; |
---|
544 | ring r = 0,(x,y,z),(dp(1),dp(2)); |
---|
545 | module M = [-1,x,y],[-7,y,y],[3,x,x]; |
---|
546 | module N = [1,x,y,x],[-1,y,x,y]; |
---|
547 | list L; L[1] = M; L[2] = N; |
---|
548 | lst2str(L); |
---|
549 | def U = freegb(L,5); |
---|
550 | lst2str(U); |
---|
551 | } |
---|
552 | |
---|
553 | proc crs(list LM, int d) |
---|
554 | "USAGE: crs(L, d); L a list of modules, d an integer |
---|
555 | RETURN: ring |
---|
556 | PURPOSE: create a ring and shift the ideal |
---|
557 | EXAMPLE: example crs; shows examples |
---|
558 | " |
---|
559 | { |
---|
560 | // d = up to degree, will be shifted to d+1 |
---|
561 | if (d<1) {"bad d"; return(0);} |
---|
562 | |
---|
563 | int ppl = printlevel-voice+2; |
---|
564 | string err = ""; |
---|
565 | |
---|
566 | int i,j,s; |
---|
567 | def save = basering; |
---|
568 | // determine max no of places in the input |
---|
569 | int slm = size(LM); // numbers of polys in the ideal |
---|
570 | int sm; |
---|
571 | intvec iv; |
---|
572 | module M; |
---|
573 | for (i=1; i<=slm; i++) |
---|
574 | { |
---|
575 | // modules, e.g. free polynomials |
---|
576 | M = LM[i]; |
---|
577 | sm = ncols(M); |
---|
578 | for (j=1; j<=sm; j++) |
---|
579 | { |
---|
580 | //vectors, e.g. free monomials |
---|
581 | iv = iv, size(M[j])-1; // 1 place is reserved by the coeff |
---|
582 | } |
---|
583 | } |
---|
584 | int D = Max(iv); // max size of input words |
---|
585 | if (d<D) {"bad d"; return(LM);} |
---|
586 | D = D + d-1; |
---|
587 | // D = d; |
---|
588 | list LR = ringlist(save); |
---|
589 | list L, tmp; |
---|
590 | L[1] = LR[1]; // ground field |
---|
591 | L[4] = LR[4]; // quotient ideal |
---|
592 | tmp = LR[2]; // varnames |
---|
593 | s = size(LR[2]); |
---|
594 | for (i=1; i<=D; i++) |
---|
595 | { |
---|
596 | for (j=1; j<=s; j++) |
---|
597 | { |
---|
598 | tmp[i*s+j] = string(tmp[j])+"("+string(i)+")"; |
---|
599 | } |
---|
600 | } |
---|
601 | for (i=1; i<=s; i++) |
---|
602 | { |
---|
603 | tmp[i] = string(tmp[i])+"("+string(0)+")"; |
---|
604 | } |
---|
605 | L[2] = tmp; |
---|
606 | list OrigNames = LR[2]; |
---|
607 | // ordering: d blocks of the ord on r |
---|
608 | // try to get whether the ord on r is blockord itself |
---|
609 | s = size(LR[3]); |
---|
610 | if (s==2) |
---|
611 | { |
---|
612 | // not a blockord, 1 block + module ord |
---|
613 | tmp = LR[3][s]; // module ord |
---|
614 | for (i=1; i<=D; i++) |
---|
615 | { |
---|
616 | LR[3][s-1+i] = LR[3][1]; |
---|
617 | } |
---|
618 | LR[3][s+D] = tmp; |
---|
619 | } |
---|
620 | if (s>2) |
---|
621 | { |
---|
622 | // there are s-1 blocks |
---|
623 | int nb = s-1; |
---|
624 | tmp = LR[3][s]; // module ord |
---|
625 | for (i=1; i<=D; i++) |
---|
626 | { |
---|
627 | for (j=1; j<=nb; j++) |
---|
628 | { |
---|
629 | LR[3][i*nb+j] = LR[3][j]; |
---|
630 | } |
---|
631 | } |
---|
632 | // size(LR[3]); |
---|
633 | LR[3][nb*(D+1)+1] = tmp; |
---|
634 | } |
---|
635 | L[3] = LR[3]; |
---|
636 | def @R = ring(L); |
---|
637 | setring @R; |
---|
638 | ideal I; |
---|
639 | poly @p; |
---|
640 | s = size(OrigNames); |
---|
641 | // "s:";s; |
---|
642 | // convert LM to canonical vectors (no powers) |
---|
643 | setring save; |
---|
644 | kill M; // M was defined earlier |
---|
645 | module M; |
---|
646 | slm = size(LM); // numbers of polys in the ideal |
---|
647 | int sv,k,l; |
---|
648 | vector v; |
---|
649 | // poly p; |
---|
650 | string sp; |
---|
651 | setring @R; |
---|
652 | poly @@p=0; |
---|
653 | setring save; |
---|
654 | for (l=1; l<=slm; l++) |
---|
655 | { |
---|
656 | // modules, e.g. free polynomials |
---|
657 | M = LM[l]; |
---|
658 | sm = ncols(M); // in intvec iv the sizes are stored |
---|
659 | for (i=0; i<=d-iv[l]; i++) |
---|
660 | { |
---|
661 | // modules, e.g. free polynomials |
---|
662 | for (j=1; j<=sm; j++) |
---|
663 | { |
---|
664 | //vectors, e.g. free monomials |
---|
665 | v = M[j]; |
---|
666 | sv = size(v); |
---|
667 | // "sv:";sv; |
---|
668 | sp = "@@p = @@p + "; |
---|
669 | for (k=2; k<=sv; k++) |
---|
670 | { |
---|
671 | sp = sp + string(v[k])+"("+string(k-2+i)+")*"; |
---|
672 | } |
---|
673 | sp = sp + string(v[1])+";"; // coef; |
---|
674 | setring @R; |
---|
675 | execute(sp); |
---|
676 | setring save; |
---|
677 | } |
---|
678 | setring @R; |
---|
679 | // "@@p:"; @@p; |
---|
680 | I = I,@@p; |
---|
681 | @@p = 0; |
---|
682 | setring save; |
---|
683 | } |
---|
684 | } |
---|
685 | setring @R; |
---|
686 | export I; |
---|
687 | return(@R); |
---|
688 | } |
---|
689 | example |
---|
690 | { |
---|
691 | "EXAMPLE:"; echo = 2; |
---|
692 | ring r = 0,(x,y,z),(dp(1),dp(2)); |
---|
693 | module M = [-1,x,y],[-7,y,y],[3,x,x]; |
---|
694 | module N = [1,x,y,x],[-1,y,x,y]; |
---|
695 | list L; L[1] = M; L[2] = N; |
---|
696 | lst2str(L); |
---|
697 | def U = crs(L,5); |
---|
698 | setring U; U; |
---|
699 | I; |
---|
700 | } |
---|
701 | |
---|
702 | proc ex_shift() |
---|
703 | { |
---|
704 | LIB "freegb.lib"; |
---|
705 | ring r = 0,(x,y,z),(dp(1),dp(2)); |
---|
706 | module M = [-1,x,y],[-7,y,y],[3,x,x]; |
---|
707 | module N = [1,x,y,x],[-1,y,x,y]; |
---|
708 | list L; L[1] = M; L[2] = N; |
---|
709 | lst2str(L); |
---|
710 | def U = crs(L,5); |
---|
711 | setring U; U; |
---|
712 | I; |
---|
713 | poly p = I[2]; // I[8]; |
---|
714 | p; |
---|
715 | system("stest",p,7,7,3); // error |
---|
716 | poly q1 = system("stest",p,1,7,3); //ok |
---|
717 | poly q6 = system("stest",p,6,7,3); //ok |
---|
718 | system("btest",p,3); |
---|
719 | system("btest",q1,3); |
---|
720 | system("btest",q6,3); |
---|
721 | } |
---|
722 | |
---|
723 | proc ex2() |
---|
724 | { |
---|
725 | option(prot); |
---|
726 | LIB "freegb.lib"; |
---|
727 | ring r = 0,(x,y),dp; |
---|
728 | module M = [-1,x,y],[3,x,x]; // 3x^2 - xy |
---|
729 | def U = freegb(M,7); |
---|
730 | lst2str(U); |
---|
731 | } |
---|
732 | |
---|
733 | proc ex_nonhomog() |
---|
734 | { |
---|
735 | option(prot); |
---|
736 | LIB "freegb.lib"; |
---|
737 | ring r = 0,(x,y,h),dp; |
---|
738 | list L; |
---|
739 | module M; |
---|
740 | M = [-1,y,y],[1,x,x,x]; // x3-y2 |
---|
741 | L[1] = M; |
---|
742 | M = [1,x,h],[-1,h,x]; // xh-hx |
---|
743 | L[2] = M; |
---|
744 | M = [1,y,h],[-1,h,y]; // yh-hy |
---|
745 | L[3] = M; |
---|
746 | def U = freegb(L,4); |
---|
747 | lst2str(U); |
---|
748 | // strange elements in the basis |
---|
749 | } |
---|
750 | |
---|
751 | proc ex_nonhomog_comm() |
---|
752 | { |
---|
753 | option(prot); |
---|
754 | LIB "freegb.lib"; |
---|
755 | ring r = 0,(x,y),dp; |
---|
756 | module M = [-1,y,y],[1,x,x,x]; |
---|
757 | def U = freegb(M,5); |
---|
758 | lst2str(U); |
---|
759 | } |
---|
760 | |
---|
761 | proc ex_nonhomog_h() |
---|
762 | { |
---|
763 | option(prot); |
---|
764 | LIB "freegb.lib"; |
---|
765 | ring r = 0,(x,y,h),(a(1,1),dp); |
---|
766 | module M = [-1,y,y,h],[1,x,x,x]; // x3 - y2h |
---|
767 | def U = freegb(M,6); |
---|
768 | lst2str(U); |
---|
769 | } |
---|
770 | |
---|
771 | proc ex_nonhomog_h2() |
---|
772 | { |
---|
773 | option(prot); |
---|
774 | LIB "freegb.lib"; |
---|
775 | ring r = 0,(x,y,h),(dp); |
---|
776 | list L; |
---|
777 | module M; |
---|
778 | M = [-1,y,y,h],[1,x,x,x]; // x3 - y2h |
---|
779 | L[1] = M; |
---|
780 | M = [1,x,h],[-1,h,x]; // xh - hx |
---|
781 | L[2] = M; |
---|
782 | M = [1,y,h],[-1,h,y]; // yh - hy |
---|
783 | L[3] = M; |
---|
784 | def U = freegb(L,3); |
---|
785 | lst2str(U); |
---|
786 | // strange answer CHECK |
---|
787 | } |
---|
788 | |
---|
789 | |
---|
790 | proc ex_nonhomog_3() |
---|
791 | { |
---|
792 | option(prot); |
---|
793 | LIB "./freegb.lib"; |
---|
794 | ring r = 0,(x,y,z),(dp); |
---|
795 | list L; |
---|
796 | module M; |
---|
797 | M = [1,z,y],[-1,x]; // zy - x |
---|
798 | L[1] = M; |
---|
799 | M = [1,z,x],[-1,y]; // zx - y |
---|
800 | L[2] = M; |
---|
801 | M = [1,y,x],[-1,z]; // yx - z |
---|
802 | L[3] = M; |
---|
803 | lst2str(L); |
---|
804 | list U = freegb(L,4); |
---|
805 | lst2str(U); |
---|
806 | // strange answer CHECK |
---|
807 | } |
---|
808 | |
---|
809 | |
---|
810 | |
---|
811 | proc ex_densep_2() |
---|
812 | { |
---|
813 | option(prot); |
---|
814 | LIB "freegb.lib"; |
---|
815 | ring r = (0,a,b,c),(x,y),(Dp); // deglex |
---|
816 | module M = [1,x,x], [a,x,y], [b,y,x], [c,y,y]; |
---|
817 | lst2str(M); |
---|
818 | list U = freegb(M,5); |
---|
819 | lst2str(U); |
---|
820 | // a=b is important -> finite basis!!! |
---|
821 | module M = [1,x,x], [a,x,y], [a,y,x], [c,y,y]; |
---|
822 | lst2str(M); |
---|
823 | list U = freegb(M,5); |
---|
824 | lst2str(U); |
---|
825 | } |
---|