 |
My Project
UNKNOWN_GIT_VERSION
|
#include "config.h"
#include "cf_assert.h"
#include "timing.h"
#include "cfModResultant.h"
#include "cf_primes.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "cf_algorithm.h"
#include "cf_iter.h"
#include "cf_irred.h"
#include "cf_generator.h"
#include "cf_random.h"
#include "cf_map_ext.h"
#include "facFqBivarUtil.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
Go to the source code of this file.
|
| TIMING_DEFINE_PRINT (fac_resultant_p) static inline void myCompress(const CanonicalForm &F |
|
| for (int i=0;i<=n;i++) degsf[i] |
|
| if (x.level() !=1) |
|
| DELETE_ARRAY (degsg) |
|
static CanonicalForm | oneNorm (const CanonicalForm &F) |
|
static CanonicalForm | uniResultant (const CanonicalForm &F, const CanonicalForm &G) |
|
static void | evalPoint (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint) |
|
static CanonicalForm | newtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x) |
|
CanonicalForm | resultantFp (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob) |
| modular resultant algorihtm over Fp More...
|
|
static CanonicalForm | balanceUni (const CanonicalForm &f, const CanonicalForm &q) |
|
static CanonicalForm | symmetricRemainder (const CanonicalForm &f, const CanonicalForm &q) |
|
CanonicalForm | resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob) |
| modular resultant algorihtm over Z More...
|
|
modular resultant algorithm
- Author
- Martin Lee
Definition in file cfModResultant.cc.
◆ balanceUni()
◆ DELETE_ARRAY()
◆ evalPoint()
◆ for()
for |
( |
int |
i = 0;i<=n;i++ | ) |
|
◆ if()
Definition at line 66 of file cfModResultant.cc.
70 for (
int i= 1;
i <= n;
i++)
101 for (
int i= 1;
i <= n;
i++)
128 for (
int i= 1;
i <= n;
i++)
163 while (min_max_deg == 0 &&
i <
m)
171 for (
int j=
i + 1;
j <=
m;
j++)
182 if (
l !=
k &&
l != xlevel &&
k != 1)
199 if (
i !=
k &&
i != xlevel &&
k != 1)
◆ newtonInterp()
◆ oneNorm()
◆ 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))
◆ symmetricRemainder()
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
fac_resultant_p |
| ) |
const & |
◆ uniResultant()
Definition at line 255 of file cfModResultant.cc.
268 nmod_poly_t FLINTF, FLINTG;
271 mp_limb_t FLINTresult= nmod_poly_resultant (FLINTF, FLINTG);
299 zz_pE::init (NTLMipo);
◆ both_non_zero
◆ both_zero
◆ degsf
◆ degsfx
◆ degsg
◆ degsgx
◆ else
Initial value:{
for (
int i= 1;
i <= n;
i++)
{
{
continue;
}
else
{
{
}
}
}
}
Definition at line 217 of file cfModResultant.cc.
◆ f_zero
◆ Flevel
◆ g_zero
◆ Glevel
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
static const int SW_RATIONAL
set to 1 for computations over Q
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
class to iterate through CanonicalForm's
const CanonicalForm int const CFList const Variable & y
nmod_poly_clear(FLINTmipo)
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
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
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
convertFacCF2nmod_poly_t(FLINTmipo, M)
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)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
#define ASSERT(expression, message)
Rational abs(const Rational &a)
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
const CanonicalForm CFMap CFMap int & both_non_zero
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define STICKYASSERT(expression, message)
static CanonicalForm balanceUni(const CanonicalForm &f, const CanonicalForm &q)
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