![]() |
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 ![]() | |
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}) More... | |
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. 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) | |
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 422 of file cfModGcd.cc.
void eval | ( | const CanonicalForm & | A, |
const CanonicalForm & | B, | ||
CanonicalForm & | Aeval, | ||
CanonicalForm & | Beval, | ||
const CFList & | L | ||
) |
Definition at line 2126 of file cfModGcd.cc.
Definition at line 1972 of file cfModGcd.cc.
CFArray evaluateMonom | ( | const CanonicalForm & | F, |
const CFList & | evalPoints | ||
) |
Definition at line 1933 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 1989 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 313 of file cfModGcd.cc.
Definition at line 4046 of file cfModGcd.cc.
for | ( | ; | i, |
0;i-- | |||
) |
Definition at line 4058 of file cfModGcd.cc.
|
inlinestatic |
Definition at line 1159 of file cfModGcd.cc.
Definition at line 1721 of file cfModGcd.cc.
Definition at line 1766 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 1898 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 807 of file cfModGcd.cc.
Definition at line 71 of file cfModGcd.cc.
if | ( | i | = =0 | ) |
CanonicalForm modGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CanonicalForm & | coF, | ||
CanonicalForm & | coG, | ||
bool & | topLevel, | ||
CFList & | l | ||
) |
Definition at line 1206 of file cfModGcd.cc.
CanonicalForm modGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
bool & | topLevel, | ||
CFList & | l | ||
) |
Definition at line 1197 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 467 of file cfModGcd.cc.
CanonicalForm modGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 453 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 860 of file cfModGcd.cc.
CanonicalForm modGCDGF | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 846 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 2140 of file cfModGcd.cc.
multiply two lists componentwise
Definition at line 2117 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 93 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 366 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 2424 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 381 of file cfModGcd.cc.
Definition at line 1692 of file cfModGcd.cc.
Definition at line 1614 of file cfModGcd.cc.
Definition at line 1805 of file cfModGcd.cc.
Definition at line 1857 of file cfModGcd.cc.
Definition at line 1561 of file cfModGcd.cc.
CanonicalForm sparseGCDFp | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
bool & | topLevel, | ||
CFList & | l | ||
) |
Definition at line 3503 of file cfModGcd.cc.
CanonicalForm sparseGCDFq | ( | const CanonicalForm & | F, |
const CanonicalForm & | G, | ||
const Variable & | alpha, | ||
CFList & | l, | ||
bool & | topLevel | ||
) |
Definition at line 3071 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 283 of file cfModGcd.cc.
CanonicalForm uni_content | ( | const CanonicalForm & | F, |
const Variable & | x | ||
) |
Definition at line 261 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 341 of file cfModGcd.cc.
while | ( | true | ) |
Definition at line 4073 of file cfModGcd.cc.
b = 1 |
Definition at line 4044 of file cfModGcd.cc.
Definition at line 69 of file cfModGcd.cc.
cd = bCommonDen( GG ) |
Definition at line 4030 of file cfModGcd.cc.
CanonicalForm cDn |
Definition at line 4070 of file cfModGcd.cc.
Definition at line 4024 of file cfModGcd.cc.
Definition at line 4024 of file cfModGcd.cc.
Definition at line 4041 of file cfModGcd.cc.
Definition at line 66 of file cfModGcd.cc.
CanonicalForm cof |
Definition at line 4070 of file cfModGcd.cc.
CanonicalForm cofn |
Definition at line 4070 of file cfModGcd.cc.
CanonicalForm cofp |
Definition at line 4070 of file cfModGcd.cc.
Definition at line 66 of file cfModGcd.cc.
CanonicalForm cog |
Definition at line 4070 of file cfModGcd.cc.
CanonicalForm cogn |
Definition at line 4070 of file cfModGcd.cc.
CanonicalForm cogp |
Definition at line 4070 of file cfModGcd.cc.
int d_deg =-1 |
Definition at line 4019 of file cfModGcd.cc.
Definition at line 4037 of file cfModGcd.cc.
int dp_deg |
Definition at line 4019 of file cfModGcd.cc.
bool equal = false |
Definition at line 4067 of file cfModGcd.cc.
f =cd*FF |
Definition at line 4022 of file cfModGcd.cc.
return false |
Definition at line 84 of file cfModGcd.cc.
Definition at line 4043 of file cfModGcd.cc.
Definition at line 66 of file cfModGcd.cc.
Definition at line 4031 of file cfModGcd.cc.
CanonicalForm gcdcfcg = gcd (cf, cg) |
Definition at line 4042 of file cfModGcd.cc.
const CanonicalForm& GG |
Definition at line 4017 of file cfModGcd.cc.
Definition at line 4043 of file cfModGcd.cc.
i = cf_getNumBigPrimes() - 1 |
Definition at line 4019 of file cfModGcd.cc.
lcf = f.lc() |
Definition at line 4038 of file cfModGcd.cc.
lcg = g.lc() |
Definition at line 4038 of file cfModGcd.cc.
|
static |
Definition at line 89 of file cfModGcd.cc.
int maxNumVars = tmax (getNumVars (f), getNumVars (g)) |
Definition at line 4071 of file cfModGcd.cc.
int minCommonDeg = 0 |
Definition at line 4045 of file cfModGcd.cc.
CanonicalForm newCof |
Definition at line 4070 of file cfModGcd.cc.
CanonicalForm newCog |
Definition at line 4070 of file cfModGcd.cc.
int p |
Definition at line 4019 of file cfModGcd.cc.
CanonicalForm test = 0 |
Definition at line 4037 of file cfModGcd.cc.
Definition at line 4023 of file cfModGcd.cc.