My Project
Loading...
Searching...
No Matches
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
22TIMING_DEFINE_PRINT (fac_squarefree)
23TIMING_DEFINE_PRINT (fac_factor_squarefree)
24
25/// Factorization of A wrt. to different second vars
26void
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
42multiFactorize (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.
51inline
53ratSqrfFactorize (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);
60 if (isOn (SW_RATIONAL))
61 F *= bCommonDen (F);
63 if (isOn (SW_RATIONAL))
64 {
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.
77inline
79ratFactorize (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 }
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
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 {
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:957
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
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: variable.h:33
int level() const
Definition: variable.h:49
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
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
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:1027
#define TIMING_DEFINE_PRINT(t)
Definition: timing.h:95
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94