1 | // $Id: elim.lib,v 1.22 2008-04-22 17:20:51 Singular Exp $ |
---|
2 | // (GMG, last modified 22.06.96) |
---|
3 | /////////////////////////////////////////////////////////////////////////////// |
---|
4 | version="$Id: elim.lib,v 1.22 2008-04-22 17:20:51 Singular Exp $"; |
---|
5 | category="Commutative Algebra"; |
---|
6 | info=" |
---|
7 | LIBRARY: elim.lib Elimination, Saturation and Blowing up |
---|
8 | |
---|
9 | PROCEDURES: |
---|
10 | blowup0(j[,s1,s2]); create presentation of blownup ring of ideal j |
---|
11 | elim(id,n,m); variable n..m eliminated from id (ideal/module) |
---|
12 | elim1(id,p); p=product of vars to be eliminated from id |
---|
13 | nselect(id,n[,m]); select generators not containing nth [..mth] variable |
---|
14 | sat(id,j); saturated quotient of ideal/module id by ideal j |
---|
15 | select(id,n[,m]); select generators containing all variables n...m |
---|
16 | select1(id,n[,m]); select generators containing one variable n...m |
---|
17 | (parameters in square brackets [] are optional) |
---|
18 | "; |
---|
19 | |
---|
20 | LIB "inout.lib"; |
---|
21 | LIB "general.lib"; |
---|
22 | LIB "poly.lib"; |
---|
23 | |
---|
24 | /////////////////////////////////////////////////////////////////////////////// |
---|
25 | |
---|
26 | proc blowup0 (ideal J,ideal C, list #) |
---|
27 | "USAGE: blowup0(J,C [,W]); J,C,W ideals |
---|
28 | @* C = ideal of center of blowup, J = ideal to be blown up, |
---|
29 | W = ideal of ambient space |
---|
30 | ASSUME: inclusion of ideals : W in J, J in C. |
---|
31 | If not, the procedure replaces J by J+W and C by C+J+W |
---|
32 | RETURN: a ring, say B, containing the ideals C,J,W and the ideals |
---|
33 | @* - bR (ideal defining the blown up basering) |
---|
34 | @* - aS (ideal of blown up ambient space) |
---|
35 | @* - eD (ideal of exceptional divisor) |
---|
36 | @* - tT (ideal of total transform) |
---|
37 | @* - sT (ideal of strict transform) |
---|
38 | @* - bM (ideal of the blowup map from basering to B) |
---|
39 | @* such that B/bR is isomorphic to the blowup ring BC. |
---|
40 | PURPOSE: compute the projective blowup of the basering in the center C, the |
---|
41 | exceptional locus, the total and strict tranform of J, |
---|
42 | and the blowup map. |
---|
43 | The projective blowup is a presentation of the blowup ring |
---|
44 | BC = R[C] = R + t*C + t^2*C^2 + ... (also called Rees ring) of the |
---|
45 | ideal C in the ring basering R. |
---|
46 | THEORY: If basering = K[x1,...,xn] and C = <f1,...,fk> then let |
---|
47 | B = K[x1,...,xn,y1,...,yk] and aS the preimage in B of W |
---|
48 | under the map B -> K[x1,...,xn,t], xi -> xi, yi -> t*fi. |
---|
49 | aS is homogeneous in the variables yi and defines a variety |
---|
50 | Z=V(aS) in A^n x P^(k-1), the ambient space of the blowup of V(W). |
---|
51 | The projection Z -> A^n is an isomorphism outside the preimage |
---|
52 | of the center V(C) in A^n and is called the blowup of the center. |
---|
53 | The preimage of V(C) is called the exceptional set, the preimage of |
---|
54 | V(J) is called the total transform of V(J). The strict transform |
---|
55 | is the closure of (total transform - exceptional set). |
---|
56 | @* If C = <x1,...,xn> then aS = <yi*xj - yj*xi | i,j=1,...,n> |
---|
57 | and Z is the blowup of A^n in 0, the exceptional set is P^(k-1). |
---|
58 | NOTE: The procedure creates a new ring with variables y(1..k) and x(1..n) |
---|
59 | where n=nvars(basering) and k=ncols(C). The ordering is a block |
---|
60 | ordering where the x-block has the ordering of the basering and |
---|
61 | the y-block has ordering dp if C is not homogeneous |
---|
62 | resp. the weighted ordering wp(b1,...bk) if C is homogeneous |
---|
63 | with deg(C[i])=bi. |
---|
64 | SEE ALSO:blowUp |
---|
65 | EXAMPLE: example blowup0; shows examples |
---|
66 | "{ |
---|
67 | def br = basering; |
---|
68 | list l = ringlist(br); |
---|
69 | int n,k,i = nvars(br),ncols(C),0; |
---|
70 | ideal W; |
---|
71 | if (size(#) !=0) |
---|
72 | { W = #[1];} |
---|
73 | J = J,W; |
---|
74 | //J = interred(J+W); |
---|
75 | //------------------------- create rings for blowup ------------------------ |
---|
76 | //Create rings tr = K[x(1),...,x(n),t] and nr = K[x(1),...,x(n),y(1),...,y(k)] |
---|
77 | //and map Bl: nr --> tr, x(i)->x(i), y(i)->t*fi. |
---|
78 | //Let ord be the ordering of the basering. |
---|
79 | //We change the ringlist l by changing l[2] and l[3] |
---|
80 | //For K[t,x(1),...,x(n),t] |
---|
81 | // - l[2]: the variables to x(1),...,x(n),t |
---|
82 | // - l[3]: the ordering to a block ordering (ord,dp(1)) |
---|
83 | //For K[x(1),...,x(n),y(1),...,y(k)] |
---|
84 | // - l[2]: the variables to x(1),...,x(n),y(1),...,y(k), |
---|
85 | // - l[3]: the ordering to a block ordering (ord,dp) if C is |
---|
86 | // not homogeneous or to (ord,wp(b1,...bk),ord) if C is |
---|
87 | // homogeneous with deg(C[i])=bi; |
---|
88 | |
---|
89 | //--------------- create tr = K[x(1),...,x(n),t] --------------------------- |
---|
90 | int s = size(l[3]); |
---|
91 | for ( i=1; i<=n; i++) |
---|
92 | { |
---|
93 | l[2][i]="x("+string(i)+")"; |
---|
94 | } |
---|
95 | l[2]=insert(l[2],"t",n); |
---|
96 | l[3]=insert(l[3],list("dp",1),s-1); |
---|
97 | def tr = ring(l); |
---|
98 | |
---|
99 | //--------------- create nr = K[x(1),...,x(n),y(1),...,y(k)] --------------- |
---|
100 | l[2]=delete(l[2],n+1); |
---|
101 | l[3]=delete(l[3],s); |
---|
102 | for ( i=1; i<=k; i++) |
---|
103 | { |
---|
104 | l[2][n+i]="y("+string(i)+")"; |
---|
105 | } |
---|
106 | |
---|
107 | //---- change l[3]: |
---|
108 | l[3][s+1] = l[3][s]; // save the module ordering of the basering |
---|
109 | intvec w; |
---|
110 | w[k]=0; w=w+1; |
---|
111 | intvec v; // containing the weights for the varibale |
---|
112 | if( homog(C) ) |
---|
113 | { |
---|
114 | for( i=1; i<=k; i++) |
---|
115 | { |
---|
116 | v[i]=deg(C[i]); |
---|
117 | } |
---|
118 | if (v != w) |
---|
119 | { |
---|
120 | l[3][s]=list("wp",v); |
---|
121 | } |
---|
122 | else |
---|
123 | { |
---|
124 | l[3][s]=list("dp",v); |
---|
125 | } |
---|
126 | } |
---|
127 | else |
---|
128 | { |
---|
129 | for( i=1; i<=k; i++) |
---|
130 | { |
---|
131 | v[i]=1; |
---|
132 | } |
---|
133 | l[3][s]=list("dp",v); |
---|
134 | } |
---|
135 | def nr = ring(l); |
---|
136 | |
---|
137 | //-------- create blowup map Bl: nr --> tr, x(i)->x(i), y(i)->t*fi --------- |
---|
138 | setring tr; |
---|
139 | ideal C = fetch(br,C); |
---|
140 | ideal bl = x(1..n); |
---|
141 | for( i=1; i<=k; i++) { bl = bl,t*C[i]; } |
---|
142 | map Bl = nr,bl; |
---|
143 | ideal Z; |
---|
144 | //------------------ compute blown up objects and return ------------------- |
---|
145 | setring nr; |
---|
146 | ideal bR = preimage(tr,Bl,Z); //ideal of blown up affine space A^n |
---|
147 | ideal C = fetch(br,C); |
---|
148 | ideal J = fetch(br,J); |
---|
149 | ideal W = fetch(br,W); |
---|
150 | ideal aS = interred(bR+W); //ideal of ambient space |
---|
151 | ideal tT = interred(J+bR+W); //ideal of total transform |
---|
152 | ideal eD = interred(C+J+bR+W); //ideal of exceptional divisor |
---|
153 | ideal sT = sat(tT,C)[1]; //ideal of strict transform |
---|
154 | ideal bM = x(1..n); //ideal of blowup map br --> nr |
---|
155 | |
---|
156 | export(bR,C,J,W,aS,tT,eD,sT,bM); |
---|
157 | return(nr); |
---|
158 | } |
---|
159 | example |
---|
160 | { "EXAMPLE:"; echo = 2; |
---|
161 | ring r = 0,(x,y),dp; |
---|
162 | poly f = x2+y3; |
---|
163 | ideal C = x,y; //center of blowup |
---|
164 | def B1 = blowup0(f,C); |
---|
165 | setring B1; |
---|
166 | aS; //ideal of blown up ambient space |
---|
167 | tT; //ideal of total transform of f |
---|
168 | sT; //ideal of strict transform of f |
---|
169 | eD; //ideal of exceptional divisor |
---|
170 | bM; //ideal of blowup map r --> B1 |
---|
171 | |
---|
172 | ring R = 0,(x,y,z),ds; |
---|
173 | poly f = y2+x3+z5; |
---|
174 | ideal C = y2,x,z; |
---|
175 | ideal W = z-x; |
---|
176 | def B2 = blowup0(f,C,W); |
---|
177 | setring B2; |
---|
178 | B2; //weighted ordering |
---|
179 | bR; //ideal of blown up R |
---|
180 | aS; //ideal of blown up R/W |
---|
181 | sT; //strict transform of f |
---|
182 | eD; //ideal of exceptional divisor |
---|
183 | //Note that the different affine charts are {y(i)=1} |
---|
184 | } |
---|
185 | /////////////////////////////////////////////////////////////////////////////// |
---|
186 | |
---|
187 | |
---|
188 | /////////////////////////////////////////////////////////////////////////////// |
---|
189 | |
---|
190 | proc elim (id, int n, int m) |
---|
191 | "USAGE: elim(id,n,m); id ideal/module, n,m integers |
---|
192 | RETURNS: ideal/module obtained from id by eliminating variables var(n) to var(m) |
---|
193 | NOTE: no special monomial ordering is required, result is a SB with |
---|
194 | respect to ordering dp (resp. ls) if the first var not to be |
---|
195 | eliminated belongs to a -p (resp. -s) blockordering |
---|
196 | This proc uses 'execute' or calls a procedure using 'execute'. |
---|
197 | SEE ALSO: elim1, eliminate |
---|
198 | EXAMPLE: example elim; shows examples |
---|
199 | " |
---|
200 | { |
---|
201 | //---- get variables to be eliminated and create string for new ordering ------ |
---|
202 | int ii; poly vars=1; |
---|
203 | for( ii=n; ii<=m; ii++ ) { vars=vars*var(ii); } |
---|
204 | if( attrib(basering,"global")) { string ordering = "),dp;"; } |
---|
205 | else { string ordering = "),ls;"; } |
---|
206 | string mpoly=string(minpoly); |
---|
207 | //-------------- create new ring and map objects to new ring ------------------ |
---|
208 | def br = basering; |
---|
209 | string str = "ring @newr = ("+charstr(br)+"),("+varstr(br)+ordering; |
---|
210 | execute(str); |
---|
211 | if (mpoly!="0") { execute("minpoly="+mpoly+";"); } |
---|
212 | def i = imap(br,id); |
---|
213 | poly vars = imap(br,vars); |
---|
214 | //---------- now eliminate in new ring and map back to old ring --------------- |
---|
215 | i = eliminate(i,vars); |
---|
216 | setring br; |
---|
217 | return(imap(@newr,i)); |
---|
218 | } |
---|
219 | example |
---|
220 | { "EXAMPLE:"; echo = 2; |
---|
221 | ring r=0,(x,y,u,v,w),dp; |
---|
222 | ideal i=x-u,y-u2,w-u3,v-x+y3; |
---|
223 | elim(i,3,4); |
---|
224 | module m=i*gen(1)+i*gen(2); |
---|
225 | m=elim(m,3,4);show(m); |
---|
226 | } |
---|
227 | /////////////////////////////////////////////////////////////////////////////// |
---|
228 | |
---|
229 | proc elim1 (id, poly vars) |
---|
230 | "USAGE: elim1(id,p); id ideal/module, p product of vars to be eliminated |
---|
231 | RETURN: ideal/module obtained from id by eliminating vars occuring in poly |
---|
232 | NOTE: no special monomial ordering is required, result is a SB with |
---|
233 | respect to ordering dp (resp. ls) if the first var not to be |
---|
234 | eliminated belongs to a -p (resp. -s) blockordering |
---|
235 | This proc uses 'execute' or calls a procedure using 'execute'. |
---|
236 | SEE ALSO: elim, eliminate |
---|
237 | EXAMPLE: example elim1; shows examples |
---|
238 | " |
---|
239 | { |
---|
240 | //---- get variables to be eliminated and create string for new ordering ------ |
---|
241 | int ii; |
---|
242 | for( ii=1; ii<=nvars(basering); ii++ ) |
---|
243 | { |
---|
244 | if( vars/var(ii)==0 ) { poly p = 1+var(ii); break;} |
---|
245 | } |
---|
246 | if( ord(p)==0 ) { string ordering = "),ls;"; } |
---|
247 | if( ord(p)>0 ) { string ordering = "),dp;"; } |
---|
248 | //-------------- create new ring and map objects to new ring ------------------ |
---|
249 | def br = basering; |
---|
250 | string str = "ring @newr = ("+charstr(br)+"),("+varstr(br)+ordering; |
---|
251 | execute(str); |
---|
252 | def id = fetch(br,id); |
---|
253 | poly vars = fetch(br,vars); |
---|
254 | //---------- now eliminate in new ring and map back to old ring --------------- |
---|
255 | id = eliminate(id,vars); |
---|
256 | setring br; |
---|
257 | return(imap(@newr,id)); |
---|
258 | } |
---|
259 | example |
---|
260 | { "EXAMPLE:"; echo = 2; |
---|
261 | ring r=0,(x,y,t,s,z),dp; |
---|
262 | ideal i=x-t,y-t2,z-t3,s-x+y3; |
---|
263 | elim1(i,ts); |
---|
264 | module m=i*gen(1)+i*gen(2); |
---|
265 | m=elim1(m,st); show(m); |
---|
266 | } |
---|
267 | /////////////////////////////////////////////////////////////////////////////// |
---|
268 | |
---|
269 | proc nselect (id, int n, list#) |
---|
270 | "USAGE: nselect(id,n[,m]); id a module or ideal, n, m integers |
---|
271 | RETURN: generators of id not containing the variable n [up to m] |
---|
272 | SEE ALSO: select, select1 |
---|
273 | EXAMPLE: example nselect; shows examples |
---|
274 | "{ |
---|
275 | int j,k; |
---|
276 | if( size(#)==0 ) { #[1]=n; } |
---|
277 | for( k=1; k<=ncols(id); k++ ) |
---|
278 | { for( j=n; j<=#[1]; j++ ) |
---|
279 | { if( size(id[k]/var(j))!=0) { id[k]=0; break; } |
---|
280 | } |
---|
281 | } |
---|
282 | return(simplify(id,2)); |
---|
283 | } |
---|
284 | example |
---|
285 | { "EXAMPLE:"; echo = 2; |
---|
286 | ring r=0,(x,y,t,s,z),(c,dp); |
---|
287 | ideal i=x-y,y-z2,z-t3,s-x+y3; |
---|
288 | nselect(i,3); |
---|
289 | module m=i*(gen(1)+gen(2)); |
---|
290 | show(m); |
---|
291 | show(nselect(m,3,4)); |
---|
292 | } |
---|
293 | /////////////////////////////////////////////////////////////////////////////// |
---|
294 | |
---|
295 | proc sat (id, ideal j) |
---|
296 | "USAGE: sat(id,j); id=ideal/module, j=ideal |
---|
297 | RETURN: list of an ideal/module [1] and an integer [2]: |
---|
298 | [1] = saturation of id with respect to j (= union_(k=1...) of id:j^k) |
---|
299 | [2] = saturation exponent (= min( k | id:j^k = id:j^(k+1) )) |
---|
300 | NOTE: [1] is a standard basis in the basering |
---|
301 | DISPLAY: saturation exponent during computation if printlevel >=1 |
---|
302 | EXAMPLE: example sat; shows an example |
---|
303 | "{ |
---|
304 | int ii,kk; |
---|
305 | def i=id; |
---|
306 | id=std(id); |
---|
307 | int p = printlevel-voice+3; // p=printlevel+1 (default: p=1) |
---|
308 | while( ii<=size(i) ) |
---|
309 | { |
---|
310 | dbprint(p-1,"// compute quotient "+string(kk+1)); |
---|
311 | i=quotient(id,j); |
---|
312 | for( ii=1; ii<=size(i); ii++ ) |
---|
313 | { |
---|
314 | if( reduce(i[ii],id,1)!=0 ) break; |
---|
315 | } |
---|
316 | id=std(i); kk++; |
---|
317 | } |
---|
318 | dbprint(p-1,"// saturation becomes stable after "+string(kk-1)+" iteration(s)",""); |
---|
319 | list L = id,kk-1; |
---|
320 | return (L); |
---|
321 | } |
---|
322 | example |
---|
323 | { "EXAMPLE:"; echo = 2; |
---|
324 | int p = printlevel; |
---|
325 | ring r = 2,(x,y,z),dp; |
---|
326 | poly F = x5+y5+(x-y)^2*xyz; |
---|
327 | ideal j = jacob(F); |
---|
328 | sat(j,maxideal(1)); |
---|
329 | printlevel = 2; |
---|
330 | sat(j,maxideal(2)); |
---|
331 | printlevel = p; |
---|
332 | } |
---|
333 | /////////////////////////////////////////////////////////////////////////////// |
---|
334 | |
---|
335 | proc select (id, int n, list#) |
---|
336 | "USAGE: select(id,n[,m]); id ideal/module, n, m integers |
---|
337 | RETURN: generators of id containing the variable n [all variables up to m] |
---|
338 | NOTE: use 'select1' for selecting generators containing at least one of the |
---|
339 | variables between n and m |
---|
340 | SEE ALSO: select1, nselect |
---|
341 | EXAMPLE: example select; shows examples |
---|
342 | "{ |
---|
343 | if( size(#)==0 ) { #[1]=n; } |
---|
344 | int j,k; |
---|
345 | for( k=1; k<=ncols(id); k++ ) |
---|
346 | { for( j=n; j<=#[1]; j++ ) |
---|
347 | { if( size(id[k]/var(j))==0) { id[k]=0; break; } |
---|
348 | } |
---|
349 | } |
---|
350 | return(simplify(id,2)); |
---|
351 | } |
---|
352 | example |
---|
353 | { "EXAMPLE:"; echo = 2; |
---|
354 | ring r=0,(x,y,t,s,z),(c,dp); |
---|
355 | ideal i=x-y,y-z2,z-t3,s-x+y3; |
---|
356 | ideal j=select(i,1); |
---|
357 | j; |
---|
358 | module m=i*(gen(1)+gen(2)); |
---|
359 | m; |
---|
360 | select(m,1,2); |
---|
361 | } |
---|
362 | /////////////////////////////////////////////////////////////////////////////// |
---|
363 | |
---|
364 | proc select1 (id, int n, list#) |
---|
365 | "USAGE: select1(id,n[,m]); id ideal/module, n, m integers |
---|
366 | RETURN: generators of id containing the variable n |
---|
367 | [at least one of the variables up to m] |
---|
368 | NOTE: use 'select' for selecting generators containing all the |
---|
369 | variables between n and m |
---|
370 | SEE ALSO: select, nselect |
---|
371 | EXAMPLE: example select1; shows examples |
---|
372 | "{ |
---|
373 | if( size(#)==0 ) { #[1]=n; } |
---|
374 | int j,k; |
---|
375 | execute (typeof(id)+" I;"); |
---|
376 | for( k=1; k<=ncols(id); k++ ) |
---|
377 | { for( j=n; j<=#[1]; j++ ) |
---|
378 | { |
---|
379 | if( size(subst(id[k],var(j),0)) != size(id[k]) ) |
---|
380 | { I=I,id[k]; break; } |
---|
381 | } |
---|
382 | } |
---|
383 | return(simplify(I,2)); |
---|
384 | } |
---|
385 | example |
---|
386 | { "EXAMPLE:"; echo = 2; |
---|
387 | ring r=0,(x,y,t,s,z),(c,dp); |
---|
388 | ideal i=x-y,y-z2,z-t3,s-x+y3; |
---|
389 | ideal j=select1(i,1); |
---|
390 | j; |
---|
391 | module m=i*(gen(1)+gen(2)); |
---|
392 | m; |
---|
393 | select1(m,1,2); |
---|
394 | } |
---|
395 | /////////////////////////////////////////////////////////////////////////////// |
---|