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