1 | //GMG, last modified 28.10.2001 |
---|
2 | /////////////////////////////////////////////////////////////////////////////// |
---|
3 | version="$Id: weierstr.lib,v 1.6 2009-04-06 12:39:02 seelisch Exp $"; |
---|
4 | category="Teaching"; |
---|
5 | info=" |
---|
6 | LIBRARY: weierstr.lib Procedures for the Weierstrass Theorems |
---|
7 | AUTHOR: G.-M. Greuel, greuel@mathematik.uni-kl.de |
---|
8 | |
---|
9 | PROCEDURES: |
---|
10 | weierstrDiv(g,f,d); perform Weierstrass division of g by f up to degree d |
---|
11 | weierstrPrep(f,d); perform Weierstrass preparation of f up to degree d |
---|
12 | lastvarGeneral(f); make f general of finite order w.r.t. last variable |
---|
13 | generalOrder(f); compute integer b s.t. f is x_n-general of order b |
---|
14 | |
---|
15 | (parameters in square brackets [] are optional) |
---|
16 | "; |
---|
17 | |
---|
18 | LIB "mondromy.lib"; |
---|
19 | LIB "poly.lib"; |
---|
20 | /////////////////////////////////////////////////////////////////////////////// |
---|
21 | |
---|
22 | proc generalOrder (poly f) |
---|
23 | "USAGE: generalOrder(f); f=poly |
---|
24 | RETURN: integer b if f is general of order b w.r.t. the last variable, say T, |
---|
25 | resp. -1 if not |
---|
26 | (i.e. f(0,...,0,T) is of order b, resp. f(0,...,0,T)==0) |
---|
27 | NOTE: the procedure works for any monomial ordering |
---|
28 | EXAMPLE: example generalOrder; shows an example |
---|
29 | " |
---|
30 | { int ii; |
---|
31 | int n = nvars(basering); |
---|
32 | for (ii=1; ii<n; ii++) |
---|
33 | { |
---|
34 | f = subst(f,var(ii),0); |
---|
35 | } |
---|
36 | return(mindeg(f)); |
---|
37 | } |
---|
38 | example |
---|
39 | { "EXAMPLE:"; echo = 2; |
---|
40 | ring R = 0,(x,y),ds; |
---|
41 | poly f = x2-4xy+4y2-2xy2+4y3+y4; |
---|
42 | generalOrder(f); |
---|
43 | } |
---|
44 | /////////////////////////////////////////////////////////////////////////////// |
---|
45 | |
---|
46 | proc weierstrDiv ( poly g, poly f, int d ) |
---|
47 | "USAGE: weierstrDiv(g,f,d); g,f=poly, d=integer |
---|
48 | ASSUME: f must be general of finite order, say b, in the last ring variable, |
---|
49 | say T; if not use the procedure lastvarGeneral first |
---|
50 | PURPOSE: perform the Weierstrass division of g by f up to order d |
---|
51 | RETURN: - a list, say l, of two polynomials and an integer, such that@* |
---|
52 | g = l[1]*f + l[2], deg_T(l[2]) < b, up to (including) total degree d@* |
---|
53 | - l[3] is the number of iterations used |
---|
54 | - if f is not T-general, return (0,g) |
---|
55 | NOTE: the procedure works for any monomial ordering |
---|
56 | THEORY: the proof of Grauert-Remmert (Analytische Stellenalgebren) is used |
---|
57 | for the algorithm |
---|
58 | EXAMPLE: example weierstrDiv; shows an example |
---|
59 | " |
---|
60 | { |
---|
61 | //------------- initialisation and check T - general ------------------------- |
---|
62 | int a,b,ii,D; |
---|
63 | poly r,h; |
---|
64 | list result; |
---|
65 | int y = printlevel - voice + 2; |
---|
66 | int n = nvars(basering); |
---|
67 | intvec v; |
---|
68 | v[n]=1; |
---|
69 | b = generalOrder(f); |
---|
70 | if (y>0) |
---|
71 | { |
---|
72 | "//",f;"// is "+string(var(n))+"-general of order", b; |
---|
73 | pause("press <return> to continue"); |
---|
74 | } |
---|
75 | if ( b==-1 ) |
---|
76 | { |
---|
77 | "// second poly is not general w.r.t. last variable"; |
---|
78 | "// use the procedure lastvarGeneral first"; |
---|
79 | result=h,g; |
---|
80 | return(result); |
---|
81 | } |
---|
82 | //------------------------- start computation -------------------------------- |
---|
83 | D = d+b; |
---|
84 | poly fhat = jet(f,b-1,v); |
---|
85 | poly ftilde = (f-fhat)/var(n)^b; |
---|
86 | poly u = invunit(ftilde,D); |
---|
87 | if (y>0) |
---|
88 | { |
---|
89 | "// fhat (up to order", d,"):"; |
---|
90 | "//", fhat; |
---|
91 | "// ftilde:"; |
---|
92 | "//", ftilde; |
---|
93 | "// ftilde-inverse:"; |
---|
94 | "//", u; |
---|
95 | pause("press <return> to continue"); |
---|
96 | } |
---|
97 | poly khat, ktilde; |
---|
98 | poly k=g; |
---|
99 | khat = jet(k,b-1,v); |
---|
100 | ktilde = (k-r)/var(n)^b; |
---|
101 | r = khat; |
---|
102 | h = ktilde; |
---|
103 | ii=0; |
---|
104 | while (size(k) > 0) |
---|
105 | { |
---|
106 | if (y>0) |
---|
107 | { |
---|
108 | "// loop",ii+1; |
---|
109 | "// khat:"; |
---|
110 | "//", khat; |
---|
111 | "// ktilde:"; |
---|
112 | "//", ktilde; |
---|
113 | "// remainder:"; |
---|
114 | "//", r; |
---|
115 | "// multiplier:"; |
---|
116 | "//", h; |
---|
117 | pause("press <return> to continue"); |
---|
118 | } |
---|
119 | k = jet(-fhat*u*ktilde,D); |
---|
120 | khat = jet(k,b-1,v); |
---|
121 | ktilde = (k-khat)/var(n)^b; |
---|
122 | r = r + khat; |
---|
123 | h = h + ktilde; |
---|
124 | ii=ii+1; |
---|
125 | } |
---|
126 | result = jet(u*h,d),jet(r,d),ii; |
---|
127 | return(result); |
---|
128 | } |
---|
129 | example |
---|
130 | { "EXAMPLE:"; echo = 2; |
---|
131 | ring R = 0,(x,y),ds; |
---|
132 | poly f = y - xy2 + x2; |
---|
133 | poly g = y; |
---|
134 | list l = weierstrDiv(g,f,10); l;""; |
---|
135 | l[1]*f + l[2]; //g = l[1]*f+l[2] up to degree 10 |
---|
136 | } |
---|
137 | /////////////////////////////////////////////////////////////////////////////// |
---|
138 | |
---|
139 | proc weierstrPrep (poly f, int d) |
---|
140 | "USAGE: weierstrPrep(f,d); f=poly, d=integer |
---|
141 | ASSUME: f must be general of finite order, say b, in the last ring variable, |
---|
142 | say T; if not apply the procedure lastvarGeneral first |
---|
143 | PURPOSE: perform the Weierstrass preparation of f up to order d |
---|
144 | RETURN: - a list, say l, of two polynomials and one integer, |
---|
145 | l[1] a unit, l[2] a Weierstrass polynomial, l[3] an integer |
---|
146 | such that l[1]*f = l[2], where l[2] is a Weierstrass polynomial, |
---|
147 | (i.e. l[2] = T^b + lower terms in T) up to (including) total degree d |
---|
148 | l[3] is the number of iterations used@* |
---|
149 | - if f is not T-general, return (0,0) |
---|
150 | NOTE: the procedure works for any monomial ordering |
---|
151 | THEORY: the proof of Grauert-Remmert (Analytische Stellenalgebren) is used |
---|
152 | for the algorithm |
---|
153 | EXAMPLE: example weierstrPrep; shows an example |
---|
154 | " |
---|
155 | { |
---|
156 | int n = nvars(basering); |
---|
157 | int b = generalOrder(f); |
---|
158 | if ( b==-1 ) |
---|
159 | { |
---|
160 | "// second poly is not general w.r.t. last variable"; |
---|
161 | "// use the procedure lastvarGeneral first"; |
---|
162 | poly h,g; |
---|
163 | list result=h,g; |
---|
164 | return(result); |
---|
165 | } |
---|
166 | list L = weierstrDiv(var(n)^b,f,d); |
---|
167 | list result = L[1], var(n)^b - L[2],L[3]; |
---|
168 | return(result); |
---|
169 | } |
---|
170 | example |
---|
171 | { "EXAMPLE:"; echo = 2; |
---|
172 | ring R = 0,(x,y),ds; |
---|
173 | poly f = xy+y2+y4; |
---|
174 | list l = weierstrPrep(f,5); l; ""; |
---|
175 | f*l[1]-l[2]; // = 0 up to degree 5 |
---|
176 | } |
---|
177 | /////////////////////////////////////////////////////////////////////////////// |
---|
178 | |
---|
179 | proc lastvarGeneral (poly f) |
---|
180 | "USAGE: lastvarGeneral(f,d); f=poly |
---|
181 | RETURN: poly, say g, obtained from f by a generic change of variables, s.t. |
---|
182 | g is general of finite order b w.r.t. the last ring variable, say T |
---|
183 | (i.e. g(0,...,0,T)= c*T^b + higher terms, c!=0) |
---|
184 | NOTE: the procedure works for any monomial ordering |
---|
185 | EXAMPLE: example lastvarGeneral; shows an example |
---|
186 | " |
---|
187 | { |
---|
188 | int n = nvars(basering); |
---|
189 | int b = generalOrder(f); |
---|
190 | if ( b >=0 ) { return(f); } |
---|
191 | else |
---|
192 | { |
---|
193 | def B = basering; |
---|
194 | int ii; |
---|
195 | map phi; |
---|
196 | ideal m=maxideal(1); |
---|
197 | int d = mindeg1(f); |
---|
198 | poly g = jet(f,d); |
---|
199 | for (ii=1; ii<=n-1; ii++) |
---|
200 | { |
---|
201 | if (size(g)>size(subst(g,var(ii),0)) ) |
---|
202 | { |
---|
203 | m[ii]= var(ii)+ random(1-(voice-2)*10,1+(voice-2)*10)*var(n); |
---|
204 | phi = B,m; |
---|
205 | g = phi(f); |
---|
206 | break; |
---|
207 | } |
---|
208 | } |
---|
209 | if ( voice <=5 ) |
---|
210 | { |
---|
211 | return(lastvarGeneral(g)); |
---|
212 | } |
---|
213 | if ( voice ==6 ) |
---|
214 | { |
---|
215 | for (ii=1; ii<=n-1; ii++) |
---|
216 | { |
---|
217 | m[ii]= var(ii)+ var(n)*random(1,1000); |
---|
218 | } |
---|
219 | phi = basering,m; |
---|
220 | g = phi(f); |
---|
221 | return(lastvarGeneral(g)); |
---|
222 | } |
---|
223 | else |
---|
224 | { |
---|
225 | for (ii=1; ii<=n-1; ii++) |
---|
226 | { |
---|
227 | m[ii]= var(ii)+ var(n)^random(2,voice*d); |
---|
228 | } |
---|
229 | phi = basering,m; |
---|
230 | g = phi(f); |
---|
231 | return(lastvarGeneral(g)); |
---|
232 | } |
---|
233 | } |
---|
234 | } |
---|
235 | example |
---|
236 | { "EXAMPLE:"; echo = 2; |
---|
237 | ring R = 2,(x,y,z),ls; |
---|
238 | poly f = xyz; |
---|
239 | lastvarGeneral(f); |
---|
240 | } |
---|
241 | /////////////////////////////////////////////////////////////////////////////// |
---|
242 | |
---|