source: git/libfac/charset/alg_factor.cc @ b96e07

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