source: git/factory/libfac/charset/alg_factor.cc @ 5f4e0e

spielwiese
Last change on this file since 5f4e0e was 5f4e0e, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: added 'subst' to substitute alg. variables in f by their image in the absolute extension
  • Property mode set to 100644
File size: 31.5 KB
Line 
1////////////////////////////////////////////////////////////
2// emacs edit mode for this file is -*- C++ -*-
3////////////////////////////////////////////////////////////
4
5// FACTORY - Includes
6#include <factory.h>
7// Factor - Includes
8#include <tmpl_inst.h>
9#include <Factor.h>
10#include <SqrFree.h>
11#include <helpstuff.h>
12// Charset - Includes
13#include "csutil.h"
14#include "charset.h"
15#include "reorder.h"
16#include "algfactor.h"
17// some CC's need this:
18#include "alg_factor.h"
19
20void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
21
22#ifdef ALGFACTORDEBUG
23#  define DEBUGOUTPUT
24#else
25#  undef DEBUGOUTPUT
26#endif
27
28#include <libfac/factor/debug.h>
29
30static Varlist
31Var_is_in_AS(const Varlist & uord, const CFList & Astar);
32
33int getAlgVar(const CanonicalForm &f, Variable &X)
34{
35  if (f.inBaseDomain()) return 0;
36  if (f.inCoeffDomain())
37  {
38    if (f.level()!=0)
39    {
40      X= f.mvar();
41      return 1;
42    }
43    return getAlgVar(f.LC(),X);
44  }
45  if (f.inPolyDomain())
46  {
47    if (getAlgVar(f.LC(),X)) return 1;
48    for( CFIterator i=f; i.hasTerms(); i++)
49    {
50      if (getAlgVar(i.coeff(),X)) return 1;
51    }
52  }
53  return 0;
54}
55
56////////////////////////////////////////////////////////////////////////
57// This implements the algorithm of Trager for factorization of
58// (multivariate) polynomials over algebraic extensions and so called
59// function field extensions.
60////////////////////////////////////////////////////////////////////////
61
62// // missing class: IntGenerator:
63bool IntGenerator::hasItems() const
64{
65    return 1;
66}
67
68CanonicalForm IntGenerator::item() const
69//int IntGenerator::item() const
70{
71  //return current; //CanonicalForm( current );
72  return mapinto(CanonicalForm( current ));
73}
74
75void IntGenerator::next()
76{
77    current++;
78}
79
80static CanonicalForm
81resultante( const CanonicalForm & f, const CanonicalForm& g, const Variable & v )
82{
83  bool on_rational = isOn(SW_RATIONAL);
84  On(SW_RATIONAL);
85  CanonicalForm cd = bCommonDen( f );
86  CanonicalForm fz = f * cd;
87  cd = bCommonDen( g );
88  CanonicalForm gz = g * cd;
89  if (!on_rational)  Off(SW_RATIONAL);
90  CanonicalForm result;
91  if (getCharacteristic() == 0)
92    result= resultantZ (fz, gz,v);
93  else
94    result= resultant (fz,gz,v);
95
96  return result;
97}
98
99// sqr-free routine for algebraic extensions
100// we need it! Ex.: f=c^2+2*a*c-1; as=[a^2+1]; f=(c+a)^2
101//static CFFList alg_sqrfree( const CanonicalForm & f )
102//{
103//  CFFList L;
104//
105//  L.append(CFFactor(f,1));
106//  return L;
107//}
108
109// Calculates a square free norm
110// Input: f(x, alpha) a square free polynomial over K(alpha),
111// alpha is defined by the minimal polynomial Palpha
112// K has more than S elements (S is defined in thesis; look getextension)
113static void
114sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
115           CFGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
116           CanonicalForm & R)
117{
118  Variable y=PPalpha.mvar(),vf=f.mvar();
119  CanonicalForm temp, Palpha=PPalpha, t;
120  int sqfreetest=0;
121  CFFList testlist;
122  CFFListIterator i;
123
124  DEBOUTLN(CERR, "sqrf_norm_sub:      f= ", f);
125  DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
126  myrandom.reset();   s=myrandom.item();   g=f;
127  R= CanonicalForm(0);
128  DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s);
129
130  // Norm, resultante taken with respect to y
131  while ( !sqfreetest )
132  {
133    DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
134    R = resultante(Palpha, g, y); R= R* bCommonDen(R);
135    DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R);
136    // sqfree check ; R is a polynomial in K[x]
137    if ( getCharacteristic() == 0 )
138    {
139      temp= gcd(R, R.deriv(vf));
140      DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp);
141      if (degree(temp,vf) != 0 || temp == temp.genZero() )
142        sqfreetest= 0;
143      else
144        sqfreetest= 1;
145      DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
146    }
147    else
148    {
149      DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!");
150      // Look at SqrFreeTest!
151      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
152      // for now we use this workaround with Factorize...
153      // ...but it should go away soon!!!!
154      Variable X;
155      if (getAlgVar(R,X))
156        testlist=factorize( R, X );
157      else
158        testlist= factorize(R);
159      DEBOUTLN(CERR, "testlist= ", testlist);
160      testlist.removeFirst();
161      sqfreetest=1;
162      for ( i=testlist; i.hasItem(); i++)
163      {
164        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0)
165        {
166          sqfreetest=0;
167          break;
168        }
169      }
170      DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest);
171    }
172    if ( ! sqfreetest )
173    {
174      myrandom.next();
175      DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item());
176      if ( getCharacteristic() == 0 )
177        t= CanonicalForm(mapinto(myrandom.item()));
178      else
179        t= CanonicalForm(myrandom.item());
180      s= t;
181      DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s);
182      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
183      DEBOUTLN(CERR, "             gives g= ", g);
184    }
185  }
186}
187static void
188sqrf_agnorm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
189           AlgExtGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
190           CanonicalForm & R)
191{
192  Variable y=PPalpha.mvar(),vf=f.mvar();
193  CanonicalForm temp, Palpha=PPalpha, t;
194  int sqfreetest=0;
195  CFFList testlist;
196  CFFListIterator i;
197
198  DEBOUTLN(CERR, "sqrf_norm_sub:      f= ", f);
199  DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
200  myrandom.reset();   s=myrandom.item();   g=f;
201  R= CanonicalForm(0);
202  DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s);
203
204  // Norm, resultante taken with respect to y
205  while ( !sqfreetest )
206  {
207    DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
208    R = resultante(Palpha, g, y); R= R* bCommonDen(R);
209    DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R);
210    // sqfree check ; R is a polynomial in K[x]
211    if ( getCharacteristic() == 0 )
212    {
213      temp= gcd(R, R.deriv(vf));
214      DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp);
215      if (degree(temp,vf) != 0 || temp == temp.genZero() )
216        sqfreetest= 0;
217      else
218        sqfreetest= 1;
219      DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
220    }
221    else
222    {
223      DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!");
224      // Look at SqrFreeTest!
225      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
226      // for now we use this workaround with Factorize...
227      // ...but it should go away soon!!!!
228      Variable X;
229      if (getAlgVar(R,X))
230        testlist= factorize( R, X );
231      else
232        testlist= factorize(R);
233      DEBOUTLN(CERR, "testlist= ", testlist);
234      testlist.removeFirst();
235      sqfreetest=1;
236      for ( i=testlist; i.hasItem(); i++)
237      {
238        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0)
239        {
240          sqfreetest=0;
241          break;
242        }
243      }
244      DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest);
245    }
246    if ( ! sqfreetest )
247    {
248      myrandom.next();
249      DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item());
250      if ( getCharacteristic() == 0 )
251        t= CanonicalForm(mapinto(myrandom.item()));
252      else
253        t= CanonicalForm(myrandom.item());
254      s= t;
255      DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s);
256      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
257      DEBOUTLN(CERR, "             gives g= ", g);
258    }
259  }
260}
261
262static void
263sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha,
264           const Variable & Extension, CanonicalForm & s,  CanonicalForm & g,
265           CanonicalForm & R)
266{
267  DEBOUTLN(CERR, "sqrf_norm:      f= ", f);
268  DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha);
269  if ( getCharacteristic() == 0 )
270  {
271    IntGenerator myrandom;
272    DEBOUTMSG(CERR, "sqrf_norm: no extension, char=0");
273    sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
274    DEBOUTLN(CERR, "sqrf_norm:      f= ", f);
275    DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha);
276    DEBOUTLN(CERR, "sqrf_norm:      s= ", s);
277    DEBOUTLN(CERR, "sqrf_norm:      g= ", g);
278    DEBOUTLN(CERR, "sqrf_norm:      R= ", R);
279  }
280  else if ( degree(Extension) > 0 ) // working over Extensions
281  {
282    DEBOUTLN(CERR, "sqrf_norm: degree of extension is ", degree(Extension));
283    AlgExtGenerator myrandom(Extension);
284    sqrf_agnorm_sub(f,PPalpha, myrandom, s,g,R);
285  }
286  else
287  {
288    FFGenerator myrandom;
289    DEBOUTMSG(CERR, "sqrf_norm: degree of extension is 0");
290    sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
291  }
292}
293
294static Varlist
295Var_is_in_AS(const Varlist & uord, const CFList & Astar){
296  Varlist output;
297  CanonicalForm elem;
298  Variable x;
299
300  for ( VarlistIterator i=uord; i.hasItem(); i++)
301  {
302    x=i.getItem();
303    for ( CFListIterator j=Astar; j.hasItem(); j++ )
304    {
305      elem= j.getItem();
306      if ( degree(elem,x) > 0 ) // x actually occures in Astar
307      {
308        output.append(x);
309        break;
310      }
311    }
312  }
313  return output;
314}
315
316// Look if Minimalpolynomials in Astar define seperable Extensions
317// Must be a power of p: i.e. y^{p^e}-x
318static int
319inseperable(const CFList & Astar)
320{
321  CanonicalForm elem;
322  int Counter= 1;
323
324  if ( Astar.length() == 0 ) return 0;
325  for ( CFListIterator i=Astar; i.hasItem(); i++)
326  {
327    elem= i.getItem();
328    if ( elem.deriv() == elem.genZero() ) return Counter;
329    else Counter += 1;
330  }
331  return 0;
332}
333
334// calculate gcd of f and g in char=0
335static CanonicalForm
336gcd0( CanonicalForm f, CanonicalForm g )
337{
338  int charac= getCharacteristic();
339  int save=isOn(SW_RATIONAL);
340  setCharacteristic(0); Off(SW_RATIONAL);
341  CanonicalForm ff= mapinto(f), gg= mapinto(g);
342  CanonicalForm result= gcd(ff,gg);
343  setCharacteristic(charac);
344  if (save) On(SW_RATIONAL);
345  return mapinto(result);
346}
347
348// calculate big enough extension for finite fields
349// Idea: first calculate k, such that q^k > S (->thesis, -> getextension)
350// Second, search k with gcd(k,m_i)=1, where m_i is the degree of the i'th
351// minimal polynomial. Then the minpoly f_i remains irrd. over q^k and we
352// have enough elements to plug in.
353static int
354getextension( IntList & degreelist, int n)
355{
356  int charac= getCharacteristic();
357  setCharacteristic(0); // need it for k !
358  int k=1, m=1, length=degreelist.length();
359  IntListIterator i;
360
361  for (i=degreelist; i.hasItem(); i++) m= m*i.getItem();
362  int q=charac;
363  while (q <= ((n*m)*(n*m)/2)) { k= k+1; q= q*charac;}
364  int l=0;
365  do {
366    for (i=degreelist; i.hasItem(); i++){
367      l= l+1;
368      if ( gcd0(k,i.getItem()) == 1){
369        DEBOUTLN(CERR, "getextension: gcd == 1, l=",l);
370        if ( l==length ){ setCharacteristic(charac);  return k; }
371      }
372      else { DEBOUTMSG(CERR, "getextension: Next iteration"); break; }
373    }
374    k= k+1; l=0;
375  }
376  while ( 1 );
377}
378
379
380/// pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
381/// but only if the leading coefficient of g is of level lower than coeffLevel
382void
383psqr (const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q,
384      CanonicalForm & r, CanonicalForm& multiplier, const Variable& x,
385      int coeffLevel)
386{
387  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
388  ASSERT( ! g.isZero(), "math error: division by zero" );
389
390  // swap variables such that x's level is larger or equal
391  // than both f's and g's levels.
392  Variable X;
393  if (f.level() > g.level())
394    X= f.mvar();
395  else
396    X= g.mvar();
397  if (X.level() < x.level())
398    X= x;
399  CanonicalForm F= swapvar (f, x, X);
400  CanonicalForm G= swapvar (g, x, X);
401
402  // now, we have to calculate the pseudo remainder of F and G
403  // w.r.t. X
404  int fDegree= degree (F, X);
405  int gDegree= degree (G, X);
406  if (fDegree < 0 || fDegree < gDegree)
407  {
408    q= 0;
409    r= f;
410  }
411  else
412  {
413    CanonicalForm LCG= LC (G, X);
414    if (LCG.level() < coeffLevel)
415    {
416      multiplier= power (LCG, fDegree - gDegree + 1);
417      divrem (multiplier*F, G, q, r);
418      q= swapvar (q, x, X);
419      r= swapvar (r, x, X);
420    }
421    else
422    {
423      q= 0;
424      r= f;
425    }
426  }
427}
428
429/// pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
430void
431psqr (const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, 
432      CanonicalForm & r, CanonicalForm& multiplier, const Variable& x)
433{
434    ASSERT( x.level() > 0, "type error: polynomial variable expected" );
435    ASSERT( ! g.isZero(), "math error: division by zero" );
436
437    // swap variables such that x's level is larger or equal
438    // than both f's and g's levels.
439    Variable X;
440    if (f.level() > g.level())
441      X= f.mvar();
442    else
443      X= g.mvar();
444    if (X.level() < x.level())
445      X= x;
446    CanonicalForm F= swapvar (f, x, X);
447    CanonicalForm G= swapvar (g, x, X);
448
449    // now, we have to calculate the pseudo remainder of F and G
450    // w.r.t. X
451    int fDegree= degree (F, X);
452    int gDegree= degree (G, X);
453    if (fDegree < 0 || fDegree < gDegree)
454    {
455      q= 0;
456      r= f;
457    }
458    else
459    {
460      CanonicalForm LCG= LC (G, X);
461      multiplier= power (LCG, fDegree - gDegree + 1);
462      divrem (multiplier*F, G, q, r);
463      q= swapvar (q, x, X);
464      r= swapvar (r, x, X);
465    }
466}
467
468CanonicalForm
469QuasiInverse (const CanonicalForm& f, const CanonicalForm& g,
470      CanonicalForm& numt, const Variable& x)
471{
472  CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
473  bool isRat= isOn (SW_RATIONAL);
474  CanonicalForm m,tmp;
475  if (isRat)
476    Off (SW_RATIONAL);
477  pi= f/content (f,x);
478  pi1= g/content (g,x);
479
480  t0= 0;
481  t1= 1;
482  bi= 1;
483
484  On (SW_RATIONAL);
485
486  int delta= degree (f, x) - degree (g, x);
487  Hi= power (LC (pi1, x), delta);
488  if ( (delta+1) % 2 )
489      bi = 1;
490  else
491      bi = -1;
492
493  while (degree (pi1,x) > 0)
494  {
495    On (SW_RATIONAL);
496    psqr( pi, pi1, q, pi2, m, x);
497    pi2 /= bi;
498
499    tmp= t1;
500    t1= t0*m - t1*q;
501    t0= tmp;
502    t1 /= bi;
503    pi = pi1; pi1 = pi2;
504    if ( degree ( pi1, x ) > 0 )
505    {
506      delta = degree( pi, x ) - degree( pi1, x );
507      if ( (delta+1) % 2 )
508        bi = LC( pi, x ) * power( Hi, delta );
509      else
510        bi = -LC( pi, x ) * power( Hi, delta );
511      Hi = power( LC( pi1, x ), delta ) / power( Hi, delta-1 );
512    }
513  }
514  t1 /= gcd (pi1, t1);
515  if (!isRat)
516    Off (SW_RATIONAL);
517  numt= t1;
518  return pi;
519}
520
521CanonicalForm
522evaluate (const CanonicalForm& f, const CanonicalForm& g, const CanonicalForm& h, const CanonicalForm& powH)
523{
524  if (f.inCoeffDomain())
525    return f;
526  CFIterator i= f;
527  int lastExp = i.exp();
528  CanonicalForm result = i.coeff()*powH;
529  i++;
530  while (i.hasTerms())
531  {
532    int i_exp= i.exp();
533    if ((lastExp - i_exp) == 1)
534    {
535      result *= g;
536      result /= h;
537    }
538    else
539    {
540      result *= power (g, lastExp - i_exp);
541      result /= power (h, lastExp - i_exp);
542    }
543    result += i.coeff()*powH;
544    lastExp = i_exp;
545    i++;
546  }
547  if (lastExp != 0)
548  {
549    result *= power (g, lastExp);
550    result /= power (h, lastExp);
551  }
552  return result;
553}
554
555
556/// evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)
557CanonicalForm
558evaluate (const CanonicalForm& f, const CanonicalForm& g,
559          const CanonicalForm& h, const CanonicalForm& powH,
560          const Variable& v)
561{
562  if (f.inCoeffDomain())
563  {
564    return f*powH;
565  }
566
567  Variable x = f.mvar();
568  if ( v > x )
569    return f*powH;
570  else  if ( v == x )
571    return evaluate (f, g, h, powH);
572
573  // v is less than main variable of f
574  CanonicalForm result= 0;
575  for (CFIterator i= f; i.hasTerms(); i++)
576    result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
577  return result;
578}
579
580// calculate a "primitive element"
581// K must have more than S elements (->thesis, -> getextension)
582static CFList
583simpleextension(const CFList & Astar, const Variable & Extension, bool& isFunctionField,
584                CanonicalForm & R)
585{
586  CFList Returnlist, Bstar=Astar;
587  CanonicalForm s, g, ra, rb, oldR, h, denra, denrb=1;
588  Variable alpha;
589  CFList tmp;
590
591  bool isRat= isOn (SW_RATIONAL);
592
593  DEBOUTLN(CERR, "simpleextension: Astar= ", Astar);
594  DEBOUTLN(CERR, "simpleextension:     R= ", R);
595  DEBOUTLN(CERR, "simpleextension: Extension= ", Extension);
596  CFListIterator j;
597  if (Astar.length() == 1)
598  {
599    R= Astar.getFirst();
600    rb= R.mvar();
601  }
602  else
603  {
604    R=Bstar.getFirst();
605    Bstar.removeFirst();
606    for (CFListIterator i=Bstar; i.hasItem(); i++)
607    {
608      j= i;
609      j++;
610      Off (SW_RATIONAL);
611      R /= icontent (R);
612      On (SW_RATIONAL);
613      oldR= R;
614      sqrf_norm (i.getItem(), R, Extension, s, g, R);
615
616      Off (SW_RATIONAL);
617      R /= icontent (R);
618
619      On (SW_RATIONAL);
620
621      if (!isFunctionField)
622      {
623        alpha= rootOf (R);
624        h= replacevar (g, g.mvar(), alpha);
625        On (SW_RATIONAL); //needed for GCD
626        h= gcd (h, oldR);
627        h /= Lc (h);
628        ra= -h[0];
629        ra= replacevar(ra, alpha, g.mvar());
630        rb= R.mvar()-s*ra;
631        for (; j.hasItem(); j++)
632        {
633          j.getItem()= j.getItem() (ra, oldR.mvar());
634          j.getItem()= j.getItem() (rb, i.getItem().mvar());
635        }
636      }
637      else
638      {
639        On (SW_RATIONAL);
640        h= swapvar (g, g.mvar(), oldR.mvar());
641        tmp= CFList (swapvar (R, g.mvar(), oldR.mvar()));
642        h= alg_gcd (h, swapvar (oldR, g.mvar(), oldR.mvar()), tmp);
643        CanonicalForm hh= replacevar (h, oldR.mvar(), alpha);
644
645        CanonicalForm numt, dent;
646        QuasiInverse (tmp.getFirst(), LC (h), numt, tmp.getFirst().mvar());
647
648        Off (SW_RATIONAL);
649        h *= numt;
650        h= reduce (h, tmp.getFirst());
651        dent= LC(h);
652
653        ra= -h[0];
654        denra= gcd (ra, dent);
655        ra /= denra;
656        denra= dent/denra;
657        denra= replacevar (denra, ra.mvar(), g.mvar());
658        ra= replacevar(ra, ra.mvar(), g.mvar());
659        rb= R.mvar()*denra-s*ra;
660        denrb= denra;
661        for (; j.hasItem(); j++)
662        {
663          CanonicalForm powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
664          j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
665          powdenra= power (denra, degree (j.getItem(), i.getItem().mvar()));
666          j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra, i.getItem().mvar());
667        }
668      }
669
670      DEBOUTLN(CERR, "simpleextension: g= ", g);
671      DEBOUTLN(CERR, "simpleextension: s= ", s);
672      DEBOUTLN(CERR, "simpleextension: R= ", R);
673      Returnlist.append (ra);
674      if (isFunctionField)
675        Returnlist.append (denra);
676    }
677  }
678  Returnlist.append (rb);
679  if (isFunctionField)
680    Returnlist.append (denrb);
681
682  if (isRat)
683    On (SW_RATIONAL);
684  else
685    Off (SW_RATIONAL);
686
687  return Returnlist;
688}
689
690CanonicalForm alg_lc(const CanonicalForm &f)
691{
692  if (f.level()>0)
693  {
694    return alg_lc(f.LC());
695  }
696  //assert(f.inCoeffDomain());
697  return f;
698}
699
700CanonicalForm
701subst (const CanonicalForm& f, const CFList& a, const CFList& b,
702       const CanonicalForm& Rstar, bool isFunctionField)
703{
704  if (isFunctionField)
705    ASSERT (2*a.length() == b.length(), "wrong length of lists");
706  else
707    ASSERT (a.length() == b.length(), "lists of equal length expected");
708  CFListIterator j= b;
709  CanonicalForm result= f, tmp, powj;
710  for (CFListIterator i= a; i.hasItem() && j.hasItem(); i++, j++)
711  {
712    if (!isFunctionField)
713      result= result (j.getItem(), i.getItem().mvar());
714    else
715    {
716      tmp= j.getItem();
717      j++;
718      powj= power (j.getItem(), degree (result, i.getItem().mvar()));
719      result= evaluate (result, tmp, j.getItem(), powj, i.getItem().mvar());
720
721      if (fdivides (powj, result, tmp))
722        result= tmp;
723
724      result /= vcontent (result, Variable (i.getItem().level() + 1));
725    }
726  }
727  result= reduce (result, Rstar);
728  result /= vcontent (result, Variable (Rstar.level() + 1));
729  return result;
730}
731
732// the heart of the algorithm: the one from Trager
733#ifndef DEBUGOUTPUT
734static CFFList
735alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist /*& oldord*/, const CFList & as)
736#else
737static CFFList
738alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as)
739#endif
740{
741  CFFList L, Factorlist;
742  CanonicalForm R, Rstar, s, g, h;
743  CFList substlist;
744
745  DEBINCLEVEL(CERR,"alg_factor");
746  DEBOUTLN(CERR, "alg_factor: f= ", f);
747
748  //out_cf("start alg_factor:",f,"\n");
749  substlist= simpleextension(Astar, vminpoly, Rstar);
750  DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
751  DEBOUTLN(CERR, "alg_factor: minpoly Rstar= ", Rstar);
752  DEBOUTLN(CERR, "alg_factor: vminpoly= ", vminpoly);
753
754  sqrf_norm(f, Rstar, vminpoly, s, g, R );
755  //out_cf("sqrf_norm R:",R,"\n");
756  //out_cf("sqrf_norm s:",s,"\n");
757  //out_cf("sqrf_norm g:",g,"\n");
758  DEBOUTLN(CERR, "alg_factor: g= ", g);
759  DEBOUTLN(CERR, "alg_factor: s= ", s);
760  DEBOUTLN(CERR, "alg_factor: R= ", R);
761  Off(SW_RATIONAL);
762  Variable X;
763  if (getAlgVar(R,X))
764  {
765    // factorize R over alg.extension with X
766//CERR << "alg: "<< X << " mipo=" << getMipo(X,Variable('X')) <<"\n";
767    if (R.isUnivariate())
768    {
769      DEBOUTLN(CERR, "alg_factor: factorize( ", R);
770      Factorlist =  factorize( R, X );
771    }
772    else
773    {
774      #if 1
775      Variable XX;
776      CanonicalForm mipo=getMipo(X,XX);
777      CFList as(mipo);
778      DEBOUTLN(CERR, "alg_factor: newfactoras( ", R);
779      int success=1;
780      Factorlist = newfactoras(R, as , success);
781      #else
782      // factor R over k
783      DEBOUTLN(CERR, "alg_factor: Factorize( ", R);
784      Factorlist = Factorize(R);
785      #endif
786    }
787  }
788  else
789  {
790    // factor R over k
791    DEBOUTLN(CERR, "alg_factor: Factorize( ", R);
792    Factorlist = Factorize(R);
793  }
794  On(SW_RATIONAL);
795  DEBOUTLN(CERR, "alg_factor: Factorize(R)= ", Factorlist);
796  if ( !Factorlist.getFirst().factor().inCoeffDomain() )
797    Factorlist.insert(CFFactor(1,1));
798  if ( Factorlist.length() == 2 && Factorlist.getLast().exp()== 1)
799  { // irreduzibel (first entry is a constant)
800    L.append(CFFactor(f,1));
801  }
802  else
803  {
804    DEBOUTLN(CERR, "alg_factor: g= ", g);
805    CanonicalForm gnew= g(s,s.mvar());
806    DEBOUTLN(CERR, "alg_factor: gnew= ", gnew);
807    g=gnew;
808    for ( CFFListIterator i=Factorlist; i.hasItem(); i++)
809    {
810      CanonicalForm fnew=i.getItem().factor();
811      fnew= fnew(s,s.mvar());
812      DEBOUTLN(CERR, "alg_factor: fnew= ", fnew);
813      DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
814      for ( CFListIterator ii=substlist; ii.hasItem(); ii++){
815        DEBOUTLN(CERR, "alg_factor: item= ", ii.getItem());
816        fnew= fnew(ii.getItem(), ii.getItem().mvar());
817        DEBOUTLN(CERR, "alg_factor: fnew= ", fnew);
818      }
819      if (degree(i.getItem().factor()) > 0 )
820      {
821          h=alg_gcd(g,fnew,as);
822        DEBOUTLN(CERR, "  alg_factor: h= ", h);
823        DEBOUTLN(CERR, "  alg_factor: oldord= ", oldord);
824        if ( degree(h) > 0 )
825        { //otherwise it's a constant
826          g= divide(g, h,as);
827          DEBOUTLN(CERR, "alg_factor: g/h= ", g);
828          DEBOUTLN(CERR, "alg_factor: s= ", s);
829          DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
830          //out_cf("new g:",g,"\n");
831          L.append(CFFactor(h,1));
832        }
833        //else printf("degree <=1\n");
834      }
835    }
836    // we are not interested in a
837    // constant (over K_r, which can be a polynomial!)
838    if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); }
839  }
840  CFFList LL;
841  if (getCharacteristic()>0)
842  {
843    CFFListIterator i=L;
844    CanonicalForm c_fac=1;
845    CanonicalForm c;
846    for(;i.hasItem(); i++ )
847    {
848      CanonicalForm ff=i.getItem().factor();
849      c=alg_lc(ff);
850      int e=i.getItem().exp();
851      ff/=c;
852      if (!ff.isOne()) LL.append(CFFactor(ff,e));
853      while (e>0) { c_fac*=c;e--; }
854    }
855    if (!c_fac.isOne()) LL.insert(CFFactor(c_fac,1));
856  }
857  else
858  {
859    LL=L;
860  }
861  //CFFListIterator i=LL;
862  //for(;i.hasItem(); i++ )
863  //  out_cf("end alg_f:",i.getItem().factor(),"\n");
864  //printf("end alg_factor\n");
865  DEBOUTLN(CERR, "alg_factor: L= ", LL);
866  DEBDECLEVEL(CERR,"alg_factor");
867  return LL;
868}
869
870static CFFList
871endler( const CanonicalForm & f, const CFList & AS, const Varlist & uord )
872{
873  CanonicalForm F=f, g, q,r;
874  CFFList Output;
875  CFList One, Two, asnew, as=AS;
876  CFListIterator i,ii;
877  VarlistIterator j;
878  Variable vg;
879
880  for (i=as; i.hasItem(); i++)
881  {
882    g= i.getItem();
883    if (g.deriv() == 0 )
884    {
885      DEBOUTLN(CERR, "Inseperable extension detected: ", g);
886      for (j=uord; j.hasItem(); j++)
887      {
888        if ( degree(g,j.getItem()) > 0 ) vg= j.getItem();
889      }
890      // Now we have the highest transzendental in vg;
891      DEBOUTLN(CERR, "Transzendental is ", vg);
892      CanonicalForm gg=-1*g[0];
893      divrem(gg,vg,q,r); r= gg-q*vg;   gg= gg-r;
894      //DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
895      DEBOUTLN(CERR, "  that is ", gg);
896      DEBOUTLN(CERR, "  maps to ", g+gg);
897      One.insert(gg); Two.insert(g+gg);
898      // Now transform all remaining polys in as:
899      int x=0;
900      for (ii=i; ii.hasItem(); ii++)
901      {
902        if ( x != 0 )
903        {
904          divrem(ii.getItem(), gg, q,r);
905//          CERR << ii.getItem() << " divided by " << gg << "\n";
906          DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
907          ii.append(ii.getItem()+q*g); ii.remove(1);
908          DEBOUTLN(CERR, "as= ", as);
909        }
910        x+= 1;
911      }
912      // Now transform F:
913      divrem(F, gg, q,r);
914      F= F+q*g;
915      DEBOUTLN(CERR, "new F= ", F);
916    }
917    else{ asnew.append(i.getItem());  }// just the identity
918  }
919  // factor F with minimal polys given in asnew:
920  DEBOUTLN(CERR, "Factor F=  ", F);
921  DEBOUTLN(CERR, "  with as= ", asnew);
922  int success=0;
923  CFFList factorlist= newcfactor(F,asnew, success);
924  DEBOUTLN(CERR, "  gives =  ", factorlist);
925  DEBOUTLN(CERR, "One= ", One);
926  DEBOUTLN(CERR, "Two= ", Two);
927
928  // Transform back:
929  for ( CFFListIterator k=factorlist; k.hasItem(); k++)
930  {
931    CanonicalForm factor= k.getItem().factor();
932    ii=One;
933    for (i=Two; i.hasItem(); i++)
934    {
935      DEBOUTLN(CERR, "Mapping ", i.getItem());
936      DEBOUTLN(CERR, "     to ", ii.getItem());
937      DEBOUTLN(CERR, "     in ", factor);
938      divrem(factor,i.getItem(),q,r); r=factor -q*i.getItem();
939      DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
940      factor= ii.getItem()*q +r; //
941      ii++;
942    }
943    Output.append(CFFactor(factor,k.getItem().exp()));
944  }
945
946  return Output;
947}
948
949void
950multiplicity (CFFList& factors, const CanonicalForm& F, const CFList& as)
951{
952  CanonicalForm G= F;
953  Variable x= F.mvar();
954  CanonicalForm q, r;
955  int count= -1;
956  On (SW_RATIONAL);
957  for (CFFListIterator iter=factors; iter.hasItem(); iter++)
958  {
959    count= -1;
960    if (iter.getItem().factor().inCoeffDomain())
961      continue;
962    while (1)
963    {
964      psqr (G, iter.getItem().factor(), q, r, x);
965
966      q= Prem (q, as);
967      r= Prem (r, as);
968      if (!r.isZero())
969        break;
970      On (SW_RATIONAL);
971      count++;
972      G= q;
973    }
974    iter.getItem()= CFFactor (iter.getItem().factor(), iter.getItem().exp()+count);
975  }
976}
977
978
979// 1) prepares data
980// 2) for char=p we distinguish 3 cases:
981//           no transcendentals, seperable and inseperable extensions
982CFFList
983newfactoras( const CanonicalForm & f, const CFList & as, int &success)
984{
985  Variable vf=f.mvar();
986  CFListIterator i;
987  CFFListIterator jj;
988  CFList reduceresult;
989  CFFList result;
990
991  success=1;
992  DEBINCLEVEL(CERR, "newfactoras");
993  DEBOUTLN(CERR, "newfactoras called with f= ", f);
994  DEBOUTLN(CERR, "               content(f)= ", content(f));
995  DEBOUTLN(CERR, "                       as= ", as);
996  DEBOUTLN(CERR, "newfactoras: cls(vf)= ", cls(vf));
997  DEBOUTLN(CERR, "newfactoras: cls(as.getLast())= ", cls(as.getLast()));
998  DEBOUTLN(CERR, "newfactoras: degree(f,vf)= ", degree(f,vf));
999
1000// F1: [Test trivial cases]
1001// 1) first trivial cases:
1002  if ( (cls(vf) <= cls(as.getLast())) ||  degree(f,vf)<=1 ){
1003// ||( (as.length()==1) && (degree(f,vf)==3) && (degree(as.getFirst()==2)) )
1004    DEBDECLEVEL(CERR,"newfactoras");
1005    return CFFList(CFFactor(f,1));
1006  }
1007
1008// 2) List of variables:
1009// 2a) Setup list of those polys in AS having degree(AS[i], AS[i].mvar()) > 1
1010// 2b) Setup variableordering
1011  CFList Astar;
1012  Variable x;
1013  CanonicalForm elem;
1014  Varlist ord, uord,oldord;
1015  for ( int ii=1; ii< level(vf) ; ii++ ) { uord.append(Variable(ii));  }
1016  oldord= uord; oldord.append(vf);
1017
1018  for ( i=as; i.hasItem(); i++ ){
1019    elem= i.getItem();
1020    x= elem.mvar();
1021    if ( degree(elem,x) > 1){ // otherwise it's not an extension
1022      Astar.append(elem);
1023      ord.append(x);
1024    }
1025  }
1026  uord= Difference(uord,ord);
1027  DEBOUTLN(CERR, "Astar is: ", Astar);
1028  DEBOUTLN(CERR, "ord is: ", ord);
1029  DEBOUTLN(CERR, "uord is: ", uord);
1030
1031// 3) second trivial cases: we already prooved irr. of f over no extensions
1032  if ( Astar.length() == 0 ){
1033    DEBDECLEVEL(CERR,"newfactoras");
1034    return CFFList(CFFactor(f,1));
1035  }
1036
1037// 4) Try to obtain a partial factorization using prop2 and prop3
1038//    Use with caution! We have to proof these propositions first!
1039  // Not yet implemented
1040
1041// 5) Look if elements in uord actually occure in any of the minimal
1042//    polynomials. If no element of uord occures in any of the minimal
1043//   polynomials, we don't have transzendentals.
1044  Varlist newuord=Var_is_in_AS(uord,Astar);
1045  DEBOUTLN(CERR, "newuord is: ", newuord);
1046
1047  CFFList Factorlist;
1048  Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar());
1049  // This is for now. we need alg_sqrfree implemented!
1050  CanonicalForm Fgcd;
1051          Fgcd= alg_gcd(f,f.deriv(),Astar);
1052  if ( Fgcd == 0 ) {DEBOUTMSG(CERR, "WARNING: p'th root ?");}
1053  if (( degree(Fgcd, f.mvar()) > 0) && (!(f.deriv().isZero())) ){
1054    DEBOUTLN(CERR, "Nontrivial GCD found of ", f);
1055    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
1056    DEBOUTLN(CERR, "  split into ", Fgcd);
1057    DEBOUTLN(CERR, "         and ", Ggcd);
1058    Fgcd= pp(Fgcd); Ggcd= pp(Ggcd);
1059    DEBDECLEVEL(CERR,"newfactoras");
1060    return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success));
1061  }
1062  if ( getCharacteristic() > 0 ){
1063
1064    // First look for extension!
1065    IntList degreelist;
1066    Variable vminpoly;
1067    for (i=Astar; i.hasItem(); i++){degreelist.append(degree(i.getItem()));}
1068    int extdeg= getextension(degreelist, degree(f));
1069    DEBOUTLN(CERR, "Extension needed of degree ", extdeg);
1070
1071    // Now the real stuff!
1072    if ( newuord.length() == 0 ){ // no transzendentals
1073      DEBOUTMSG(CERR, "No transzendentals!");
1074      if ( extdeg > 1 ){
1075        CanonicalForm MIPO= generate_mipo( extdeg, vminpoly);
1076        DEBOUTLN(CERR, "Minpoly produced ", MIPO);
1077        vminpoly= rootOf(MIPO);
1078      }
1079      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
1080      DEBDECLEVEL(CERR,"newfactoras");
1081      return Factorlist;
1082    }
1083    else if ( inseperable(Astar) > 0 ){ // Look if extensions are seperable
1084      // a) Use Endler
1085      DEBOUTMSG(CERR, "Inseperable extensions! Using Endler!");
1086      CFFList templist= endler(f,Astar, newuord);
1087      DEBOUTLN(CERR, "Endler gives: ", templist);
1088      return templist;
1089    }
1090    else{ // we are on the save side: Use trager
1091      DEBOUTMSG(CERR, "Only seperable extensions!");
1092      if (extdeg > 1 ){
1093        CanonicalForm MIPO=generate_mipo(extdeg, vminpoly );
1094        vminpoly= rootOf(MIPO);
1095        DEBOUTLN(CERR, "Minpoly generated: ", MIPO);
1096        DEBOUTLN(CERR, "vminpoly= ", vminpoly);
1097        DEBOUTLN(CERR, "degree(vminpoly)= ", degree(vminpoly));
1098      }
1099      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
1100      DEBDECLEVEL(CERR,"newfactoras");
1101      return Factorlist;
1102    }
1103  }
1104  else{ // char=0 apply trager directly
1105    DEBOUTMSG(CERR, "Char=0! Apply Trager!");
1106    Variable vminpoly;
1107    Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
1108      DEBDECLEVEL(CERR,"newfactoras");
1109      return Factorlist;
1110  }
1111
1112  DEBDECLEVEL(CERR,"newfactoras");
1113  return CFFList(CFFactor(f,1));
1114}
1115
1116CFFList
1117newcfactor(const CanonicalForm & f, const CFList & as, int & success )
1118{
1119  Off(SW_RATIONAL);
1120  CFFList Output, output, Factors=Factorize(f);
1121  On(SW_RATIONAL);
1122  Factors.removeFirst();
1123
1124  if ( as.length() == 0 ){ success=1; return Factors;}
1125  if ( cls(f) <= cls(as.getLast()) ) { success=1; return Factors;}
1126
1127  success=1;
1128  for ( CFFListIterator i=Factors; i.hasItem(); i++ )
1129  {
1130    output=newfactoras(i.getItem().factor(),as, success);
1131    for ( CFFListIterator j=output; j.hasItem(); j++)
1132      Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp()));
1133  }
1134  return Output;
1135}
Note: See TracBrowser for help on using the repository browser.