source: git/factory/facBivar.h @ 6e81fc

spielwiese
Last change on this file since 6e81fc was 015711, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: issues with building without NTL
  • Property mode set to 100644
File size: 6.9 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 * @internal @version \$Id$
11 *
12 **/
13/*****************************************************************************/
14
15#ifndef FAC_BIVAR_H
16#define FAC_BIVAR_H
17
18#include <config.h>
19
20#include "assert.h"
21
22#include "facFqBivarUtil.h"
23#include "DegreePattern.h"
24#include "cf_util.h"
25#include "facFqSquarefree.h"
26#include "cf_map.h"
27#include "cfNewtonPolygon.h"
28#include "algext.h"
29#include "fac_util.h"
30
31/// @return @a biFactorize returns a list of factors of F. If F is not monic
32///         its leading coefficient is not outputted.
33CFList
34biFactorize (const CanonicalForm& F,       ///< [in] a bivariate poly
35             const Variable& v             ///< [in] some algebraic variable
36            );
37
38/// factorize a squarefree bivariate polynomial over \f$ Q(\alpha) \f$.
39///
40/// @ return @a ratBiSqrfFactorize returns a list of monic factors, the first
41///         element is the leading coefficient.
42#ifdef HAVE_NTL
43inline
44CFList
45ratBiSqrfFactorize (const CanonicalForm & G,        ///< [in] a bivariate poly
46                    const Variable& v= Variable (1) ///< [in] algebraic variable
47                   )
48{
49  CFMap N;
50  CanonicalForm F= compress (G, N);
51  CanonicalForm contentX= content (F, 1);
52  CanonicalForm contentY= content (F, 2);
53  F /= (contentX*contentY);
54  CFFList contentXFactors, contentYFactors;
55  if (v.level() != 1)
56  {
57    contentXFactors= factorize (contentX, v);
58    contentYFactors= factorize (contentY, v);
59  }
60  else
61  {
62    contentXFactors= factorize (contentX);
63    contentYFactors= factorize (contentY);
64  }
65  if (contentXFactors.getFirst().factor().inCoeffDomain())
66    contentXFactors.removeFirst();
67  if (contentYFactors.getFirst().factor().inCoeffDomain())
68    contentYFactors.removeFirst();
69  if (F.inCoeffDomain())
70  {
71    CFList result;
72    for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
73      result.append (N (i.getItem().factor()));
74    for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
75      result.append (N (i.getItem().factor()));
76    if (isOn (SW_RATIONAL))
77    {
78      normalize (result);
79      result.insert (Lc (G));
80    }
81    return result;
82  }
83  mat_ZZ M;
84  vec_ZZ S;
85  F= compress (F, M, S);
86  CFList result= biFactorize (F, v);
87  for (CFListIterator i= result; i.hasItem(); i++)
88    i.getItem()= N (decompress (i.getItem(), M, S));
89  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
90    result.append (N(i.getItem().factor()));
91  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
92    result.append (N (i.getItem().factor()));
93  if (isOn (SW_RATIONAL))
94  {
95    normalize (result);
96    result.insert (Lc (G));
97  }
98  return result;
99}
100
101/// factorize a bivariate polynomial over \f$ Q(\alpha) \f$
102///
103/// @return @a ratBiFactorize returns a list of monic factors with
104///         multiplicity, the first element is the leading coefficient.
105inline
106CFFList
107ratBiFactorize (const CanonicalForm & G,         ///< [in] a bivariate poly
108                const Variable& v= Variable (1), ///< [in] algebraic variable
109                bool substCheck= true        ///< [in] enables substitute check
110               )
111{
112  CFMap N;
113  CanonicalForm F= compress (G, N);
114
115  if (substCheck)
116  {
117    bool foundOne= false;
118    int * substDegree= new int [F.level()];
119    for (int i= 1; i <= F.level(); i++)
120    {
121      substDegree[i-1]= substituteCheck (F, Variable (i));
122      if (substDegree [i-1] > 1)
123      {
124        foundOne= true;
125        subst (F, F, substDegree[i-1], Variable (i));
126      }
127    }
128    if (foundOne)
129    {
130      CFFList result= ratBiFactorize (F, v, false);
131      CFFList newResult, tmp;
132      CanonicalForm tmp2;
133      newResult.insert (result.getFirst());
134      result.removeFirst();
135      for (CFFListIterator i= result; i.hasItem(); i++)
136      {
137        tmp2= i.getItem().factor();
138        for (int j= 1; j <= F.level(); j++)
139        {
140          if (substDegree[j-1] > 1)
141            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
142        }
143        tmp= ratBiFactorize (tmp2, v, false);
144        tmp.removeFirst();
145        for (CFFListIterator j= tmp; j.hasItem(); j++)
146          newResult.append (CFFactor (j.getItem().factor(),
147                                      j.getItem().exp()*i.getItem().exp()));
148      }
149      decompress (newResult, N);
150      delete [] substDegree;
151      return newResult;
152    }
153    delete [] substDegree;
154  }
155
156  CanonicalForm LcF= Lc (F);
157  CanonicalForm contentX= content (F, 1);
158  CanonicalForm contentY= content (F, 2);
159  F /= (contentX*contentY);
160  CFFList contentXFactors, contentYFactors;
161  if (v.level() != 1)
162  {
163    contentXFactors= factorize (contentX, v);
164    contentYFactors= factorize (contentY, v);
165  }
166  else
167  {
168    contentXFactors= factorize (contentX);
169    contentYFactors= factorize (contentY);
170  }
171  if (contentXFactors.getFirst().factor().inCoeffDomain())
172    contentXFactors.removeFirst();
173  if (contentYFactors.getFirst().factor().inCoeffDomain())
174    contentYFactors.removeFirst();
175  decompress (contentXFactors, N);
176  decompress (contentYFactors, N);
177  CFFList result, resultRoot;
178  if (F.inCoeffDomain())
179  {
180    result= Union (contentXFactors, contentYFactors);
181    if (isOn (SW_RATIONAL))
182    {
183      normalize (result);
184      if (v.level() == 1)
185      {
186        for (CFFListIterator i= result; i.hasItem(); i++)
187        {
188          LcF /= bCommonDen (i.getItem().factor());
189          i.getItem()= CFFactor (i.getItem().factor()*
190                       bCommonDen(i.getItem().factor()), i.getItem().exp());
191        }
192      }
193      result.insert (CFFactor (LcF, 1));
194    }
195    return result;
196  }
197  mat_ZZ M;
198  vec_ZZ S;
199  F= compress (F, M, S);
200  CFFList sqrfFactors= sqrFree (F);
201  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
202  {
203    CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
204    for (CFListIterator j= tmp; j.hasItem(); j++)
205    {
206      if (j.getItem().inCoeffDomain()) continue;
207      result.append (CFFactor (N (decompress (j.getItem(), M, S)),
208                               i.getItem().exp()));
209    }
210  }
211  result= Union (result, contentXFactors);
212  result= Union (result, contentYFactors);
213  if (isOn (SW_RATIONAL))
214  {
215    normalize (result);
216    if (v.level() == 1)
217    {
218      for (CFFListIterator i= result; i.hasItem(); i++)
219      {
220        LcF /= bCommonDen (i.getItem().factor());
221        i.getItem()= CFFactor (i.getItem().factor()*
222                     bCommonDen(i.getItem().factor()), i.getItem().exp());
223      }
224    }
225    result.insert (CFFactor (LcF, 1));
226  }
227  return result;
228}
229
230#endif
231
232/// convert a CFFList to a CFList by dropping the multiplicity
233CFList conv (const CFFList& L ///< [in] a CFFList
234            );
235
236modpk
237coeffBound ( const CanonicalForm & f, int p, const CanonicalForm& mipo );
238
239void findGoodPrime(const CanonicalForm &f, int &start);
240
241modpk
242coeffBound ( const CanonicalForm & f, int p );
243
244#endif
245
Note: See TracBrowser for help on using the repository browser.