# source:git/factory/facBivar.h@530295

spielwiese
Last change on this file since 530295 was 530295, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: more changes to replace polynomial factorization over integer with new algorithm
• Property mode set to 100644
File size: 6.1 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  CFList result= biFactorize (F, v);
86  for (CFListIterator i= result; i.hasItem(); i++)
87    i.getItem()= N (decompress (i.getItem(), M, S));
88  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
89    result.append (N(i.getItem().factor()));
90  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
91    result.append (N (i.getItem().factor()));
92  if (isOn (SW_RATIONAL))
93  {
94    normalize (result);
95    result.insert (Lc (G));
96  }
97  return result;
98}
99
100/// factorize a bivariate polynomial over \f$Q(\alpha) \f$
101///
102/// @return @a ratBiFactorize returns a list of monic factors with
103///         multiplicity, the first element is the leading coefficient.
104inline
105CFFList
106ratBiFactorize (const CanonicalForm & G,         ///< [in] a bivariate poly
107                const Variable& v= Variable (1), ///< [in] algebraic variable
108                bool substCheck= true        ///< [in] enables substitute check
109               )
110{
111  CFMap N;
112  CanonicalForm F= compress (G, N);
113
114  if (substCheck)
115  {
116    bool foundOne= false;
117    int * substDegree= new int [F.level()];
118    for (int i= 1; i <= F.level(); i++)
119    {
120      substDegree[i-1]= substituteCheck (F, Variable (i));
121      if (substDegree [i-1] > 1)
122      {
123        foundOne= true;
124        subst (F, F, substDegree[i-1], Variable (i));
125      }
126    }
127    if (foundOne)
128    {
129      CFFList result= ratBiFactorize (F, v, false);
130      CFFList newResult, tmp;
131      CanonicalForm tmp2;
132      newResult.insert (result.getFirst());
133      result.removeFirst();
134      for (CFFListIterator i= result; i.hasItem(); i++)
135      {
136        tmp2= i.getItem().factor();
137        for (int j= 1; j <= F.level(); j++)
138        {
139          if (substDegree[j-1] > 1)
140            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
141        }
142        tmp= ratBiFactorize (tmp2, v, false);
143        tmp.removeFirst();
144        for (CFFListIterator j= tmp; j.hasItem(); j++)
145          newResult.append (CFFactor (j.getItem().factor(),
146                                      j.getItem().exp()*i.getItem().exp()));
147      }
148      decompress (newResult, N);
149      delete [] substDegree;
150      return newResult;
151    }
152    delete [] substDegree;
153  }
154
155  CanonicalForm LcF= Lc (F);
156  CanonicalForm contentX= content (F, 1);
157  CanonicalForm contentY= content (F, 2);
158  F /= (contentX*contentY);
159  CFFList contentXFactors, contentYFactors;
160  if (v.level() != 1)
161  {
162    contentXFactors= factorize (contentX, v);
163    contentYFactors= factorize (contentY, v);
164  }
165  else
166  {
167    contentXFactors= factorize (contentX);
168    contentYFactors= factorize (contentY);
169  }
170  if (contentXFactors.getFirst().factor().inCoeffDomain())
171    contentXFactors.removeFirst();
172  if (contentYFactors.getFirst().factor().inCoeffDomain())
173    contentYFactors.removeFirst();
174  decompress (contentXFactors, N);
175  decompress (contentYFactors, N);
176  CFFList result, resultRoot;
177  if (F.inCoeffDomain())
178  {
179    result= Union (contentXFactors, contentYFactors);
180    if (isOn (SW_RATIONAL))
181    {
182      normalize (result);
183      result.insert (CFFactor (LcF, 1));
184    }
185    return result;
186  }
187  mat_ZZ M;
188  vec_ZZ S;
189  F= compress (F, M, S);
190  CFFList sqrfFactors= sqrFree (F);
191  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
192  {
193    CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
194    for (CFListIterator j= tmp; j.hasItem(); j++)
195    {
196      if (j.getItem().inCoeffDomain()) continue;
197      result.append (CFFactor (N (decompress (j.getItem(), M, S)), i.getItem().exp()));
198    }
199  }
200  result= Union (result, contentXFactors);
201  result= Union (result, contentYFactors);
202  if (isOn (SW_RATIONAL))
203  {
204    normalize (result);
205    result.insert (CFFactor (LcF, 1));
206  }
207  return result;
208}
209
210#endif
211
212/// convert a CFFList to a CFList by dropping the multiplicity
213CFList conv (const CFFList& L ///< [in] a CFFList
214            );
215
216#endif
217
Note: See TracBrowser for help on using the repository browser.