 |
My Project
UNKNOWN_GIT_VERSION
|
modular resultant algorithm as described by G.
More...
Go to the source code of this file.
modular resultant algorithm as described by G.
E. Collins in "The Calculation
of multivariate polynomial resultants"
- Author
- Martin Lee
Definition in file cfModResultant.h.
◆ resultantFp()
modular resultant algorihtm over Fp
- Returns
- resultantFp returns the resultant of A and B wrt. x
- Parameters
-
[in] | A | some poly |
[in] | B | some poly |
[in] | x | some polynomial variable |
[in] | prob | if true use probabilistic algorithm |
Definition at line 349 of file cfModResultant.cc.
395 bool extOfExt=
false;
399 if (!algExt && (
p < (1 << 28)))
407 gen= AlgExtGen.
clone();
408 for (
int i= 0;
i <
p;
i++)
422 mpz_init (field_size);
423 mpz_ui_pow_ui (field_size,
p,
427 if (mpz_fits_sint_p (field_size))
433 bool primFail=
false;
436 ASSERT (!primFail,
"failure in integer factorizer");
441 F=
mapUp (F,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
442 G=
mapUp (
G,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
447 mpz_ui_pow_ui (field_size,
p, deg);
451 mpz_ui_pow_ui (field_size,
p, deg);
458 bool primFail=
false;
461 ASSERT (!primFail,
"failure in integer factorizer");
466 F=
mapUp (F,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
467 G=
mapUp (
G,
alpha,
v, primElemAlpha, imPrimElemAlpha, source, dest);
470 mpz_clear (field_size);
473 gen= AlgExtGen.
clone();
474 for (
int i= 0;
i <
p;
i++)
486 H=
newtonInterp ((*gen).item(), recResult, newtonPoly, modResult,
y);
500 if (extOfExt && !
isInExtension (
H, imPrimElemAlpha, 1, primElemAlpha,
503 H=
mapDown (
H, primElemAlpha, imPrimElemAlpha,
alpha, dest, source);
513 newtonPoly *= (
y - (*gen).item());
514 if ((*gen).hasItems())
◆ resultantZ()
modular resultant algorihtm over Z
- Returns
- resultantZ returns the resultant of A and B wrt. x
- Parameters
-
[in] | A | some poly |
[in] | B | some poly |
[in] | x | some polynomial variable |
[in] | prob | if true use probabilistic algorithm |
Definition at line 560 of file cfModResultant.cc.
618 for (
int i= degBx + degAx;
i > 1;
i--)
638 while (
i >= 0 &&
mod(
l,
p ) == 0)
674 if (newQ >
bound || (prob && equalCount == 2))
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
static const int SW_RATIONAL
set to 1 for computations over Q
class to iterate through CanonicalForm's
const CanonicalForm int const CFList const Variable & y
static CanonicalForm uniResultant(const CanonicalForm &F, const CanonicalForm &G)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
const CanonicalForm CFMap & M
static CanonicalForm oneNorm(const CanonicalForm &F)
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL
virtual class for generators
int cf_getBigPrime(int i)
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
const signed long ceil(const ampf< Precision > &x)
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
#define ASSERT(expression, message)
int status int void * buf
TIMING_START(fac_alg_resultant)
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
generate all elements in F_p starting from 0
void prune(Variable &alpha)
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
virtual CFGenerator * clone() const
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define STICKYASSERT(expression, message)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
factory's class for variables
gmp_float log(const gmp_float &a)
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
const CanonicalForm CFMap CFMap & N
const CanonicalForm CFMap CFMap const Variable & x
const Variable & v
< [in] a sqrfree bivariate poly
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
int status int void size_t count
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 mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
CFGenerator * clone() const
generate all elements in F_p(alpha) starting from 0