Functions | Variables
facBivar.h File Reference

bivariate factorization over Q(a) More...

#include "cf_assert.h"
#include "timing.h"
#include "facFqBivarUtil.h"
#include "DegreePattern.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "cf_map.h"
#include "cfNewtonPolygon.h"
#include "fac_util.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_bi_sqrf) TIMING_DEFINE_PRINT(fac_bi_factor_sqrf) CFList biFactorize(const CanonicalForm &F
 
CFList ratBiSqrfFactorize (const CanonicalForm &G, const Variable &v=Variable(1))
 factorize a squarefree bivariate polynomial over $ Q(\alpha) $. More...
 
CFFList ratBiFactorize (const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
 factorize a bivariate polynomial over $ Q(\alpha) $ More...
 
CFList conv (const CFFList &L)
 convert a CFFList to a CFList by dropping the multiplicity More...
 
modpk coeffBound (const CanonicalForm &f, int p, const CanonicalForm &mipo)
 compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo) More...
 
void findGoodPrime (const CanonicalForm &f, int &start)
 find a big prime p from our tables such that no term of f vanishes mod p More...
 
modpk coeffBound (const CanonicalForm &f, int p)
 compute p^k larger than the bound on the coefficients of a factor of f over Z More...
 

Variables

const Variablev
 < [in] a sqrfree bivariate poly More...
 

Detailed Description

bivariate factorization over Q(a)

Author
Martin Lee

Definition in file facBivar.h.

Function Documentation

modpk coeffBound ( const CanonicalForm f,
int  p,
const CanonicalForm mipo 
)

compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)

Parameters
[in]fpoly over Z[a]
[in]psome positive integer
[in]mipominimal polynomial with denominator 1

Definition at line 96 of file facBivar.cc.

