![]() |
My Project
|
This file implements the GCD of two polynomials over
#include "config.h"
#include <math.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 421 of file cfModGcd.cc.
void eval | ( | const CanonicalForm & | A, |
const CanonicalForm & | B, | ||
CanonicalForm & | Aeval, | ||
CanonicalForm & | Beval, | ||
const CFList & | L ) |
Definition at line 2193 of file cfModGcd.cc.
Definition at line 2039 of file cfModGcd.cc.
CFArray evaluateMonom | ( | const CanonicalForm & | F, |
const CFList & | evalPoints ) |
Definition at line 2000 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 2056 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 312 of file cfModGcd.cc.
for | ( | ; | i, |
0;i-- | ) |
Definition at line 4125 of file cfModGcd.cc.
|
inlinestatic |
Definition at line 1172 of file cfModGcd.cc.
Definition at line 1740 of file cfModGcd.cc.
Definition at line 1785 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 1965 of file cfModGcd.cc.
|
inlinestatic |
compute a random element a of GF, s.t. F(a)
Definition at line 820 of file cfModGcd.cc.
if | ( | i | = =0 | ) |
Definition at line 72 of file cfModGcd.cc.
CanonicalForm modGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
bool & | topLevel, | ||
CFList & | l ) |
Definition at line 1213 of file cfModGcd.cc.
CanonicalForm modGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | coF, | ||
CanonicalForm & | coG, | ||
bool & | topLevel, | ||
CFList & | l ) |
Definition at line 1224 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 479 of file cfModGcd.cc.
CanonicalForm modGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel ) |
Definition at line 463 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 873 of file cfModGcd.cc.
CanonicalForm modGCDGF | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CFList & | l, | ||
bool & | topLevel ) |
Definition at line 859 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 2207 of file cfModGcd.cc.
multiply two lists componentwise
Definition at line 2184 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 92 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 365 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 2491 of file cfModGcd.cc.
|
inlinestatic |
compute a random element a of
Definition at line 380 of file cfModGcd.cc.
Definition at line 1711 of file cfModGcd.cc.
M in row echolon form, rk rank of M.
Definition at line 1689 of file cfModGcd.cc.
Definition at line 1633 of file cfModGcd.cc.
Definition at line 1844 of file cfModGcd.cc.
Definition at line 1896 of file cfModGcd.cc.
Definition at line 1580 of file cfModGcd.cc.
CanonicalForm sparseGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
bool & | topLevel, | ||
CFList & | l ) |
Definition at line 3570 of file cfModGcd.cc.
CanonicalForm sparseGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel ) |
Definition at line 3138 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 282 of file cfModGcd.cc.
CanonicalForm uni_content | ( | const CanonicalForm & | F, |
const Variable & | x ) |
Definition at line 260 of file cfModGcd.cc.
|
inlinestatic |
compute the leading coefficient of F, where F is considered as an element of
Definition at line 340 of file cfModGcd.cc.
while | ( | true | ) |
Definition at line 4140 of file cfModGcd.cc.
else L b = 1 |
Definition at line 4111 of file cfModGcd.cc.
Definition at line 69 of file cfModGcd.cc.
cd | ( | bCommonDen(FF) | ) | = bCommonDen( GG ) |
Definition at line 4097 of file cfModGcd.cc.
CanonicalForm cDn |
Definition at line 4137 of file cfModGcd.cc.
Definition at line 4091 of file cfModGcd.cc.
Definition at line 4091 of file cfModGcd.cc.
Definition at line 4108 of file cfModGcd.cc.
Definition at line 68 of file cfModGcd.cc.
CanonicalForm cof |
Definition at line 4137 of file cfModGcd.cc.
CanonicalForm cofn |
Definition at line 4137 of file cfModGcd.cc.
CanonicalForm cofp |
Definition at line 4137 of file cfModGcd.cc.
Definition at line 68 of file cfModGcd.cc.
CanonicalForm cog |
Definition at line 4137 of file cfModGcd.cc.
CanonicalForm cogn |
Definition at line 4137 of file cfModGcd.cc.
CanonicalForm cogp |
Definition at line 4137 of file cfModGcd.cc.
int d_deg =-1 |
Definition at line 4086 of file cfModGcd.cc.
Definition at line 4104 of file cfModGcd.cc.
int dp_deg |
Definition at line 4086 of file cfModGcd.cc.
bool equal = false |
Definition at line 4134 of file cfModGcd.cc.
f =cd*FF |
Definition at line 4089 of file cfModGcd.cc.
return false |
Definition at line 85 of file cfModGcd.cc.
Definition at line 4110 of file cfModGcd.cc.
Definition at line 67 of file cfModGcd.cc.
Definition at line 4098 of file cfModGcd.cc.
CanonicalForm gcdcfcg = gcd (cf, cg) |
Definition at line 4109 of file cfModGcd.cc.
const CanonicalForm& GG |
Definition at line 4083 of file cfModGcd.cc.
Definition at line 4110 of file cfModGcd.cc.
i = cf_getNumBigPrimes() - 1 |
Definition at line 4086 of file cfModGcd.cc.
lcf = f.lc() |
Definition at line 4105 of file cfModGcd.cc.
lcg = g.lc() |
Definition at line 4105 of file cfModGcd.cc.
int maxNumVars = tmax (getNumVars (f), getNumVars (g)) |
Definition at line 4138 of file cfModGcd.cc.
int minCommonDeg = 0 |
Definition at line 4112 of file cfModGcd.cc.
CanonicalForm newCof |
Definition at line 4137 of file cfModGcd.cc.
CanonicalForm newCog |
Definition at line 4137 of file cfModGcd.cc.
int p |
Definition at line 4086 of file cfModGcd.cc.
CanonicalForm test = 0 |
Definition at line 4104 of file cfModGcd.cc.
Definition at line 4090 of file cfModGcd.cc.