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 **/
91 #if 0
92 int si_factor_reminder=1;
93 #endif
95 {
96  CanonicalForm fc, gc, d1;
97  bool fc_isUnivariate=f.isUnivariate();
98  bool gc_isUnivariate=g.isUnivariate();
99  bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
100  fc = f;
101  gc = g;
102  if ( getCharacteristic() != 0 )
103  {
104  #ifdef HAVE_NTL
105  if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
106  {
107  fc= EZGCD_P (fc, gc);
108  }
109  else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
110  {
111  Variable a;
112  if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
113  fc=modGCDFq (fc, gc, a);
115  fc=modGCDGF (fc, gc);
116  else
117  fc=modGCDFp (fc, gc);
118  }
119  else
120  #endif
121  fc = subResGCD_p( fc, gc );
122  }
123  else if (!fc_and_gc_Univariate)
124  {
125  if ( isOn( SW_USE_EZGCD ) )
126  fc= ezgcd (fc, gc);
127 #ifdef HAVE_NTL
128  else if (isOn(SW_USE_CHINREM_GCD))
129  fc = modGCDZ( fc, gc);
130 #endif
131  else
132  {
133  fc = subResGCD_0( fc, gc );
134  }
135  }
136  else
137  {
138  fc = subResGCD_0( fc, gc );
139  }
140  if ( d1.degree() > 0 )
141  fc *= d1;
142  return fc;
143 }
144 
145 /** static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
146  *
147  * cf_content() - return gcd(g, content(f)).
148  *
149  * content(f) is calculated with respect to f's main variable.
150  *
151  * @sa gcd(), content(), content( CF, Variable ).
152  *
153 **/
154 static CanonicalForm
156 {
157  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
158  {
159  CFIterator i = f;
161  while ( i.hasTerms() && ! result.isOne() )
162  {
163  result = gcd( i.coeff(), result );
164  i++;
165  }
166  return result;
167  }
168  else
169  return abs( f );
170 }
171 
172 /** CanonicalForm content ( const CanonicalForm & f )
173  *
174  * content() - return content(f) with respect to main variable.
175  *
176  * Normalizes result.
177  *
178 **/
181 {
182  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
183  {
184  CFIterator i = f;
185  CanonicalForm result = abs( i.coeff() );
186  i++;
187  while ( i.hasTerms() && ! result.isOne() )
188  {
189  result = gcd( i.coeff(), result );
190  i++;
191  }
192  return result;
193  }
194  else
195  return abs( f );
196 }
197 
198 /** CanonicalForm content ( const CanonicalForm & f, const Variable & x )
199  *
200  * content() - return content(f) with respect to x.
201  *
202  * x should be a polynomial variable.
203  *
204 **/
206 content ( const CanonicalForm & f, const Variable & x )
207 {
208  if (f.inBaseDomain()) return f;
209  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
210  Variable y = f.mvar();
211 
212  if ( y == x )
213  return cf_content( f, 0 );
214  else if ( y < x )
215  return f;
216  else
217  return swapvar( content( swapvar( f, y, x ), y ), y, x );
218 }
219 
220 /** CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
221  *
222  * vcontent() - return content of f with repect to variables >= x.
223  *
224  * The content is recursively calculated over all coefficients in
225  * f having level less than x. x should be a polynomial
226  * variable.
227  *
228 **/
230 vcontent ( const CanonicalForm & f, const Variable & x )
231 {
232  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
233 
234  if ( f.mvar() <= x )
235  return content( f, x );
236  else {
237  CFIterator i;
238  CanonicalForm d = 0;
239  for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
240  d = gcd( d, vcontent( i.coeff(), x ) );
241  return d;
242  }
243 }
244 
245 /** CanonicalForm pp ( const CanonicalForm & f )
246  *
247  * pp() - return primitive part of f.
248  *
249  * Returns zero if f equals zero, otherwise f / content(f).
250  *
251 **/
253 pp ( const CanonicalForm & f )
254 {
255  if ( f.isZero() )
256  return f;
257  else
258  return f / content( f );
259 }
260 
262 gcd ( const CanonicalForm & f, const CanonicalForm & g )
263 {
264  bool b = f.isZero();
265  if ( b || g.isZero() )
266  {
267  if ( b )
268  return abs( g );
269  else
270  return abs( f );
271  }
272  if ( f.inPolyDomain() || g.inPolyDomain() )
273  {
274  if ( f.mvar() != g.mvar() )
275  {
276  if ( f.mvar() > g.mvar() )
277  return cf_content( f, g );
278  else
279  return cf_content( g, f );
280  }
281  if (isOn(SW_USE_QGCD))
282  {
283  Variable m;
284  if (
285  (getCharacteristic() == 0) &&
286  (hasFirstAlgVar(f,m) || hasFirstAlgVar(g,m))
287  )
288  {
289  bool on_rational = isOn(SW_RATIONAL);
290  CanonicalForm r=QGCD(f,g);
291  On(SW_RATIONAL);
292  CanonicalForm cdF = bCommonDen( r );
293  if (!on_rational) Off(SW_RATIONAL);
294  return cdF*r;
295  }
296  }
297 
298  if ( f.inExtension() && getReduce( f.mvar() ) )
299  return CanonicalForm(1);
300  else
301  {
302  if ( fdivides( f, g ) )
303  return abs( f );
304  else if ( fdivides( g, f ) )
305  return abs( g );
306  if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
307  {
308  CanonicalForm d;
309  d = gcd_poly( f, g );
310  return abs( d );
311  }
312  else
313  {
314  CanonicalForm cdF = bCommonDen( f );
315  CanonicalForm cdG = bCommonDen( g );
316  Off( SW_RATIONAL );
317  CanonicalForm l = lcm( cdF, cdG );
318  On( SW_RATIONAL );
319  CanonicalForm F = f * l, G = g * l;
320  Off( SW_RATIONAL );
321  l = gcd_poly( F, G );
322  On( SW_RATIONAL );
323  return abs( l );
324  }
325  }
326  }
327  if ( f.inBaseDomain() && g.inBaseDomain() )
328  return bgcd( f, g );
329  else
330  return 1;
331 }
332 
333 /** CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
334  *
335  * lcm() - return least common multiple of f and g.
336  *
337  * The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).
338  *
339  * Returns zero if one of f or g equals zero.
340  *
341 **/
343 lcm ( const CanonicalForm & f, const CanonicalForm & g )
344 {
345  if ( f.isZero() || g.isZero() )
346  return 0;
347  else
348  return ( f / gcd( f, g ) ) * g;
349 }
350 
int level() const
Definition: factory.h:132
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:438
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
GCD over Q(a)
Conversion to and from NTL.
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
const poly a
Definition: syzextra.cc:212
CanonicalForm pp(const CanonicalForm &f)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
void Off(int sw)
switches
functions to print debug output
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:42
factory&#39;s class for variables
Definition: factory.h:115
subresultant pseudo remainder sequence GCD over finite fields and Z
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:34
generate random evaluation points
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:343
factory&#39;s main class
Definition: canonicalform.h:75
assertions for Factory
g
Definition: cfModGcd.cc:4031
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
bool isPurePoly(const CanonicalForm &)
Definition: cf_factor.cc:229
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c ) ...
Definition: cf_gcd.cc:46
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
bool inExtension() const
static TreeM * G
Definition: janet.cc:38
Extended Zassenhaus GCD over finite fields and Z.
int getCharacteristic()
Definition: cf_char.cc:51
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
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
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const ring r
Definition: syzextra.cc:208
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:94
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g ) ...
Definition: cf_gcd.cc:155
int m
Definition: cfEzgcd.cc:119
bool isOn(int sw)
switches
void On(int sw)
switches
Iterators for CanonicalForm&#39;s.
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
factory switches.
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: cf_defs.h:38
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
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
bool isUnivariate() const
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
bool inPolyDomain() const
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:802
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
access to prime tables
static int gettype()
Definition: cf_factory.h:27
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition: cfGcdAlgExt.cc:720
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:32
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
modular and sparse modular GCD algorithms over finite fields and Z.
bool inBaseDomain() const
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm subResGCD_0(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over Z.
Definition: cfSubResGcd.cc:165
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:262
const poly b
Definition: syzextra.cc:213
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
Header for factory&#39;s main class CanonicalForm.