My Project  UNKNOWN_GIT_VERSION
Functions
cfGcdAlgExt.h File Reference
#include "canonicalform.h"
#include "variable.h"

Go to the source code of this file.

Functions

CanonicalForm QGCD (const CanonicalForm &, const CanonicalForm &)
 gcd over Q(a) More...
 
void tryInvert (const CanonicalForm &, const CanonicalForm &, CanonicalForm &, bool &)
 
void tryBrownGCD (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel=true)
 modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true. More...
 
int * leadDeg (const CanonicalForm &f, int *degs)
 
bool isLess (int *a, int *b, int lower, int upper)
 
bool isEqual (int *a, int *b, int lower, int upper)
 
CanonicalForm firstLC (const CanonicalForm &f)
 

Detailed Description

GCD over Q(a)

ABSTRACT: Implementation of Encarnacion's GCD algorithm over number fields, see M.J. Encarnacion "Computing GCDs of polynomials over number fields", extended to the multivariate case.

See also
cfNTLzzpEXGCD.h

Definition in file cfGcdAlgExt.h.

Function Documentation

◆ firstLC()

CanonicalForm firstLC ( const CanonicalForm f)

Definition at line 956 of file cfGcdAlgExt.cc.

957 { // returns the leading coefficient (LC) of level <= 1
958  CanonicalForm ret = f;
959  while(ret.level() > 1)
960  ret = LC(ret);
961  return ret;
962 }

◆ isEqual()

bool isEqual ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 947 of file cfGcdAlgExt.cc.

948 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
949  for(int i=lower; i<=upper; i++)
950  if(a[i] != b[i])
951  return false;
952  return true;
953 }

◆ isLess()

bool isLess ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 936 of file cfGcdAlgExt.cc.

937 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
938  for(int i=upper; i>=lower; i--)
939  if(a[i] == b[i])
940  continue;
941  else
942  return a[i] < b[i];
943  return true;
944 }

◆ leadDeg()

int* leadDeg ( const CanonicalForm f,
int *  degs 
)

Definition at line 919 of file cfGcdAlgExt.cc.

920 { // leading degree vector w.r.t. lex. monomial order x(i+1) > x(i)
921  // if f is in a coeff domain, the zero pointer is returned
922  // 'a' should point to an array of sufficient size level(f)+1
923  if(f.inCoeffDomain())
924  return 0;
925  CanonicalForm tmp = f;
926  do
927  {
928  degs[tmp.level()] = tmp.degree();
929  tmp = LC(tmp);
930  }
931  while(!tmp.inCoeffDomain());
932  return degs;
933 }

◆ QGCD()

gcd over Q(a)

Definition at line 715 of file cfGcdAlgExt.cc.

