44 if (!
f.inCoeffDomain())
49 while (
i.hasTerms() && !
result.isOne())
71 if (
g.lc().sign() < 0 )
return -
g;
74 else if (
g.isZero() )
76 if (
f.lc().sign() < 0 )
return -
f;
81 if (
f.level() <=
v ||
g.level() <=
v)
87 bool has_alg_var=
false;
118 if (
g.inBaseDomain() ||
f.inBaseDomain())
230 g=
f (vf - t*Palpha.
mvar(), vf);
244 temp=
gcd (
R,
R.deriv (vf));
255 if (testlist.
getFirst().factor().inCoeffDomain())
258 for (
i= testlist;
i.hasItem();
i++)
260 if (
i.getItem().exp() > 1 &&
degree (
i.getItem().factor(),
R.mvar()) > 0)
275 g=
f (vf - t*Palpha.
mvar(), vf);
297 else if (
degree (Extension) > 0)
314 const Variable & Extension,
bool& isFunctionField,
317 CFList Returnlist, Bstar= Astar;
331 Returnlist.
append (denrb);
359 if (!isFunctionField)
370 for (;
j.hasItem();
j++)
372 j.getItem()=
j.getItem() (rb,
i.getItem().mvar());
373 j.getItem()=
j.getItem() (ra, oldR.
mvar());
393 denra=
gcd (ra, deninv);
396 rb=
R.mvar()*denra-
s*ra;
398 for (;
j.hasItem();
j++)
401 i.getItem().mvar()));
402 j.getItem()=
evaluate (
j.getItem(), rb, denrb, powdenra,
405 j.getItem()=
evaluate (
j.getItem(),ra, denra, powdenra, oldR.
mvar());
412 Returnlist.
append (denra);
415 Returnlist.
append (denrb);
431 const Variable & vminpoly,
const CFList & as,
bool isFunctionField)
437 CFList substlist, backSubsts;
439 substlist=
simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
442 f=
subst (
f, Astar, substlist, Rstar, isFunctionField);
445 if (!isFunctionField)
457 if (!
h.inCoeffDomain())
499 else if (
degree (vminpoly) > 0)
513 (void)
norm (
f, Rstar, *Gen,
s,
g,
R,
false);
520 if (normFactors.
getFirst().factor().inCoeffDomain())
522 if (normFactors.
length() < 1 || (normFactors.
length() == 1 && normFactors.
getLast().exp() == 1))
535 for (iter2= normFactors; iter2.
hasItem(); iter2++)
542 fnew= fnew (
g.mvar() +
s*Rstar.
mvar(),
g.mvar());
552 if (
h.level() > Rstar.
level())
567 if (
g.level() <= Rstar.
level())
571 if (normFactors.
getLast().exp() == 1 &&
g.level() > Rstar.
level())
579 else if (normFactors.
getLast().exp() > 1 &&
580 g.level() > Rstar.
level())
612 int j,
exp= 0, tmpExp;
624 if (
i.getItem().deriv() == 0)
630 varsG /=
i.getItem().mvar();
632 lcmVars=
lcm (varsG, lcmVars);
634 while (!varsG.
isOne())
636 if (
i.getItem().deriv (varsG.
level()).isZero())
663 varsG /= varsG.
mvar();
669 for (; ii.hasItem(); ii++)
671 if (ii.getItem() ==
i.getItem())
682 for (; ii.hasItem(); ii++)
691 if (varsGMap[
j].isEmpty())
692 varsGMap[
j]= varsGMapLevel;
700 "wrong length of lists");
724 while (!lcmVars.
isOne())
727 lcmVars /= lcmVars.
mvar();
732 if (varsGMap[
j].isEmpty())
739 if (
iter.
getItem().factor() == iter2.getItem().factor())
765 bool derivZeroF=
false;
766 int j, expF= 0, tmpExp;
780 lcmVars=
lcm (varsF, lcmVars);
785 asnew=
mapIntoPIE (varsMapLevel, lcmVars, as);
815 for (
i= asnew;
i.hasItem();
i++)
839 for (
i= asnew;
i.hasItem();
i++)
852 transform= transBack;
861 transform= transBack;
865 for (
i= transform;
i.hasItem();
i++)
867 if (
degree (
i.getItem(),
f.mvar()) > 0)
869 if (
i.getItem().level() >
f.level())
930 for (
int ii= 1; ii <
level (vf); ii++)
933 for (
i= as;
i.hasItem();
i++)
961 bool isFunctionField= (newuord.
length() > 0);
968 bool derivZero=
f.deriv().isZero();
969 if (isFunctionField && (
degree (Fgcd,
f.mvar()) > 0) && !derivZero)
992 for (
i= Astar;
i.hasItem();
i++)
997 if (newuord.
length() == 0)
1004 Factorlist=
Trager(
f, Astar, vminpoly, as, isFunctionField);
1021 Factorlist=
Trager (
f, Astar, vminpoly, as, isFunctionField);
1030 Factorlist=
Trager (
f, Astar, vminpoly, as, isFunctionField);
1049 if (Factors.
getFirst().factor().inCoeffDomain())
1072 j.getItem().exp()*
i.getItem().exp()));
Rational abs(const Rational &a)
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
This file provides functions to compute characteristic sets.
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
CanonicalForm cd(bCommonDen(FF))
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
modular resultant algorithm as described by G.
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
generate integers, elements of finite fields
Iterators for CanonicalForm's.
int ipower(int b, int m)
int ipower ( int b, int m )
generate all elements in F_p(alpha) starting from 0
CFGenerator * clone() const
static CFGenerator * generate()
virtual class for generators
virtual CanonicalForm item() const
class to iterate through CanonicalForm's
generate all elements in F_p starting from 0
generate integers starting from 0
factory's class for variables
functions to print debug output
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int hasVar(const CanonicalForm &f, const Variable &v)
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
int getDegOfExt(IntList °reelist, int n)
bool isInseparable(const CFList &Astar)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm generateMipo(int degOfExt)
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
Utility functions for factorization over algebraic function fields.
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.
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
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.
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
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,...
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set
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...
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Factorization over algebraic function fields.
const Variable & v
< [in] a sqrfree bivariate poly
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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 mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
gmp_float exp(const gmp_float &a)
int status int void size_t count
void prune(Variable &alpha)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables