source: git/factory/facAlgFunc.cc @ 517ffa

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