source: git/libfac/charset/alg_factor.cc @ 01e8874

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