Functions | Variables
cfGcdAlgExt.cc File Reference
#include "config.h"
#include <stdio.h>
#include <iostream>
#include "cf_assert.h"
#include "timing.h"
#include "templates/ftmpl_functions.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "cfGcdAlgExt.h"
#include "cfUnivarGcd.h"
#include "cf_map.h"
#include "cf_generator.h"
#include "facMul.h"
#include "cfNTLzzpEXGCD.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (alg_content_p) TIMING_DEFINE_PRINT(alg_content) TIMING_DEFINE_PRINT(alg_compress) TIMING_DEFINE_PRINT(alg_termination) TIMING_DEFINE_PRINT(alg_termination_p) TIMING_DEFINE_PRINT(alg_reconstruction) TIMING_DEFINE_PRINT(alg_newton_p) TIMING_DEFINE_PRINT(alg_recursion_p) TIMING_DEFINE_PRINT(alg_gcd_p) TIMING_DEFINE_PRINT(alg_euclid_p) static int myCompress(const CanonicalForm &F
 compressing two polynomials F and G, M is used for compressing, N to reverse the compression More...
 
 for (int i=0;i<=n;i++) degsf[i]
 
 if (topLevel)
 
void tryInvert (const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
 
static CanonicalForm trycontent (const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
 
static CanonicalForm tryvcontent (const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
 
static CanonicalForm trycf_content (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
 
static CanonicalForm tryNewtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
 
void tryBrownGCD (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
 modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true. More...
 
static CanonicalForm myicontent (const CanonicalForm &f, const CanonicalForm &c)
 
static CanonicalForm myicontent (const CanonicalForm &f)
 
CanonicalForm QGCD (const CanonicalForm &F, const CanonicalForm &G)
 gcd over Q(a) 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)
 

Variables

const CanonicalFormG
 
const CanonicalForm CFMapM
 
const CanonicalForm CFMap CFMapN
 
const CanonicalForm CFMap CFMap bool topLevel
 
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
 
 else
 
 return
 

Function Documentation

§ firstLC()

CanonicalForm firstLC ( const CanonicalForm f)

Definition at line 946 of file cfGcdAlgExt.cc.

947 { // returns the leading coefficient (LC) of level <= 1
948  CanonicalForm ret = f;
949  while(ret.level() > 1)
950  ret = LC(ret);
951  return ret;
952 }
f
Definition: cfModGcd.cc:4022
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
CanonicalForm LC(const CanonicalForm &f)

§ 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 ( topLevel  )

Definition at line 73 of file cfGcdAlgExt.cc.

74  {
75  for (int i= 1; i <= n; i++)
76  {
77  if (degsf[i] != 0 && degsg[i] != 0)
78  {
79  both_non_zero++;
80  continue;
81  }
82  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
83  {
84  f_zero++;
85  continue;
86  }
87  if (degsg[i] == 0 && degsf[i] && i <= F.level())
88  {
89  g_zero++;
90  continue;
91  }
92  }
93 
94  if (both_non_zero == 0)
95  {
96  delete [] degsf;
97  delete [] degsg;
98  return 0;
99  }
100 
101  // map Variables which do not occur in both polynomials to higher levels
102  int k= 1;
103  int l= 1;
104  for (int i= 1; i <= n; i++)
105  {
106  if (degsf[i] != 0 && degsg[i] == 0 && i <= F.level())
107  {
108  if (k + both_non_zero != i)
109  {
110  M.newpair (Variable (i), Variable (k + both_non_zero));
111  N.newpair (Variable (k + both_non_zero), Variable (i));
112  }
113  k++;
114  }
115  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
116  {
117  if (l + g_zero + both_non_zero != i)
118  {
119  M.newpair (Variable (i), Variable (l + g_zero + both_non_zero));
120  N.newpair (Variable (l + g_zero + both_non_zero), Variable (i));
121  }
122  l++;
123  }
124  }
125 
126  // sort Variables x_{i} in increasing order of
127  // min(deg_{x_{i}}(f),deg_{x_{i}}(g))
128  int m= tmax (F.level(), G.level());
129  int min_max_deg;
130  k= both_non_zero;
131  l= 0;
132  int i= 1;
133  while (k > 0)
134  {
135  if (degsf [i] != 0 && degsg [i] != 0)
136  min_max_deg= tmax (degsf[i], degsg[i]);
137  else
138  min_max_deg= 0;
139  while (min_max_deg == 0)
140  {
141  i++;
142  min_max_deg= tmax (degsf[i], degsg[i]);
143  if (degsf [i] != 0 && degsg [i] != 0)
144  min_max_deg= tmax (degsf[i], degsg[i]);
145  else
146  min_max_deg= 0;
147  }
148  for (int j= i + 1; j <= m; j++)
149  {
150  if (tmax (degsf[j],degsg[j]) <= min_max_deg && degsf[j] != 0 && degsg [j] != 0)
151  {
152  min_max_deg= tmax (degsf[j], degsg[j]);
153  l= j;
154  }
155  }
156  if (l != 0)
157  {
158  if (l != k)
159  {
160  M.newpair (Variable (l), Variable(k));
161  N.newpair (Variable (k), Variable(l));
162  degsf[l]= 0;
163  degsg[l]= 0;
164  l= 0;
165  }
166  else
167  {
168  degsf[l]= 0;
169  degsg[l]= 0;
170  l= 0;
171  }
172  }
173  else if (l == 0)
174  {
175  if (i != k)
176  {
177  M.newpair (Variable (i), Variable (k));
178  N.newpair (Variable (k), Variable (i));
179  degsf[i]= 0;
180  degsg[i]= 0;
181  }
182  else
183  {
184  degsf[i]= 0;
185  degsg[i]= 0;
186  }
187  i++;
188  }
189  k--;
190  }
191  }
int f_zero
Definition: cfGcdAlgExt.cc:69
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:115
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
int both_non_zero
Definition: cfGcdAlgExt.cc:68
int k
Definition: cfEzgcd.cc:93
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:55
int * degsf
Definition: cfGcdAlgExt.cc:59
int j
Definition: myNF.cc:70
int * degsg
Definition: cfGcdAlgExt.cc:60
const CanonicalForm CFMap CFMap & N
Definition: cfGcdAlgExt.cc:55
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int g_zero
Definition: cfGcdAlgExt.cc:70
int level() const
level() returns the level of CO.
int l
Definition: cfEzgcd.cc:94

§ isEqual()

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

Definition at line 937 of file cfGcdAlgExt.cc.

938 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
939  for(int i=lower; i<=upper; i++)
940  if(a[i] != b[i])
941  return false;
942  return true;
943 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213

§ isLess()

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

Definition at line 926 of file cfGcdAlgExt.cc.

927 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
928  for(int i=upper; i>=lower; i--)
929  if(a[i] == b[i])
930  continue;
931  else
932  return a[i] < b[i];
933  return true;
934 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213

§ leadDeg()

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

Definition at line 909 of file cfGcdAlgExt.cc.

910 { // leading degree vector w.r.t. lex. monomial order x(i+1) > x(i)
911  // if f is in a coeff domain, the zero pointer is returned
912  // 'a' should point to an array of sufficient size level(f)+1
913  if(f.inCoeffDomain())
914  return 0;
915  CanonicalForm tmp = f;
916  do
917  {
918  degs[tmp.level()] = tmp.degree();
919  tmp = LC(tmp);
920  }
921  while(!tmp.inCoeffDomain());
922  return degs;
923 }
f
Definition: cfModGcd.cc:4022
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
CanonicalForm LC(const CanonicalForm &f)
bool inCoeffDomain() const

§ myicontent() [1/2]

static CanonicalForm myicontent ( const CanonicalForm f,
const CanonicalForm c 
)
static

Definition at line 654 of file cfGcdAlgExt.cc.

655 {
656 #ifdef HAVE_NTL
657  if (f.isOne() || c.isOne())
658  return 1;
659  if ( f.inBaseDomain() && c.inBaseDomain())
660  {
661  if (c.isZero()) return abs(f);
662  return bgcd( f, c );
663  }
664  else if ( (f.inCoeffDomain() && c.inCoeffDomain()) ||
665  (f.inCoeffDomain() && c.inBaseDomain()) ||
666  (f.inBaseDomain() && c.inCoeffDomain()))
667  {
668  if (c.isZero()) return abs (f);
669 #ifdef HAVE_FLINT
670  fmpz_poly_t FLINTf, FLINTc;
671  convertFacCF2Fmpz_poly_t (FLINTf, f);
672  convertFacCF2Fmpz_poly_t (FLINTc, c);
673  fmpz_poly_gcd (FLINTc, FLINTc, FLINTf);
675  if (f.inCoeffDomain())
676  result= convertFmpz_poly_t2FacCF (FLINTc, f.mvar());
677  else
678  result= convertFmpz_poly_t2FacCF (FLINTc, c.mvar());
679  fmpz_poly_clear (FLINTc);
680  fmpz_poly_clear (FLINTf);
681  return result;
682 #else
683  ZZX NTLf= convertFacCF2NTLZZX (f);
684  ZZX NTLc= convertFacCF2NTLZZX (c);
685  NTLc= GCD (NTLc, NTLf);
686  if (f.inCoeffDomain())
687  return convertNTLZZX2CF(NTLc,f.mvar());
688  else
689  return convertNTLZZX2CF(NTLc,c.mvar());
690 #endif
691  }
692  else
693  {
694  CanonicalForm g = c;
695  for ( CFIterator i = f; i.hasTerms() && ! g.isOne(); i++ )
696  g = myicontent( i.coeff(), g );
697  return g;
698  }
699 #else
700  return 1;
701 #endif
702 }
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:654
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:688
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
bool inBaseDomain() 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.
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
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:281
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ myicontent() [2/2]

static CanonicalForm myicontent ( const CanonicalForm f)
static

Definition at line 704 of file cfGcdAlgExt.cc.

705 {
706 #ifdef HAVE_NTL
707  return myicontent( f, 0 );
708 #else
709  return 1;
710 #endif
711 }
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:654

§ QGCD()

gcd over Q(a)

Definition at line 713 of file cfGcdAlgExt.cc.

714 { // f,g in Q(a)[x1,...,xn]
715  if(F.isZero())
716  {
717  if(G.isZero())
718  return G; // G is zero
719  if(G.inCoeffDomain())
720  return CanonicalForm(1);
721  CanonicalForm lcinv= 1/Lc (G);
722  return G*lcinv; // return monic G
723  }
724  if(G.isZero()) // F is non-zero
725  {
726  if(F.inCoeffDomain())
727  return CanonicalForm(1);
728  CanonicalForm lcinv= 1/Lc (F);
729  return F*lcinv; // return monic F
730  }
731  if(F.inCoeffDomain() || G.inCoeffDomain())
732  return CanonicalForm(1);
733  // here: both NOT inCoeffDomain
734  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
735  int p, i;
736  int *bound, *other; // degree vectors
737  bool fail;
738  bool off_rational=!isOn(SW_RATIONAL);
739  On( SW_RATIONAL ); // needed by bCommonDen
740  f = F * bCommonDen(F);
741  g = G * bCommonDen(G);
743  CanonicalForm contf= myicontent (f);
744  CanonicalForm contg= myicontent (g);
745  f /= contf;
746  g /= contg;
747  CanonicalForm gcdcfcg= myicontent (contf, contg);
748  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
749  Variable a, b;
750  if(hasFirstAlgVar(f,a))
751  {
752  if(hasFirstAlgVar(g,b))
753  {
754  if(b.level() > a.level())
755  a = b;
756  }
757  }
758  else
759  {
760  if(!hasFirstAlgVar(g,a))// both not in extension
761  {
762  Off( SW_RATIONAL );
763  Off( SW_USE_QGCD );
764  tmp = gcdcfcg*gcd( f, g );
765  On( SW_USE_QGCD );
766  if (off_rational) Off(SW_RATIONAL);
767  return tmp;
768  }
769  }
770  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
771  setReduce(a,false); // do not reduce expressions modulo mipo
772  tmp = getMipo(a);
773  M = tmp * bCommonDen(tmp);
774  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
775  Off( SW_RATIONAL ); // needed by mod
776  // calculate upper bound for degree vector of gcd
777  int mv = f.level(); i = g.level();
778  if(i > mv)
779  mv = i;
780  // here: mv is level of the largest variable in f, g
781  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
782  other = new int[mv+1];
783  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
784  bound[i] = other[i] = 0;
785  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
786  other = leadDeg(g,other);
787  for(int i=1; i<=mv; i++) // entry at i=0 not visited
788  if(other[i] < bound[i])
789  bound[i] = other[i];
790  // now 'bound' is the smaller vector
791  cl = lc(M) * lc(f) * lc(g);
792  q = 1;
793  D = 0;
794  CanonicalForm test= 0;
795  bool equal= false;
796  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
797  {
798  p = cf_getBigPrime(i);
799  if( mod( cl, p ).isZero() ) // skip lc-bad primes
800  continue;
801  fail = false;
803  mipo = mapinto(M);
804  mipo /= mipo.lc();
805  // here: mipo is monic
806  TIMING_START (alg_gcd_p)
807  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
808  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
809  if( fail ) // mipo splits in char p
810  {
812  continue;
813  }
814  if( Dp.inCoeffDomain() ) // early termination
815  {
816  tryInvert(Dp,mipo,tmp,fail); // check if zero divisor
818  if(fail)
819  continue;
820  setReduce(a,true);
821  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
822  return gcdcfcg;
823  }
825  // here: Dp NOT inCoeffDomain
826  for(int i=1; i<=mv; i++)
827  other[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
828  other = leadDeg(Dp,other);
829 
830  if(isEqual(bound, other, 1, mv)) // equal
831  {
832  chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
833  // tmp = Dp mod p
834  // tmp = D mod q
835  // newq = p*q
836  q = newq;
837  if( D != tmp )
838  D = tmp;
839  On( SW_RATIONAL );
840  TIMING_START (alg_reconstruction)
841  tmp = Farey( D, q ); // Farey
842  tmp *= bCommonDen (tmp);
843  TIMING_END_AND_PRINT (alg_reconstruction,
844  "time for rational reconstruction in alg gcd: ")
845  setReduce(a,true); // reduce expressions modulo mipo
846  On( SW_RATIONAL ); // needed by fdivides
847  if (test != tmp)
848  test= tmp;
849  else
850  equal= true; // modular image did not add any new information
851  TIMING_START (alg_termination)
852 #ifdef HAVE_NTL
853 #ifdef HAVE_FLINT
854  if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
855  && f.level() == tmp.level() && tmp.level() == g.level())
856  {
857  CanonicalForm Q, R;
858  newtonDivrem (f, tmp, Q, R);
859  if (R.isZero())
860  {
861  newtonDivrem (g, tmp, Q, R);
862  if (R.isZero())
863  {
864  Off (SW_RATIONAL);
865  setReduce (a,true);
866  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
867  TIMING_END_AND_PRINT (alg_termination,
868  "time for successful termination test in alg gcd: ")
869  return tmp*gcdcfcg;
870  }
871  }
872  }
873  else
874 #endif
875 #endif
876  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
877  {
878  Off( SW_RATIONAL );
879  setReduce(a,true);
880  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
881  TIMING_END_AND_PRINT (alg_termination,
882  "time for successful termination test in alg gcd: ")
883  return tmp*gcdcfcg;
884  }
885  TIMING_END_AND_PRINT (alg_termination,
886  "time for unsuccessful termination test in alg gcd: ")
887  Off( SW_RATIONAL );
888  setReduce(a,false); // do not reduce expressions modulo mipo
889  continue;
890  }
891  if( isLess(bound, other, 1, mv) ) // current prime unlucky
892  continue;
893  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
894  q = p;
895  D = mapinto(Dp); // shortcut CRA // shortcut CRA
896  for(int i=1; i<=mv; i++) // tighten bound
897  bound[i] = other[i];
898  }
899  // hopefully, we never reach this point
900  setReduce(a,true);
901  Off( SW_USE_QGCD );
902  D = gcdcfcg*gcd( f, g );
903  On( SW_USE_QGCD );
904  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
905  return D;
906 }
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:654
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
#define D(A)
Definition: gentable.cc:123
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:66
const poly a
Definition: syzextra.cc:212
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)
return P p
Definition: myNF.cc:203
f
Definition: cfModGcd.cc:4022
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
cl
Definition: cfModGcd.cc:4041
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
#define Q
Definition: sirandom.c:25
CanonicalForm Lc(const CanonicalForm &f)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:219
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CanonicalForm lc(const CanonicalForm &f)
bool equal
Definition: cfModGcd.cc:4067
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
bool isLess(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:926
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
const ring R
Definition: DebugPrint.cc:36
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)
Definition: facFqBivar.cc:1809
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
return false
Definition: cfModGcd.cc:84
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
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, satisfying F=G*Q+R, deg(R) < deg(G)
Definition: facMul.cc:342
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
if(topLevel)
Definition: cfGcdAlgExt.cc:73
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:937
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
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
else
Definition: cfGcdAlgExt.cc:193
CanonicalForm mipo
Definition: facAlgExt.cc:57
int gcd(int a, int b)
Definition: walkSupport.cc:839
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
static number Farey(number p, number n, const coeffs)
Definition: flintcf_Q.cc:469
bool isZero(const CFArray &A)
checks if entries of A are zero
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
Definition: cfGcdAlgExt.cc:370
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4042
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:909
const poly b
Definition: syzextra.cc:213
return
Definition: cfGcdAlgExt.cc:216
bool inCoeffDomain() const

§ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( alg_content_p  ) const

compressing two polynomials F and G, M is used for compressing, N to reverse the compression

§ tryBrownGCD()

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

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 370 of file cfGcdAlgExt.cc.

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

§ trycf_content()

static CanonicalForm trycf_content ( const CanonicalForm f,
const CanonicalForm g,
const CanonicalForm M,
bool &  fail 
)
static

Definition at line 1057 of file cfGcdAlgExt.cc.

1058 { // as cf_content, but takes care of zero divisors
1059  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
1060  {
1061  CFIterator i = f;
1062  CanonicalForm tmp = g, result;
1063  while ( i.hasTerms() && ! tmp.isOne() && ! fail )
1064  {
1065  tryBrownGCD( i.coeff(), tmp, M, result, fail );
1066  tmp = result;
1067  i++;
1068  }
1069  return result;
1070  }
1071  return abs( f );
1072 }
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
f
Definition: cfModGcd.cc:4022
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
bool inPolyDomain() const
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
int i
Definition: cfEzgcd.cc:123
bool inExtension() const
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
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
Definition: cfGcdAlgExt.cc:370
return result
Definition: facAbsBiFact.cc:76

§ trycontent()

static CanonicalForm trycontent ( const CanonicalForm f,
const Variable x,
const CanonicalForm M,
bool &  fail 
)
static

Definition at line 1026 of file cfGcdAlgExt.cc.

1027 { // as 'content', but takes care of zero divisors
1028  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
1029  Variable y = f.mvar();
1030  if ( y == x )
1031  return trycf_content( f, 0, M, fail );
1032  if ( y < x )
1033  return f;
1034  return swapvar( trycontent( swapvar( f, y, x ), y, M, fail ), y, x );
1035 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
f
Definition: cfModGcd.cc:4022
factory&#39;s class for variables
Definition: factory.h:115
static CanonicalForm trycf_content(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level() const
Definition: factory.h:132
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
static CanonicalForm trycontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
#define ASSERT(expression, message)
Definition: cf_assert.h:99

§ tryInvert()

void tryInvert ( const CanonicalForm F,
const CanonicalForm M,
CanonicalForm inv,
bool &  fail 
)

Definition at line 219 of file cfGcdAlgExt.cc.

220 { // F, M are required to be "univariate" polynomials in an algebraic variable
221  // we try to invert F modulo M
222  if(F.inBaseDomain())
223  {
224  if(F.isZero())
225  {
226  fail = true;
227  return;
228  }
229  inv = 1/F;
230  return;
231  }
233  Variable a = M.mvar();
234  Variable x = Variable(1);
235  if(!extgcd( replacevar( F, a, x ), replacevar( M, a, x ), inv, b ).isOne())
236  fail = true;
237  else
238  inv = replacevar( inv, x, a ); // change back to alg var
239 }
const poly a
Definition: syzextra.cc:212
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
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
bool inBaseDomain() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
const poly b
Definition: syzextra.cc:213

§ tryNewtonInterp()

static CanonicalForm tryNewtonInterp ( const CanonicalForm alpha,
const CanonicalForm u,
const CanonicalForm newtonPoly,
const CanonicalForm oldInterPoly,
const Variable x,
const CanonicalForm M,
bool &  fail 
)
inlinestatic

Definition at line 355 of file cfGcdAlgExt.cc.

358 {
359  CanonicalForm interPoly;
360 
361  CanonicalForm inv;
362  tryInvert (newtonPoly (alpha, x), M, inv, fail);
363  if (fail)
364  return 0;
365 
366  interPoly= oldInterPoly+reduce ((u - oldInterPoly (alpha, x))*inv*newtonPoly, M);
367  return interPoly;
368 }
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
factory&#39;s main class
Definition: canonicalform.h:75
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:219

§ tryvcontent()

static CanonicalForm tryvcontent ( const CanonicalForm f,
const Variable x,
const CanonicalForm M,
bool &  fail 
)
static

Definition at line 1038 of file cfGcdAlgExt.cc.

1039 { // as vcontent, but takes care of zero divisors
1040  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
1041  if ( f.mvar() <= x )
1042  return trycontent( f, x, M, fail );
1043  CFIterator i;
1044  CanonicalForm d = 0, e, ret;
1045  for ( i = f; i.hasTerms() && ! d.isOne() && ! fail; i++ )
1046  {
1047  e = tryvcontent( i.coeff(), x, M, fail );
1048  if(fail)
1049  break;
1050  tryBrownGCD( d, e, M, ret, fail );
1051  d = ret;
1052  }
1053  return d;
1054 }
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
Definition: factory.h:132
int i
Definition: cfEzgcd.cc:123
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
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
static CanonicalForm trycontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
Variable x
Definition: cfModGcd.cc:4023
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
Definition: cfGcdAlgExt.cc:370
#define ASSERT(expression, message)
Definition: cf_assert.h:99

Variable Documentation

§ both_non_zero

int both_non_zero = 0

Definition at line 68 of file cfGcdAlgExt.cc.

§ both_zero

int both_zero = 0

Definition at line 71 of file cfGcdAlgExt.cc.

§ degsf

degsf = new int [n + 1]

Definition at line 59 of file cfGcdAlgExt.cc.

§ degsg

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

Definition at line 60 of file cfGcdAlgExt.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)
{
M.newpair (Variable (i), Variable (i - both_zero));
N.newpair (Variable (i - both_zero), Variable (i));
}
}
}
}
delete [] degsf
int both_zero
Definition: cfGcdAlgExt.cc:71
factory&#39;s class for variables
Definition: factory.h:115
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
int * degsf
Definition: cfGcdAlgExt.cc:59
int * degsg
Definition: cfGcdAlgExt.cc:60
const CanonicalForm CFMap CFMap & N
Definition: cfGcdAlgExt.cc:55
int i
Definition: cfEzgcd.cc:123

Definition at line 193 of file cfGcdAlgExt.cc.

§ f_zero

int f_zero = 0

Definition at line 69 of file cfGcdAlgExt.cc.

§ G

Definition at line 55 of file cfGcdAlgExt.cc.

§ g_zero

int g_zero = 0

Definition at line 70 of file cfGcdAlgExt.cc.

§ M

Definition at line 55 of file cfGcdAlgExt.cc.

§ N

Definition at line 55 of file cfGcdAlgExt.cc.

§ return

return

Definition at line 216 of file cfGcdAlgExt.cc.

§ topLevel

const CanonicalForm CFMap CFMap bool topLevel
Initial value:
{
int n= tmax (F.level(), G.level())
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:55
int level() const
level() returns the level of CO.

Definition at line 57 of file cfGcdAlgExt.cc.