Loading...
Searching...
No Matches
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. , and each element of as is assumed to be integral as well. must be either or .
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. , and each element of as is assumed to be integral as well. must be either or .

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

{
if (fff.inCoeffDomain() || ggg.inCoeffDomain())
return 1;
CanonicalForm f=fff;
CanonicalForm g=ggg;
f=Prem(f,as);
g=Prem(g,as);
if ( f.isZero() )
{
if ( g.lc().sign() < 0 ) return -g;
else return g;
}
else if ( g.isZero() )
{
if ( f.lc().sign() < 0 ) return -f;
else return f;
}
int v= as.getLast().level();
if (f.level() <= v || g.level() <= v)
return 1;
CanonicalForm res;
// does as appear in f and g ?
bool has_alg_var=false;
for ( CFListIterator j=as;j.hasItem(); j++ )
{
Variable v=j.getItem().mvar();
if (hasVar (f, v))
has_alg_var=true;
if (hasVar (g, v))
has_alg_var=true;
}
if (!has_alg_var)
{
/*if ((hasAlgVar(f))
|| (hasAlgVar(g)))
{
Varlist ord;
for ( CFListIterator j=as;j.hasItem(); j++ )
ord.append(j.getItem().mvar());
res=algcd(f,g,as,ord);
}
else*/
if (!hasAlgVar (f) && !hasAlgVar (g))
return res=gcd(f,g);
}
int mvf=f.level();
int mvg=g.level();
if (mvg > mvf)
{
CanonicalForm tmp=f; f=g; g=tmp;
int tmp2=mvf; mvf=mvg; mvg=tmp2;
}
if (g.inBaseDomain() || f.inBaseDomain())
return CanonicalForm(1);
CanonicalForm c_f= alg_content (f, as);
if (mvf != mvg)
{
res= alg_gcd (g, c_f, as);
return res;
}
Variable x= f.mvar();
// now: mvf==mvg, f.level()==g.level()
CanonicalForm c_g= alg_content (g, as);
int delta= degree (f) - degree (g);
f= divide (f, c_f, as);
g= divide (g, c_g, as);
// gcd of contents
CanonicalForm c_gcd= alg_gcd (c_f, c_g, as);
CanonicalForm tmp;
if (delta < 0)
{
tmp= f;
f= g;
g= tmp;
delta= -delta;
}
CanonicalForm r= 1;
while (degree (g, x) > 0)
{
r= Prem (f, g);
r= Prem (r, as);
if (!r.isZero())
{
r= divide (r, alg_content (r,as), as);
r /= vcontent (r,Variable (v+1));
}
f= g;
g= r;
}
if (degree (g, x) == 0)
return c_gcd;
c_f= alg_content (f, as);
f= divide (f, c_f, as);
f *= c_gcd;
f /= vcontent (f, Variable (v+1));
return f;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
vcontent
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ).
Definition cf_gcd.cc:653
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
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
x
Variable x
Definition cfModGcd.cc:4090
g
g
Definition cfModGcd.cc:4098
f
FILE * f
Definition checklibs.c:9
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
Variable
factory's class for variables
Definition factory.h:127
res
CanonicalForm res
Definition facAbsFact.cc:60
divide
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
Definition facAlgFuncUtil.cc:496
hasVar
int hasVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:345
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:322
alg_content
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition facAlgFunc.cc:42
alg_gcd
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition facAlgFunc.cc:61
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
tmp2
CFList tmp2
Definition facFqBivar.cc:75
j
int j
Definition facHensel.cc:110
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
gcd
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. , and each element of as is assumed to be integral as well. must be either or .

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. , and each element of as is assumed to be integral as well. must be either or .

Parameters

  [in] | f | univariate poly
  [in] | as | irreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

