# source:git/factory/facBivar.h@2fbb9e6

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