source:git/factory/facBivar.h@72bfc8

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