My Project
|
This file implements the GCD of two polynomials over , , GF or Z based on Alg. More...
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "canonicalform.h"
#include "cfGcdUtil.h"
#include "cf_map.h"
#include "cf_util.h"
#include "cf_irred.h"
#include "templates/ftmpl_functions.h"
#include "cf_random.h"
#include "cf_reval.h"
#include "facHensel.h"
#include "cf_iter.h"
#include "cfNewtonPolygon.h"
#include "cf_algorithm.h"
#include "cf_primes.h"
#include "cf_map_ext.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
#include "cfModGcd.h"
Go to the source code of this file.
Functions | |
TIMING_DEFINE_PRINT (gcd_recursion) TIMING_DEFINE_PRINT(newton_interpolation) TIMING_DEFINE_PRINT(termination_test) TIMING_DEFINE_PRINT(ez_p_compress) TIMING_DEFINE_PRINT(ez_p_hensel_lift) TIMING_DEFINE_PRINT(ez_p_eval) TIMING_DEFINE_PRINT(ez_p_content) bool terminationTest(const CanonicalForm &F | |
if (LCCand *abs(LC(coF))==abs(LC(F))) | |
int | myCompress (const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel) |
compressing two polynomials F and G, M is used for compressing, N to reverse the compression More... | |
static CanonicalForm | uni_content (const CanonicalForm &F) |
compute the content of F, where F is considered as an element of More... | |
CanonicalForm | uni_content (const CanonicalForm &F, const Variable &x) |
CanonicalForm | extractContents (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &contentF, CanonicalForm &contentG, CanonicalForm &ppF, CanonicalForm &ppG, const int d) |
static CanonicalForm | uni_lcoeff (const CanonicalForm &F) |
compute the leading coefficient of F, where F is considered as an element of , order on is dp. More... | |
static CanonicalForm | newtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x) |
Newton interpolation - Incremental algorithm. Given a list of values alpha_i and a list of polynomials u_i, 1 <= i <= n, computes the interpolation polynomial assuming that the polynomials in u are the results of evaluating the variabe x of the unknown polynomial at the alpha values. This incremental version receives only the values of alpha_n and u_n and the previous interpolation polynomial for points 1 <= i <= n-1, and computes the polynomial interpolating in all the points. newtonPoly must be equal to (x - alpha_1) * ... * (x - alpha_{n-1}) More... | |
static CanonicalForm | randomElement (const CanonicalForm &F, const Variable &alpha, CFList &list, bool &fail) |
compute a random element a of , s.t. F(a) , F is a univariate polynomial, returns fail if there are no field elements left which have not been used before More... | |
static Variable | chooseExtension (const Variable &alpha) |
CanonicalForm | modGCDFq (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel) |
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg. 7.2. as described in "Algorithms for
Computer Algebra" by Geddes, Czapor, Labahn. More... | |
CanonicalForm | modGCDFq (const CanonicalForm &F, const CanonicalForm &G, Variable &alpha, CFList &l, bool &topLevel) |
static CanonicalForm | GFRandomElement (const CanonicalForm &F, CFList &list, bool &fail) |
compute a random element a of GF, s.t. F(a) , F is a univariate polynomial, returns fail if there are no field elements left which have not been used before More... | |
CanonicalForm | modGCDGF (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel) |
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for
Computer Algebra" by Geddes, Czapor, Labahn Usually this algorithm will be faster than modGCDFq since GF has faster field arithmetics, however it might fail if the input is large since the size of the base field is bounded by 2^16, output is monic. More... | |
CanonicalForm | modGCDGF (const CanonicalForm &F, const CanonicalForm &G, CFList &l, bool &topLevel) |
static CanonicalForm | FpRandomElement (const CanonicalForm &F, CFList &list, bool &fail) |
CanonicalForm | modGCDFp (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l) |
CanonicalForm | modGCDFp (const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l) |
CFArray | solveVandermonde (const CFArray &M, const CFArray &A) |
CFArray | solveGeneralVandermonde (const CFArray &M, const CFArray &A) |
CFArray | readOffSolution (const CFMatrix &M, const long rk) |
M in row echolon form, rk rank of M. More... | |
CFArray | readOffSolution (const CFMatrix &M, const CFArray &L, const CFArray &partialSol) |
long | gaussianElimFp (CFMatrix &M, CFArray &L) |
long | gaussianElimFq (CFMatrix &M, CFArray &L, const Variable &alpha) |
CFArray | solveSystemFp (const CFMatrix &M, const CFArray &L) |
CFArray | solveSystemFq (const CFMatrix &M, const CFArray &L, const Variable &alpha) |
CFArray | getMonoms (const CanonicalForm &F) |
extract monomials of F, parts in algebraic variable are considered coefficients More... | |
CFArray | evaluateMonom (const CanonicalForm &F, const CFList &evalPoints) |
CFArray | evaluate (const CFArray &A, const CFList &evalPoints) |
CFList | evaluationPoints (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Feval, CanonicalForm &Geval, const CanonicalForm &LCF, const bool &GF, const Variable &alpha, bool &fail, CFList &list) |
void | mult (CFList &L1, const CFList &L2) |
multiply two lists componentwise More... | |
void | eval (const CanonicalForm &A, const CanonicalForm &B, CanonicalForm &Aeval, CanonicalForm &Beval, const CFList &L) |
CanonicalForm | monicSparseInterpol (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms) |
CanonicalForm | nonMonicSparseInterpol (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms) |
CanonicalForm | sparseGCDFq (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel) |
CanonicalForm | sparseGCDFp (const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l) |
TIMING_DEFINE_PRINT (modZ_termination) TIMING_DEFINE_PRINT(modZ_recursion) CanonicalForm modGCDZ(const CanonicalForm &FF | |
modular gcd algorithm, see Keith, Czapor, Geddes "Algorithms for Computer
Algebra", Algorithm 7.1 More... | |
for (i=tmax(f.level(), g.level());i > 0;i--) | |
if (i==0) return gcdcfcg | |
for (;i > 0;i--) | |
while (true) | |
Variables | |
const CanonicalForm & | G |
const CanonicalForm const CanonicalForm & | coF |
const CanonicalForm const CanonicalForm const CanonicalForm & | coG |
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & | cand |
return | false |
const CanonicalForm & | GG |
int | p |
int | i = cf_getNumBigPrimes() - 1 |
int | dp_deg |
int | d_deg =-1 |
CanonicalForm | cd (bCommonDen(FF)) = bCommonDen( GG ) |
f =cd*FF | |
Variable | x = Variable (1) |
CanonicalForm | cf = icontent (f) |
CanonicalForm | cg = icontent (g) |
g =cd*GG | |
CanonicalForm | Dn |
CanonicalForm | test = 0 |
CanonicalForm | lcf = f.lc() |
CanonicalForm | lcg = g.lc() |
cl = gcd (f.lc(),g.lc()) | |
CanonicalForm | gcdcfcg = gcd (cf, cg) |
CanonicalForm | fp |
CanonicalForm | gp |
CanonicalForm | b = 1 |
int | minCommonDeg = 0 |
bool | equal = false |
CanonicalForm | cof |
CanonicalForm | cog |
CanonicalForm | cofp |
CanonicalForm | cogp |
CanonicalForm | newCof |
CanonicalForm | newCog |
CanonicalForm | cofn |
CanonicalForm | cogn |
CanonicalForm | cDn |
int | maxNumVars = tmax (getNumVars (f), getNumVars (g)) |
This file implements the GCD of two polynomials over , , GF or Z based on Alg.
7.1. and 7.2. as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahn via modular computations. And sparse modular variants as described in Zippel "Effective Polynomial Computation", deKleine, Monagan, Wittkopf "Algorithms for the non-monic case of the sparse modular GCD algorithm" and Javadi "A new solution to the normalization problem"
Definition in file cfModGcd.cc.
Definition at line 420 of file cfModGcd.cc.
void eval | ( | const CanonicalForm & | A, |
const CanonicalForm & | B, | ||
CanonicalForm & | Aeval, | ||
CanonicalForm & | Beval, | ||
const CFList & | L | ||
) |
Definition at line 2185 of file cfModGcd.cc.
Definition at line 2031 of file cfModGcd.cc.
CFArray evaluateMonom | ( | const CanonicalForm & | F, |
const CFList & | evalPoints | ||
) |
Definition at line 1992 of file cfModGcd.cc.
CFList evaluationPoints | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | Feval, | ||
CanonicalForm & | Geval, | ||
const CanonicalForm & | LCF, | ||
const bool & | GF, | ||
const Variable & | alpha, | ||
bool & | fail, | ||
CFList & | list | ||
) |
Definition at line 2048 of file cfModGcd.cc.
CanonicalForm extractContents | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | contentF, | ||
CanonicalForm & | contentG, | ||
CanonicalForm & | ppF, | ||
CanonicalForm & | ppG, | ||
const int | d | ||
) |
Definition at line 311 of file cfModGcd.cc.
for | ( | ; | i, |
0;i-- | |||
) |
Definition at line 4117 of file cfModGcd.cc.
|
inlinestatic |
Definition at line 1171 of file cfModGcd.cc.
Definition at line 1739 of file cfModGcd.cc.
Definition at line 1784 of file cfModGcd.cc.
CFArray getMonoms | ( | const CanonicalForm & | F | ) |
extract monomials of F, parts in algebraic variable are considered coefficients
[in] | F | some poly |
Definition at line 1957 of file cfModGcd.cc.
|
inlinestatic |
compute a random element a of GF, s.t. F(a) , F is a univariate polynomial, returns fail if there are no field elements left which have not been used before
Definition at line 819 of file cfModGcd.cc.
if | ( | i | = =0 | ) |
Definition at line 71 of file cfModGcd.cc.
CanonicalForm modGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
bool & | topLevel, | ||
CFList & | l | ||
) |
Definition at line 1212 of file cfModGcd.cc.
CanonicalForm modGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | coF, | ||
CanonicalForm & | coG, | ||
bool & | topLevel, | ||
CFList & | l | ||
) |
Definition at line 1223 of file cfModGcd.cc.
CanonicalForm modGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | coF, | ||
CanonicalForm & | coG, | ||
Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahn.
Definition at line 478 of file cfModGcd.cc.
CanonicalForm modGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 462 of file cfModGcd.cc.
CanonicalForm modGCDGF | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | coF, | ||
CanonicalForm & | coG, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahn Usually this algorithm will be faster than modGCDFq since GF has faster field arithmetics, however it might fail if the input is large since the size of the base field is bounded by 2^16, output is monic.
Definition at line 872 of file cfModGcd.cc.
CanonicalForm modGCDGF | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 858 of file cfModGcd.cc.
CanonicalForm monicSparseInterpol | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | skeleton, | ||
const Variable & | alpha, | ||
bool & | fail, | ||
CFArray *& | coeffMonoms, | ||
CFArray & | Monoms | ||
) |
Definition at line 2199 of file cfModGcd.cc.
multiply two lists componentwise
Definition at line 2176 of file cfModGcd.cc.
int myCompress | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CFMap & | M, | ||
CFMap & | N, | ||
bool | topLevel | ||
) |
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition at line 91 of file cfModGcd.cc.
|
inlinestatic |
Newton interpolation - Incremental algorithm. Given a list of values alpha_i and a list of polynomials u_i, 1 <= i <= n, computes the interpolation polynomial assuming that the polynomials in u are the results of evaluating the variabe x of the unknown polynomial at the alpha values. This incremental version receives only the values of alpha_n and u_n and the previous interpolation polynomial for points 1 <= i <= n-1, and computes the polynomial interpolating in all the points. newtonPoly must be equal to (x - alpha_1) * ... * (x - alpha_{n-1})
Definition at line 364 of file cfModGcd.cc.
CanonicalForm nonMonicSparseInterpol | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const CanonicalForm & | skeleton, | ||
const Variable & | alpha, | ||
bool & | fail, | ||
CFArray *& | coeffMonoms, | ||
CFArray & | Monoms | ||
) |
Definition at line 2483 of file cfModGcd.cc.
|
inlinestatic |
compute a random element a of , s.t. F(a) , F is a univariate polynomial, returns fail if there are no field elements left which have not been used before
Definition at line 379 of file cfModGcd.cc.
Definition at line 1710 of file cfModGcd.cc.
M in row echolon form, rk rank of M.
Definition at line 1688 of file cfModGcd.cc.
Definition at line 1632 of file cfModGcd.cc.
Definition at line 1840 of file cfModGcd.cc.
Definition at line 1892 of file cfModGcd.cc.
Definition at line 1579 of file cfModGcd.cc.
CanonicalForm sparseGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
bool & | topLevel, | ||
CFList & | l | ||
) |
Definition at line 3562 of file cfModGcd.cc.
CanonicalForm sparseGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 3130 of file cfModGcd.cc.
TIMING_DEFINE_PRINT | ( | gcd_recursion | ) | const & |
TIMING_DEFINE_PRINT | ( | modZ_termination | ) | const & |
modular gcd algorithm, see Keith, Czapor, Geddes "Algorithms for Computer Algebra", Algorithm 7.1
|
inlinestatic |
compute the content of F, where F is considered as an element of
Definition at line 281 of file cfModGcd.cc.
CanonicalForm uni_content | ( | const CanonicalForm & | F, |
const Variable & | x | ||
) |
Definition at line 259 of file cfModGcd.cc.
|
inlinestatic |
compute the leading coefficient of F, where F is considered as an element of , order on is dp.
Definition at line 339 of file cfModGcd.cc.
while | ( | true | ) |
Definition at line 4132 of file cfModGcd.cc.
else L b = 1 |
Definition at line 4103 of file cfModGcd.cc.
Definition at line 68 of file cfModGcd.cc.
cd | ( | bCommonDen(FF) | ) | = bCommonDen( GG ) |
Definition at line 4089 of file cfModGcd.cc.
CanonicalForm cDn |
Definition at line 4129 of file cfModGcd.cc.
Definition at line 4083 of file cfModGcd.cc.
Definition at line 4083 of file cfModGcd.cc.
Definition at line 4100 of file cfModGcd.cc.
Definition at line 67 of file cfModGcd.cc.
CanonicalForm cof |
Definition at line 4129 of file cfModGcd.cc.
CanonicalForm cofn |
Definition at line 4129 of file cfModGcd.cc.
CanonicalForm cofp |
Definition at line 4129 of file cfModGcd.cc.
Definition at line 67 of file cfModGcd.cc.
CanonicalForm cog |
Definition at line 4129 of file cfModGcd.cc.
CanonicalForm cogn |
Definition at line 4129 of file cfModGcd.cc.
CanonicalForm cogp |
Definition at line 4129 of file cfModGcd.cc.
int d_deg =-1 |
Definition at line 4078 of file cfModGcd.cc.
Definition at line 4096 of file cfModGcd.cc.
int dp_deg |
Definition at line 4078 of file cfModGcd.cc.
bool equal = false |
Definition at line 4126 of file cfModGcd.cc.
f =cd*FF |
Definition at line 4081 of file cfModGcd.cc.
return false |
Definition at line 84 of file cfModGcd.cc.
Definition at line 4102 of file cfModGcd.cc.
Definition at line 66 of file cfModGcd.cc.
Definition at line 4090 of file cfModGcd.cc.
CanonicalForm gcdcfcg = gcd (cf, cg) |
Definition at line 4101 of file cfModGcd.cc.
const CanonicalForm& GG |
Definition at line 4075 of file cfModGcd.cc.
Definition at line 4102 of file cfModGcd.cc.
i = cf_getNumBigPrimes() - 1 |
Definition at line 4078 of file cfModGcd.cc.
lcf = f.lc() |
Definition at line 4097 of file cfModGcd.cc.
lcg = g.lc() |
Definition at line 4097 of file cfModGcd.cc.
int maxNumVars = tmax (getNumVars (f), getNumVars (g)) |
Definition at line 4130 of file cfModGcd.cc.
int minCommonDeg = 0 |
Definition at line 4104 of file cfModGcd.cc.
CanonicalForm newCof |
Definition at line 4129 of file cfModGcd.cc.
CanonicalForm newCog |
Definition at line 4129 of file cfModGcd.cc.
int p |
Definition at line 4078 of file cfModGcd.cc.
CanonicalForm test = 0 |
Definition at line 4096 of file cfModGcd.cc.
Definition at line 4082 of file cfModGcd.cc.