My Project
Functions
cfSubResGcd.h File Reference

subresultant pseudo remainder sequence GCD over finite fields and Z More...

Go to the source code of this file.

Functions

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 More...
 
CanonicalForm subResGCD_0 (const CanonicalForm &f, const CanonicalForm &g)
 subresultant GCD over Z. More...
 

Detailed Description

subresultant pseudo remainder sequence GCD over finite fields and Z

Definition in file cfSubResGcd.h.

Function Documentation

◆ subResGCD_0()

CanonicalForm subResGCD_0 ( const CanonicalForm f,
const CanonicalForm g 
)

subresultant GCD over Z.

Note
in contrast to subResGCD_p we do not switch to a modular algorithm in case things become too dense

Definition at line 167 of file cfSubResGcd.cc.

168 {
169  CanonicalForm pi, pi1;
170  CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
171  int delta = degree( f ) - degree( g );
172 
173  if ( delta >= 0 )
174  {
175  pi = f; pi1 = g;
176  }
177  else
178  {
179  pi = g; pi1 = f; delta = -delta;
180  }
181  Ci = content( pi ); Ci1 = content( pi1 );
182  pi1 = pi1 / Ci1; pi = pi / Ci;
183  C = gcd( Ci, Ci1 );
184  if ( pi.isUnivariate() && pi1.isUnivariate() )
185  {
186 #ifdef HAVE_FLINT
187  if (isPurePoly(pi) && isPurePoly(pi1) )
188  return gcd_univar_flint0(pi, pi1 ) * C;
189 #else
190 #ifdef HAVE_NTL
191  if (isPurePoly(pi) && isPurePoly(pi1) )
192  return gcd_univar_ntl0(pi, pi1 ) * C;
193 #endif
194 #endif
195 #ifndef HAVE_NTL
196  return gcd_poly_univar0( pi, pi1, true ) * C;
197 #endif
198  }
199  #ifdef HAVE__NTL // gcd_test_one, primitievElement
200  else if ( gcd_test_one( pi1, pi, true, d ) )
201  return C;
202  #else
203  else if (gcd(pi1,pi)==1)
204  return C;
205  #endif
206  Variable v = f.mvar();
207  Hi = power( LC( pi1, v ), delta );
208  if ( (delta+1) % 2 )
209  bi = 1;
210  else
211  bi = -1;
212  while ( degree( pi1, v ) > 0 )
213  {
214  pi2 = psr( pi, pi1, v );
215  pi2 = pi2 / bi;
216  pi = pi1; pi1 = pi2;
217  if ( degree( pi1, v ) > 0 )
218  {
219  delta = degree( pi, v ) - degree( pi1, v );
220  if ( (delta+1) % 2 )
221  bi = LC( pi, v ) * power( Hi, delta );
222  else
223  bi = -LC( pi, v ) * power( Hi, delta );
224  Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
225  }
226  }
227  if ( degree( pi1, v ) == 0 )
228  return C;
229  else
230  return C * pp( pi );
231 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int degree(const CanonicalForm &f)
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm LC(const CanonicalForm &f)
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
g
Definition: cfModGcd.cc:4092
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
static CanonicalForm gcd_poly_univar0(const CanonicalForm &F, const CanonicalForm &G, bool primitive)
Definition: cf_gcd.cc:178
static CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Definition: cf_gcd.cc:94
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:86
bool isUnivariate() const
factory's class for variables
Definition: factory.h:134
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
#define pi
Definition: libparse.cc:1145
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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 at line 12 of file cfSubResGcd.cc.

13 {
14  if (f.inCoeffDomain() || g.inCoeffDomain()) //zero case should be caught by gcd
15  return 1;
16  CanonicalForm pi, pi1;
17  CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
18  bool bpure, ezgcdon= isOn (SW_USE_EZGCD_P);
19  int delta = degree( f ) - degree( g );
20 
21  if ( delta >= 0 )
22  {
23  pi = f; pi1 = g;
24  }
25  else
26  {
27  pi = g; pi1 = f; delta = -delta;
28  }
29  if (pi.isUnivariate())
30  Ci= 1;
31  else
32  {
33  if (!ezgcdon)
35  Ci = content( pi );
36  if (!ezgcdon)
38  pi = pi / Ci;
39  }
40  if (pi1.isUnivariate())
41  Ci1= 1;
42  else
43  {
44  if (!ezgcdon)
46  Ci1 = content( pi1 );
47  if (!ezgcdon)
49  pi1 = pi1 / Ci1;
50  }
51  C = gcd( Ci, Ci1 );
52  #ifdef HAVE_NTL // gcd_test_one, primitiveElement
53  int d= 0;
54  if ( !( pi.isUnivariate() && pi1.isUnivariate() ) )
55  {
56  if ( gcd_test_one( pi1, pi, true, d ) )
57  {
58  C=abs(C);
59  //out_cf("GCD:",C,"\n");
60  return C;
61  }
62  bpure = false;
63  }
64  else
65  #endif
66  {
67  bpure = isPurePoly(pi) && isPurePoly(pi1);
68 #ifdef HAVE_FLINT
69  if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
70  return gcd_univar_flintp(pi,pi1)*C;
71 #else
72 #ifdef HAVE_NTL
73  if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
74  return gcd_univar_ntlp(pi, pi1 ) * C;
75 #endif
76 #endif
77  }
78  Variable v = f.mvar();
79  Hi = power( LC( pi1, v ), delta );
80  int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
81 
82  if (!(pi.isUnivariate() && pi1.isUnivariate()))
83  {
84  if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
85  {
87  C *= gcd (pi, pi1);
89  return C;
90  }
91  }
92 
93  if ( (delta+1) % 2 )
94  bi = 1;
95  else
96  bi = -1;
97  CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
98  while ( degree( pi1, v ) > 0 )
99  {
100  if (!(pi.isUnivariate() && pi1.isUnivariate()))
101  {
102  if (size (pi)/maxNumVars > 500 || size (pi1)/maxNumVars > 500)
103  {
105  C *= gcd (oldPi, oldPi1);
107  return C;
108  }
109  }
110  pi2 = psr( pi, pi1, v );
111  pi2 = pi2 / bi;
112  pi = pi1; pi1 = pi2;
113  maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
114  if (!pi1.isUnivariate() && (size (pi1)/maxNumVars > 500))
115  {
117  C *= gcd (oldPi, oldPi1);
119  return C;
120  }
121  if ( degree( pi1, v ) > 0 )
122  {
123  delta = degree( pi, v ) - degree( pi1, v );
124  powHi= power (Hi, delta-1);
125  if ( (delta+1) % 2 )
126  bi = LC( pi, v ) * powHi*Hi;
127  else
128  bi = -LC( pi, v ) * powHi*Hi;
129  Hi = power( LC( pi1, v ), delta ) / powHi;
130  if (!(pi.isUnivariate() && pi1.isUnivariate()))
131  {
132  if (size (Hi)*size (pi)/(maxNumVars*3) > 1500) //maybe this needs more tuning
133  {
135  C *= gcd (oldPi, oldPi1);
137  return C;
138  }
139  }
140  }
141  }
142  if ( degree( pi1, v ) == 0 )
143  {
144  C=abs(C);
145  //out_cf("GCD:",C,"\n");
146  return C;
147  }
148  if (!pi.isUnivariate())
149  {
150  if (!ezgcdon)
151  On (SW_USE_EZGCD_P);
152  Ci= gcd (LC (oldPi,v), LC (oldPi1,v));
153  pi /= LC (pi,v)/Ci;
154  Ci= content (pi);
155  pi /= Ci;
156  if (!ezgcdon)
158  }
159  if ( bpure )
160  pi /= pi.lc();
161  C=abs(C*pi);
162  //out_cf("GCD:",C,"\n");
163  return C;
164 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int maxNumVars
Definition: cfModGcd.cc:4132
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:36
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:44
#define GaloisFieldDomain
Definition: cf_defs.h:24
static CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
Definition: cf_gcd.cc:81
static int gettype()
Definition: cf_factory.h:28
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)