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

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