 |
My Project
UNKNOWN_GIT_VERSION
|
#include "config.h"
#include <stdio.h>
#include <iostream>
#include "cf_assert.h"
#include "timing.h"
#include "templates/ftmpl_functions.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "cfGcdAlgExt.h"
#include "cfUnivarGcd.h"
#include "cf_map.h"
#include "cf_generator.h"
#include "facMul.h"
#include "cfNTLzzpEXGCD.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
Go to the source code of this file.
|
| TIMING_DEFINE_PRINT (alg_content_p) TIMING_DEFINE_PRINT(alg_content) TIMING_DEFINE_PRINT(alg_compress) TIMING_DEFINE_PRINT(alg_termination) TIMING_DEFINE_PRINT(alg_termination_p) TIMING_DEFINE_PRINT(alg_reconstruction) TIMING_DEFINE_PRINT(alg_newton_p) TIMING_DEFINE_PRINT(alg_recursion_p) TIMING_DEFINE_PRINT(alg_gcd_p) TIMING_DEFINE_PRINT(alg_euclid_p) static int myCompress(const CanonicalForm &F |
| compressing two polynomials F and G, M is used for compressing, N to reverse the compression More...
|
|
| for (int i=0;i<=n;i++) degsf[i] |
|
| if (topLevel) |
|
| DELETE_ARRAY (degsg) |
|
void | tryInvert (const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail) |
|
static CanonicalForm | trycontent (const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail) |
|
static CanonicalForm | tryvcontent (const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail) |
|
static CanonicalForm | trycf_content (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail) |
|
static CanonicalForm | tryNewtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail) |
|
void | tryBrownGCD (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel) |
| modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true. More...
|
|
static CanonicalForm | myicontent (const CanonicalForm &f, const CanonicalForm &c) |
|
static CanonicalForm | myicontent (const CanonicalForm &f) |
|
CanonicalForm | QGCD (const CanonicalForm &F, const CanonicalForm &G) |
| gcd over Q(a) More...
|
|
int * | leadDeg (const CanonicalForm &f, int *degs) |
|
bool | isLess (int *a, int *b, int lower, int upper) |
|
bool | isEqual (int *a, int *b, int lower, int upper) |
|
CanonicalForm | firstLC (const CanonicalForm &f) |
|
◆ DELETE_ARRAY()
◆ firstLC()
◆ for()
for |
( |
int |
i = 0;i<=n;i++ | ) |
|
◆ if()
Definition at line 75 of file cfGcdAlgExt.cc.
77 for (
int i= 1;
i <= n;
i++)
106 for (
int i= 1;
i <= n;
i++)
141 while (min_max_deg == 0)
150 for (
int j=
i + 1;
j <=
m;
j++)
◆ isEqual()
bool isEqual |
( |
int * |
a, |
|
|
int * |
b, |
|
|
int |
lower, |
|
|
int |
upper |
|
) |
| |
◆ isLess()
bool isLess |
( |
int * |
a, |
|
|
int * |
b, |
|
|
int |
lower, |
|
|
int |
upper |
|
) |
| |
◆ leadDeg()
◆ myicontent() [1/2]
◆ myicontent() [2/2]
Definition at line 656 of file cfGcdAlgExt.cc.
659 if (
f.isOne() || c.
isOne())
672 fmpz_poly_t FLINTf, FLINTc;
675 fmpz_poly_gcd (FLINTc, FLINTc, FLINTf);
677 if (
f.inCoeffDomain())
681 fmpz_poly_clear (FLINTc);
682 fmpz_poly_clear (FLINTf);
687 NTLc= GCD (NTLc, NTLf);
688 if (
f.inCoeffDomain())
◆ QGCD()
gcd over Q(a)
Definition at line 715 of file cfGcdAlgExt.cc.
779 int mv =
f.level();
i =
g.level();
783 bound =
new int[mv+1];
784 other =
new int[mv+1];
785 for(
int i=1;
i<=mv;
i++)
789 for(
int i=1;
i<=mv;
i++)
830 for(
int i=1;
i<=mv;
i++)
848 "time for rational reconstruction in alg gcd: ")
858 if (
equal && tmp.isUnivariate() &&
f.isUnivariate() &&
g.isUnivariate()
859 &&
f.level() == tmp.level() && tmp.level() ==
g.level())
872 "time for successful termination test in alg gcd: ")
888 "time for successful termination test in alg gcd: ")
894 "time
for unsuccessful termination
test in alg
gcd: ")
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
alg_content_p |
| ) |
const & |
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
◆ tryBrownGCD()
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true.
Definition at line 372 of file cfGcdAlgExt.cc.
461 zz_pE::init (NTLMipo);
502 tryEuclid(
cf,
cg,
M,c,fail);
507 f.tryDiv (
cf,
M, fail);
511 g.tryDiv (
cg,
M, fail);
515 if(
f.inCoeffDomain())
523 if(
g.inCoeffDomain())
531 int *L =
new int[mv+1];
532 int *
N =
new int[mv+1];
533 for(
int i=2;
i<=mv;
i++)
556 int *dg_im = new
int[mv+1];
574 "time for recursive calls in alg gcd mod p: ")
578 if(g_image.inCoeffDomain())
586 for(
int i=2;
i<=mv;
i++)
588 dg_im =
leadDeg(g_image, dg_im);
596 g_image *= gamma_image;
601 "time for Newton interpolation in alg gcd mod p: ")
608 if((
firstLC(gnew) == gamma) || (gnew == gm))
631 "time for successful termination test in alg gcd mod p: ")
◆ trycf_content()
Definition at line 1067 of file cfGcdAlgExt.cc.
1069 if (
f.inPolyDomain() || (
f.inExtension() && !
getReduce(
f.mvar() ) ) )
1073 while (
i.hasTerms() && ! tmp.
isOne() && ! fail )
◆ trycontent()
◆ tryInvert()
◆ tryNewtonInterp()
◆ tryvcontent()
Definition at line 1048 of file cfGcdAlgExt.cc.
1050 ASSERT(
x.
level() > 0,
"cannot calculate vcontent with respect to algebraic variable" );
1051 if (
f.mvar() <=
x )
1055 for (
i =
f;
i.hasTerms() && ! d.
isOne() && ! fail;
i++ )
◆ both_non_zero
◆ both_zero
◆ degsf
◆ degsg
◆ else
Initial value:{
for (
int i= 1;
i <= n;
i++)
{
{
continue;
}
else
{
{
}
}
}
}
Definition at line 195 of file cfGcdAlgExt.cc.
◆ f_zero
◆ Flevel
◆ g_zero
◆ Glevel
◆ return
◆ topLevel
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
static const int SW_RATIONAL
set to 1 for computations over Q
const CanonicalForm CFMap CFMap & N
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
bool isZero(const CFArray &A)
checks if entries of A are zero
CanonicalForm firstLC(const CanonicalForm &f)
class to iterate through CanonicalForm's
const CanonicalForm int const CFList const Variable & y
bool isEqual(int *a, int *b, int lower, int upper)
static CanonicalForm trycontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
int cf_getBigPrime(int i)
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
int * leadDeg(const CanonicalForm &f, int *degs)
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
#define ASSERT(expression, message)
Rational abs(const Rational &a)
TIMING_START(fac_alg_resultant)
generate all elements in F_p starting from 0
for(int i=0;i<=n;i++) degsf[i]
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
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,...
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
const CanonicalForm CFMap CFMap int & both_non_zero
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
static CanonicalForm trycf_content(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void setReduce(const Variable &alpha, bool reduce)
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
const CanonicalForm CFMap CFMap bool topLevel
const CanonicalForm CFMap & M
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
const Variable & v
< [in] a sqrfree bivariate poly
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
static number Farey(number p, number n, const coeffs)
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
bool getReduce(const Variable &alpha)
void tryNTLGCD(zz_pEX &x, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the GCD x of a and b, fail is set to true if a zero divisor is encountered
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
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
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
bool isLess(int *a, int *b, int lower, int upper)