Loading...
Searching...
No Matches
cfSubResGcd.cc
Go to the documentation of this file.
#include "config.h"
#include "cf_defs.h"
#include "cf_algorithm.h"
#include "cfEzgcd.h"
#include "cfGcdUtil.h"
#include "templates/ftmpl_functions.h"
#include "cf_factory.h"
#include "cfUnivarGcd.h"
CanonicalForm
subResGCD_p( const CanonicalForm & f, const CanonicalForm & g )
{
if (f.inCoeffDomain() || g.inCoeffDomain()) //zero case should be caught by gcd
return 1;
CanonicalForm pi, pi1;
CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
bool bpure, ezgcdon= isOn (SW_USE_EZGCD_P);
int delta = degree( f ) - degree( g );
if ( delta >= 0 )
{
pi = f; pi1 = g;
}
else
{
pi = g; pi1 = f; delta = -delta;
}
if (pi.isUnivariate())
Ci= 1;
else
{
if (!ezgcdon)
On (SW_USE_EZGCD_P);
Ci = content( pi );
if (!ezgcdon)
Off (SW_USE_EZGCD_P);
pi = pi / Ci;
}
if (pi1.isUnivariate())
Ci1= 1;
else
{
if (!ezgcdon)
On (SW_USE_EZGCD_P);
Ci1 = content( pi1 );
if (!ezgcdon)
Off (SW_USE_EZGCD_P);
pi1 = pi1 / Ci1;
}
C = gcd( Ci, Ci1 );
#ifdef HAVE_NTL // gcd_test_one, primitiveElement
int d= 0;
if ( !( pi.isUnivariate() && pi1.isUnivariate() ) )
{
if ( gcd_test_one( pi1, pi, true, d ) )
{
C=abs(C);
//out_cf("GCD:",C,"\n");
return C;
}
bpure = false;
}
else
#endif
{
bpure = isPurePoly(pi) && isPurePoly(pi1);
#ifdef HAVE_FLINT
if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
return gcd_univar_flintp(pi,pi1)*C;
#else
#ifdef HAVE_NTL
if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
return gcd_univar_ntlp(pi, pi1 ) * C;
#endif
#endif
}
Variable v = f.mvar();
Hi = power( LC( pi1, v ), delta );
int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
if (!(pi.isUnivariate() && pi1.isUnivariate()))
{
if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (pi, pi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
}
if ( (delta+1) % 2 )
bi = 1;
else
bi = -1;
CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
while ( degree( pi1, v ) > 0 )
{
if (!(pi.isUnivariate() && pi1.isUnivariate()))
{
if (size (pi)/maxNumVars > 500 || size (pi1)/maxNumVars > 500)
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (oldPi, oldPi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
}
pi2 = psr( pi, pi1, v );
pi2 = pi2 / bi;
pi = pi1; pi1 = pi2;
maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
if (!pi1.isUnivariate() && (size (pi1)/maxNumVars > 500))
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (oldPi, oldPi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
if ( degree( pi1, v ) > 0 )
{
delta = degree( pi, v ) - degree( pi1, v );
powHi= power (Hi, delta-1);
if ( (delta+1) % 2 )
bi = LC( pi, v ) * powHi*Hi;
else
bi = -LC( pi, v ) * powHi*Hi;
Hi = power( LC( pi1, v ), delta ) / powHi;
if (!(pi.isUnivariate() && pi1.isUnivariate()))
{
if (size (Hi)*size (pi)/(maxNumVars*3) > 1500) //maybe this needs more tuning
{
On (SW_USE_FF_MOD_GCD);
C *= gcd (oldPi, oldPi1);
Off (SW_USE_FF_MOD_GCD);
return C;
}
}
}
}
if ( degree( pi1, v ) == 0 )
{
C=abs(C);
//out_cf("GCD:",C,"\n");
return C;
}
if (!pi.isUnivariate())
{
if (!ezgcdon)
On (SW_USE_EZGCD_P);
Ci= gcd (LC (oldPi,v), LC (oldPi1,v));
pi /= LC (pi,v)/Ci;
Ci= content (pi);
pi /= Ci;
if (!ezgcdon)
Off (SW_USE_EZGCD_P);
}
if ( bpure )
pi /= pi.lc();
C=abs(C*pi);
//out_cf("GCD:",C,"\n");
return C;
}
CanonicalForm
subResGCD_0( const CanonicalForm & f, const CanonicalForm & g )
{
CanonicalForm pi, pi1;
CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
int delta = degree( f ) - degree( g );
if ( delta >= 0 )
{
pi = f; pi1 = g;
}
else
{
pi = g; pi1 = f; delta = -delta;
}
Ci = content( pi ); Ci1 = content( pi1 );
pi1 = pi1 / Ci1; pi = pi / Ci;
C = gcd( Ci, Ci1 );
if ( pi.isUnivariate() && pi1.isUnivariate() )
{
#ifdef HAVE_FLINT
if (isPurePoly(pi) && isPurePoly(pi1) )
return gcd_univar_flint0(pi, pi1 ) * C;
#else
#ifdef HAVE_NTL
if (isPurePoly(pi) && isPurePoly(pi1) )
return gcd_univar_ntl0(pi, pi1 ) * C;
#endif
#endif
#ifndef HAVE_NTL
return gcd_poly_univar0( pi, pi1, true ) * C;
#endif
}
#ifdef HAVE__NTL // gcd_test_one, primitievElement
else if ( gcd_test_one( pi1, pi, true, d ) )
return C;
#else
else if (gcd(pi1,pi)==1)
return C;
#endif
Variable v = f.mvar();
Hi = power( LC( pi1, v ), delta );
if ( (delta+1) % 2 )
bi = 1;
else
bi = -1;
while ( degree( pi1, v ) > 0 )
{
pi2 = psr( pi, pi1, v );
pi2 = pi2 / bi;
pi = pi1; pi1 = pi2;
if ( degree( pi1, v ) > 0 )
{
delta = degree( pi, v ) - degree( pi1, v );
if ( (delta+1) % 2 )
bi = LC( pi, v ) * power( Hi, delta );
else
bi = -LC( pi, v ) * power( Hi, delta );
Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
}
}
if ( degree( pi1, v ) == 0 )
return C;
else
return C * pp( pi );
}
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
cfEzgcd.h
Extended Zassenhaus GCD over finite fields and Z.
gcd_test_one
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition cfGcdUtil.cc:25
cfGcdUtil.h
coprimality check and change of representation mod n
g
g
Definition cfModGcd.cc:4098
maxNumVars
int maxNumVars
Definition cfModGcd.cc:4138
subResGCD_p
CanonicalForm subResGCD_p(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over finite fields. In case things become too dense we switch to a modular algorithm
Definition cfSubResGcd.cc:12
subResGCD_0
CanonicalForm subResGCD_0(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over Z.
Definition cfSubResGcd.cc:167
cfUnivarGcd.h
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
cf_algorithm.h
declarations of higher level algorithms.
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
psr
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
cf_defs.h
factory switches.
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition cf_defs.h:37
SW_USE_FF_MOD_GCD
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition cf_defs.h:45
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
cf_factory.h
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
gcd_univar_flintp
static CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
Definition cf_gcd.cc:81
gcd_poly_univar0
static CanonicalForm gcd_poly_univar0(const CanonicalForm &F, const CanonicalForm &G, bool primitive)
Definition cf_gcd.cc:178
gcd_univar_flint0
static CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Definition cf_gcd.cc:94
f
FILE * f
Definition checklibs.c:9
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
Variable
factory's class for variables
Definition factory.h:127
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
ftmpl_functions.h
some useful template functions.
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
pi
#define pi
Definition libparse.cc:1145
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836