{
bool isRat= isOn (SW_RATIONAL);
if (!isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
CFFList Output, output, Factors= factorize(f);
if (Factors.getFirst().factor().inCoeffDomain())
Factors.removeFirst();
if (as.length() == 0)
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Factors;
}
if (f.level() <= as.getLast().level())
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Factors;
}
for (CFFListIterator i=Factors; i.hasItem(); i++)
{
if (i.getItem().factor().level() > as.getLast().level())
{
output= facAlgFunc2 (i.getItem().factor(), as);
for (CFFListIterator j= output; j.hasItem(); j++)
Output= append (Output, CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
}
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Output;
}
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
i
int i
Definition cfEzgcd.cc:132
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::length
int length() const
Definition ftmpl_list.cc:273
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
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

## 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. , and each element of as is assumed to be integral as well. must be either or .

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. , and each element of as is assumed to be integral as well. must be either or .

Parameters

  [in] | f | univariate poly
  [in] | as | irreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

{
bool isRat= isOn (SW_RATIONAL);
if (!isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
Variable vf=f.mvar();
CFListIterator i;
CFFListIterator jj;
CFList reduceresult;
CFFList result;
// F1: [Test trivial cases]
// 1) first trivial cases:
if (vf.level() <= as.getLast().level())
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return CFFList(CFFactor(f,1));
}
// 2) Setup list of those polys in AS having degree > 1
CFList Astar;
Variable x;
CanonicalForm elem;
Varlist ord, uord;
for (int ii= 1; ii < level (vf); ii++)
uord.append (Variable (ii));
for (i= as; i.hasItem(); i++)
{
elem= i.getItem();
x= elem.mvar();
if (degree (elem, x) > 1) // otherwise it's not an extension
{
Astar.append (elem);
ord.append (x);
}
}
uord= Difference (uord, ord);
// 3) second trivial cases: we already proved irr. of f over no extensions
if (Astar.length() == 0)
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return CFFList (CFFactor (f, 1));
}
// 4) Look if elements in uord actually occur in any of the minimal
// polynomials. If no element of uord occures in any of the minimal
// polynomials the field is an alg. number field not an alg. function field
Varlist newuord= varsInAs (uord, Astar);
CFFList Factorlist;
Varlist gcdord= Union (ord, newuord);
gcdord.append (f.mvar());
bool isFunctionField= (newuord.length() > 0);
// TODO alg_sqrfree?
CanonicalForm Fgcd= 0;
if (isFunctionField)
Fgcd= alg_gcd (f, f.deriv(), Astar);
bool derivZero= f.deriv().isZero();
if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
{
CanonicalForm Ggcd= divide(f, Fgcd,Astar);
if (getCharacteristic() == 0)
{
CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
multiplicity (result, f, Astar);
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return result;
}
Fgcd= pp (Fgcd);
Ggcd= pp (Ggcd);
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
}
if (getCharacteristic() > 0)
{
IntList degreelist;
Variable vminpoly;
for (i= Astar; i.hasItem(); i++)
degreelist.append (degree (i.getItem()));
int extdeg= getDegOfExt (degreelist, degree (f));
if (newuord.length() == 0) // no parameters
{
if (extdeg > 1)
{
CanonicalForm MIPO= generateMipo (extdeg);
vminpoly= rootOf(MIPO);
}
Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
if (extdeg > 1)
prune (vminpoly);
return Factorlist;
}
else if (isInseparable(Astar) || derivZero) // inseparable case
{
Factorlist= SteelTrager (f, Astar);
return Factorlist;
}
else // separable case
{
if (extdeg > 1)
{
CanonicalForm MIPO=generateMipo (extdeg);
vminpoly= rootOf (MIPO);
}
Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
if (extdeg > 1)
prune (vminpoly);
return Factorlist;
}
}
else // char 0
{
Variable vminpoly;
Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Factorlist;
}
return CFFList (CFFactor(f,1));
}
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
IntList
List< int > IntList
Definition canonicalform.h:401
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
Varlist
List< Variable > Varlist
Definition canonicalform.h:403
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition cfNewtonPolygon.cc:230
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable::level
int level() const
Definition factory.h:143
result
return result
Definition facAbsBiFact.cc:76
varsInAs
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Definition facAlgFuncUtil.cc:66
getDegOfExt
int getDegOfExt(IntList &degreelist, int n)
Definition facAlgFuncUtil.cc:539
isInseparable
bool isInseparable(const CFList &Astar)
Definition facAlgFuncUtil.cc:518
generateMipo
CanonicalForm generateMipo(int degOfExt)
Definition facAlgFuncUtil.cc:90
SteelTrager
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primarydecomposition and multivariate ...
Definition facAlgFunc.cc:759
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
rootOf
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
multiplicity
STATIC_VAR int * multiplicity
Definition interpolation.cc:86