716 { // f,g in Q(a)[x1,...,xn]
717  if(F.isZero())
718  {
719  if(G.isZero())
720  return G; // G is zero
721  if(G.inCoeffDomain())
722  return CanonicalForm(1);
723  CanonicalForm lcinv= 1/Lc (G);
724  return G*lcinv; // return monic G
725  }
726  if(G.isZero()) // F is non-zero
727  {
728  if(F.inCoeffDomain())
729  return CanonicalForm(1);
730  CanonicalForm lcinv= 1/Lc (F);
731  return F*lcinv; // return monic F
732  }
733  if(F.inCoeffDomain() || G.inCoeffDomain())
734  return CanonicalForm(1);
735  // here: both NOT inCoeffDomain
736  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
737  int p, i;
738  int *bound, *other; // degree vectors
739  bool fail;
740  bool off_rational=!isOn(SW_RATIONAL);
741  On( SW_RATIONAL ); // needed by bCommonDen
742  f = F * bCommonDen(F);
743  g = G * bCommonDen(G);
745  CanonicalForm contf= myicontent (f);
746  CanonicalForm contg= myicontent (g);
747  f /= contf;
748  g /= contg;
749  CanonicalForm gcdcfcg= myicontent (contf, contg);
750  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
751  Variable a, b;
752  if(hasFirstAlgVar(f,a))
753  {
754  if(hasFirstAlgVar(g,b))
755  {
756  if(b.level() > a.level())
757  a = b;
758  }
759  }
760  else
761  {
762  if(!hasFirstAlgVar(g,a))// both not in extension
763  {
764  Off( SW_RATIONAL );
765  Off( SW_USE_QGCD );
766  tmp = gcdcfcg*gcd( f, g );
767  On( SW_USE_QGCD );
768  if (off_rational) Off(SW_RATIONAL);
769  return tmp;
770  }
771  }
772  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
773  setReduce(a,false); // do not reduce expressions modulo mipo
774  tmp = getMipo(a);
775  M = tmp * bCommonDen(tmp);
776  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
777  Off( SW_RATIONAL ); // needed by mod
778  // calculate upper bound for degree vector of gcd
779  int mv = f.level(); i = g.level();
780  if(i > mv)
781  mv = i;
782  // here: mv is level of the largest variable in f, g
783  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
784  other = new int[mv+1];
785  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
786  bound[i] = other[i] = 0;
787  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
788  other = leadDeg(g,other);
789  for(int i=1; i<=mv; i++) // entry at i=0 not visited
790  if(other[i] < bound[i])
791  bound[i] = other[i];
792  // now 'bound' is the smaller vector
793  cl = lc(M) * lc(f) * lc(g);
794  q = 1;
795  D = 0;
796  CanonicalForm test= 0;
797  bool equal= false;
798  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
799  {
800  p = cf_getBigPrime(i);
801  if( mod( cl, p ).isZero() ) // skip lc-bad primes
802  continue;
803  fail = false;
805  mipo = mapinto(M);
806  mipo /= mipo.lc();
807  // here: mipo is monic
808  TIMING_START (alg_gcd_p)
809  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
810  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
811  if( fail ) // mipo splits in char p
812  {
814  continue;
815  }
816  if( Dp.inCoeffDomain() ) // early termination
817  {
818  tryInvert(Dp,mipo,tmp,fail); // check if zero divisor
820  if(fail)
821  continue;
822  setReduce(a,true);
823  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
824  delete[] other;
825  delete[] bound;
826  return gcdcfcg;
827  }
829  // here: Dp NOT inCoeffDomain
830  for(int i=1; i<=mv; i++)
831  other[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
832  other = leadDeg(Dp,other);
833 
834  if(isEqual(bound, other, 1, mv)) // equal
835  {
836  chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
837  // tmp = Dp mod p
838  // tmp = D mod q
839  // newq = p*q
840  q = newq;
841  if( D != tmp )
842  D = tmp;
843  On( SW_RATIONAL );
844  TIMING_START (alg_reconstruction)
845  tmp = Farey( D, q ); // Farey
846  tmp *= bCommonDen (tmp);
847  TIMING_END_AND_PRINT (alg_reconstruction,
848  "time for rational reconstruction in alg gcd: ")
849  setReduce(a,true); // reduce expressions modulo mipo
850  On( SW_RATIONAL ); // needed by fdivides
851  if (test != tmp)
852  test= tmp;
853  else
854  equal= true; // modular image did not add any new information
855  TIMING_START (alg_termination)
856 #ifdef HAVE_NTL
857 #ifdef HAVE_FLINT
858  if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
859  && f.level() == tmp.level() && tmp.level() == g.level())
860  {
861  CanonicalForm Q, R;
862  newtonDivrem (f, tmp, Q, R);
863  if (R.isZero())
864  {
865  newtonDivrem (g, tmp, Q, R);
866  if (R.isZero())
867  {
868  Off (SW_RATIONAL);
869  setReduce (a,true);
870  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
871  TIMING_END_AND_PRINT (alg_termination,
872  "time for successful termination test in alg gcd: ")
873  delete[] other;
874  delete[] bound;
875  return tmp*gcdcfcg;
876  }
877  }
878  }
879  else
880 #endif
881 #endif
882  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
883  {
884  Off( SW_RATIONAL );
885  setReduce(a,true);
886  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
887  TIMING_END_AND_PRINT (alg_termination,
888  "time for successful termination test in alg gcd: ")
889  delete[] other;
890  delete[] bound;
891  return tmp*gcdcfcg;
892  }
893  TIMING_END_AND_PRINT (alg_termination,
894  "time for unsuccessful termination test in alg gcd: ")
895  Off( SW_RATIONAL );
896  setReduce(a,false); // do not reduce expressions modulo mipo
897  continue;
898  }
899  if( isLess(bound, other, 1, mv) ) // current prime unlucky
900  continue;
901  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
902  q = p;
903  D = mapinto(Dp); // shortcut CRA // shortcut CRA
904  for(int i=1; i<=mv; i++) // tighten bound
905  bound[i] = other[i];
906  }
907  // hopefully, we never reach this point
908  setReduce(a,true);
909  delete[] other;
910  delete[] bound;
911  Off( SW_USE_QGCD );
912  D = gcdcfcg*gcd( f, g );
913  On( SW_USE_QGCD );
914  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
915  return D;
916 }

◆ tryBrownGCD()

