Loading...
Searching...
No Matches
facAlgFunc.cc
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facAlgFunc.cc
*
* 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
*
**/
/*****************************************************************************/
#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"
void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
CanonicalForm
alg_content (const CanonicalForm& f, const CFList& as)
{
if (!f.inCoeffDomain())
{
CFIterator i= f;
CanonicalForm result= abs (i.coeff());
i++;
while (i.hasTerms() && !result.isOne())
{
result= alg_gcd (i.coeff(), result, as);
i++;
}
return result;
}
return abs (f);
}
CanonicalForm
alg_gcd (const CanonicalForm & fff, const CanonicalForm &ggg, const CFList &as)
{
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;
}
static CanonicalForm
resultante (const CanonicalForm & f, const CanonicalForm& g, const Variable & v)
{
bool on_rational = isOn(SW_RATIONAL);
if (!on_rational && getCharacteristic() == 0)
On(SW_RATIONAL);
CanonicalForm cd = bCommonDen( f );
CanonicalForm fz = f * cd;
cd = bCommonDen( g );
CanonicalForm gz = g * cd;
if (!on_rational && getCharacteristic() == 0)
Off(SW_RATIONAL);
CanonicalForm result;
#ifdef HAVE_NTL
if (getCharacteristic() == 0)
result= resultantZ (fz, gz,v);
else
#endif
result= resultant (fz,gz,v);
return result;
}
/// 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.
static CFFList
norm (const CanonicalForm & f, const CanonicalForm & PPalpha,
CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g,
CanonicalForm & R, bool proof)
{
Variable y= PPalpha.mvar(), vf= f.mvar();
CanonicalForm temp, Palpha= PPalpha, t;
int sqfreetest= 0;
CFFList testlist;
CFFListIterator i;
if (proof)
{
myrandom.reset();
s= myrandom.item();
g= f;
R= CanonicalForm(0);
}
else
{
if (getCharacteristic() == 0)
t= CanonicalForm (mapinto (myrandom.item()));
else
t= CanonicalForm (myrandom.item());
s= t;
g= f (vf - t*Palpha.mvar(), vf);
}
// Norm, resultante taken with respect to y
while (!sqfreetest)
{
R= resultante (Palpha, g, y);
R= R* bCommonDen(R);
R /= content (R);
if (proof)
{
// sqfree check ; R is a polynomial in K[x]
if (getCharacteristic() == 0)
{
temp= gcd (R, R.deriv (vf));
if (degree(temp,vf) != 0 || temp == temp.genZero())
sqfreetest= 0;
else
sqfreetest= 1;
}
else
{
Variable X;
testlist= sqrFree (R);
if (testlist.getFirst().factor().inCoeffDomain())
testlist.removeFirst();
sqfreetest= 1;
for (i= testlist; i.hasItem(); i++)
{
if (i.getItem().exp() > 1 && degree (i.getItem().factor(),R.mvar()) > 0)
{
sqfreetest= 0;
break;
}
}
}
if (!sqfreetest)
{
myrandom.next();
if (getCharacteristic() == 0)
t= CanonicalForm (mapinto (myrandom.item()));
else
t= CanonicalForm (myrandom.item());
s= t;
g= f (vf - t*Palpha.mvar(), vf);
}
}
else
break;
}
return testlist;
}
/// see @a norm, R is guaranteed to be squarefree
/// Based on Trager's sqrf_norm algorithm.
static CFFList
sqrfNorm (const CanonicalForm & f, const CanonicalForm & PPalpha,
const Variable & Extension, CanonicalForm & s, CanonicalForm & g,
CanonicalForm & R)
{
CFFList result;
if (getCharacteristic() == 0)
{
IntGenerator myrandom;
result= norm (f, PPalpha, myrandom, s, g, R, true);
}
else if (degree (Extension) > 0)
{
AlgExtGenerator myrandom (Extension);
result= norm (f, PPalpha, myrandom, s, g, R, true);
}
else
{
FFGenerator myrandom;
result= norm (f, PPalpha, myrandom, s, g, R, true);
}
return result;
}
// calculate a "primitive element"
// K must have more than S elements (-> getDegOfExt)
static CFList
simpleExtension (CFList& backSubst, const CFList & Astar,
const Variable & Extension, bool& isFunctionField,
CanonicalForm & R)
{
CFList Returnlist, Bstar= Astar;
CanonicalForm s, g, ra, rb, oldR, h, denra, denrb= 1;
Variable alpha;
CFList tmp;
bool isRat= isOn (SW_RATIONAL);
CFListIterator j;
if (Astar.length() == 1)
{
R= Astar.getFirst();
rb= R.mvar();
Returnlist.append (rb);
if (isFunctionField)
Returnlist.append (denrb);
}
else
{
R=Bstar.getFirst();
Bstar.removeFirst();
for (CFListIterator i= Bstar; i.hasItem(); i++)
{
j= i;
j++;
if (getCharacteristic() == 0)
Off (SW_RATIONAL);
R /= icontent (R);
if (getCharacteristic() == 0)
On (SW_RATIONAL);
oldR= R;
//TODO normalize i.getItem over K(R)?
(void) sqrfNorm (i.getItem(), R, Extension, s, g, R);
backSubst.insert (s);
if (getCharacteristic() == 0)
Off (SW_RATIONAL);
R /= icontent (R);
if (getCharacteristic() == 0)
On (SW_RATIONAL);
if (!isFunctionField)
{
alpha= rootOf (R);
h= replacevar (g, g.mvar(), alpha);
if (getCharacteristic() == 0)
On (SW_RATIONAL); //needed for GCD
h= gcd (h, oldR);
h /= Lc (h);
ra= -h[0];
ra= replacevar(ra, alpha, g.mvar());
rb= R.mvar()-s*ra;
for (; j.hasItem(); j++)
{
j.getItem()= j.getItem() (rb, i.getItem().mvar());
j.getItem()= j.getItem() (ra, oldR.mvar());
}
prune (alpha);
}
else
{
if (getCharacteristic() == 0)
On (SW_RATIONAL);
Variable v= Variable (tmax (g.level(), oldR.level()) + 1);
h= swapvar (g, oldR.mvar(), v);
tmp= CFList (R);
h= alg_gcd (h, swapvar (oldR, oldR.mvar(), v), tmp);
CanonicalForm numinv, deninv;
numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
h *= numinv;
h= Prem (h, tmp);
deninv= LC(h);
ra= -h[0];
denra= gcd (ra, deninv);
ra /= denra;
denra= deninv/denra;
rb= R.mvar()*denra-s*ra;
denrb= denra;
for (; j.hasItem(); j++)
{
CanonicalForm powdenra= power (denra, degree (j.getItem(),
i.getItem().mvar()));
j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
i.getItem().mvar());
powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
}
}
Returnlist.append (ra);
if (isFunctionField)
Returnlist.append (denra);
Returnlist.append (rb);
if (isFunctionField)
Returnlist.append (denrb);
}
}
if (isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
else if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Returnlist;
}
/// Trager's algorithm, i.e. convert to one field extension and
/// factorize over this field extension
static CFFList
Trager (const CanonicalForm & F, const CFList & Astar,
const Variable & vminpoly, const CFList & as, bool isFunctionField)
{
bool isRat= isOn (SW_RATIONAL);
CFFList L, normFactors, tmp;
CFFListIterator iter, iter2;
CanonicalForm R, Rstar, s, g, h, f= F;
CFList substlist, backSubsts;
substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
Rstar);
f= subst (f, Astar, substlist, Rstar, isFunctionField);
Variable alpha;
if (!isFunctionField)
{
alpha= rootOf (Rstar);
g= replacevar (f, Rstar.mvar(), alpha);
if (!isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
tmp= factorize (g, alpha); // factorization over number field
for (iter= tmp; iter.hasItem(); iter++)
{
h= iter.getItem().factor();
if (!h.inCoeffDomain())
{
h= replacevar (h, alpha, Rstar.mvar());
h *= bCommonDen(h);
h= backSubst (h, backSubsts, Astar);
h= Prem (h, as);
L.append (CFFactor (h, iter.getItem().exp()));
}
}
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
prune (alpha);
return L;
}
// after here we are over an extension of a function field
// make quasi monic
CFList Rstarlist= CFList (Rstar);
int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
CanonicalForm numinv;
if (!isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());
f *= numinv;
f= Prem (f, Rstarlist);
f /= vcontent (f, Rstar.mvar());
// end quasi monic
if (degree (f) == 1)
{
f= backSubst (f, backSubsts, Astar);
f *= bCommonDen (f);
f= Prem (f, as);
f /= vcontent (f, as.getFirst().mvar());
return CFFList (CFFactor (f, 1));
}
CFGenerator * Gen;
if (getCharacteristic() == 0)
Gen= CFGenFactory::generate();
else if (degree (vminpoly) > 0)
Gen= AlgExtGenerator (vminpoly).clone();
else
Gen= CFGenFactory::generate();
CFFList LL= CFFList (CFFactor (f, 1));
Variable X;
do
{
tmp= CFFList();
for (iter= LL; iter.hasItem(); iter++)
{
f= iter.getItem().factor();
(void) norm (f, Rstar, *Gen, s, g, R, false);
if (hasFirstAlgVar (R, X))
normFactors= factorize (R, X);
else
normFactors= factorize (R);
if (normFactors.getFirst().factor().inCoeffDomain())
normFactors.removeFirst();
if (normFactors.length() < 1 || (normFactors.length() == 1 && normFactors.getLast().exp() == 1))
{
f= backSubst (f, backSubsts, Astar);
f *= bCommonDen (f);
f= Prem (f, as);
f /= vcontent (f, as.getFirst().mvar());
L.append (CFFactor (f, 1));
}
else
{
g= f;
int count= 0;
for (iter2= normFactors; iter2.hasItem(); iter2++)
{
CanonicalForm fnew= iter2.getItem().factor();
if (fnew.level() <= Rstar.level()) //factor is a constant from the function field
continue;
else
{
fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
fnew= Prem (fnew, CFList (Rstar));
}
h= alg_gcd (g, fnew, Rstarlist);
numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
h *= numinv;
h= Prem (h, Rstarlist);
h /= vcontent (h, Rstar.mvar());
if (h.level() > Rstar.level())
{
g= divide (g, h, Rstarlist);
if (degree (h) == 1 || iter2.getItem().exp() == 1)
{
h= backSubst (h, backSubsts, Astar);
h= Prem (h, as);
h *= bCommonDen (h);
h /= vcontent (h, as.getFirst().mvar());
L.append (CFFactor (h, 1));
}
else
tmp.append (CFFactor (h, iter2.getItem().exp()));
}
count++;
if (g.level() <= Rstar.level())
break;
if (count == normFactors.length() - 1)
{
if (normFactors.getLast().exp() == 1 && g.level() > Rstar.level())
{
g= backSubst (g, backSubsts, Astar);
g= Prem (g, as);
g *= bCommonDen (g);
g /= vcontent (g, as.getFirst().mvar());
L.append (CFFactor (g, 1));
}
else if (normFactors.getLast().exp() > 1 &&
g.level() > Rstar.level())
{
g /= vcontent (g, Rstar.mvar());
tmp.append (CFFactor (g, normFactors.getLast().exp()));
}
break;
}
}
}
}
LL= tmp;
(*Gen).next();
}
while (!LL.isEmpty());
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
delete Gen;
return L;
}
/// map elements in @a AS into a PIE \f$ L \f$ and record where the variables
/// are mapped to in @a varsMapLevel, i.e @a varsMapLevel contains a list of
/// pairs of variables \f$ v_i \f$ and integers \f$ e_i \f$ such that
/// \f$ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) \f$
CFList
mapIntoPIE (CFFList& varsMapLevel, CanonicalForm& lcmVars, const CFList & AS)
{
CanonicalForm varsG;
int j, exp= 0, tmpExp;
bool recurse= false;
CFList asnew, as= AS;
CFListIterator i= as, ii;
CFFList varsGMapLevel, tmp;
CFFListIterator iter;
CFFList * varsGMap= new CFFList [as.length()];
for (j= 0; j < as.length(); j++)
varsGMap[j]= CFFList();
j= 0;
while (i.hasItem())
{
if (i.getItem().deriv() == 0)
{
deflateDegree (i.getItem(), exp, i.getItem().level());
i.getItem()= deflatePoly (i.getItem(), exp, i.getItem().level());
varsG= getVars (i.getItem());
varsG /= i.getItem().mvar();
lcmVars= lcm (varsG, lcmVars);
while (!varsG.isOne())
{
if (i.getItem().deriv (varsG.level()).isZero())
{
deflateDegree (i.getItem(), tmpExp, varsG.level());
if (exp >= tmpExp)
{
if (exp == tmpExp)
i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
else
{
if (j != 0)
recurse= true;
i.getItem()= deflatePoly (i.getItem(), tmpExp, varsG.level());
}
varsGMapLevel.insert (CFFactor (varsG.mvar(), exp - tmpExp));
}
else
{
i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
varsGMapLevel.insert (CFFactor (varsG.mvar(), 0));
}
}
else
{
if (j != 0)
recurse= true;
varsGMapLevel.insert (CFFactor (varsG.mvar(),exp));
}
varsG /= varsG.mvar();
}
if (recurse)
{
ii= as;
for (; ii.hasItem(); ii++)
{
if (ii.getItem() == i.getItem())
continue;
for (iter= varsGMapLevel; iter.hasItem(); iter++)
ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
iter.getItem().factor().level());
}
}
else
{
ii= i;
ii++;
for (; ii.hasItem(); ii++)
{
for (iter= varsGMapLevel; iter.hasItem(); iter++)
{
ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
iter.getItem().factor().level());
}
}
}
if (varsGMap[j].isEmpty())
varsGMap[j]= varsGMapLevel;
else
{
if (!varsGMapLevel.isEmpty())
{
tmp= varsGMap[j];
CFFListIterator iter2= varsGMapLevel;
ASSERT (tmp.length() == varsGMapLevel.length(),
"wrong length of lists");
for (iter=tmp; iter.hasItem(); iter++, iter2++)
iter.getItem()= CFFactor (iter.getItem().factor(),
iter.getItem().exp() + iter2.getItem().exp());
varsGMap[j]= tmp;
}
}
varsGMapLevel= CFFList();
}
asnew.append (i.getItem());
if (!recurse)
{
i++;
j++;
}
else
{
i= as;
j= 0;
recurse= false;
asnew= CFList();
}
}
while (!lcmVars.isOne())
{
varsMapLevel.insert (CFFactor (lcmVars.mvar(), 0));
lcmVars /= lcmVars.mvar();
}
for (j= 0; j < as.length(); j++)
{
if (varsGMap[j].isEmpty())
continue;
for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
{
for (iter= varsMapLevel; iter.hasItem(); iter++)
{
if (iter.getItem().factor() == iter2.getItem().factor())
{
iter.getItem()= CFFactor (iter.getItem().factor(),
iter.getItem().exp() + iter2.getItem().exp());
}
}
}
}
delete [] varsGMap;
return asnew;
}
/// 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
CFFList
SteelTrager (const CanonicalForm & f, const CFList & AS)
{
CanonicalForm F= f, lcmVars= 1;
CFList asnew, as= AS;
CFListIterator i, ii;
bool derivZeroF= false;
int j, expF=0, tmpExp=0;
CFFList varsMapLevel, tmp;
CFFListIterator iter;
// check if F is separable
if (F.deriv().isZero())
{
derivZeroF= true;
deflateDegree (F, expF, F.level());
}
CanonicalForm varsF= getVars (F);
varsF /= F.mvar();
lcmVars= lcm (varsF, lcmVars);
if (derivZeroF)
as.append (F);
asnew= mapIntoPIE (varsMapLevel, lcmVars, as);
if (derivZeroF)
{
asnew.removeLast();
F= deflatePoly (F, expF, F.level());
}
// map variables in F
for (iter= varsMapLevel; iter.hasItem(); iter++)
{
if (expF > 0)
tmpExp= iter.getItem().exp() - expF;
else
tmpExp= iter.getItem().exp();
if (tmpExp > 0)
F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
else if (tmpExp < 0)
F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
}
// factor F with minimal polys given in asnew
asnew.append (F);
asnew= charSetViaModCharSet (asnew, false);
F= asnew.getLast();
F /= content (F);
asnew.removeLast();
for (i= asnew; i.hasItem(); i++)
i.getItem() /= content (i.getItem());
tmp= facAlgFunc (F, asnew);
// transform back
j= 0;
int p= getCharacteristic();
CFList transBack;
CFMap M;
CanonicalForm g;
for (iter= varsMapLevel; iter.hasItem(); iter++)
{
if (iter.getItem().exp() > 0)
{
j++;
g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
iter.getItem().factor().mvar();
transBack.append (g);
M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
}
}
for (i= asnew; i.hasItem(); i++)
transBack.insert (M (i.getItem()));
if (expF > 0)
tmpExp= ipower (p, expF);
CFFList result;
CFList transform;
bool found;
for (iter= tmp; iter.hasItem(); iter++)
{
found= false;
transform= transBack;
CanonicalForm factor= iter.getItem().factor();
factor= M (factor);
transform.append (factor);
transform= modCharSet (transform, false);
retry:
if (transform.isEmpty())
{
transform= transBack;
transform.append (factor);
transform= charSetViaCharSetN (transform);
}
for (i= transform; i.hasItem(); i++)
{
if (degree (i.getItem(), f.mvar()) > 0)
{
if (i.getItem().level() > f.level())
break;
found= true;
factor= i.getItem();
break;
}
}
if (!found)
{
found= false;
transform= CFList();
goto retry;
}
factor /= content (factor);
if (expF > 0)
{
int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
result.append (CFFactor (factor, iter.getItem().exp()*mult));
}
else
result.append (CFFactor (factor, iter.getItem().exp()));
}
return result;
}
/// factorize a polynomial that is irreducible over the ground field modulo an
/// extension given by an irreducible characteristic set
// 1) prepares data
// 2) for char=p we distinguish 3 cases:
// no transcendentals, separable and inseparable extensions
CFFList
facAlgFunc2 (const CanonicalForm & f, const CFList & as)
{
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));
}
/// factorize a polynomial modulo an extension given by an irreducible
/// characteristic set
CFFList
facAlgFunc (const CanonicalForm & f, const CFList & as)
{
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;
}
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
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
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f ).
Definition cf_ops.cc:350
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
replacevar
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ).
Definition cf_ops.cc:271
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
vcontent
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ).
Definition cf_gcd.cc:653
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
IntList
List< int > IntList
Definition canonicalform.h:401
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
mvar
Variable mvar(const CanonicalForm &f)
Definition canonicalform.h:334
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
Varlist
List< Variable > Varlist
Definition canonicalform.h:403
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
charSetViaCharSetN
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition cfCharSets.cc:246
charSetViaModCharSet
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition cfCharSets.cc:356
modCharSet
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition cfCharSets.cc:284
cfCharSets.h
This file provides functions to compute characteristic sets.
i
int i
Definition cfEzgcd.cc:132
x
Variable x
Definition cfModGcd.cc:4090
evaluate
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition cfModGcd.cc:2039
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
cd
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
resultantZ
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
Definition cfModResultant.cc:560
cfModResultant.h
modular resultant algorithm as described by G.
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition cfNewtonPolygon.cc:230
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
cf_algorithm.h
declarations of higher level algorithms.
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
resultant
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).
Definition cf_resultant.cc:173
cf_assert.h
assertions for Factory
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
cf_generator.h
generate integers, elements of finite fields
cf_iter.h
Iterators for CanonicalForm's.
cf_map.h
map polynomials
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
cf_util.h
f
FILE * f
Definition checklibs.c:9
AlgExtGenerator
generate all elements in F_p(alpha) starting from 0
Definition cf_generator.h:94
AlgExtGenerator::clone
CFGenerator * clone() const
Definition cf_generator.cc:216
CFGenFactory::generate
static CFGenerator * generate()
Definition cf_generator.cc:221
CFGenerator
virtual class for generators
Definition cf_generator.h:22
CFGenerator::item
virtual CanonicalForm item() const
Definition cf_generator.h:28
CFGenerator::next
virtual void next()
Definition cf_generator.h:29
CFGenerator::reset
virtual void reset()
Definition cf_generator.h:27
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
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
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::genZero
CanonicalForm genZero() const
genOne(), genZero()
Definition canonicalform.cc:1867
CanonicalForm::deriv
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
Definition canonicalform.cc:1300
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
FFGenerator
generate all elements in F_p starting from 0
Definition cf_generator.h:56
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
IntGenerator
generate integers starting from 0
Definition cf_generator.h:37
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
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
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
List::removeLast
void removeLast()
Definition ftmpl_list.cc:317
Variable
factory's class for variables
Definition factory.h:127
Variable::level
int level() const
Definition factory.h:143
debug.h
functions to print debug output
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
alpha
Variable alpha
Definition facAbsBiFact.cc:52
result
return result
Definition facAbsBiFact.cc:76
s
const CanonicalForm int s
Definition facAbsFact.cc:51
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
res
CanonicalForm res
Definition facAbsFact.cc:60
factor
CanonicalForm factor
Definition facAbsFact.cc:97
norm
mipo *CanonicalForm norm
Definition facAlgExt.cc:61
varsInAs
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Definition facAlgFuncUtil.cc:66
deflateDegree
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
Definition facAlgFuncUtil.cc:195
alg_LC
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
Definition facAlgFuncUtil.cc:110
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
inflatePoly
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
Definition facAlgFuncUtil.cc:266
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:322
getDegOfExt
int getDegOfExt(IntList &degreelist, int n)
Definition facAlgFuncUtil.cc:539
isInseparable
bool isInseparable(const CFList &Astar)
Definition facAlgFuncUtil.cc:518
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
backSubst
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
Definition facAlgFuncUtil.cc:178
QuasiInverse
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
Definition facAlgFuncUtil.cc:578
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition facAlgFuncUtil.cc:120
generateMipo
CanonicalForm generateMipo(int degOfExt)
Definition facAlgFuncUtil.cc:90
deflatePoly
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
Definition facAlgFuncUtil.cc:238
facAlgFuncUtil.h
Utility functions for factorization over algebraic function fields.
sqrfNorm
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.
Definition facAlgFunc.cc:287
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
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
simpleExtension
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
Definition facAlgFunc.cc:313
mapIntoPIE
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,...
Definition facAlgFunc.cc:609
facAlgFunc
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set
Definition facAlgFunc.cc:1043
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
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
Definition cf_factor.cc:103
resultante
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Definition facAlgFunc.cc:179
facAlgFunc.h
Factorization over algebraic function fields.
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
found
bool found
Definition facFactorize.cc:55
tmp2
CFList tmp2
Definition facFqBivar.cc:75
j
int j
Definition facHensel.cc:110
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
ftmpl_functions.h
some useful template functions.
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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
h
STATIC_VAR Poly * h
Definition janet.cc:971
mult
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:647
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:709
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
count
int status int void size_t count
Definition si_signals.h:69
R
#define R
Definition sirandom.c:27
M
#define M
Definition sirandom.c:25
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836