 |
My Project
UNKNOWN_GIT_VERSION
|
This file provides functions to factorize polynomials over alg.
More...
#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"
Go to the source code of this file.
|
void | out_cf (const char *s1, const CanonicalForm &f, const char *s2) |
| cf_algorithm.cc - simple mathematical algorithms. More...
|
|
CanonicalForm | alg_content (const CanonicalForm &f, const CFList &as) |
|
CanonicalForm | alg_gcd (const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as) |
|
static CanonicalForm | resultante (const CanonicalForm &f, const CanonicalForm &g, const Variable &v) |
|
static CFFList | norm (const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof) |
| 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. More...
|
|
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. More...
|
|
static CFList | simpleExtension (CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R) |
|
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. More...
|
|
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, i.e varsMapLevel contains a list of pairs of variables and integers such that More...
|
|
CFFList | SteelTrager (const CanonicalForm &f, const CFList &AS) |
| 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 More...
|
|
CFFList | facAlgFunc2 (const CanonicalForm &f, const CFList &as) |
| factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set More...
|
|
CFFList | facAlgFunc (const CanonicalForm &f, const CFList &as) |
| factorize a polynomial modulo an extension given by an irreducible characteristic set More...
|
|
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
Definition in file facAlgFunc.cc.
◆ alg_content()
◆ alg_gcd()
Definition at line 61 of file facAlgFunc.cc.
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())
◆ facAlgFunc()
factorize a polynomial modulo an extension given by an irreducible characteristic set
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.
1049 if (Factors.
getFirst().factor().inCoeffDomain())
1072 j.getItem().exp()*
i.getItem().exp()));
◆ facAlgFunc2()
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set
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.
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);
◆ mapIntoPIE()
map elements in AS into a PIE
and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables
and integers
such that
Definition at line 609 of file facAlgFunc.cc.
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())
◆ norm()
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.
Definition at line 206 of file facAlgFunc.cc.
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);
◆ out_cf()
cf_algorithm.cc - simple mathematical algorithms.
Hierarchy: mathematical algorithms on canonical forms
Developers note:
A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.
Compare these functions to the functions in ‘cf_ops.cc’, which are structural algorithms.
Definition at line 90 of file cf_factor.cc.
93 if (
f.isZero()) printf(
"+0");
95 else if (!
f.inBaseDomain() )
101 if (
i.coeff().isOne())
104 if (e==0) printf(
"1");
108 if (e!=1) printf(
"^%d",e);
117 if (e!=1) printf(
"^%d",e);
142 printf(
"+%ld",
f.intval());
151 char * str =
new char[mpz_sizeinbase(
m, 10 ) + 2];
152 str = mpz_get_str( str, 10,
m );
161 char * str =
new char[mpz_sizeinbase(
m, 10 ) + 2];
162 str = mpz_get_str( str, 10,
m );
163 puts(str);putchar(
'/');
167 str =
new char[mpz_sizeinbase(
m, 10 ) + 2];
168 str = mpz_get_str( str, 10,
m );
183 if (
f.inExtension()) printf(
"E(%d)",
f.level());
◆ resultante()
◆ simpleExtension()
Definition at line 313 of file facAlgFunc.cc.
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);
◆ sqrfNorm()
see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm.
Definition at line 287 of file facAlgFunc.cc.
297 else if (
degree (Extension) > 0)
◆ SteelTrager()
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
Definition at line 759 of file facAlgFunc.cc.
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())
◆ Trager()
Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.
Definition at line 430 of file facAlgFunc.cc.
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())
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
static const int SW_RATIONAL
set to 1 for computations over Q
generate integers starting from 0
class to iterate through CanonicalForm's
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
const CanonicalForm int const CFList const Variable & y
bool isInseparable(const CFList &Astar)
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
virtual class for generators
bool delta(X x, Y y, D d)
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 CFFList norm(const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addi...
#define GaloisFieldDomain
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
#define ASSERT(expression, message)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
Rational abs(const Rational &a)
CanonicalForm cd(bCommonDen(FF))
generate all elements in F_p starting from 0
void prune(Variable &alpha)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
int ipower(int b, int m)
int ipower ( int b, int m )
gmp_float exp(const gmp_float &a)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
static long imm2int(const InternalCF *const imm)
factory's class for variables
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
int getDegOfExt(IntList °reelist, int n)
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...
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
const Variable & v
< [in] a sqrfree bivariate poly
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
const CanonicalForm int s
int status int void size_t count
static int * multiplicity
CFGenerator * clone() const
int hasVar(const CanonicalForm &f, const Variable &v)
virtual CanonicalForm item() const
static CFGenerator * generate()
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
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 generateMipo(int degOfExt)
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,...
generate all elements in F_p(alpha) starting from 0