My Project  UNKNOWN_GIT_VERSION
cf_gcd.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file cf_gcd.cc
5  *
6  * gcd/content/lcm of polynomials
7  *
8  * To compute the GCD different variants are chosen automatically
9 **/
10 
11 #include "config.h"
12 
13 
14 #include "timing.h"
15 #include "cf_assert.h"
16 #include "debug.h"
17 
18 #include "cf_defs.h"
19 #include "canonicalform.h"
20 #include "cf_iter.h"
21 #include "cf_reval.h"
22 #include "cf_primes.h"
23 #include "cf_algorithm.h"
24 #include "cfEzgcd.h"
25 #include "cfGcdAlgExt.h"
26 #include "cfSubResGcd.h"
27 #include "cfModGcd.h"
28 
29 #ifdef HAVE_NTL
30 #include <NTL/ZZX.h>
31 #include "NTLconvert.h"
32 bool isPurePoly(const CanonicalForm & );
33 #endif
34 
35 void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
36 
37 /** static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
38  *
39  * icontent() - return gcd of c and all coefficients of f which
40  * are in a coefficient domain.
41  *
42  * @sa icontent().
43  *
44 **/
45 static CanonicalForm
46 icontent ( const CanonicalForm & f, const CanonicalForm & c )
47 {
48  if ( f.inBaseDomain() )
49  {
50  if (c.isZero()) return abs(f);
51  return bgcd( f, c );
52  }
53  //else if ( f.inCoeffDomain() )
54  // return gcd(f,c);
55  else
56  {
57  CanonicalForm g = c;
58  for ( CFIterator i = f; i.hasTerms() && ! g.isOne(); i++ )
59  g = icontent( i.coeff(), g );
60  return g;
61  }
62 }
63 
64 /** CanonicalForm icontent ( const CanonicalForm & f )
65  *
66  * icontent() - return gcd over all coefficients of f which are
67  * in a coefficient domain.
68  *
69 **/
72 {
73  return icontent( f, 0 );
74 }
75 
76 /** CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
77  *
78  * gcd_poly() - calculate polynomial gcd.
79  *
80  * This is the dispatcher for polynomial gcd calculation.
81  * Different gcd variants get called depending the input, characteristic, and
82  * on switches (cf_defs.h)
83  *
84  * With the current settings from Singular (i.e. SW_USE_EZGCD= on,
85  * SW_USE_EZGCD_P= on, SW_USE_CHINREM_GCD= on, the EZ GCD variants are the
86  * default algorithms for multivariate polynomial GCD computations)
87  *
88  * @sa gcd(), cf_defs.h
89  *
90 **/
92 {
93  CanonicalForm fc, gc;
94  bool fc_isUnivariate=f.isUnivariate();
95  bool gc_isUnivariate=g.isUnivariate();
96  bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
97  fc = f;
98  gc = g;
99  if ( getCharacteristic() != 0 )
100  {
101  #ifdef HAVE_NTL
102  if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
103  {
104  fc= EZGCD_P (fc, gc);
105  }
106  else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
107  {
108  Variable a;
109  if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
110  fc=modGCDFq (fc, gc, a);
112  fc=modGCDGF (fc, gc);
113  else
114  fc=modGCDFp (fc, gc);
115  }
116  else
117  #endif
118  fc = subResGCD_p( fc, gc );
119  }
120  else if (!fc_and_gc_Univariate)
121  {
122  if ( isOn( SW_USE_EZGCD ) )
123  fc= ezgcd (fc, gc);
124 #ifdef HAVE_NTL
125  else if (isOn(SW_USE_CHINREM_GCD))
126  fc = modGCDZ( fc, gc);
127 #endif
128  else
129  {
130  fc = subResGCD_0( fc, gc );
131  }
132  }
133  else
134  {
135  fc = subResGCD_0( fc, gc );
136  }
137  return fc;
138 }
139 
140 /** static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
141  *
142  * cf_content() - return gcd(g, content(f)).
143  *
144  * content(f) is calculated with respect to f's main variable.
145  *
146  * @sa gcd(), content(), content( CF, Variable ).
147  *
148 **/
149 static CanonicalForm
151 {
152  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
153  {
154  CFIterator i = f;
156  while ( i.hasTerms() && ! result.isOne() )
157  {
158  result = gcd( i.coeff(), result );
159  i++;
160  }
161  return result;
162  }
163  else
164  return abs( f );
165 }
166 
167 /** CanonicalForm content ( const CanonicalForm & f )
168  *
169  * content() - return content(f) with respect to main variable.
170  *
171  * Normalizes result.
172  *
173 **/
176 {
177  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
178  {
179  CFIterator i = f;
180  CanonicalForm result = abs( i.coeff() );
181  i++;
182  while ( i.hasTerms() && ! result.isOne() )
183  {
184  result = gcd( i.coeff(), result );
185  i++;
186  }
187  return result;
188  }
189  else
190  return abs( f );
191 }
192 
193 /** CanonicalForm content ( const CanonicalForm & f, const Variable & x )
194  *
195  * content() - return content(f) with respect to x.
196  *
197  * x should be a polynomial variable.
198  *
199 **/
201 content ( const CanonicalForm & f, const Variable & x )
202 {
203  if (f.inBaseDomain()) return f;
204  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
205  Variable y = f.mvar();
206 
207  if ( y == x )
208  return cf_content( f, 0 );
209  else if ( y < x )
210  return f;
211  else
212  return swapvar( content( swapvar( f, y, x ), y ), y, x );
213 }
214 
215 /** CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
216  *
217  * vcontent() - return content of f with repect to variables >= x.
218  *
219  * The content is recursively calculated over all coefficients in
220  * f having level less than x. x should be a polynomial
221  * variable.
222  *
223 **/
225 vcontent ( const CanonicalForm & f, const Variable & x )
226 {
227  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
228 
229  if ( f.mvar() <= x )
230  return content( f, x );
231  else {
232  CFIterator i;
233  CanonicalForm d = 0;
234  for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
235  d = gcd( d, vcontent( i.coeff(), x ) );
236  return d;
237  }
238 }
239 
240 /** CanonicalForm pp ( const CanonicalForm & f )
241  *
242  * pp() - return primitive part of f.
243  *
244  * Returns zero if f equals zero, otherwise f / content(f).
245  *
246 **/
248 pp ( const CanonicalForm & f )
249 {
250  if ( f.isZero() )
251  return f;
252  else
253  return f / content( f );
254 }
255 
257 gcd ( const CanonicalForm & f, const CanonicalForm & g )
258 {
259  bool b = f.isZero();
260  if ( b || g.isZero() )
261  {
262  if ( b )
263  return abs( g );
264  else
265  return abs( f );
266  }
267  if ( f.inPolyDomain() || g.inPolyDomain() )
268  {
269  if ( f.mvar() != g.mvar() )
270  {
271  if ( f.mvar() > g.mvar() )
272  return cf_content( f, g );
273  else
274  return cf_content( g, f );
275  }
276  if (isOn(SW_USE_QGCD))
277  {
278  Variable m;
279  if (
280  (getCharacteristic() == 0) &&
282  )
283  {
284  bool on_rational = isOn(SW_RATIONAL);
285  CanonicalForm r=QGCD(f,g);
286  On(SW_RATIONAL);
287  CanonicalForm cdF = bCommonDen( r );
288  if (!on_rational) Off(SW_RATIONAL);
289  return cdF*r;
290  }
291  }
292 
293  if ( f.inExtension() && getReduce( f.mvar() ) )
294  return CanonicalForm(1);
295  else
296  {
297  if ( fdivides( f, g ) )
298  return abs( f );
299  else if ( fdivides( g, f ) )
300  return abs( g );
301  if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
302  {
303  CanonicalForm d;
304  d = gcd_poly( f, g );
305  return abs( d );
306  }
307  else
308  {
309  CanonicalForm cdF = bCommonDen( f );
310  CanonicalForm cdG = bCommonDen( g );
311  Off( SW_RATIONAL );
312  CanonicalForm l = lcm( cdF, cdG );
313  On( SW_RATIONAL );
314  CanonicalForm F = f * l, G = g * l;
315  Off( SW_RATIONAL );
316  l = gcd_poly( F, G );
317  On( SW_RATIONAL );
318  return abs( l );
319  }
320  }
321  }
322  if ( f.inBaseDomain() && g.inBaseDomain() )
323  return bgcd( f, g );
324  else
325  return 1;
326 }
327 
328 /** CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
329  *
330  * lcm() - return least common multiple of f and g.
331  *
332  * The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).
333  *
334  * Returns zero if one of f or g equals zero.
335  *
336 **/
338 lcm ( const CanonicalForm & f, const CanonicalForm & g )
339 {
340  if ( f.isZero() || g.isZero() )
341  return 0;
342  else
343  return ( f / gcd( f, g ) ) * g;
344 }
345 
timing.h
cfEzgcd.h
Extended Zassenhaus GCD over finite fields and Z.
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
lcm
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:338
f
FILE * f
Definition: checklibs.c:9
canonicalform.h
Header for factory's main class CanonicalForm.
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
subResGCD_0
CanonicalForm subResGCD_0(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over Z.
Definition: cfSubResGcd.cc:165
cf_reval.h
generate random evaluation points
cfSubResGcd.h
subresultant pseudo remainder sequence GCD over finite fields and Z
isPurePoly
bool isPurePoly(const CanonicalForm &)
Definition: cf_factor.cc:229
icontent
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition: cf_gcd.cc:46
vcontent
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:225
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:481
g
g
Definition: cfModGcd.cc:4031
pp
CanonicalForm pp(const CanonicalForm &f)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
cf_primes.h
access to prime tables
QGCD
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition: cfGcdAlgExt.cc:715
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
gcd_poly
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:91
CanonicalForm
factory's main class
Definition: canonicalform.h:83
SW_USE_EZGCD
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:32
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
i
int i
Definition: cfEzgcd.cc:125
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
abs
Rational abs(const Rational &a)
Definition: GMPrat.cc:439
cf_defs.h
factory switches.
cf_iter.h
Iterators for CanonicalForm's.
modGCDFq
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition: cfModGcd.cc:467
NTLconvert.h
Conversion to and from NTL.
cf_algorithm.h
declarations of higher level algorithms.
EZGCD_P
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
Definition: cfEzgcd.cc:862
SW_USE_CHINREM_GCD
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: cf_defs.h:38
Variable::level
int level() const
Definition: factory.h:134
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:42
content
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
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
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
Variable
factory's class for variables
Definition: factory.h:118
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:34
gcd
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:257
cf_content
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:150
m
int m
Definition: cfEzgcd.cc:121
cfModGcd.h
modular and sparse modular GCD algorithms over finite fields and Z.
l
int l
Definition: cfEzgcd.cc:93
bgcd
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
Definition: canonicalform.cc:1589
cf_assert.h
assertions for Factory
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
cfGcdAlgExt.h
GCD over Q(a)
SW_USE_QGCD
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
modGCDZ
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
getReduce
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
G
static TreeM * G
Definition: janet.cc:32
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
debug.h
functions to print debug output
modGCDGF
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
Definition: cfModGcd.cc:860