My Project
facBivar.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facBivar.h
5  *
6  * bivariate factorization over Q(a)
7  *
8  * @author Martin Lee
9  *
10  **/
11 /*****************************************************************************/
12 
13 #ifndef FAC_BIVAR_H
14 #define FAC_BIVAR_H
15 
16 // #include "config.h"
17 
18 #include "cf_assert.h"
19 #include "timing.h"
20 
21 #include "facFqBivarUtil.h"
22 #include "DegreePattern.h"
23 #include "cf_util.h"
24 #include "facFqSquarefree.h"
25 #include "cf_map.h"
26 #include "cf_algorithm.h"
27 #include "cfNewtonPolygon.h"
28 #include "fac_util.h"
29 #include "cf_algorithm.h"
30 
31 TIMING_DEFINE_PRINT(fac_bi_sqrf)
32 TIMING_DEFINE_PRINT(fac_bi_factor_sqrf)
33 
34 /// @return @a biFactorize returns a list of factors of F. If F is not monic
35 /// its leading coefficient is not outputted.
36 CFList
37 biFactorize (const CanonicalForm& F, ///< [in] a sqrfree bivariate poly
38  const Variable& v ///< [in] some algebraic variable
39  );
40 
41 /// factorize a squarefree bivariate polynomial over \f$ Q(\alpha) \f$.
42 ///
43 /// @ return @a ratBiSqrfFactorize returns a list of monic factors, the first
44 /// element is the leading coefficient.
45 inline
46 CFList
47 ratBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
48  const Variable& v= Variable (1) ///< [in] algebraic variable
49  )
50 {
51  CFMap N;
52  CanonicalForm F= compress (G, N);
53  CanonicalForm contentX= content (F, 1); //erwarte hier primitiven input: primitiv über Z bzw. Z[a]
54  CanonicalForm contentY= content (F, 2);
55  F /= (contentX*contentY);
56  CFFList contentXFactors, contentYFactors;
57  if (v.level() != 1)
58  {
59  contentXFactors= factorize (contentX, v);
60  contentYFactors= factorize (contentY, v);
61  }
62  else
63  {
64  contentXFactors= factorize (contentX);
65  contentYFactors= factorize (contentY);
66  }
67  if (contentXFactors.getFirst().factor().inCoeffDomain())
68  contentXFactors.removeFirst();
69  if (contentYFactors.getFirst().factor().inCoeffDomain())
70  contentYFactors.removeFirst();
71  if (F.inCoeffDomain())
72  {
73  CFList result;
74  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
75  result.append (N (i.getItem().factor()));
76  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
77  result.append (N (i.getItem().factor()));
78  if (isOn (SW_RATIONAL))
79  {
80  normalize (result);
81  result.insert (Lc (G));
82  }
83  return result;
84  }
85 
86  mpz_t * M=new mpz_t [4];
87  mpz_init (M[0]);
88  mpz_init (M[1]);
89  mpz_init (M[2]);
90  mpz_init (M[3]);
91 
92  mpz_t * S=new mpz_t [2];
93  mpz_init (S[0]);
94  mpz_init (S[1]);
95 
96  F= compress (F, M, S);
97  CFList result= biFactorize (F, v);
98  for (CFListIterator i= result; i.hasItem(); i++)
99  i.getItem()= N (decompress (i.getItem(), M, S));
100  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
101  result.append (N(i.getItem().factor()));
102  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
103  result.append (N (i.getItem().factor()));
104  if (isOn (SW_RATIONAL))
105  {
106  normalize (result);
107  result.insert (Lc (G));
108  }
109 
110  mpz_clear (M[0]);
111  mpz_clear (M[1]);
112  mpz_clear (M[2]);
113  mpz_clear (M[3]);
114  delete [] M;
115 
116  mpz_clear (S[0]);
117  mpz_clear (S[1]);
118  delete [] S;
119 
120  return result;
121 }
122 
123 /// factorize a bivariate polynomial over \f$ Q(\alpha) \f$
124 ///
125 /// @return @a ratBiFactorize returns a list of monic factors with
126 /// multiplicity, the first element is the leading coefficient.
127 inline
128 CFFList
129 ratBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
130  const Variable& v= Variable (1), ///< [in] algebraic variable
131  bool substCheck= true ///< [in] enables substitute check
132  )
133 {
134  CFMap N;
135  CanonicalForm F= compress (G, N);
136 
137  if (substCheck)
138  {
139  bool foundOne= false;
140  int * substDegree= new int [F.level()];
141  for (int i= 1; i <= F.level(); i++)
142  {
143  substDegree[i-1]= substituteCheck (F, Variable (i));
144  if (substDegree [i-1] > 1)
145  {
146  foundOne= true;
147  subst (F, F, substDegree[i-1], Variable (i));
148  }
149  }
150  if (foundOne)
151  {
152  CFFList result= ratBiFactorize (F, v, false);
153  CFFList newResult, tmp;
155  newResult.insert (result.getFirst());
156  result.removeFirst();
157  for (CFFListIterator i= result; i.hasItem(); i++)
158  {
159  tmp2= i.getItem().factor();
160  for (int j= 1; j <= F.level(); j++)
161  {
162  if (substDegree[j-1] > 1)
163  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
164  }
165  tmp= ratBiFactorize (tmp2, v, false);
166  tmp.removeFirst();
167  for (CFFListIterator j= tmp; j.hasItem(); j++)
168  newResult.append (CFFactor (j.getItem().factor(),
169  j.getItem().exp()*i.getItem().exp()));
170  }
171  decompress (newResult, N);
172  delete [] substDegree;
173  return newResult;
174  }
175  delete [] substDegree;
176  }
177 
178  CanonicalForm LcF= Lc (F);
179  CanonicalForm contentX= content (F, 1);
180  CanonicalForm contentY= content (F, 2);
181  F /= (contentX*contentY);
182  CFFList contentXFactors, contentYFactors;
183  if (v.level() != 1)
184  {
185  contentXFactors= factorize (contentX, v);
186  contentYFactors= factorize (contentY, v);
187  }
188  else
189  {
190  contentXFactors= factorize (contentX);
191  contentYFactors= factorize (contentY);
192  }
193  if (contentXFactors.getFirst().factor().inCoeffDomain())
194  contentXFactors.removeFirst();
195  if (contentYFactors.getFirst().factor().inCoeffDomain())
196  contentYFactors.removeFirst();
197  decompress (contentXFactors, N);
198  decompress (contentYFactors, N);
199  CFFList result, resultRoot;
200  if (F.inCoeffDomain())
201  {
202  result= Union (contentXFactors, contentYFactors);
203  if (isOn (SW_RATIONAL))
204  {
205  normalize (result);
206  if (v.level() == 1)
207  {
208  for (CFFListIterator i= result; i.hasItem(); i++)
209  {
210  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
211  i.getItem()= CFFactor (i.getItem().factor()*
212  bCommonDen(i.getItem().factor()), i.getItem().exp());
213  }
214  }
215  result.insert (CFFactor (LcF, 1));
216  }
217  return result;
218  }
219 
220  mpz_t * M=new mpz_t [4];
221  mpz_init (M[0]);
222  mpz_init (M[1]);
223  mpz_init (M[2]);
224  mpz_init (M[3]);
225 
226  mpz_t * S=new mpz_t [2];
227  mpz_init (S[0]);
228  mpz_init (S[1]);
229 
230  F= compress (F, M, S);
231  TIMING_START (fac_bi_sqrf);
232  CFFList sqrfFactors= sqrFree (F);
233  TIMING_END_AND_PRINT (fac_bi_sqrf,
234  "time for bivariate sqrf factors over Q: ");
235  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
236  {
237  TIMING_START (fac_bi_factor_sqrf);
238  CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
239  TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
240  "time to factor bivariate sqrf factors over Q: ");
241  for (CFListIterator j= tmp; j.hasItem(); j++)
242  {
243  if (j.getItem().inCoeffDomain()) continue;
244  result.append (CFFactor (N (decompress (j.getItem(), M, S)),
245  i.getItem().exp()));
246  }
247  }
248  result= Union (result, contentXFactors);
249  result= Union (result, contentYFactors);
250  if (isOn (SW_RATIONAL))
251  {
252  normalize (result);
253  if (v.level() == 1)
254  {
255  for (CFFListIterator i= result; i.hasItem(); i++)
256  {
257  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
258  i.getItem()= CFFactor (i.getItem().factor()*
259  bCommonDen(i.getItem().factor()), i.getItem().exp());
260  }
261  }
262  result.insert (CFFactor (LcF, 1));
263  }
264 
265  mpz_clear (M[0]);
266  mpz_clear (M[1]);
267  mpz_clear (M[2]);
268  mpz_clear (M[3]);
269  delete [] M;
270 
271  mpz_clear (S[0]);
272  mpz_clear (S[1]);
273  delete [] S;
274 
275  return result;
276 }
277 
278 /// convert a CFFList to a CFList by dropping the multiplicity
279 CFList conv (const CFFList& L ///< [in] a CFFList
280  );
281 
282 /// compute p^k larger than the bound on the coefficients of a factor of @a f
283 /// over Q (mipo)
284 modpk
285 coeffBound (const CanonicalForm & f, ///< [in] poly over Z[a]
286  int p, ///< [in] some positive integer
287  const CanonicalForm& mipo ///< [in] minimal polynomial with
288  ///< denominator 1
289  );
290 
291 /// find a big prime p from our tables such that no term of f vanishes mod p
292 void findGoodPrime(const CanonicalForm &f, ///< [in] poly over Z or Z[a]
293  int &start ///< [in,out] index of big prime in
294  /// cf_primetab.h
295  );
296 
297 /// compute p^k larger than the bound on the coefficients of a factor of @a f
298 /// over Z
299 modpk
300 coeffBound (const CanonicalForm & f, ///< [in] poly over Z
301  int p ///< [in] some positive integer
302  );
303 
304 #endif
305 
This file provides a class to handle degree patterns.
bool isOn(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int i
Definition: cfEzgcd.cc:132
int p
Definition: cfModGcd.cc:4078
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
map polynomials
FILE * f
Definition: checklibs.c:9
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: factory.h:127
int level() const
Definition: factory.h:143
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition: facBivar.cc:188
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)
Definition: facBivar.cc:97
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:47
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition: facBivar.h:129
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
TIMING_DEFINE_PRINT(fac_bi_sqrf) TIMING_DEFINE_PRINT(fac_bi_factor_sqrf) CFList biFactorize(const CanonicalForm &F
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:61
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
This file provides utility functions for bivariate factorization.
CFList tmp2
Definition: facFqBivar.cc:72
This file provides functions for squarefrees factorizing over , or GF.
int j
Definition: facHensel.cc:110
operations mod p^k and some other useful functions for factorization
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define M
Definition: sirandom.c:25
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026