My Project  UNKNOWN_GIT_VERSION
Functions
facAlgFunc.h File Reference
#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

◆ alg_gcd()

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 }

◆ facAlgFunc()

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

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 }

◆ facAlgFunc2()

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

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 }
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
x
Variable x
Definition: cfModGcd.cc:4023
Prem
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Definition: cfCharSetsUtil.cc:616
result
return result
Definition: facAbsBiFact.cc:76
isInseparable
bool isInseparable(const CFList &Astar)
Definition: facAlgFuncUtil.cc:522
varsInAs
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Definition: facAlgFuncUtil.cc:66
CFFList
List< CFFactor > CFFList
Definition: canonicalform.h:386
vcontent
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:225
g
g
Definition: cfModGcd.cc:4031
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
rootOf
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
alg_gcd
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
Trager
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.
Definition: facAlgFunc.cc:430
CanonicalForm
factory's main class
Definition: canonicalform.h:83
i
int i
Definition: cfEzgcd.cc:125
res
CanonicalForm res
Definition: facAbsFact.cc:64
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
prune
void prune(Variable &alpha)
Definition: variable.cc:261
Variable::level
int level() const
Definition: factory.h:134
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
Factor
Definition: ftmpl_factor.h:18
SteelTrager
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
divide
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
Definition: facAlgFuncUtil.cc:500
List::length
int length() const
Definition: ftmpl_list.cc:273
Variable
factory's class for variables
Definition: factory.h:118
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
getDegOfExt
int getDegOfExt(IntList &degreelist, int n)
Definition: facAlgFuncUtil.cc:543
facAlgFunc2
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
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition: facAlgFuncUtil.cc:322
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
List
Definition: ftmpl_list.h:20
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
multiplicity
static int * multiplicity
Definition: interpolation.cc:86
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
hasVar
int hasVar(const CanonicalForm &f, const Variable &v)
Definition: facAlgFuncUtil.cc:345
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
alg_content
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition: cfNewtonPolygon.cc:230
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
generateMipo
CanonicalForm generateMipo(int degOfExt)
Definition: facAlgFuncUtil.cc:90
ListIterator
Definition: ftmpl_list.h:17