source: git/factory/facBivar.h

spielwiese
Last change on this file was 1e9197, checked in by Hans Schoenemann <hannes@…>, 3 years ago
factorization (multivariate) over Zp(a) via FLINT 2.7.0
  • Property mode set to 100644
File size: 8.7 KB
Line 
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
31TIMING_DEFINE_PRINT(fac_bi_sqrf)
32TIMING_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.
36CFList
37biFactorize (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.
45inline
46CFList
47ratBiSqrfFactorize (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.
127inline
128CFFList
129ratBiFactorize (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
279CFList 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)
284modpk
285coeffBound (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
292void 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
299modpk
300coeffBound (const CanonicalForm & f, ///< [in] poly over Z
301            int p                    ///< [in] some positive integer
302           );
303
304#endif
305
Note: See TracBrowser for help on using the repository browser.