My Project  debian-1:4.1.2-p1+ds-2
facFactorize.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFactorize.h
5  *
6  * multivariate factorization over Q(a)
7  *
8  * @author Martin Lee
9  *
10  **/
11 /*****************************************************************************/
12 
13 #ifndef FAC_FACTORIZE_H
14 #define FAC_FACTORIZE_H
15 
16 // #include "config.h"
17 #include "timing.h"
18 
19 #include "facBivar.h"
20 #include "facFqBivarUtil.h"
21 
22 TIMING_DEFINE_PRINT (fac_squarefree)
23 TIMING_DEFINE_PRINT (fac_factor_squarefree)
24 
25 /// Factorization of A wrt. to different second vars
26 void
28  const CanonicalForm& A, ///<[in] poly
29  CFList*& Aeval, ///<[in,out] A evaluated wrt.
30  ///< different second vars
31  ///< returns bivariate factors
32  int& minFactorsLength, ///<[in,out] minimal length of
33  ///< bivariate factors
34  bool& irred, ///<[in,out] Is A irreducible?
35  const Variable& w ///<[in] alg. variable
36  );
37 
38 /// Factorization over Q (a)
39 ///
40 /// @return @a multiFactorize returns a factorization of F
41 CFList
42 multiFactorize (const CanonicalForm& F, ///< [in] sqrfree poly
43  const Variable& v ///< [in] some algebraic variable
44  );
45 
46 /// factorize a squarefree multivariate polynomial over \f$ Q(\alpha) \f$
47 ///
48 /// @return @a ratSqrfFactorize returns a list of monic factors, the first
49 /// element is the leading coefficient.
50 #ifdef HAVE_NTL
51 inline
52 CFList
53 ratSqrfFactorize (const CanonicalForm & G, ///<[in] a multivariate poly
54  const Variable& v= Variable (1) ///<[in] algebraic variable
55  )
56 {
57  if (getNumVars (G) == 2)
58  return ratBiSqrfFactorize (G, v);
59  CanonicalForm F= G;
60  if (isOn (SW_RATIONAL))
61  F *= bCommonDen (F);
63  if (isOn (SW_RATIONAL))
64  {
65  normalize (result);
66  result.insert (Lc(F));
67  }
68  return result;
69 }
70 
71 /// factorize a multivariate polynomial over \f$ Q(\alpha) \f$
72 ///
73 /// @return @a ratFactorize returns a list of monic factors with
74 /// multiplicity, the first element is the leading coefficient.
75 inline
76 CFFList
77 ratFactorize (const CanonicalForm& G, ///<[in] a multivariate poly
78  const Variable& v= Variable (1), ///<[in] algebraic variable
79  bool substCheck= true ///<[in] enables substitute check
80  )
81 {
82  if (getNumVars (G) == 2)
83  {
85  return result;
86  }
87  CanonicalForm F= G;
88 
89  if (substCheck)
90  {
91  bool foundOne= false;
92  int * substDegree= new int [F.level()];
93  for (int i= 1; i <= F.level(); i++)
94  {
95  if (degree (F, i) > 0)
96  {
97  substDegree[i-1]= substituteCheck (F, Variable (i));
98  if (substDegree [i-1] > 1)
99  {
100  foundOne= true;
101  subst (F, F, substDegree[i-1], Variable (i));
102  }
103  }
104  else
105  substDegree[i-1]= -1;
106  }
107  if (foundOne)
108  {
109  CFFList result= ratFactorize (F, v, false);
110  CFFList newResult, tmp;
112  newResult.insert (result.getFirst());
113  result.removeFirst();
114  for (CFFListIterator i= result; i.hasItem(); i++)
115  {
116  tmp2= i.getItem().factor();
117  for (int j= 1; j <= G.level(); j++)
118  {
119  if (substDegree[j-1] > 1)
120  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
121  }
122  tmp= ratFactorize (tmp2, v, false);
123  tmp.removeFirst();
124  for (CFFListIterator j= tmp; j.hasItem(); j++)
125  newResult.append (CFFactor (j.getItem().factor(),
126  j.getItem().exp()*i.getItem().exp()));
127  }
128  delete [] substDegree;
129  return newResult;
130  }
131  delete [] substDegree;
132  }
133 
134  CanonicalForm LcF= Lc (F);
135  if (isOn (SW_RATIONAL))
136  F *= bCommonDen (F);
137 
138  CFFList result;
139  TIMING_START (fac_squarefree);
140  CFFList sqrfFactors= sqrFree (F);
141  TIMING_END_AND_PRINT (fac_squarefree,
142  "time for squarefree factorization over Q: ");
143 
144  CFList tmp;
145  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
146  {
147  TIMING_START (fac_factor_squarefree);
148  tmp= ratSqrfFactorize (i.getItem().factor(), v);
149  TIMING_END_AND_PRINT (fac_factor_squarefree,
150  "time to factorize sqrfree factor over Q: ");
151  for (CFListIterator j= tmp; j.hasItem(); j++)
152  {
153  if (j.getItem().inCoeffDomain()) continue;
154  result.append (CFFactor (j.getItem(), i.getItem().exp()));
155  }
156  }
157  if (isOn (SW_RATIONAL))
158  {
159  normalize (result);
160  if (v.level() == 1)
161  {
162  for (CFFListIterator i= result; i.hasItem(); i++)
163  {
164  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
165  i.getItem()= CFFactor (i.getItem().factor()*
166  bCommonDen(i.getItem().factor()), i.getItem().exp());
167  }
168  }
169  result.insert (CFFactor (LcF, 1));
170  }
171  return result;
172 }
173 #endif
174 
175 #endif
176 
bool isOn(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int degree(const CanonicalForm &f)
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
int i
Definition: cfEzgcd.cc:125
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
factory's main class
Definition: canonicalform.h:83
int level() const
level() returns the level of CO.
void removeFirst()
Definition: ftmpl_list.cc:287
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: factory.h:118
int level() const
Definition: factory.h:134
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:76
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
bivariate factorization over Q(a)
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:46
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition: facBivar.h:128
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
TIMING_DEFINE_PRINT(fac_squarefree) TIMING_DEFINE_PRINT(fac_factor_squarefree) void factorizationWRTDifferentSecondVars(const CanonicalForm &A
Factorization of A wrt. to different second vars.
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:77
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CFList int bool const Variable & w
<[in] alg. variable
Definition: facFactorize.h:36
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
This file provides utility functions for bivariate factorization.
CFList tmp2
Definition: facFqBivar.cc:70
int j
Definition: facHensel.cc:105
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define A
Definition: sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026