![]() |
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.