source: git/factory/facAlgFunc.cc @ 36dfca

spielwiese
Last change on this file since 36dfca was 36dfca, checked in by Martin Lee <martinlee84@…>, 9 years ago
fix for #628
  • Property mode set to 100644
File size: 26.9 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 "cf_generator.h"
29#include "cf_iter.h"
30#include "cf_util.h"
31#include "cf_algorithm.h"
32#include "templates/ftmpl_functions.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#ifdef HAVE_NTL
192  if (getCharacteristic() == 0)
193    result= resultantZ (fz, gz,v);
194  else
195#endif
196    result= resultant (fz,gz,v);
197
198  return result;
199}
200
201/// compute the norm R of f over PPalpha, g= f (x-s*alpha)
202/// if proof==true, R is squarefree and if in addition getCharacteristic() > 0
203/// the squarefree factors of R are returned.
204/// Based on Trager's sqrf_norm algorithm.
205static CFFList
206norm (const CanonicalForm & f, const CanonicalForm & PPalpha,
207      CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g,
208      CanonicalForm & R, bool proof)
209{
210  Variable y= PPalpha.mvar(), vf= f.mvar();
211  CanonicalForm temp, Palpha= PPalpha, t;
212  int sqfreetest= 0;
213  CFFList testlist;
214  CFFListIterator i;
215
216  if (proof)
217  {
218    myrandom.reset();
219    s= myrandom.item();
220    g= f;
221    R= CanonicalForm(0);
222  }
223  else
224  {
225    if (getCharacteristic() == 0)
226      t= CanonicalForm (mapinto (myrandom.item()));
227    else
228      t= CanonicalForm (myrandom.item());
229    s= t;
230    g= f (vf - t*Palpha.mvar(), vf);
231  }
232
233  // Norm, resultante taken with respect to y
234  while (!sqfreetest)
235  {
236    R= resultante (Palpha, g, y);
237    R= R* bCommonDen(R);
238    R /= content (R);
239    if (proof)
240    {
241      // sqfree check ; R is a polynomial in K[x]
242      if (getCharacteristic() == 0)
243      {
244        temp= gcd (R, R.deriv (vf));
245        if (degree(temp,vf) != 0 || temp == temp.genZero())
246          sqfreetest= 0;
247        else
248          sqfreetest= 1;
249      }
250      else
251      {
252        Variable X;
253        testlist= sqrFree (R);
254
255        if (testlist.getFirst().factor().inCoeffDomain())
256          testlist.removeFirst();
257        sqfreetest= 1;
258        for (i= testlist; i.hasItem(); i++)
259        {
260          if (i.getItem().exp() > 1 && degree (i.getItem().factor(),R.mvar()) > 0)
261          {
262            sqfreetest= 0;
263            break;
264          }
265        }
266      }
267      if (!sqfreetest)
268      {
269        myrandom.next();
270        if (getCharacteristic() == 0)
271          t= CanonicalForm (mapinto (myrandom.item()));
272        else
273          t= CanonicalForm (myrandom.item());
274        s= t;
275        g= f (vf - t*Palpha.mvar(), vf);
276      }
277    }
278    else
279      break;
280  }
281  return testlist;
282}
283
284/// see @a norm, R is guaranteed to be squarefree
285/// Based on Trager's sqrf_norm algorithm.
286static CFFList
287sqrfNorm (const CanonicalForm & f, const CanonicalForm & PPalpha,
288          const Variable & Extension, CanonicalForm & s,  CanonicalForm & g,
289          CanonicalForm & R)
290{
291  CFFList result;
292  if (getCharacteristic() == 0)
293  {
294    IntGenerator myrandom;
295    result= norm (f, PPalpha, myrandom, s, g, R, true);
296  }
297  else if (degree (Extension) > 0)
298  {
299    AlgExtGenerator myrandom (Extension);
300    result= norm (f, PPalpha, myrandom, s, g, R, true);
301  }
302  else
303  {
304    FFGenerator myrandom;
305    result= norm (f, PPalpha, myrandom, s, g, R, true);
306  }
307  return result;
308}
309
310// calculate a "primitive element"
311// K must have more than S elements (-> getDegOfExt)
312static CFList
313simpleExtension (CFList& backSubst, const CFList & Astar,
314                 const Variable & Extension, bool& isFunctionField,
315                 CanonicalForm & R)
316{
317  CFList Returnlist, Bstar= Astar;
318  CanonicalForm s, g, ra, rb, oldR, h, denra, denrb= 1;
319  Variable alpha;
320  CFList tmp;
321
322  bool isRat= isOn (SW_RATIONAL);
323
324  CFListIterator j;
325  if (Astar.length() == 1)
326  {
327    R= Astar.getFirst();
328    rb= R.mvar();
329  }
330  else
331  {
332    R=Bstar.getFirst();
333    Bstar.removeFirst();
334    for (CFListIterator i= Bstar; i.hasItem(); i++)
335    {
336      j= i;
337      j++;
338      if (getCharacteristic() == 0)
339        Off (SW_RATIONAL);
340      R /= icontent (R);
341      if (getCharacteristic() == 0)
342        On (SW_RATIONAL);
343      oldR= R;
344      //TODO normalize i.getItem over K(R)?
345      (void) sqrfNorm (i.getItem(), R, Extension, s, g, R);
346
347      backSubst.insert (s);
348
349      if (getCharacteristic() == 0)
350        Off (SW_RATIONAL);
351      R /= icontent (R);
352
353      if (getCharacteristic() == 0)
354        On (SW_RATIONAL);
355
356      if (!isFunctionField)
357      {
358        alpha= rootOf (R);
359        h= replacevar (g, g.mvar(), alpha);
360        if (getCharacteristic() == 0)
361          On (SW_RATIONAL); //needed for GCD
362        h= gcd (h, oldR);
363        h /= Lc (h);
364        ra= -h[0];
365        ra= replacevar(ra, alpha, g.mvar());
366        rb= R.mvar()-s*ra;
367        for (; j.hasItem(); j++)
368        {
369          j.getItem()= j.getItem() (ra, oldR.mvar());
370          j.getItem()= j.getItem() (rb, i.getItem().mvar());
371        }
372        prune (alpha);
373      }
374      else
375      {
376        if (getCharacteristic() == 0)
377          On (SW_RATIONAL);
378        Variable v= Variable (tmax (g.level(), oldR.level()) + 1);
379        h= swapvar (g, oldR.mvar(), v);
380        tmp= CFList (R);
381        h= alg_gcd (h, swapvar (oldR, oldR.mvar(), v), tmp);
382
383        CanonicalForm numinv, deninv;
384        numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
385
386        if (getCharacteristic() == 0)
387          Off (SW_RATIONAL);
388        h *= numinv;
389        h= reduce (h, tmp.getFirst());
390        deninv= LC(h);
391
392        ra= -h[0];
393        denra= gcd (ra, deninv);
394        ra /= denra;
395        denra= deninv/denra;
396        rb= R.mvar()*denra-s*ra;
397        denrb= denra;
398        for (; j.hasItem(); j++)
399        {
400          CanonicalForm powdenra= power (denra, degree (j.getItem(),
401                                                        oldR.mvar()));
402          j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
403          powdenra= power (denra, degree (j.getItem(), i.getItem().mvar()));
404          j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
405                                 i.getItem().mvar());
406        }
407      }
408
409      Returnlist.append (ra);
410      if (isFunctionField)
411        Returnlist.append (denra);
412    }
413  }
414  Returnlist.append (rb);
415  if (isFunctionField)
416    Returnlist.append (denrb);
417
418  if (isRat && getCharacteristic() == 0)
419    On (SW_RATIONAL);
420  else if (!isRat && getCharacteristic() == 0)
421    Off (SW_RATIONAL);
422
423  return Returnlist;
424}
425
426/// Trager's algorithm, i.e. convert to one field extension and
427/// factorize over this field extension
428static CFFList
429Trager (const CanonicalForm & F, const CFList & Astar,
430        const Variable & vminpoly, const CFList & as, bool isFunctionField)
431{
432  bool isRat= isOn (SW_RATIONAL);
433  CFFList L, normFactors, tmp;
434  CFFListIterator iter, iter2;
435  CanonicalForm R, Rstar, s, g, h, f= F;
436  CFList substlist, backSubsts;
437
438  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
439                              Rstar);
440
441  f= subst (f, Astar, substlist, Rstar, isFunctionField);
442
443  Variable alpha;
444  if (!isFunctionField)
445  {
446    alpha= rootOf (Rstar);
447    g= replacevar (f, Rstar.mvar(), alpha);
448
449    if (!isRat && getCharacteristic() == 0)
450      On (SW_RATIONAL);
451    tmp= factorize (g, alpha); // factorization over number field
452
453    for (iter= tmp; iter.hasItem(); iter++)
454    {
455      h= iter.getItem().factor();
456      if (!h.inCoeffDomain())
457      {
458        h= replacevar (h, alpha, Rstar.mvar());
459        h *= bCommonDen(h);
460        h= backSubst (h, backSubsts, Astar);
461        h= Prem (h, as);
462        L.append (CFFactor (h, iter.getItem().exp()));
463      }
464    }
465    if (!isRat && getCharacteristic() == 0)
466      Off (SW_RATIONAL);
467    prune (alpha);
468    return L;
469  }
470  // after here we are over an extension of a function field
471
472  // make quasi monic
473  CFList Rstarlist= CFList (Rstar);
474  int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
475  CanonicalForm numinv;
476  if (!isRat && getCharacteristic() == 0)
477    On (SW_RATIONAL);
478  numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());
479
480  f *= numinv;
481  f= Prem (f, Rstarlist);
482  f /= vcontent (f, Rstar.mvar());
483  // end quasi monic
484
485  if (degree (f) == 1)
486  {
487    f= backSubst (f, backSubsts, Astar);
488    f *= bCommonDen (f);
489    f= Prem (f, as);
490    f /= vcontent (f, as.getFirst().mvar());
491
492    return CFFList (CFFactor (f, 1));
493  }
494
495  CFGenerator * Gen;
496  if (getCharacteristic() == 0)
497    Gen= CFGenFactory::generate();
498  else if (degree (vminpoly) > 0)
499    Gen= AlgExtGenerator (vminpoly).clone();
500  else
501    Gen= CFGenFactory::generate();
502
503  CFFList LL= CFFList (CFFactor (f, 1));
504
505  Variable X;
506  do
507  {
508    tmp= CFFList();
509    for (iter= LL; iter.hasItem(); iter++)
510    {
511      f= iter.getItem().factor();
512      (void) norm (f, Rstar, *Gen, s, g, R, false);
513
514      if (hasFirstAlgVar (R, X))
515        normFactors= factorize (R, X);
516      else
517        normFactors= factorize (R);
518
519      if (normFactors.getFirst().factor().inCoeffDomain())
520        normFactors.removeFirst();
521      if (normFactors.length() == 1 && normFactors.getLast().exp() == 1)
522      {
523        f= backSubst (f, backSubsts, Astar);
524        f *= bCommonDen (f);
525        f= Prem (f, as);
526        f /= vcontent (f, as.getFirst().mvar());
527
528        L.append (CFFactor (f, 1));
529        break;
530      }
531      else
532      {
533        g= f;
534        int count= 0;
535        for (iter2= normFactors; iter2.hasItem(); iter2++)
536        {
537          CanonicalForm fnew= iter2.getItem().factor();
538          if (fnew.level() <= Rstar.level()) //factor is a constant from the function field
539            continue;
540          else
541          {
542            fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
543            fnew= reduce (fnew, Rstar);
544          }
545
546          h= alg_gcd (g, fnew, Rstarlist);
547          numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
548          h *= numinv;
549          h= Prem (h, Rstarlist);
550          h /= vcontent (h, Rstar.mvar());
551
552          if (h.level() > Rstar.level())
553          {
554            g= divide (g, h, Rstarlist);
555            if (degree (h) == 1 || iter2.getItem().exp() == 1)
556            {
557              h= backSubst (h, backSubsts, Astar);
558              h= Prem (h, as);
559              h *= bCommonDen (h);
560              h /= vcontent (h, as.getFirst().mvar());
561              L.append (CFFactor (h, 1));
562            }
563            else
564              tmp.append (CFFactor (h, iter2.getItem().exp()));
565          }
566          count++;
567          if (g.level() <= Rstar.level())
568            break;
569          if (count == normFactors.length() - 1)
570          {
571            if (normFactors.getLast().exp() == 1 && g.level() > Rstar.level())
572            {
573              g= backSubst (g, backSubsts, Astar);
574              g= Prem (g, as);
575              g *= bCommonDen (g);
576              g /= vcontent (g, as.getFirst().mvar());
577              L.append (CFFactor (g, 1));
578            }
579            else if (normFactors.getLast().exp() > 1 &&
580                     g.level() > Rstar.level())
581            {
582              g /= vcontent (g, Rstar.mvar());
583              tmp.append (CFFactor (g, normFactors.getLast().exp()));
584            }
585            break;
586          }
587        }
588      }
589    }
590    LL= tmp;
591    (*Gen).next();
592  }
593  while (!LL.isEmpty());
594
595  if (!isRat && getCharacteristic() == 0)
596    Off (SW_RATIONAL);
597
598  delete Gen;
599
600  return L;
601}
602
603
604/// map elements in @a AS into a PIE \f$ L \f$ and record where the variables
605/// are mapped to in @a varsMapLevel, i.e @a varsMapLevel contains a list of
606/// pairs of variables \f$ v_i \f$ and integers \f$ e_i \f$ such that
607/// \f$ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) \f$
608CFList
609mapIntoPIE (CFFList& varsMapLevel, CanonicalForm& lcmVars, const CFList & AS)
610{
611  CanonicalForm varsG;
612  int j, exp= 0, tmpExp;
613  bool recurse= false;
614  CFList asnew, as= AS;
615  CFListIterator i= as, ii;
616  CFFList varsGMapLevel, tmp;
617  CFFListIterator iter;
618  CFFList * varsGMap= new CFFList [as.length()];
619  for (j= 0; j < as.length(); j++)
620    varsGMap[j]= CFFList();
621  j= 0;
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  for (j= 0; j < as.length(); j++)
731  {
732    if (varsGMap[j].isEmpty())
733      continue;
734
735    for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
736    {
737      for (iter= varsMapLevel; iter.hasItem(); iter++)
738      {
739        if (iter.getItem().factor() == iter2.getItem().factor())
740        {
741          iter.getItem()= CFFactor (iter.getItem().factor(),
742                                  iter.getItem().exp() + iter2.getItem().exp());
743        }
744      }
745    }
746  }
747
748  delete [] varsGMap;
749
750  return asnew;
751}
752
753/// algorithm of A. Steel described in "Conquering Inseparability: Primary
754/// decomposition and multivariate factorization over algebraic function fields
755/// of positive characteristic" with the following modifications: we use
756/// characteristic sets in IdealOverSubfield and Trager's primitive element
757/// algorithm instead of FGLM
758CFFList
759SteelTrager (const CanonicalForm & f, const CFList & AS)
760{
761  CanonicalForm F= f, lcmVars= 1;
762  CFList asnew, as= AS;
763  CFListIterator i, ii;
764
765  bool derivZeroF= false;
766  int j, expF= 0, tmpExp;
767  CFFList varsMapLevel, tmp;
768  CFFListIterator iter;
769
770  // check if F is separable
771  if (F.deriv().isZero())
772  {
773    derivZeroF= true;
774    deflateDegree (F, expF, F.level());
775  }
776
777  CanonicalForm varsF= getVars (F);
778  varsF /= F.mvar();
779
780  lcmVars= lcm (varsF, lcmVars);
781
782  if (derivZeroF)
783    as.append (F);
784
785  asnew= mapIntoPIE (varsMapLevel, lcmVars, as);
786
787  if (derivZeroF)
788  {
789    asnew.removeLast();
790    F= deflatePoly (F, expF, F.level());
791  }
792
793  // map variables in F
794  for (iter= varsMapLevel; iter.hasItem(); iter++)
795  {
796    if (expF > 0)
797      tmpExp= iter.getItem().exp() - expF;
798    else
799      tmpExp= iter.getItem().exp();
800
801    if (tmpExp > 0)
802      F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
803    else if (tmpExp < 0)
804      F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
805  }
806
807  // factor F with minimal polys given in asnew
808  asnew.append (F);
809  asnew= charSetViaModCharSet (asnew, false);
810
811  F= asnew.getLast();
812  F /= content (F);
813
814  asnew.removeLast();
815  for (i= asnew; i.hasItem(); i++)
816    i.getItem() /= content (i.getItem());
817
818  tmp= facAlgFunc (F, asnew);
819
820  // transform back
821  j= 0;
822  int p= getCharacteristic();
823  CFList transBack;
824  CFMap M;
825  CanonicalForm g;
826
827  for (iter= varsMapLevel; iter.hasItem(); iter++)
828  {
829    if (iter.getItem().exp() > 0)
830    {
831      j++;
832      g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
833         iter.getItem().factor().mvar();
834      transBack.append (g);
835      M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
836    }
837  }
838
839  for (i= asnew; i.hasItem(); i++)
840    transBack.insert (M (i.getItem()));
841
842  if (expF > 0)
843    tmpExp= ipower (p, expF);
844
845  CFFList result;
846  CFList transform;
847
848  bool found;
849  for (iter= tmp; iter.hasItem(); iter++)
850  {
851    found= false;
852    transform= transBack;
853    CanonicalForm factor= iter.getItem().factor();
854    factor= M (factor);
855    transform.append (factor);
856    transform= modCharSet (transform, false);
857
858retry:
859    if (transform.isEmpty())
860    {
861      transform= transBack;
862      transform.append (factor);
863      transform= charSetViaCharSetN (transform);
864    }
865    for (i= transform; i.hasItem(); i++)
866    {
867      if (degree (i.getItem(), f.mvar()) > 0)
868      {
869        if (i.getItem().level() > f.level())
870          break;
871        found= true;
872        factor= i.getItem();
873        break;
874      }
875    }
876
877    if (!found)
878    {
879      found= false;
880      transform= CFList();
881      goto retry;
882    }
883
884    factor /= content (factor);
885
886    if (expF > 0)
887    {
888      int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
889      result.append (CFFactor (factor, iter.getItem().exp()*mult));
890    }
891    else
892      result.append (CFFactor (factor, iter.getItem().exp()));
893  }
894
895  return result;
896}
897
898/// factorize a polynomial that is irreducible over the ground field modulo an
899/// extension given by an irreducible characteristic set
900
901// 1) prepares data
902// 2) for char=p we distinguish 3 cases:
903//           no transcendentals, separable and inseparable extensions
904CFFList
905facAlgFunc2 (const CanonicalForm & f, const CFList & as)
906{
907  bool isRat= isOn (SW_RATIONAL);
908  if (!isRat && getCharacteristic() == 0)
909    On (SW_RATIONAL);
910  Variable vf=f.mvar();
911  CFListIterator i;
912  CFFListIterator jj;
913  CFList reduceresult;
914  CFFList result;
915
916// F1: [Test trivial cases]
917// 1) first trivial cases:
918  if (vf.level() <= as.getLast().level())
919  {
920    if (!isRat && getCharacteristic() == 0)
921      Off (SW_RATIONAL);
922    return CFFList(CFFactor(f,1));
923  }
924
925// 2) Setup list of those polys in AS having degree > 1
926  CFList Astar;
927  Variable x;
928  CanonicalForm elem;
929  Varlist ord, uord;
930  for (int ii= 1; ii < level (vf); ii++)
931    uord.append (Variable (ii));
932
933  for (i= as; i.hasItem(); i++)
934  {
935    elem= i.getItem();
936    x= elem.mvar();
937    if (degree (elem, x) > 1)  // otherwise it's not an extension
938    {
939      Astar.append (elem);
940      ord.append (x);
941    }
942  }
943  uord= Difference (uord, ord);
944
945// 3) second trivial cases: we already proved irr. of f over no extensions
946  if (Astar.length() == 0)
947  {
948    if (!isRat && getCharacteristic() == 0)
949      Off (SW_RATIONAL);
950    return CFFList (CFFactor (f, 1));
951  }
952
953// 4) Look if elements in uord actually occur in any of the minimal
954//    polynomials. If no element of uord occures in any of the minimal
955//    polynomials the field is an alg. number field not an alg. function field
956  Varlist newuord= varsInAs (uord, Astar);
957
958  CFFList Factorlist;
959  Varlist gcdord= Union (ord, newuord);
960  gcdord.append (f.mvar());
961  bool isFunctionField= (newuord.length() > 0);
962
963  // TODO alg_sqrfree?
964  CanonicalForm Fgcd= 0;
965  if (isFunctionField)
966    Fgcd= alg_gcd (f, f.deriv(), Astar);
967
968  bool derivZero= f.deriv().isZero();
969  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
970  {
971    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
972    if (getCharacteristic() == 0)
973    {
974      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
975      multiplicity (result, f, Astar);
976      if (!isRat && getCharacteristic() == 0)
977        Off (SW_RATIONAL);
978      return result;
979    }
980
981    Fgcd= pp (Fgcd);
982    Ggcd= pp (Ggcd);
983    if (!isRat && getCharacteristic() == 0)
984      Off (SW_RATIONAL);
985    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
986  }
987
988  if (getCharacteristic() > 0)
989  {
990    IntList degreelist;
991    Variable vminpoly;
992    for (i= Astar; i.hasItem(); i++)
993      degreelist.append (degree (i.getItem()));
994
995    int extdeg= getDegOfExt (degreelist, degree (f));
996
997    if (newuord.length() == 0) // no parameters
998    {
999      if (extdeg > 1)
1000      {
1001        CanonicalForm MIPO= generateMipo (extdeg);
1002        vminpoly= rootOf(MIPO);
1003      }
1004      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
1005      if (extdeg > 1)
1006        prune (vminpoly);
1007      return Factorlist;
1008    }
1009    else if (isInseparable(Astar) || derivZero) // inseparable case
1010    {
1011      Factorlist= SteelTrager (f, Astar);
1012      return Factorlist;
1013    }
1014    else // separable case
1015    {
1016      if (extdeg > 1)
1017      {
1018        CanonicalForm MIPO=generateMipo (extdeg);
1019        vminpoly= rootOf (MIPO);
1020      }
1021      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1022      if (extdeg > 1)
1023        prune (vminpoly);
1024      return Factorlist;
1025    }
1026  }
1027  else // char 0
1028  {
1029    Variable vminpoly;
1030    Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1031    if (!isRat && getCharacteristic() == 0)
1032      Off (SW_RATIONAL);
1033    return Factorlist;
1034  }
1035
1036  return CFFList (CFFactor(f,1));
1037}
1038
1039
1040/// factorize a polynomial modulo an extension given by an irreducible
1041/// characteristic set
1042CFFList
1043facAlgFunc (const CanonicalForm & f, const CFList & as)
1044{
1045  bool isRat= isOn (SW_RATIONAL);
1046  if (!isRat && getCharacteristic() == 0)
1047    On (SW_RATIONAL);
1048  CFFList Output, output, Factors= factorize(f);
1049  if (Factors.getFirst().factor().inCoeffDomain())
1050    Factors.removeFirst();
1051
1052  if (as.length() == 0)
1053  {
1054    if (!isRat && getCharacteristic() == 0)
1055      Off (SW_RATIONAL);
1056    return Factors;
1057  }
1058  if (f.level() <= as.getLast().level())
1059  {
1060    if (!isRat && getCharacteristic() == 0)
1061      Off (SW_RATIONAL);
1062    return Factors;
1063  }
1064
1065  for (CFFListIterator i=Factors; i.hasItem(); i++)
1066  {
1067    if (i.getItem().factor().level() > as.getLast().level())
1068    {
1069      output= facAlgFunc2 (i.getItem().factor(), as);
1070      for (CFFListIterator j= output; j.hasItem(); j++)
1071        Output= append (Output, CFFactor (j.getItem().factor(),
1072                                          j.getItem().exp()*i.getItem().exp()));
1073    }
1074  }
1075
1076  if (!isRat && getCharacteristic() == 0)
1077    Off (SW_RATIONAL);
1078  return Output;
1079}
Note: See TracBrowser for help on using the repository browser.