97 {
98  int * degs = degrees( f );
99  int M = 0, i, k = f.level();
100  CanonicalForm K= 1;
101  for ( i = 1; i <= k; i++ )
102  {
103  M += degs[i];
104  K *= degs[i] + 1;
105  }
106  K /= power (CanonicalForm (2), k/2);
107  K *= power (CanonicalForm (2), M);
108  int N= degree (mipo);
110  b= 2*power (maxNorm (f), N)*power (maxNorm (mipo), 4*N)*K*
111  power (CanonicalForm (2), N)*
112  power (CanonicalForm (N+1), 4*N);
113  b /= power (abs (lc (mipo)), N);
114 
115  CanonicalForm B = p;
116  k = 1;
117  while ( B < b ) {
118  B *= p;
119  k++;
120  }
121  return modpk( p, k );
122 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
factory's main class
Definition: canonicalform.h:75
int i
Definition: facBivar.cc:41
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
int level() const
level() returns the level of CO.
CanonicalForm lc(const CanonicalForm &f)
return modpk(p, k)
int p
Definition: facBivar.cc:39
CanonicalForm b
Definition: facBivar.cc:42
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int M
Definition: facBivar.cc:41
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
b *CanonicalForm B
Definition: facBivar.cc:51
int degree(const CanonicalForm &f)
int k
Definition: facBivar.cc:41
modpk coeffBound ( const CanonicalForm f,
int  p 
)

compute p^k larger than the bound on the coefficients of a factor of f over Z

Parameters
[in]fpoly over Z
[in]psome positive integer
CFList conv ( const CFFList L)

convert a CFFList to a CFList by dropping the multiplicity

Parameters
[in]La CFFList

Definition at line 124 of file facBivar.cc.

125 {
126  CFList result;
127  for (CFFListIterator i= L; i.hasItem(); i++)
128  result.append (i.getItem().factor());
129  return result;
130 }
int i
Definition: facBivar.cc:41
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76
void findGoodPrime ( const CanonicalForm f,
int &  start 
)

find a big prime p from our tables such that no term of f vanishes mod p

Parameters
[in]fpoly over Z or Z[a]
[in,out]startindex of big prime in cf_primetab.h

Definition at line 60 of file facBivar.cc.

61 {
62  if (! f.inBaseDomain() )
63  {
64  CFIterator i = f;
65  for(;;)
66  {
67  if ( i.hasTerms() )
68  {
69  findGoodPrime(i.coeff(),start);
70  if (0==cf_getBigPrime(start)) return;
71  if((i.exp()!=0) && ((i.exp() % cf_getBigPrime(start))==0))
72  {
73  start++;
74  i=f;
75  }
76  else i++;
77  }
78  else break;
79  }
80  }
81  else
82  {
83  if (f.inZ())
84  {
85  if (0==cf_getBigPrime(start)) return;
86  while((!f.isZero()) && (mod(f,cf_getBigPrime(start))==0))
87  {
88  start++;
89  if (0==cf_getBigPrime(start)) return;
90  }
91  }
92  }
93 }
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int i
Definition: facBivar.cc:41
bool inZ() const
predicates
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
FILE * f
Definition: checklibs.c:7
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
Definition: facBivar.cc:60
bool inBaseDomain() const
CFFList ratBiFactorize ( const CanonicalForm G,
const Variable v = Variable (1),
bool  substCheck = true 
)
inline

factorize a bivariate polynomial over $ Q(\alpha) $

Returns
ratBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
Parameters
[in]Ga bivariate poly
[in]valgebraic variable
[in]substCheckenables substitute check

Definition at line 128 of file facBivar.h.

132 {
133  CFMap N;
134  CanonicalForm F= compress (G, N);
135 
136  if (substCheck)
137  {
138  bool foundOne= false;
139  int * substDegree= new int [F.level()];
140  for (int i= 1; i <= F.level(); i++)
141  {
142  substDegree[i-1]= substituteCheck (F, Variable (i));
143  if (substDegree [i-1] > 1)
144  {
145  foundOne= true;
146  subst (F, F, substDegree[i-1], Variable (i));
147  }
148  }
149  if (foundOne)
150  {
151  CFFList result= ratBiFactorize (F, v, false);
152  CFFList newResult, tmp;
154  newResult.insert (result.getFirst());
155  result.removeFirst();
156  for (CFFListIterator i= result; i.hasItem(); i++)
157  {
158  tmp2= i.getItem().factor();
159  for (int j= 1; j <= F.level(); j++)
160  {
161  if (substDegree[j-1] > 1)
162  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
163  }
164  tmp= ratBiFactorize (tmp2, v, false);
165  tmp.removeFirst();
166  for (CFFListIterator j= tmp; j.hasItem(); j++)
167  newResult.append (CFFactor (j.getItem().factor(),
168  j.getItem().exp()*i.getItem().exp()));
169  }
170  decompress (newResult, N);
171  delete [] substDegree;
172  return newResult;
173  }
174  delete [] substDegree;
175  }
176 
177  CanonicalForm LcF= Lc (F);
178  CanonicalForm contentX= content (F, 1);
179  CanonicalForm contentY= content (F, 2);
180  F /= (contentX*contentY);
181  CFFList contentXFactors, contentYFactors;
182  if (v.level() != 1)
183  {
184  contentXFactors= factorize (contentX, v);
185  contentYFactors= factorize (contentY, v);
186  }
187  else
188  {
189  contentXFactors= factorize (contentX);
190  contentYFactors= factorize (contentY);
191  }
192  if (contentXFactors.getFirst().factor().inCoeffDomain())
193  contentXFactors.removeFirst();
194  if (contentYFactors.getFirst().factor().inCoeffDomain())
195  contentYFactors.removeFirst();
196  decompress (contentXFactors, N);
197  decompress (contentYFactors, N);
198  CFFList result, resultRoot;
199  if (F.inCoeffDomain())
200  {
201  result= Union (contentXFactors, contentYFactors);
202  if (isOn (SW_RATIONAL))
203  {
204  normalize (result);
205  if (v.level() == 1)
206  {
207  for (CFFListIterator i= result; i.hasItem(); i++)
208  {
209  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
210  i.getItem()= CFFactor (i.getItem().factor()*
211  bCommonDen(i.getItem().factor()), i.getItem().exp());
212  }
213  }
214  result.insert (CFFactor (LcF, 1));
215  }
216  return result;
217  }
218 
219  mpz_t * M=new mpz_t [4];
220  mpz_init (M[0]);
221  mpz_init (M[1]);
222  mpz_init (M[2]);
223  mpz_init (M[3]);
224 
225  mpz_t * S=new mpz_t [2];
226  mpz_init (S[0]);
227  mpz_init (S[1]);
228 
229  F= compress (F, M, S);
230  TIMING_START (fac_bi_sqrf);
231  CFFList sqrfFactors= sqrFree (F);
232  TIMING_END_AND_PRINT (fac_bi_sqrf,
233  "time for bivariate sqrf factors over Q: ");
234  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
235  {
236  TIMING_START (fac_bi_factor_sqrf);
237  CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
238  TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
239  "time to factor bivariate sqrf factors over Q: ");
240  for (CFListIterator j= tmp; j.hasItem(); j++)
241  {
242  if (j.getItem().inCoeffDomain()) continue;
243  result.append (CFFactor (N (decompress (j.getItem(), M, S)),
244  i.getItem().exp()));
245  }
246  }
247  result= Union (result, contentXFactors);
248  result= Union (result, contentYFactors);
249  if (isOn (SW_RATIONAL))
250  {
251  normalize (result);
252  if (v.level() == 1)
253  {
254  for (CFFListIterator i= result; i.hasItem(); i++)
255  {
256  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
257  i.getItem()= CFFactor (i.getItem().factor()*
258  bCommonDen(i.getItem().factor()), i.getItem().exp());
259  }
260  }
261  result.insert (CFFactor (LcF, 1));
262  }
263 
264  mpz_clear (M[0]);
265  mpz_clear (M[1]);
266  mpz_clear (M[2]);
267  mpz_clear (M[3]);
268  delete [] M;
269 
270  mpz_clear (S[0]);
271  mpz_clear (S[1]);
272  delete [] S;
273 
274  return result;
275 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int level() const
Definition: variable.h:49
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1028
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition: facBivar.h:128
bool inCoeffDomain() const
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory's class for variables
Definition: variable.h:32
factory's main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int level() const
level() returns the level of CO.
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
T getFirst() const
Definition: ftmpl_list.cc:279
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
class CFMap
Definition: cf_map.h:84
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:46
Factor< CanonicalForm > CFFactor
#define TIMING_START(t)
Definition: timing.h:87
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
void append(const T &)
Definition: ftmpl_list.cc:256
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
return result
Definition: facAbsBiFact.cc:76
CFList ratBiSqrfFactorize ( const CanonicalForm G,
const Variable v = Variable (1) 
)
inline

factorize a squarefree bivariate polynomial over $ Q(\alpha) $.

@ return ratBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

Parameters
[in]Ga bivariate poly
[in]valgebraic variable

Definition at line 46 of file facBivar.h.

49 {
50  CFMap N;
51  CanonicalForm F= compress (G, N);
52  CanonicalForm contentX= content (F, 1); //erwarte hier primitiven input: primitiv über Z bzw. Z[a]
53  CanonicalForm contentY= content (F, 2);
54  F /= (contentX*contentY);
55  CFFList contentXFactors, contentYFactors;
56  if (v.level() != 1)
57  {
58  contentXFactors= factorize (contentX, v);
59  contentYFactors= factorize (contentY, v);
60  }
61  else
62  {
63  contentXFactors= factorize (contentX);
64  contentYFactors= factorize (contentY);
65  }
66  if (contentXFactors.getFirst().factor().inCoeffDomain())
67  contentXFactors.removeFirst();
68  if (contentYFactors.getFirst().factor().inCoeffDomain())
69  contentYFactors.removeFirst();
70  if (F.inCoeffDomain())
71  {
72  CFList result;
73  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
74  result.append (N (i.getItem().factor()));
75  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
76  result.append (N (i.getItem().factor()));
77  if (isOn (SW_RATIONAL))
78  {
79  normalize (result);
80  result.insert (Lc (G));
81  }
82  return result;
83  }
84 
85  mpz_t * M=new mpz_t [4];
86  mpz_init (M[0]);
87  mpz_init (M[1]);
88  mpz_init (M[2]);
89  mpz_init (M[3]);
90 
91  mpz_t * S=new mpz_t [2];
92  mpz_init (S[0]);
93  mpz_init (S[1]);
94 
95  F= compress (F, M, S);
96  CFList result= biFactorize (F, v);
97  for (CFListIterator i= result; i.hasItem(); i++)
98  i.getItem()= N (decompress (i.getItem(), M, S));
99  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
100  result.append (N(i.getItem().factor()));
101  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
102  result.append (N (i.getItem().factor()));
103  if (isOn (SW_RATIONAL))
104  {
105  normalize (result);
106  result.insert (Lc (G));
107  }
108 
109  mpz_clear (M[0]);
110  mpz_clear (M[1]);
111  mpz_clear (M[2]);
112  mpz_clear (M[3]);
113  delete [] M;
114 
115  mpz_clear (S[0]);
116  mpz_clear (S[1]);
117  delete [] S;
118 
119  return result;
120 }
int level() const
Definition: variable.h:49
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1028
bool inCoeffDomain() const
factory's main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
T getFirst() const
Definition: ftmpl_list.cc:279
int i
Definition: cfEzgcd.cc:123
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition: facBivar.cc:185
class CFMap
Definition: cf_map.h:84
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76
TIMING_DEFINE_PRINT ( fac_bi_sqrf  ) const
Returns
biFactorize returns a list of factors of F. If F is not monic its leading coefficient is not outputted.

Variable Documentation

< [in] a sqrfree bivariate poly

< [in] some algebraic variable

Definition at line 37 of file facBivar.h.