Functions
facAlgFunc.h File Reference

Factorization over algebraic function fields. More...

#include "canonicalform.h"

Go to the source code of this file.

Functions

CanonicalForm alg_gcd (const CanonicalForm &, const CanonicalForm &, const CFList &)
 
CFFList facAlgFunc2 (const CanonicalForm &f, const CFList &as)
 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 $. More...
 
CFFList facAlgFunc (const CanonicalForm &f, const CFList &as)
 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 $. More...
 

Detailed Description

Factorization over algebraic 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.
Author
Martin Lee

Definition in file facAlgFunc.h.

Function Documentation

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 }
int level() const
Definition: factory.h:132
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: factory.h:115
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
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 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 $.

Returns
the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

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 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 $.

Returns
the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

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: factory.h:132
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: factory.h:115
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
void prune(Variable &alpha)
Definition: variable.cc:261
int level() const
level() returns the level of CO.
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
Variable rootOf(const CanonicalForm &, char name= '@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
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
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
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759