Functions | Variables
cfModResultant.cc File Reference

modular resultant algorithm More...

#include "config.h"
#include "cf_assert.h"
#include "timing.h"
#include "cfModResultant.h"
#include "cf_primes.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "cf_algorithm.h"
#include "cf_iter.h"
#include "cf_irred.h"
#include "cf_generator.h"
#include "cf_random.h"
#include "cf_map_ext.h"
#include "facFqBivarUtil.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_resultant_p) static inline void myCompress(const CanonicalForm &F
 
 for (int i=0;i<=n;i++) degsf[i]
 
 if (x.level() !=1)
 
static CanonicalForm oneNorm (const CanonicalForm &F)
 
static CanonicalForm uniResultant (const CanonicalForm &F, const CanonicalForm &G)
 
static void evalPoint (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
 
static CanonicalForm newtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
 
CanonicalForm resultantFp (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
 modular resultant algorihtm over Fp More...
 
static CanonicalForm balanceUni (const CanonicalForm &f, const CanonicalForm &q)
 
static CanonicalForm symmetricRemainder (const CanonicalForm &f, const CanonicalForm &q)
 
CanonicalForm resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
 modular resultant algorihtm over Z More...
 

Variables

const CanonicalFormG
 
const CanonicalForm CFMapM
 
const CanonicalForm CFMap CFMapN
 
const CanonicalForm CFMap CFMap const Variablex
 
int * degsf = new int [n + 1]
 
int * degsg = new int [n + 1]
 
int both_non_zero = 0
 
int f_zero = 0
 
int g_zero = 0
 
int both_zero = 0
 
int degsfx
 
int degsgx
 
 else
 

Detailed Description

modular resultant algorithm

Author
Martin Lee

Definition in file cfModResultant.cc.

Function Documentation

§ balanceUni()

static CanonicalForm balanceUni ( const CanonicalForm f,
const CanonicalForm q 
)
inlinestatic

Definition at line 525 of file cfModResultant.cc.

526 {
527  Variable x = f.mvar();
528  CanonicalForm result = 0, qh = q / 2;
529  CanonicalForm c;
530  CFIterator i;
531  for ( i = f; i.hasTerms(); i++ ) {
532  c = mod( i.coeff(), q );
533  if ( c > qh )
534  result += power( x, i.exp() ) * (c - q);
535  else
536  result += power( x, i.exp() ) * c;
537  }
538  return result;
539 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
const CanonicalForm CFMap CFMap const Variable & x
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:75
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

§ evalPoint()

static void evalPoint ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm FEval,
CanonicalForm GEval,
CFGenerator evalPoint 
)
inlinestatic

Definition at line 309 of file cfModResultant.cc.

312 {
313  int degF, degG;
314  Variable x= Variable (1);
315  degF= degree (F, x);
316  degG= degree (G, x);
317  do
318  {
319  if (!evalPoint.hasItems())
320  break;
321  FEval= F (evalPoint.item(), 2);
322  GEval= G (evalPoint.item(), 2);
323  if (degree (FEval, 1) < degF || degree (GEval, 1) < degG)
324  {
325  evalPoint.next();
326  continue;
327  }
328  else
329  return;
330  }
331  while (evalPoint.hasItems());
332 }
const CanonicalForm CFMap CFMap const Variable & x
factory&#39;s class for variables
Definition: factory.h:115
virtual bool hasItems() const
Definition: cf_generator.h:26
const CanonicalForm & G
int degree(const CanonicalForm &f)
virtual void next()
Definition: cf_generator.h:29
virtual CanonicalForm item() const
Definition: cf_generator.h:28

§ for()

for ( int  i = 0;i<=n;i++)

Definition at line 66 of file cfEzgcd.cc.

67  {
68  if (degsf[i] != 0 && degsg[i] != 0)
69  {
70  both_non_zero++;
71  continue;
72  }
73  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
74  {
75  f_zero++;
76  continue;
77  }
78  if (degsg[i] == 0 && degsf[i] && i <= F.level())
79  {
80  g_zero++;
81  continue;
82  }
83  }
int * degsg
Definition: cfEzgcd.cc:54
int i
Definition: cfEzgcd.cc:123
const CanonicalForm & G
Definition: cfEzgcd.cc:49
int f_zero
Definition: cfEzgcd.cc:63
int g_zero
Definition: cfEzgcd.cc:64
const CanonicalForm CFMap CFMap int & both_non_zero
Definition: cfEzgcd.cc:51
int level() const
level() returns the level of CO.
int * degsf
Definition: cfEzgcd.cc:53

§ if()

if ( x.level() !  = 1)

Definition at line 64 of file cfModResultant.cc.

65  {
66  int xlevel= x.level();
67 
68  for (int i= 1; i <= n; i++)
69  {
70  if (degsf[i] != 0 && degsg[i] != 0)
71  {
72  both_non_zero++;
73  continue;
74  }
75  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
76  {
77  f_zero++;
78  continue;
79  }
80  if (degsg[i] == 0 && degsf[i] && i <= F.level())
81  {
82  g_zero++;
83  continue;
84  }
85  }
86 
87  M.newpair (Variable (xlevel), Variable (1));
88  N.newpair (Variable (1), Variable (xlevel));
89  degsfx= degsf [xlevel];
90  degsgx= degsg [xlevel];
91  degsf [xlevel]= 0;
92  degsg [xlevel]= 0;
93  if ((getNumVars (F) == 2 && getNumVars (G) == 1) ||
94  (getNumVars (G) == 2 && getNumVars (F) == 1) ||
95  (getNumVars (F) == 2 && getNumVars (F) == getNumVars (G)
96  && getVars (F) == getVars (G)))
97  {
98  int pos= 2;
99  for (int i= 1; i <= n; i++)
100  {
101  if (i != xlevel)
102  {
103  if (i != pos && (degsf[i] != 0 || degsg [i] != 0))
104  {
105  M.newpair (Variable (i), Variable (pos));
106  N.newpair (Variable (pos), Variable (i));
107  pos++;
108  }
109  }
110  }
111  delete [] degsf;
112  delete [] degsg;
113  return;
114  }
115 
116  if (both_non_zero == 0)
117  {
118  delete [] degsf;
119  delete [] degsg;
120  return;
121  }
122 
123  // map Variables which do not occur in both polynomials to higher levels
124  int k= 1;
125  int l= 1;
126  for (int i= 1; i <= n; i++)
127  {
128  if (i == xlevel)
129  continue;
130  if (degsf[i] != 0 && degsg[i] == 0 && i <= F.level())
131  {
132  if (k + both_non_zero != i)
133  {
134  M.newpair (Variable (i), Variable (k + both_non_zero));
135  N.newpair (Variable (k + both_non_zero), Variable (i));
136  }
137  k++;
138  }
139  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
140  {
141  if (l + g_zero + both_non_zero != i)
142  {
143  M.newpair (Variable (i), Variable (l + g_zero + both_non_zero));
144  N.newpair (Variable (l + g_zero + both_non_zero), Variable (i));
145  }
146  l++;
147  }
148  }
149 
150  int m= n;
151  int min_max_deg;
152  k= both_non_zero;
153  l= 0;
154  int i= 1;
155  while (k > 0)
156  {
157  if (degsf [i] != 0 && degsg [i] != 0)
158  min_max_deg= degsgx*degsf[i] + degsfx*degsg[i];
159  else
160  min_max_deg= 0;
161  while (min_max_deg == 0 && i < m + 1)
162  {
163  i++;
164  if (degsf [i] != 0 && degsg [i] != 0)
165  min_max_deg= degsgx*degsf[i] + degsfx*degsg[i];
166  else
167  min_max_deg= 0;
168  }
169  for (int j= i + 1; j <= m; j++)
170  {
171  if (degsgx*degsf[j] + degsfx*degsg[j] <= min_max_deg &&
172  degsf[j] != 0 && degsg [j] != 0)
173  {
174  min_max_deg= degsgx*degsf[j] + degsfx*degsg[j];
175  l= j;
176  }
177  }
178  if (l != 0)
179  {
180  if (l != k && l != xlevel && k != 1)
181  {
182  M.newpair (Variable (l), Variable(k));
183  N.newpair (Variable (k), Variable(l));
184  degsf[l]= 0;
185  degsg[l]= 0;
186  l= 0;
187  }
188  else if (l < m + 1)
189  {
190  degsf[l]= 0;
191  degsg[l]= 0;
192  l= 0;
193  }
194  }
195  else if (l == 0)
196  {
197  if (i != k && i != xlevel && k != 1)
198  {
199  M.newpair (Variable (i), Variable (k));
200  N.newpair (Variable (k), Variable (i));
201  degsf[i]= 0;
202  degsg[i]= 0;
203  }
204  else if (i < m + 1)
205  {
206  degsf[i]= 0;
207  degsg[i]= 0;
208  }
209  i++;
210  }
211  k--;
212  }
213  }
int degsgx
int * degsg
const CanonicalForm CFMap CFMap const Variable & x
factory&#39;s class for variables
Definition: factory.h:115
int * degsf
int both_non_zero
int k
Definition: cfEzgcd.cc:93
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
const CanonicalForm CFMap CFMap & N
int m
Definition: cfEzgcd.cc:119
const CanonicalForm CFMap & M
int i
Definition: cfEzgcd.cc:123
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
const CanonicalForm & G
int f_zero
int degsfx
int g_zero
int level() const
level() returns the level of CO.
int l
Definition: cfEzgcd.cc:94

§ newtonInterp()

static CanonicalForm newtonInterp ( const CanonicalForm alpha,
const CanonicalForm u,
const CanonicalForm newtonPoly,
const CanonicalForm oldInterPoly,
const Variable x 
)
inlinestatic

Definition at line 335 of file cfModResultant.cc.

338 {
339  CanonicalForm interPoly;
340 
341  interPoly= oldInterPoly+((u - oldInterPoly (alpha, x))/newtonPoly (alpha, x))
342  *newtonPoly;
343  return interPoly;
344 }
factory&#39;s main class
Definition: canonicalform.h:75

§ oneNorm()

static CanonicalForm oneNorm ( const CanonicalForm F)
inlinestatic

Definition at line 240 of file cfModResultant.cc.

241 {
242  if (F.inZ())
243  return abs (F);
244 
246  for (CFIterator i= F; i.hasTerms(); i++)
247  result += oneNorm (i.coeff());
248  return result;
249 }
factory&#39;s main class
Definition: canonicalform.h:75
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
bool inZ() const
predicates
static CanonicalForm oneNorm(const CanonicalForm &F)
return result
Definition: facAbsBiFact.cc:76

§ resultantFp()

CanonicalForm resultantFp ( const CanonicalForm A,
const CanonicalForm B,
const Variable x,
bool  prob = true 
)

modular resultant algorihtm over Fp

Returns
resultantFp returns the resultant of A and B wrt. x
Parameters
[in]Asome poly
[in]Bsome poly
[in]xsome polynomial variable
[in]probif true use probabilistic algorithm

Definition at line 347 of file cfModResultant.cc.

349 {
350  ASSERT (getCharacteristic() > 0, "characteristic > 0 expected");
351 
352  if (A.isZero() || B.isZero())
353  return 0;
354 
355  int degAx= degree (A, x);
356  int degBx= degree (B, x);
357  if (A.level() < x.level())
358  return power (A, degBx);
359  if (B.level() < x.level())
360  return power (B, degAx);
361 
362  if (degAx == 0)
363  return power (A, degBx);
364  else if (degBx == 0)
365  return power (B, degAx);
366 
367  if (A.isUnivariate() && B.isUnivariate() && A.level() == B.level())
368  return uniResultant (A, B);
369 
370  CanonicalForm F= A;
371  CanonicalForm G= B;
372 
373  CFMap M, N;
374  myCompress (F, G, M, N, x);
375 
376  F= M (F);
377  G= M (G);
378 
379  Variable y= Variable (2);
380 
381  CanonicalForm GEval, FEval, recResult, H;
382  CanonicalForm newtonPoly= 1;
383  CanonicalForm modResult= 0;
384 
385  Variable z= Variable (1);
386  int bound= degAx*degree (G, 2) + degree (F, 2)*degBx;
387 
388  int p= getCharacteristic();
389  CanonicalForm minpoly;
390  Variable alpha= Variable (tmax (F.level(), G.level()) + 1);
391  bool algExt= hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha);
392  CFGenerator * gen;
393  bool extOfExt= false;
394  Variable v= alpha;
395  CanonicalForm primElemAlpha, imPrimElemAlpha;
396  CFList source,dest;
397  if (!algExt && (p < (1 << 28)))
398  {
399  // pass to an extension of size at least 2^29
400  // for very very large input that is maybe too small though
401  int deg= ceil (29.0*((double) log (2)/log (p)))+1;
402  minpoly= randomIrredpoly (deg, z);
403  alpha= rootOf (minpoly);
404  AlgExtGenerator AlgExtGen (alpha);
405  gen= AlgExtGen.clone();
406  for (int i= 0; i < p; i++) // skip values from the prime field
407  (*gen).next();
408  }
409  else if (!algExt)
410  {
411  FFGenerator FFGen;
412  gen= FFGen.clone();
413  }
414  else
415  {
416  int deg= ceil (29.0*((double) log (2)/log (p)));
417  if (degree (getMipo (alpha)) < deg)
418  {
419  mpz_t field_size;
420  mpz_init (field_size);
421  mpz_ui_pow_ui (field_size, p,
422  deg + degree (getMipo (alpha)) - deg%degree (getMipo (alpha)));
423 
424  // field_size needs to fit in an int because of mapUp, mapDown, length of lists etc.
425  if (mpz_fits_sint_p (field_size))
426  {
427  minpoly= randomIrredpoly (deg + degree (getMipo (alpha))
428  - deg%degree (getMipo (alpha)), z);
429  v= rootOf (minpoly);
430  Variable V_buf2;
431  bool primFail= false;
432  extOfExt= true;
433  primElemAlpha= primitiveElement (alpha, V_buf2, primFail);
434  ASSERT (!primFail, "failure in integer factorizer");
435  if (primFail)
436  ; //ERROR
437  else
438  imPrimElemAlpha= mapPrimElem (primElemAlpha, alpha, v);
439  F= mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
440  G= mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
441  }
442  else
443  {
444  deg= deg - deg % degree (getMipo (alpha));
445  mpz_ui_pow_ui (field_size, p, deg);
446  while (deg / degree (getMipo (alpha)) >= 2 && !mpz_fits_sint_p (field_size))
447  {
448  deg -= degree (getMipo (alpha));
449  mpz_ui_pow_ui (field_size, p, deg);
450  }
451  if (deg != degree (getMipo (alpha)))
452  {
453  minpoly= randomIrredpoly (deg, z);
454  v= rootOf (minpoly);
455  Variable V_buf2;
456  bool primFail= false;
457  extOfExt= true;
458  primElemAlpha= primitiveElement (alpha, V_buf2, primFail);
459  ASSERT (!primFail, "failure in integer factorizer");
460  if (primFail)
461  ; //ERROR
462  else
463  imPrimElemAlpha= mapPrimElem (primElemAlpha, alpha, v);
464  F= mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
465  G= mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
466  }
467  }
468  mpz_clear (field_size);
469  }
470  AlgExtGenerator AlgExtGen (v);
471  gen= AlgExtGen.clone();
472  for (int i= 0; i < p; i++)
473  (*gen).next();
474  }
475  int count= 0;
476  int equalCount= 0;
477  CanonicalForm point;
478  do
479  {
480  evalPoint (F, G, FEval, GEval, *gen);
481 
482  recResult= resultantFp (FEval, GEval, z, prob);
483 
484  H= newtonInterp ((*gen).item(), recResult, newtonPoly, modResult, y);
485 
486  if (H == modResult)
487  equalCount++;
488  else
489  equalCount= 0;
490 
491  count++;
492  if (count > bound || (prob && equalCount == 2 && !H.inCoeffDomain()))
493  {
494  if (!algExt && degree (H, alpha) <= 0)
495  break;
496  else if (algExt)
497  {
498  if (extOfExt && !isInExtension (H, imPrimElemAlpha, 1, primElemAlpha,
499  dest, source))
500  {
501  H= mapDown (H, primElemAlpha, imPrimElemAlpha, alpha, dest, source);
502  prune (v);
503  break;
504  }
505  else if (!extOfExt)
506  break;
507  }
508  }
509 
510  modResult= H;
511  newtonPoly *= (y - (*gen).item());
512  if ((*gen).hasItems())
513  (*gen).next();
514  else
515  STICKYASSERT (0, "out of evaluation points");
516  } while (1);
517 
518  delete gen;
519 
520  return N (H);
521 }
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:93
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
Definition: cf_map_ext.cc:310
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
virtual class for generators
Definition: cf_generator.h:21
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
generate all elements in F_p starting from 0
Definition: cf_generator.h:55
gmp_float log(const gmp_float &a)
Definition: mpr_complex.cc:345
factory&#39;s main class
Definition: canonicalform.h:75
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression ...
Definition: cfModGcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
void prune(Variable &alpha)
Definition: variable.cc:261
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
int level() const
Definition: factory.h:132
bool isUnivariate() const
const CanonicalForm CFMap CFMap & N
#define A
Definition: sirandom.c:23
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
const CanonicalForm CFMap & M
int i
Definition: cfEzgcd.cc:123
CanonicalForm H
Definition: facAbsFact.cc:64
class CFMap
Definition: cf_map.h:84
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
#define STICKYASSERT(expression, message)
Definition: cf_assert.h:64
const CanonicalForm & G
static CanonicalForm uniResultant(const CanonicalForm &F, const CanonicalForm &G)
b *CanonicalForm B
Definition: facBivar.cc:51
virtual CFGenerator * clone() const
Definition: cf_generator.h:30
int level() const
level() returns the level of CO.
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
Definition: cf_irred.cc:42
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
virtual void next()
Definition: cf_generator.h:29
CFGenerator * clone() const
Definition: cf_generator.cc:52
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
bool inCoeffDomain() const

§ resultantZ()

CanonicalForm resultantZ ( const CanonicalForm A,
const CanonicalForm B,
const Variable x,
bool  prob = true 
)

modular resultant algorihtm over Z

Returns
resultantZ returns the resultant of A and B wrt. x
Parameters
[in]Asome poly
[in]Bsome poly
[in]xsome polynomial variable
[in]probif true use probabilistic algorithm

Definition at line 558 of file cfModResultant.cc.

560 {
561  ASSERT (getCharacteristic() == 0, "characteristic > 0 expected");
562 #ifndef NOASSERT
563  bool isRat= isOn (SW_RATIONAL);
564  On (SW_RATIONAL);
565  ASSERT (bCommonDen (A).isOne(), "input A is rational");
566  ASSERT (bCommonDen (B).isOne(), "input B is rational");
567  if (!isRat)
568  Off (SW_RATIONAL);
569 #endif
570 
571  int degAx= degree (A, x);
572  int degBx= degree (B, x);
573  if (A.level() < x.level())
574  return power (A, degBx);
575  if (B.level() < x.level())
576  return power (B, degAx);
577 
578  if (degAx == 0)
579  return power (A, degBx);
580  else if (degBx == 0)
581  return power (B, degAx);
582 
583  CanonicalForm F= A;
584  CanonicalForm G= B;
585 
586  Variable X= x;
587  if (F.level() != x.level() || G.level() != x.level())
588  {
589  if (F.level() > G.level())
590  X= F.mvar();
591  else
592  X= G.mvar();
593  F= swapvar (F, X, x);
594  G= swapvar (G, X, x);
595  }
596 
597  // now X is the main variable
598 
599  CanonicalForm d= 0;
600  CanonicalForm dd= 0;
602  for (CFIterator i= F; i.hasTerms(); i++)
603  {
604  buf= oneNorm (i.coeff());
605  d= (buf > d) ? buf : d;
606  }
607  CanonicalForm e= 0, ee= 0;
608  for (CFIterator i= G; i.hasTerms(); i++)
609  {
610  buf= oneNorm (i.coeff());
611  e= (buf > e) ? buf : e;
612  }
613  d= power (d, degBx);
614  e= power (e, degAx);
615  CanonicalForm bound= 1;
616  for (int i= degBx + degAx; i > 1; i--)
617  bound *= i;
618  bound *= d*e;
619  bound *= 2;
620 
621  bool onRational= isOn (SW_RATIONAL);
622  if (onRational)
623  Off (SW_RATIONAL);
624  int i = cf_getNumBigPrimes() - 1;
625  int p;
626  CanonicalForm l= lc (F)*lc(G);
627  CanonicalForm resultModP, q (0), newResult, newQ;
629  int equalCount= 0;
630  CanonicalForm test, newTest;
631  int count= 0;
632  do
633  {
634  p = cf_getBigPrime( i );
635  i--;
636  while ( i >= 0 && mod( l, p ) == 0)
637  {
638  p = cf_getBigPrime( i );
639  i--;
640  }
641 
642  if (i <= 0)
643  return resultant (A, B, x);
644 
645  setCharacteristic (p);
646 
647  TIMING_START (fac_resultant_p);
648  resultModP= resultantFp (mapinto (F), mapinto (G), X, prob);
649  TIMING_END_AND_PRINT (fac_resultant_p, "time to compute resultant mod p: ");
650 
651  setCharacteristic (0);
652 
653  count++;
654  if ( q.isZero() )
655  {
656  result= mapinto(resultModP);
657  q= p;
658  }
659  else
660  {
661  chineseRemainder( result, q, mapinto (resultModP), p, newResult, newQ );
662  q= newQ;
663  result= newResult;
664  test= symmetricRemainder (result,q);
665  if (test != newTest)
666  {
667  newTest= test;
668  equalCount= 0;
669  }
670  else
671  equalCount++;
672  if (newQ > bound || (prob && equalCount == 2))
673  {
674  result= test;
675  break;
676  }
677  }
678  } while (1);
679 
680  if (onRational)
681  On (SW_RATIONAL);
682  return swapvar (result, X, x);
683 }
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
void Off(int sw)
switches
TIMING_START(fac_alg_resultant)
const CanonicalForm CFMap CFMap const Variable & x
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
void setCharacteristic(int c)
Definition: cf_char.cc:23
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
#define A
Definition: sirandom.c:23
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
CanonicalForm mapinto(const CanonicalForm &f)
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm test
Definition: cfModGcd.cc:4037
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2...
Definition: cf_chinese.cc:52
const CanonicalForm & G
b *CanonicalForm B
Definition: facBivar.cc:51
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
static CanonicalForm oneNorm(const CanonicalForm &F)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94

§ symmetricRemainder()

static CanonicalForm symmetricRemainder ( const CanonicalForm f,
const CanonicalForm q 
)
inlinestatic

Definition at line 543 of file cfModResultant.cc.

544 {
546  if (f.isUnivariate() || f.inCoeffDomain())
547  return balanceUni (f, q);
548  else
549  {
550  Variable x= f.mvar();
551  for (CFIterator i= f; i.hasTerms(); i++)
552  result += power (x, i.exp())*symmetricRemainder (i.coeff(), q);
553  }
554  return result;
555 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm CFMap CFMap const Variable & x
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
bool isUnivariate() const
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
return result
Definition: facAbsBiFact.cc:76
static CanonicalForm balanceUni(const CanonicalForm &f, const CanonicalForm &q)
bool inCoeffDomain() const

§ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_resultant_p  ) const

§ uniResultant()

static CanonicalForm uniResultant ( const CanonicalForm F,
const CanonicalForm G 
)
inlinestatic

Definition at line 253 of file cfModResultant.cc.

254 {
255 #ifdef HAVE_NTL
256  ASSERT (getCharacteristic() > 0, "characteristic > 0 expected");
257  if (F.inCoeffDomain() && G.inCoeffDomain())
258  return 1;
259  if (F.isZero() || G.isZero())
260  return 0;
261  Variable alpha;
262 
263 #ifdef HAVE_FLINT
264  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G,alpha))
265  {
266  nmod_poly_t FLINTF, FLINTG;
267  convertFacCF2nmod_poly_t (FLINTF, F);
268  convertFacCF2nmod_poly_t (FLINTG, G);
269  mp_limb_t FLINTresult= nmod_poly_resultant (FLINTF, FLINTG);
270  nmod_poly_clear (FLINTF);
271  nmod_poly_clear (FLINTG);
272  return CanonicalForm ((long) FLINTresult);
273  }
274 #else
275  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G,alpha))
276  {
278  {
280  zz_p::init (getCharacteristic());
281  }
282  zz_pX NTLF= convertFacCF2NTLzzpX (F);
283  zz_pX NTLG= convertFacCF2NTLzzpX (G);
284 
285  zz_p NTLResult= resultant (NTLF, NTLG);
286 
287  return CanonicalForm (to_long (rep (NTLResult)));
288  }
289 #endif
290  //at this point F or G has an algebraic var.
292  {
294  zz_p::init (getCharacteristic());
295  }
296  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
297  zz_pE::init (NTLMipo);
298  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
299  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
300  zz_pE NTLResult= resultant (NTLF, NTLG);
301 
302  return convertNTLzzpE2CF (NTLResult, alpha);
303 #else
304  return resultant (F, G, F.mvar());
305 #endif
306 }
factory&#39;s class for variables
Definition: factory.h:115
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:797
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
nmod_poly_clear(FLINTmipo)
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
convertFacCF2nmod_poly_t(FLINTmipo, M)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1066
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:103
#define ASSERT(expression, message)
Definition: cf_assert.h:99
long fac_NTL_char
Definition: NTLconvert.cc:44
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
bool inCoeffDomain() const

