1 | /* Copyright 1997 Michael Messollen. All rights reserved. */ |
---|
2 | //////////////////////////////////////////////////////////// |
---|
3 | // emacs edit mode for this file is -*- C++ -*- |
---|
4 | //////////////////////////////////////////////////////////// |
---|
5 | static char * rcsid = "$Id: alg_factor.cc,v 1.12 2003-02-18 11:09:25 Singular Exp $"; |
---|
6 | //////////////////////////////////////////////////////////// |
---|
7 | // FACTORY - Includes |
---|
8 | #include <factory.h> |
---|
9 | // Factor - Includes |
---|
10 | #include <tmpl_inst.h> |
---|
11 | #include <Factor.h> |
---|
12 | #include <SqrFree.h> |
---|
13 | #include <helpstuff.h> |
---|
14 | // Charset - Includes |
---|
15 | #include "csutil.h" |
---|
16 | #include "charset.h" |
---|
17 | #include "reorder.h" |
---|
18 | #include "algfactor.h" |
---|
19 | // some CC's need this: |
---|
20 | #include "alg_factor.h" |
---|
21 | |
---|
22 | void out_cf(char *s1,const CanonicalForm &f,char *s2); |
---|
23 | |
---|
24 | #ifdef ALGFACTORDEBUG |
---|
25 | # define DEBUGOUTPUT |
---|
26 | #else |
---|
27 | # undef DEBUGOUTPUT |
---|
28 | #endif |
---|
29 | |
---|
30 | #include "debug.h" |
---|
31 | #include "timing.h" |
---|
32 | TIMING_DEFINE_PRINT(newfactoras_time); |
---|
33 | |
---|
34 | static Varlist |
---|
35 | Var_is_in_AS(const Varlist & uord, const CFList & Astar); |
---|
36 | |
---|
37 | int getAlgVar(const CanonicalForm &f, Variable &X) |
---|
38 | { |
---|
39 | if (f.inBaseDomain()) return 0; |
---|
40 | if (f.inCoeffDomain()) |
---|
41 | { |
---|
42 | if (f.level()!=0) |
---|
43 | { |
---|
44 | X= f.mvar(); |
---|
45 | return 1; |
---|
46 | } |
---|
47 | return getAlgVar(f.LC(),X); |
---|
48 | } |
---|
49 | if (f.inPolyDomain()) |
---|
50 | { |
---|
51 | if (getAlgVar(f.LC(),X)) return 1; |
---|
52 | for( CFIterator i=f; i.hasTerms(); i++) |
---|
53 | { |
---|
54 | if (getAlgVar(i.coeff(),X)) return 1; |
---|
55 | } |
---|
56 | } |
---|
57 | return 0; |
---|
58 | } |
---|
59 | |
---|
60 | //////////////////////////////////////////////////////////////////////// |
---|
61 | // This implements the algorithm of Trager for factorization of |
---|
62 | // (multivariate) polynomials over algebraic extensions and so called |
---|
63 | // function field extensions. |
---|
64 | //////////////////////////////////////////////////////////////////////// |
---|
65 | |
---|
66 | // // missing class: IntGenerator: |
---|
67 | bool IntGenerator::hasItems() const |
---|
68 | { |
---|
69 | return 1; |
---|
70 | } |
---|
71 | |
---|
72 | CanonicalForm IntGenerator::item() const |
---|
73 | //int IntGenerator::item() const |
---|
74 | { |
---|
75 | //return current; //CanonicalForm( current ); |
---|
76 | return mapinto(CanonicalForm( current )); |
---|
77 | } |
---|
78 | |
---|
79 | void IntGenerator::next() |
---|
80 | { |
---|
81 | current++; |
---|
82 | } |
---|
83 | |
---|
84 | // replacement for factory's broken psr |
---|
85 | static CanonicalForm |
---|
86 | mypsr ( const CanonicalForm &rr, const CanonicalForm &vv, const Variable & x ){ |
---|
87 | CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue; |
---|
88 | int dr, dv, d,n=0; |
---|
89 | |
---|
90 | |
---|
91 | dr = degree( r, x ); |
---|
92 | dv = degree( v, x ); |
---|
93 | if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);} |
---|
94 | else { l = 1; } |
---|
95 | d= dr-dv+1; |
---|
96 | while ( ( dv <= dr ) && ( r != r.genZero()) ){ |
---|
97 | test = power(x,dr-dv)*v*LC(r,x); |
---|
98 | if ( dr == 0 ) { r= CanonicalForm(0); } |
---|
99 | else { r= r - LC(r,x)*power(x,dr); } |
---|
100 | r= l*r -test; |
---|
101 | dr= degree(r,x); |
---|
102 | n+=1; |
---|
103 | } |
---|
104 | r= power(l, d-n)*r; |
---|
105 | return r; |
---|
106 | } |
---|
107 | |
---|
108 | // replacement for factory's broken resultant |
---|
109 | static CanonicalForm |
---|
110 | resultante( const CanonicalForm & f, const CanonicalForm& g, const Variable & v ){ |
---|
111 | return resultant(f,g,v); |
---|
112 | |
---|
113 | CanonicalForm h, beta, help, F, G; |
---|
114 | int delta; |
---|
115 | |
---|
116 | DEBOUTLN( cout, "resultante: called f= ", f); |
---|
117 | DEBOUTLN( cout, "resultante: called g= ", g); |
---|
118 | DEBOUTLN( cout, "resultante: called v= ", v); |
---|
119 | if ( f.mvar() < v || g.mvar() < v ){ |
---|
120 | DEBOUTMSG(cout, "resultante: f.mvar() < v || g.mvar() < v"); |
---|
121 | return 1; |
---|
122 | } |
---|
123 | |
---|
124 | if ( f.degree( v ) < 1 || g.degree( v ) < 1 ){ |
---|
125 | DEBOUTMSG(cout, "resultante: f.degree( v ) < 1 || g.degree( v ) < 1"); |
---|
126 | // If deg(F,v) == 0 , then resultante(F,G,v) = F^n, where n=deg(G,v) |
---|
127 | if ( f.degree( v ) < 1 ) return power(f,degree(g,v)); |
---|
128 | else return power(g,degree(f,v)); |
---|
129 | } |
---|
130 | |
---|
131 | if ( f.degree( v ) >= g.degree( v ) ) { F = f; G = g; } |
---|
132 | else { G = f; F = g; } |
---|
133 | |
---|
134 | h = CanonicalForm(1); |
---|
135 | while ( G != G.genZero() ) { |
---|
136 | delta= degree(F,v) -degree(G,v); |
---|
137 | beta = power(CanonicalForm(-1), delta+1) * LC(F,v)* power(h, delta); |
---|
138 | h= (h * power(LC(G,v), delta)) / power(h, delta); |
---|
139 | help= G; |
---|
140 | G= mypsr(F,G,v); |
---|
141 | G= G/beta; |
---|
142 | F=help; |
---|
143 | } |
---|
144 | if ( degree(F,v) != 0 ) F= CanonicalForm(0); |
---|
145 | return F; |
---|
146 | } |
---|
147 | |
---|
148 | // sqr-free routine for algebraic extensions |
---|
149 | // we need it! Ex.: f=c^2+2*a*c-1; as=[a^2+1]; f=(c+a)^2 |
---|
150 | static CFFList |
---|
151 | alg_sqrfree( const CanonicalForm & f ){ |
---|
152 | CFFList L; |
---|
153 | |
---|
154 | L.append(CFFactor(f,1)); |
---|
155 | return L; |
---|
156 | } |
---|
157 | |
---|
158 | // Calculates a square free norm |
---|
159 | // Input: f(x, alpha) a square free polynomial over K(alpha), |
---|
160 | // alpha is defined by the minimal polynomial Palpha |
---|
161 | // K has more than S elements (S is defined in thesis; look getextension) |
---|
162 | static void |
---|
163 | sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha, |
---|
164 | CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g, |
---|
165 | CanonicalForm & R){ |
---|
166 | Variable y=PPalpha.mvar(),vf=f.mvar(); |
---|
167 | CanonicalForm temp, Palpha=PPalpha, t; |
---|
168 | int sqfreetest=0; |
---|
169 | CFFList testlist; |
---|
170 | CFFListIterator i; |
---|
171 | |
---|
172 | DEBOUTLN(cout, "sqrf_norm_sub: f= ", f); |
---|
173 | DEBOUTLN(cout, "sqrf_norm_sub: Palpha= ", Palpha); |
---|
174 | myrandom.reset(); s=f.mvar()-myrandom.item()*Palpha.mvar(); g=f; |
---|
175 | R= CanonicalForm(0); |
---|
176 | DEBOUTLN(cout, "sqrf_norm_sub: myrandom s= ", s); |
---|
177 | |
---|
178 | // Norm, resultante taken with respect to y |
---|
179 | while ( !sqfreetest ){ |
---|
180 | DEBOUTLN(cout, "sqrf_norm_sub: Palpha= ", Palpha); |
---|
181 | R = resultante(Palpha, g, y); R= R* bCommonDen(R); |
---|
182 | DEBOUTLN(cout, "sqrf_norm_sub: R= ", R); |
---|
183 | // sqfree check ; R is a polynomial in K[x] |
---|
184 | if ( getCharacteristic() == 0 ) |
---|
185 | { |
---|
186 | temp= gcd(R, R.deriv(vf)); |
---|
187 | DEBOUTLN(cout, "sqrf_norm_sub: temp= ", temp); |
---|
188 | if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; } |
---|
189 | else { sqfreetest= 1; } |
---|
190 | DEBOUTLN(cout, "sqrf_norm_sub: sqfreetest= ", sqfreetest); |
---|
191 | } |
---|
192 | else{ |
---|
193 | DEBOUTMSG(cout, "Starting SqrFreeTest(R)!"); |
---|
194 | // Look at SqrFreeTest! |
---|
195 | // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 ! |
---|
196 | // for now we use this workaround with Factorize... |
---|
197 | // ...but it should go away soon!!!! |
---|
198 | Variable X; |
---|
199 | if (getAlgVar(R,X)) |
---|
200 | { |
---|
201 | if (R.isUnivariate()) |
---|
202 | testlist=factorize( R, X ); |
---|
203 | else |
---|
204 | testlist= Factorize(R, X, 0); |
---|
205 | } |
---|
206 | else |
---|
207 | testlist= Factorize(R); |
---|
208 | DEBOUTLN(cout, "testlist= ", testlist); |
---|
209 | testlist.removeFirst(); |
---|
210 | sqfreetest=1; |
---|
211 | for ( i=testlist; i.hasItem(); i++) |
---|
212 | if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; } |
---|
213 | DEBOUTLN(cout, "SqrFreeTest(R)= ", sqfreetest); |
---|
214 | } |
---|
215 | if ( ! sqfreetest ){ |
---|
216 | myrandom.next(); |
---|
217 | DEBOUTLN(cout, "sqrf_norm_sub generated new myrandom item: ", myrandom.item()); |
---|
218 | if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(myrandom.item())); |
---|
219 | else t= CanonicalForm(myrandom.item()); |
---|
220 | s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution |
---|
221 | DEBOUTLN(cout, "sqrf_norm_sub: testing s= ", s); |
---|
222 | g= f(f.mvar()-t*Palpha.mvar(), f.mvar()); |
---|
223 | DEBOUTLN(cout, " gives g= ", g); |
---|
224 | } |
---|
225 | } |
---|
226 | } |
---|
227 | |
---|
228 | static void |
---|
229 | sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha, |
---|
230 | const Variable & Extension, CanonicalForm & s, CanonicalForm & g, |
---|
231 | CanonicalForm & R){ |
---|
232 | |
---|
233 | DEBOUTLN(cout, "sqrf_norm: f= ", f); |
---|
234 | DEBOUTLN(cout, "sqrf_norm: Palpha= ", PPalpha); |
---|
235 | if ( getCharacteristic() == 0 ) { |
---|
236 | IntGenerator myrandom; |
---|
237 | DEBOUTMSG(cout, "sqrf_norm: no extension, char=0"); |
---|
238 | sqrf_norm_sub(f,PPalpha, myrandom, s,g,R); |
---|
239 | DEBOUTLN(cout, "sqrf_norm: f= ", f); |
---|
240 | DEBOUTLN(cout, "sqrf_norm: Palpha= ", PPalpha); |
---|
241 | DEBOUTLN(cout, "sqrf_norm: s= ", s); |
---|
242 | DEBOUTLN(cout, "sqrf_norm: g= ", g); |
---|
243 | DEBOUTLN(cout, "sqrf_norm: R= ", R); |
---|
244 | } |
---|
245 | else if ( degree(Extension) > 0 ){ // working over Extensions |
---|
246 | DEBOUTLN(cout, "sqrf_norm: degree of extension is ", degree(Extension)); |
---|
247 | AlgExtGenerator myrandom(Extension); |
---|
248 | sqrf_norm_sub(f,PPalpha, myrandom, s,g,R); |
---|
249 | } |
---|
250 | else{ |
---|
251 | FFGenerator myrandom; |
---|
252 | DEBOUTMSG(cout, "sqrf_norm: degree of extension is 0"); |
---|
253 | sqrf_norm_sub(f,PPalpha, myrandom, s,g,R); |
---|
254 | } |
---|
255 | } |
---|
256 | |
---|
257 | static Varlist |
---|
258 | Var_is_in_AS(const Varlist & uord, const CFList & Astar){ |
---|
259 | Varlist output; |
---|
260 | CanonicalForm elem; |
---|
261 | Variable x; |
---|
262 | |
---|
263 | for ( VarlistIterator i=uord; i.hasItem(); i++){ |
---|
264 | x=i.getItem(); |
---|
265 | for ( CFListIterator j=Astar; j.hasItem(); j++ ){ |
---|
266 | elem= j.getItem(); |
---|
267 | if ( degree(elem,x) > 0 ){ // x actually occures in Astar |
---|
268 | output.append(x); |
---|
269 | break; |
---|
270 | } |
---|
271 | } |
---|
272 | } |
---|
273 | return output; |
---|
274 | } |
---|
275 | |
---|
276 | // Look if Minimalpolynomials in Astar define seperable Extensions |
---|
277 | // Must be a power of p: i.e. y^{p^e}-x |
---|
278 | static int |
---|
279 | inseperable(const CFList & Astar){ |
---|
280 | CanonicalForm elem; |
---|
281 | int Counter= 1; |
---|
282 | |
---|
283 | if ( Astar.length() == 0 ) return 0; |
---|
284 | for ( CFListIterator i=Astar; i.hasItem(); i++){ |
---|
285 | elem= i.getItem(); |
---|
286 | if ( elem.deriv() == elem.genZero() ) return Counter; |
---|
287 | else Counter += 1; |
---|
288 | } |
---|
289 | return 0; |
---|
290 | } |
---|
291 | |
---|
292 | // calculate gcd of f and g in char=0 |
---|
293 | static CanonicalForm |
---|
294 | gcd0( CanonicalForm f, CanonicalForm g ){ |
---|
295 | int charac= getCharacteristic(); |
---|
296 | setCharacteristic(0); Off(SW_RATIONAL); |
---|
297 | CanonicalForm ff= mapinto(f), gg= mapinto(g); |
---|
298 | CanonicalForm result= gcd(ff,gg); |
---|
299 | setCharacteristic(charac); On(SW_RATIONAL); |
---|
300 | return mapinto(result); |
---|
301 | } |
---|
302 | |
---|
303 | // calculate big enough extension for finite fields |
---|
304 | // Idea: first calculate k, such that q^k > S (->thesis, -> getextension) |
---|
305 | // Second, search k with gcd(k,m_i)=1, where m_i is the degree of the i'th |
---|
306 | // minimal polynomial. Then the minpoly f_i remains irrd. over q^k and we |
---|
307 | // have enough elements to plug in. |
---|
308 | static int |
---|
309 | getextension( IntList & degreelist, int n){ |
---|
310 | int charac= getCharacteristic(); |
---|
311 | setCharacteristic(0); // need it for k ! |
---|
312 | int k=1, m=1, length=degreelist.length(); |
---|
313 | IntListIterator i; |
---|
314 | |
---|
315 | for (i=degreelist; i.hasItem(); i++) m= m*i.getItem(); |
---|
316 | int q=charac; |
---|
317 | while (q <= ((n*m)*(n*m)/2)) { k= k+1; q= q*charac;} |
---|
318 | int l=0; |
---|
319 | do { |
---|
320 | for (i=degreelist; i.hasItem(); i++){ |
---|
321 | l= l+1; |
---|
322 | if ( gcd0(k,i.getItem()) == 1){ |
---|
323 | DEBOUTLN(cout, "getextension: gcd == 1, l=",l); |
---|
324 | if ( l==length ){ setCharacteristic(charac); return k; } |
---|
325 | } |
---|
326 | else { DEBOUTMSG(cout, "getextension: Next iteration"); break; } |
---|
327 | } |
---|
328 | k= k+1; l=0; |
---|
329 | } |
---|
330 | while ( 1 ); |
---|
331 | } |
---|
332 | |
---|
333 | // calculate a "primitive element" |
---|
334 | // K must have more than S elements (->thesis, -> getextension) |
---|
335 | static CFList |
---|
336 | simpleextension(const CFList & Astar, const Variable & Extension, |
---|
337 | CanonicalForm & R){ |
---|
338 | CFList Returnlist, Bstar=Astar; |
---|
339 | CanonicalForm s, g; |
---|
340 | |
---|
341 | DEBOUTLN(cout, "simpleextension: Astar= ", Astar); |
---|
342 | DEBOUTLN(cout, "simpleextension: R= ", R); |
---|
343 | DEBOUTLN(cout, "simpleextension: Extension= ", Extension); |
---|
344 | if ( Astar.length() == 1 ){ R= Astar.getFirst();} |
---|
345 | else{ |
---|
346 | R=Bstar.getFirst(); Bstar.removeFirst(); |
---|
347 | for ( CFListIterator i=Bstar; i.hasItem(); i++){ |
---|
348 | DEBOUTLN(cout, "simpleextension: f(x)= ", i.getItem()); |
---|
349 | DEBOUTLN(cout, "simpleextension: P(x)= ", R); |
---|
350 | sqrf_norm(i.getItem(), R, Extension, s, g, R); |
---|
351 | // spielt die Repraesentation eine Rolle? |
---|
352 | // muessen wir die Nachfolger aendern, wenn s != 0 ? |
---|
353 | DEBOUTLN(cout, "simpleextension: g= ", g); |
---|
354 | if ( s != 0 ) DEBOUTLN(cout, "simpleextension: s= ", s); |
---|
355 | else DEBOUTLN(cout, "simpleextension: s= ", s); |
---|
356 | DEBOUTLN(cout, "simpleextension: R= ", R); |
---|
357 | Returnlist.insert(s); |
---|
358 | } |
---|
359 | } |
---|
360 | |
---|
361 | return Returnlist; |
---|
362 | } |
---|
363 | |
---|
364 | CanonicalForm alg_lc(const CanonicalForm &f) |
---|
365 | { |
---|
366 | if (f.inCoeffDomain()) return f; |
---|
367 | if (f.level()>0) |
---|
368 | { |
---|
369 | return alg_lc(f.LC()); |
---|
370 | } |
---|
371 | } |
---|
372 | |
---|
373 | // the heart of the algorithm: the one from Trager |
---|
374 | static CFFList |
---|
375 | alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as){ |
---|
376 | CFFList L, Factorlist; |
---|
377 | CanonicalForm R, Rstar, s, g, h; |
---|
378 | CFList substlist; |
---|
379 | |
---|
380 | DEBINCLEVEL(cout,"alg_factor"); |
---|
381 | DEBOUTLN(cout, "alg_factor: f= ", f); |
---|
382 | //out_cf("start alg_factor:",f,"\n"); |
---|
383 | substlist= simpleextension(Astar, vminpoly, Rstar); |
---|
384 | DEBOUTLN(cout, "alg_factor: substlist= ", substlist); |
---|
385 | DEBOUTLN(cout, "alg_factor: minpoly Rstar= ", Rstar); |
---|
386 | DEBOUTLN(cout, "alg_factor: vminpoly= ", vminpoly); |
---|
387 | |
---|
388 | sqrf_norm(f, Rstar, vminpoly, s, g, R ); |
---|
389 | //out_cf("sqrf_norm R:",R,"\n"); |
---|
390 | //out_cf("sqrf_norm s:",s,"\n"); |
---|
391 | //out_cf("sqrf_norm g:",g,"\n"); |
---|
392 | DEBOUTLN(cout, "alg_factor: g= ", g); |
---|
393 | DEBOUTLN(cout, "alg_factor: s= ", s); |
---|
394 | DEBOUTLN(cout, "alg_factor: R= ", R); |
---|
395 | Off(SW_RATIONAL); |
---|
396 | Variable X; |
---|
397 | if (getAlgVar(R,X)) |
---|
398 | { |
---|
399 | // factorize R over alg.extension with X |
---|
400 | //cout << "alg: "<< X << " mipo=" << getMipo(X,Variable('X')) <<endl; |
---|
401 | if (R.isUnivariate()) |
---|
402 | { |
---|
403 | DEBOUTLN(cout, "alg_factor: factorize( ", R); |
---|
404 | Factorlist = factorize( R, X ); |
---|
405 | } |
---|
406 | else |
---|
407 | { |
---|
408 | #if 1 |
---|
409 | Variable XX; |
---|
410 | CanonicalForm mipo=getMipo(X,XX); |
---|
411 | CFList as(mipo); |
---|
412 | DEBOUTLN(cout, "alg_factor: newfactoras( ", R); |
---|
413 | Factorlist = newfactoras(R, as , 1); |
---|
414 | #else |
---|
415 | // factor R over k |
---|
416 | DEBOUTLN(cout, "alg_factor: Factorize( ", R); |
---|
417 | Factorlist = Factorize(R); |
---|
418 | #endif |
---|
419 | } |
---|
420 | } |
---|
421 | else |
---|
422 | { |
---|
423 | // factor R over k |
---|
424 | DEBOUTLN(cout, "alg_factor: Factorize( ", R); |
---|
425 | Factorlist = Factorize(R); |
---|
426 | } |
---|
427 | On(SW_RATIONAL); |
---|
428 | DEBOUTLN(cout, "alg_factor: Factorize(R)= ", Factorlist); |
---|
429 | if ( !Factorlist.getFirst().factor().inCoeffDomain() ) |
---|
430 | Factorlist.insert(CFFactor(1,1)); |
---|
431 | if ( Factorlist.length() == 2 && Factorlist.getLast().exp()== 1){ // irreduzibel (first entry is a constant) |
---|
432 | L.append(CFFactor(f,1)); |
---|
433 | } |
---|
434 | else{ |
---|
435 | DEBOUTLN(cout, "alg_factor: g= ", g); |
---|
436 | CanonicalForm gnew= g(s,s.mvar()); |
---|
437 | DEBOUTLN(cout, "alg_factor: gnew= ", gnew); |
---|
438 | g=gnew; |
---|
439 | for ( CFFListIterator i=Factorlist; i.hasItem(); i++){ |
---|
440 | CanonicalForm fnew=i.getItem().factor(); |
---|
441 | fnew= fnew(s,s.mvar()); |
---|
442 | DEBOUTLN(cout, "alg_factor: fnew= ", fnew); |
---|
443 | DEBOUTLN(cout, "alg_factor: substlist= ", substlist); |
---|
444 | for ( CFListIterator ii=substlist; ii.hasItem(); ii++){ |
---|
445 | DEBOUTLN(cout, "alg_factor: item= ", ii.getItem()); |
---|
446 | fnew= fnew(ii.getItem(), ii.getItem().mvar()); |
---|
447 | DEBOUTLN(cout, "alg_factor: fnew= ", fnew); |
---|
448 | } |
---|
449 | if (degree(i.getItem().factor()) > 0 ){ |
---|
450 | // undo linear transformation!!!! and then gcd! |
---|
451 | //cout << "algcd(" << g << "," << fnew << ",as" << as << ")" << endl; |
---|
452 | //out_cf("algcd g=",g,"\n"); |
---|
453 | //out_cf("algcd fnew=",fnew,"\n"); |
---|
454 | //h= algcd(g,fnew, as, oldord); |
---|
455 | //if (as.length() >1) |
---|
456 | // h= algcd(g,fnew, as, oldord); |
---|
457 | //else |
---|
458 | h=alg_gcd(g,fnew,as); |
---|
459 | //out_cf(" -> algcd=",algcd(g,fnew, as, oldord),"\n"); |
---|
460 | //out_cf(" -> alg_gcd=",alg_gcd(g,fnew,as),"\n"); |
---|
461 | //cout << "algcd result:" << h << endl; |
---|
462 | DEBOUTLN(cout, " alg_factor: h= ", h); |
---|
463 | DEBOUTLN(cout, " alg_factor: oldord= ", oldord); |
---|
464 | if ( degree(h) > 0 ){ //otherwise it's a constant |
---|
465 | g= divide(g, h,as); |
---|
466 | DEBOUTLN(cout, "alg_factor: g/h= ", g); |
---|
467 | DEBOUTLN(cout, "alg_factor: s= ", s); |
---|
468 | DEBOUTLN(cout, "alg_factor: substlist= ", substlist); |
---|
469 | L.append(CFFactor(h,1)); |
---|
470 | } |
---|
471 | } |
---|
472 | } |
---|
473 | // we are not interested in a |
---|
474 | // constant (over K_r, which can be a polynomial!) |
---|
475 | if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); } |
---|
476 | } |
---|
477 | CFFList LL; |
---|
478 | if (getCharacteristic()>0) |
---|
479 | { |
---|
480 | CFFListIterator i=L; |
---|
481 | CanonicalForm c_fac=1; |
---|
482 | CanonicalForm c; |
---|
483 | for(;i.hasItem(); i++ ) |
---|
484 | { |
---|
485 | CanonicalForm ff=i.getItem().factor(); |
---|
486 | c=alg_lc(ff); |
---|
487 | int e=i.getItem().exp(); |
---|
488 | ff/=c; |
---|
489 | if (!ff.isOne()) LL.append(CFFactor(ff,e)); |
---|
490 | while (e>0) { c_fac*=c;e--; } |
---|
491 | } |
---|
492 | if (!c_fac.isOne()) LL.insert(CFFactor(c_fac,1)); |
---|
493 | } |
---|
494 | else |
---|
495 | { |
---|
496 | LL=L; |
---|
497 | } |
---|
498 | //CFFListIterator i=LL; |
---|
499 | //for(;i.hasItem(); i++ ) |
---|
500 | // out_cf("end alg_f:",i.getItem().factor(),"\n"); |
---|
501 | //printf("end alg_factor\n"); |
---|
502 | DEBOUTLN(cout, "alg_factor: L= ", LL); |
---|
503 | DEBDECLEVEL(cout,"alg_factor"); |
---|
504 | return LL; |
---|
505 | } |
---|
506 | |
---|
507 | static CFFList |
---|
508 | endler( const CanonicalForm & f, const CFList & AS, const Varlist & uord ){ |
---|
509 | CanonicalForm F=f, g, q,r; |
---|
510 | CFFList Output; |
---|
511 | CFList One, Two, asnew, as=AS; |
---|
512 | CFListIterator i,ii; |
---|
513 | VarlistIterator j; |
---|
514 | Variable vg; |
---|
515 | |
---|
516 | for (i=as; i.hasItem(); i++){ |
---|
517 | g= i.getItem(); |
---|
518 | if (g.deriv() == 0 ){ |
---|
519 | DEBOUTLN(cout, "Inseperable extension detected: ", g); |
---|
520 | for (j=uord; j.hasItem(); j++){ |
---|
521 | if ( degree(g,j.getItem()) > 0 ) vg= j.getItem(); |
---|
522 | } |
---|
523 | // Now we have the highest transzendental in vg; |
---|
524 | DEBOUTLN(cout, "Transzendental is ", vg); |
---|
525 | CanonicalForm gg=-1*g[0]; |
---|
526 | divrem(gg,vg,q,r); r= gg-q*vg; gg= gg-r; |
---|
527 | //DEBOUTLN(cout, "q= ", q); DEBOUTLN(cout, "r= ", r); |
---|
528 | DEBOUTLN(cout, " that is ", gg); |
---|
529 | DEBOUTLN(cout, " maps to ", g+gg); |
---|
530 | One.insert(gg); Two.insert(g+gg); |
---|
531 | // Now transform all remaining polys in as: |
---|
532 | int x=0; |
---|
533 | for (ii=i; ii.hasItem(); ii++){ |
---|
534 | if ( x != 0 ){ |
---|
535 | divrem(ii.getItem(), gg, q,r); |
---|
536 | // cout << ii.getItem() << " divided by " << gg << endl; |
---|
537 | DEBOUTLN(cout, "q= ", q); DEBOUTLN(cout, "r= ", r); |
---|
538 | ii.append(ii.getItem()+q*g); ii.remove(1); |
---|
539 | DEBOUTLN(cout, "as= ", as); |
---|
540 | } |
---|
541 | x+= 1; |
---|
542 | } |
---|
543 | // Now transform F: |
---|
544 | divrem(F, gg, q,r); |
---|
545 | F= F+q*g; |
---|
546 | DEBOUTLN(cout, "new F= ", F); |
---|
547 | } |
---|
548 | else{ asnew.append(i.getItem()); }// just the identity |
---|
549 | } |
---|
550 | // factor F with minimal polys given in asnew: |
---|
551 | DEBOUTLN(cout, "Factor F= ", F); |
---|
552 | DEBOUTLN(cout, " with as= ", asnew); |
---|
553 | int success=0; |
---|
554 | CFFList factorlist= newcfactor(F,asnew, success); |
---|
555 | DEBOUTLN(cout, " gives = ", factorlist); |
---|
556 | DEBOUTLN(cout, "One= ", One); |
---|
557 | DEBOUTLN(cout, "Two= ", Two); |
---|
558 | |
---|
559 | // Transform back: |
---|
560 | for ( CFFListIterator k=factorlist; k.hasItem(); k++){ |
---|
561 | CanonicalForm factor= k.getItem().factor(); |
---|
562 | ii=One; |
---|
563 | for (i=Two; i.hasItem(); i++){ |
---|
564 | DEBOUTLN(cout, "Mapping ", i.getItem()); |
---|
565 | DEBOUTLN(cout, " to ", ii.getItem()); |
---|
566 | DEBOUTLN(cout, " in ", factor); |
---|
567 | divrem(factor,i.getItem(),q,r); r=factor -q*i.getItem(); |
---|
568 | DEBOUTLN(cout, "q= ", q); DEBOUTLN(cout, "r= ", r); |
---|
569 | factor= ii.getItem()*q +r; // |
---|
570 | ii++; |
---|
571 | } |
---|
572 | Output.append(CFFactor(factor,k.getItem().exp())); |
---|
573 | } |
---|
574 | |
---|
575 | return Output; |
---|
576 | } |
---|
577 | |
---|
578 | |
---|
579 | // 1) prepares data |
---|
580 | // 2) for char=p we distinguish 3 cases: |
---|
581 | // no transcendentals, seperable and inseperable extensions |
---|
582 | CFFList |
---|
583 | newfactoras( const CanonicalForm & f, const CFList & as, int success){ |
---|
584 | Variable vf=f.mvar(); |
---|
585 | CFListIterator i; |
---|
586 | CFFListIterator jj; |
---|
587 | CFList reduceresult; |
---|
588 | CFFList result; |
---|
589 | |
---|
590 | success=1; |
---|
591 | DEBINCLEVEL(cout, "newfactoras"); |
---|
592 | DEBOUTMSG(cerr, rcsid); |
---|
593 | DEBOUTLN(cout, "newfactoras called with f= ", f); |
---|
594 | DEBOUTLN(cout, " content(f)= ", content(f)); |
---|
595 | DEBOUTLN(cout, " as= ", as); |
---|
596 | DEBOUTLN(cout, "newfactoras: cls(vf)= ", cls(vf)); |
---|
597 | DEBOUTLN(cout, "newfactoras: cls(as.getLast())= ", cls(as.getLast())); |
---|
598 | DEBOUTLN(cout, "newfactoras: degree(f,vf)= ", degree(f,vf)); |
---|
599 | |
---|
600 | // F1: [Test trivial cases] |
---|
601 | // 1) first trivial cases: |
---|
602 | if ( (cls(vf) <= cls(as.getLast())) || degree(f,vf)<=1 ){ |
---|
603 | // ||( (as.length()==1) && (degree(f,vf)==3) && (degree(as.getFirst()==2)) ) |
---|
604 | DEBDECLEVEL(cout,"newfactoras"); |
---|
605 | return CFFList(CFFactor(f,1)); |
---|
606 | } |
---|
607 | |
---|
608 | // 2) List of variables: |
---|
609 | // 2a) Setup list of those polys in AS having degree(AS[i], AS[i].mvar()) > 1 |
---|
610 | // 2b) Setup variableordering |
---|
611 | CFList Astar; |
---|
612 | Variable x; |
---|
613 | CanonicalForm elem; |
---|
614 | Varlist ord, uord,oldord; |
---|
615 | for ( int ii=1; ii< level(vf) ; ii++ ) { uord.append(Variable(ii)); } |
---|
616 | oldord= uord; oldord.append(vf); |
---|
617 | |
---|
618 | for ( i=as; i.hasItem(); i++ ){ |
---|
619 | elem= i.getItem(); |
---|
620 | x= elem.mvar(); |
---|
621 | if ( degree(elem,x) > 1){ // otherwise it's not an extension |
---|
622 | //if ( degree(f,x) > 0 ){ // does it occure in f? RICHTIG? |
---|
623 | Astar.append(elem); |
---|
624 | ord.append(x); |
---|
625 | //} |
---|
626 | } |
---|
627 | } |
---|
628 | uord= Difference(uord,ord); |
---|
629 | DEBOUTLN(cout, "Astar is: ", Astar); |
---|
630 | DEBOUTLN(cout, "ord is: ", ord); |
---|
631 | DEBOUTLN(cout, "uord is: ", uord); |
---|
632 | |
---|
633 | // 3) second trivial cases: we already prooved irr. of f over no extensions |
---|
634 | if ( Astar.length() == 0 ){ |
---|
635 | DEBDECLEVEL(cout,"newfactoras"); |
---|
636 | return CFFList(CFFactor(f,1)); |
---|
637 | } |
---|
638 | |
---|
639 | // 4) Try to obtain a partial factorization using prop2 and prop3 |
---|
640 | // Use with caution! We have to proof these propositions first! |
---|
641 | // Not yet implemented |
---|
642 | |
---|
643 | // 5) Look if elements in uord actually occure in any of the minimal |
---|
644 | // polynomials. If no element of uord occures in any of the minimal |
---|
645 | // polynomials, we don't have transzendentals. |
---|
646 | Varlist newuord=Var_is_in_AS(uord,Astar); |
---|
647 | DEBOUTLN(cout, "newuord is: ", newuord); |
---|
648 | |
---|
649 | CFFList Factorlist; |
---|
650 | Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar()); |
---|
651 | // This is for now. we need alg_sqrfree implemented! |
---|
652 | //cout << "algcd(" << f << "," << f.deriv() << " as:" << Astar <<endl; |
---|
653 | //CanonicalForm Fgcd= algcd(f,f.deriv(),Astar,gcdord); |
---|
654 | CanonicalForm Fgcd; |
---|
655 | //if (Astar.length() >1) |
---|
656 | // Fgcd= algcd(f,f.deriv(),Astar,gcdord); |
---|
657 | //else |
---|
658 | Fgcd= alg_gcd(f,f.deriv(),Astar); |
---|
659 | //out_cf("algcd:",algcd(f,f.deriv(),Astar,gcdord),"\n"); |
---|
660 | //out_cf("alg_gcd:",alg_gcd(f,f.deriv(),Astar),"\n"); |
---|
661 | // cout << "algcd result:" << Fgcd << endl; |
---|
662 | if ( Fgcd == 0 ) DEBOUTMSG(cerr, "WARNING: p'th root ?"); |
---|
663 | if (( degree(Fgcd, f.mvar()) > 0) && (!(f.deriv().isZero())) ){ |
---|
664 | DEBOUTLN(cout, "Nontrivial GCD found of ", f); |
---|
665 | CanonicalForm Ggcd= divide(f, Fgcd,Astar); |
---|
666 | DEBOUTLN(cout, " split into ", Fgcd); |
---|
667 | DEBOUTLN(cout, " and ", Ggcd); |
---|
668 | Fgcd= pp(Fgcd); Ggcd= pp(Ggcd); |
---|
669 | DEBDECLEVEL(cout,"newfactoras"); |
---|
670 | return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success)); |
---|
671 | } |
---|
672 | if ( getCharacteristic() > 0 ){ |
---|
673 | |
---|
674 | // First look for extension! |
---|
675 | IntList degreelist; |
---|
676 | Variable vminpoly; |
---|
677 | for (i=Astar; i.hasItem(); i++){degreelist.append(degree(i.getItem()));} |
---|
678 | int extdeg= getextension(degreelist, degree(f)); |
---|
679 | DEBOUTLN(cout, "Extension needed of degree ", extdeg); |
---|
680 | |
---|
681 | // Now the real stuff! |
---|
682 | if ( newuord.length() == 0 ){ // no transzendentals |
---|
683 | DEBOUTMSG(cout, "No transzendentals!"); |
---|
684 | if ( extdeg > 1 ){ |
---|
685 | CanonicalForm MIPO= generate_mipo( extdeg, vminpoly); |
---|
686 | DEBOUTLN(cout, "Minpoly produced ", MIPO); |
---|
687 | vminpoly= rootOf(MIPO); |
---|
688 | } |
---|
689 | Factorlist= alg_factor(f, Astar, vminpoly, oldord, as); |
---|
690 | DEBDECLEVEL(cout,"newfactoras"); |
---|
691 | return Factorlist; |
---|
692 | } |
---|
693 | else if ( inseperable(Astar) > 0 ){ // Look if extensions are seperable |
---|
694 | // a) Use Endler |
---|
695 | DEBOUTMSG(cout, "Inseperable extensions! Using Endler!"); |
---|
696 | CFFList templist= endler(f,Astar, newuord); |
---|
697 | DEBOUTLN(cout, "Endler gives: ", templist); |
---|
698 | return templist; |
---|
699 | } |
---|
700 | else{ // we are on the save side: Use trager |
---|
701 | DEBOUTMSG(cout, "Only seperable extensions!"); |
---|
702 | if (extdeg > 1 ){ |
---|
703 | CanonicalForm MIPO=generate_mipo(extdeg, vminpoly ); |
---|
704 | vminpoly= rootOf(MIPO); |
---|
705 | DEBOUTLN(cout, "Minpoly generated: ", MIPO); |
---|
706 | DEBOUTLN(cout, "vminpoly= ", vminpoly); |
---|
707 | DEBOUTLN(cout, "degree(vminpoly)= ", degree(vminpoly)); |
---|
708 | } |
---|
709 | Factorlist= alg_factor(f, Astar, vminpoly, oldord, as); |
---|
710 | DEBDECLEVEL(cout,"newfactoras"); |
---|
711 | return Factorlist; |
---|
712 | } |
---|
713 | } |
---|
714 | else{ // char=0 apply trager directly |
---|
715 | DEBOUTMSG(cout, "Char=0! Apply Trager!"); |
---|
716 | Variable vminpoly; |
---|
717 | Factorlist= alg_factor(f, Astar, vminpoly, oldord, as); |
---|
718 | DEBDECLEVEL(cout,"newfactoras"); |
---|
719 | return Factorlist; |
---|
720 | } |
---|
721 | |
---|
722 | DEBDECLEVEL(cout,"newfactoras"); |
---|
723 | return CFFList(CFFactor(f,1)); |
---|
724 | } |
---|
725 | |
---|
726 | CFFList |
---|
727 | newcfactor(const CanonicalForm & f, const CFList & as, int success ){ |
---|
728 | Off(SW_RATIONAL); |
---|
729 | CFFList Output, output, Factors=Factorize(f); On(SW_RATIONAL); |
---|
730 | Factors.removeFirst(); |
---|
731 | |
---|
732 | if ( as.length() == 0 ){ success=1; return Factors;} |
---|
733 | if ( cls(f) <= cls(as.getLast()) ) { success=1; return Factors;} |
---|
734 | |
---|
735 | success=1; |
---|
736 | for ( CFFListIterator i=Factors; i.hasItem(); i++ ){ |
---|
737 | output=newfactoras(i.getItem().factor(),as, success); |
---|
738 | for ( CFFListIterator j=output; j.hasItem(); j++) |
---|
739 | Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp())); |
---|
740 | } |
---|
741 | return Output; |
---|
742 | } |
---|
743 | |
---|
744 | /* |
---|
745 | $Log: not supported by cvs2svn $ |
---|
746 | Revision 1.11 2002/10/24 17:22:21 Singular |
---|
747 | * hannes: factoring in alg.ext., alg_gcd, NTL stuff |
---|
748 | |
---|
749 | Revision 1.10 2002/08/19 11:11:29 Singular |
---|
750 | * hannes/pfister: alg_gcd etc. |
---|
751 | |
---|
752 | Revision 1.9 2002/07/30 15:16:19 Singular |
---|
753 | *hannes: fix for alg. extension |
---|
754 | |
---|
755 | Revision 1.8 2001/08/06 08:32:53 Singular |
---|
756 | * hannes: code cleanup |
---|
757 | |
---|
758 | Revision 1.7 2001/06/27 13:58:05 Singular |
---|
759 | *hannes/GP: debug newfactoras, char_series, ... |
---|
760 | |
---|
761 | Revision 1.6 2001/06/21 14:57:04 Singular |
---|
762 | *hannes/GP: Factorize, newfactoras, ... |
---|
763 | |
---|
764 | Revision 1.5 2001/06/18 08:44:39 pfister |
---|
765 | * hannes/GP/michael: factory debug, Factorize |
---|
766 | |
---|
767 | Revision 1.4 1998/05/25 18:32:38 obachman |
---|
768 | 1998-05-25 Olaf Bachmann <obachman@mathematik.uni-kl.de> |
---|
769 | |
---|
770 | * charset/alg_factor.cc: replaced identifiers 'random' by |
---|
771 | 'myrandom' to avoid name conflicts with the built-in (stdlib) |
---|
772 | library function 'random' which might be a macro -- and, actually |
---|
773 | is under gcc v 2.6.3 |
---|
774 | |
---|
775 | Revision 1.3 1998/03/12 12:34:24 schmidt |
---|
776 | * charset/csutil.cc, charset/alg_factor.cc: all references to |
---|
777 | `common_den()' replaced by `bCommonDen()' |
---|
778 | |
---|
779 | Revision 1.2 1997/09/12 07:19:37 Singular |
---|
780 | * hannes/michael: libfac-0.3.0 |
---|
781 | |
---|
782 | */ |
---|