My Project
|
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_iter.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 "FLINTconvert.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) | |
DELETE_ARRAY (degsf) | |
DELETE_ARRAY (degsg) | |
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 void | gcd_mon_rec (CanonicalForm G, CanonicalForm &cf, int *exp, int pl) |
static CanonicalForm | gcd_mon (CanonicalForm F, CanonicalForm G) |
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_ARRAY(int,n + 1) |
int * | degsg = NEW_ARRAY(int,n + 1) |
int | f_zero = 0 |
int | g_zero = 0 |
int | k = 1 |
int | l = 1 |
int | Flevel =F.level() |
int | Glevel =G.level() |
int | m = tmin (Flevel, Glevel) |
int | max_min_deg |
int | i = 1 |
STATIC_VAR int | maxNumEval = 200 |
STATIC_VAR 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.
DELETE_ARRAY | ( | degsf | ) |
DELETE_ARRAY | ( | degsg | ) |
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 861 of file cfEzgcd.cc.
|
static |
real implementation of EZGCD over Z
—> A2
—> A3
—> A4
—> A5
—> A6
—> A7
—> A8 (gcdfound)
—> A9
Definition at line 498 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 876 of file cfEzgcd.cc.
|
static |
Definition at line 386 of file cfEzgcd.cc.
Definition at line 72 of file cfEzgcd.cc.
|
static |
Definition at line 470 of file cfEzgcd.cc.
|
static |
Definition at line 452 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 302 of file cfEzgcd.cc.
if | ( | both_non_zero | = = 0 | ) |
Definition at line 91 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 215 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 195 of file cfEzgcd.cc.
|
inlinestatic |
Definition at line 231 of file cfEzgcd.cc.
TIMING_DEFINE_PRINT | ( | ez_eval | ) | const & |
while | ( | k | , |
0 | |||
) |
return both_non_zero |
Definition at line 56 of file cfEzgcd.cc.
degsf = NEW_ARRAY(int,n + 1) |
Definition at line 59 of file cfEzgcd.cc.
degsg = NEW_ARRAY(int,n + 1) |
Definition at line 60 of file cfEzgcd.cc.
int f_zero = 0 |
Definition at line 69 of file cfEzgcd.cc.
int Flevel =F.level() |
Definition at line 101 of file cfEzgcd.cc.
Definition at line 55 of file cfEzgcd.cc.
int g_zero = 0 |
Definition at line 70 of file cfEzgcd.cc.
int Glevel =G.level() |
Definition at line 102 of file cfEzgcd.cc.
int i = 1 |
Definition at line 132 of file cfEzgcd.cc.
k = 1 |
Definition at line 99 of file cfEzgcd.cc.
l = 1 |
Definition at line 100 of file cfEzgcd.cc.
|
static |
Definition at line 45 of file cfEzgcd.cc.
Definition at line 55 of file cfEzgcd.cc.
Definition at line 128 of file cfEzgcd.cc.
int max_min_deg |
Definition at line 129 of file cfEzgcd.cc.
STATIC_VAR int maxNumEval = 200 |
Definition at line 871 of file cfEzgcd.cc.
Definition at line 56 of file cfEzgcd.cc.
STATIC_VAR int sizePerVars1 = 500 |
Definition at line 872 of file cfEzgcd.cc.