My Project
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 #if defined(HAVE_NTL) || defined(HAVE_FLINT) // ratBiSqrfFactorize
47 /// factorize a squarefree multivariate polynomial over \f$ Q(\alpha) \f$
48 ///
49 /// @return @a ratSqrfFactorize returns a list of monic factors, the first
50 /// element is the leading coefficient.
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 #endif
71 
72 #if defined(HAVE_NTL) || defined(HAVE_FLINT) // multiFactorize, henselLiftAndEarly, nonMonicHenselLift
73 /// factorize a multivariate polynomial over \f$ Q(\alpha) \f$
74 ///
75 /// @return @a ratFactorize returns a list of monic factors with
76 /// multiplicity, the first element is the leading coefficient.
77 inline
78 CFFList
79 ratFactorize (const CanonicalForm& G, ///<[in] a multivariate poly
80  const Variable& v= Variable (1), ///<[in] algebraic variable
81  bool substCheck= true ///<[in] enables substitute check
82  )
83 {
84  if (getNumVars (G) == 2)
85  {
87  return result;
88  }
89  CanonicalForm F= G;
90 
91  if (substCheck)
92  {
93  bool foundOne= false;
94  int * substDegree= new int [F.level()];
95  for (int i= 1; i <= F.level(); i++)
96  {
97  if (degree (F, i) > 0)
98  {
99  substDegree[i-1]= substituteCheck (F, Variable (i));
100  if (substDegree [i-1] > 1)
101  {
102  foundOne= true;
103  subst (F, F, substDegree[i-1], Variable (i));
104  }
105  }
106  else
107  substDegree[i-1]= -1;
108  }
109  if (foundOne)
110  {
111  CFFList result= ratFactorize (F, v, false);
112  CFFList newResult, tmp;
114  newResult.insert (result.getFirst());
115  result.removeFirst();
116  for (CFFListIterator i= result; i.hasItem(); i++)
117  {
118  tmp2= i.getItem().factor();
119  for (int j= 1; j <= G.level(); j++)
120  {
121  if (substDegree[j-1] > 1)
122  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
123  }
124  tmp= ratFactorize (tmp2, v, false);
125  tmp.removeFirst();
126  for (CFFListIterator j= tmp; j.hasItem(); j++)
127  newResult.append (CFFactor (j.getItem().factor(),
128  j.getItem().exp()*i.getItem().exp()));
129  }
130  delete [] substDegree;
131  return newResult;
132  }
133  delete [] substDegree;
134  }
135 
136  CanonicalForm LcF= Lc (F);
137  if (isOn (SW_RATIONAL))
138  F *= bCommonDen (F);
139 
140  CFFList result;
141  TIMING_START (fac_squarefree);
142  CFFList sqrfFactors= sqrFree (F);
143  TIMING_END_AND_PRINT (fac_squarefree,
144  "time for squarefree factorization over Q: ");
145 
146  CFList tmp;
147  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
148  {
149  TIMING_START (fac_factor_squarefree);
150  tmp= ratSqrfFactorize (i.getItem().factor(), v);
151  TIMING_END_AND_PRINT (fac_factor_squarefree,
152  "time to factorize sqrfree factor over Q: ");
153  for (CFListIterator j= tmp; j.hasItem(); j++)
154  {
155  if (j.getItem().inCoeffDomain()) continue;
156  result.append (CFFactor (j.getItem(), i.getItem().exp()));
157  }
158  }
159  if (isOn (SW_RATIONAL))
160  {
161  normalize (result);
162  if (v.level() == 1)
163  {
164  for (CFFListIterator i= result; i.hasItem(); i++)
165  {
166  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
167  i.getItem()= CFFactor (i.getItem().factor()*
168  bCommonDen(i.getItem().factor()), i.getItem().exp());
169  }
170  }
171  result.insert (CFFactor (LcF, 1));
172  }
173  return result;
174 }
175 #endif
176 #endif
177 
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:132
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:946
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
factory's main class
Definition: canonicalform.h:86
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:134
int level() const
Definition: factory.h:150
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
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:47
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition: facBivar.h:129
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
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:79
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:72
int j
Definition: facHensel.cc:110
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