source: git/factory/facAlgFunc.cc @ 67294f1

spielwiese
Last change on this file since 67294f1 was 67294f1, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: move IntGenerator from facAlgFuncUtil to cf_generator
  • Property mode set to 100644
File size: 25.4 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facAlgFunc.cc
5 *
6 * This file provides functions to factorize polynomials over alg. function
7 * fields
8 *
9 * @note some of the code is code from libfac or derived from code from libfac.
10 * Libfac is written by M. Messollen. See also COPYING for license information
11 * and README for general information on characteristic sets.
12 *
13 * ABSTRACT: Descriptions can be found in B. Trager "Algebraic Factoring and
14 * Rational Function Integration" and A. Steel "Conquering Inseparability:
15 * Primary decomposition and multivariate factorization over algebraic function
16 * fields of positive characteristic"
17 *
18 * @author Martin Lee
19 *
20 **/
21/*****************************************************************************/
22
23#include "config.h"
24
25#include "cf_assert.h"
26#include "debug.h"
27
28#include "algext.h"
29#include "cf_generator.h"
30#include "cf_iter.h"
31#include "cf_util.h"
32#include "cf_algorithm.h"
33#include "cf_map.h"
34#include "cfModResultant.h"
35#include "cfCharSets.h"
36#include "facAlgFunc.h"
37#include "facAlgFuncUtil.h"
38
39void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
40
41CanonicalForm
42alg_content (const CanonicalForm& f, const CFList& as)
43{
44  if (!f.inCoeffDomain())
45  {
46    CFIterator i= f;
47    CanonicalForm result= abs (i.coeff());
48    i++;
49    while (i.hasTerms() && !result.isOne())
50    {
51      result= alg_gcd (i.coeff(), result, as);
52      i++;
53    }
54    return result;
55  }
56
57  return abs (f);
58}
59
60CanonicalForm
61alg_gcd (const CanonicalForm & fff, const CanonicalForm &ggg, const CFList &as)
62{
63  if (fff.inCoeffDomain() || ggg.inCoeffDomain())
64    return 1;
65  CanonicalForm f=fff;
66  CanonicalForm g=ggg;
67  f=Prem(f,as);
68  g=Prem(g,as);
69  if ( f.isZero() )
70  {
71    if ( g.lc().sign() < 0 ) return -g;
72    else                     return g;
73  }
74  else  if ( g.isZero() )
75  {
76    if ( f.lc().sign() < 0 ) return -f;
77    else                     return f;
78  }
79
80  int v= as.getLast().level();
81  if (f.level() <= v || g.level() <= v)
82    return 1;
83
84  CanonicalForm res;
85
86  // does as appear in f and g ?
87  bool has_alg_var=false;
88  for ( CFListIterator j=as;j.hasItem(); j++ )
89  {
90    Variable v=j.getItem().mvar();
91    if (hasVar (f, v))
92      has_alg_var=true;
93    if (hasVar (g, v))
94      has_alg_var=true;
95  }
96  if (!has_alg_var)
97  {
98    /*if ((hasAlgVar(f))
99    || (hasAlgVar(g)))
100    {
101      Varlist ord;
102      for ( CFListIterator j=as;j.hasItem(); j++ )
103        ord.append(j.getItem().mvar());
104      res=algcd(f,g,as,ord);
105    }
106    else*/
107    if (!hasAlgVar (f) && !hasAlgVar (g))
108      return res=gcd(f,g);
109  }
110
111  int mvf=f.level();
112  int mvg=g.level();
113  if (mvg > mvf)
114  {
115    CanonicalForm tmp=f; f=g; g=tmp;
116    int tmp2=mvf; mvf=mvg; mvg=tmp2;
117  }
118  if (g.inBaseDomain() || f.inBaseDomain())
119    return CanonicalForm(1);
120
121  CanonicalForm c_f= alg_content (f, as);
122
123  if (mvf != mvg)
124  {
125    res= alg_gcd (g, c_f, as);
126    return res;
127  }
128  Variable x= f.mvar();
129
130  // now: mvf==mvg, f.level()==g.level()
131  CanonicalForm c_g= alg_content (g, as);
132
133  int delta= degree (f) - degree (g);
134
135  f= divide (f, c_f, as);
136  g= divide (g, c_g, as);
137
138  // gcd of contents
139  CanonicalForm c_gcd= alg_gcd (c_f, c_g, as);
140  CanonicalForm tmp;
141
142  if (delta < 0)
143  {
144    tmp= f;
145    f= g;
146    g= tmp;
147    delta= -delta;
148  }
149
150  CanonicalForm r= 1;
151
152  while (degree (g, x) > 0)
153  {
154    r= Prem (f, g);
155    r= Prem (r, as);
156    if (!r.isZero())
157    {
158      r= divide (r, alg_content (r,as), as);
159      r /= vcontent (r,Variable (v+1));
160    }
161    f= g;
162    g= r;
163  }
164
165  if (degree (g, x) == 0)
166    return c_gcd;
167
168  c_f= alg_content (f, as);
169
170  f= divide (f, c_f, as);
171
172  f *= c_gcd;
173  f /= vcontent (f, Variable (v+1));
174
175  return f;
176}
177
178static CanonicalForm
179resultante (const CanonicalForm & f, const CanonicalForm& g, const Variable & v)
180{
181  bool on_rational = isOn(SW_RATIONAL);
182  if (!on_rational && getCharacteristic() == 0)
183    On(SW_RATIONAL);
184  CanonicalForm cd = bCommonDen( f );
185  CanonicalForm fz = f * cd;
186  cd = bCommonDen( g );
187  CanonicalForm gz = g * cd;
188  if (!on_rational && getCharacteristic() == 0)
189    Off(SW_RATIONAL);
190  CanonicalForm result;
191  if (getCharacteristic() == 0)
192    result= resultantZ (fz, gz,v);
193  else
194    result= resultant (fz,gz,v);
195
196  return result;
197}
198
199/// compute the norm R of f over PPalpha, g= f (x-s*alpha)
200/// if proof==true, R is squarefree and if in addition getCharacteristic() > 0
201/// the squarefree factors of R are returned.
202/// Based on Trager's sqrf_norm algorithm.
203static CFFList
204norm (const CanonicalForm & f, const CanonicalForm & PPalpha,
205      CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g,
206      CanonicalForm & R, bool proof)
207{
208  Variable y= PPalpha.mvar(), vf= f.mvar();
209  CanonicalForm temp, Palpha= PPalpha, t;
210  int sqfreetest= 0;
211  CFFList testlist;
212  CFFListIterator i;
213
214  if (proof)
215  {
216    myrandom.reset();
217    s= myrandom.item();
218    g= f;
219    R= CanonicalForm(0);
220  }
221  else
222  {
223    if (getCharacteristic() == 0)
224      t= CanonicalForm (mapinto (myrandom.item()));
225    else
226      t= CanonicalForm (myrandom.item());
227    s= t;
228    g= f (vf - t*Palpha.mvar(), vf);
229  }
230
231  // Norm, resultante taken with respect to y
232  while (!sqfreetest)
233  {
234    R= resultante (Palpha, g, y);
235    R= R* bCommonDen(R);
236    R /= content (R);
237    if (proof)
238    {
239      // sqfree check ; R is a polynomial in K[x]
240      if (getCharacteristic() == 0)
241      {
242        temp= gcd (R, R.deriv (vf));
243        if (degree(temp,vf) != 0 || temp == temp.genZero())
244          sqfreetest= 0;
245        else
246          sqfreetest= 1;
247      }
248      else
249      {
250        Variable X;
251        testlist= sqrFree (R);
252
253        if (testlist.getFirst().factor().inCoeffDomain())
254          testlist.removeFirst();
255        sqfreetest= 1;
256        for (i= testlist; i.hasItem(); i++)
257        {
258          if (i.getItem().exp() > 1 && degree (i.getItem().factor(),R.mvar()) > 0)
259          {
260            sqfreetest= 0;
261            break;
262          }
263        }
264      }
265      if (!sqfreetest)
266      {
267        myrandom.next();
268        if (getCharacteristic() == 0)
269          t= CanonicalForm (mapinto (myrandom.item()));
270        else
271          t= CanonicalForm (myrandom.item());
272        s= t;
273        g= f (vf - t*Palpha.mvar(), vf);
274      }
275    }
276    else
277      break;
278  }
279  return testlist;
280}
281
282/// see @a norm, R is guaranteed to be squarefree
283/// Based on Trager's sqrf_norm algorithm.
284static CFFList
285sqrfNorm (const CanonicalForm & f, const CanonicalForm & PPalpha,
286          const Variable & Extension, CanonicalForm & s,  CanonicalForm & g,
287          CanonicalForm & R)
288{
289  CFFList result;
290  if (getCharacteristic() == 0)
291  {
292    IntGenerator myrandom;
293    result= norm (f, PPalpha, myrandom, s, g, R, true);
294  }
295  else if (degree (Extension) > 0)
296  {
297    AlgExtGenerator myrandom (Extension);
298    result= norm (f, PPalpha, myrandom, s, g, R, true);
299  }
300  else
301  {
302    FFGenerator myrandom;
303    result= norm (f, PPalpha, myrandom, s, g, R, true);
304  }
305  return result;
306}
307
308// calculate a "primitive element"
309// K must have more than S elements (-> getDegOfExt)
310static CFList
311simpleExtension (CFList& backSubst, const CFList & Astar,
312                 const Variable & Extension, bool& isFunctionField,
313                 CanonicalForm & R)
314{
315  CFList Returnlist, Bstar= Astar;
316  CanonicalForm s, g, ra, rb, oldR, h, denra, denrb= 1;
317  Variable alpha;
318  CFList tmp;
319
320  bool isRat= isOn (SW_RATIONAL);
321
322  CFListIterator j;
323  if (Astar.length() == 1)
324  {
325    R= Astar.getFirst();
326    rb= R.mvar();
327  }
328  else
329  {
330    R=Bstar.getFirst();
331    Bstar.removeFirst();
332    for (CFListIterator i= Bstar; i.hasItem(); i++)
333    {
334      j= i;
335      j++;
336      if (getCharacteristic() == 0)
337        Off (SW_RATIONAL);
338      R /= icontent (R);
339      if (getCharacteristic() == 0)
340        On (SW_RATIONAL);
341      oldR= R;
342      //TODO normalize i.getItem over K(R)?
343      (void) sqrfNorm (i.getItem(), R, Extension, s, g, R);
344
345      backSubst.insert (s);
346
347      if (getCharacteristic() == 0)
348        Off (SW_RATIONAL);
349      R /= icontent (R);
350
351      if (getCharacteristic() == 0)
352        On (SW_RATIONAL);
353
354      if (!isFunctionField)
355      {
356        alpha= rootOf (R);
357        h= replacevar (g, g.mvar(), alpha);
358        if (getCharacteristic() == 0)
359          On (SW_RATIONAL); //needed for GCD
360        h= gcd (h, oldR);
361        h /= Lc (h);
362        ra= -h[0];
363        ra= replacevar(ra, alpha, g.mvar());
364        rb= R.mvar()-s*ra;
365        for (; j.hasItem(); j++)
366        {
367          j.getItem()= j.getItem() (ra, oldR.mvar());
368          j.getItem()= j.getItem() (rb, i.getItem().mvar());
369        }
370      }
371      else
372      {
373        if (getCharacteristic() == 0)
374          On (SW_RATIONAL);
375        h= swapvar (g, g.mvar(), oldR.mvar());
376        tmp= CFList (swapvar (R, g.mvar(), oldR.mvar()));
377        h= alg_gcd (h, swapvar (oldR, g.mvar(), oldR.mvar()), tmp);
378        CanonicalForm hh= replacevar (h, oldR.mvar(), alpha);
379
380        CanonicalForm numinv, deninv;
381        numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
382
383        if (getCharacteristic() == 0)
384          Off (SW_RATIONAL);
385        h *= numinv;
386        h= reduce (h, tmp.getFirst());
387        deninv= LC(h);
388
389        ra= -h[0];
390        denra= gcd (ra, deninv);
391        ra /= denra;
392        denra= deninv/denra;
393        denra= replacevar (denra, ra.mvar(), g.mvar());
394        ra= replacevar(ra, ra.mvar(), g.mvar());
395        rb= R.mvar()*denra-s*ra;
396        denrb= denra;
397        for (; j.hasItem(); j++)
398        {
399          CanonicalForm powdenra= power (denra, degree (j.getItem(),
400                                                        oldR.mvar()));
401          j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
402          powdenra= power (denra, degree (j.getItem(), i.getItem().mvar()));
403          j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
404                                 i.getItem().mvar());
405        }
406      }
407
408      Returnlist.append (ra);
409      if (isFunctionField)
410        Returnlist.append (denra);
411    }
412  }
413  Returnlist.append (rb);
414  if (isFunctionField)
415    Returnlist.append (denrb);
416
417  if (isRat && getCharacteristic() == 0)
418    On (SW_RATIONAL);
419  else if (!isRat && getCharacteristic() == 0)
420    Off (SW_RATIONAL);
421
422  return Returnlist;
423}
424
425/// Trager's algorithm, i.e. convert to one field extension and
426/// factorize over this field extension
427static CFFList
428Trager (const CanonicalForm & F, const CFList & Astar,
429        const Variable & vminpoly, const CFList & as, bool isFunctionField)
430{
431  bool isRat= isOn (SW_RATIONAL);
432  CFFList L, sqrfFactors, Factorlist, tmp;
433  CFFListIterator iter, iter2;
434  CanonicalForm R, Rstar, s, g, h, f= F;
435  CFList substlist, backSubsts;
436
437  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
438                              Rstar);
439
440  f= subst (f, Astar, substlist, Rstar, isFunctionField);
441
442  Variable alpha;
443  if (!isFunctionField)
444  {
445    alpha= rootOf (Rstar);
446    g= replacevar (f, Rstar.mvar(), alpha);
447
448    if (!isRat && getCharacteristic() == 0)
449      On (SW_RATIONAL);
450    Factorlist= factorize (g, alpha);
451
452    for (iter= Factorlist; iter.hasItem(); iter++)
453    {
454      h= iter.getItem().factor();
455      if (!h.inCoeffDomain())
456      {
457        h= replacevar (h, alpha, Rstar.mvar());
458        h *= bCommonDen(h);
459        h= backSubst (h, backSubsts, Astar);
460        h= Prem (h, as);
461        L.append (CFFactor (h, iter.getItem().exp()));
462      }
463    }
464    if (!isRat && getCharacteristic() == 0)
465      Off (SW_RATIONAL);
466    return L;
467  }
468  // after here we are over an extension of a function field
469
470  // make quasi monic
471  CFList Rstarlist= CFList (Rstar);
472  int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
473  CanonicalForm numinv;
474  if (!isRat && getCharacteristic() == 0)
475    On (SW_RATIONAL);
476  numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());
477
478  f *= numinv;
479  f= Prem (f, Rstarlist);
480  f /= vcontent (f, Rstar.mvar());
481  // end quasi monic
482
483  if (degree (f) == 1)
484  {
485    f= backSubst (f, backSubsts, Astar);
486    f *= bCommonDen (f);
487    f= Prem (f, as);
488    f /= vcontent (f, as.getFirst().mvar());
489
490    return CFFList (CFFactor (f, 1));
491  }
492
493  CFGenerator * Gen;
494  if (getCharacteristic() == 0)
495    Gen= CFGenFactory::generate();
496  else if (degree (vminpoly) > 0)
497    Gen= AlgExtGenerator (vminpoly).clone();
498  else
499    Gen= CFGenFactory::generate();
500
501  CFFList LL= CFFList (CFFactor (f, 1));
502
503  Variable X;
504  do
505  {
506    tmp= CFFList();
507    for (iter= LL; iter.hasItem(); iter++)
508    {
509      f= iter.getItem().factor();
510      sqrfFactors= norm (f, Rstar, *Gen, s, g, R, false);
511
512      if (hasFirstAlgVar (R, X))
513        Factorlist= factorize (R, X);
514      else
515        Factorlist= factorize (R);
516
517      if (!Factorlist.getFirst().factor().inCoeffDomain())
518        Factorlist.insert (CFFactor (1, 1));
519      if (Factorlist.length() == 2 && Factorlist.getLast().exp() == 1)
520      {
521        f= backSubst (f, backSubsts, Astar);
522        f *= bCommonDen (f);
523        f= Prem (f, as);
524        f /= vcontent (f, as.getFirst().mvar());
525
526        L.append (CFFactor (f, 1));
527        break;
528      }
529      else
530      {
531        g= f;
532        for (iter2= Factorlist; iter2.hasItem(); iter2++)
533        {
534          CanonicalForm fnew= iter2.getItem().factor();
535          if (fnew.level() < Rstar.level()) //factor is a constant from the function field
536            continue;
537          else
538          {
539            fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
540            fnew= reduce (fnew, Rstar);
541          }
542
543          h= alg_gcd (g, fnew, Rstarlist);
544          numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
545          h *= numinv;
546          h= Prem (h, Rstarlist);
547          h /= vcontent (h, Rstar.mvar());
548
549          if (h.level() >= Rstar.level())
550          {
551            g= divide (g, h, Rstarlist);
552            if (degree (h) == 1 || iter2.getItem().exp() == 1)
553            {
554              h= backSubst (h, backSubsts, Astar);
555              h= Prem (h, as);
556              h *= bCommonDen (h);
557              h /= vcontent (h, as.getFirst().mvar());
558              L.append (CFFactor (h, 1));
559            }
560            else
561              tmp.append (CFFactor (h, iter2.getItem().exp()));
562          }
563        }
564      }
565    }
566    LL= tmp;
567    (*Gen).next();
568  }
569  while (!LL.isEmpty());
570
571  if (!isRat && getCharacteristic() == 0)
572    Off (SW_RATIONAL);
573
574  delete Gen;
575
576  return L;
577}
578
579/// algorithm of A. Steel described in "Conquering Inseparability: Primary
580/// decomposition and multivariate factorization over algebraic function fields
581/// of positive characteristic" with the following modifications: we use
582/// characteristic sets in IdealOverSubfield and Trager's primitive element
583/// algorithm instead of FGLM
584CFFList
585SteelTrager (const CanonicalForm & f, const CFList & AS)
586{
587  CanonicalForm F= f, lcmVars= 1;
588  CFList asnew, as= AS;
589  CFListIterator i, ii;
590
591  bool derivZeroF= false;
592  int j, exp=0, expF= 0, tmpExp;
593  CFFList varsMapLevel;
594  CFFListIterator iter;
595
596  // check if F is separable
597  if (F.deriv().isZero())
598  {
599    derivZeroF= true;
600    deflateDegree (F, expF, F.level());
601  }
602
603  CanonicalForm varsF= getVars (F);
604  varsF /= F.mvar();
605
606  lcmVars= lcm (varsF, lcmVars);
607
608  if (derivZeroF)
609    as.append (F);
610
611  CFFList varsGMapLevel;
612  CFFList tmp;
613  CFFList * varsGMap= new CFFList [as.length()];
614  for (j= 0; j < as.length(); j++)
615    varsGMap[j]= CFFList();
616
617  CanonicalForm varsG;
618  j= 0;
619  bool recurse= false;
620  i= as;
621  // make minimal polys and F separable
622  while (i.hasItem())
623  {
624    if (i.getItem().deriv() == 0)
625    {
626      deflateDegree (i.getItem(), exp, i.getItem().level());
627      i.getItem()= deflatePoly (i.getItem(), exp, i.getItem().level());
628     
629      varsG= getVars (i.getItem());
630      varsG /= i.getItem().mvar();
631
632      lcmVars= lcm (varsG, lcmVars);
633
634      while (!varsG.isOne())
635      {
636        if (i.getItem().deriv (varsG.level()).isZero())
637        {
638          deflateDegree (i.getItem(), tmpExp, varsG.level());
639          if (exp >= tmpExp)
640          {
641            if (exp == tmpExp)
642              i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
643            else
644            {
645              if (j != 0)
646                recurse= true;
647              i.getItem()= deflatePoly (i.getItem(), tmpExp, varsG.level());
648            }
649            varsGMapLevel.insert (CFFactor (varsG.mvar(), exp - tmpExp));
650          }
651          else
652          {
653            i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
654            varsGMapLevel.insert (CFFactor (varsG.mvar(), 0));
655          }
656        }
657        else
658        {
659          if (j != 0)
660            recurse= true;
661          varsGMapLevel.insert (CFFactor (varsG.mvar(),exp));
662        }
663        varsG /= varsG.mvar();
664      }
665
666      if (recurse)
667      {
668        ii= as;
669        for (; ii.hasItem(); ii++)
670        {
671          if (ii.getItem() == i.getItem())
672            continue;
673          for (iter= varsGMapLevel; iter.hasItem(); iter++)
674            ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
675                                       iter.getItem().factor().level());
676        }
677      }
678      else
679      {
680        ii= i;
681        ii++;
682        for (; ii.hasItem(); ii++)
683        {
684          for (iter= varsGMapLevel; iter.hasItem(); iter++)
685          {
686            ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
687                                       iter.getItem().factor().level());
688          }
689        }
690      }
691      if (varsGMap[j].isEmpty())
692        varsGMap[j]= varsGMapLevel;
693      else
694      {
695        if (!varsGMapLevel.isEmpty())
696        {
697          tmp= varsGMap[j];
698          CFFListIterator iter2= varsGMapLevel;
699          ASSERT (tmp.length() == varsGMapLevel.length(),
700                  "wrong length of lists");
701          for (iter=tmp; iter.hasItem(); iter++, iter2++)
702            iter.getItem()= CFFactor (iter.getItem().factor(),
703                                  iter.getItem().exp() + iter2.getItem().exp());
704          varsGMap[j]= tmp;
705        }
706      }
707      varsGMapLevel= CFFList();
708    }
709    asnew.append (i.getItem());
710    if (!recurse)
711    {
712      i++;
713      j++;
714    }
715    else
716    {
717      i= as;
718      j= 0;
719      recurse= false;
720      asnew= CFList();
721    }
722  }
723
724  while (!lcmVars.isOne())
725  {
726    varsMapLevel.insert (CFFactor (lcmVars.mvar(), 0));
727    lcmVars /= lcmVars.mvar();
728  }
729
730  // compute how to map variables in F
731  for (j= 0; j < as.length(); j++)
732  {
733    if (varsGMap[j].isEmpty())
734      continue;
735
736    for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
737    {
738      for (iter= varsMapLevel; iter.hasItem(); iter++)
739      {
740        if (iter.getItem().factor() == iter2.getItem().factor())
741        {
742          iter.getItem()= CFFactor (iter.getItem().factor(),
743                                  iter.getItem().exp() + iter2.getItem().exp());
744        }
745      }
746    }
747  }
748
749  delete [] varsGMap;
750
751  if (derivZeroF)
752  {
753    as.removeLast();
754    asnew.removeLast();
755    F= deflatePoly (F, expF, F.level());
756  }
757
758  // map variables in F
759  for (iter= varsMapLevel; iter.hasItem(); iter++)
760  {
761    if (expF > 0)
762      tmpExp= iter.getItem().exp() - expF;
763    else
764      tmpExp= iter.getItem().exp();
765
766    if (tmpExp > 0)
767      F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
768    else if (tmpExp < 0)
769      F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
770  }
771
772  // factor F with minimal polys given in asnew
773  asnew.append (F);
774  asnew= charSetViaModCharSet (asnew, false);
775
776  F= asnew.getLast();
777  F /= content (F);
778
779  asnew.removeLast();
780  for (i= asnew; i.hasItem(); i++)
781    i.getItem() /= content (i.getItem());
782
783  tmp= facAlgFunc (F, asnew);
784
785  // transform back
786  j= 0;
787  int p= getCharacteristic();
788  CFList transBack;
789  CFMap M;
790  CanonicalForm g;
791
792  for (iter= varsMapLevel; iter.hasItem(); iter++)
793  {
794    if (iter.getItem().exp() > 0)
795    {
796      j++;
797      g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
798         iter.getItem().factor().mvar();
799      transBack.append (g);
800      M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
801    }
802  }
803
804  for (i= asnew; i.hasItem(); i++)
805    transBack.insert (M (i.getItem()));
806
807  if (expF > 0)
808    tmpExp= ipower (p, expF);
809
810  CFFList result;
811  CFList transform;
812
813  for (iter= tmp; iter.hasItem(); iter++)
814  {
815    transform= transBack;
816    CanonicalForm factor= iter.getItem().factor();
817    factor= M (factor);
818    transform.append (factor);
819    transform= charSetViaModCharSet (transform, false);
820    for (i= transform; i.hasItem(); i++)
821    {
822      if (degree (i.getItem(), f.mvar()) > 0)
823      {
824        factor= i.getItem();
825        break;
826      }
827    }
828
829    factor /= content (factor);
830
831    if (expF > 0)
832    {
833      int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
834      result.append (CFFactor (factor, iter.getItem().exp()*mult));
835    }
836    else
837      result.append (CFFactor (factor, iter.getItem().exp()));
838  }
839
840  return result;
841}
842
843/// factorize a polynomial that is irreducible over the ground field modulo an
844/// extension given by an irreducible characteristic set
845
846// 1) prepares data
847// 2) for char=p we distinguish 3 cases:
848//           no transcendentals, separable and inseparable extensions
849CFFList
850facAlgFunc2 (const CanonicalForm & f, const CFList & as)
851{
852  bool isRat= isOn (SW_RATIONAL);
853  if (!isRat && getCharacteristic() == 0)
854    On (SW_RATIONAL);
855  Variable vf=f.mvar();
856  CFListIterator i;
857  CFFListIterator jj;
858  CFList reduceresult;
859  CFFList result;
860
861// F1: [Test trivial cases]
862// 1) first trivial cases:
863  if (vf.level() <= as.getLast().level())
864  {
865    if (!isRat && getCharacteristic() == 0)
866      Off (SW_RATIONAL);
867    return CFFList(CFFactor(f,1));
868  }
869
870// 2) Setup list of those polys in AS having degree > 1
871  CFList Astar;
872  Variable x;
873  CanonicalForm elem;
874  Varlist ord, uord;
875  for (int ii= 1; ii < level (vf); ii++)
876    uord.append (Variable (ii));
877
878  for (i= as; i.hasItem(); i++)
879  {
880    elem= i.getItem();
881    x= elem.mvar();
882    if (degree (elem, x) > 1)  // otherwise it's not an extension
883    {
884      Astar.append (elem);
885      ord.append (x);
886    }
887  }
888  uord= Difference (uord, ord);
889
890// 3) second trivial cases: we already proved irr. of f over no extensions
891  if (Astar.length() == 0)
892  {
893    if (!isRat && getCharacteristic() == 0)
894      Off (SW_RATIONAL);
895    return CFFList (CFFactor (f, 1));
896  }
897
898// 4) Look if elements in uord actually occur in any of the minimal
899//    polynomials. If no element of uord occures in any of the minimal
900//    polynomials the field is an alg. number field not an alg. function field
901  Varlist newuord= varsInAs (uord, Astar);
902
903  CFFList Factorlist;
904  Varlist gcdord= Union (ord, newuord);
905  gcdord.append (f.mvar());
906  bool isFunctionField= (newuord.length() > 0);
907
908  // TODO alg_sqrfree?
909  CanonicalForm Fgcd= 0;
910  if (isFunctionField)
911    Fgcd= alg_gcd (f, f.deriv(), Astar);
912
913  bool derivZero= f.deriv().isZero();
914  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
915  {
916    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
917    if (getCharacteristic() == 0)
918    {
919      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
920      multiplicity (result, f, Astar);
921      if (!isRat && getCharacteristic() == 0)
922        Off (SW_RATIONAL);
923      return result;
924    }
925
926    Fgcd= pp (Fgcd);
927    Ggcd= pp (Ggcd);
928    if (!isRat && getCharacteristic() == 0)
929      Off (SW_RATIONAL);
930    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
931  }
932
933  if (getCharacteristic() > 0)
934  {
935    IntList degreelist;
936    Variable vminpoly;
937    for (i= Astar; i.hasItem(); i++)
938      degreelist.append (degree (i.getItem()));
939
940    int extdeg= getDegOfExt (degreelist, degree (f));
941
942    if (newuord.length() == 0) // no parameters
943    {
944      if (extdeg > 1)
945      {
946        CanonicalForm MIPO= generateMipo (extdeg);
947        vminpoly= rootOf(MIPO);
948      }
949      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
950      return Factorlist;
951    }
952    else if (isInseparable(Astar) || derivZero) // inseparable case
953    {
954      Factorlist= SteelTrager (f, Astar);
955      return Factorlist;
956    }
957    else // separable case
958    {
959      if (extdeg > 1)
960      {
961        CanonicalForm MIPO=generateMipo (extdeg);
962        vminpoly= rootOf (MIPO);
963      }
964      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
965      return Factorlist;
966    }
967  }
968  else // char 0
969  {
970    Variable vminpoly;
971    Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
972    if (!isRat && getCharacteristic() == 0)
973      Off (SW_RATIONAL);
974    return Factorlist;
975  }
976
977  return CFFList (CFFactor(f,1));
978}
979
980
981/// factorize a polynomial modulo an extension given by an irreducible
982/// characteristic set
983CFFList
984facAlgFunc (const CanonicalForm & f, const CFList & as)
985{
986  bool isRat= isOn (SW_RATIONAL);
987  if (!isRat && getCharacteristic() == 0)
988    On (SW_RATIONAL);
989  CFFList Output, output, Factors= factorize(f);
990  if (Factors.getFirst().factor().inCoeffDomain())
991    Factors.removeFirst();
992
993  if (as.length() == 0)
994  {
995    if (!isRat && getCharacteristic() == 0)
996      Off (SW_RATIONAL);
997    return Factors;
998  }
999  if (f.level() <= as.getLast().level())
1000  {
1001    if (!isRat && getCharacteristic() == 0)
1002      Off (SW_RATIONAL);
1003    return Factors;
1004  }
1005
1006  for (CFFListIterator i=Factors; i.hasItem(); i++)
1007  {
1008    if (i.getItem().factor().level() > as.getLast().level())
1009    {
1010      output= facAlgFunc2 (i.getItem().factor(), as);
1011      for (CFFListIterator j= output; j.hasItem(); j++)
1012        Output= append (Output, CFFactor (j.getItem().factor(),
1013                                          j.getItem().exp()*i.getItem().exp()));
1014    }
1015  }
1016
1017  if (!isRat && getCharacteristic() == 0)
1018    Off (SW_RATIONAL);
1019  return Output;
1020}
Note: See TracBrowser for help on using the repository browser.