![]() |
My Project
|
This file implements the GCD of two polynomials over
#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 | |
static CanonicalForm | uni_content (const CanonicalForm &F) |
compute the content of F, where F is considered as an element of ![]() | |
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 ![]() ![]() | |
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}) | |
static CanonicalForm | randomElement (const CanonicalForm &F, const Variable &alpha, CFList &list, bool &fail) |
compute a random element a of ![]() ![]() | |
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 ![]() | |
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) ![]() | |
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. | |
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. | |
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 | |
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 | |
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 | |
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
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 2184 of file cfModGcd.cc.
Definition at line 2030 of file cfModGcd.cc.
CFArray evaluateMonom | ( | const CanonicalForm & | F, |
const CFList & | evalPoints | ||
) |
Definition at line 1991 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 2047 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 4116 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 1956 of file cfModGcd.cc.
|
inlinestatic |
compute a random element a of GF, s.t. F(a)
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
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 2198 of file cfModGcd.cc.
multiply two lists componentwise
Definition at line 2175 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 2482 of file cfModGcd.cc.
|
inlinestatic |
compute a random element a of
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 1839 of file cfModGcd.cc.
Definition at line 1891 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 3561 of file cfModGcd.cc.
CanonicalForm sparseGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 3129 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
Definition at line 339 of file cfModGcd.cc.
while | ( | true | ) |
Definition at line 4131 of file cfModGcd.cc.
else L b = 1 |
Definition at line 4102 of file cfModGcd.cc.
Definition at line 68 of file cfModGcd.cc.
cd | ( | bCommonDen(FF) | ) | = bCommonDen( GG ) |
Definition at line 4088 of file cfModGcd.cc.
CanonicalForm cDn |
Definition at line 4128 of file cfModGcd.cc.
Definition at line 4082 of file cfModGcd.cc.
Definition at line 4082 of file cfModGcd.cc.
Definition at line 4099 of file cfModGcd.cc.
Definition at line 67 of file cfModGcd.cc.
CanonicalForm cof |
Definition at line 4128 of file cfModGcd.cc.
CanonicalForm cofn |
Definition at line 4128 of file cfModGcd.cc.
CanonicalForm cofp |
Definition at line 4128 of file cfModGcd.cc.
Definition at line 67 of file cfModGcd.cc.
CanonicalForm cog |
Definition at line 4128 of file cfModGcd.cc.
CanonicalForm cogn |
Definition at line 4128 of file cfModGcd.cc.
CanonicalForm cogp |
Definition at line 4128 of file cfModGcd.cc.
int d_deg =-1 |
Definition at line 4077 of file cfModGcd.cc.
Definition at line 4095 of file cfModGcd.cc.
int dp_deg |
Definition at line 4077 of file cfModGcd.cc.
bool equal = false |
Definition at line 4125 of file cfModGcd.cc.
f =cd*FF |
Definition at line 4080 of file cfModGcd.cc.
return false |
Definition at line 84 of file cfModGcd.cc.
Definition at line 4101 of file cfModGcd.cc.
Definition at line 66 of file cfModGcd.cc.
Definition at line 4089 of file cfModGcd.cc.
CanonicalForm gcdcfcg = gcd (cf, cg) |
Definition at line 4100 of file cfModGcd.cc.
const CanonicalForm& GG |
Definition at line 4074 of file cfModGcd.cc.
Definition at line 4101 of file cfModGcd.cc.
i = cf_getNumBigPrimes() - 1 |
Definition at line 4077 of file cfModGcd.cc.
lcf = f.lc() |
Definition at line 4096 of file cfModGcd.cc.
lcg = g.lc() |
Definition at line 4096 of file cfModGcd.cc.
int maxNumVars = tmax (getNumVars (f), getNumVars (g)) |
Definition at line 4129 of file cfModGcd.cc.
int minCommonDeg = 0 |
Definition at line 4103 of file cfModGcd.cc.
CanonicalForm newCof |
Definition at line 4128 of file cfModGcd.cc.
CanonicalForm newCog |
Definition at line 4128 of file cfModGcd.cc.
int p |
Definition at line 4077 of file cfModGcd.cc.
CanonicalForm test = 0 |
Definition at line 4095 of file cfModGcd.cc.
Definition at line 4081 of file cfModGcd.cc.