My Project
Loading...
Searching...
No Matches
facBivar.h
Go to the documentation of this file.
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 **/
11/*****************************************************************************/
12
13#ifndef FAC_BIVAR_H
14#define FAC_BIVAR_H
15
16// #include "config.h"
17
18#include "cf_assert.h"
19#include "timing.h"
20
21#include "facFqBivarUtil.h"
22#include "DegreePattern.h"
23#include "cf_util.h"
24#include "facFqSquarefree.h"
25#include "cf_map.h"
26#include "cf_algorithm.h"
27#include "cfNewtonPolygon.h"
28#include "fac_util.h"
29#include "cf_algorithm.h"
30
32TIMING_DEFINE_PRINT(fac_bi_factor_sqrf)
33
34/// @return @a biFactorize returns a list of factors of F. If F is not monic
35/// its leading coefficient is not outputted.
37biFactorize (const CanonicalForm& F, ///< [in] a sqrfree bivariate poly
38 const Variable& v ///< [in] some algebraic variable
39 );
40
41/// factorize a squarefree bivariate polynomial over \f$ Q(\alpha) \f$.
42///
43/// @ return @a ratBiSqrfFactorize returns a list of monic factors, the first
44/// element is the leading coefficient.
45inline
47ratBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
48 const Variable& v= Variable (1) ///< [in] algebraic variable
49 )
50{
51 CFMap N;
53 CanonicalForm contentX= content (F, 1); //erwarte hier primitiven input: primitiv über Z bzw. Z[a]
54 CanonicalForm contentY= content (F, 2);
55 F /= (contentX*contentY);
56 CFFList contentXFactors, contentYFactors;
57 if (v.level() != 1)
58 {
59 contentXFactors= factorize (contentX, v);
60 contentYFactors= factorize (contentY, v);
61 }
62 else
63 {
64 contentXFactors= factorize (contentX);
65 contentYFactors= factorize (contentY);
66 }
67 if (contentXFactors.getFirst().factor().inCoeffDomain())
68 contentXFactors.removeFirst();
69 if (contentYFactors.getFirst().factor().inCoeffDomain())
70 contentYFactors.removeFirst();
71 if (F.inCoeffDomain())
72 {
74 for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
75 result.append (N (i.getItem().factor()));
76 for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
77 result.append (N (i.getItem().factor()));
78 if (isOn (SW_RATIONAL))
79 {
81 result.insert (Lc (G));
82 }
83 return result;
84 }
85
86 mpz_t * M=new mpz_t [4];
87 mpz_init (M[0]);
88 mpz_init (M[1]);
89 mpz_init (M[2]);
90 mpz_init (M[3]);
91
92 mpz_t * S=new mpz_t [2];
93 mpz_init (S[0]);
94 mpz_init (S[1]);
95
96 F= compress (F, M, S);
98 for (CFListIterator i= result; i.hasItem(); i++)
99 i.getItem()= N (decompress (i.getItem(), M, S));
100 for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
101 result.append (N(i.getItem().factor()));
102 for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
103 result.append (N (i.getItem().factor()));
104 if (isOn (SW_RATIONAL))
105 {
107 result.insert (Lc (G));
108 }
109
110 mpz_clear (M[0]);
111 mpz_clear (M[1]);
112 mpz_clear (M[2]);
113 mpz_clear (M[3]);
114 delete [] M;
115
116 mpz_clear (S[0]);
117 mpz_clear (S[1]);
118 delete [] S;
119
120 return result;
121}
122
123/// factorize a bivariate polynomial over \f$ Q(\alpha) \f$
124///
125/// @return @a ratBiFactorize returns a list of monic factors with
126/// multiplicity, the first element is the leading coefficient.
127inline
129ratBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
130 const Variable& v= Variable (1), ///< [in] algebraic variable
131 bool substCheck= true ///< [in] enables substitute check
132 )
133{
134 CFMap N;
136
137 if (substCheck)
138 {
139 bool foundOne= false;
140 int * substDegree= new int [F.level()];
141 for (int i= 1; i <= F.level(); i++)
142 {
143 substDegree[i-1]= substituteCheck (F, Variable (i));
144 if (substDegree [i-1] > 1)
145 {
146 foundOne= true;
147 subst (F, F, substDegree[i-1], Variable (i));
148 }
149 }
150 if (foundOne)
151 {
152 CFFList result= ratBiFactorize (F, v, false);
153 CFFList newResult, tmp;
155 newResult.insert (result.getFirst());
156 result.removeFirst();
157 for (CFFListIterator i= result; i.hasItem(); i++)
158 {
159 tmp2= i.getItem().factor();
160 for (int j= 1; j <= F.level(); j++)
161 {
162 if (substDegree[j-1] > 1)
163 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
164 }
165 tmp= ratBiFactorize (tmp2, v, false);
166 tmp.removeFirst();
167 for (CFFListIterator j= tmp; j.hasItem(); j++)
168 newResult.append (CFFactor (j.getItem().factor(),
169 j.getItem().exp()*i.getItem().exp()));
170 }
171 decompress (newResult, N);
172 delete [] substDegree;
173 return newResult;
174 }
175 delete [] substDegree;
176 }
177
178 CanonicalForm LcF= Lc (F);
179 CanonicalForm contentX= content (F, 1);
180 CanonicalForm contentY= content (F, 2);
181 F /= (contentX*contentY);
182 CFFList contentXFactors, contentYFactors;
183 if (v.level() != 1)
184 {
185 contentXFactors= factorize (contentX, v);
186 contentYFactors= factorize (contentY, v);
187 }
188 else
189 {
190 contentXFactors= factorize (contentX);
191 contentYFactors= factorize (contentY);
192 }
193 if (contentXFactors.getFirst().factor().inCoeffDomain())
194 contentXFactors.removeFirst();
195 if (contentYFactors.getFirst().factor().inCoeffDomain())
196 contentYFactors.removeFirst();
197 decompress (contentXFactors, N);
198 decompress (contentYFactors, N);
199 CFFList result, resultRoot;
200 if (F.inCoeffDomain())
201 {
202 result= Union (contentXFactors, contentYFactors);
203 if (isOn (SW_RATIONAL))
204 {
206 if (v.level() == 1)
207 {
208 for (CFFListIterator i= result; i.hasItem(); i++)
209 {
210 LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
211 i.getItem()= CFFactor (i.getItem().factor()*
212 bCommonDen(i.getItem().factor()), i.getItem().exp());
213 }
214 }
215 result.insert (CFFactor (LcF, 1));
216 }
217 return result;
218 }
219
220 mpz_t * M=new mpz_t [4];
221 mpz_init (M[0]);
222 mpz_init (M[1]);
223 mpz_init (M[2]);
224 mpz_init (M[3]);
225
226 mpz_t * S=new mpz_t [2];
227 mpz_init (S[0]);
228 mpz_init (S[1]);
229
230 F= compress (F, M, S);
231 TIMING_START (fac_bi_sqrf);
232 CFFList sqrfFactors= sqrFree (F);
233 TIMING_END_AND_PRINT (fac_bi_sqrf,
234 "time for bivariate sqrf factors over Q: ");
235 for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
236 {
237 TIMING_START (fac_bi_factor_sqrf);
238 CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
239 TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
240 "time to factor bivariate sqrf factors over Q: ");
241 for (CFListIterator j= tmp; j.hasItem(); j++)
242 {
243 if (j.getItem().inCoeffDomain()) continue;
244 result.append (CFFactor (N (decompress (j.getItem(), M, S)),
245 i.getItem().exp()));
246 }
247 }
248 result= Union (result, contentXFactors);
249 result= Union (result, contentYFactors);
250 if (isOn (SW_RATIONAL))
251 {
253 if (v.level() == 1)
254 {
255 for (CFFListIterator i= result; i.hasItem(); i++)
256 {
257 LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
258 i.getItem()= CFFactor (i.getItem().factor()*
259 bCommonDen(i.getItem().factor()), i.getItem().exp());
260 }
261 }
262 result.insert (CFFactor (LcF, 1));
263 }
264
265 mpz_clear (M[0]);
266 mpz_clear (M[1]);
267 mpz_clear (M[2]);
268 mpz_clear (M[3]);
269 delete [] M;
270
271 mpz_clear (S[0]);
272 mpz_clear (S[1]);
273 delete [] S;
274
275 return result;
276}
277
278/// convert a CFFList to a CFList by dropping the multiplicity
279CFList conv (const CFFList& L ///< [in] a CFFList
280 );
281
282/// compute p^k larger than the bound on the coefficients of a factor of @a f
283/// over Q (mipo)
284modpk
285coeffBound (const CanonicalForm & f, ///< [in] poly over Z[a]
286 int p, ///< [in] some positive integer
287 const CanonicalForm& mipo ///< [in] minimal polynomial with
288 ///< denominator 1
289 );
290
291/// find a big prime p from our tables such that no term of f vanishes mod p
292void findGoodPrime(const CanonicalForm &f, ///< [in] poly over Z or Z[a]
293 int &start ///< [in,out] index of big prime in
294 /// cf_primetab.h
295 );
296
297/// compute p^k larger than the bound on the coefficients of a factor of @a f
298/// over Z
299modpk
300coeffBound (const CanonicalForm & f, ///< [in] poly over Z
301 int p ///< [in] some positive integer
302 );
303
304#endif
305
This file provides a class to handle degree patterns.
bool isOn(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int i
Definition: cfEzgcd.cc:132
int p
Definition: cfModGcd.cc:4078
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
map polynomials
FILE * f
Definition: checklibs.c:9
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T getFirst() const
Definition: ftmpl_list.cc:279
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
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition: facBivar.cc:188
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
Definition: facBivar.cc:97
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:47
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
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 findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
Definition: facBivar.cc:61
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
This file provides functions for squarefrees factorizing over , or GF.
int j
Definition: facHensel.cc:110
operations mod p^k and some other useful functions for factorization
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define M
Definition: sirandom.c:25
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