source: git/factory/libfac/charset/alg_factor.cc @ d92d71

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