My Project
Loading...
Searching...
No Matches
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
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
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:4090
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: variable.h:33
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;
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)
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:4130
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:37
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:45
#define GaloisFieldDomain
Definition: cf_defs.h:18
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 &)