# source:git/factory/facBivar.h@17a710

spielwiese
Last change on this file since 17a710 was 17a710, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: debug output and experimental code
• Property mode set to 100644
File size: 7.4 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 "cfNewtonPolygon.h"
27#include "algext.h"
28#include "fac_util.h"
29
30TIMING_DEFINE_PRINT(fac_bi_sqrf)
31TIMING_DEFINE_PRINT(fac_bi_factor_sqrf)
32
33/// @return @a biFactorize returns a list of factors of F. If F is not monic
34///         its leading coefficient is not outputted.
35CFList
36biFactorize (const CanonicalForm& F,       ///< [in] a bivariate poly
37             const Variable& v             ///< [in] some algebraic variable
38            );
39
40/// factorize a squarefree bivariate polynomial over \f$Q(\alpha) \f$.
41///
42/// @ return @a ratBiSqrfFactorize returns a list of monic factors, the first
43///         element is the leading coefficient.
44#ifdef HAVE_NTL
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  mat_ZZ M;
86  vec_ZZ S;
87  F= compress (F, M, S);
88  CFList result= biFactorize (F, v);
89  for (CFListIterator i= result; i.hasItem(); i++)
90    i.getItem()= N (decompress (i.getItem(), M, S));
91  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
92    result.append (N(i.getItem().factor()));
93  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
94    result.append (N (i.getItem().factor()));
95  if (isOn (SW_RATIONAL))
96  {
97    normalize (result);
98    result.insert (Lc (G));
99  }
100  return result;
101}
102
103/// factorize a bivariate polynomial over \f$Q(\alpha) \f$
104///
105/// @return @a ratBiFactorize returns a list of monic factors with
106///         multiplicity, the first element is the leading coefficient.
107inline
108CFFList
109ratBiFactorize (const CanonicalForm & G,         ///< [in] a bivariate poly
110                const Variable& v= Variable (1), ///< [in] algebraic variable
111                bool substCheck= true        ///< [in] enables substitute check
112               )
113{
114  CFMap N;
115  CanonicalForm F= compress (G, N);
116
117  if (substCheck)
118  {
119    bool foundOne= false;
120    int * substDegree= new int [F.level()];
121    for (int i= 1; i <= F.level(); i++)
122    {
123      substDegree[i-1]= substituteCheck (F, Variable (i));
124      if (substDegree [i-1] > 1)
125      {
126        foundOne= true;
127        subst (F, F, substDegree[i-1], Variable (i));
128      }
129    }
130    if (foundOne)
131    {
132      CFFList result= ratBiFactorize (F, v, false);
133      CFFList newResult, tmp;
134      CanonicalForm tmp2;
135      newResult.insert (result.getFirst());
136      result.removeFirst();
137      for (CFFListIterator i= result; i.hasItem(); i++)
138      {
139        tmp2= i.getItem().factor();
140        for (int j= 1; j <= F.level(); j++)
141        {
142          if (substDegree[j-1] > 1)
143            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
144        }
145        tmp= ratBiFactorize (tmp2, v, false);
146        tmp.removeFirst();
147        for (CFFListIterator j= tmp; j.hasItem(); j++)
148          newResult.append (CFFactor (j.getItem().factor(),
149                                      j.getItem().exp()*i.getItem().exp()));
150      }
151      decompress (newResult, N);
152      delete [] substDegree;
153      return newResult;
154    }
155    delete [] substDegree;
156  }
157
158  CanonicalForm LcF= Lc (F);
159  CanonicalForm contentX= content (F, 1);
160  CanonicalForm contentY= content (F, 2);
161  F /= (contentX*contentY);
162  CFFList contentXFactors, contentYFactors;
163  if (v.level() != 1)
164  {
165    contentXFactors= factorize (contentX, v);
166    contentYFactors= factorize (contentY, v);
167  }
168  else
169  {
170    contentXFactors= factorize (contentX);
171    contentYFactors= factorize (contentY);
172  }
173  if (contentXFactors.getFirst().factor().inCoeffDomain())
174    contentXFactors.removeFirst();
175  if (contentYFactors.getFirst().factor().inCoeffDomain())
176    contentYFactors.removeFirst();
177  decompress (contentXFactors, N);
178  decompress (contentYFactors, N);
179  CFFList result, resultRoot;
180  if (F.inCoeffDomain())
181  {
182    result= Union (contentXFactors, contentYFactors);
183    if (isOn (SW_RATIONAL))
184    {
185      normalize (result);
186      if (v.level() == 1)
187      {
188        for (CFFListIterator i= result; i.hasItem(); i++)
189        {
190          LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
191          i.getItem()= CFFactor (i.getItem().factor()*
192                       bCommonDen(i.getItem().factor()), i.getItem().exp());
193        }
194      }
195      result.insert (CFFactor (LcF, 1));
196    }
197    return result;
198  }
199  mat_ZZ M;
200  vec_ZZ S;
201  F= compress (F, M, S);
202  TIMING_START (fac_bi_sqrf);
203  CFFList sqrfFactors= sqrFree (F);
204  TIMING_END_AND_PRINT (fac_bi_sqrf,
205                       "time for bivariate sqrf factors over Q: ");
206  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
207  {
208    TIMING_START (fac_bi_factor_sqrf);
209    CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
210    TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
211                          "time to factor bivariate sqrf factors over Q: ");
212    for (CFListIterator j= tmp; j.hasItem(); j++)
213    {
214      if (j.getItem().inCoeffDomain()) continue;
215      result.append (CFFactor (N (decompress (j.getItem(), M, S)),
216                               i.getItem().exp()));
217    }
218  }
219  result= Union (result, contentXFactors);
220  result= Union (result, contentYFactors);
221  if (isOn (SW_RATIONAL))
222  {
223    normalize (result);
224    if (v.level() == 1)
225    {
226      for (CFFListIterator i= result; i.hasItem(); i++)
227      {
228        LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
229        i.getItem()= CFFactor (i.getItem().factor()*
230                     bCommonDen(i.getItem().factor()), i.getItem().exp());
231      }
232    }
233    result.insert (CFFactor (LcF, 1));
234  }
235  return result;
236}
237
238#endif
239
240/// convert a CFFList to a CFList by dropping the multiplicity
241CFList conv (const CFFList& L ///< [in] a CFFList
242            );
243
244modpk
245coeffBound ( const CanonicalForm & f, int p, const CanonicalForm& mipo );
246
247void findGoodPrime(const CanonicalForm &f, int &start);
248
249modpk
250coeffBound ( const CanonicalForm & f, int p );
251
252#endif
253
Note: See TracBrowser for help on using the repository browser.