Variable Documentation

§ both_non_zero

int both_non_zero = 0

Definition at line 58 of file cfModResultant.cc.

§ both_zero

int both_zero = 0

Definition at line 61 of file cfModResultant.cc.

§ degsf

degsf = new int [n + 1]

Definition at line 49 of file cfModResultant.cc.

§ degsfx

int degsfx

Definition at line 62 of file cfModResultant.cc.

§ degsg

delete [] degsg = new int [n + 1]

Definition at line 50 of file cfModResultant.cc.

§ degsgx

int degsgx

Definition at line 62 of file cfModResultant.cc.

§ else

else
Initial value:
{
for (int i= 1; i <= n; i++)
{
if (degsf[i] == 0 && degsg[i] == 0)
{
continue;
}
else
{
if (both_zero != 0 && i != 1)
{
M.newpair (Variable (i), Variable (i - both_zero));
N.newpair (Variable (i - both_zero), Variable (i));
}
}
}
}
delete [] degsf
int * degsg
factory&#39;s class for variables
Definition: factory.h:115
int * degsf
const CanonicalForm CFMap CFMap & N
const CanonicalForm CFMap & M
int i
Definition: cfEzgcd.cc:123
int both_zero

Definition at line 215 of file cfModResultant.cc.

§ f_zero

int f_zero = 0

Definition at line 59 of file cfModResultant.cc.

§ G

Definition at line 45 of file cfModResultant.cc.

§ g_zero

int g_zero = 0

Definition at line 60 of file cfModResultant.cc.

§ M

Definition at line 45 of file cfModResultant.cc.

§ N

Definition at line 45 of file cfModResultant.cc.

§ x

Initial value:
{
int n= tmax (F.level(), G.level())
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
const CanonicalForm & G
int level() const
level() returns the level of CO.

Definition at line 47 of file cfModResultant.cc.