![]() |
This file implements the GCD of two multivariate polynomials over Q or F_q using EZ-GCD as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahnn. More...
#include "config.h"
#include "timing.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cfEzgcd.h"
#include "cfModGcd.h"
#include "cf_util.h"
#include "cf_map_ext.h"
#include "cf_algorithm.h"
#include "cf_reval.h"
#include "cf_random.h"
#include "cf_primes.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "facHensel.h"
#include "NTLconvert.h"
Go to the source code of this file.
Functions | |
TIMING_DEFINE_PRINT (ez_eval) TIMING_DEFINE_PRINT(ez_compress) TIMING_DEFINE_PRINT(ez_hensel_lift) TIMING_DEFINE_PRINT(ez_content) TIMING_DEFINE_PRINT(ez_termination) static int compress4EZGCD(const CanonicalForm &F | |
for (int i=0;i<=n;i++) degsf[i] | |
if (both_non_zero==0) | |
while (k > 0) | |
static CanonicalForm | myShift2Zero (const CanonicalForm &F, CFList &Feval, const CFList &evaluation) |
static CanonicalForm | myReverseShift (const CanonicalForm &F, const CFList &evaluation) |
static Evaluation | optimize4Lift (const CanonicalForm &F, CFMap &M, CFMap &N, const Evaluation &A) |
static int | Hensel (const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs) |
static bool | findeval (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Fb, CanonicalForm &Gb, CanonicalForm &Db, REvaluation &b, int delta, int degF, int degG, int maxeval, int &count, int &k, int bound, int &l) |
static CanonicalForm | ezgcd (const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal) |
real implementation of EZGCD over Z More... | |
CanonicalForm | ezgcd (const CanonicalForm &FF, const CanonicalForm &GG) |
Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm. More... | |
CanonicalForm | EZGCD_P (const CanonicalForm &FF, const CanonicalForm &GG) |
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm. More... | |
Variables | |
static const double | log2exp = 1.442695041 |
const CanonicalForm & | G |
const CanonicalForm CFMap & | M |
const CanonicalForm CFMap CFMap & | N |
const CanonicalForm CFMap CFMap int & | both_non_zero |
int * | degsf = new int [n + 1] |
int * | degsg = new int [n + 1] |
int | f_zero = 0 |
int | g_zero = 0 |
int | k = 1 |
int | l = 1 |
int | m = tmin (F.level(), G.level()) |
int | max_min_deg |
int | i = 1 |
static int | maxNumEval = 200 |
static int | sizePerVars1 = 500 |
This file implements the GCD of two multivariate polynomials over Q or F_q using EZ-GCD as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahnn.
Definition in file cfEzgcd.cc.
|
static |
real implementation of EZGCD over Z
—> A2
—> A3
—> A4
—> A5
—> A6
—> A7
—> A8 (gcdfound)
—> A9
Definition at line 438 of file cfEzgcd.cc.
CanonicalForm ezgcd | ( | const CanonicalForm & | FF, |
const CanonicalForm & | GG | ||
) |
Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm.
Definition at line 783 of file cfEzgcd.cc.
CanonicalForm EZGCD_P | ( | const CanonicalForm & | FF, |
const CanonicalForm & | GG | ||
) |
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.
Definition at line 802 of file cfEzgcd.cc.
|
static |
Definition at line 371 of file cfEzgcd.cc.
Definition at line 66 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 290 of file cfEzgcd.cc.
if | ( | both_non_zero | = = 0 | ) |
Definition at line 85 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 205 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 185 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 220 of file cfEzgcd.cc.
TIMING_DEFINE_PRINT | ( | ez_eval | ) | const |
while | ( | k | , |
0 | |||
) |
Definition at line 124 of file cfEzgcd.cc.
return both_non_zero |
Definition at line 51 of file cfEzgcd.cc.
delete [] degsf = new int [n + 1] |
Definition at line 53 of file cfEzgcd.cc.
delete [] degsg = new int [n + 1] |
Definition at line 54 of file cfEzgcd.cc.
int f_zero = 0 |
Definition at line 63 of file cfEzgcd.cc.
Definition at line 49 of file cfEzgcd.cc.
int g_zero = 0 |
Definition at line 64 of file cfEzgcd.cc.
int i = 1 |
Definition at line 123 of file cfEzgcd.cc.
k = 1 |
Definition at line 93 of file cfEzgcd.cc.
l = 1 |
Definition at line 94 of file cfEzgcd.cc.
|
static |
Definition at line 40 of file cfEzgcd.cc.
Definition at line 49 of file cfEzgcd.cc.
Definition at line 119 of file cfEzgcd.cc.
int max_min_deg |
Definition at line 120 of file cfEzgcd.cc.
|
static |
Definition at line 797 of file cfEzgcd.cc.
Definition at line 49 of file cfEzgcd.cc.
|
static |
Definition at line 798 of file cfEzgcd.cc.