My Project
Loading...
Searching...
No Matches
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

◆ alg_gcd()

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}
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T getLast() const
Definition: ftmpl_list.cc:309
factory's class for variables
Definition: variable.h:33
CanonicalForm res
Definition: facAbsFact.cc:60
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int hasVar(const CanonicalForm &f, const Variable &v)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int gcd(int a, int b)
Definition: walkSupport.cc:836

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

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}
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
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

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

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();
913 CFList reduceresult;
915
916// F1: [Test trivial cases]
917// 1) first trivial cases:
918 if (vf.level() <= as.getLast().level())
919 {
920 if (!isRat && getCharacteristic() == 0)
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)
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)
978 return result;
979 }
980
981 Fgcd= pp (Fgcd);
982 Ggcd= pp (Ggcd);
983 if (!isRat && getCharacteristic() == 0)
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}
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
int level(const CanonicalForm &f)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void append(const T &)
Definition: ftmpl_list.cc:256
int level() const
Definition: variable.h:49
return result
Definition: facAbsBiFact.cc:75
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
int getDegOfExt(IntList &degreelist, int n)
bool isInseparable(const CFList &Astar)
CanonicalForm generateMipo(int degOfExt)
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
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
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR int * multiplicity
void prune(Variable &alpha)
Definition: variable.cc:261
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