source: git/factory/facAlgFunc.cc @ 2c8d8eb

spielwiese
Last change on this file since 2c8d8eb was 2c8d8eb, checked in by Martin Lee <martinlee84@…>, 9 years ago
fix: stupid erroneous break
  • 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() (rb, i.getItem().mvar());
370          j.getItem()= j.getItem() (ra, oldR.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        h *= numinv;
386        h= Prem (h, tmp);
387        deninv= LC(h);
388
389        ra= -h[0];
390        denra= gcd (ra, deninv);
391        ra /= denra;
392        denra= deninv/denra;
393        rb= R.mvar()*denra-s*ra;
394        denrb= denra;
395        for (; j.hasItem(); j++)
396        {
397          CanonicalForm powdenra= power (denra, degree (j.getItem(),
398                                         i.getItem().mvar()));
399          j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
400                                 i.getItem().mvar());
401          powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
402          j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
403
404        }
405      }
406
407      Returnlist.append (ra);
408      if (isFunctionField)
409        Returnlist.append (denra);
410    }
411  }
412  Returnlist.append (rb);
413  if (isFunctionField)
414    Returnlist.append (denrb);
415
416  if (isRat && getCharacteristic() == 0)
417    On (SW_RATIONAL);
418  else if (!isRat && getCharacteristic() == 0)
419    Off (SW_RATIONAL);
420
421  return Returnlist;
422}
423
424/// Trager's algorithm, i.e. convert to one field extension and
425/// factorize over this field extension
426static CFFList
427Trager (const CanonicalForm & F, const CFList & Astar,
428        const Variable & vminpoly, const CFList & as, bool isFunctionField)
429{
430  bool isRat= isOn (SW_RATIONAL);
431  CFFList L, normFactors, tmp;
432  CFFListIterator iter, iter2;
433  CanonicalForm R, Rstar, s, g, h, f= F;
434  CFList substlist, backSubsts;
435
436  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
437                              Rstar);
438
439  f= subst (f, Astar, substlist, Rstar, isFunctionField);
440
441  Variable alpha;
442  if (!isFunctionField)
443  {
444    alpha= rootOf (Rstar);
445    g= replacevar (f, Rstar.mvar(), alpha);
446
447    if (!isRat && getCharacteristic() == 0)
448      On (SW_RATIONAL);
449    tmp= factorize (g, alpha); // factorization over number field
450
451    for (iter= tmp; iter.hasItem(); iter++)
452    {
453      h= iter.getItem().factor();
454      if (!h.inCoeffDomain())
455      {
456        h= replacevar (h, alpha, Rstar.mvar());
457        h *= bCommonDen(h);
458        h= backSubst (h, backSubsts, Astar);
459        h= Prem (h, as);
460        L.append (CFFactor (h, iter.getItem().exp()));
461      }
462    }
463    if (!isRat && getCharacteristic() == 0)
464      Off (SW_RATIONAL);
465    prune (alpha);
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      (void) norm (f, Rstar, *Gen, s, g, R, false);
511
512      if (hasFirstAlgVar (R, X))
513        normFactors= factorize (R, X);
514      else
515        normFactors= factorize (R);
516
517      if (normFactors.getFirst().factor().inCoeffDomain())
518        normFactors.removeFirst();
519      if (normFactors.length() < 1 || (normFactors.length() == 1 && normFactors.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      }
528      else
529      {
530        g= f;
531        int count= 0;
532        for (iter2= normFactors; 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= Prem (fnew, CFList (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          count++;
564          if (g.level() <= Rstar.level())
565            break;
566          if (count == normFactors.length() - 1)
567          {
568            if (normFactors.getLast().exp() == 1 && g.level() > Rstar.level())
569            {
570              g= backSubst (g, backSubsts, Astar);
571              g= Prem (g, as);
572              g *= bCommonDen (g);
573              g /= vcontent (g, as.getFirst().mvar());
574              L.append (CFFactor (g, 1));
575            }
576            else if (normFactors.getLast().exp() > 1 &&
577                     g.level() > Rstar.level())
578            {
579              g /= vcontent (g, Rstar.mvar());
580              tmp.append (CFFactor (g, normFactors.getLast().exp()));
581            }
582            break;
583          }
584        }
585      }
586    }
587    LL= tmp;
588    (*Gen).next();
589  }
590  while (!LL.isEmpty());
591
592  if (!isRat && getCharacteristic() == 0)
593    Off (SW_RATIONAL);
594
595  delete Gen;
596
597  return L;
598}
599
600
601/// map elements in @a AS into a PIE \f$ L \f$ and record where the variables
602/// are mapped to in @a varsMapLevel, i.e @a varsMapLevel contains a list of
603/// pairs of variables \f$ v_i \f$ and integers \f$ e_i \f$ such that
604/// \f$ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) \f$
605CFList
606mapIntoPIE (CFFList& varsMapLevel, CanonicalForm& lcmVars, const CFList & AS)
607{
608  CanonicalForm varsG;
609  int j, exp= 0, tmpExp;
610  bool recurse= false;
611  CFList asnew, as= AS;
612  CFListIterator i= as, ii;
613  CFFList varsGMapLevel, tmp;
614  CFFListIterator iter;
615  CFFList * varsGMap= new CFFList [as.length()];
616  for (j= 0; j < as.length(); j++)
617    varsGMap[j]= CFFList();
618  j= 0;
619  while (i.hasItem())
620  {
621    if (i.getItem().deriv() == 0)
622    {
623      deflateDegree (i.getItem(), exp, i.getItem().level());
624      i.getItem()= deflatePoly (i.getItem(), exp, i.getItem().level());
625
626      varsG= getVars (i.getItem());
627      varsG /= i.getItem().mvar();
628
629      lcmVars= lcm (varsG, lcmVars);
630
631      while (!varsG.isOne())
632      {
633        if (i.getItem().deriv (varsG.level()).isZero())
634        {
635          deflateDegree (i.getItem(), tmpExp, varsG.level());
636          if (exp >= tmpExp)
637          {
638            if (exp == tmpExp)
639              i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
640            else
641            {
642              if (j != 0)
643                recurse= true;
644              i.getItem()= deflatePoly (i.getItem(), tmpExp, varsG.level());
645            }
646            varsGMapLevel.insert (CFFactor (varsG.mvar(), exp - tmpExp));
647          }
648          else
649          {
650            i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
651            varsGMapLevel.insert (CFFactor (varsG.mvar(), 0));
652          }
653        }
654        else
655        {
656          if (j != 0)
657            recurse= true;
658          varsGMapLevel.insert (CFFactor (varsG.mvar(),exp));
659        }
660        varsG /= varsG.mvar();
661      }
662
663      if (recurse)
664      {
665        ii= as;
666        for (; ii.hasItem(); ii++)
667        {
668          if (ii.getItem() == i.getItem())
669            continue;
670          for (iter= varsGMapLevel; iter.hasItem(); iter++)
671            ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
672                                       iter.getItem().factor().level());
673        }
674      }
675      else
676      {
677        ii= i;
678        ii++;
679        for (; ii.hasItem(); ii++)
680        {
681          for (iter= varsGMapLevel; iter.hasItem(); iter++)
682          {
683            ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
684                                       iter.getItem().factor().level());
685          }
686        }
687      }
688      if (varsGMap[j].isEmpty())
689        varsGMap[j]= varsGMapLevel;
690      else
691      {
692        if (!varsGMapLevel.isEmpty())
693        {
694          tmp= varsGMap[j];
695          CFFListIterator iter2= varsGMapLevel;
696          ASSERT (tmp.length() == varsGMapLevel.length(),
697                  "wrong length of lists");
698          for (iter=tmp; iter.hasItem(); iter++, iter2++)
699            iter.getItem()= CFFactor (iter.getItem().factor(),
700                                  iter.getItem().exp() + iter2.getItem().exp());
701          varsGMap[j]= tmp;
702        }
703      }
704      varsGMapLevel= CFFList();
705    }
706    asnew.append (i.getItem());
707    if (!recurse)
708    {
709      i++;
710      j++;
711    }
712    else
713    {
714      i= as;
715      j= 0;
716      recurse= false;
717      asnew= CFList();
718    }
719  }
720
721  while (!lcmVars.isOne())
722  {
723    varsMapLevel.insert (CFFactor (lcmVars.mvar(), 0));
724    lcmVars /= lcmVars.mvar();
725  }
726
727  for (j= 0; j < as.length(); j++)
728  {
729    if (varsGMap[j].isEmpty())
730      continue;
731
732    for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
733    {
734      for (iter= varsMapLevel; iter.hasItem(); iter++)
735      {
736        if (iter.getItem().factor() == iter2.getItem().factor())
737        {
738          iter.getItem()= CFFactor (iter.getItem().factor(),
739                                  iter.getItem().exp() + iter2.getItem().exp());
740        }
741      }
742    }
743  }
744
745  delete [] varsGMap;
746
747  return asnew;
748}
749
750/// algorithm of A. Steel described in "Conquering Inseparability: Primary
751/// decomposition and multivariate factorization over algebraic function fields
752/// of positive characteristic" with the following modifications: we use
753/// characteristic sets in IdealOverSubfield and Trager's primitive element
754/// algorithm instead of FGLM
755CFFList
756SteelTrager (const CanonicalForm & f, const CFList & AS)
757{
758  CanonicalForm F= f, lcmVars= 1;
759  CFList asnew, as= AS;
760  CFListIterator i, ii;
761
762  bool derivZeroF= false;
763  int j, expF= 0, tmpExp;
764  CFFList varsMapLevel, tmp;
765  CFFListIterator iter;
766
767  // check if F is separable
768  if (F.deriv().isZero())
769  {
770    derivZeroF= true;
771    deflateDegree (F, expF, F.level());
772  }
773
774  CanonicalForm varsF= getVars (F);
775  varsF /= F.mvar();
776
777  lcmVars= lcm (varsF, lcmVars);
778
779  if (derivZeroF)
780    as.append (F);
781
782  asnew= mapIntoPIE (varsMapLevel, lcmVars, as);
783
784  if (derivZeroF)
785  {
786    asnew.removeLast();
787    F= deflatePoly (F, expF, F.level());
788  }
789
790  // map variables in F
791  for (iter= varsMapLevel; iter.hasItem(); iter++)
792  {
793    if (expF > 0)
794      tmpExp= iter.getItem().exp() - expF;
795    else
796      tmpExp= iter.getItem().exp();
797
798    if (tmpExp > 0)
799      F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
800    else if (tmpExp < 0)
801      F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
802  }
803
804  // factor F with minimal polys given in asnew
805  asnew.append (F);
806  asnew= charSetViaModCharSet (asnew, false);
807
808  F= asnew.getLast();
809  F /= content (F);
810
811  asnew.removeLast();
812  for (i= asnew; i.hasItem(); i++)
813    i.getItem() /= content (i.getItem());
814
815  tmp= facAlgFunc (F, asnew);
816
817  // transform back
818  j= 0;
819  int p= getCharacteristic();
820  CFList transBack;
821  CFMap M;
822  CanonicalForm g;
823
824  for (iter= varsMapLevel; iter.hasItem(); iter++)
825  {
826    if (iter.getItem().exp() > 0)
827    {
828      j++;
829      g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
830         iter.getItem().factor().mvar();
831      transBack.append (g);
832      M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
833    }
834  }
835
836  for (i= asnew; i.hasItem(); i++)
837    transBack.insert (M (i.getItem()));
838
839  if (expF > 0)
840    tmpExp= ipower (p, expF);
841
842  CFFList result;
843  CFList transform;
844
845  bool found;
846  for (iter= tmp; iter.hasItem(); iter++)
847  {
848    found= false;
849    transform= transBack;
850    CanonicalForm factor= iter.getItem().factor();
851    factor= M (factor);
852    transform.append (factor);
853    transform= modCharSet (transform, false);
854
855retry:
856    if (transform.isEmpty())
857    {
858      transform= transBack;
859      transform.append (factor);
860      transform= charSetViaCharSetN (transform);
861    }
862    for (i= transform; i.hasItem(); i++)
863    {
864      if (degree (i.getItem(), f.mvar()) > 0)
865      {
866        if (i.getItem().level() > f.level())
867          break;
868        found= true;
869        factor= i.getItem();
870        break;
871      }
872    }
873
874    if (!found)
875    {
876      found= false;
877      transform= CFList();
878      goto retry;
879    }
880
881    factor /= content (factor);
882
883    if (expF > 0)
884    {
885      int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
886      result.append (CFFactor (factor, iter.getItem().exp()*mult));
887    }
888    else
889      result.append (CFFactor (factor, iter.getItem().exp()));
890  }
891
892  return result;
893}
894
895/// factorize a polynomial that is irreducible over the ground field modulo an
896/// extension given by an irreducible characteristic set
897
898// 1) prepares data
899// 2) for char=p we distinguish 3 cases:
900//           no transcendentals, separable and inseparable extensions
901CFFList
902facAlgFunc2 (const CanonicalForm & f, const CFList & as)
903{
904  bool isRat= isOn (SW_RATIONAL);
905  if (!isRat && getCharacteristic() == 0)
906    On (SW_RATIONAL);
907  Variable vf=f.mvar();
908  CFListIterator i;
909  CFFListIterator jj;
910  CFList reduceresult;
911  CFFList result;
912
913// F1: [Test trivial cases]
914// 1) first trivial cases:
915  if (vf.level() <= as.getLast().level())
916  {
917    if (!isRat && getCharacteristic() == 0)
918      Off (SW_RATIONAL);
919    return CFFList(CFFactor(f,1));
920  }
921
922// 2) Setup list of those polys in AS having degree > 1
923  CFList Astar;
924  Variable x;
925  CanonicalForm elem;
926  Varlist ord, uord;
927  for (int ii= 1; ii < level (vf); ii++)
928    uord.append (Variable (ii));
929
930  for (i= as; i.hasItem(); i++)
931  {
932    elem= i.getItem();
933    x= elem.mvar();
934    if (degree (elem, x) > 1)  // otherwise it's not an extension
935    {
936      Astar.append (elem);
937      ord.append (x);
938    }
939  }
940  uord= Difference (uord, ord);
941
942// 3) second trivial cases: we already proved irr. of f over no extensions
943  if (Astar.length() == 0)
944  {
945    if (!isRat && getCharacteristic() == 0)
946      Off (SW_RATIONAL);
947    return CFFList (CFFactor (f, 1));
948  }
949
950// 4) Look if elements in uord actually occur in any of the minimal
951//    polynomials. If no element of uord occures in any of the minimal
952//    polynomials the field is an alg. number field not an alg. function field
953  Varlist newuord= varsInAs (uord, Astar);
954
955  CFFList Factorlist;
956  Varlist gcdord= Union (ord, newuord);
957  gcdord.append (f.mvar());
958  bool isFunctionField= (newuord.length() > 0);
959
960  // TODO alg_sqrfree?
961  CanonicalForm Fgcd= 0;
962  if (isFunctionField)
963    Fgcd= alg_gcd (f, f.deriv(), Astar);
964
965  bool derivZero= f.deriv().isZero();
966  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
967  {
968    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
969    if (getCharacteristic() == 0)
970    {
971      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
972      multiplicity (result, f, Astar);
973      if (!isRat && getCharacteristic() == 0)
974        Off (SW_RATIONAL);
975      return result;
976    }
977
978    Fgcd= pp (Fgcd);
979    Ggcd= pp (Ggcd);
980    if (!isRat && getCharacteristic() == 0)
981      Off (SW_RATIONAL);
982    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
983  }
984
985  if (getCharacteristic() > 0)
986  {
987    IntList degreelist;
988    Variable vminpoly;
989    for (i= Astar; i.hasItem(); i++)
990      degreelist.append (degree (i.getItem()));
991
992    int extdeg= getDegOfExt (degreelist, degree (f));
993
994    if (newuord.length() == 0) // no parameters
995    {
996      if (extdeg > 1)
997      {
998        CanonicalForm MIPO= generateMipo (extdeg);
999        vminpoly= rootOf(MIPO);
1000      }
1001      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
1002      if (extdeg > 1)
1003        prune (vminpoly);
1004      return Factorlist;
1005    }
1006    else if (isInseparable(Astar) || derivZero) // inseparable case
1007    {
1008      Factorlist= SteelTrager (f, Astar);
1009      return Factorlist;
1010    }
1011    else // separable case
1012    {
1013      if (extdeg > 1)
1014      {
1015        CanonicalForm MIPO=generateMipo (extdeg);
1016        vminpoly= rootOf (MIPO);
1017      }
1018      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1019      if (extdeg > 1)
1020        prune (vminpoly);
1021      return Factorlist;
1022    }
1023  }
1024  else // char 0
1025  {
1026    Variable vminpoly;
1027    Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1028    if (!isRat && getCharacteristic() == 0)
1029      Off (SW_RATIONAL);
1030    return Factorlist;
1031  }
1032
1033  return CFFList (CFFactor(f,1));
1034}
1035
1036
1037/// factorize a polynomial modulo an extension given by an irreducible
1038/// characteristic set
1039CFFList
1040facAlgFunc (const CanonicalForm & f, const CFList & as)
1041{
1042  bool isRat= isOn (SW_RATIONAL);
1043  if (!isRat && getCharacteristic() == 0)
1044    On (SW_RATIONAL);
1045  CFFList Output, output, Factors= factorize(f);
1046  if (Factors.getFirst().factor().inCoeffDomain())
1047    Factors.removeFirst();
1048
1049  if (as.length() == 0)
1050  {
1051    if (!isRat && getCharacteristic() == 0)
1052      Off (SW_RATIONAL);
1053    return Factors;
1054  }
1055  if (f.level() <= as.getLast().level())
1056  {
1057    if (!isRat && getCharacteristic() == 0)
1058      Off (SW_RATIONAL);
1059    return Factors;
1060  }
1061
1062  for (CFFListIterator i=Factors; i.hasItem(); i++)
1063  {
1064    if (i.getItem().factor().level() > as.getLast().level())
1065    {
1066      output= facAlgFunc2 (i.getItem().factor(), as);
1067      for (CFFListIterator j= output; j.hasItem(); j++)
1068        Output= append (Output, CFFactor (j.getItem().factor(),
1069                                          j.getItem().exp()*i.getItem().exp()));
1070    }
1071  }
1072
1073  if (!isRat && getCharacteristic() == 0)
1074    Off (SW_RATIONAL);
1075  return Output;
1076}
Note: See TracBrowser for help on using the repository browser.