void tryBrownGCD ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M,
CanonicalForm result,
bool &  fail,
bool  topLevel = true 
)

modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true.

Definition at line 372 of file cfGcdAlgExt.cc.

373 { // assume F,G are multivariate polys over Z/p(a) for big prime p, M "univariate" polynomial in an algebraic variable
374  // M is assumed to be monic
375  if(F.isZero())
376  {
377  if(G.isZero())
378  {
379  result = G; // G is zero
380  return;
381  }
382  if(G.inCoeffDomain())
383  {
384  tryInvert(G,M,result,fail);
385  if(fail)
386  return;
387  result = 1;
388  return;
389  }
390  // try to make G monic modulo M
391  CanonicalForm inv;
392  tryInvert(Lc(G),M,inv,fail);
393  if(fail)
394  return;
395  result = inv*G;
396  result= reduce (result, M);
397  return;
398  }
399  if(G.isZero()) // F is non-zero
400  {
401  if(F.inCoeffDomain())
402  {
403  tryInvert(F,M,result,fail);
404  if(fail)
405  return;
406  result = 1;
407  return;
408  }
409  // try to make F monic modulo M
410  CanonicalForm inv;
411  tryInvert(Lc(F),M,inv,fail);
412  if(fail)
413  return;
414  result = inv*F;
415  result= reduce (result, M);
416  return;
417  }
418  // here: F,G both nonzero
419  if(F.inCoeffDomain())
420  {
421  tryInvert(F,M,result,fail);
422  if(fail)
423  return;
424  result = 1;
425  return;
426  }
427  if(G.inCoeffDomain())
428  {
429  tryInvert(G,M,result,fail);
430  if(fail)
431  return;
432  result = 1;
433  return;
434  }
435  TIMING_START (alg_compress)
436  CFMap MM,NN;
437  int lev= myCompress (F, G, MM, NN, topLevel);
438  if (lev == 0)
439  {
440  result= 1;
441  return;
442  }
443  CanonicalForm f=MM(F);
444  CanonicalForm g=MM(G);
445  TIMING_END_AND_PRINT (alg_compress, "time to compress in alg gcd: ")
446  // here: f,g are compressed
447  // compute largest variable in f or g (least one is Variable(1))
448  int mv = f.level();
449  if(g.level() > mv)
450  mv = g.level();
451  // here: mv is level of the largest variable in f, g
452  Variable v1= Variable (1);
453 #ifdef HAVE_NTL
454  Variable v= M.mvar();
456  {
458  zz_p::init (getCharacteristic());
459  }
460  zz_pX NTLMipo= convertFacCF2NTLzzpX (M);
461  zz_pE::init (NTLMipo);
462  zz_pEX NTLResult;
463  zz_pEX NTLF;
464  zz_pEX NTLG;
465 #endif
466  if(mv == 1) // f,g univariate
467  {
468  TIMING_START (alg_euclid_p)
469 #ifdef HAVE_NTL
470  NTLF= convertFacCF2NTLzz_pEX (f, NTLMipo);
471  NTLG= convertFacCF2NTLzz_pEX (g, NTLMipo);
472  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
473  if (fail)
474  return;
475  result= convertNTLzz_pEX2CF (NTLResult, f.mvar(), v);
476 #else
477  tryEuclid(f,g,M,result,fail);
478  if(fail)
479  return;
480 #endif
481  TIMING_END_AND_PRINT (alg_euclid_p, "time for euclidean alg mod p: ")
482  result= NN (reduce (result, M)); // do not forget to map back
483  return;
484  }
485  TIMING_START (alg_content_p)
486  // here: mv > 1
487  CanonicalForm cf = tryvcontent(f, Variable(2), M, fail); // cf is univariate poly in var(1)
488  if(fail)
489  return;
490  CanonicalForm cg = tryvcontent(g, Variable(2), M, fail);
491  if(fail)
492  return;
493  CanonicalForm c;
494 #ifdef HAVE_NTL
495  NTLF= convertFacCF2NTLzz_pEX (cf, NTLMipo);
496  NTLG= convertFacCF2NTLzz_pEX (cg, NTLMipo);
497  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
498  if (fail)
499  return;
500  c= convertNTLzz_pEX2CF (NTLResult, v1, v);
501 #else
502  tryEuclid(cf,cg,M,c,fail);
503  if(fail)
504  return;
505 #endif
506  // f /= cf
507  f.tryDiv (cf, M, fail);
508  if(fail)
509  return;
510  // g /= cg
511  g.tryDiv (cg, M, fail);
512  if(fail)
513  return;
514  TIMING_END_AND_PRINT (alg_content_p, "time for content in alg gcd mod p: ")
515  if(f.inCoeffDomain())
516  {
517  tryInvert(f,M,result,fail);
518  if(fail)
519  return;
520  result = NN(c);
521  return;
522  }
523  if(g.inCoeffDomain())
524  {
525  tryInvert(g,M,result,fail);
526  if(fail)
527  return;
528  result = NN(c);
529  return;
530  }
531  int *L = new int[mv+1]; // L is addressed by i from 2 to mv
532  int *N = new int[mv+1];
533  for(int i=2; i<=mv; i++)
534  L[i] = N[i] = 0;
535  L = leadDeg(f, L);
536  N = leadDeg(g, N);
537  CanonicalForm gamma;
538  TIMING_START (alg_euclid_p)
539 #ifdef HAVE_NTL
540  NTLF= convertFacCF2NTLzz_pEX (firstLC (f), NTLMipo);
541  NTLG= convertFacCF2NTLzz_pEX (firstLC (g), NTLMipo);
542  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
543  if (fail)
544  return;
545  gamma= convertNTLzz_pEX2CF (NTLResult, v1, v);
546 #else
547  tryEuclid( firstLC(f), firstLC(g), M, gamma, fail );
548  if(fail)
549  return;
550 #endif
551  TIMING_END_AND_PRINT (alg_euclid_p, "time for gcd of lcs in alg mod p: ")
552  for(int i=2; i<=mv; i++) // entries at i=0,1 not visited
553  if(N[i] < L[i])
554  L[i] = N[i];
555  // L is now upper bound for degrees of gcd
556  int *dg_im = new int[mv+1]; // for the degree vector of the image we don't need any entry at i=1
557  for(int i=2; i<=mv; i++)
558  dg_im[i] = 0; // initialize
559  CanonicalForm gamma_image, m=1;
560  CanonicalForm gm=0;
561  CanonicalForm g_image, alpha, gnew;
562  FFGenerator gen = FFGenerator();
563  Variable x= Variable (1);
564  bool divides= true;
565  for(FFGenerator gen = FFGenerator(); gen.hasItems(); gen.next())
566  {
567  alpha = gen.item();
568  gamma_image = reduce(gamma(alpha, x),M); // plug in alpha for var(1)
569  if(gamma_image.isZero()) // skip lc-bad points var(1)-alpha
570  continue;
571  TIMING_START (alg_recursion_p)
572  tryBrownGCD( f(alpha, x), g(alpha, x), M, g_image, fail, false ); // recursive call with one var less
573  TIMING_END_AND_PRINT (alg_recursion_p,
574  "time for recursive calls in alg gcd mod p: ")
575  if(fail)
576  return;
577  g_image = reduce(g_image, M);
578  if(g_image.inCoeffDomain()) // early termination
579  {
580  tryInvert(g_image,M,result,fail);
581  if(fail)
582  return;
583  result = NN(c);
584  return;
585  }
586  for(int i=2; i<=mv; i++)
587  dg_im[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
588  dg_im = leadDeg(g_image, dg_im); // dg_im cannot be NIL-pointer
589  if(isEqual(dg_im, L, 2, mv))
590  {
591  CanonicalForm inv;
592  tryInvert (firstLC (g_image), M, inv, fail);
593  if (fail)
594  return;
595  g_image *= inv;
596  g_image *= gamma_image; // multiply by multiple of image lc(gcd)
597  g_image= reduce (g_image, M);
598  TIMING_START (alg_newton_p)
599  gnew= tryNewtonInterp (alpha, g_image, m, gm, x, M, fail);
600  TIMING_END_AND_PRINT (alg_newton_p,
601  "time for Newton interpolation in alg gcd mod p: ")
602  // gnew = gm mod m
603  // gnew = g_image mod var(1)-alpha
604  // mnew = m * (var(1)-alpha)
605  if(fail)
606  return;
607  m *= (x - alpha);
608  if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
609  {
610  TIMING_START (alg_termination_p)
611  cf = tryvcontent(gnew, Variable(2), M, fail);
612  if(fail)
613  return;
614  divides = true;
615  g_image= gnew;
616  g_image.tryDiv (cf, M, fail);
617  if(fail)
618  return;
619  divides= tryFdivides (g_image,f, M, fail); // trial division (f)
620  if(fail)
621  return;
622  if(divides)
623  {
624  bool divides2= tryFdivides (g_image,g, M, fail); // trial division (g)
625  if(fail)
626  return;
627  if(divides2)
628  {
629  result = NN(reduce (c*g_image, M));
630  TIMING_END_AND_PRINT (alg_termination_p,
631  "time for successful termination test in alg gcd mod p: ")
632  return;
633  }
634  }
635  TIMING_END_AND_PRINT (alg_termination_p,
636  "time for unsuccessful termination test in alg gcd mod p: ")
637  }
638  gm = gnew;
639  continue;
640  }
641 
642  if(isLess(L, dg_im, 2, mv)) // dg_im > L --> current point unlucky
643  continue;
644 
645  // here: isLess(dg_im, L, 2, mv) --> all previous points were unlucky
646  m = CanonicalForm(1); // reset
647  gm = 0; // reset
648  for(int i=2; i<=mv; i++) // tighten bound
649  L[i] = dg_im[i];
650  }
651  // we are out of evaluation points
652  fail = true;
653 }

◆ tryInvert()

void tryInvert ( const CanonicalForm ,
const CanonicalForm ,
CanonicalForm ,
bool &   
)

Definition at line 221 of file cfGcdAlgExt.cc.

222 { // F, M are required to be "univariate" polynomials in an algebraic variable
223  // we try to invert F modulo M
224  if(F.inBaseDomain())
225  {
226  if(F.isZero())
227  {
228  fail = true;
229  return;
230  }
231  inv = 1/F;
232  return;
233  }
235  Variable a = M.mvar();
236  Variable x = Variable(1);
237  if(!extgcd( replacevar( F, a, x ), replacevar( M, a, x ), inv, b ).isOne())
238  fail = true;
239  else
240  inv = replacevar( inv, x, a ); // change back to alg var
241 }
test
CanonicalForm test
Definition: cfModGcd.cc:4037
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
tryvcontent
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:1048
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
N
const CanonicalForm CFMap CFMap & N
Definition: cfGcdAlgExt.cc:56
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
f
FILE * f
Definition: checklibs.c:9
firstLC
CanonicalForm firstLC(const CanonicalForm &f)
Definition: cfGcdAlgExt.cc:956
CanonicalForm::tryDiv
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
Definition: canonicalform.cc:840
equal
bool equal
Definition: cfModGcd.cc:4067
x
Variable x
Definition: cfModGcd.cc:4023
if
if(topLevel)
Definition: cfGcdAlgExt.cc:75
result
return result
Definition: facAbsBiFact.cc:76
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
CFMap
class CFMap
Definition: cf_map.h:84
isEqual
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:947
reduce
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition: cf_ops.cc:646
g
g
Definition: cfModGcd.cc:4031
else
else
Definition: cfGcdAlgExt.cc:195
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
tryFdivides
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
Definition: cf_algorithm.cc:454
tryNewtonInterp
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:357
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
extgcd
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:173
cl
cl
Definition: cfModGcd.cc:4041
cf_getNumBigPrimes
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CanonicalForm
factory's main class
Definition: canonicalform.h:77
next
ListNode * next
Definition: janet.h:31
leadDeg
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:919
gcdcfcg
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4042
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
TIMING_START
TIMING_START(fac_alg_resultant)
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
D
#define D(A)
Definition: gentable.cc:131
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
FFGenerator
generate all elements in F_p starting from 0
Definition: cf_generator.h:55
cg
CanonicalForm cg
Definition: cfModGcd.cc:4024
for
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:65
return
return
Definition: cfGcdAlgExt.cc:218
convertNTLzz_pEX2CF
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
false
return false
Definition: cfModGcd.cc:84
chineseRemainder
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
myicontent
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:656
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
newtonDivrem
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
Definition: facMul.cc:342
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
setReduce
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
Variable
factory's class for variables
Definition: factory.h:117
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition: canonicalform.cc:381
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
topLevel
const CanonicalForm CFMap CFMap bool topLevel
Definition: cfGcdAlgExt.cc:57
M
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition: canonicalform.h:348
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition: canonicalform.cc:304
m
int m
Definition: cfEzgcd.cc:121
R
#define R
Definition: sirandom.c:26
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
replacevar
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
tryInvert
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:221
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
Farey
static number Farey(number p, number n, const coeffs)
Definition: flintcf_Q.cc:441
SW_USE_QGCD
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
Q
#define Q
Definition: sirandom.c:25
tryNTLGCD
void tryNTLGCD(zz_pEX &x, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the GCD x of a and b, fail is set to true if a zero divisor is encountered
Definition: cfNTLzzpEXGCD.cc:242
G
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:55
myCompress
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
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
alg_content
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
isLess
bool isLess(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:936