Functions
facAlgFunc.cc File Reference

This file provides functions to factorize polynomials over alg. More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_generator.h"
#include "cf_iter.h"
#include "cf_util.h"
#include "cf_algorithm.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "cfModResultant.h"
#include "cfCharSets.h"
#include "facAlgFunc.h"
#include "facAlgFuncUtil.h"

Go to the source code of this file.

Functions

void out_cf (const char *s1, const CanonicalForm &f, const char *s2)
 cf_algorithm.cc - simple mathematical algorithms. More...
 
CanonicalForm alg_content (const CanonicalForm &f, const CFList &as)
 
CanonicalForm alg_gcd (const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
 
static CanonicalForm resultante (const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
 
static CFFList norm (const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
 compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addition getCharacteristic() > 0 the squarefree factors of R are returned. Based on Trager's sqrf_norm algorithm. More...
 
static CFFList sqrfNorm (const CanonicalForm &f, const CanonicalForm &PPalpha, const Variable &Extension, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R)
 see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm. More...
 
static CFList simpleExtension (CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
 
static CFFList Trager (const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
 Trager's algorithm, i.e. convert to one field extension and factorize over this field extension. More...
 
CFList mapIntoPIE (CFFList &varsMapLevel, CanonicalForm &lcmVars, const CFList &AS)
 map elements in AS into a PIE $ L $ and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables $ v_i $ and integers $ e_i $ such that $ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) $ More...
 
CFFList SteelTrager (const CanonicalForm &f, const CFList &AS)
 algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic" with the following modifications: we use characteristic sets in IdealOverSubfield and Trager's primitive element algorithm instead of FGLM More...
 
CFFList facAlgFunc2 (const CanonicalForm &f, const CFList &as)
 factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set More...
 
CFFList facAlgFunc (const CanonicalForm &f, const CFList &as)
 factorize a polynomial modulo an extension given by an irreducible characteristic set More...
 

Detailed Description

This file provides functions to factorize polynomials over alg.

function fields

Note
some of the code is code from libfac or derived from code from libfac. Libfac is written by M. Messollen. See also COPYING for license information and README for general information on characteristic sets.

ABSTRACT: Descriptions can be found in B. Trager "Algebraic Factoring and Rational Function Integration" and A. Steel "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic"

Author
Martin Lee

Definition in file facAlgFunc.cc.

Function Documentation

CanonicalForm alg_content ( const CanonicalForm f,
const CFList as 
)

Definition at line 42 of file facAlgFunc.cc.

43 {
44  if (!f.inCoeffDomain())
45  {
46  CFIterator i= f;
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 }
bool inCoeffDomain() const
factory's main class
Definition: canonicalform.h:75
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
return result
Definition: facAbsBiFact.cc:76
CanonicalForm alg_gcd ( const CanonicalForm fff,
const CanonicalForm ggg,
const CFList as 
)

Definition at line 61 of file facAlgFunc.cc.

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 
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 }
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
factory&#39;s class for variables
Definition: variable.h:32
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int level() const
level() returns the level of CO.
poly res
Definition: myNF.cc:322
const ring r
Definition: syzextra.cc:208
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
CFList tmp2
Definition: facFqBivar.cc:70
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
int gcd(int a, int b)
Definition: walkSupport.cc:839
T getLast() const
Definition: ftmpl_list.cc:309
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
bool inBaseDomain() const
int degree(const CanonicalForm &f)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
int hasVar(const CanonicalForm &f, const Variable &v)
int sign() const
int CanonicalForm::sign () const
CFFList facAlgFunc ( const CanonicalForm f,
const CFList as 
)

factorize a polynomial modulo an extension given by an irreducible characteristic set

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

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 }
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
Definition: facAlgFunc.cc:905
void Off(int sw)
switches
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
int level() const
level() returns the level of CO.
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
int j
Definition: myNF.cc:70
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CFFList facAlgFunc2 ( const CanonicalForm f,
const CFList as 
)

factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

906 {
907  bool isRat= isOn (SW_RATIONAL);
908  if (!isRat && getCharacteristic() == 0)
909  On (SW_RATIONAL);
910  Variable vf=f.mvar();
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 }
int level() const
Definition: variable.h:49
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
int level(const CanonicalForm &f)
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
Definition: facAlgFunc.cc:905
void Off(int sw)
switches
CanonicalForm generateMipo(int degOfExt)
factory&#39;s class for variables
Definition: variable.h:32
static CFFList Trager(const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
Trager&#39;s algorithm, i.e. convert to one field extension and factorize over this field extension...
Definition: facAlgFunc.cc:430
int getDegOfExt(IntList &degreelist, int n)
static int * multiplicity
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
factory&#39;s main class
Definition: canonicalform.h:75
List< CFFactor > CFFList
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
int getCharacteristic()
Definition: cf_char.cc:51
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
poly pp
Definition: myNF.cc:296
int level() const
level() returns the level of CO.
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isInseparable(const CFList &Astar)
bool isOn(int sw)
switches
void On(int sw)
switches
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
T & getItem() const
Definition: ftmpl_list.cc:431
Factor< CanonicalForm > CFFactor
T getLast() const
Definition: ftmpl_list.cc:309
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
CFList mapIntoPIE ( CFFList varsMapLevel,
CanonicalForm lcmVars,
const CFList AS 
)

map elements in AS into a PIE $ L $ and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables $ v_i $ and integers $ e_i $ such that $ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) $

Definition at line 609 of file facAlgFunc.cc.

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;
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 }
List< CanonicalForm > CFList
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
List< CFFactor > CFFList
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
int isEmpty() const
Definition: ftmpl_list.cc:267
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
Factor< CanonicalForm > CFFactor
bool isZero(const CFArray &A)
checks if entries of A are zero
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
#define ASSERT(expression, message)
Definition: cf_assert.h:99
p exp[i]
Definition: DebugPrint.cc:39
void append(const T &)
Definition: ftmpl_list.cc:256
static CFFList norm ( const CanonicalForm f,
const CanonicalForm PPalpha,
CFGenerator myrandom,
CanonicalForm s,
CanonicalForm g,
CanonicalForm R,
bool  proof 
)
static

compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addition getCharacteristic() > 0 the squarefree factors of R are returned. Based on Trager's sqrf_norm algorithm.

Definition at line 206 of file facAlgFunc.cc.

209 {
210  Variable y= PPalpha.mvar(), vf= f.mvar();
211  CanonicalForm temp, Palpha= PPalpha, t;
212  int sqfreetest= 0;
213  CFFList testlist;
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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
factory&#39;s class for variables
Definition: variable.h:32
factory&#39;s main class
Definition: canonicalform.h:75
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Definition: facAlgFunc.cc:179
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CanonicalForm genZero() const
genOne(), genZero()
T getFirst() const
Definition: ftmpl_list.cc:279
virtual CanonicalForm item() const
Definition: cf_generator.h:28
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
virtual void reset()
Definition: cf_generator.h:27
T & getItem() const
Definition: ftmpl_list.cc:431
int gcd(int a, int b)
Definition: walkSupport.cc:839
int degree(const CanonicalForm &f)
virtual void next()
Definition: cf_generator.h:29
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
void out_cf ( const char *  s1,
const CanonicalForm f,
const char *  s2 
)

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in `cf_ops.cc', which are structural algorithms.

Definition at line 90 of file cf_factor.cc.

91 {
92  printf("%s",s1);
93  if (f.isZero()) printf("+0");
94  //else if (! f.inCoeffDomain() )
95  else if (! f.inBaseDomain() )
96  {
97  int l = f.level();
98  for ( CFIterator i = f; i.hasTerms(); i++ )
99  {
100  int e=i.exp();
101  if (i.coeff().isOne())
102  {
103  printf("+");
104  if (e==0) printf("1");
105  else
106  {
107  printf("v(%d)",l);
108  if (e!=1) printf("^%d",e);
109  }
110  }
111  else
112  {
113  out_cf("+(",i.coeff(),")");
114  if (e!=0)
115  {
116  printf("*v(%d)",l);
117  if (e!=1) printf("^%d",e);
118  }
119  }
120  }
121  }
122  else
123  {
124  if ( f.isImm() )
125  {
127  {
128  long a= imm2int (f.getval());
129  if ( a == gf_q )
130  printf ("+%ld", a);
131  else if ( a == 0L )
132  printf ("+1");
133  else if ( a == 1L )
134  printf ("+%c",gf_name);
135  else
136  {
137  printf ("+%c",gf_name);
138  printf ("^%ld",a);
139  }
140  }
141  else
142  printf("+%ld",f.intval());
143  }
144  else
145  {
146  #ifdef NOSTREAMIO
147  if (f.inZ())
148  {
149  mpz_t m;
150  gmp_numerator(f,m);
151  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
152  str = mpz_get_str( str, 10, m );
153  printf("%s",str);
154  delete[] str;
155  mpz_clear(m);
156  }
157  else if (f.inQ())
158  {
159  mpz_t m;
160  gmp_numerator(f,m);
161  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
162  str = mpz_get_str( str, 10, m );
163  printf("%s/",str);
164  delete[] str;
165  mpz_clear(m);
166  gmp_denominator(f,m);
167  str = new char[mpz_sizeinbase( m, 10 ) + 2];
168  str = mpz_get_str( str, 10, m );
169  printf("%s",str);
170  delete[] str;
171  mpz_clear(m);
172  }
173  #else
174  std::cout << f;
175  #endif
176  }
177  //if (f.inZ()) printf("(Z)");
178  //else if (f.inQ()) printf("(Q)");
179  //else if (f.inFF()) printf("(FF)");
180  //else if (f.inPP()) printf("(PP)");
181  //else if (f.inGF()) printf("(PP)");
182  //else
183  if (f.inExtension()) printf("E(%d)",f.level());
184  }
185  printf("%s",s2);
186 }
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
bool inQ() const
const poly a
Definition: syzextra.cc:212
char gf_name
Definition: gfops.cc:52
bool inZ() const
predicates
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
bool inExtension() const
long intval() const
conversion functions
int level() const
level() returns the level of CO.
int gf_q
Definition: gfops.cc:47
int m
Definition: cfEzgcd.cc:119
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
bool isImm() const
long imm2int(const InternalCF *const imm)
Definition: imm.h:66
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
static int gettype()
Definition: cf_factory.h:27
#define GaloisFieldDomain
Definition: cf_defs.h:22
bool inBaseDomain() const
InternalCF * getval() const
int l
Definition: cfEzgcd.cc:94
static CanonicalForm resultante ( const CanonicalForm f,
const CanonicalForm g,
const Variable v 
)
static

Definition at line 179 of file facAlgFunc.cc.

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);
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 }
void Off(int sw)
switches
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
return result
Definition: facAbsBiFact.cc:76
static CFList simpleExtension ( CFList backSubst,
const CFList Astar,
const Variable Extension,
bool &  isFunctionField,
CanonicalForm R 
)
static

Definition at line 313 of file facAlgFunc.cc.

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 
325  if (Astar.length() == 1)
326  {
327  R= Astar.getFirst();
328  rb= R.mvar();
329  Returnlist.append (rb);
330  if (isFunctionField)
331  Returnlist.append (denrb);
332  }
333  else
334  {
335  R=Bstar.getFirst();
336  Bstar.removeFirst();
337  for (CFListIterator i= Bstar; i.hasItem(); i++)
338  {
339  j= i;
340  j++;
341  if (getCharacteristic() == 0)
342  Off (SW_RATIONAL);
343  R /= icontent (R);
344  if (getCharacteristic() == 0)
345  On (SW_RATIONAL);
346  oldR= R;
347  //TODO normalize i.getItem over K(R)?
348  (void) sqrfNorm (i.getItem(), R, Extension, s, g, R);
349 
350  backSubst.insert (s);
351 
352  if (getCharacteristic() == 0)
353  Off (SW_RATIONAL);
354  R /= icontent (R);
355 
356  if (getCharacteristic() == 0)
357  On (SW_RATIONAL);
358 
359  if (!isFunctionField)
360  {
361  alpha= rootOf (R);
362  h= replacevar (g, g.mvar(), alpha);
363  if (getCharacteristic() == 0)
364  On (SW_RATIONAL); //needed for GCD
365  h= gcd (h, oldR);
366  h /= Lc (h);
367  ra= -h[0];
368  ra= replacevar(ra, alpha, g.mvar());
369  rb= R.mvar()-s*ra;
370  for (; j.hasItem(); j++)
371  {
372  j.getItem()= j.getItem() (rb, i.getItem().mvar());
373  j.getItem()= j.getItem() (ra, oldR.mvar());
374  }
375  prune (alpha);
376  }
377  else
378  {
379  if (getCharacteristic() == 0)
380  On (SW_RATIONAL);
381  Variable v= Variable (tmax (g.level(), oldR.level()) + 1);
382  h= swapvar (g, oldR.mvar(), v);
383  tmp= CFList (R);
384  h= alg_gcd (h, swapvar (oldR, oldR.mvar(), v), tmp);
385 
386  CanonicalForm numinv, deninv;
387  numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
388  h *= numinv;
389  h= Prem (h, tmp);
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  i.getItem().mvar()));
402  j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
403  i.getItem().mvar());
404  powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
405  j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
406 
407  }
408  }
409 
410  Returnlist.append (ra);
411  if (isFunctionField)
412  Returnlist.append (denra);
413  Returnlist.append (rb);
414  if (isFunctionField)
415  Returnlist.append (denrb);
416  }
417  }
418 
419  if (isRat && getCharacteristic() == 0)
420  On (SW_RATIONAL);
421  else if (!isRat && getCharacteristic() == 0)
422  Off (SW_RATIONAL);
423 
424  return Returnlist;
425 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
const CanonicalForm int s
Definition: facAbsFact.cc:55
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void Off(int sw)
switches
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: variable.h:32
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
Variable alpha
Definition: facAbsBiFact.cc:52
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
int level() const
level() returns the level of CO.
static CFFList sqrfNorm(const CanonicalForm &f, const CanonicalForm &PPalpha, const Variable &Extension, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R)
see norm, R is guaranteed to be squarefree Based on Trager&#39;s sqrf_norm algorithm. ...
Definition: facAlgFunc.cc:287
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int j
Definition: myNF.cc:70
const ring R
Definition: DebugPrint.cc:36
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
void prune(Variable &alpha)
Definition: variable.cc:261
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:1972
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
T & getItem() const
Definition: ftmpl_list.cc:431
int gcd(int a, int b)
Definition: walkSupport.cc:839
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
static Poly * h
Definition: janet.cc:978
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
static CFFList sqrfNorm ( const CanonicalForm f,
const CanonicalForm PPalpha,
const Variable Extension,
CanonicalForm s,
CanonicalForm g,
CanonicalForm R 
)
static

see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm.

Definition at line 287 of file facAlgFunc.cc.

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 }
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:93
generate all elements in F_p starting from 0
Definition: cf_generator.h:55
generate integers starting from 0
Definition: cf_generator.h:36
int getCharacteristic()
Definition: cf_char.cc:51
static CFFList norm(const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addi...
Definition: facAlgFunc.cc:206
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
CFFList SteelTrager ( const CanonicalForm f,
const CFList AS 
)

algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic" with the following modifications: we use characteristic sets in IdealOverSubfield and Trager's primitive element algorithm instead of FGLM

Definition at line 759 of file facAlgFunc.cc.

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;
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;
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 
858 retry:
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 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: variable.h:32
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
g
Definition: cfModGcd.cc:4031
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int level() const
level() returns the level of CO.
bool found
Definition: facFactorize.cc:56
int isEmpty() const
Definition: ftmpl_list.cc:267
#define M
Definition: sirandom.c:24
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
void removeLast()
Definition: ftmpl_list.cc:317
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
CanonicalForm factor
Definition: facAbsFact.cc:101
CFList mapIntoPIE(CFFList &varsMapLevel, CanonicalForm &lcmVars, const CFList &AS)
map elements in AS into a PIE and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables and integers such that
Definition: facAlgFunc.cc:609
class CFMap
Definition: cf_map.h:84
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:649
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
T & getItem() const
Definition: ftmpl_list.cc:431
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set ...
Definition: facAlgFunc.cc:1043
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
static CFFList Trager ( const CanonicalForm F,
const CFList Astar,
const Variable vminpoly,
const CFList as,
bool  isFunctionField 
)
static

Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.

Definition at line 430 of file facAlgFunc.cc.

432 {
433  bool isRat= isOn (SW_RATIONAL);
434  CFFList L, normFactors, tmp;
435  CFFListIterator iter, iter2;
436  CanonicalForm R, Rstar, s, g, h, f= F;
437  CFList substlist, backSubsts;
438 
439  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
440  Rstar);
441 
442  f= subst (f, Astar, substlist, Rstar, isFunctionField);
443 
444  Variable alpha;
445  if (!isFunctionField)
446  {
447  alpha= rootOf (Rstar);
448  g= replacevar (f, Rstar.mvar(), alpha);
449 
450  if (!isRat && getCharacteristic() == 0)
451  On (SW_RATIONAL);
452  tmp= factorize (g, alpha); // factorization over number field
453 
454  for (iter= tmp; iter.hasItem(); iter++)
455  {
456  h= iter.getItem().factor();
457  if (!h.inCoeffDomain())
458  {
459  h= replacevar (h, alpha, Rstar.mvar());
460  h *= bCommonDen(h);
461  h= backSubst (h, backSubsts, Astar);
462  h= Prem (h, as);
463  L.append (CFFactor (h, iter.getItem().exp()));
464  }
465  }
466  if (!isRat && getCharacteristic() == 0)
467  Off (SW_RATIONAL);
468  prune (alpha);
469  return L;
470  }
471  // after here we are over an extension of a function field
472 
473  // make quasi monic
474  CFList Rstarlist= CFList (Rstar);
475  int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
476  CanonicalForm numinv;
477  if (!isRat && getCharacteristic() == 0)
478  On (SW_RATIONAL);
479  numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());
480 
481  f *= numinv;
482  f= Prem (f, Rstarlist);
483  f /= vcontent (f, Rstar.mvar());
484  // end quasi monic
485 
486  if (degree (f) == 1)
487  {
488  f= backSubst (f, backSubsts, Astar);
489  f *= bCommonDen (f);
490  f= Prem (f, as);
491  f /= vcontent (f, as.getFirst().mvar());
492 
493  return CFFList (CFFactor (f, 1));
494  }
495 
496  CFGenerator * Gen;
497  if (getCharacteristic() == 0)
498  Gen= CFGenFactory::generate();
499  else if (degree (vminpoly) > 0)
500  Gen= AlgExtGenerator (vminpoly).clone();
501  else
502  Gen= CFGenFactory::generate();
503 
504  CFFList LL= CFFList (CFFactor (f, 1));
505 
506  Variable X;
507  do
508  {
509  tmp= CFFList();
510  for (iter= LL; iter.hasItem(); iter++)
511  {
512  f= iter.getItem().factor();
513  (void) norm (f, Rstar, *Gen, s, g, R, false);
514 
515  if (hasFirstAlgVar (R, X))
516  normFactors= factorize (R, X);
517  else
518  normFactors= factorize (R);
519 
520  if (normFactors.getFirst().factor().inCoeffDomain())
521  normFactors.removeFirst();
522  if (normFactors.length() < 1 || (normFactors.length() == 1 && normFactors.getLast().exp() == 1))
523  {
524  f= backSubst (f, backSubsts, Astar);
525  f *= bCommonDen (f);
526  f= Prem (f, as);
527  f /= vcontent (f, as.getFirst().mvar());
528 
529  L.append (CFFactor (f, 1));
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= Prem (fnew, CFList (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 }
int status int void size_t count
Definition: si_signals.h:59
List< CanonicalForm > CFList
const CanonicalForm int s
Definition: facAbsFact.cc:55
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:93
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void Off(int sw)
switches
bool inCoeffDomain() const
factory&#39;s class for variables
Definition: variable.h:32
virtual class for generators
Definition: cf_generator.h:21
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
factory&#39;s main class
Definition: canonicalform.h:75
List< CFFactor > CFFList
g
Definition: cfModGcd.cc:4031
Variable alpha
Definition: facAbsBiFact.cc:52
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
int level() const
level() returns the level of CO.
int isEmpty() const
Definition: ftmpl_list.cc:267
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
const ring R
Definition: DebugPrint.cc:36
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
T getFirst() const
Definition: ftmpl_list.cc:279
FILE * f
Definition: checklibs.c:7
int length() const
Definition: ftmpl_list.cc:273
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
T & getItem() const
Definition: ftmpl_list.cc:431
static CFGenerator * generate()
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
Definition: facAlgFunc.cc:313
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
static CFFList norm(const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addi...
Definition: facAlgFunc.cc:206
CFGenerator * clone() const
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
static Poly * h
Definition: janet.cc:978
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162