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;
154       CanonicalForm tmp2;
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 
306