1 | //last change: 13.02.2001 (Eric Westenberger) |
---|
2 | /////////////////////////////////////////////////////////////////////////////// |
---|
3 | version="$Id: presolve.lib,v 1.27 2006-12-18 18:37:04 Singular Exp $"; |
---|
4 | category="Symbolic-numerical solving"; |
---|
5 | info=" |
---|
6 | LIBRARY: presolve.lib Pre-Solving of Polynomial Equations |
---|
7 | AUTHOR: Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de, |
---|
8 | |
---|
9 | PROCEDURES: |
---|
10 | degreepart(id,d1,d2); elements of id of total degree >= d1 and <= d2 |
---|
11 | elimlinearpart(id); linear part eliminated from id |
---|
12 | elimpart(id[,n]); partial elimination of vars [among first n vars] |
---|
13 | elimpartanyr(i,p); factors of p partially eliminated from i in any ring |
---|
14 | fastelim(i,p[..]); fast elimination of factors of p from i [options] |
---|
15 | findvars(id[..]); ideal of variables occuring in id [more information] |
---|
16 | hilbvec(id[,c,o]); intvec of Hilberseries of id [in char c and ord o] |
---|
17 | linearpart(id); elements of id of total degree <=1 |
---|
18 | tolessvars(id[,]); maps id to new basering having only vars occuring in id |
---|
19 | solvelinearpart(id); reduced std-basis of linear part of id |
---|
20 | sortandmap(id[..]); map to new basering with vars sorted w.r.t. complexity |
---|
21 | sortvars(id[n1,p1..]); sort vars w.r.t. complexity in id [different blocks] |
---|
22 | valvars(id[..]); valuation of vars w.r.t. to their complexity in id |
---|
23 | idealSplit(id,tF,fS); a list of ideals such that their intersection |
---|
24 | has the same radical as id |
---|
25 | ( parameters in square brackets [] are optional) |
---|
26 | "; |
---|
27 | |
---|
28 | LIB "inout.lib"; |
---|
29 | LIB "general.lib"; |
---|
30 | LIB "matrix.lib"; |
---|
31 | LIB "ring.lib"; |
---|
32 | LIB "elim.lib"; |
---|
33 | /////////////////////////////////////////////////////////////////////////////// |
---|
34 | proc shortid (id,int n,list #) |
---|
35 | "USAGE: shortid(id,n[,e]); id= ideal/module, n,e=integers |
---|
36 | RETURN: - if called with two arguments or e=0: |
---|
37 | @* same type as id, containing generators of id having <= n terms. |
---|
38 | @* - if called with three arguments and e!=0: |
---|
39 | @* a list L: |
---|
40 | @* L[1]: same type as id, containing generators of id having <= n terms. |
---|
41 | @* L[2]: number of corresponding generator of id |
---|
42 | NOTE: May be used to compute partial standard basis in case id is to hard |
---|
43 | EXAMPLE: example shortid; shows an example |
---|
44 | " |
---|
45 | { |
---|
46 | intvec v; |
---|
47 | int ii; |
---|
48 | for(ii=1; ii<=ncols(id); ii++) |
---|
49 | { |
---|
50 | if (size(id[ii]) <=n and id[ii]!=0 ) |
---|
51 | { |
---|
52 | v=v,ii; |
---|
53 | } |
---|
54 | if (size(id[ii]) > n ) |
---|
55 | { |
---|
56 | id[ii]=0; |
---|
57 | } |
---|
58 | } |
---|
59 | if( size(v)>1 ) |
---|
60 | { |
---|
61 | v = v[2..size(v)]; |
---|
62 | } |
---|
63 | id = simplify(id,2); |
---|
64 | list L = id,v; |
---|
65 | if ( size(#)==0 ) |
---|
66 | { |
---|
67 | return(id); |
---|
68 | } |
---|
69 | if ( size(#)!=0 ) |
---|
70 | { |
---|
71 | if(#[1]==0) |
---|
72 | { |
---|
73 | return(id); |
---|
74 | } |
---|
75 | if(#[1]!=0) |
---|
76 | { |
---|
77 | return(L); |
---|
78 | } |
---|
79 | } |
---|
80 | } |
---|
81 | example |
---|
82 | { "EXAMPLE:"; echo = 2; |
---|
83 | ring s=0,(x,y,z,w),dp; |
---|
84 | ideal i = (x3+y2+yw2)^2,(xz+z2)^2,xyz-w2-xzw; |
---|
85 | shortid(i,3); |
---|
86 | } |
---|
87 | /////////////////////////////////////////////////////////////////////////////// |
---|
88 | |
---|
89 | proc degreepart (id,int d1,int d2,list #) |
---|
90 | "USAGE: degreepart(id,d1,d2[,v]); id=ideal/module, d1,d1=integers, v=intvec |
---|
91 | RETURN: generators of id of [v-weighted] total degree >= d1 and <= d2 |
---|
92 | (default: v = 1,...,1) |
---|
93 | EXAMPLE: example degreepart; shows an example |
---|
94 | " |
---|
95 | { |
---|
96 | def dpart = id; |
---|
97 | int s,ii = size(id),0; |
---|
98 | if ( size(#)==0 ) |
---|
99 | { |
---|
100 | for ( ii=1; ii<=s; ii=ii+1 ) |
---|
101 | { |
---|
102 | dpart[ii] = (jet(id[ii],d1-1)==0)*(id[ii]==jet(id[ii],d2))*id[ii]; |
---|
103 | } |
---|
104 | } |
---|
105 | else |
---|
106 | { |
---|
107 | for ( ii=1; ii<=s; ii=ii+1 ) |
---|
108 | { |
---|
109 | dpart[ii]=(jet(id[ii],d1-1,#[1])==0)*(id[ii]==jet(id[ii],d2,#[1]))*id[ii]; |
---|
110 | } |
---|
111 | } |
---|
112 | return(simplify(dpart,2)); |
---|
113 | } |
---|
114 | example |
---|
115 | { "EXAMPLE:"; echo = 2; |
---|
116 | ring r=0,(x,y,z),dp; |
---|
117 | ideal i=1+x+x2+x3+x4,3,xz+y3+z8; |
---|
118 | degreepart(i,0,4); |
---|
119 | module m=[x,y,z],x*[x3,y2,z],[1,x2,z3,0,1]; |
---|
120 | intvec v=2,3,6; |
---|
121 | show(degreepart(m,8,8,v)); |
---|
122 | } |
---|
123 | /////////////////////////////////////////////////////////////////////////////// |
---|
124 | |
---|
125 | proc elimlinearpart (ideal i,list #) |
---|
126 | "USAGE: elimlinearpart(i[,n]); i=ideal, n=integer,@* |
---|
127 | default: n=nvars(basering) |
---|
128 | RETURN: list L with 5 entries: |
---|
129 | @format |
---|
130 | L[1]: (interreduced) ideal obtained from i by substituing |
---|
131 | from the first n variables those, which appear in a linear part |
---|
132 | of i, by putting this part into triangular form |
---|
133 | L[2]: ideal of variables which have been substituted |
---|
134 | L[3]: ideal, j-th element defines substitution of j-th var in [2] |
---|
135 | L[4]: ideal of variables of basering, eliminated ones are set to 0 |
---|
136 | L[5]: ideal, describing the map from the basering to itself such that |
---|
137 | L[1] is the image of i |
---|
138 | @end format |
---|
139 | NOTE: the procedure does always interreduce the ideal i internally w.r.t. |
---|
140 | ordering dp. |
---|
141 | EXAMPLE: example elimlinearpart; shows an example |
---|
142 | " |
---|
143 | { |
---|
144 | int ii,n,fi,k; |
---|
145 | string o, newo; |
---|
146 | intvec getoption = option(get); |
---|
147 | option(redSB); |
---|
148 | def P = basering; |
---|
149 | n = nvars(P); |
---|
150 | //--------------- replace ordering by dp-ordering if necessary ---------------- |
---|
151 | o = "dp("+string(n)+")"; |
---|
152 | fi = find(ordstr(P),o); |
---|
153 | if( fi == 0 or find(ordstr(P),"a") != 0 ) |
---|
154 | { |
---|
155 | execute("ring newP = ("+charstr(P)+"),("+varstr(P)+"),dp;"); |
---|
156 | ideal i = imap(P,i); |
---|
157 | } |
---|
158 | //---------------------------------- start ------------------------------------ |
---|
159 | if ( size(#)!=0 ) { n=#[1]; } |
---|
160 | ideal maxi,rest = maxideal(1),0; |
---|
161 | if ( n < nvars(P) ) { rest = maxi[n+1..nvars(P)]; } |
---|
162 | attrib(rest,"isSB",1); |
---|
163 | //-------------------- interreduce and find linear part ---------------------- |
---|
164 | // interred does the only real work. Because of ordering dp the linear part is |
---|
165 | // within the first elements after interreduction |
---|
166 | // **: perhaps Bareiss to constant matrix of linear part instead of interred, |
---|
167 | // and/or for big systems, interred only those generators of id |
---|
168 | // which do not contain elements not to be eliminated |
---|
169 | |
---|
170 | ideal id = interred(i); |
---|
171 | |
---|
172 | if(id[1] == 1 ) //special case of unit ideal |
---|
173 | { |
---|
174 | setring P; |
---|
175 | list L = ideal(1), ideal(0), ideal(0), maxideal(1), maxideal(1); |
---|
176 | option(set,getoption); |
---|
177 | return(L); |
---|
178 | } |
---|
179 | |
---|
180 | for ( ii=1; ii<=size(id); ii++ ) |
---|
181 | { |
---|
182 | if( deg(id[ii]) > 1) { break; } |
---|
183 | k=ii; |
---|
184 | } |
---|
185 | if( k == 0 ) { ideal lin; } |
---|
186 | else { ideal lin = id[1..k];} |
---|
187 | if( k < size(id) ) { id = id[k+1..size(id)]; } |
---|
188 | else { id = 0; } |
---|
189 | //----- remove generators from lin containing vars not to be eliminated ------ |
---|
190 | if ( n < nvars(P) ) |
---|
191 | { |
---|
192 | for ( ii=1; ii<=size(lin); ii++ ) |
---|
193 | { |
---|
194 | if ( reduce(lead(lin[ii]),rest) == 0 ) |
---|
195 | { |
---|
196 | id=lin[ii],id; |
---|
197 | lin[ii] = 0; |
---|
198 | } |
---|
199 | } |
---|
200 | } |
---|
201 | lin = simplify(lin,3); |
---|
202 | attrib(lin,"isSB",1); |
---|
203 | ideal eva = lead(lin); |
---|
204 | attrib(eva,"isSB",1); |
---|
205 | ideal neva = reduce(maxideal(1),eva); |
---|
206 | //------------------ go back to original ring end return --------------------- |
---|
207 | if( fi == 0 or find(ordstr(P),"a") != 0 ) |
---|
208 | { |
---|
209 | setring P; |
---|
210 | ideal id = imap(newP,id); |
---|
211 | ideal eva = imap(newP,eva); |
---|
212 | ideal lin = imap(newP,lin); |
---|
213 | ideal neva = imap(newP,neva); |
---|
214 | } |
---|
215 | |
---|
216 | eva = eva[ncols(eva)..1]; // sorting according to variables in basering |
---|
217 | lin = lin[ncols(lin)..1]; |
---|
218 | ideal phi= neva; |
---|
219 | k = 1; |
---|
220 | for( ii=1; ii<=n; ii++ ) |
---|
221 | { |
---|
222 | if( neva[ii] == 0 ) |
---|
223 | { |
---|
224 | phi[ii] = eva[k]-lin[k]; |
---|
225 | k=k+1; |
---|
226 | } |
---|
227 | } |
---|
228 | list L = id, eva, lin, neva, phi; |
---|
229 | option(set,getoption); |
---|
230 | return(L); |
---|
231 | } |
---|
232 | example |
---|
233 | { "EXAMPLE:"; echo = 2; |
---|
234 | ring s=0,(x,y,z),dp; |
---|
235 | ideal i = x3+y2+z,x2y2+z3,y+z+1; |
---|
236 | elimlinearpart(i); |
---|
237 | } |
---|
238 | /////////////////////////////////////////////////////////////////////////////// |
---|
239 | |
---|
240 | proc elimpart (ideal i,list #) |
---|
241 | "USAGE: elimpart(i [,n,e] ); i=ideal, n,e=integers |
---|
242 | n : only the first n vars are considered for substitution,@* |
---|
243 | e =0: substitute from linear part of i (same as elimlinearpart)@* |
---|
244 | e!=0: eliminate also by direct substitution@* |
---|
245 | (default: n = nvars(basering), e = 1) |
---|
246 | RETURN: list of 5 objects: |
---|
247 | @format |
---|
248 | [1]: ideal obtained by substituting from the first n variables those |
---|
249 | from i, which appear in the linear part of i (or, if e!=0, which |
---|
250 | can be expressed directly in the remaining vars) |
---|
251 | [2]: ideal, variables which have been substituted |
---|
252 | [3]: ideal, i-th element defines substitution of i-th var in [2] |
---|
253 | [4]: ideal of variables of basering, substituted ones are set to 0 |
---|
254 | [5]: ideal, describing the map from the basering, say k[x(1..m)], to |
---|
255 | itself onto k[..variables from [4]..] and [1] is the image of i |
---|
256 | @end format |
---|
257 | The ideal i is generated by [1] and [3] in k[x(1..m)], the map [5] |
---|
258 | maps [3] to 0, hence induces an isomorphism |
---|
259 | @format |
---|
260 | k[x(1..m)]/i -> k[..variables from [4]..]/[1] |
---|
261 | @end format |
---|
262 | NOTE: If the basering has ordering (c,dp), this is faster for big ideals, |
---|
263 | since it avoids internal ring change and mapping. |
---|
264 | EXAMPLE: example elimpart; shows an example |
---|
265 | " |
---|
266 | { |
---|
267 | def P = basering; |
---|
268 | int n,e = nvars(P),1; |
---|
269 | if ( size(#)==1 ) { n=#[1]; } |
---|
270 | if ( size(#)==2 ) { n=#[1]; e=#[2];} |
---|
271 | //----------- interreduce linear part with proc elimlinearpart ---------------- |
---|
272 | // lin = ideal after interreduction of linear part |
---|
273 | // eva = eliminated (substituted) variables |
---|
274 | // sub = polynomials defining substitution |
---|
275 | // neva= not eliminated variables |
---|
276 | // phi = map describing substitution |
---|
277 | list L = elimlinearpart(i,n); |
---|
278 | ideal lin, eva, sub, neva, phi = L[1], L[2], L[3], L[4], L[5]; |
---|
279 | //-------- direct substitution of variables if possible and if e!=0 ----------- |
---|
280 | // first find terms lin1 of pure degree 1 in each poly of lin |
---|
281 | // k1 = pure degree 1 part, k1+k2 = those polys of lin which contained a pure |
---|
282 | // degree 1 part. |
---|
283 | // Then go to ring newP with ordering c,dp(n) and create a matrix with size(k1) |
---|
284 | // colums and 2 rows, such that if [f1,f2] is a column of M then f1+f2 is one |
---|
285 | // of the polys of lin containing a pure degree 1 part and f1 is this part |
---|
286 | // interreduce this matrix (i.e. Gauss elimination on linear part, with rest |
---|
287 | // transformed accordingly). |
---|
288 | int ii, kk; |
---|
289 | if ( e!=0 ) |
---|
290 | { |
---|
291 | ideal k1,k2; |
---|
292 | int l = size(lin); |
---|
293 | ideal lin1 = jet(lin,1) - jet(lin,0); // part of pure degree 1 |
---|
294 | lin = lin - lin1; // rest, part of degree 1 substracted |
---|
295 | |
---|
296 | for( ii=1; ii<=l; ii++ ) |
---|
297 | { |
---|
298 | if( lin1[ii] != 0 ) |
---|
299 | { |
---|
300 | kk = kk+1; |
---|
301 | k1[kk] = lin1[ii]; // part of pure degree 1, renumbered |
---|
302 | k2[kk] = lin[ii]; // rest of those polys which had a degree 1 part |
---|
303 | lin[ii] = 0; |
---|
304 | } |
---|
305 | } |
---|
306 | |
---|
307 | if( kk != 0 ) |
---|
308 | { |
---|
309 | if( ordstr(P) != "c,dp(n)" ) |
---|
310 | { |
---|
311 | execute("ring newP = ("+charstr(P)+"),("+varstr(P)+"),(c,dp);"); |
---|
312 | ideal k1 = imap(P,k1); |
---|
313 | ideal k2 = imap(P,k2); |
---|
314 | ideal lin = imap(P,lin); |
---|
315 | ideal eva = imap(P,eva); |
---|
316 | ideal sub = imap(P,sub); |
---|
317 | ideal neva = imap(P,neva); |
---|
318 | } |
---|
319 | ideal k12 = k1,k2; |
---|
320 | matrix M = matrix(k12,2,kk); |
---|
321 | // M = interred(M); |
---|
322 | l = ncols(M); |
---|
323 | k1 = M[1,1..l]; |
---|
324 | k2 = M[2,1..l]; |
---|
325 | ideal kin = matrix(k1)+matrix(k2); |
---|
326 | lin = simplify(lin,2); |
---|
327 | |
---|
328 | l = size(kin); |
---|
329 | poly p; map phi; ideal max; |
---|
330 | for ( ii=1; ii<=n; ii++ ) |
---|
331 | { |
---|
332 | for (kk=1; kk<=l; kk++ ) |
---|
333 | { |
---|
334 | p = kin[kk]/var(ii); |
---|
335 | if ( deg(p) == 0 ) |
---|
336 | { |
---|
337 | eva = eva+var(ii); |
---|
338 | neva[ii] = 0; |
---|
339 | sub = sub+kin[kk]/p; |
---|
340 | max = maxideal(1); |
---|
341 | max[ii] = var(ii) - (kin[kk]/p); |
---|
342 | phi = basering,max; |
---|
343 | lin = phi(lin); |
---|
344 | kin = simplify(phi(kin),2); |
---|
345 | l = size(kin); |
---|
346 | // ii=ii+1; |
---|
347 | break; |
---|
348 | } |
---|
349 | } |
---|
350 | } |
---|
351 | lin = kin+lin; |
---|
352 | } |
---|
353 | } |
---|
354 | for( ii=1; ii<=size(lin); ii++ ) |
---|
355 | { |
---|
356 | lin[ii] = cleardenom(lin[ii]); |
---|
357 | } |
---|
358 | if( defined(newP) ) |
---|
359 | { |
---|
360 | setring P; |
---|
361 | lin = imap(newP,lin); |
---|
362 | eva = imap(newP,eva); |
---|
363 | sub = imap(newP,sub); |
---|
364 | neva = imap(newP,neva); |
---|
365 | } |
---|
366 | for( ii=1; ii<=n; ii++ ) |
---|
367 | { |
---|
368 | for( kk=1; kk<=size(eva); kk++ ) |
---|
369 | { |
---|
370 | if (phi[ii] == eva[kk] ) |
---|
371 | { phi[ii] = eva[kk]-sub[kk]; break; } |
---|
372 | } |
---|
373 | } |
---|
374 | map psi=P,phi; |
---|
375 | ideal phi1=maxideal(1); |
---|
376 | for(ii=1;ii<=size(eva);ii++){phi1=psi(phi1);} |
---|
377 | L = lin, eva, sub, neva, phi1; |
---|
378 | return(L); |
---|
379 | } |
---|
380 | example |
---|
381 | { "EXAMPLE:"; echo = 2; |
---|
382 | ring s=0,(x,y,z),dp; |
---|
383 | ideal i =x2+y2,x2+y+1; |
---|
384 | elimpart(i,3,0); |
---|
385 | elimpart(i,3,1); |
---|
386 | } |
---|
387 | |
---|
388 | /////////////////////////////////////////////////////////////////////////////// |
---|
389 | |
---|
390 | proc elimpartanyr (ideal i, list #) |
---|
391 | "USAGE: elimpartanyr(i [,p,e] ); i=ideal, p=polynomial, e=integer@* |
---|
392 | p: product of vars to be eliminated,@* |
---|
393 | e =0: substitute from linear part of i (same as elimlinearpart)@* |
---|
394 | e!=0: eliminate also by direct substitution@* |
---|
395 | (default: p=product of all vars, e=1) |
---|
396 | RETURN: list of 6 objects: |
---|
397 | @format |
---|
398 | [1]: (interreduced) ideal obtained by substituting from i those vars |
---|
399 | appearing in p, which occur in the linear part of i (or which can |
---|
400 | be expressed directly in the remaining variables, if e!=0) |
---|
401 | [2]: ideal, variables which have been substituted |
---|
402 | [3]: ideal, i-th element defines substitution of i-th var in [2] |
---|
403 | [4]: ideal of variables of basering, substituted ones are set to 0 |
---|
404 | [5]: ideal, describing the map from the basering, say k[x(1..m)], to |
---|
405 | itself onto k[..variables fom [4]..] and [1] is the image of i |
---|
406 | [6]: int, # of vars considered for substitution (= # of factors of p) |
---|
407 | @end format |
---|
408 | The ideal i is generated by [1] and [3] in k[x(1..m)], the map [5] |
---|
409 | maps [3] to 0, hence induces an isomorphism |
---|
410 | @format |
---|
411 | k[x(1..m)]/i -> k[..variables fom [4]..]/[1] |
---|
412 | @end format |
---|
413 | NOTE: the procedure uses @code{execute} to create a ring with ordering dp |
---|
414 | and vars placed correctly and then applies @code{elimpart}. |
---|
415 | EXAMPLE: example elimpartanyr; shows an example |
---|
416 | " |
---|
417 | { |
---|
418 | def P = basering; |
---|
419 | int j,n,e = 0,0,1; |
---|
420 | poly p = product(maxideal(1)); |
---|
421 | if ( size(#)==1 ) { p=#[1]; } |
---|
422 | if ( size(#)==2 ) { p=#[1]; e=#[2]; } |
---|
423 | string a,b; |
---|
424 | for ( j=1; j<=nvars(P); j++ ) |
---|
425 | { |
---|
426 | if (deg(p/var(j))>=0) { a = a+varstr(j)+","; n = n+1; } |
---|
427 | else { b = b+varstr(j)+","; } |
---|
428 | } |
---|
429 | if ( size(b) != 0 ) { b = b[1,size(b)-1]; } |
---|
430 | else { a = a[1,size(a)-1]; } |
---|
431 | execute("ring gnir ="+charstr(P)+",("+a+b+"),dp;"); |
---|
432 | ideal i = imap(P,i); |
---|
433 | list L = elimpart(i,n,e)+list(n); |
---|
434 | setring P; |
---|
435 | list L = imap(gnir,L); |
---|
436 | return(L); |
---|
437 | } |
---|
438 | example |
---|
439 | { "EXAMPLE:"; echo = 2; |
---|
440 | ring s=0,(x,y,z),dp; |
---|
441 | ideal i = x3+y2+z,x2y2+z3,y+z+1; |
---|
442 | elimpartanyr(i,z); |
---|
443 | } |
---|
444 | /////////////////////////////////////////////////////////////////////////////// |
---|
445 | |
---|
446 | proc fastelim (ideal i, poly p, list #) |
---|
447 | "USAGE: fastelim(i,p[h,o,a,b,e,m]); i=ideal, p=polynomial; h,o,a,b,e=integers |
---|
448 | p: product of variables to be eliminated;@* |
---|
449 | Optional parameters: |
---|
450 | @format |
---|
451 | - h !=0: use Hilbert-series driven std-basis computation |
---|
452 | - o !=0: use proc @code{valvars} for a - hopefully - optimal ordering of vars |
---|
453 | - a !=0: order vars to be eliminated w.r.t. increasing complexity |
---|
454 | - b !=0: order vars not to be eliminated w.r.t. increasing complexity |
---|
455 | - e !=0: use @code{elimpart} first to eliminate easy part |
---|
456 | - m !=0: compute a minimal system of generators |
---|
457 | @end format |
---|
458 | (default: h,o,a,b,e,m = 0,1,0,0,0,0) |
---|
459 | RETURN: ideal obtained from i by eliminating those variables, which occur in p |
---|
460 | EXAMPLE: example fastelim; shows an example. |
---|
461 | " |
---|
462 | { |
---|
463 | def P = basering; |
---|
464 | int h,o,a,b,e,m = 0,1,0,0,0,0; |
---|
465 | if ( size(#) == 1 ) { h=#[1]; } |
---|
466 | if ( size(#) == 2 ) { h=#[1]; o=#[2]; } |
---|
467 | if ( size(#) == 3 ) { h=#[1]; o=#[2]; a=#[3]; } |
---|
468 | if ( size(#) == 4 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4];} |
---|
469 | if ( size(#) == 5 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4]; e=#[5]; } |
---|
470 | if ( size(#) == 6 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4]; e=#[5]; m=#[6]; } |
---|
471 | list L = elimpartanyr(i,p,e); |
---|
472 | poly q = product(L[2]); //product of vars which are already eliminated |
---|
473 | if ( q==0 ) { q=1; } |
---|
474 | p = p/q; //product of vars which must still be eliminated |
---|
475 | int nu = size(L[5])-size(L[2]); //number of vars which must still be eliminated |
---|
476 | if ( p==1 ) //ready if no vars are left |
---|
477 | { //compute minbase if 3-rd argument !=0 |
---|
478 | if ( m != 0 ) { L[1]=minbase(L[1]); } |
---|
479 | return(L); |
---|
480 | } |
---|
481 | //---------------- create new ring with remaining variables ------------------- |
---|
482 | string newvar = string(L[4]); |
---|
483 | L = L[1],p; |
---|
484 | execute("ring r1=("+charstr(P)+"),("+newvar+"),"+"dp;"); |
---|
485 | list L = imap(P,L); |
---|
486 | //------------------- find "best" ordering of variables ---------------------- |
---|
487 | newvar = string(maxideal(1)); |
---|
488 | if ( o != 0 ) |
---|
489 | { |
---|
490 | list ordevar = valvars(L[1],a,L[2],b); |
---|
491 | intvec v = ordevar[1]; |
---|
492 | newvar=string(sort(maxideal(1),v)[1]); |
---|
493 | //------------ create new ring with "best" ordering of variables -------------- |
---|
494 | def r0=changevar(newvar); |
---|
495 | setring r0; |
---|
496 | list L = imap(r1,L); |
---|
497 | kill r1; |
---|
498 | def r1 = r0; |
---|
499 | kill r0; |
---|
500 | } |
---|
501 | //----------------- h==0: eliminate remaining vars directly ------------------- |
---|
502 | if ( h == 0 ) |
---|
503 | { |
---|
504 | L[1] = eliminate(L[1],L[2]); |
---|
505 | def r2 = r1; |
---|
506 | } |
---|
507 | else |
---|
508 | //------- h!=0: homogenize and compute Hilbert series using hilbvec ---------- |
---|
509 | { |
---|
510 | intvec hi = hilbvec(L[1]); // Hilbert series of i |
---|
511 | execute("ring r2=("+charstr(P)+"),("+varstr(basering)+",@homo),dp;"); |
---|
512 | list L = imap(r1,L); |
---|
513 | L[1] = homog(L[1],@homo); // @homo = homogenizing var |
---|
514 | //---- use Hilbert-series to eliminate variables with Hilbert-driven std ----- |
---|
515 | L[1] = eliminate(L[1],L[2],hi); |
---|
516 | L[1]=subst(L[1],@homo,1); // dehomogenize by setting @homo=1 |
---|
517 | } |
---|
518 | if ( m != 0 ) // compute minbase |
---|
519 | { |
---|
520 | if ( #[1] != 0 ) { L[1] = minbase(L[1]); } |
---|
521 | } |
---|
522 | def id = L[1]; |
---|
523 | setring P; |
---|
524 | return(imap(r2,id)); |
---|
525 | } |
---|
526 | example |
---|
527 | { "EXAMPLE:"; echo = 2; |
---|
528 | ring s=31991,(e,f,x,y,z,t,u,v,w,a,b,c,d),dp; |
---|
529 | ideal i = w2+f2-1, x2+t2+a2-1, y2+u2+b2-1, z2+v2+c2-1, |
---|
530 | d2+e2-1, f4+2u, wa+tf, xy+tu+ab; |
---|
531 | fastelim(i,xytua,1,1); //with hilb,valvars |
---|
532 | fastelim(i,xytua,1,0,1); //with hilb,minbase |
---|
533 | } |
---|
534 | /////////////////////////////////////////////////////////////////////////////// |
---|
535 | |
---|
536 | proc faststd (@id, list #) |
---|
537 | "USAGE: faststd(id [,\"hilb\",\"sort\",\"dec\",o,\"blocks\"]); |
---|
538 | id=ideal/module, o=string (allowed:\"lp\",\"dp\",\"Dp\",\"ls\", |
---|
539 | \"ds\",\"Ds\"), \"hilb\",\"sort\",\"dec\",\"block\" options for |
---|
540 | Hilbert-driven std, and the procedure sortandmap |
---|
541 | RETURN: a ring R, in which an ideal STD_id is stored: @* |
---|
542 | - the ring R differs from the active basering only in the choice |
---|
543 | of monomial ordering and in the sorting of the variables. |
---|
544 | - STD_id is a standard basis for the image (under imap) of the input |
---|
545 | ideal/module id with respect to the new monomial ordering. @* |
---|
546 | NOTE: Using the optional input parameters, we may modify the computations |
---|
547 | performed: @* |
---|
548 | - \"hilb\" : use Hilbert-driven standard basis computation@* |
---|
549 | - \"sort\" : use 'sortandmap' for a best sorting of the variables@* |
---|
550 | - \"dec\" : order vars w.r.t. decreasing complexity (with \"sort\")@* |
---|
551 | - \"block\" : create block ordering, each block having ordstr=o, s.t. |
---|
552 | vars of same complexity are in one block (with \"sort\")@* |
---|
553 | - o : defines the basic ordering of the resulting ring@* |
---|
554 | [default: o=ordering of 1st block of basering (if allowed, else o=\"dp\"], |
---|
555 | \"sort\", if none of the optional parameters is given @* |
---|
556 | This procedure is only useful for hard problems where other methods fail.@* |
---|
557 | \"hilb\" is useful for hard orderings (as \"lp\") or for characteristic 0,@* |
---|
558 | it is correct for \"lp\",\"dp\",\"Dp\" (and for block orderings combining |
---|
559 | these) but not for s-orderings or if the vars have different weights.@* |
---|
560 | There seem to be only few cases in which \"dec\" is fast. |
---|
561 | SEE ALSO: groebner |
---|
562 | EXAMPLE: example faststd; shows an example. |
---|
563 | " |
---|
564 | { |
---|
565 | def @P = basering; |
---|
566 | int @h,@s,@n,@m,@ii = 0,0,0,0,0; |
---|
567 | string @o,@va,@c = ordstr(basering),"",""; |
---|
568 | //-------------------- prepare ordering and set options ----------------------- |
---|
569 | if ( @o[1]=="c" or @o[1]=="C") |
---|
570 | { @o = @o[3,2]; } |
---|
571 | else |
---|
572 | { @o = @o[1,2]; } |
---|
573 | if( @o[1]!="d" and @o[1]!="D" and @o[1]!="l") |
---|
574 | { @o="dp"; } |
---|
575 | |
---|
576 | if (size(#) == 0 ) |
---|
577 | { @s = 1; } |
---|
578 | for ( @ii=1; @ii<=size(#); @ii++ ) |
---|
579 | { |
---|
580 | if ( typeof(#[@ii]) != "string" ) |
---|
581 | { |
---|
582 | "// wrong syntax! type: help faststd"; |
---|
583 | return(); |
---|
584 | } |
---|
585 | else |
---|
586 | { |
---|
587 | if ( #[@ii] == "hilb" ) { @h = 1; } |
---|
588 | if ( #[@ii] == "dec" ) { @n = 1; } |
---|
589 | if ( #[@ii] == "block" ) { @m = 1; } |
---|
590 | if ( #[@ii] == "sort" ) { @s = 1; } |
---|
591 | if ( #[@ii]=="lp" or #[@ii]=="dp" or #[@ii]=="Dp" or #[@ii]=="ls" |
---|
592 | or #[@ii]=="ds" or #[@ii]=="Ds" ) { @o = #[@ii]; } |
---|
593 | } |
---|
594 | } |
---|
595 | if( voice==2 ) { "// chosen options, hilb sort dec block:",@h,@s,@n,@m; } |
---|
596 | |
---|
597 | //-------------------- nosort: create ring with new name ---------------------- |
---|
598 | if ( @s==0 ) |
---|
599 | { |
---|
600 | execute("ring @S1 =("+charstr(@P)+"),("+varstr(@P)+"),("+@o+");"); |
---|
601 | def STD_id = imap(@P,@id); |
---|
602 | if ( @h==0 ) { STD_id = std(STD_id); } |
---|
603 | } |
---|
604 | |
---|
605 | //---------------------- no hilb: compute SB directly ------------------------- |
---|
606 | if ( @s != 0 and @h == 0 ) |
---|
607 | { |
---|
608 | intvec getoption = option(get); |
---|
609 | option(redSB); |
---|
610 | @id = interred(sort(@id)[1]); |
---|
611 | poly @p = product(maxideal(1),1..nvars(@P)); |
---|
612 | def @S1=sortandmap(@id,@n,@p,0,@o,@m); |
---|
613 | setring @S1; |
---|
614 | option(set,getoption); |
---|
615 | def STD_id=imap(@S1,IMAG); |
---|
616 | STD_id = std(STD_id); |
---|
617 | } |
---|
618 | //------- hilb: homogenize and compute Hilbert-series using hilbvec ----------- |
---|
619 | // this uses another standardbasis computation |
---|
620 | if ( @h != 0 ) |
---|
621 | { |
---|
622 | execute("ring @Q=("+charstr(@P)+"),("+varstr(@P)+",@homo),("+@o+");"); |
---|
623 | def @id = imap(@P,@id); |
---|
624 | @id = homog(@id,@homo); // @homo = homogenizing var |
---|
625 | if ( @s != 0 ) |
---|
626 | { |
---|
627 | intvec getoption = option(get); |
---|
628 | option(redSB); |
---|
629 | @id = interred(sort(@id)[1]); |
---|
630 | poly @p = product(maxideal(1),1..(nvars(@Q)-1)); |
---|
631 | def @S1=sortandmap(@id,@n,@p,0,@o,@m); |
---|
632 | setring @S1; |
---|
633 | option(set,getoption); |
---|
634 | kill @Q; |
---|
635 | def @Q= basering; |
---|
636 | def @id = IMAG; |
---|
637 | } |
---|
638 | intvec @hi; // encoding of Hilbert-series of i |
---|
639 | @hi = hilbvec(@id); |
---|
640 | //if ( @s!=0 ) { @hi = hilbvec(@id,"32003",ordstr(@Q)); } |
---|
641 | //else { @hi = hilbvec(@id); } |
---|
642 | //-------------------------- use Hilbert-driven std -------------------------- |
---|
643 | @id = std(@id,@hi); |
---|
644 | @id = subst(@id,@homo,1); // dehomogenize by setting @homo=1 |
---|
645 | @va = varstr(@Q)[1,size(varstr(@Q))-6]; |
---|
646 | if ( @s!=0 ) |
---|
647 | { |
---|
648 | @o = ordstr(@Q); |
---|
649 | if ( @o[1]=="c" or @o[1]=="C") { @o = @o[1,size(@o)-6]; } |
---|
650 | else { @o = @o[1,size(@o)-8] + @o[size(@o)-1,2]; } |
---|
651 | } |
---|
652 | kill @S1; |
---|
653 | execute("ring @S1=("+charstr(@Q)+"),("+@va+"),("+@o+");"); |
---|
654 | def STD_id = imap(@Q,@id); |
---|
655 | } |
---|
656 | attrib(STD_id,"isSB",1); |
---|
657 | export STD_id; |
---|
658 | if (defined(IMAG)) { kill IMAG; } |
---|
659 | setring @P; |
---|
660 | dbprint(printlevel-voice+3," |
---|
661 | // 'faststd' created a ring, in which an object STD_id is stored. |
---|
662 | // To access the object, type (if the name R was assigned to the return value): |
---|
663 | setring R; STD_id; "); |
---|
664 | return(@S1); |
---|
665 | } |
---|
666 | example |
---|
667 | { "EXAMPLE:"; echo = 2; |
---|
668 | system("--ticks-per-sec",100); // show time in 1/100 sec |
---|
669 | ring s = 0,(e,f,x,y,z,t,u,v,w,a,b,c,d),(c,lp); |
---|
670 | ideal i = w2+f2-1, x2+t2+a2-1, y2+u2+b2-1, z2+v2+c2-1, |
---|
671 | d2+e2-1, f4+2u, wa+tf, xy+tu+ab; |
---|
672 | option(prot); timer=1; |
---|
673 | int time = timer; |
---|
674 | ideal j=std(i); |
---|
675 | timer-time; |
---|
676 | dim(j),mult(j); |
---|
677 | |
---|
678 | time = timer; |
---|
679 | def R=faststd(i); // use "best" ordering of vars |
---|
680 | timer-time; |
---|
681 | show(R);setring R;dim(STD_id),mult(STD_id); |
---|
682 | |
---|
683 | setring s;kill R;time = timer; |
---|
684 | def R=faststd(i,"hilb"); // hilb-std only |
---|
685 | timer-time; |
---|
686 | show(R);setring R;dim(STD_id),mult(STD_id); |
---|
687 | |
---|
688 | setring s;kill R;time = timer; |
---|
689 | def R=faststd(i,"hilb","sort"); // hilb-std,"best" ordering |
---|
690 | timer-time; |
---|
691 | show(R);setring R;dim(STD_id),mult(STD_id); |
---|
692 | |
---|
693 | setring s;kill R;time = timer; |
---|
694 | def R=faststd(i,"hilb","sort","block","dec"); // hilb-std,"best",blocks |
---|
695 | timer-time; |
---|
696 | show(R);setring R;dim(STD_id),mult(STD_id); |
---|
697 | |
---|
698 | setring s;kill R;time = timer; |
---|
699 | timer-time;time = timer; |
---|
700 | def R=faststd(i,"sort","block","Dp"); //"best",decreasing,Dp-blocks |
---|
701 | timer-time; |
---|
702 | show(R);setring R;dim(STD_id),mult(STD_id); |
---|
703 | } |
---|
704 | /////////////////////////////////////////////////////////////////////////////// |
---|
705 | |
---|
706 | proc findvars(id, list #) |
---|
707 | "USAGE: findvars(id [,any] ); id=poly/ideal/vector/module/matrix, any=any type |
---|
708 | RETURN: if no second argument is present: ideal of variables occuring in id,@* |
---|
709 | if a second argument is given (of any type): list L with 4 entries: |
---|
710 | @format |
---|
711 | L[1]: ideal of variables occuring in id |
---|
712 | L[2]: intvec of variables occuring in id |
---|
713 | L[3]: ideal of variables not occuring in id |
---|
714 | L[4]: intvec of variables not occuring in id |
---|
715 | @end format |
---|
716 | EXAMPLE: example findvars; shows an example |
---|
717 | " |
---|
718 | { |
---|
719 | int ii,n; |
---|
720 | ideal found, notfound; |
---|
721 | intvec f,nf; |
---|
722 | n = nvars(basering); |
---|
723 | ideal i = simplify(ideal(matrix(id)),10); |
---|
724 | matrix M[ncols(i)][1] = i; |
---|
725 | vector v = module(M)[1]; |
---|
726 | ideal max = maxideal(1); |
---|
727 | |
---|
728 | for (ii=1; ii<=n; ii++) |
---|
729 | { |
---|
730 | if ( v != subst(v,var(ii),0) ) |
---|
731 | { |
---|
732 | found = found+var(ii); |
---|
733 | f = f,ii; |
---|
734 | } |
---|
735 | else |
---|
736 | { |
---|
737 | notfound = notfound+var(ii); |
---|
738 | nf = nf,ii; |
---|
739 | } |
---|
740 | } |
---|
741 | if ( size(f)>1 ) { f = f[2..size(f)]; } //intvec of found vars |
---|
742 | if ( size(nf)>1 ) { nf = nf[2..size(nf)]; } //intvec of vars not found |
---|
743 | if( size(#)==0 ) { return(found); } |
---|
744 | if( size(#)!=0 ) { list L = found,f,notfound,nf; return(L); } |
---|
745 | } |
---|
746 | example |
---|
747 | { "EXAMPLE:"; echo = 2; |
---|
748 | ring s = 0,(e,f,x,y,t,u,v,w,a,d),dp; |
---|
749 | ideal i = w2+f2-1, x2+t2+a2-1; |
---|
750 | findvars(i); |
---|
751 | findvars(i,1); |
---|
752 | } |
---|
753 | /////////////////////////////////////////////////////////////////////////////// |
---|
754 | |
---|
755 | proc hilbvec (@id, list #) |
---|
756 | "USAGE: hilbvec(id[,c,o]); id=poly/ideal/vector/module/matrix, c,o=strings,@* |
---|
757 | c=char, o=ordering used by @code{hilb}@* |
---|
758 | (default: c=\"32003\", o=\"dp\") |
---|
759 | RETURN: intvec of 1-st Hilbert-series of id, computed in char c and ordering o |
---|
760 | NOTE: id must be homogeneous (i.e. all vars have weight 1) |
---|
761 | EXAMPLE: example hilbvec; shows an example |
---|
762 | " |
---|
763 | { |
---|
764 | def @P = basering; |
---|
765 | string @c,@o = "32003", "dp"; |
---|
766 | if ( size(#) == 1 ) { @c = #[1]; } |
---|
767 | if ( size(#) == 2 ) { @c = #[1]; @o = #[2]; } |
---|
768 | string @si = typeof(@id)+" @i = "+string(@id)+";"; //** weg |
---|
769 | execute("ring @r=("+@c+"),("+varstr(basering)+"),("+@o+");"); |
---|
770 | //**def i = imap(P,@id); |
---|
771 | execute(@si); //** weg |
---|
772 | //show(basering); |
---|
773 | @i = std(@i); |
---|
774 | intvec @hi = hilb(@i,1); // intvec of 1-st Hilbert-series of id |
---|
775 | return(@hi); |
---|
776 | } |
---|
777 | example |
---|
778 | { "EXAMPLE:"; echo = 2; |
---|
779 | ring s = 0,(e,f,x,y,z,t,u,v,w,a,b,c,d,H),dp; |
---|
780 | ideal id = w2+f2-1, x2+t2+a2-1, y2+u2+b2-1, z2+v2+c2-1, |
---|
781 | d2+e2-1, f4+2u, wa+tf, xy+tu+ab; |
---|
782 | id = homog(id,H); |
---|
783 | hilbvec(id); |
---|
784 | } |
---|
785 | /////////////////////////////////////////////////////////////////////////////// |
---|
786 | |
---|
787 | proc linearpart (id) |
---|
788 | "USAGE: linearpart(id); id=ideal/module |
---|
789 | RETURN: generators of id of total degree <= 1 |
---|
790 | EXAMPLE: example linearpart; shows an example |
---|
791 | " |
---|
792 | { |
---|
793 | return(degreepart(id,0,1)); |
---|
794 | } |
---|
795 | example |
---|
796 | { "EXAMPLE:"; echo = 2; |
---|
797 | ring r=0,(x,y,z),dp; |
---|
798 | ideal i=1+x+x2+x3,3,x+3y+5z; |
---|
799 | linearpart(i); |
---|
800 | module m=[x,y,z],x*[x3,y2,z],[1,x2,z3,0,1]; |
---|
801 | show(linearpart(m)); |
---|
802 | } |
---|
803 | /////////////////////////////////////////////////////////////////////////////// |
---|
804 | |
---|
805 | proc tolessvars (id ,list #) |
---|
806 | "USAGE: tolessvars(id [,s1,s2] ); id poly/ideal/vector/module/matrix, |
---|
807 | s1=string (new ordering)@* |
---|
808 | [default: s1=\"dp\" or \"ds\" depending on whether the first block |
---|
809 | of the old ordering is a p- or an s-ordering, respectively] |
---|
810 | RETURN: If id contains all vars of the basering: empty list. @* |
---|
811 | Else: ring R with the same char as the basering, but possibly less |
---|
812 | variables (only those variables which actually occur in id). In R |
---|
813 | an object IMAG (image of id under imap) is stored. |
---|
814 | DISPLAY: If printlevel >=0, display ideal of vars, which have been omitted |
---|
815 | from the old ring. |
---|
816 | EXAMPLE: example tolessvars; shows an example |
---|
817 | " |
---|
818 | { |
---|
819 | //---------------- initialisation and check occurence of vars ----------------- |
---|
820 | int s,ii,n,fp,fs; |
---|
821 | string s2,newvar; |
---|
822 | int pr = printlevel-voice+3; // p = printlevel+1 (default: p=1) |
---|
823 | def P = basering; |
---|
824 | s2 = ordstr(P); |
---|
825 | |
---|
826 | list L = findvars(id,1); |
---|
827 | newvar = string(L[1]); // string of new variables |
---|
828 | n = size(L[1]); // number of new variables |
---|
829 | if( n == 0 ) |
---|
830 | { |
---|
831 | dbprint( pr,"","// no variable occured in "+typeof(id)+", no change of ring!"); |
---|
832 | return(id); |
---|
833 | } |
---|
834 | if( n == nvars(P) ) |
---|
835 | { |
---|
836 | dbprint(printlevel-voice+3," |
---|
837 | // All variables appear in input object. |
---|
838 | // empty list returned. "); |
---|
839 | return(list()); |
---|
840 | } |
---|
841 | //----------------- prepare new ring, map to it and return -------------------- |
---|
842 | if ( size(#) == 0 ) |
---|
843 | { |
---|
844 | fp = find(s2,"p"); |
---|
845 | fs = find(s2,"s"); |
---|
846 | if( fs==0 or (fs>=fp && fp!=0) ) { s2="dp"; } |
---|
847 | else { s2="ds"; } |
---|
848 | } |
---|
849 | if ( size(#) ==1 ) { s2=#[1]; } |
---|
850 | dbprint( pr,"","// variables which did not occur:",L[3] ); |
---|
851 | execute("ring S1=("+charstr(P)+"),("+newvar+"),("+s2+");"); |
---|
852 | def IMAG = imap(P,id); |
---|
853 | export IMAG; |
---|
854 | dbprint(printlevel-voice+3," |
---|
855 | // 'tolessvars' created a ring, in which an object IMAG is stored. |
---|
856 | // To access the object, type (if the name R was assigned to the return value): |
---|
857 | setring R; IMAG; "); |
---|
858 | return(S1); |
---|
859 | } |
---|
860 | example |
---|
861 | { "EXAMPLE:"; echo = 2; |
---|
862 | ring r = 0,(x,y,z),dp; |
---|
863 | ideal i = y2-x3,x-3,y-2x; |
---|
864 | def R_r = tolessvars(i,"lp"); |
---|
865 | setring R_r; |
---|
866 | show(basering); |
---|
867 | IMAG; |
---|
868 | kill R_r; |
---|
869 | } |
---|
870 | /////////////////////////////////////////////////////////////////////////////// |
---|
871 | |
---|
872 | proc solvelinearpart (id,list #) |
---|
873 | "USAGE: solvelinearpart(id [,n] ); id=ideal/module, n=integer,@* |
---|
874 | (default: n=0) |
---|
875 | RETURN: (interreduced) generators of id of degree <=1 in reduced triangular |
---|
876 | form if n=0 [non-reduced triangular form if n!=0] |
---|
877 | ASSUME: monomial ordering is a global ordering (p-ordering) |
---|
878 | NOTE: may be used to solve a system of linear equations |
---|
879 | see @code{gauss_row} from 'matrix.lib' for a different method |
---|
880 | WARNING: the result is very likely to be false for 'real' coefficients, use |
---|
881 | char 0 instead! |
---|
882 | EXAMPLE: example solvelinearpart; shows an example |
---|
883 | " |
---|
884 | { |
---|
885 | intvec getoption = option(get); |
---|
886 | option(redSB); |
---|
887 | if ( size(#)!=0 ) |
---|
888 | { |
---|
889 | if(#[1]!=0) { option(noredSB); } |
---|
890 | } |
---|
891 | def lin = interred(degreepart(id,0,1)); |
---|
892 | if ( size(#)!=0 ) |
---|
893 | { |
---|
894 | if(#[1]!=0) |
---|
895 | { |
---|
896 | return(lin); |
---|
897 | } |
---|
898 | } |
---|
899 | option(set,getoption); |
---|
900 | return(simplify(lin,1)); |
---|
901 | } |
---|
902 | example |
---|
903 | { "EXAMPLE:"; echo = 2; |
---|
904 | // Solve the system of linear equations: |
---|
905 | // 3x + y + z - u = 2 |
---|
906 | // 3x + 8y + 6z - 7u = 1 |
---|
907 | // 14x + 10y + 6z - 7u = 0 |
---|
908 | // 7x + 4y + 3z - 3u = 3 |
---|
909 | ring r = 0,(x,y,z,u),lp; |
---|
910 | ideal i= 3x + y + z - u, |
---|
911 | 13x + 8y + 6z - 7u, |
---|
912 | 14x + 10y + 6z - 7u, |
---|
913 | 7x + 4y + 3z - 3u; |
---|
914 | ideal j= 2,1,0,3; |
---|
915 | j = i-j; // difference of 1x4 matrices |
---|
916 | // compute reduced triangular form, setting |
---|
917 | solvelinearpart(j); // the RHS equal 0 gives the solutions! |
---|
918 | solvelinearpart(j,1); ""; // triangular form, not reduced |
---|
919 | } |
---|
920 | /////////////////////////////////////////////////////////////////////////////// |
---|
921 | |
---|
922 | proc sortandmap (@id, list #) |
---|
923 | "USAGE: sortandmap(id [,n1,p1,n2,p2...,o1,m1,o2,m2...]);@* |
---|
924 | id=poly/ideal/vector/module,@* |
---|
925 | p1,p2,...= polynomials (product of variables),@* |
---|
926 | n1,n2,...= integers,@* |
---|
927 | o1,o2,...= strings,@* |
---|
928 | m1,m2,...= integers@* |
---|
929 | (default: p1=product of all vars, n1=0, o1=\"dp\",m1=0) |
---|
930 | the last pi (containing the remaining vars) may be omitted |
---|
931 | RETURN: a ring R, in which a poly/ideal/vector/module IMAG is stored: @* |
---|
932 | - the ring R differs from the active basering only in the choice |
---|
933 | of monomial ordering and in the sorting of the variables.@* |
---|
934 | - IMAG is the image (under imap) of the input ideal/module id @* |
---|
935 | The new monomial ordering and sorting of vars is as follows: |
---|
936 | @format |
---|
937 | - each block of vars occuring in pi is sorted w.r.t. its complexity in id, |
---|
938 | - ni controls the sorting in i-th block (= vars occuring in pi): |
---|
939 | ni=0 (resp. ni!=0) means that least complex (resp. most complex) vars come |
---|
940 | first @* |
---|
941 | - oi and mi define the monomial ordering of the i-th block: |
---|
942 | if mi =0, oi=ordstr(i-th block) |
---|
943 | if mi!=0, the ordering of the i-th block itself is a blockordering, |
---|
944 | each subblock having ordstr=oi, such that vars of same complexity are |
---|
945 | in one block |
---|
946 | @end format |
---|
947 | Note that only simple ordstrings oi are allowed: \"lp\",\"dp\",\"Dp\", |
---|
948 | \"ls\",\"ds\",\"Ds\". @* |
---|
949 | NOTE: We define a variable x to be more complex than y (with respect to id) |
---|
950 | if val(x) > val(y) lexicographically, where val(x) denotes the |
---|
951 | valuation vector of x:@* |
---|
952 | consider id as list of polynomials in x with coefficients in the |
---|
953 | remaining variables. Then:@* |
---|
954 | val(x) = (maximal occuring power of x, # of all monomials in leading |
---|
955 | coefficient, # of all monomials in coefficient of next smaller power |
---|
956 | of x,...). |
---|
957 | EXAMPLE: example sortandmap; shows an example |
---|
958 | " |
---|
959 | { |
---|
960 | def @P = basering; |
---|
961 | int @ii,@jj; |
---|
962 | intvec @v; |
---|
963 | string @o; |
---|
964 | //----------------- find o in # and split # into 2 lists --------------------- |
---|
965 | # = # +list("dp",0); |
---|
966 | for ( @ii=1; @ii<=size(#); @ii++) |
---|
967 | { |
---|
968 | if ( typeof(#[@ii])=="string" ) break; |
---|
969 | } |
---|
970 | if ( @ii==1 ) { list @L1 = list(); } |
---|
971 | else { list @L1 = #[1..@ii-1]; } |
---|
972 | list @L2 = #[@ii..size(#)]; |
---|
973 | list @L = sortvars(@id,@L1); |
---|
974 | string @va = string(@L[1]); |
---|
975 | list @l = @L[2]; //e.g. @l[4]=intvec describing permutation of 1-st block |
---|
976 | //----------------- construct correct ordering with oi and mi ---------------- |
---|
977 | for ( @ii=4; @ii<=size(@l); @ii=@ii+4 ) |
---|
978 | { |
---|
979 | @L2=@L2+list("dp",0); |
---|
980 | if ( @L2[@ii/2] != 0) |
---|
981 | { |
---|
982 | @v = @l[@ii]; |
---|
983 | for ( @jj=1; @jj<=size(@v); @jj++ ) |
---|
984 | { |
---|
985 | @o = @o+@L2[@ii/2 -1]+"("+string(@v[@jj])+"),"; |
---|
986 | } |
---|
987 | } |
---|
988 | else |
---|
989 | { |
---|
990 | @o = @o+@L2[@ii/2 -1]+"("+string(size(@l[@ii/2]))+"),"; |
---|
991 | } |
---|
992 | } |
---|
993 | @o=@o[1..size(@o)-1]; |
---|
994 | execute("ring @S1 =("+charstr(@P)+"),("+@va+"),("+@o+");"); |
---|
995 | def IMAG = imap(@P,@id); |
---|
996 | export IMAG; |
---|
997 | dbprint(printlevel-voice+3," |
---|
998 | // 'sortandmap' created a ring, in which an object IMAG is stored. |
---|
999 | // To access the object, type (if the name R was assigned to the return value): |
---|
1000 | setring R; IMAG; "); |
---|
1001 | return(@S1); |
---|
1002 | } |
---|
1003 | example |
---|
1004 | { "EXAMPLE:"; echo = 2; |
---|
1005 | ring s = 32003,(x,y,z),dp; |
---|
1006 | ideal i=x3+y2,xz+z2; |
---|
1007 | def R_r=sortandmap(i); |
---|
1008 | show(R_r); |
---|
1009 | setring R_r; IMAG; |
---|
1010 | kill R_r; setring s; |
---|
1011 | def R_r=sortandmap(i,1,xy,0,z,0,"ds",0,"lp",0); |
---|
1012 | show(R_r); |
---|
1013 | setring R_r; IMAG; |
---|
1014 | kill R_r; |
---|
1015 | } |
---|
1016 | /////////////////////////////////////////////////////////////////////////////// |
---|
1017 | |
---|
1018 | proc sortvars (id, list #) |
---|
1019 | "USAGE: sortvars(id[,n1,p1,n2,p2,...]);@* |
---|
1020 | id=poly/ideal/vector/module,@* |
---|
1021 | p1,p2,...= polynomials (product of vars),@* |
---|
1022 | n1,n2,...=integers@* |
---|
1023 | (default: p1=product of all vars, n1=0) |
---|
1024 | the last pi (containing the remaining vars) may be omitted |
---|
1025 | COMPUTE: sort variables with respect to their complexity in id |
---|
1026 | RETURN: list of two elements, an ideal and a list: |
---|
1027 | @format |
---|
1028 | [1]: ideal, variables of basering sorted w.r.t their complexity in id |
---|
1029 | ni controls the ordering in i-th block (= vars occuring in pi): |
---|
1030 | ni=0 (resp. ni!=0) means that less (resp. more) complex vars come first |
---|
1031 | [2]: a list with 4 entries for each pi: |
---|
1032 | ideal ai : vars of pi in correct order, |
---|
1033 | intvec vi: permutation vector describing the ordering in ai, |
---|
1034 | intmat Mi: valuation matrix of ai, the columns of Mi being the |
---|
1035 | valuation vectors of the vars in ai |
---|
1036 | intvec wi: size of 1-st, 2-nd,... block of identical columns of Mi |
---|
1037 | (vars with same valuation) |
---|
1038 | @end format |
---|
1039 | NOTE: We define a variable x to be more complex than y (with respect to id) |
---|
1040 | if val(x) > val(y) lexicographically, where val(x) denotes the |
---|
1041 | valuation vector of x:@* |
---|
1042 | consider id as list of polynomials in x with coefficients in the |
---|
1043 | remaining variables. Then:@* |
---|
1044 | val(x) = (maximal occuring power of x, # of all monomials in leading |
---|
1045 | coefficient, # of all monomials in coefficient of next smaller power |
---|
1046 | of x,...). |
---|
1047 | EXAMPLE: example sortvars; shows an example |
---|
1048 | " |
---|
1049 | { |
---|
1050 | int ii,jj,n,s; |
---|
1051 | list L = valvars(id,#); |
---|
1052 | list L2, L3 = L[2], L[3]; |
---|
1053 | list K; intmat M; intvec v1,v2,w; |
---|
1054 | ideal i = sort(maxideal(1),L[1])[1]; |
---|
1055 | for ( ii=1; ii<=size(L2); ii++ ) |
---|
1056 | { |
---|
1057 | M = transpose(L3[2*ii]); |
---|
1058 | M = M[L2[ii],1..nrows(L3[2*ii])]; |
---|
1059 | w = 0; s = 0; |
---|
1060 | for ( jj=1; jj<=nrows(M)-1; jj++ ) |
---|
1061 | { |
---|
1062 | v1 = M[jj,1..ncols(M)]; |
---|
1063 | v2 = M[jj+1,1..ncols(M)]; |
---|
1064 | if ( v1 != v2 ) { n=jj-s; s=s+n; w = w,n; } |
---|
1065 | } |
---|
1066 | w=w,nrows(M)-s; w=w[2..size(w)]; |
---|
1067 | K = K+sort(L3[2*ii-1],L2[ii])+list(transpose(M))+list(w); |
---|
1068 | } |
---|
1069 | L = i,K; |
---|
1070 | return(L); |
---|
1071 | } |
---|
1072 | example |
---|
1073 | { "EXAMPLE:"; echo = 2; |
---|
1074 | ring s=0,(x,y,z,w),dp; |
---|
1075 | ideal i = x3+y2+yw2,xz+z2,xyz-w2; |
---|
1076 | sortvars(i,0,xy,1,zw); |
---|
1077 | } |
---|
1078 | /////////////////////////////////////////////////////////////////////////////// |
---|
1079 | |
---|
1080 | proc valvars (id, list #) |
---|
1081 | "USAGE: valvars(id[,n1,p1,n2,p2,...]);@* |
---|
1082 | id=poly/ideal/vector/module,@* |
---|
1083 | p1,p2,...= polynomials (product of vars),@* |
---|
1084 | n1,n2,...= integers, |
---|
1085 | |
---|
1086 | ni controls the ordering of vars occuring in pi: ni=0 (resp. ni!=0) |
---|
1087 | means that less (resp. more) complex vars come first@* |
---|
1088 | (default: p1=product of all vars, n1=0) |
---|
1089 | the last pi (containing the remaining vars) may be omitted |
---|
1090 | COMPUTE: valuation (complexity) of variables with respect to id.@* |
---|
1091 | ni controls the ordering of vars occuring in pi:@* |
---|
1092 | ni=0 (resp. ni!=0) means that less (resp. more) complex vars come first. |
---|
1093 | RETURN: list with 3 entries: |
---|
1094 | @format |
---|
1095 | [1]: intvec, say v, describing the permutation such that the permuted |
---|
1096 | ring variables are ordered with respect to their complexity in id |
---|
1097 | [2]: list of intvecs, i-th intvec, say v(i) describing permutation |
---|
1098 | of vars in a(i) such that v=v(1),v(2),... |
---|
1099 | [3]: list of ideals and intmat's, say a(i) and M(i), where |
---|
1100 | a(i): factors of pi, |
---|
1101 | M(i): valuation matrix of a(i), such that the j-th column of M(i) |
---|
1102 | is the valuation vector of j-th generator of a(i) |
---|
1103 | @end format |
---|
1104 | NOTE: Use @code{sortvars} in order to actually sort the variables! |
---|
1105 | We define a variable x to be more complex than y (with respect to id) |
---|
1106 | if val(x) > val(y) lexicographically, where val(x) denotes the |
---|
1107 | valuation vector of x:@* |
---|
1108 | consider id as list of polynomials in x with coefficients in the |
---|
1109 | remaining variables. Then:@* |
---|
1110 | val(x) = (maximal occuring power of x, # of all monomials in leading |
---|
1111 | coefficient, # of all monomials in coefficient of next smaller power |
---|
1112 | of x,...). |
---|
1113 | EXAMPLE: example valvars; shows an example |
---|
1114 | " |
---|
1115 | { |
---|
1116 | //---------------------------- initialization --------------------------------- |
---|
1117 | int ii,jj,kk,n; |
---|
1118 | list L; // list of valuation vectors in one block |
---|
1119 | intvec vec; // describes permutation of vars (in one block) |
---|
1120 | list blockvec; // i-th element = vec of i-th block |
---|
1121 | intvec varvec; // result intvector |
---|
1122 | list Li; // result list of ideals |
---|
1123 | list LM; // result list of intmat's |
---|
1124 | intvec v,w,s; // w valuation vector for one variable |
---|
1125 | matrix C; // coefficient matrix for different variables |
---|
1126 | ideal i = simplify(ideal(matrix(id)),10); |
---|
1127 | |
---|
1128 | //---- for each pii in # create ideal a(ii) intvec v(ii) and list L(ii) ------- |
---|
1129 | // a(ii) = ideal of vars in product, v(ii)[j]=k <=> a(ii)[j]=var(k) |
---|
1130 | |
---|
1131 | v = 1..nvars(basering); |
---|
1132 | int l = size(#); |
---|
1133 | if ( l >= 2 ) |
---|
1134 | { |
---|
1135 | ideal m=maxideal(1); |
---|
1136 | for ( ii=2; ii<=l; ii=ii+2 ) |
---|
1137 | { |
---|
1138 | int n(ii) = #[ii-1]; |
---|
1139 | ideal a(ii); |
---|
1140 | intvec v(ii); |
---|
1141 | for ( jj=1; jj<=nvars(basering); jj++ ) |
---|
1142 | { |
---|
1143 | if ( #[ii]/var(jj) != 0) |
---|
1144 | { |
---|
1145 | a(ii) = a(ii) + var(jj); |
---|
1146 | v(ii)=v(ii),jj; |
---|
1147 | m[jj]=0; |
---|
1148 | v[jj]=0; |
---|
1149 | } |
---|
1150 | } |
---|
1151 | v(ii)=v(ii)[2..size(v(ii))]; |
---|
1152 | } |
---|
1153 | if ( size(m)!=0 ) |
---|
1154 | { |
---|
1155 | l = 2*(l/2)+2; |
---|
1156 | ideal a(l) = simplify(m,2); |
---|
1157 | intvec v(l) = compress(v); |
---|
1158 | int n(l); |
---|
1159 | if ( size(#)==l-1 ) { n(l) = #[l-1]; } |
---|
1160 | } |
---|
1161 | } |
---|
1162 | else |
---|
1163 | { |
---|
1164 | l = 2; |
---|
1165 | ideal a(2) = maxideal(1); |
---|
1166 | intvec v(2) = v; |
---|
1167 | int n(2); |
---|
1168 | if ( size(#)==1 ) { n(2) = #[1]; } |
---|
1169 | } |
---|
1170 | //------------- start loop to order variables in each a(ii) ------------------- |
---|
1171 | |
---|
1172 | for ( kk=2; kk<=l; kk=kk+2 ) |
---|
1173 | { |
---|
1174 | L = list(); |
---|
1175 | n = 0; |
---|
1176 | //---------------- get valuation of all variables in a(kk) -------------------- |
---|
1177 | for ( ii=1; ii<=size(a(kk)); ii++ ) |
---|
1178 | { |
---|
1179 | C = coeffs(i,a(kk)[ii]); |
---|
1180 | w = nrows(C); // =(maximal occuring power of a(kk)[ii])+1 |
---|
1181 | for ( jj=w[1]; jj>1; jj-- ) |
---|
1182 | { |
---|
1183 | s = size(C[jj,1..ncols(C)]); |
---|
1184 | w[w[1]-jj+2] = sum(s); |
---|
1185 | } |
---|
1186 | // w[1] should represent the maximal occuring power of a(kk)[ii] so it |
---|
1187 | // has to be decreased by 1 since otherwise the constant term is also |
---|
1188 | // counted |
---|
1189 | w[1]=w[1]-1; |
---|
1190 | |
---|
1191 | L[ii]=w; |
---|
1192 | n = size(w)*(size(w) > n) + n*(size(w) <= n); |
---|
1193 | } |
---|
1194 | intmat M(kk)[size(a(kk))][n]; |
---|
1195 | for ( ii=1; ii<=size(a(kk)); ii++ ) |
---|
1196 | { |
---|
1197 | if ( n==1 ) { w = L[ii]; M(kk)[ii,1] = w[1]; } |
---|
1198 | else { M(kk)[ii,1..n] = L[ii]; } |
---|
1199 | } |
---|
1200 | LM[kk-1] = a(kk); |
---|
1201 | LM[kk] = transpose(compress(M(kk))); |
---|
1202 | //------------------- compare valuation and insert in vec --------------------- |
---|
1203 | vec = sort(L)[2]; |
---|
1204 | if ( n(kk) != 0 ) { vec = vec[size(vec)..1]; } |
---|
1205 | blockvec[kk/2] = vec; |
---|
1206 | vec = sort(v(kk),vec)[1]; |
---|
1207 | varvec = varvec,vec; |
---|
1208 | } |
---|
1209 | varvec = varvec[2..size(varvec)]; |
---|
1210 | list result = varvec,blockvec,LM; |
---|
1211 | return(result); |
---|
1212 | } |
---|
1213 | example |
---|
1214 | { "EXAMPLE:"; echo = 2; |
---|
1215 | ring s=0,(x,y,z,a,b),dp; |
---|
1216 | ideal i=ax2+ay3-b2x,abz+by2; |
---|
1217 | valvars (i,0,xyz); |
---|
1218 | } |
---|
1219 | /////////////////////////////////////////////////////////////////////////////// |
---|
1220 | proc idealSplit(ideal I,list #) |
---|
1221 | "USAGE: idealSplit(id,timeF,timeS); id ideal and optional |
---|
1222 | timeF, timeS integers to bound the time which can be used |
---|
1223 | for factorization resp. standard basis computation |
---|
1224 | RETURN: a list of ideals such that their intersection |
---|
1225 | has the same radical as id |
---|
1226 | EXAMPLE: example idealSplit; shows an example |
---|
1227 | " |
---|
1228 | { |
---|
1229 | option(redSB); |
---|
1230 | int j,k,e; |
---|
1231 | int i=1; |
---|
1232 | int l=attrib(I,"isSB"); |
---|
1233 | ideal J; |
---|
1234 | int timeF; |
---|
1235 | int timeS; |
---|
1236 | list re,fac,te; |
---|
1237 | |
---|
1238 | if(size(#)==1) |
---|
1239 | { |
---|
1240 | if(typeof(#[1])=="ideal") |
---|
1241 | { |
---|
1242 | re=#; |
---|
1243 | } |
---|
1244 | else |
---|
1245 | { |
---|
1246 | timeF=#[1]; |
---|
1247 | } |
---|
1248 | } |
---|
1249 | if(size(#)==2) |
---|
1250 | { |
---|
1251 | if(typeof(#[1])=="list") |
---|
1252 | { |
---|
1253 | re=#[1]; |
---|
1254 | timeF=#[2]; |
---|
1255 | } |
---|
1256 | else |
---|
1257 | { |
---|
1258 | timeF=#[1]; |
---|
1259 | timeS=#[2]; |
---|
1260 | } |
---|
1261 | } |
---|
1262 | if(size(#)==3){re=#[1];timeF=#[2];timeS=#[3];} |
---|
1263 | |
---|
1264 | fac=timeFactorize(I[1],timeF); |
---|
1265 | |
---|
1266 | while((size(fac[1])==2)&&(i<size(I))) |
---|
1267 | { |
---|
1268 | i++; |
---|
1269 | fac=timeFactorize(I[i],timeF); |
---|
1270 | } |
---|
1271 | if(size(fac[1])>2) |
---|
1272 | { |
---|
1273 | for(j=2;j<=size(fac[1]);j++) |
---|
1274 | { |
---|
1275 | I[i]=fac[1][j]; |
---|
1276 | attrib(I,"isSB",1); |
---|
1277 | e=1; |
---|
1278 | k=0; |
---|
1279 | while(k<size(re)) |
---|
1280 | { |
---|
1281 | k++; |
---|
1282 | if(size(reduce(re[k],I))==0){e=0;break;} |
---|
1283 | attrib(re[k],"isSB",1); |
---|
1284 | if(size(reduce(I,re[k]))==0){re=delete(re,k);k--;} |
---|
1285 | } |
---|
1286 | if(e) |
---|
1287 | { |
---|
1288 | if(l) |
---|
1289 | { |
---|
1290 | J=I; |
---|
1291 | J[i]=0; |
---|
1292 | J=simplify(J,2); |
---|
1293 | attrib(J,"isSB",1); |
---|
1294 | re=idealSplit(std(J,fac[1][j]),re,timeF,timeS); |
---|
1295 | } |
---|
1296 | else |
---|
1297 | { |
---|
1298 | re=idealSplit(timeStd(I,timeS),re,timeF,timeS); |
---|
1299 | } |
---|
1300 | } |
---|
1301 | } |
---|
1302 | return(re); |
---|
1303 | } |
---|
1304 | J=timeStd(I,timeS); |
---|
1305 | attrib(I,"isSB",1); |
---|
1306 | if(size(reduce(J,I))==0){return(re+list(I));} |
---|
1307 | return(re+idealSplit(J,re,timeF,timeS)); |
---|
1308 | } |
---|
1309 | example |
---|
1310 | { "EXAMPLE:"; echo = 2; |
---|
1311 | ring r=32003,(b,s,t,u,v,w,x,y,z),dp; |
---|
1312 | ideal i= |
---|
1313 | bv+su, |
---|
1314 | bw+tu, |
---|
1315 | sw+tv, |
---|
1316 | by+sx, |
---|
1317 | bz+tx, |
---|
1318 | sz+ty, |
---|
1319 | uy+vx, |
---|
1320 | uz+wx, |
---|
1321 | vz+wy, |
---|
1322 | bvz; |
---|
1323 | idealSplit(i); |
---|
1324 | } |
---|
1325 | /////////////////////////////////////////////////////////////////////////////// |
---|
1326 | proc idealSimplify(ideal J,list #) |
---|
1327 | "USAGE: idealSimplify(id); id ideal |
---|
1328 | RETURN: ideal I = eliminate(Id,m) m is a product of variables |
---|
1329 | which are only linearly involved in the generators of id |
---|
1330 | EXAMPLE: example idealSimplify; shows an example |
---|
1331 | " |
---|
1332 | { |
---|
1333 | ideal I=J; |
---|
1334 | if(size(#)!=0){I=#[1];} |
---|
1335 | def R=basering; |
---|
1336 | matrix M=jacob(I); |
---|
1337 | ideal ma=maxideal(1); |
---|
1338 | int i,j,k; |
---|
1339 | map phi; |
---|
1340 | |
---|
1341 | for(i=1;i<=nrows(M);i++) |
---|
1342 | { |
---|
1343 | for(j=1;j<=ncols(M);j++) |
---|
1344 | { |
---|
1345 | if(deg(M[i,j])==0) |
---|
1346 | { |
---|
1347 | ma[j]=(-1/M[i,j])*(I[i]-M[i,j]*var(j)); |
---|
1348 | phi=R,ma; |
---|
1349 | I=phi(I); |
---|
1350 | J=phi(J); |
---|
1351 | for(k=1;k<=ncols(I);k++){I[k]=cleardenom(I[k]);} |
---|
1352 | M=jacob(I); |
---|
1353 | } |
---|
1354 | } |
---|
1355 | } |
---|
1356 | J=simplify(J,2); |
---|
1357 | for(i=1;i<=size(J);i++){J[i]=cleardenom(J[i]);} |
---|
1358 | return(J); |
---|
1359 | } |
---|
1360 | example |
---|
1361 | { "EXAMPLE:"; echo = 2; |
---|
1362 | ring r=0,(x,y,z,w,t),dp; |
---|
1363 | ideal i= |
---|
1364 | t, |
---|
1365 | x3+y2+2z, |
---|
1366 | x2+3y, |
---|
1367 | x2+y2+z2, |
---|
1368 | w2+z; |
---|
1369 | ideal j=idealSimplify(i); |
---|
1370 | ideal k=eliminate(i,zyt); |
---|
1371 | reduce(k,std(j)); |
---|
1372 | reduce(j,std(k)); |
---|
1373 | } |
---|
1374 | |
---|
1375 | /////////////////////////////////////////////////////////////////////////////// |
---|
1376 | |
---|
1377 | /* |
---|
1378 | |
---|
1379 | ring s=31991,(e,f,x,y,z,t,u,v,w,a,b,c,d),dp; |
---|
1380 | ring s=31991,(x,y,z,t,u,v,w,a,b,c,d,f,e,h),dp; //standard |
---|
1381 | ring s1=31991,(y,u,b,c,a,z,t,x,v,d,w,e,f,h),dp; //gut |
---|
1382 | v; |
---|
1383 | 13,12,11,10,8,7,6,5,4,3,2,1,9,14 |
---|
1384 | print(matrix(sort(maxideal(1),v))); |
---|
1385 | f,e,w,d,x,t,z,a,c,b,u,y,v,h |
---|
1386 | print(matrix(maxideal(1))); |
---|
1387 | y,u,b,c,a,z,t,x,v,d,w,e,f,h |
---|
1388 | v0; |
---|
1389 | 14,9,12,11,10,8,7,6,5,4,3,2,1,13 |
---|
1390 | print(matrix(sort(maxideal(1),v0))); |
---|
1391 | h,v,e,w,d,x,t,z,a,c,b,u,y,f |
---|
1392 | v1;v2; |
---|
1393 | 9,12,11,10,8,7,6,5,4,3,2,1,13,14 |
---|
1394 | 13,12,11,10,8,7,6,5,4,3,2,1,9,14 |
---|
1395 | |
---|
1396 | Ev. Gute Ordnung fuer i: |
---|
1397 | ======================== |
---|
1398 | i=ad*x^d+ad-1*x^(d-1)+...+a1*x+a0, ad!=0 |
---|
1399 | mit ar=(ar1,...,ark), k=size(i) |
---|
1400 | arj in K[..x^..] |
---|
1401 | d=deg_x(i) := max{deg_x(i[k]) | k=1..size(i)} |
---|
1402 | size_x(i,deg_x(i)..0) := size(ad),...,size(a0) |
---|
1403 | x>y <== |
---|
1404 | 1. deg_x(i)>deg_y(i) |
---|
1405 | 2. "=" in 1. und size_x lexikographisch |
---|
1406 | |
---|
1407 | hier im Beispiel: |
---|
1408 | f: 5,1,0,1,2 |
---|
1409 | |
---|
1410 | u: 3,1,4 |
---|
1411 | |
---|
1412 | y: 3,1,3 |
---|
1413 | b: 3,1,3 |
---|
1414 | c: 3,1,3 |
---|
1415 | a: 3,1,3 |
---|
1416 | z: 3,1,3 |
---|
1417 | t: 3,1,3 |
---|
1418 | |
---|
1419 | x: 3,1,2 |
---|
1420 | v: 3,1,2 |
---|
1421 | d: 3,1,2 |
---|
1422 | w: 3,1,2 |
---|
1423 | e: 3,1,2 |
---|
1424 | probier mal: |
---|
1425 | ring s=31991,(f,u,y,z,t,a,b,c,v,w,d,e,h),dp; //standard |
---|
1426 | |
---|
1427 | */ |
---|