source: git/libfac/charset/alg_factor.cc @ 91b36d

fieker-DuValspielwiese
Last change on this file since 91b36d was 91b36d, checked in by Hans Schönemann <hannes@…>, 16 years ago
*hannes: licence stuff git-svn-id: file:///usr/local/Singular/svn/trunk@10750 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 27.9 KB
Line 
1////////////////////////////////////////////////////////////
2// emacs edit mode for this file is -*- C++ -*-
3////////////////////////////////////////////////////////////
4/* $Id: alg_factor.cc,v 1.24 2008-06-10 14:49:14 Singular Exp $ */
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 "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  CanonicalForm h, beta, help, F, G;
121  int delta;
122
123  DEBOUTLN( CERR, "resultante: called  f= ", f);
124  DEBOUTLN( CERR, "resultante: called  g= ", g);
125  DEBOUTLN( CERR, "resultante: called  v= ", v);
126  if ( f.mvar() < v || g.mvar() < v ){
127    DEBOUTMSG(CERR, "resultante: f.mvar() < v || g.mvar() < v");
128    return 1;
129  }
130
131  if ( f.degree( v ) < 1 || g.degree( v ) < 1 ){
132    DEBOUTMSG(CERR, "resultante: f.degree( v ) < 1 || g.degree( v ) < 1");
133    // If deg(F,v) == 0 , then resultante(F,G,v) = F^n, where n=deg(G,v)
134    if ( f.degree( v ) < 1 ) return power(f,degree(g,v));
135    else return power(g,degree(f,v));
136  }
137
138   if ( f.degree( v ) >= g.degree( v ) ) { F = f; G = g; }
139   else { G = f; F = g; }
140
141  h = CanonicalForm(1);
142  while ( G != G.genZero() ) {
143     delta= degree(F,v) -degree(G,v);
144     beta = power(CanonicalForm(-1), delta+1) * LC(F,v)* power(h, delta);
145     h= (h * power(LC(G,v), delta)) / power(h, delta);
146     help= G;
147     G= mypsr(F,G,v);
148     G= G/beta;
149     F=help;
150   }
151   if ( degree(F,v) != 0 ) F= CanonicalForm(0);
152   return F;
153}
154
155// sqr-free routine for algebraic extensions
156// we need it! Ex.: f=c^2+2*a*c-1; as=[a^2+1]; f=(c+a)^2
157static CFFList
158alg_sqrfree( const CanonicalForm & f ){
159  CFFList L;
160
161  L.append(CFFactor(f,1));
162  return L;
163}
164
165// Calculates a square free norm
166// Input: f(x, alpha) a square free polynomial over K(alpha),
167// alpha is defined by the minimal polynomial Palpha
168// K has more than S elements (S is defined in thesis; look getextension)
169static void
170sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
171           CFGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
172           CanonicalForm & R){
173  Variable y=PPalpha.mvar(),vf=f.mvar();
174  CanonicalForm temp, Palpha=PPalpha, t;
175  int sqfreetest=0;
176  CFFList testlist;
177  CFFListIterator i;
178
179  DEBOUTLN(CERR, "sqrf_norm_sub:      f= ", f);
180  DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
181  myrandom.reset();   s=f.mvar()-myrandom.item()*Palpha.mvar();   g=f;
182  R= CanonicalForm(0);
183  DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s);
184
185  // Norm, resultante taken with respect to y
186  while ( !sqfreetest ){
187    DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
188    R = resultante(Palpha, g, y); R= R* bCommonDen(R);
189    DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R);
190    // sqfree check ; R is a polynomial in K[x]
191    if ( getCharacteristic() == 0 )
192    {
193      temp= gcd(R, R.deriv(vf));
194      DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp);
195      if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; }
196      else { sqfreetest= 1; }
197      DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
198    }
199    else{
200      DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!");
201      // Look at SqrFreeTest!
202      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
203      // for now we use this workaround with Factorize...
204      // ...but it should go away soon!!!!
205      Variable X;
206      if (getAlgVar(R,X))
207      {
208        if (R.isUnivariate())
209          testlist=factorize( R, X );
210        else
211          testlist= Factorize(R, X, 0);
212      }
213      else
214        testlist= Factorize(R);
215      DEBOUTLN(CERR, "testlist= ", testlist);
216      testlist.removeFirst();
217      sqfreetest=1;
218      for ( i=testlist; i.hasItem(); i++)
219        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; }
220      DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest);
221    }
222    if ( ! sqfreetest ){
223      myrandom.next();
224      DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item());
225      if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(myrandom.item()));
226      else t= CanonicalForm(myrandom.item());
227      s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution
228      DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s);
229      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
230      DEBOUTLN(CERR, "             gives g= ", g);
231    }
232  }
233}
234static void
235sqrf_agnorm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
236           AlgExtGenerator & myrandom, CanonicalForm & s,  CanonicalForm & g,
237           CanonicalForm & R){
238  Variable y=PPalpha.mvar(),vf=f.mvar();
239  CanonicalForm temp, Palpha=PPalpha, t;
240  int sqfreetest=0;
241  CFFList testlist;
242  CFFListIterator i;
243
244  DEBOUTLN(CERR, "sqrf_norm_sub:      f= ", f);
245  DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
246  myrandom.reset();   s=f.mvar()-myrandom.item()*Palpha.mvar();   g=f;
247  R= CanonicalForm(0);
248  DEBOUTLN(CERR, "sqrf_norm_sub: myrandom s= ", s);
249
250  // Norm, resultante taken with respect to y
251  while ( !sqfreetest ){
252    DEBOUTLN(CERR, "sqrf_norm_sub: Palpha= ", Palpha);
253    R = resultante(Palpha, g, y); R= R* bCommonDen(R);
254    DEBOUTLN(CERR, "sqrf_norm_sub: R= ", R);
255    // sqfree check ; R is a polynomial in K[x]
256    if ( getCharacteristic() == 0 )
257    {
258      temp= gcd(R, R.deriv(vf));
259      DEBOUTLN(CERR, "sqrf_norm_sub: temp= ", temp);
260      if (degree(temp,vf) != 0 || temp == temp.genZero() ){ sqfreetest= 0; }
261      else { sqfreetest= 1; }
262      DEBOUTLN(CERR, "sqrf_norm_sub: sqfreetest= ", sqfreetest);
263    }
264    else{
265      DEBOUTMSG(CERR, "Starting SqrFreeTest(R)!");
266      // Look at SqrFreeTest!
267      // (z+a^5+w)^4 with z<w<a should not give sqfreetest=1 !
268      // for now we use this workaround with Factorize...
269      // ...but it should go away soon!!!!
270      Variable X;
271      if (getAlgVar(R,X))
272      {
273        if (R.isUnivariate())
274          testlist=factorize( R, X );
275        else
276          testlist= Factorize(R, X, 0);
277      }
278      else
279        testlist= Factorize(R);
280      DEBOUTLN(CERR, "testlist= ", testlist);
281      testlist.removeFirst();
282      sqfreetest=1;
283      for ( i=testlist; i.hasItem(); i++)
284        if ( i.getItem().exp() > 1 && degree(i.getItem().factor(), R.mvar()) > 0) { sqfreetest=0; break; }
285      DEBOUTLN(CERR, "SqrFreeTest(R)= ", sqfreetest);
286    }
287    if ( ! sqfreetest ){
288      myrandom.next();
289      DEBOUTLN(CERR, "sqrf_norm_sub generated new myrandom item: ", myrandom.item());
290      if ( getCharacteristic() == 0 ) t= CanonicalForm(mapinto(myrandom.item()));
291      else t= CanonicalForm(myrandom.item());
292      s= f.mvar()+t*Palpha.mvar(); // s defines backsubstitution
293      DEBOUTLN(CERR, "sqrf_norm_sub: testing s= ", s);
294      g= f(f.mvar()-t*Palpha.mvar(), f.mvar());
295      DEBOUTLN(CERR, "             gives g= ", g);
296    }
297  }
298}
299
300static void
301sqrf_norm( const CanonicalForm & f, const CanonicalForm & PPalpha,
302           const Variable & Extension, CanonicalForm & s,  CanonicalForm & g,
303           CanonicalForm & R){
304
305  DEBOUTLN(CERR, "sqrf_norm:      f= ", f);
306  DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha);
307  if ( getCharacteristic() == 0 ) {
308    IntGenerator myrandom;
309    DEBOUTMSG(CERR, "sqrf_norm: no extension, char=0");
310    sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
311    DEBOUTLN(CERR, "sqrf_norm:      f= ", f);
312    DEBOUTLN(CERR, "sqrf_norm: Palpha= ", PPalpha);
313    DEBOUTLN(CERR, "sqrf_norm:      s= ", s);
314    DEBOUTLN(CERR, "sqrf_norm:      g= ", g);
315    DEBOUTLN(CERR, "sqrf_norm:      R= ", R);
316  }
317  else if ( degree(Extension) > 0 ){ // working over Extensions
318    DEBOUTLN(CERR, "sqrf_norm: degree of extension is ", degree(Extension));
319    AlgExtGenerator myrandom(Extension);
320    sqrf_agnorm_sub(f,PPalpha, myrandom, s,g,R);
321  }
322  else{
323    FFGenerator myrandom;
324    DEBOUTMSG(CERR, "sqrf_norm: degree of extension is 0");
325    sqrf_norm_sub(f,PPalpha, myrandom, s,g,R);
326  }
327}
328
329static Varlist
330Var_is_in_AS(const Varlist & uord, const CFList & Astar){
331  Varlist output;
332  CanonicalForm elem;
333  Variable x;
334
335  for ( VarlistIterator i=uord; i.hasItem(); i++){
336    x=i.getItem();
337    for ( CFListIterator j=Astar; j.hasItem(); j++ ){
338      elem= j.getItem();
339      if ( degree(elem,x) > 0 ){ // x actually occures in Astar
340        output.append(x);
341        break;
342      }
343    }
344  }
345  return output;
346}
347
348// Look if Minimalpolynomials in Astar define seperable Extensions
349// Must be a power of p: i.e. y^{p^e}-x
350static int
351inseperable(const CFList & Astar){
352  CanonicalForm elem;
353  int Counter= 1;
354
355  if ( Astar.length() == 0 ) return 0;
356  for ( CFListIterator i=Astar; i.hasItem(); i++){
357    elem= i.getItem();
358    if ( elem.deriv() == elem.genZero() ) return Counter;
359    else Counter += 1;
360  }
361  return 0;
362}
363
364// calculate gcd of f and g in char=0
365static CanonicalForm
366gcd0( CanonicalForm f, CanonicalForm g ){
367  int charac= getCharacteristic();
368  int save=isOn(SW_RATIONAL);
369  setCharacteristic(0); Off(SW_RATIONAL);
370  CanonicalForm ff= mapinto(f), gg= mapinto(g);
371  CanonicalForm result= gcd(ff,gg);
372  setCharacteristic(charac); 
373  if (save) On(SW_RATIONAL);
374  return mapinto(result);
375}
376
377// calculate big enough extension for finite fields
378// Idea: first calculate k, such that q^k > S (->thesis, -> getextension)
379// Second, search k with gcd(k,m_i)=1, where m_i is the degree of the i'th
380// minimal polynomial. Then the minpoly f_i remains irrd. over q^k and we
381// have enough elements to plug in.
382static int
383getextension( IntList & degreelist, int n){
384  int charac= getCharacteristic();
385  setCharacteristic(0); // need it for k !
386  int k=1, m=1, length=degreelist.length();
387  IntListIterator i;
388
389  for (i=degreelist; i.hasItem(); i++) m= m*i.getItem();
390  int q=charac;
391  while (q <= ((n*m)*(n*m)/2)) { k= k+1; q= q*charac;}
392  int l=0;
393  do {
394    for (i=degreelist; i.hasItem(); i++){
395      l= l+1;
396      if ( gcd0(k,i.getItem()) == 1){
397        DEBOUTLN(CERR, "getextension: gcd == 1, l=",l);
398        if ( l==length ){ setCharacteristic(charac);  return k; }
399      }
400      else { DEBOUTMSG(CERR, "getextension: Next iteration"); break; }
401    }
402    k= k+1; l=0;
403  }
404  while ( 1 );
405}
406
407// calculate a "primitive element"
408// K must have more than S elements (->thesis, -> getextension)
409static CFList
410simpleextension(const CFList & Astar, const Variable & Extension,
411                CanonicalForm & R){
412  CFList Returnlist, Bstar=Astar;
413  CanonicalForm s, g;
414
415  DEBOUTLN(CERR, "simpleextension: Astar= ", Astar);
416  DEBOUTLN(CERR, "simpleextension:     R= ", R);
417  DEBOUTLN(CERR, "simpleextension: Extension= ", Extension);
418  if ( Astar.length() == 1 ){ R= Astar.getFirst();}
419  else{
420    R=Bstar.getFirst(); Bstar.removeFirst();
421    for ( CFListIterator i=Bstar; i.hasItem(); i++){
422      DEBOUTLN(CERR, "simpleextension: f(x)= ", i.getItem());
423      DEBOUTLN(CERR, "simpleextension: P(x)= ", R);
424      sqrf_norm(i.getItem(), R, Extension, s, g, R);
425      // spielt die Repraesentation eine Rolle?
426      // muessen wir die Nachfolger aendern, wenn s != 0 ?
427      DEBOUTLN(CERR, "simpleextension: g= ", g);
428      if ( s != 0 ) DEBOUTLN(CERR, "simpleextension: s= ", s);
429      else DEBOUTLN(CERR, "simpleextension: s= ", s);
430      DEBOUTLN(CERR, "simpleextension: R= ", R);
431      Returnlist.insert(s);
432    }
433  }
434
435  return Returnlist;
436}
437
438CanonicalForm alg_lc(const CanonicalForm &f)
439{
440  if (f.inCoeffDomain()) return f;
441  if (f.level()>0)
442  {
443    return alg_lc(f.LC());
444  }
445}
446
447// the heart of the algorithm: the one from Trager
448static CFFList
449alg_factor( const CanonicalForm & f, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as)
450{
451  CFFList L, Factorlist;
452  CanonicalForm R, Rstar, s, g, h;
453  CFList substlist;
454
455  DEBINCLEVEL(CERR,"alg_factor");
456  DEBOUTLN(CERR, "alg_factor: f= ", f);
457
458  //out_cf("start alg_factor:",f,"\n");
459  substlist= simpleextension(Astar, vminpoly, Rstar);
460  DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
461  DEBOUTLN(CERR, "alg_factor: minpoly Rstar= ", Rstar);
462  DEBOUTLN(CERR, "alg_factor: vminpoly= ", vminpoly);
463
464  sqrf_norm(f, Rstar, vminpoly, s, g, R );
465  //out_cf("sqrf_norm R:",R,"\n");
466  //out_cf("sqrf_norm s:",s,"\n");
467  //out_cf("sqrf_norm g:",g,"\n");
468  DEBOUTLN(CERR, "alg_factor: g= ", g);
469  DEBOUTLN(CERR, "alg_factor: s= ", s);
470  DEBOUTLN(CERR, "alg_factor: R= ", R);
471  Off(SW_RATIONAL);
472  Variable X;
473  if (getAlgVar(R,X))
474  {
475    // factorize R over alg.extension with X
476//CERR << "alg: "<< X << " mipo=" << getMipo(X,Variable('X')) <<"\n";
477    if (R.isUnivariate())
478    {
479      DEBOUTLN(CERR, "alg_factor: factorize( ", R);
480      Factorlist =  factorize( R, X );
481    }
482    else
483    {
484      #if 1
485      Variable XX;
486      CanonicalForm mipo=getMipo(X,XX);
487      CFList as(mipo);
488      DEBOUTLN(CERR, "alg_factor: newfactoras( ", R);
489      Factorlist = newfactoras(R, as , 1);
490      #else
491      // factor R over k
492      DEBOUTLN(CERR, "alg_factor: Factorize( ", R);
493      Factorlist = Factorize(R);
494      #endif
495    }
496  }
497  else
498  {
499    // factor R over k
500    DEBOUTLN(CERR, "alg_factor: Factorize( ", R);
501    Factorlist = Factorize(R);
502  }
503  On(SW_RATIONAL);
504  DEBOUTLN(CERR, "alg_factor: Factorize(R)= ", Factorlist);
505  if ( !Factorlist.getFirst().factor().inCoeffDomain() )
506    Factorlist.insert(CFFactor(1,1));
507  if ( Factorlist.length() == 2 && Factorlist.getLast().exp()== 1)
508  { // irreduzibel (first entry is a constant)
509    L.append(CFFactor(f,1));
510  }
511  else
512  {
513    DEBOUTLN(CERR, "alg_factor: g= ", g);
514    CanonicalForm gnew= g(s,s.mvar());
515    DEBOUTLN(CERR, "alg_factor: gnew= ", gnew);
516    g=gnew;
517    for ( CFFListIterator i=Factorlist; i.hasItem(); i++)
518    {
519      CanonicalForm fnew=i.getItem().factor();
520      fnew= fnew(s,s.mvar());
521      DEBOUTLN(CERR, "alg_factor: fnew= ", fnew);
522      DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
523      for ( CFListIterator ii=substlist; ii.hasItem(); ii++){
524        DEBOUTLN(CERR, "alg_factor: item= ", ii.getItem());
525        fnew= fnew(ii.getItem(), ii.getItem().mvar());
526        DEBOUTLN(CERR, "alg_factor: fnew= ", fnew);
527      }
528      if (degree(i.getItem().factor()) > 0 )
529      {
530        // undo linear transformation!!!! and then gcd!
531        //CERR << "algcd(" << g << "," << fnew << ",as" << as << ")" << "\n";
532        //out_cf("g=",g,"\n");
533        //out_cf("fnew=",fnew,"\n");
534        //h= algcd(g,fnew, as, oldord);
535        //if (as.length() >1)
536        //  h= algcd(g,fnew, as, oldord);
537        //else
538          h=alg_gcd(g,fnew,as);
539        //out_cf(" -> algcd=",algcd(g,fnew, as, oldord),"\n");
540        //out_cf(" -> alg_gcd=",alg_gcd(g,fnew,as),"\n");
541        //CERR << "algcd result:" << h << "\n";
542        DEBOUTLN(CERR, "  alg_factor: h= ", h);
543        DEBOUTLN(CERR, "  alg_factor: oldord= ", oldord);
544        if ( degree(h) > 0 )
545        { //otherwise it's a constant
546          //CanonicalForm c=LC(h,g.mvar());
547          //out_cf("new lc h:",c,"\n");
548          //h= divide(h,c,as);
549          //out_cf("new factor h/c:",h,"\n");
550          g= divide(g, h,as);
551          DEBOUTLN(CERR, "alg_factor: g/h= ", g);
552          DEBOUTLN(CERR, "alg_factor: s= ", s);
553          DEBOUTLN(CERR, "alg_factor: substlist= ", substlist);
554          //out_cf("new g:",g,"\n");
555          L.append(CFFactor(h,1));
556        }
557        //else printf("degree <=1\n");
558      }
559    }
560    // we are not interested in a
561    // constant (over K_r, which can be a polynomial!)
562    if (degree(g, f.mvar())>0){ L.append(CFFactor(g,1)); }
563  }
564  CFFList LL;
565  if (getCharacteristic()>0)
566  {
567    CFFListIterator i=L;
568    CanonicalForm c_fac=1;
569    CanonicalForm c;
570    for(;i.hasItem(); i++ )
571    {
572      CanonicalForm ff=i.getItem().factor();
573      c=alg_lc(ff);
574      int e=i.getItem().exp();
575      ff/=c;
576      if (!ff.isOne()) LL.append(CFFactor(ff,e));
577      while (e>0) { c_fac*=c;e--; }
578    }
579    if (!c_fac.isOne()) LL.insert(CFFactor(c_fac,1));
580  }
581  else
582  {
583    LL=L;
584  }
585  //CFFListIterator i=LL;
586  //for(;i.hasItem(); i++ )
587  //  out_cf("end alg_f:",i.getItem().factor(),"\n");
588  //printf("end alg_factor\n");
589  DEBOUTLN(CERR, "alg_factor: L= ", LL);
590  DEBDECLEVEL(CERR,"alg_factor");
591  return LL;
592}
593
594static CFFList
595endler( const CanonicalForm & f, const CFList & AS, const Varlist & uord ){
596  CanonicalForm F=f, g, q,r;
597  CFFList Output;
598  CFList One, Two, asnew, as=AS;
599  CFListIterator i,ii;
600  VarlistIterator j;
601  Variable vg;
602
603  for (i=as; i.hasItem(); i++){
604    g= i.getItem();
605    if (g.deriv() == 0 ){
606      DEBOUTLN(CERR, "Inseperable extension detected: ", g);
607      for (j=uord; j.hasItem(); j++){
608        if ( degree(g,j.getItem()) > 0 ) vg= j.getItem();
609      }
610      // Now we have the highest transzendental in vg;
611      DEBOUTLN(CERR, "Transzendental is ", vg);
612      CanonicalForm gg=-1*g[0];
613      divrem(gg,vg,q,r); r= gg-q*vg;   gg= gg-r;
614      //DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
615      DEBOUTLN(CERR, "  that is ", gg);
616      DEBOUTLN(CERR, "  maps to ", g+gg);
617      One.insert(gg); Two.insert(g+gg);
618      // Now transform all remaining polys in as:
619      int x=0;
620      for (ii=i; ii.hasItem(); ii++){
621        if ( x != 0 ){
622          divrem(ii.getItem(), gg, q,r);
623//          CERR << ii.getItem() << " divided by " << gg << "\n";
624          DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
625          ii.append(ii.getItem()+q*g); ii.remove(1);
626          DEBOUTLN(CERR, "as= ", as);
627        }
628        x+= 1;
629      }
630      // Now transform F:
631      divrem(F, gg, q,r);
632      F= F+q*g;
633      DEBOUTLN(CERR, "new F= ", F);
634    }
635    else{ asnew.append(i.getItem());  }// just the identity
636  }
637  // factor F with minimal polys given in asnew:
638  DEBOUTLN(CERR, "Factor F=  ", F);
639  DEBOUTLN(CERR, "  with as= ", asnew);
640  int success=0;
641  CFFList factorlist= newcfactor(F,asnew, success);
642  DEBOUTLN(CERR, "  gives =  ", factorlist);
643  DEBOUTLN(CERR, "One= ", One);
644  DEBOUTLN(CERR, "Two= ", Two);
645
646  // Transform back:
647  for ( CFFListIterator k=factorlist; k.hasItem(); k++){
648    CanonicalForm factor= k.getItem().factor();
649    ii=One;
650    for (i=Two; i.hasItem(); i++){
651      DEBOUTLN(CERR, "Mapping ", i.getItem());
652      DEBOUTLN(CERR, "     to ", ii.getItem());
653      DEBOUTLN(CERR, "     in ", factor);
654      divrem(factor,i.getItem(),q,r); r=factor -q*i.getItem();
655      DEBOUTLN(CERR, "q= ", q); DEBOUTLN(CERR, "r= ", r);
656      factor= ii.getItem()*q +r; //
657      ii++;
658    }
659    Output.append(CFFactor(factor,k.getItem().exp()));
660  }
661
662  return Output;
663}
664
665
666// 1) prepares data
667// 2) for char=p we distinguish 3 cases:
668//           no transcendentals, seperable and inseperable extensions
669CFFList
670newfactoras( const CanonicalForm & f, const CFList & as, int success){
671  Variable vf=f.mvar();
672  CFListIterator i;
673  CFFListIterator jj;
674  CFList reduceresult;
675  CFFList result;
676
677  success=1;
678  DEBINCLEVEL(CERR, "newfactoras");
679  DEBOUTLN(CERR, "newfactoras called with f= ", f);
680  DEBOUTLN(CERR, "               content(f)= ", content(f));
681  DEBOUTLN(CERR, "                       as= ", as);
682  DEBOUTLN(CERR, "newfactoras: cls(vf)= ", cls(vf));
683  DEBOUTLN(CERR, "newfactoras: cls(as.getLast())= ", cls(as.getLast()));
684  DEBOUTLN(CERR, "newfactoras: degree(f,vf)= ", degree(f,vf));
685
686// F1: [Test trivial cases]
687// 1) first trivial cases:
688  if ( (cls(vf) <= cls(as.getLast())) ||  degree(f,vf)<=1 ){
689// ||( (as.length()==1) && (degree(f,vf)==3) && (degree(as.getFirst()==2)) )
690    DEBDECLEVEL(CERR,"newfactoras");
691    return CFFList(CFFactor(f,1));
692  }
693
694// 2) List of variables:
695// 2a) Setup list of those polys in AS having degree(AS[i], AS[i].mvar()) > 1
696// 2b) Setup variableordering
697  CFList Astar;
698  Variable x;
699  CanonicalForm elem;
700  Varlist ord, uord,oldord;
701  for ( int ii=1; ii< level(vf) ; ii++ ) { uord.append(Variable(ii));  }
702  oldord= uord; oldord.append(vf);
703
704  for ( i=as; i.hasItem(); i++ ){
705    elem= i.getItem();
706    x= elem.mvar();
707    if ( degree(elem,x) > 1){ // otherwise it's not an extension
708      Astar.append(elem);
709      ord.append(x);
710    }
711  }
712  uord= Difference(uord,ord);
713  DEBOUTLN(CERR, "Astar is: ", Astar);
714  DEBOUTLN(CERR, "ord is: ", ord);
715  DEBOUTLN(CERR, "uord is: ", uord);
716
717// 3) second trivial cases: we already prooved irr. of f over no extensions
718  if ( Astar.length() == 0 ){
719    DEBDECLEVEL(CERR,"newfactoras");
720    return CFFList(CFFactor(f,1));
721  }
722
723// 4) Try to obtain a partial factorization using prop2 and prop3
724//    Use with caution! We have to proof these propositions first!
725  // Not yet implemented
726
727// 5) Look if elements in uord actually occure in any of the minimal
728//    polynomials. If no element of uord occures in any of the minimal
729//   polynomials, we don't have transzendentals.
730  Varlist newuord=Var_is_in_AS(uord,Astar);
731  DEBOUTLN(CERR, "newuord is: ", newuord);
732
733  CFFList Factorlist;
734  Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar());
735  // This is for now. we need alg_sqrfree implemented!
736  //CERR << "algcd(" << f << "," << f.deriv() << " as:" << Astar <<"\n";
737  //CanonicalForm Fgcd= algcd(f,f.deriv(),Astar,gcdord);
738  CanonicalForm Fgcd;
739        //if (Astar.length() >1)
740        //  Fgcd= algcd(f,f.deriv(),Astar,gcdord);
741        //else
742          Fgcd= alg_gcd(f,f.deriv(),Astar);
743        //out_cf("algcd:",algcd(f,f.deriv(),Astar,gcdord),"\n");
744        //out_cf("alg_gcd:",alg_gcd(f,f.deriv(),Astar),"\n");
745 // CERR << "algcd result:"  << Fgcd << "\n";
746  if ( Fgcd == 0 ) DEBOUTMSG(CERR, "WARNING: p'th root ?");
747  if (( degree(Fgcd, f.mvar()) > 0) && (!(f.deriv().isZero())) ){
748    DEBOUTLN(CERR, "Nontrivial GCD found of ", f);
749    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
750    DEBOUTLN(CERR, "  split into ", Fgcd);
751    DEBOUTLN(CERR, "         and ", Ggcd);
752    Fgcd= pp(Fgcd); Ggcd= pp(Ggcd);
753    DEBDECLEVEL(CERR,"newfactoras");
754    return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success));
755  }
756  if ( getCharacteristic() > 0 ){
757
758    // First look for extension!
759    IntList degreelist;
760    Variable vminpoly;
761    for (i=Astar; i.hasItem(); i++){degreelist.append(degree(i.getItem()));}
762    int extdeg= getextension(degreelist, degree(f));
763    DEBOUTLN(CERR, "Extension needed of degree ", extdeg);
764
765    // Now the real stuff!
766    if ( newuord.length() == 0 ){ // no transzendentals
767      DEBOUTMSG(CERR, "No transzendentals!");
768      if ( extdeg > 1 ){
769        CanonicalForm MIPO= generate_mipo( extdeg, vminpoly);
770        DEBOUTLN(CERR, "Minpoly produced ", MIPO);
771        vminpoly= rootOf(MIPO);
772      }
773      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
774      DEBDECLEVEL(CERR,"newfactoras");
775      return Factorlist;
776    }
777    else if ( inseperable(Astar) > 0 ){ // Look if extensions are seperable
778      // a) Use Endler
779      DEBOUTMSG(CERR, "Inseperable extensions! Using Endler!");
780      CFFList templist= endler(f,Astar, newuord);
781      DEBOUTLN(CERR, "Endler gives: ", templist);
782      return templist;
783    }
784    else{ // we are on the save side: Use trager
785      DEBOUTMSG(CERR, "Only seperable extensions!");
786      if (extdeg > 1 ){
787        CanonicalForm MIPO=generate_mipo(extdeg, vminpoly );
788        vminpoly= rootOf(MIPO);
789        DEBOUTLN(CERR, "Minpoly generated: ", MIPO);
790        DEBOUTLN(CERR, "vminpoly= ", vminpoly);
791        DEBOUTLN(CERR, "degree(vminpoly)= ", degree(vminpoly));
792      }
793      Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
794      DEBDECLEVEL(CERR,"newfactoras");
795      return Factorlist;
796    }
797  }
798  else{ // char=0 apply trager directly
799    DEBOUTMSG(CERR, "Char=0! Apply Trager!");
800    Variable vminpoly;
801    Factorlist= alg_factor(f, Astar, vminpoly, oldord, as);
802      DEBDECLEVEL(CERR,"newfactoras");
803      return Factorlist;
804  }
805
806  DEBDECLEVEL(CERR,"newfactoras");
807  return CFFList(CFFactor(f,1));
808}
809
810CFFList
811newcfactor(const CanonicalForm & f, const CFList & as, int success ){
812  Off(SW_RATIONAL);
813  CFFList Output, output, Factors=Factorize(f); On(SW_RATIONAL);
814  Factors.removeFirst();
815
816  if ( as.length() == 0 ){ success=1; return Factors;}
817  if ( cls(f) <= cls(as.getLast()) ) { success=1; return Factors;}
818
819  success=1;
820  for ( CFFListIterator i=Factors; i.hasItem(); i++ ){
821    output=newfactoras(i.getItem().factor(),as, success);
822    for ( CFFListIterator j=output; j.hasItem(); j++)
823      Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp()));
824  }
825  return Output;
826}
827
828/*
829$Log: not supported by cvs2svn $
830Revision 1.23  2008/04/08 16:19:09  Singular
831*hannes: removed rcsid
832
833Revision 1.22  2008/03/18 17:46:14  Singular
834*hannes: gcc 4.2
835
836Revision 1.21  2008/03/17 17:44:15  Singular
837*hannes: fact.tst
838
839Revision 1.17  2007/05/15 14:46:48  Singular
840*hannes: factorize in Zp(a)[x...]
841
842Revision 1.16  2006/05/16 14:46:48  Singular
843*hannes: gcc 4.1 fixes
844
845Revision 1.15  2005/10/17 13:16:18  Singular
846*hannes: code cleanup
847
848Revision 1.14  2005/07/08 09:18:15  Singular
849*hannes: fixed call of resultant
850
851Revision 1.13  2004/12/10 10:15:05  Singular
852*pohl: AlgExtGenerator etc.
853
854Revision 1.12  2003/02/18 11:09:25  Singular
855* hannes: alg_gcd(f,f'=0) get a special handling
856
857Revision 1.11  2002/10/24 17:22:21  Singular
858* hannes: factoring in alg.ext., alg_gcd, NTL stuff
859
860Revision 1.10  2002/08/19 11:11:29  Singular
861* hannes/pfister: alg_gcd etc.
862
863Revision 1.9  2002/07/30 15:16:19  Singular
864*hannes: fix for alg. extension
865
866Revision 1.8  2001/08/06 08:32:53  Singular
867* hannes: code cleanup
868
869Revision 1.7  2001/06/27 13:58:05  Singular
870*hannes/GP: debug newfactoras, char_series, ...
871
872Revision 1.6  2001/06/21 14:57:04  Singular
873*hannes/GP: Factorize, newfactoras, ...
874
875Revision 1.5  2001/06/18 08:44:39  pfister
876* hannes/GP/michael: factory debug, Factorize
877
878Revision 1.4  1998/05/25 18:32:38  obachman
8791998-05-25  Olaf Bachmann  <obachman@mathematik.uni-kl.de>
880
881        * charset/alg_factor.cc: replaced identifiers 'random' by
882        'myrandom' to avoid name conflicts with the built-in (stdlib)
883        library function 'random' which might be a macro -- and, actually
884        is  under gcc v 2.6.3
885
886Revision 1.3  1998/03/12 12:34:24  schmidt
887        * charset/csutil.cc, charset/alg_factor.cc: all references to
888          `common_den()' replaced by `bCommonDen()'
889
890Revision 1.2  1997/09/12 07:19:37  Singular
891* hannes/michael: libfac-0.3.0
892
893*/
Note: See TracBrowser for help on using the repository browser.